Taming Undefined Behavior in LLVM
blog.regehr.org
blog.regehr.org
> Finally, we noticed that there has been an interesting bit of convergent evolution in compiler IRs: basically all heavily optimizing AOT compilers (including GCC, MSVC, and Intel CC) have their own versions of deferred UB.
Does anyone know how GCC's deferred UB solution works and whether it suffers from the same problems as LLVM's?
Essentially, undefined behaviour exposed to the user is an extra layer of "types"/rules on top of the underlying type system, both of which the compiler can use for optimisation purposes (but only one of which the compiler checks for the programmer). More and more advanced type systems can push more of the former into the latter (e.g. for index-out-of-bounds, in the limit, dependent typing can allow one to statically ensure that all integers are in range of the arrays they index).
EDIT: More information here http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
int v = *p;
if (p == NULL) { /* ... */ }
which can mean erasure of the if block, to be perfectly clear here.
edit: any good compiler will warn about the assignment or throw an error, though, using the right compiler options.
interesting.
In fact, this type of thing has probably been done about 15-20 times in the past at least that i've seen.
Someone always brings this up.
Someone eventually bothers to run numbers, and it's very consistent that for icc, xlc, gcc, llvm, etc, you gain significantly in what you can do with loops and conditionals, as well as pointer analysis.
Personally, as a pointer analysis maintainer, TBAA buys, on average, 10-20% precision. There is even a paper in a conference from intel that has the breakdown of where they get precision gains from various parts of aliasing disambiguation.
I'm not aware of any good way to request "all optimizations except the ones that rely on undefined behavior," so it would be very difficult to get this kind of test. But it's also true that whenever somebody files a bug against a compiler because the compiler did something unexpected when the programmer triggered undefined behavior (e.g., expected signed integer arithmetic to wrap, dereferenced a null pointer, got aliasing rules wrong, etc.) the compiler team is able to quickly point out the the performance gain from that particular optimization (e.g., "having signed integer overflow undefined means that tight loops run up to 20% faster").
UB isn't exclusively for performance reasons. Some UB, like aliasing-related UB, is simply because there is no Right Way to do things (The standard does not define memory layout).
1. Install Gentoo.
2. Compile with global optimization flags on for a week.
3. Compile with global optimization flags off for a week.
4. Decide.
Unless you're doing numerical work (encoding/decoding/3D geometry/computer vision/...), you probably won't notice. And some desktop applications which used to work, might not work right anymore.
The majority of those optimizations aren't taking advantage of undefined behaviour. Neither GCC nor clang provide a simple way of getting "no undefined behaviour" optimisations.
Unfortunately, in practice it's often hard to define what that would actually mean. For example, fairly simple optimiations like optimising:
int silly(int i) {
int y = 3;
int x[4];
x[i] = 4;
return y;
}
return 3;
Of course studies have been done on how expensive overflow checking is. IIRC around 5% overhead in the most extreme examples.
If the optimizer determines a store is dead and can elide it, should it also elide the overflow checks? If "no," then it seems we've unnecessarily hamstrung the optimizer. If "yes," then whether a program panics is optimization-level dependent.
> The store to x is dead and ought to be totally elided
Yet, it's a clear sign of a bug in the program; the fact it happened to be elided in that case doesn't change the fact that it's almost certainly a bug that I want to know about.
Heck, earlier today I wrote a Rust function along these lines:
fn foo<A, B>(a: &A) -> &B {
assert_eq!(size_of::<A>() == size_of::<B>());
unsafe {
// do horrible low-level things
}
}
I definitely wouldn't want that assertion to get elided just because the "horrible low-level things" happened to be categorized as undefined behavior!
1) Of course, a sufficiently smart compiler could detect that the assertion was false at compile time in this simplified example.
This is only memory safety, not using other optimizations related to undefined behavior will add a bunch more overhead.
[Citation needed]
They most certainly do rely on UB to move statements past other statements, to delete dead code, etc.
If you want a source: I've written all or parts of gcc's statement sinking, partial redundancy elimination, dead store elimination, alias analysis, etc.
Same with LLVM. They all rely on UB being UB to be able to do their work effectively.
You could never, for example, hoist a load if it wasn't UB to dereference a null pointer, unless you could prove it was non-null (and you mostly can't).
You'd have to insert null checks everywhere, like java, and then try to get rid of them.
You could never move anything past (up or down) an external function call if you didn't rely on UB.
I could go on, but it's pretty silly. Random assertions about "optimizations taking advantage of UB don't gain performance" simply are not in accord with reality.
If it wasn't true, we'd just make programming languages with no UB. It's not like compiler writers are just lazy.
Well, we do make programming languages with no undefined behavior. :) It's just that C and C++ need UB.
For instance, all your examples are things that Rust and Swift can statically prove without resorting to UB in the language semantics. Null pointer assumptions become precise with nullable types. Optimizations around opaque calls can be made sound with static knowledge of aliasing and type safety (most importantly, TBAA is a sound analysis if your language is memory safe). Signed overflow UB is less important to optimize around if programmers use proper iterator constructs so the compiler can soundly determine trip count. And so forth.
(I'm sure you know all of this, just stating for the record.)
There's a reason it's not on by default: it makes things fast, dangerously.
Could you be more specific? ffast-math isn't something you enable all the time to get a magical speed boost, it has trade offs.
Your question itself is not at all specific about what information you require.
These rules are unnecessary - for most problems. If you have a problem where you need them, though, your calculations will silently produce garbage without them.
I think (but I am not sure) that most of the time, if you need full IEEE arithmetic for your problem, you know that you need it.
If you want a good example of undefined behavior enabling optimizations, you can eliminate loop bounds checks by assuming that integers will never overflow.
No. It loses accuracy. That's why it's not on by default.
AFAIK the goal of optimizers is to generate faster code while preserving the initial visible behaviour. If the initial behaviour is undefined, what can an optimizer try to preserve?
Could someone give an example on how it would be possible not to have "UB in the compiler", while still having optimizations?
Same motivations for D, Swift and Go, except you get a bit less performance due to need for GC.