5 ms·

We need a -Wundefined-behavior, which can be used in combination with -Werror. It is a practically impossible job to be so aware of the standard while working t

by jononor 10y ago

We need a -Wundefined-behavior, which can be used in combination with -Werror. It is a practically impossible job to be so aware of the standard while working to get this right without assistance.

masklinn 10y ago
> We need a -Wundefined-behavior, which can be used in combination with -Werror. The problem is that you probably won't be able to use any optimising compiler if you do that. As a result of a bunch of optimisation (mainly inlining) the compiler "uncovers" lots of UBs which it can use to pare down the code, that's why inlining is one of the most important intermediate/early optimisation. Here's an old example by mikeash: int ComputeStuff(int *value) { if(value == NULL) { long and complex computation for a NULL value return result } else { long and complex computation using the data pointed to by value return result } } void DoStuff(int *value) { int pointedTo = *value; // value *must* be non-NULL // do some work with pointedTo int computedResult = ComputeStuff(value); // do some more work with whatever } Here the compiler can inline ComputeStuff, at which point it can rely on UB to assert that half the inlined code is dead and can remove it. What would it even do on "-Werror -Wundefined-behavior", fault on the original DoStuff? On the inlined one? On both? Would -Wundefined-behaviour forbid assuming a pointer is non-null ever, requiring (and outputting) a check before each use of a pointer in a given scope/lifetime?
- jononor 10y ago
  For such inlining optimization it is the compiler that 'introduces' the UB in its intermediate step. That is not a fault of the input code, so no warning should be emitted? If the compiler can know that the pointer is non-null, why would it need to rely on UB to optimize it? Problem I guess is the ever-present possibility of pointer aliasing and such nearly allowing anything to change anything else at any time... Not easy making things more sound on such a foundation.
  - derf_ 10y ago
    If the compiler can know that the pointer is non-null, why would it need to rely on UB to optimize it? You've got this backwards. The compilers "knows" the pointer is non-null because you dereferenced it, and dereferencing null would have been undefined behavior. That's what allows the compiler to assume that didn't happen. There are many operations which will produce undefined behavior for some inputs (e.g., every pointer dereference, every signed integer arithmetic operation). Figuring out if it is possible for a program to encounter such inputs at runtime is equivalent to the halting problem. This is why any attempt to craft a -Wundefined-behavior that works on non-trivial programs is doomed to failure. It may be possible to prove a program will definitely invoke undefined behavior in some useful subset of cases. Compilers already do this in some of them, even. But those cases (and many more, besides) would also be caught with ubsan and a unit test.
    - jononor 10y ago
      You're right, it is an intractable problem in general. I guess just use Rust if one cares about this..
  - masklinn 10y ago
    > For such inlining optimization it is the compiler that 'introduces' the UB in its intermediate step. Technically the UB is in the original code, it's the dereferencing of a pointer without checking it. The compiler can merely use that to assert dead code (checking for a null pointer after having already deref'd the pointer is nonsensical) and optimise it away.
    - jononor 10y ago
      I don't support this unsafe compiler behavior. There should be a check on the pointer in sight, or a manual declaration that "this is safe, trust me". Otherwise, emit a UB warning...
      - adrianN 10y ago
        Then you want to use a different language. Java for example throws NullPointerException instead of having UB for null pointer accesses.
- Asooka 10y ago
  > Would -Wundefined-behaviour forbid assuming a pointer is non-null ever, requiring (and outputting) a check before each use of a pointer in a given scope/lifetime Either emit the if, or throw an error that the code is internally inconsistent. I mean, it IS inconsistent - first it dereferences the pointer, then it checks if it's NULL or not! This is pretty much obviously an error! I'd much rather add a bunch of assert(value != NULL); to my code to signal to the compiler that yes, this pointer is really not NULL within this scope, than have to deal with the current UB-hell. Another acceptable alternative would be to rewrite the if(value == NULL) branch to call terminate() since if we get there, then the program has executed UB and cannot continue. Since UB is rare, we can even arrange things such that the branch doesn't slow down the CPU in the general case.
  - zAy0LfpBZLC8mAC 10y ago
    > This is pretty much obviously an error! No, in most cases that's the result of defensive programming and macros or inlining, where there is a perfectly useful sanity check in some inlined function, but the compiler can see that in some specific context where it was inlined, the check is actually redundant, and thus removes it. > Since UB is rare, we can even arrange things such that the branch doesn't slow down the CPU in the general case. It's an additional instruction, so it always has the potential to slow the code down, if only because it makes the code bigger than the cache. Also, it's usually not one such branch, but lots and lots of them throughout the program. That's why the optimizer tries to eliminate them.
Manishearth 10y ago
The presence of UB is not statically detectable. Global analysis may help, but it's probably reducible to the halting problem. (of course, you can detect some common mistakes, which is what many analysis tools do) UB is not a property of the local code. It's a property of the code and the values you feed to it. Without explicit annotations of contracts you won't be able to statically detect this for C/C++. At runtime UBSan exists to detect this.
- kbenson 10y ago
  This isn't about statically detecting undefined behavior in general, it's about using detected undefined behavior to make assumptions that don't play well with later stages in the optimization pipeline. Deciding that a statement must be true because otherwise it would contain undefined behavior (which is assuming the developer won't cause undefined behavior), and then using it's truthiness to elide the check the developer included to attempt to make sure they weren't causing undefined behavior is some contorted reasoning that I'm confident isn't something that compiler authors decided specifically should be included, but instead is an unfortunate interaction between two separate aspects of compilation.
  - Manishearth 10y ago
    I don't think it's that clear cut. It's not "an unfortunate interaction between two separate aspects of compilation", it's how it's supposed to work -- the optimizer gathers invariants about the control flow and then makes optimizations based on it. The problem here is that the intent of the code is not something the optimizer can pick up on. Regular bounds check elimination works pretty much exactly the same way.
    - kbenson 10y ago
      There is a difference between whether something is an invariant based entirely on mathematical properties and rules that the compiler ensures, and one that also includes expected programmer behavior. In this case, the optimizer made an assumption that required the programmer to have ensured than an addition could not overflow, otherwise it would be undefined behavior. The compiler assuming that holds as true when it isn't necessarily so (and in this case was not so), is a problem. Optimizations that assume a programmer was diligent enough to follow those rules should not be attempted, period, if they result in the removal of some code (or possibly ever, just to be safe). That's not to say those optimization are forever lost to us. It just requires the programmer be more careful about the actions they take such that no assumptions need be made. For example, if you are adding two types which could cause an overflow, and overflows are undefined, you can cast and use larger types, or rely on compiler knowledge. Examples of that might be casting in the comparison or casting to larger types earlier on and not modifying it prior to comparison, in which case a sufficiently smart compiler might infer that since it was an unsigned char originally and you haven't modified it since you casted it to an unsigned int, while its type is actually an unsigned int, for comparisons of overflow detection for optimization you can treat it as an unsigned char.

by jononor 10y ago

We need a -Wundefined-behavior, which can be used in combination with -Werror. It is a practically impossible job to be so aware of the standard while working to get this right without assistance.

masklinn 10y ago

> We need a -Wundefined-behavior, which can be used in combination with -Werror. The problem is that you probably won't be able to use any optimising compiler if you do that. As a result of a bunch of optimisation (mainly inlining) the compiler "uncovers" lots of UBs which it can use to pare down the code, that's why inlining is one of the most important intermediate/early optimisation. Here's an old example by mikeash: int ComputeStuff(int *value) { if(value == NULL) { long and complex computation for a NULL value return result } else { long and complex computation using the data pointed to by value return result } } void DoStuff(int *value) { int pointedTo = *value; // value *must* be non-NULL // do some work with pointedTo int computedResult = ComputeStuff(value); // do some more work with whatever } Here the compiler can inline ComputeStuff, at which point it can rely on UB to assert that half the inlined code is dead and can remove it. What would it even do on "-Werror -Wundefined-behavior", fault on the original DoStuff? On the inlined one? On both? Would -Wundefined-behaviour forbid assuming a pointer is non-null ever, requiring (and outputting) a check before each use of a pointer in a given scope/lifetime?

jononor 10y ago
For such inlining optimization it is the compiler that 'introduces' the UB in its intermediate step. That is not a fault of the input code, so no warning should be emitted? If the compiler can know that the pointer is non-null, why would it need to rely on UB to optimize it? Problem I guess is the ever-present possibility of pointer aliasing and such nearly allowing anything to change anything else at any time... Not easy making things more sound on such a foundation.
- derf_ 10y ago
  If the compiler can know that the pointer is non-null, why would it need to rely on UB to optimize it? You've got this backwards. The compilers "knows" the pointer is non-null because you dereferenced it, and dereferencing null would have been undefined behavior. That's what allows the compiler to assume that didn't happen. There are many operations which will produce undefined behavior for some inputs (e.g., every pointer dereference, every signed integer arithmetic operation). Figuring out if it is possible for a program to encounter such inputs at runtime is equivalent to the halting problem. This is why any attempt to craft a -Wundefined-behavior that works on non-trivial programs is doomed to failure. It may be possible to prove a program will definitely invoke undefined behavior in some useful subset of cases. Compilers already do this in some of them, even. But those cases (and many more, besides) would also be caught with ubsan and a unit test.
  - jononor 10y ago
    You're right, it is an intractable problem in general. I guess just use Rust if one cares about this..
- masklinn 10y ago
  > For such inlining optimization it is the compiler that 'introduces' the UB in its intermediate step. Technically the UB is in the original code, it's the dereferencing of a pointer without checking it. The compiler can merely use that to assert dead code (checking for a null pointer after having already deref'd the pointer is nonsensical) and optimise it away.
  - jononor 10y ago
    I don't support this unsafe compiler behavior. There should be a check on the pointer in sight, or a manual declaration that "this is safe, trust me". Otherwise, emit a UB warning...
    - adrianN 10y ago
      Then you want to use a different language. Java for example throws NullPointerException instead of having UB for null pointer accesses.
Asooka 10y ago
> Would -Wundefined-behaviour forbid assuming a pointer is non-null ever, requiring (and outputting) a check before each use of a pointer in a given scope/lifetime Either emit the if, or throw an error that the code is internally inconsistent. I mean, it IS inconsistent - first it dereferences the pointer, then it checks if it's NULL or not! This is pretty much obviously an error! I'd much rather add a bunch of assert(value != NULL); to my code to signal to the compiler that yes, this pointer is really not NULL within this scope, than have to deal with the current UB-hell. Another acceptable alternative would be to rewrite the if(value == NULL) branch to call terminate() since if we get there, then the program has executed UB and cannot continue. Since UB is rare, we can even arrange things such that the branch doesn't slow down the CPU in the general case.
- zAy0LfpBZLC8mAC 10y ago
  > This is pretty much obviously an error! No, in most cases that's the result of defensive programming and macros or inlining, where there is a perfectly useful sanity check in some inlined function, but the compiler can see that in some specific context where it was inlined, the check is actually redundant, and thus removes it. > Since UB is rare, we can even arrange things such that the branch doesn't slow down the CPU in the general case. It's an additional instruction, so it always has the potential to slow the code down, if only because it makes the code bigger than the cache. Also, it's usually not one such branch, but lots and lots of them throughout the program. That's why the optimizer tries to eliminate them.

Manishearth 10y ago

The presence of UB is not statically detectable. Global analysis may help, but it's probably reducible to the halting problem. (of course, you can detect some common mistakes, which is what many analysis tools do) UB is not a property of the local code. It's a property of the code and the values you feed to it. Without explicit annotations of contracts you won't be able to statically detect this for C/C++. At runtime UBSan exists to detect this.

kbenson 10y ago
This isn't about statically detecting undefined behavior in general, it's about using detected undefined behavior to make assumptions that don't play well with later stages in the optimization pipeline. Deciding that a statement must be true because otherwise it would contain undefined behavior (which is assuming the developer won't cause undefined behavior), and then using it's truthiness to elide the check the developer included to attempt to make sure they weren't causing undefined behavior is some contorted reasoning that I'm confident isn't something that compiler authors decided specifically should be included, but instead is an unfortunate interaction between two separate aspects of compilation.
- Manishearth 10y ago
  I don't think it's that clear cut. It's not "an unfortunate interaction between two separate aspects of compilation", it's how it's supposed to work -- the optimizer gathers invariants about the control flow and then makes optimizations based on it. The problem here is that the intent of the code is not something the optimizer can pick up on. Regular bounds check elimination works pretty much exactly the same way.
  - kbenson 10y ago
    There is a difference between whether something is an invariant based entirely on mathematical properties and rules that the compiler ensures, and one that also includes expected programmer behavior. In this case, the optimizer made an assumption that required the programmer to have ensured than an addition could not overflow, otherwise it would be undefined behavior. The compiler assuming that holds as true when it isn't necessarily so (and in this case was not so), is a problem. Optimizations that assume a programmer was diligent enough to follow those rules should not be attempted, period, if they result in the removal of some code (or possibly ever, just to be safe). That's not to say those optimization are forever lost to us. It just requires the programmer be more careful about the actions they take such that no assumptions need be made. For example, if you are adding two types which could cause an overflow, and overflows are undefined, you can cast and use larger types, or rely on compiler knowledge. Examples of that might be casting in the comparison or casting to larger types earlier on and not modifying it prior to comparison, in which case a sufficiently smart compiler might infer that since it was an unsigned char originally and you haven't modified it since you casted it to an unsigned int, while its type is actually an unsigned int, for comparisons of overflow detection for optimization you can treat it as an unsigned char.