4 ms·

The compiler causing undefined behavior on its own reminds me of one of the fun bugs we found[1] with 32-bit x86 clang where one compiler pass fools another int

The compiler causing undefined behavior on its own reminds me of one of the fun bugs we found[1] with 32-bit x86 clang where one compiler pass fools another into thinking there's an undefined behavior by combining three struct field initializations into a single 4-byte load, but the struct itself was 3-bytes long. Another pass looked at this and thought there's an undefined behavior writing past the struct boundary, silently eliminating the initialization altogether, resulting in bad codegen. [1]: https://mehrdad.afshari.me/pubs/compiler-validation-via-equivalence-modulo-inputs.pdf https://mehrdad.afshari.me/pubs/compiler-validation-via-equi...

slededit 11y ago
Compilers are way too overzealous eliminating code because of undefined behavior. Legally it is allowed and I'm sure it helps in synthetic benchmarks. But writers of real programs won't be impressed of the perf gains when you stop running half their program.
- kazinator 11y ago
  Rather, they are getting zealous in eliminating code because of the assumption that there is no undefined behavior. The scope of what undefined behaviors do this is increasing and that breaks programs that make some assumptions on traditional compiler behavior, or that have hidden bugs. I believe that C should have safer semantics, plus standard-defined modes of operation which restore the unsafe semantics selectively. The optimizer then must obey whichever semantics in effect (safer or less safe). Then, in addition to telling your compiler you want a certain optimization level, you could tell it which standard-defined modes of operation you would like. Currently, this is already de facto the case outside of the standard. For instance, users of GCC who want to do certain pointer aliasing without unpredictable behavior tell the compiler to be in a mode in which that is allowed (effectively an altered C dialect) using -fno-strict-aliasing. This kind of thing should be a standard, portable feature. Look, everywhere in this program, I want nice left-to-right evaluation within all expressions and among initializers and function arguments. Except in super-fast.c; when compiling super-fast.c to super-fast.o, please do it in a mode where unspecified-evaluation-order semantics applies and optimize accordingly. (I might even want this on a more finer-grained scale than translation units.) We need safety, and we need to sometimes throw away safe semantics in exchange for better speed (whereby we still ensure that the code we are writing is correct with regard to the weakened semantics; i.e. we promise to the compiler that even if it relaxes the evaluation order, or whatever, we know what we are doing and everything is cool). It would be good to do this without compiler-specific guesswork. Optimization control alone over a language with a single set of semantics (which is largely unsafe) is a bad way to achieve this.
  - slededit 11y ago
    I agree you should be able to opt-in to a safety level. For example most programmers do expect signed integer overflows to follow 2s compliment behavior - regardless of what the standard says. There really seems to be a large disconnect between the tool writers and the users of said tools. I've had countless discussions with compiler writers where we've essentially talked passed each other. The compiler writer arguing from a legalistic (and dare I say moral perspective) that the programmer must not write undefined code, and myself from the perspective that developers do write undefined code and we should therefore find a way to handle it in a safe way. Perhaps even by standardizing more than we do currently. In reflection its not unlike the drug legalization debate.
    - jeffdavis 11y ago
      Keep in mind that the compiler doesn't always know whether code is undefined or not. Is x+y at risk of overflow? Maybe, depending on some logic in a separate compilation unit. So what your asking is to define behavior for all code, such that the compiler can prove locally that's it's well-defined. That's not a crazy idea, and a lot of languages do that. But C counts itself as special, for better or worse. I think we really just need more alternatives. There's C++, Rust, Ada, and not much else. I am very hopeful about rust.
      - kazinator 11y ago
        The problem is that C compilers don't bother proving anything, when it comes to taking advantage of what is defined. For instance, if x is signed, a C compiler can assume that x + 1 produces a value which is greater than x, and optimize accordingly. It's up to the programmer (and failing that, user) to ensure that x is less than INT_MAX prior to the execution of that x + 1. In fact there is a proof involved, but it is trivial. The compiler assumes that x + 1 > x because, by logical inference, the only way this can be false is if x == INT_MAX. But in that case, the behavior of x + 1 is undefined, and so, who cares about that; it is the programmer's responsibility that this is not the case. Q.E.D. Rather than require compilers to implement complicated proofs, which essentially consists of a whole lot of work whose end result is only to curtail optimizations, it's far simpler to have ways in the language to tweak the semantics. If there is a safe mode in which x + 1 is well-defined, even if x is INT_MAX, then the compiler can no longer assume that x + 1 > x. That assumption is simply off the table. (Now the difficult work of proof kicks in if you still want the same optimization: the compiler can still optimize on the assumption that x + 1 > x, but that assumption can be false, yet x + 1 can be well-defined! If an assumption can be false in correct code, then you have hard work to do: you must prove the assumption true before relying on it.) This safe mode is not linked to optimization level. Unless turned off by the programmer, it is in effect regardless of optimization level. Right now we have a situation in which compiler optimization or "code generation" options are used for controlling safety. Programmers know that de facto these options affect the actual semantics of C code, and so they get used that way. We know that if we tell GCC "-fno-strict-aliasing", we are not simply defeating some optimizations, but we are in effect requesting a C dialect in which cases of certain aliasing are well defined. This is a poor situation. Why? Because it's nonportable (the next compiler you use after GCC might not have this option). But, more importantly, semantics and optimization must be decoupled from each other. We pin down the semantics we want from the language (we pin down what is well-defined), and then optimization preserves that semantics: whatever is well-defined behaves the same way regardless of how hard we optimize. Semantics and optimization have to be independently controlled. That is how you can eat your cake and have it too. If you think some code benefits from an optimization which assumes that x + 1 > x, you just compile that under suitable semantics. Then if you don't ensure x < INT_MAX, it's really your fault: you explicitly chose a mode in which things break if you don't ensure that, and then you didn't ensure that.

slededit 11y ago

Compilers are way too overzealous eliminating code because of undefined behavior. Legally it is allowed and I'm sure it helps in synthetic benchmarks. But writers of real programs won't be impressed of the perf gains when you stop running half their program.

kazinator 11y ago
Rather, they are getting zealous in eliminating code because of the assumption that there is no undefined behavior. The scope of what undefined behaviors do this is increasing and that breaks programs that make some assumptions on traditional compiler behavior, or that have hidden bugs. I believe that C should have safer semantics, plus standard-defined modes of operation which restore the unsafe semantics selectively. The optimizer then must obey whichever semantics in effect (safer or less safe). Then, in addition to telling your compiler you want a certain optimization level, you could tell it which standard-defined modes of operation you would like. Currently, this is already de facto the case outside of the standard. For instance, users of GCC who want to do certain pointer aliasing without unpredictable behavior tell the compiler to be in a mode in which that is allowed (effectively an altered C dialect) using -fno-strict-aliasing. This kind of thing should be a standard, portable feature. Look, everywhere in this program, I want nice left-to-right evaluation within all expressions and among initializers and function arguments. Except in super-fast.c; when compiling super-fast.c to super-fast.o, please do it in a mode where unspecified-evaluation-order semantics applies and optimize accordingly. (I might even want this on a more finer-grained scale than translation units.) We need safety, and we need to sometimes throw away safe semantics in exchange for better speed (whereby we still ensure that the code we are writing is correct with regard to the weakened semantics; i.e. we promise to the compiler that even if it relaxes the evaluation order, or whatever, we know what we are doing and everything is cool). It would be good to do this without compiler-specific guesswork. Optimization control alone over a language with a single set of semantics (which is largely unsafe) is a bad way to achieve this.
- slededit 11y ago
  I agree you should be able to opt-in to a safety level. For example most programmers do expect signed integer overflows to follow 2s compliment behavior - regardless of what the standard says. There really seems to be a large disconnect between the tool writers and the users of said tools. I've had countless discussions with compiler writers where we've essentially talked passed each other. The compiler writer arguing from a legalistic (and dare I say moral perspective) that the programmer must not write undefined code, and myself from the perspective that developers do write undefined code and we should therefore find a way to handle it in a safe way. Perhaps even by standardizing more than we do currently. In reflection its not unlike the drug legalization debate.
  - jeffdavis 11y ago
    Keep in mind that the compiler doesn't always know whether code is undefined or not. Is x+y at risk of overflow? Maybe, depending on some logic in a separate compilation unit. So what your asking is to define behavior for all code, such that the compiler can prove locally that's it's well-defined. That's not a crazy idea, and a lot of languages do that. But C counts itself as special, for better or worse. I think we really just need more alternatives. There's C++, Rust, Ada, and not much else. I am very hopeful about rust.
    - kazinator 11y ago
      The problem is that C compilers don't bother proving anything, when it comes to taking advantage of what is defined. For instance, if x is signed, a C compiler can assume that x + 1 produces a value which is greater than x, and optimize accordingly. It's up to the programmer (and failing that, user) to ensure that x is less than INT_MAX prior to the execution of that x + 1. In fact there is a proof involved, but it is trivial. The compiler assumes that x + 1 > x because, by logical inference, the only way this can be false is if x == INT_MAX. But in that case, the behavior of x + 1 is undefined, and so, who cares about that; it is the programmer's responsibility that this is not the case. Q.E.D. Rather than require compilers to implement complicated proofs, which essentially consists of a whole lot of work whose end result is only to curtail optimizations, it's far simpler to have ways in the language to tweak the semantics. If there is a safe mode in which x + 1 is well-defined, even if x is INT_MAX, then the compiler can no longer assume that x + 1 > x. That assumption is simply off the table. (Now the difficult work of proof kicks in if you still want the same optimization: the compiler can still optimize on the assumption that x + 1 > x, but that assumption can be false, yet x + 1 can be well-defined! If an assumption can be false in correct code, then you have hard work to do: you must prove the assumption true before relying on it.) This safe mode is not linked to optimization level. Unless turned off by the programmer, it is in effect regardless of optimization level. Right now we have a situation in which compiler optimization or "code generation" options are used for controlling safety. Programmers know that de facto these options affect the actual semantics of C code, and so they get used that way. We know that if we tell GCC "-fno-strict-aliasing", we are not simply defeating some optimizations, but we are in effect requesting a C dialect in which cases of certain aliasing are well defined. This is a poor situation. Why? Because it's nonportable (the next compiler you use after GCC might not have this option). But, more importantly, semantics and optimization must be decoupled from each other. We pin down the semantics we want from the language (we pin down what is well-defined), and then optimization preserves that semantics: whatever is well-defined behaves the same way regardless of how hard we optimize. Semantics and optimization have to be independently controlled. That is how you can eat your cake and have it too. If you think some code benefits from an optimization which assumes that x + 1 > x, you just compile that under suitable semantics. Then if you don't ensure x < INT_MAX, it's really your fault: you explicitly chose a mode in which things break if you don't ensure that, and then you didn't ensure that.