10 ms·

If ((uint32_t)x<<32)==x on one system, and ((uint32_t)x<<32)==0 on another, why is that a problem? The issue isn't that one system behaves differently from anot

• tormeh 11y ago
  The, to me, obvious thing to do with code with undefined behaviour is to emit an error and refuse to compile it. Programmers should never rely on undefined behaviour. Then again, I think languages shouldn't have undefined behaviour and that programmers who use languages with undefined behaviour deserve what they get.
  • caf 11y ago
    In the most interesting cases, it can't reasonably be detected at compile-time anyway. See also here: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
  • daurnimator 11y ago
    It's usually only at runtime rather than compile time that such situations arise. At runtime we have the clang and gcc undefined behaviour sanitizers, but they aren't free in terms of performance.
  • scott_s 11y ago
    The problem, as Regehr (the author of this submission) has pointed out many times before, is more subtle than that. Because certain behavior is considered undefined, compilers are allowed to assume the code it is compiling is well defined, and optimize accordingly. That can cause simple bugs to have mysterious effects. For example: a->thing = 42; if (a == NULL) { return; } Obviously that code is wrong; I should check for NULL before using a. But because I dereferenced a, the compiler can assume a must not be NULL, and just removes the null check as dead code. This scenario has caused problems in the kernel, and made bad bugs even worse.
    • tamana 11y ago
      But the compiler could just as well emit a warning "useless NULL comparison" instead of blithely assuming that the programmer intentionally wrote a book expression. That wouldn't handle every case of UB, but would handle many.
      • superuser2 11y ago
        A warning on removed dead code isn't helpful because dead come is legitimately removed all the time. No one would ever heed it.
        • slavik81 11y ago
          If you ignored dead code produced by macros and limited the check to function-scope, I think you'd mostly eliminate false positives.
• caf 11y ago
  If the standard writers had wanted to, they could have specified that a shift by an amount as wide or wider than the type had an "implementation-defined result", which is used elsewhere (for example, right-shifting a negative value gives an implementation-defined result).
  • to3m 11y ago
    Yes. And that would make sense. They might not insist on exactly this, but they already leave this sort of possibility open by suggesting that undefined behaviour could result in the program behaving "in a documented manner characteristic of the environment". If the standard writers' hands were tied by having to cater for every system they'd ever heard of, even the stupid ones where shifting by 32 (or whatever) results in rand() (or whatever) - implementers' hands are not! They have only one system to think about! If that system happens to be one of the stupid ones - well, anybody working on it will have exactly the same problem. But if it isn't one of the stupid ones - why do they insist that their users should behave as if it is?
• viraptor 11y ago
  Probably because it would go in the same direction as multiple-dialects proposal. If we can have bcc-x86 that returns x ans bcc-arm that returns 0, then we'll likely end up with bcc-x86-fullshifting-nounaligned-nullcheckremoveok-otheroptions and 10 dialects that switch some of those behaviours. If you're designing a well-defined language, then why make it well-defined-per-architecture?
  • to3m 11y ago
    But the standard already permits this. I'm just suggesting that rather than have compiler writers use these liberties to allow their compiler to remove code or make it do something peculiar, they could just allow it to do the natural thing for the target platform. (This is explicitly allowed by the standard. Consult its definition of undefined behaviour.) Why not create a compiler that does what your users want? Why spend your time creating a stick to beat them with?
    • bcoates 11y ago
      Because the overwhelming majority of users of C compilers are compiling someone else's code that isn't narrowly targeted to the platform+compiler in question. So they get no benefit at all from specifying undefined behavior, but they do get a benefit from the performance gained by assuming away undefined behavior as dead cases.
      • barrkel 11y ago
        they do get a benefit from the performance gained by assuming away undefined behavior as dead cases I think this is a highly suspicious assumption. Programmers don't write code for no reason; they have a mental model of the current state of parameters and variables, and establish invariants as they write loops and conditionals. If you're going to start throwing out chunks of code the programmer wrote, you need to be certain - not merely unsure, but certain - that the code is dead. Infectious undefined values that propagate through data flow to break code flow isn't a sane programming environment.
• cygx 11y ago
  What modern interpretation? As long as C has been standardized, undefined behaviour has meant nasal demons. There's an argument to be had that some undefined behaviour should rather be unspecified or implementation-defined, but compilers making use of it for aggressive optimization? That's by design. Quoting another article by John Regehr: My view is that exploiting undefined behavior can sometimes be OK if a good debugging tool is available to find the undefined behavior. Thus -fsanitize=undefined.
  • to3m 11y ago
    Undefined behaviour has meant undefined behaviour. That doesn't mean nasal demons. That means this: Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). Permit me to suggest that when there is a choice between making things behave in a documented manner characteristic of the environment, or something else - don't go for the something else.
    • cygx 11y ago
      the Standard imposes no requirements on undefined behaviour. The list you quoted is informative, to give us a basic idea what to possibly expect, not a list of things we may rely upon. Rejecting translation outright aside, undefined behaviour is the strongest language the standard uses for illegal constructs. I do not see it as undefined in the sense of lacking a common definition (eg is 0 a natural number, or not) but something that is undefined the way 0/0 is undefined in maths. In a way, the criticized behaviour of aggressively opimizing compilers is a consequence of ignoring the situation completely with unpredictable results. It's the same line of reasoning that makes restrict useful, just on steroids.
      • to3m 11y ago
        Well I submit that as a simple question of quality of implementation, implementers should try their hardest to go for the something that behaves "in a documented manner characteristic of the platform"! But instead, they seem to pick something else. And I claim that this is not helpful to their users, who would be far better served by the characteristic-of-the-platform option.
• jws 11y ago
  Apparently a (uint32_t) shifted by 32 is license to become completely insane. int main(int argc, char **argv) { uint32_t x = (uint32_t)0x12345678<<(uint32_t)32; printf("x<<32 = %x\n", x ); } (Almost all compilers make a warning about the shift size) gcc 4.9.2 on Debian x86: 0x0 gcc 4.9.2 on Debian x86, -O3: 0x0 clang 3.6 on Debian x86: 0x0 clang 3.7 on Debian x86: 0x0 gcc 4.9.2 on Raspbian ARM: 0x0 tcc 0.9.27 on Raspbian ARM: 0x0 NO WARNING tcc 0.9.27 on Debian x86: Segmentation fault NO WARNING clang on El Capitan: 0x5a788cb0 clang on El Capitan, -O3: 0x54049be8
  • to3m 11y ago
    I am almost LOLing at the segmentation fault. Where the fuck does a segmentation fault come from? It's shifting a value. Utterly mystifying.
    • ars 11y ago
      Maybe it's a hardware trap and not a regular null reference segmentation fault?
      • pcwalton 11y ago
        Well, shl doesn't trap on x86 for out of range values; it just masks the second operand by 0x1f [1]. But it could be some other kind of trap. Complete guess in the dark: tcc misencoded an instruction causing an illegal instruction trap, maybe in some sort of misguided attempt to optimize the shift to a lea. [1]: http://x86.renejeschke.de/html/file_module_x86_id_285.html http://x86.renejeschke.de/html/file_module_x86_id_285.html
        • Filligree 11y ago
          Wouldn't that normally produce SIGILL, not SIGSEGV?
    • userbinator 11y ago
      Looking at the generated instructions might give a clue, but I'm just as mystified. Given the size of the program, I doubt there's much of it to inspect anyway.
• overgard 11y ago
  I think the problem is that some of these optimizations aren't just compiler makers being greedy, they're actually a huge benefit. IMO what's missing is the ability to mark areas "unsafe" -- IE, tell the compiler "it's ok to take advantage of certain optimizations here" while marking other areas "please don't goof with this" (ie, security critical code). You can kind of do this with pragmas, but not really. Here's a good example from the llvm blog: ( http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... ) > Signed integer overflow: If arithmetic on an 'int' type (for example) overflows, the result is undefined. One example is that "INT_MAX+1" is not guaranteed to be INT_MIN. This behavior enables certain classes of optimizations that are important for some code. For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X". While these may seem trivial, these sorts of things are commonly exposed by inlining and macro expansion. A more important optimization that this allows is for "<=" loops like this: > for (i = 0; i <= N; ++i) { ... } > In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations.
  • userbinator 11y ago
    For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". If a programmer writes "X+1 > X", chances are this is an overflow check. Doing this is perfectly defined by the standard if X is an unsigned integer, but not if it's signed. That's what doesn't make sense, since they could've made the unsigned case undefined as well. which allows a broad range of loop optimizations to kick in What sort of optimisations exactly, and just how significant are they? I don't believe C should be a language where the compiler does all sorts of high-level optimisation; it should be a straightforward "do what I say" type of language where you get almost exactly what you write, and the only optimisations should be at the level of things like instruction selection --- the optimisations that a programmer would not be able to do at the source level.
• pcwalton 11y ago
  > But why can't it just produce something different on each system? It could. That is indeed how Rust, for example, defines it. But in C "unspecified values" have a way of turning into undefined behavior really quickly. Here's an actual bug we have in Rust [1]: let index = 1.04E+17 as u8; let array = vec![1, 2, 3, 4, 5]; println!("{}", array[index as usize]); // segfault Why does that segfault instead of emitting a safe panic? Because the IR looks something roughly like this (in C notation): double tmp = 1.04e+17; uint8_t index = (uint8_t)tmp; vector *array = make_a_vector(); if (index >= array->length) panic(); printf("%d\n", array->ptr[index]); The optimizer correctly determines that the cast from double to uint8_t results in an undefined value. In LLVM terminology, undefined values can arbitrarily change value over their live range, and this is allowed per the C specification. So LLVM is allowed to replace the conditional "index >= array->length" with "false", and this is indeed what it does, leading to this code: double tmp = 1.04e+17; uint8_t index = (uint8_t)tmp; vector *array = make_a_vector(); printf("%d\n", array->ptr[index]); And with that, LLVM optimizes out our bounds check, and safe code is able to perform arbitrary memory reads and writes. Note that all we needed was an unspecified value resulting from a floating point cast! The fix is probably going to be to stop using LLVM's floating point conversion instructions and to instead use some "safe conversion" intrinsics that we'll define. > What compilers do today should be the recourse of absolute last resort, and the sort of thing that makes its authors feel bad. But it seems to be treated as a matter of course. I don't know what to say. You might think that I would think this way too after fighting bugs like the above, but I actually don't. I appreciate the performance that undefined behavior brings to C, and I think we'd have much slower programs without it. Undefined behavior resulting from strict aliasing is the reason why a for loop setting an array to zero can optimize to a 10x faster memset, for example. And heavily inlined series of functions, as well as generic libraries like the C++ STL, frequently require these optimizations to get reasonable performance. I think it's not an exaggeration to say that much of the software performance we take for granted—stuff you care about, like codecs, games, browser implementations—is the result of optimizations that are enabled by undefined behavior. [1]: https://github.com/rust-lang/rust/issues/10184 https://github.com/rust-lang/rust/issues/10184
  • nly 11y ago
    For anyone wondering: double -> uintx_t is indeed undefined in C and C++ for values outside of (0, UINTx_MAX), which is kind of a gotcha since, double -> long -> uint8_t is fine (assuming all integer parts of double fit in a long).
• legulere 11y ago
  It's a problem because that will lead to bugs. You write code on x86, it works for years and then you let it run on ARM and it will misbehave. If it weren't a problem, then the compiler doing whatever it wants also wouldn't be a problem. IMO the best thing would be if the compiler would insert code to print to screen a warning and exit the program, if it comes across undefined behaviour. (This is different from sanitizers, that check for all places whether undefined behaviour will occur).
  • zAy0LfpBZLC8mAC 11y ago
    The whole point of undefined behaviour is to allow for optimizations. Adding tons of runtime checks is the opposite of optimization. A lot of this is about being able to use a single instruction of the respective target architecture vs. adding another two, three instructions for the check, thus slowing things down to half the speed or less.
    • legulere 11y ago
      It's not really about optimisations, but more about being able to translate directly to fast machine instructions (which may behave differently on different machines). What I'm talking about is not adding checks, but what happens when the compiler knows that something has undefined behavior through e.g. Constant propagation. This happens in the optimizer on IR level. The undefined behaviour is there to make translations to machine instructions efficient - so that you don't need to do checks on pointers and that addition, shift, etc. on several instructions are supported although they behave slightly differently
      • zAy0LfpBZLC8mAC 11y ago
        > What I'm talking about is not adding checks, but what happens when the compiler knows that something has undefined behavior through e.g. Constant propagation. But ... either the compiler can prove at compile time that the program has undefined behaviour, in which case it should simply refuse to compile, or it can not, in which case it has to emit a runtime check to determine when undefined behaviour "is about to happen", which is potentially expensive? > The undefined behaviour is there to make translations to machine instructions efficient - so that you don't need to do checks on pointers and that addition, shift, etc. on several instructions are supported although they behave slightly differently ... or in other words: for optimisation? I mean, optimisation ultimately is nothing but the selection of the cheapest possible sequence of instructions to perform a given computation. And undefined behaviour helps with that, not just in the last step of mapping your IR to instructions, but in every step before that, as every optimisation step has to preserve the semantics of the code, and the fewer restrictions there are on the interpretation of a given piece of code, the more options every optimisation step has to transform the code without changing the semantics, and thus the more chances for one of them being cheaper than the others.