5 ms·

TFA is misunderstanding. As he cites from the C standard, “Undefined behavior gives the implementor license not to catch certain program errors that are difficu

by layer8 2y ago

TFA is misunderstanding. As he cites from the C standard, “Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose.” Since it’s difficult (and even, in the general case of runtime conditions, impossible at compile time) to diagnose, the implementor (compiler writer) has two choices: (a) assume that the undefined behavior doesn’t occur, and implement optimizations under that assumption, or (b) nevertheless implement a defined behavior for it, which in many cases amounts to a pessimization. Given that competition between compilers is driven by benchmarks, guess which option compiler writers are choosing. The discussions in comp.lang.c (a Usenet newsgroup, not a mailing list) were educating C programmers that they can’t rely on (b) in portable C, and moreover, can’t make any assumptions about undefined behavior in portable C, because the C specification (the standard) explicitly refrains from imposing any requirements whatsoever on the C implementation in that case. The additional thing to understand is that compiler writers are not malevolently detecting undefined behavior and then inserting optimizations in that case, but instead that applying optimizations is a process of logical deduction within the compiler, and that it is the lack of assumptions related to undefined behavior being put into the compiler implementation, that is leading to surprising consequences if undefined behavior actually occurs. This is also the reason why undefined behavior can affect code executing prior to the occurrence of the undefined condition, because logical deduction as performed by the compiler is not restricted to the forward direction of control flow (and also because compilers reorder code as a consequence of their analysis).

nothrabannosir 2y ago
> This is also the reason why undefined behavior can affect code executing prior to the occurrence of the undefined condition, because logical deduction as performed by the compiler is not restricted to the forward direction of control flow (and also because compilers reorder code as a consequence of their analysis). According to Martin Uecker, of the C standard comittee, that is not true: > In C, undefined behavior can not time travel. This was never supported by the wording and we clarified this in C23. https://news.ycombinator.com/item?id=40790203 https://news.ycombinator.com/item?id=40790203
- layer8 2y ago
  It is really hard to prevent this in an optimizing compiler. I don’t think it’s realistic. For example, loop invariants can be affected by undefined behavior in the loop body, and that in turn can affect the code that is generated for a loop condition at the start of the loop, whose execution precedes the loop body. This is a general consequence in static code analysis. Even more so with whole-program optimization.
  - ordu 2y ago
    Maybe I don't understand something, but for me it seems pretty easy. What is needed to be done: 1. Make a list of all UB 2. Define the sensible compiler behavior in each case (for example, let MAX_INT+1 to calculate into MIN_INT on x86_64, just because `add` on x86_64 does that) 3. Treat this as a part of a standard, when compiling the code. This approach allows to have different compiler behavior on different architectures, which are better suited for the architecture. Maybe on some architectures `add` on signed numbers will generate a CPU exception on overflow, so define this as a way to behave and go with it.
    - twoodfin 2y ago
      The requirement for “sensible” (i.e. repeatable) behavior breaks many simple, critical optimizations like maintaining the referent of a nominally un-aliased pointer in a register. What if there’s UB & it is aliased? Some other pointer of a different type in scope also references the same value. The “sensible” thing to do when the value is updated through the alias is…?
    - cokernel_hacker 2y ago
      That works for a lot of behavior but not everything. For example: int f(int x) { static int y[] = {42, 43}; return y[x]; } What behavior should `f(-1)` or `f(100)` have? What is sensible?
      - Y_Y 2y ago
        Desugar to pointer arithmetic, try to do an dereference like *(y-1) and more than likely segfault, or return the value at that address if it's somehow valid.
torstenvl 2y ago
> the implementor (compiler writer) has two choices: (a) assume that the undefined behavior doesn’t occur, and implement optimizations under that assumption, or (b) nevertheless implement a defined behavior for it, which in many cases amounts to a pessimization. No. The implementor has three choices: (1) Ignore the situation altogether; (2) behave according to documentation (with or without a warning); or (3) issue an error and stop compilation. Consider for (int i=0; i>=0; i++); (1) Doesn't attempt to detect UB, it just ignores UB and generates the straightforward translation mov 0, %l0 loop: cmp %l0, 0 bge loop add %l0, 1, %l0 ! Delay slot ! Continue with rest of program (2) May detect that would result in integer overflow and do something it documents (like a trap instruction, or run the whole loop, or elide the whole loop). (3) Detects that would result in integer overflow and stops compilation with an error message. An expressio unius interpretation—or simply following the well-worn principle of construing ambiguity against the drafter—would not permit crazy things with UB that many current compilers do.
- cokernel_hacker 2y ago
  What behavior should the following have: int f(int x) { switch (x) { case 0: return 31; case 1: return 28; case 2: return 30; } } This code on its own has no undefined behavior. In another translation unit, someone calls `f(3)`. What would you have compilers do in that case? That path through the program has undefined behavior. However, the two translation units are separate and as such normal tooling will not be able to detect any sort of UB without some kind of whole program static analysis or heavy instrumentation which would harm performance.
  - torstenvl 2y ago
    I would do what the standard tells me to do, which is to ignore the undefined behavior if I don't detect it. On most platforms, that would probably result in the return value of 3 (it would still be in AX, EAX, r0, x0, o0/i0, whatever, when execution hits the ret instruction or whatever that ISA/ABI uses to mark the end of the function). But it would be undefined. But that's fine. [EDIT: I misremembered the x86 calling convention, so my references to AX and EAX are wrong above. Mea culpa.] What isn't fine is ignoring the end of the function, not emitting a ret instruction, and letting execution fall through to the next label/function, which is what I suspect GCC does.
SAI_Peregrinus 2y ago
> implementor (compiler writer) has two choices: (a) assume that the undefined behavior doesn’t occur, and implement optimizations under that assumption, or (b) nevertheless implement a defined behavior for it, which in many cases amounts to a pessimization. No, they have two choices: (a) assume that the undefined behavior doesn't occur, and implement any output code generation whatsoever under that assumption, or (b) define a behavior for it, and implement output code generation based on that assumption which in many cases amounts to a pessimization. Optimization isn't relevant. Assuming it can't happen and then continuing to generate code as though it can't happen is all that matters. You can't make any assumptions, including that disabling optimization will change the output code.

by layer8 2y ago

nothrabannosir 2y ago

> This is also the reason why undefined behavior can affect code executing prior to the occurrence of the undefined condition, because logical deduction as performed by the compiler is not restricted to the forward direction of control flow (and also because compilers reorder code as a consequence of their analysis). According to Martin Uecker, of the C standard comittee, that is not true: > In C, undefined behavior can not time travel. This was never supported by the wording and we clarified this in C23. https://news.ycombinator.com/item?id=40790203 https://news.ycombinator.com/item?id=40790203

layer8 2y ago
It is really hard to prevent this in an optimizing compiler. I don’t think it’s realistic. For example, loop invariants can be affected by undefined behavior in the loop body, and that in turn can affect the code that is generated for a loop condition at the start of the loop, whose execution precedes the loop body. This is a general consequence in static code analysis. Even more so with whole-program optimization.
- ordu 2y ago
  Maybe I don't understand something, but for me it seems pretty easy. What is needed to be done: 1. Make a list of all UB 2. Define the sensible compiler behavior in each case (for example, let MAX_INT+1 to calculate into MIN_INT on x86_64, just because `add` on x86_64 does that) 3. Treat this as a part of a standard, when compiling the code. This approach allows to have different compiler behavior on different architectures, which are better suited for the architecture. Maybe on some architectures `add` on signed numbers will generate a CPU exception on overflow, so define this as a way to behave and go with it.
  - twoodfin 2y ago
    The requirement for “sensible” (i.e. repeatable) behavior breaks many simple, critical optimizations like maintaining the referent of a nominally un-aliased pointer in a register. What if there’s UB & it is aliased? Some other pointer of a different type in scope also references the same value. The “sensible” thing to do when the value is updated through the alias is…?
  - cokernel_hacker 2y ago
    That works for a lot of behavior but not everything. For example: int f(int x) { static int y[] = {42, 43}; return y[x]; } What behavior should `f(-1)` or `f(100)` have? What is sensible?
    - Y_Y 2y ago
      Desugar to pointer arithmetic, try to do an dereference like *(y-1) and more than likely segfault, or return the value at that address if it's somehow valid.

torstenvl 2y ago

> the implementor (compiler writer) has two choices: (a) assume that the undefined behavior doesn’t occur, and implement optimizations under that assumption, or (b) nevertheless implement a defined behavior for it, which in many cases amounts to a pessimization. No. The implementor has three choices: (1) Ignore the situation altogether; (2) behave according to documentation (with or without a warning); or (3) issue an error and stop compilation. Consider for (int i=0; i>=0; i++); (1) Doesn't attempt to detect UB, it just ignores UB and generates the straightforward translation mov 0, %l0 loop: cmp %l0, 0 bge loop add %l0, 1, %l0 ! Delay slot ! Continue with rest of program (2) May detect that would result in integer overflow and do something it documents (like a trap instruction, or run the whole loop, or elide the whole loop). (3) Detects that would result in integer overflow and stops compilation with an error message. An expressio unius interpretation—or simply following the well-worn principle of construing ambiguity against the drafter—would not permit crazy things with UB that many current compilers do.

cokernel_hacker 2y ago
What behavior should the following have: int f(int x) { switch (x) { case 0: return 31; case 1: return 28; case 2: return 30; } } This code on its own has no undefined behavior. In another translation unit, someone calls `f(3)`. What would you have compilers do in that case? That path through the program has undefined behavior. However, the two translation units are separate and as such normal tooling will not be able to detect any sort of UB without some kind of whole program static analysis or heavy instrumentation which would harm performance.
- torstenvl 2y ago
  I would do what the standard tells me to do, which is to ignore the undefined behavior if I don't detect it. On most platforms, that would probably result in the return value of 3 (it would still be in AX, EAX, r0, x0, o0/i0, whatever, when execution hits the ret instruction or whatever that ISA/ABI uses to mark the end of the function). But it would be undefined. But that's fine. [EDIT: I misremembered the x86 calling convention, so my references to AX and EAX are wrong above. Mea culpa.] What isn't fine is ignoring the end of the function, not emitting a ret instruction, and letting execution fall through to the next label/function, which is what I suspect GCC does.

SAI_Peregrinus 2y ago

> implementor (compiler writer) has two choices: (a) assume that the undefined behavior doesn’t occur, and implement optimizations under that assumption, or (b) nevertheless implement a defined behavior for it, which in many cases amounts to a pessimization. No, they have two choices: (a) assume that the undefined behavior doesn't occur, and implement any output code generation whatsoever under that assumption, or (b) define a behavior for it, and implement output code generation based on that assumption which in many cases amounts to a pessimization. Optimization isn't relevant. Assuming it can't happen and then continuing to generate code as though it can't happen is all that matters. You can't make any assumptions, including that disabling optimization will change the output code.