3 ms·

What's odd about that example is that the optimization is only valid if the loop in fact overflows the array every time. So the compiler is proving that the arr

What's odd about that example is that the optimization is only valid if the loop in fact overflows the array every time. So the compiler is proving that the array is being overflowed and rather than emitting a warning to that effect, it generates absurd code.

kllrnohj 3y ago
> So the compiler is proving that the array is being overflowed and rather than emitting a warning to that effect <source>:5:13: warning: unsafe buffer access [-Wunsafe-buffer-usage] 5 | if (table[i] == v) return true; | ^~~~~ https://godbolt.org/z/zGxnKxvz6 https://godbolt.org/z/zGxnKxvz6 This one is weirdly hard to get a compiler warning out of which is a fair critque, but so many of the "Look what the compiler did to my UB silently!" issues are not at all silent and would have been stopped dead with "-Wall -Wextra -Werror"
- iainmerrick 3y ago
  As noted elsewhere in this thread, GCC by default does the "optimization" and doesn't warn. No doubt there are other examples where Clang is the one that misbehaves. How are we supposed to know whether our code is being compiled sensibly or not, without poring over the disassembly? Just set all the warning flags and hope for the best?
  - UncleMeat 3y ago
    I think that a big problem is that for every compile that seems "not sensible" and is actually not sensible, there are 100s or 1000s of compiles that would look absolutely insane to a human but are actually exactly what you want when you sit down and think about it for a long time. Almost all of the "don't do the overly clever stuff!" proposals would throw away a huge amount of actually productive clever stuff.
    - fluoridation 3y ago
      I think what the GP means by "not sensible" is that proving that the code is broken in order to silently optimize it more aggressively is not sensible. If your theorem proven can find a class of bugs then have it emit diagnostics. Don't only use those bugs to make the code run faster. Yes, make the code run faster, but let me know I may be doing something nonsensical, since chances are that it is nonsensical and it doesn't cost anything at run time.
      - UncleMeat 3y ago
        Right and the next part is the hard part: defining this clearly. What I'm saying is that there is a surprising amount of "wait, actually I do want that" when you dig into this proposal.
        fluoridation 3y ago
        A reasonable compiler would let you turn off a specific warning for a section of code.
        torstenvl 3y ago
        They pretty much all do. #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wwhatever" // code #pragma clang diagnostic pop
        fluoridation 3y ago
        I was going to comment that GCC doesn't, but it seems it was added as some point since the last time I checked. I know at one time GCC had as a policy not to allow doing that.
        torstenvl 3y ago
        Here's an example: https://pastebin.com/raw/fH0Lj2Zb https://pastebin.com/raw/fH0Lj2Zb
  - moefh 3y ago
    > whether our code is being compiled sensibly or not I'm failing to see what's not sensible about how that code is compiled. The only possible way that function could return false is if you read past the end of the array and the value there happens to be different from `v`. Is it really the more sensible to rely on that, rather than fixing a known behavior in case of array overflow?
    - robinsonb5 3y ago
      If the compiler's going to interpret undefined behaviour as license to do something that runs counter to the programmer's expectations, the most sensible course of action is for the compiler to yell very loudly about it instead of near-silently producing (differently!) broken code. Currently that piece of code doesn't trigger a warning with -Wall. It's not even flagged with -Wextra - it needs -Weverything.
      - moefh 3y ago
        One man's "broken code produced by the compiler" is another man's "excellently optimized code by the compiler". Where to draw the line is not always clear, but here's a very clear-cut example[1] where emitting a warning would be bad. If you don't want to watch the video, it's basically this: - the code technically contains undefined behavior, but it will never be actually triggered by the program - changing the code to remove undefined behavior forces the compiler to emit terrible code Making the compiler yell at the programmer in this case would be terrible, but it's clearly a consequence of what you're asking. [1] https://youtu.be/yG1OZ69H_-o?t=2358 https://youtu.be/yG1OZ69H_-o?t=2358
        jeffbee 3y ago
        Exactly. I think a lot of this noise is by non-practitioners of the language. The compiler is steel-manning this loop. It is generously interpreting the 4 as irrelevant, and deducing that the loop must always exit early. The author can’t possibly have meant to access beyond the end, because that’s not defined. QED. It seems altogether sensible to me.
  - uecker 3y ago
    I agree there should be a warning. But it is not trivial to teach a compiler when to warn or not to not generate too many false positives. Not as good as warning, but UBSan catches this at run-time: https://godbolt.org/z/Mdjn7h8dj https://godbolt.org/z/Mdjn7h8dj
- bondant 3y ago
  I am not sure this warning is proving any overflow, you can get the same warning by just accessing table[i]. https://godbolt.org/z/Gxd3rK9Ts https://godbolt.org/z/Gxd3rK9Ts
fanf2 3y ago
No, the logic for the optimization is: - a correct program does not access table[4] - therefore the loop must always exit early - the only way to exit early is to return true
- toxicdevil 3y ago
  int table[4]; bool exists_in_table(int v) { for (int i = 0; i <= 4; i++) { if (table[i] == v) return true; } return false; } i -> 0 goto return true or next iter i -> 1 goto return true or next iter i -> 2 goto return true or next iter i -> 3 goto return true or next iter i -> 4 goto return true or exit loop and return false Since the branch in on undef behavior it is okay for the compiler to choose any branch destination or none at all (i.e. remove all further code). The compiler in this case likely chose to just remove the branch and any destinations. All that the prior code does is return true, since there is no next iter, so thats all what is left.
tedunangst 3y ago
No, the compiler knows the array isn't overflowed, because C programs don't contain overflows. Therefore the loop must exit via one of the return true statements.
Joker_vD 3y ago
> What's odd about that example is that the optimization is only valid if the loop in fact overflows the array every time. No, the optimization is valid if the function is always called with "v" that is actually exists in the table; in this case the function should always return true so it's only proper for the compiler to throw out the extraneous code. And writing the loop in such way is programmer's promise/guarantee to the compiler that the function will indeed be called only in that manner. That's the essence of the UB: it's the programmer who promises to the compiler that she will perform all the necessary checks (or formal proofs of impossibilty) herself; the compiler may go forward and rely on the implied invariants and preconditions. And this is, of course, the main problem of the UB because 95% of the time the programmer does not actually intend to make such a gurantee: she simply is unaware (for whatever reason) that there is a pre-condition (checked by nobody!) that's required for the program's correctness to hold... or it's even just a typo she made.
gpderetta 3y ago
No, the compiler is proving that the return true statement must be executed given the axiom that the loop cannot overflow. This is tricky, because the code is perfectly valid if it always early-exit (and I have written code like this myself that avoids bound checking by guaranteeing an early exit, when micro-optimizing), so it is hard to statically reject it. On the other hand it seems a very obvious thing to warn on.

kllrnohj 3y ago

> So the compiler is proving that the array is being overflowed and rather than emitting a warning to that effect <source>:5:13: warning: unsafe buffer access [-Wunsafe-buffer-usage] 5 | if (table[i] == v) return true; | ^~~~~ https://godbolt.org/z/zGxnKxvz6 https://godbolt.org/z/zGxnKxvz6 This one is weirdly hard to get a compiler warning out of which is a fair critque, but so many of the "Look what the compiler did to my UB silently!" issues are not at all silent and would have been stopped dead with "-Wall -Wextra -Werror"

iainmerrick 3y ago
As noted elsewhere in this thread, GCC by default does the "optimization" and doesn't warn. No doubt there are other examples where Clang is the one that misbehaves. How are we supposed to know whether our code is being compiled sensibly or not, without poring over the disassembly? Just set all the warning flags and hope for the best?
- UncleMeat 3y ago
  I think that a big problem is that for every compile that seems "not sensible" and is actually not sensible, there are 100s or 1000s of compiles that would look absolutely insane to a human but are actually exactly what you want when you sit down and think about it for a long time. Almost all of the "don't do the overly clever stuff!" proposals would throw away a huge amount of actually productive clever stuff.
  - fluoridation 3y ago
    I think what the GP means by "not sensible" is that proving that the code is broken in order to silently optimize it more aggressively is not sensible. If your theorem proven can find a class of bugs then have it emit diagnostics. Don't only use those bugs to make the code run faster. Yes, make the code run faster, but let me know I may be doing something nonsensical, since chances are that it is nonsensical and it doesn't cost anything at run time.
    - UncleMeat 3y ago
      Right and the next part is the hard part: defining this clearly. What I'm saying is that there is a surprising amount of "wait, actually I do want that" when you dig into this proposal.
      - fluoridation 3y ago
        A reasonable compiler would let you turn off a specific warning for a section of code.
        torstenvl 3y ago
        They pretty much all do. #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wwhatever" // code #pragma clang diagnostic pop
        fluoridation 3y ago
        I was going to comment that GCC doesn't, but it seems it was added as some point since the last time I checked. I know at one time GCC had as a policy not to allow doing that.
        torstenvl 3y ago
        Here's an example: https://pastebin.com/raw/fH0Lj2Zb https://pastebin.com/raw/fH0Lj2Zb
- moefh 3y ago
  > whether our code is being compiled sensibly or not I'm failing to see what's not sensible about how that code is compiled. The only possible way that function could return false is if you read past the end of the array and the value there happens to be different from `v`. Is it really the more sensible to rely on that, rather than fixing a known behavior in case of array overflow?
  - robinsonb5 3y ago
    If the compiler's going to interpret undefined behaviour as license to do something that runs counter to the programmer's expectations, the most sensible course of action is for the compiler to yell very loudly about it instead of near-silently producing (differently!) broken code. Currently that piece of code doesn't trigger a warning with -Wall. It's not even flagged with -Wextra - it needs -Weverything.
    - moefh 3y ago
      One man's "broken code produced by the compiler" is another man's "excellently optimized code by the compiler". Where to draw the line is not always clear, but here's a very clear-cut example[1] where emitting a warning would be bad. If you don't want to watch the video, it's basically this: - the code technically contains undefined behavior, but it will never be actually triggered by the program - changing the code to remove undefined behavior forces the compiler to emit terrible code Making the compiler yell at the programmer in this case would be terrible, but it's clearly a consequence of what you're asking. [1] https://youtu.be/yG1OZ69H_-o?t=2358 https://youtu.be/yG1OZ69H_-o?t=2358
      - jeffbee 3y ago
        Exactly. I think a lot of this noise is by non-practitioners of the language. The compiler is steel-manning this loop. It is generously interpreting the 4 as irrelevant, and deducing that the loop must always exit early. The author can’t possibly have meant to access beyond the end, because that’s not defined. QED. It seems altogether sensible to me.
- uecker 3y ago
  I agree there should be a warning. But it is not trivial to teach a compiler when to warn or not to not generate too many false positives. Not as good as warning, but UBSan catches this at run-time: https://godbolt.org/z/Mdjn7h8dj https://godbolt.org/z/Mdjn7h8dj
bondant 3y ago
I am not sure this warning is proving any overflow, you can get the same warning by just accessing table[i]. https://godbolt.org/z/Gxd3rK9Ts https://godbolt.org/z/Gxd3rK9Ts

fanf2 3y ago

No, the logic for the optimization is: - a correct program does not access table[4] - therefore the loop must always exit early - the only way to exit early is to return true

toxicdevil 3y ago
int table[4]; bool exists_in_table(int v) { for (int i = 0; i <= 4; i++) { if (table[i] == v) return true; } return false; } i -> 0 goto return true or next iter i -> 1 goto return true or next iter i -> 2 goto return true or next iter i -> 3 goto return true or next iter i -> 4 goto return true or exit loop and return false Since the branch in on undef behavior it is okay for the compiler to choose any branch destination or none at all (i.e. remove all further code). The compiler in this case likely chose to just remove the branch and any destinations. All that the prior code does is return true, since there is no next iter, so thats all what is left.

tedunangst 3y ago

No, the compiler knows the array isn't overflowed, because C programs don't contain overflows. Therefore the loop must exit via one of the return true statements.

Joker_vD 3y ago

> What's odd about that example is that the optimization is only valid if the loop in fact overflows the array every time. No, the optimization is valid if the function is always called with "v" that is actually exists in the table; in this case the function should always return true so it's only proper for the compiler to throw out the extraneous code. And writing the loop in such way is programmer's promise/guarantee to the compiler that the function will indeed be called only in that manner. That's the essence of the UB: it's the programmer who promises to the compiler that she will perform all the necessary checks (or formal proofs of impossibilty) herself; the compiler may go forward and rely on the implied invariants and preconditions. And this is, of course, the main problem of the UB because 95% of the time the programmer does not actually intend to make such a gurantee: she simply is unaware (for whatever reason) that there is a pre-condition (checked by nobody!) that's required for the program's correctness to hold... or it's even just a typo she made.

gpderetta 3y ago

No, the compiler is proving that the return true statement must be executed given the axiom that the loop cannot overflow. This is tricky, because the code is perfectly valid if it always early-exit (and I have written code like this myself that avoids bound checking by guaranteeing an early exit, when micro-optimizing), so it is hard to statically reject it. On the other hand it seems a very obvious thing to warn on.