3 ms·
> 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"
by 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 agoFor 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).
- tarpherder 11y agoWhich they don't? Right?
- barrkel 11y agoThe problem here is, as you point out, the conversion of double to unsigned byte. More specifically, the problem is that processing this operation is not producing error; it instead propagates the problem and produces invalid code. That's a situation where nobody wins. I think we'd be better off if many undefined behaviours were instead implementation defined. If, instead, LLVM had converted the double to some integer and then chosen the lowest 8 bits from that integer, we'd have gotten some random value - but at least the comparison wouldn't have been ignored. The comparison should only be ignored if the compiler can prove that the value definitely lies within the range; if it isn't sure, it can't remove the comparison. The programmer wrote it for a reason; ignoring the intent of the programmer is a bug. On strict aliasing, I'm against it without explicit opt-in over a delimited subset of source code. I understand that using & is going to harm the performance of my code; I think that's an acceptable tradeoff for more predictable behaviour. If it harms the performance of C++ vector iterators, for example, I don't care: strict aliasing rules are a worse cure than the disease of C++'s poorly thought out abstraction tools. Let a subset of the program follow Fortran rules if it's required.
- pcwalton 11y ago> On strict aliasing, I'm against it without explicit opt-in over a delimited subset of source code. I understand that using & is going to harm the performance of my code; I think that's an acceptable tradeoff for more predictable behaviour. I believe that you and others think that's an acceptable tradeoff. At the end of the day, though, most people want C compilers to produce the fastest code possible. Compiler authors are just responding to what users want. The example below is actually an excellent example of this. > If it harms the performance of C++ vector iterators, for example, I don't care: strict aliasing rules are a worse cure than the disease of C++'s poorly thought out abstraction tools. It's not just C++. Consider (from Chris Lattner's blog post): float *array; void zero_out() { for (int i = 0; i < 100; i++) array[i] = 0.0; } People saw compilers missing the optimization to compile this to a memset, and filed bugs against them. As a matter of fact, though, that is an illegal optimization to make unless the compiler is able to take advantage of strict aliasing. That's because, absent strict aliasing, array[0] could legally be a type-casted pointer back to "array" itself, even though almost nobody would actually write that code. The reason why compilers implemented strict aliasing rules is that their users demanded that they fix "optimizer bugs" like the one above. And, honestly, I can't blame either the compiler developers or the users. Strict aliasing ends up being one of the things that's often important for performance. The problem, if anything, lies with the C language.