4 ms·

I think this is a point of view that seems sensible, but probably hasn't really thought through how this works. For example some_array[i] What should the co

I think this is a point of view that seems sensible, but probably hasn't really thought through how this works. For example some_array[i] What should the compiler emit here? Should it emit a bounds check? In the event the bounds check fails, what should it do? It is only through the practice of undefined behavior that the compiler can consistently generate code that avoids the bounds check. (We don't need it, because if `i` is out-of-bounds then it's undefined behavior and illegal). If you think this is bad, then you're arguing against memory unsafe languages in general. A sane position is the one the Rust takes, which is by default, yes indeed you should always generate the bounds check (unless you can prove it always succeeds). But there will likely always be hot inner loops where we need to discharge the bounds checks statically. Ideally that would be done with some kind of formal reasoning support, but the industry is far that atm. For a more in depth read: https://blog.regehr.org/archives/213 https://blog.regehr.org/archives/213

Dylan16807 2y ago
> What should the compiler emit here? It should emit an instruction to access memory location some_array + i. That's all most people that complain about optimizations on undefined behavior want. Sometimes there are questions that are hard to answer, but in a situation like this, the answer is "Try it and hope it doesn't corrupt memory." The behavior that's not wanted is for the compiler to wildly change behavior on purpose when something is undefined. For example, the compiler could optimize if(foo) { misbehaving_code(); return puppies; } else { delete_data(); } into delete_data();
- g15jv2dp 2y ago
  > It should emit an instruction to access memory location some_array + i. That's definitely what compilers emit. The UB comes from the fact that the compiler cannot guarantee how the actual memory will respond to that. Will the OS kill you? Will your bare metal MCU silently return garbage? Will you corrupt your program state and jump into branches that should never be reached? Who knows. You're advocating for wild behavior but you don't even realize it. As for your example. No, the compiler couldn't optimize like that. You seem to have some misconceptions about UB. If foo is false in your code, then the behavior is completely defined.
  - Dylan16807 2y ago
    > If foo is false in your code, then the behavior is completely defined. That's the point. If foo is false, both versions do the same thing. If foo is true, then it's undefined and it doesn't matter. Therefore, assume foo is false. Remove the branch.
    - myrryr 2y ago
      Yes! This is exactly the point. It is undefined, so given that, it could do what the other branch does, so you can safely remove that branch. you get it, but a lot of other people don't understand just how undefined, undefined code is.
      - SonOfLilit 2y ago
        We do. We just wish undefined was defined to be a bit less undefined, and are willing to sacrifice a bit of performance for higher debuggability an. ability to reason.
        uecker 2y ago
        Why not use -fsanitize=signed-integer-overflow ?
      - Dylan16807 2y ago
        It could do what the other branch does, in theory. But let me put it this way. If you only had the misbehaving_code(); line by itself, the compiler would rightly be called crazy and malicious if it compiled that to delete_data(); So maybe it's not reasonable to treat both branches as having the same behavior, even if you can.
- tialaramex 2y ago
  > That's all most people that complain about optimizations on undefined behavior want If this was true most of them could just adopt Rust where of course this isn't a problem. But in fact they're often vehemently against Rust. They like C and C++ where they can write total nonsense which has no meaning but it compiles and then they can blame the compiler for not reading their mind and doing whatever it is they thought it "obviously" should do.
  - II2II 2y ago
    I could be wrong here since I don't develop compilers, but from my understanding many of the undefined behaviours in C are the product of not knowing what the outcome will be for edge cases or due to variations in processor architecture. In these cases, undefined behaviour was intended as a red flag for application developers. Many application developers ended up treating the undefined behaviours as deterministic provided that certain conditions were met. On the other hand, compiler developers took undefined behaviour to mean they could do what they wanted, generating different results in different circumstance, thus violating the expectations of application developers.
    - robinsonb5 2y ago
      I think the problem is that some behaviours are undefined where developers expect them to be implementation-defined (especially in C's largest remaining stronghold, the embedded world) - i.e. do what makes sense on this particular CPU. Signed overflow is the classic example - making that undefined rather than implementation-defined is a decision that makes less to those of us living in today's exclusively two's-complement world than it would have done when it was taken. It's become more of an issue in recent years as compilers started doing more advanced optimisations, which some people perceived as the compiler being "lawful evil". What it reminds me of is that episode of Red Dwarf with Kryten (with his behavioural chip disabled) explaining why he thought it was OK to serve roast human to the crew: "If you eat chicken then obviously you'd eat your own species too, otherwise you'd just be picking on the chickens"!
- cobbal 2y ago
  Ah, but what if it writes so far off the array that it messes with the contents of another variable on the stack that is currently cached in a register? Should the compiler reload that register because the out of bounds write might have updated it? Probably not, let's just assume they didn't mean to do that and use the in-register version. That's taking advantage of undefined behavior to optimize a program.
  - Dylan16807 2y ago
    > Ah, but what if it writes so far off the array that it messes with the contents of another variable on the stack that is currently cached in a register? Should the compiler reload that register because the out of bounds write might have updated it? Probably not, let's just assume they didn't mean to do that and use the in-register version. Yes, go ahead and assume it won't alias outside the rules of C and hope it works out. > That's taking advantage of undefined behavior to optimize a program. I don't know if I really agree with that, but even taking that as true, that's fine. The objection isn't to doing any optimizations. Assuming memory didn't get stomped is fine. Optimizations that significantly change program flow in the face of misbehavior and greatly amplify it are painful. And lots of things are in the middle.
- opnitro 2y ago
  I think the "do the normal" thing is very easy to say and very hard to do in general. Should every case of `a / b` inject a `(b != 0) && ((a != INT_MAX && b != -1))`? If that evaluates to `true` then what should the program do? Or: should the compiler assume this can't happen. Languages with rich runtimes get around this by having an agreed upon way to signal errors, at the expense of runtime checking. An example directly stolen from the linked blog post: int stupid (int a) { return (a+1) > a; } What should the compiler emit for this? Should it check for overflow, or should it emit the asm equivalent of `return 1`? If your answer is check for overflow: then should the compiler be forced to check for overflow every time it increments an integer in a for loop? If your answer is don't check: then how do you explain this function behaving completely weird in the overflow case? The point I'm trying to get at is that "do the obvious thing" is completely dependent on context.
  - tsimionescu 2y ago
    The compiler should emit the code to add one to a, and then code to check if the result is greater than a. This is completely evident, and is what all C and C++ compilers did for the first few decades of their existence. Maybe a particularly smart compiler could issue a `jo` instead of a `cmp ax, bx; jz `. The for loop example is silly. There is no reason whatsoever to add an overflow check in a for loop. The code of a standard for loop, `for (int i = 0; i < n; i++)` doesn't say to do any overflow check, so why would the compiler insert one? Not inserting overflow checks is completely different than omitting overflow checks explicitly added in the code. Not to mention, for this type of loop, the compiler doesn't need any UB-based logic to prove that the loop terminates - for any possible value of n, including INT_MAX, this loop will terminate, assuming `i` is not modified elsewhere. I'd also note that the "most correct" type to use for the iteration variable in a loop used to access an array, per the standard, would be `size_t`, which is an unsigned type, which does allow overflow to happen. The standard for loop should be `for (size_t i = 0; i < n; ++i)`, which doesn't allow the compiler to omit any overflow checks, even if any were present.
    - mgaunard 2y ago
      The interesting case is what should the code do if inlined on a code path where a is deduced to be INT_MAX. A compiler will just avoid inlining any code here, since it's not valid, and thus by definition that branch cannot be taken, removing cruft that would impact the instruction cache.
- uecker 2y ago
  Why not just turn off (or down) optimizations? I mean, optimization is not even activated by default
  - andrewaylett 2y ago
    Unfortunately it's not necessarily specified what counts as "an optimisation". For example, the (DSP-related) compiler I worked on back in the day had an instruction selection pass, and much of the performance of optimised code came from it being a very good instruction selector. "Turning off optimisations" meant not running compiler passes that weren't required in order to generate code, we didn't have a second sub-optimal instruction selector. And undefined behaviour is still undefined behaviour without all the optimisation passes turned on.

Dylan16807 2y ago

> What should the compiler emit here? It should emit an instruction to access memory location some_array + i. That's all most people that complain about optimizations on undefined behavior want. Sometimes there are questions that are hard to answer, but in a situation like this, the answer is "Try it and hope it doesn't corrupt memory." The behavior that's not wanted is for the compiler to wildly change behavior on purpose when something is undefined. For example, the compiler could optimize if(foo) { misbehaving_code(); return puppies; } else { delete_data(); } into delete_data();

g15jv2dp 2y ago
> It should emit an instruction to access memory location some_array + i. That's definitely what compilers emit. The UB comes from the fact that the compiler cannot guarantee how the actual memory will respond to that. Will the OS kill you? Will your bare metal MCU silently return garbage? Will you corrupt your program state and jump into branches that should never be reached? Who knows. You're advocating for wild behavior but you don't even realize it. As for your example. No, the compiler couldn't optimize like that. You seem to have some misconceptions about UB. If foo is false in your code, then the behavior is completely defined.
- Dylan16807 2y ago
  > If foo is false in your code, then the behavior is completely defined. That's the point. If foo is false, both versions do the same thing. If foo is true, then it's undefined and it doesn't matter. Therefore, assume foo is false. Remove the branch.
  - myrryr 2y ago
    Yes! This is exactly the point. It is undefined, so given that, it could do what the other branch does, so you can safely remove that branch. you get it, but a lot of other people don't understand just how undefined, undefined code is.
    - SonOfLilit 2y ago
      We do. We just wish undefined was defined to be a bit less undefined, and are willing to sacrifice a bit of performance for higher debuggability an. ability to reason.
      - uecker 2y ago
        Why not use -fsanitize=signed-integer-overflow ?
    - Dylan16807 2y ago
      It could do what the other branch does, in theory. But let me put it this way. If you only had the misbehaving_code(); line by itself, the compiler would rightly be called crazy and malicious if it compiled that to delete_data(); So maybe it's not reasonable to treat both branches as having the same behavior, even if you can.
tialaramex 2y ago
> That's all most people that complain about optimizations on undefined behavior want If this was true most of them could just adopt Rust where of course this isn't a problem. But in fact they're often vehemently against Rust. They like C and C++ where they can write total nonsense which has no meaning but it compiles and then they can blame the compiler for not reading their mind and doing whatever it is they thought it "obviously" should do.
- II2II 2y ago
  I could be wrong here since I don't develop compilers, but from my understanding many of the undefined behaviours in C are the product of not knowing what the outcome will be for edge cases or due to variations in processor architecture. In these cases, undefined behaviour was intended as a red flag for application developers. Many application developers ended up treating the undefined behaviours as deterministic provided that certain conditions were met. On the other hand, compiler developers took undefined behaviour to mean they could do what they wanted, generating different results in different circumstance, thus violating the expectations of application developers.
  - robinsonb5 2y ago
    I think the problem is that some behaviours are undefined where developers expect them to be implementation-defined (especially in C's largest remaining stronghold, the embedded world) - i.e. do what makes sense on this particular CPU. Signed overflow is the classic example - making that undefined rather than implementation-defined is a decision that makes less to those of us living in today's exclusively two's-complement world than it would have done when it was taken. It's become more of an issue in recent years as compilers started doing more advanced optimisations, which some people perceived as the compiler being "lawful evil". What it reminds me of is that episode of Red Dwarf with Kryten (with his behavioural chip disabled) explaining why he thought it was OK to serve roast human to the crew: "If you eat chicken then obviously you'd eat your own species too, otherwise you'd just be picking on the chickens"!
cobbal 2y ago
Ah, but what if it writes so far off the array that it messes with the contents of another variable on the stack that is currently cached in a register? Should the compiler reload that register because the out of bounds write might have updated it? Probably not, let's just assume they didn't mean to do that and use the in-register version. That's taking advantage of undefined behavior to optimize a program.
- Dylan16807 2y ago
  > Ah, but what if it writes so far off the array that it messes with the contents of another variable on the stack that is currently cached in a register? Should the compiler reload that register because the out of bounds write might have updated it? Probably not, let's just assume they didn't mean to do that and use the in-register version. Yes, go ahead and assume it won't alias outside the rules of C and hope it works out. > That's taking advantage of undefined behavior to optimize a program. I don't know if I really agree with that, but even taking that as true, that's fine. The objection isn't to doing any optimizations. Assuming memory didn't get stomped is fine. Optimizations that significantly change program flow in the face of misbehavior and greatly amplify it are painful. And lots of things are in the middle.
opnitro 2y ago
I think the "do the normal" thing is very easy to say and very hard to do in general. Should every case of `a / b` inject a `(b != 0) && ((a != INT_MAX && b != -1))`? If that evaluates to `true` then what should the program do? Or: should the compiler assume this can't happen. Languages with rich runtimes get around this by having an agreed upon way to signal errors, at the expense of runtime checking. An example directly stolen from the linked blog post: int stupid (int a) { return (a+1) > a; } What should the compiler emit for this? Should it check for overflow, or should it emit the asm equivalent of `return 1`? If your answer is check for overflow: then should the compiler be forced to check for overflow every time it increments an integer in a for loop? If your answer is don't check: then how do you explain this function behaving completely weird in the overflow case? The point I'm trying to get at is that "do the obvious thing" is completely dependent on context.
- tsimionescu 2y ago
  The compiler should emit the code to add one to a, and then code to check if the result is greater than a. This is completely evident, and is what all C and C++ compilers did for the first few decades of their existence. Maybe a particularly smart compiler could issue a `jo` instead of a `cmp ax, bx; jz `. The for loop example is silly. There is no reason whatsoever to add an overflow check in a for loop. The code of a standard for loop, `for (int i = 0; i < n; i++)` doesn't say to do any overflow check, so why would the compiler insert one? Not inserting overflow checks is completely different than omitting overflow checks explicitly added in the code. Not to mention, for this type of loop, the compiler doesn't need any UB-based logic to prove that the loop terminates - for any possible value of n, including INT_MAX, this loop will terminate, assuming `i` is not modified elsewhere. I'd also note that the "most correct" type to use for the iteration variable in a loop used to access an array, per the standard, would be `size_t`, which is an unsigned type, which does allow overflow to happen. The standard for loop should be `for (size_t i = 0; i < n; ++i)`, which doesn't allow the compiler to omit any overflow checks, even if any were present.
  - mgaunard 2y ago
    The interesting case is what should the code do if inlined on a code path where a is deduced to be INT_MAX. A compiler will just avoid inlining any code here, since it's not valid, and thus by definition that branch cannot be taken, removing cruft that would impact the instruction cache.
uecker 2y ago
Why not just turn off (or down) optimizations? I mean, optimization is not even activated by default
- andrewaylett 2y ago
  Unfortunately it's not necessarily specified what counts as "an optimisation". For example, the (DSP-related) compiler I worked on back in the day had an instruction selection pass, and much of the performance of optimised code came from it being a very good instruction selector. "Turning off optimisations" meant not running compiler passes that weren't required in order to generate code, we didn't have a second sub-optimal instruction selector. And undefined behaviour is still undefined behaviour without all the optimisation passes turned on.