4 ms·

Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.

simias 9y ago
It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable). That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft. One case I can come up with is if you have some code that does, say: int foo(int a) { int next = a + 1; return increment(a); } int increment(int a) { if (a == INT_MAX) { return 0; } return ++a; } In this situation if the compiler inlines "increment" it can also get rid of the "if" because it can assume that it'll always be false. If it wasn't false then "int next = a + 1" triggers UB so the compiler can do whatever it wants. Now, if this is an actual coding error, that's nasty. If however I wrote foo that way because I'm sure that "a" is a small integer with no risk of overflow then it's a fine optimization. If overflow is implementation defined then the optimization is illegal, in case of overflow "next" is implementation defined but the test should run. Note that here I put the "next = a + 1" before the call to increment, but it would still be a valid optimization if the call was done after the call to increment (with the original value of a, that is): int foo(int a) { int next, ret; ret = increment(a); next = a + 1; return ret; } UB "travels backwards in time", so to speak. If the compiler knows for a fact that "a == INT_MAX" could cause an UB anywhere in the code, it has the right to assume that it can't happen if it allows him to optimize some more.
- iainmerrick 9y ago
  So that "next = a + 1" is essentially a note to the compiler, promising that "++a" won't overflow? To me that seems really reckless! If you need that note, make it a compiler pragma or something, rather than trying to sneak it in by repurposing some existing code. Now if overflow were implementation-defined, the compiler would have to assume that INT_MAX + 1 wraps to INT_MIN (say). So as written, the "if (a == INT_MAX)" line would stay. That's what I would expect to happen on reading the code, and I'm confident that that's what most reasonable people would expect too. If you want to skip the "if (a == INT_MAX)" check, just take it out. I'm sure optimizations like this are important for squeezing a few extra percent out of the standard benchmarks. But for most ordinary programmers they're just a minefield you have to tiptoe carefully around.
  - simias 9y ago
    I wouldn't write code like this on purpose, rather I'd genuinely need "next" for some other computation and the compiler could then use that to infer that I know "a" not to overflow. If I wanted to make it an "annotation" then I'd use "assert(a < INT_MAX);" which would serve the same function to the compiler and make sense to the next coder reading it (or me in two months). Actually "assert" is probably not the right one since it could get removed with NDEBUG, but something like that. This is a very simple example of course, but maybe this "increment" code is actually used in many other parts of the codebase where the test actually makes sense. It's not rare for instance to start a C function with "if (param == NULL) return;", just in case. If the compiler inlines the function and sees that the caller dereferences "param" it can assume that it's not null and remove the test. But you're right that it makes it easy to shoot yourself in the foot. I remember a strange bug in the linux kernel source that was "hidden" by such an optimization, the code looked something like that: int bar(somestruct *ptr) { int somevalue = ptr->val; if (ptr == NULL) { return -EINVAL; } // Rest of the function here } The real code was a little more complicated than that obviously, but at a glance it might look that the function won't run if "ptr" is NULL. GCC however noticed the dereference before the test and happily decided that "of course this coder knows what they're doing, ptr can't be NULL!" and removed it. It can take a while to debug code like that.
    - iainmerrick 9y ago
      That code ought to be a compile error. "On this code path, your code assumes ptr is null and not-null at the same time!" Not all UB can be detected at compile time, but when it can be detected, it should be flagged to the user.
      - simias 9y ago
        But what if it's the result of some inlining or simply macro expansion? It's a tough call to make.
        inetknght 9y ago
- kps 9y ago
  But at the time C89 invented 'undefined behaviour', C compilers didn't (couldn't) do that. This modern interpretation simply didn't occur to anyone at the time. If it had, people would have screamed bloody murder, and the language simply would not have passed. Compare dmr's criticism of the 'noalias' proposal: “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs”. In the accompanying Rationale, the committee explicitly calls out places where the standard intentionally diverged from existing practice; they did not do so for UB. They thought “the most serious semantic change” was mandating value-preserving rather than unsigned-preserving integer promotion.
littlestymaar 9y ago
Undefined means : the compiler can omit this case and assume it never happens. Take integer overflow for instance: an implementation-defined behavior means in case of overflow the compiler can either wrap, crash, or have a saturation at max value. Undefined behavior means the compiler can assume it doesn't happen and optimize with this information in mind. For instance, the following code : for(i = 0; i<max; i++){ for(j = i; j<max; j=j*2){ //do something } } With the undefined behavior, the compiler assume that j will never overflow, which means it can re-order the loops if he wants, or unfold it, or any other optimization if he desires so. But if it takes the possible overflow into account, it cannot optimize anything since the inner loop could be an infinite loop if `max` is big enough.
- iainmerrick 9y ago
  That's a good example, thanks! Reminds me of the Java binary search bug: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://research.googleblog.com/2006/06/extra-extra-read-all... I think the correct code here would be something like: for (j = i; j <= (max+1)/2; j = j*2) Or something like that. Obviously that's rather awkward, with the risk of a sneaky off-by-one bug. (Edit to add: heh, just noticed I'm assuming max+1 won't overflow!) It would be great to have a C-like language that encourages safer code like that.
  - nayuki 9y ago
    The silver lining in that Java bug is that it is guaranteed to compute the same wrong negative indexes every time on every platform, and it is guaranteed to throw ArrayIndexOutOfBoundsException when the array is attempted to be indexed. Though the code is wrong, it is at least consistently wrong and loudly wrong. The same cannot be said for a similar bug implemented in C.
    - littlestymaar 9y ago
      Well nobody prevents you from writing a compiler that will have this exact same behavior for the C language. In practice it doesn't happen because this «good citizen» compiler will produce code being slower than GCC or Clang on all benchmark, and since nowadays people mostly use C when performance is critical, this compiler will not be used by anyone. Why even bother writing C if you all you achieve is Java, PyPy or JavaScript level in term of performance ?

It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable). That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft. One case I can come up with is if you have some code that does, say: int foo(int a) { int next = a + 1; return increment(a); } int increment(int a) { if (a == INT_MAX) { return 0; } return ++a; } In this situation if the compiler inlines "increment" it can also get rid of the "if" because it can assume that it'll always be false. If it wasn't false then "int next = a + 1" triggers UB so the compiler can do whatever it wants. Now, if this is an actual coding error, that's nasty. If however I wrote foo that way because I'm sure that "a" is a small integer with no risk of overflow then it's a fine optimization. If overflow is implementation defined then the optimization is illegal, in case of overflow "next" is implementation defined but the test should run. Note that here I put the "next = a + 1" before the call to increment, but it would still be a valid optimization if the call was done after the call to increment (with the original value of a, that is): int foo(int a) { int next, ret; ret = increment(a); next = a + 1; return ret; } UB "travels backwards in time", so to speak. If the compiler knows for a fact that "a == INT_MAX" could cause an UB anywhere in the code, it has the right to assume that it can't happen if it allows him to optimize some more.

iainmerrick 9y ago
So that "next = a + 1" is essentially a note to the compiler, promising that "++a" won't overflow? To me that seems really reckless! If you need that note, make it a compiler pragma or something, rather than trying to sneak it in by repurposing some existing code. Now if overflow were implementation-defined, the compiler would have to assume that INT_MAX + 1 wraps to INT_MIN (say). So as written, the "if (a == INT_MAX)" line would stay. That's what I would expect to happen on reading the code, and I'm confident that that's what most reasonable people would expect too. If you want to skip the "if (a == INT_MAX)" check, just take it out. I'm sure optimizations like this are important for squeezing a few extra percent out of the standard benchmarks. But for most ordinary programmers they're just a minefield you have to tiptoe carefully around.
- simias 9y ago
  I wouldn't write code like this on purpose, rather I'd genuinely need "next" for some other computation and the compiler could then use that to infer that I know "a" not to overflow. If I wanted to make it an "annotation" then I'd use "assert(a < INT_MAX);" which would serve the same function to the compiler and make sense to the next coder reading it (or me in two months). Actually "assert" is probably not the right one since it could get removed with NDEBUG, but something like that. This is a very simple example of course, but maybe this "increment" code is actually used in many other parts of the codebase where the test actually makes sense. It's not rare for instance to start a C function with "if (param == NULL) return;", just in case. If the compiler inlines the function and sees that the caller dereferences "param" it can assume that it's not null and remove the test. But you're right that it makes it easy to shoot yourself in the foot. I remember a strange bug in the linux kernel source that was "hidden" by such an optimization, the code looked something like that: int bar(somestruct *ptr) { int somevalue = ptr->val; if (ptr == NULL) { return -EINVAL; } // Rest of the function here } The real code was a little more complicated than that obviously, but at a glance it might look that the function won't run if "ptr" is NULL. GCC however noticed the dereference before the test and happily decided that "of course this coder knows what they're doing, ptr can't be NULL!" and removed it. It can take a while to debug code like that.
  - iainmerrick 9y ago
    That code ought to be a compile error. "On this code path, your code assumes ptr is null and not-null at the same time!" Not all UB can be detected at compile time, but when it can be detected, it should be flagged to the user.
    - simias 9y ago
      But what if it's the result of some inlining or simply macro expansion? It's a tough call to make.
      - inetknght 9y ago
kps 9y ago
But at the time C89 invented 'undefined behaviour', C compilers didn't (couldn't) do that. This modern interpretation simply didn't occur to anyone at the time. If it had, people would have screamed bloody murder, and the language simply would not have passed. Compare dmr's criticism of the 'noalias' proposal: “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs”. In the accompanying Rationale, the committee explicitly calls out places where the standard intentionally diverged from existing practice; they did not do so for UB. They thought “the most serious semantic change” was mandating value-preserving rather than unsigned-preserving integer promotion.

littlestymaar 9y ago

Undefined means : the compiler can omit this case and assume it never happens. Take integer overflow for instance: an implementation-defined behavior means in case of overflow the compiler can either wrap, crash, or have a saturation at max value. Undefined behavior means the compiler can assume it doesn't happen and optimize with this information in mind. For instance, the following code : for(i = 0; i<max; i++){ for(j = i; j<max; j=j*2){ //do something } } With the undefined behavior, the compiler assume that j will never overflow, which means it can re-order the loops if he wants, or unfold it, or any other optimization if he desires so. But if it takes the possible overflow into account, it cannot optimize anything since the inner loop could be an infinite loop if `max` is big enough.

iainmerrick 9y ago
That's a good example, thanks! Reminds me of the Java binary search bug: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://research.googleblog.com/2006/06/extra-extra-read-all... I think the correct code here would be something like: for (j = i; j <= (max+1)/2; j = j*2) Or something like that. Obviously that's rather awkward, with the risk of a sneaky off-by-one bug. (Edit to add: heh, just noticed I'm assuming max+1 won't overflow!) It would be great to have a C-like language that encourages safer code like that.
- nayuki 9y ago
  The silver lining in that Java bug is that it is guaranteed to compute the same wrong negative indexes every time on every platform, and it is guaranteed to throw ArrayIndexOutOfBoundsException when the array is attempted to be indexed. Though the code is wrong, it is at least consistently wrong and loudly wrong. The same cannot be said for a similar bug implemented in C.
  - littlestymaar 9y ago
    Well nobody prevents you from writing a compiler that will have this exact same behavior for the C language. In practice it doesn't happen because this «good citizen» compiler will produce code being slower than GCC or Clang on all benchmark, and since nowadays people mostly use C when performance is critical, this compiler will not be used by anyone. Why even bother writing C if you all you achieve is Java, PyPy or JavaScript level in term of performance ?