> 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?
The thing that trips me out is I kept seeing opposite claims in R&D: undefined behavior can improve performance a lot; using type-directed compilation can improve performance a lot. Most compilers rely on undefined behavior for aggressive optimizations. I wonder what the cutting-edge is on opposite end for type-safe languages and type-directed optimizations. FLINT for SML is the first one I saw like that:
They're not at all opposite: one can think of reasoning about types as reasoning about UB. For instance, if a value is of type `int`, it's undefined behaviour for it to be of type `float`, and so the compiler can optimise based on this fact (there's just the added bonus that the compiler also checks this UB "perfectly": code won't violate the rules).
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).
To me, undefined behaviour analysis and typing analysis seem very similar: Both allow a compiler to infer things that can help improve performance … So why do you see the claims that both can help performance as “opposite”?
The type system proves things about my program that must be true and disallows invalid programs. The undefined behavior system decides things about my program that may or may not be true and just breaks my program when one of us is wrong (and I don't even care who: whether it is the compiler that came up with something insane or me trying to do the impossible <- I honestly don't care).
I think when undefined behaviour is used for optimizations the programmer does not want it is more of a misunderstanding than one party (programmer or compiler) necessarily being “wrong”, as a compiler assumes that a program should make sense (i.e. is not undefined) and infers things from that. To clarify, would you say that assumption is problematic?
One claims to be undefined. One claims to use typed things to produce other typed things. I could see them doing similar or dissimilar things. Undefined vs specific types just seemed opposite to me.
The thing about undefined behavior is that it means the compiler can do whatever it wants. Most of the time, since the compiler wants to create efficient code, it can just assume that invalid values won't occur the same way a type system can allow a compiler to know that invalid values can't occur.
Most of the complaints about UB-based optimization that I've seen are from when the compiler uses UB to assume some type restraint that the programmer wishes it did not. E.g.:
int v = *p;
if (p == NULL) { /* ... */ }
The compiler uses UB to annotate the type information on p to indicate it's non-null, and then performs type-directed optimization.
Errr.
It's been done before.
Search the gcc mailing list archives, etc.
So i'm not sure what you are waiting for.
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.
Assuming you meant "I'm waiting to see an A:B test that shows compiler optimizations that assume there is no undefined behavior in the program being compiled lead to a binary that runs faster" or something similar: each time somebody adds any kind of optimization to a compiler, they have to first check that the optimization actually leads to a faster binary.
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").
No compiler-performed optimization will make your computer run faster, unless it's software that pokes magic variables in the hardware.
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).
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;
}
To just:
return 3;
Technically relies on undefined behaviour -- if you compile this without optimisation then on my machine passing silly(7) returns 4 (as x[7] happens to write over y). So the question becomes, where is the "line" we want to draw on not allowing undefined behaviour optimisations? It turns out unfortunately in practice everyone seems to have a different line on what should be allowed.
This is an interesting example. The store to x is dead and ought to be totally elided, but Rust will still emit an "overflow check" for an array that does not exist. This overflow check dominates the cost of the function.
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.
edit: re-reading your comment I suspect we're in violent agreement. :)
> 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
}
}
The assertion is there to make sure that two generic type parameters that should have an identical size actually do. If they do in optimized builds the compiler knows the assertion is true and completely elides the assertion itself. If the sizes aren't identical, the assertion isn't elided and I'll quickly find the bug when the program crashes(1).
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.
These people have done this work (and it's great!), and in their self-selected benchmarks programs they claim about 16% overhead: https://www.cis.upenn.edu/acg/softbound/
This is only memory safety, not using other optimizations related to undefined behavior will add a bunch more overhead.
"Global optimizations mostly do not rely on UB in order to get speed-ups, so this is not an A:B test of the value of UB.
"
[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.
> 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.)
The issue with UB and optimizations is that sometimes programs rely on UB deliberately. The code is actually tested in every way, and it works fine for years. Then a compiler update deliberately breaks it, oops; the optimizer now assumes that it can do anything it wants if that UB occurs.
Well, UB is, by definition, non-portable code. Nobody who knows C should be surprised that a different compiler produces different results on such code. Or even the same compiler, targeting a different architecture. Or even the same compiler, targeting the same architecture, with different flags.
Also, use-after-free is UB. I have yet to hear the argument that "unoptimized C" means using a conservative garbage collector, and a free(3) that isn't a no-op is an "optimization".
I think the parent meant (global (optimisation flags)), not ((global optimisation) flags). Of course, some optimisations don't rely on UB, the difference between the unoptimised and optimised code won't be entirely based on UB (a more reasonable comparison for one single type of UB would be passing -fwrapv vs. not, to stop the compiler thinking signed integers never wrap).
Repeating what I said further down this thread, but I've had this compiler flag break things involving computations with numbers in the range of 1 to 1,000.
If I understand correctly, it means that the math no longer fully conforms to every aspect of the IEEE spec. You lose some things like bits of precision in some operations, graceful underflow (where you keep as many bits as you can), and so on.
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.
Between you and ori_b, it sounds like proponents of undefined behavior optimization should distinguish between better optimization that's correct and possibly incorrect. I don't care how much faster it will go if it breaks my program or corrupts my data in subtle ways. However, if I didn't care for specific computations, then it would be good to know there were such optimizations available.
This isn't about undefined behavior. It's about ignoring the way that floating point math works like real numbers. That lets you assume things like addition are commutative, which enables things like loop invariant code motion, reordering of operations, and generally doing
The parent of my original comment gave it as an example of undefined behavior improving performance. I don't know enough to say whether that's true or not but was responding to correctness issues in that. So, now you're saying that the floating point optimizations sacrificing accuracy don't use any undefined behavior? That the parent just gave a bad example?
I'm saying that it violates the spec if you enable it. It's not undefined behavior in the spec.
If you want a good example of undefined behavior enabling optimizations, you can eliminate loop bounds checks by assuming that integers will never overflow.
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?
I think what pizlonator meant is that some languages like C have pervasive undefined behavior. (For instance, INT_MAX + 1 is allowed to erase your hard drive.) The claim is that this allows compiler optimizations that would otherwise not be possible. The question is: how bad would that be? Let's turn off all these optimizations and see how much the benchmark scores drop. If everything is twice as slow, then maybe this undefined stuff is worth it. If everything is one percent slower, then maybe it's not.
That part of the field is still in exploration phase. The reason is that you can mix run-time checks with no checks for performance enhancement. Static analysis and other schemes are used to prove specific code doesn't need checks. The rest get checks automatically. Performance varies per scheme applied with overhead going down significantly over past decade. We don't yet know the answer on just how much spatial or temporal safety we can get at what cost.
The point is: people are quick to say that taking advantage of undefined behaviour in the modern style is necessary to get best performance, and that this is worth the bother. But others (and I expect this person to be one of them) feel that perhaps good performance could be attained by some other route, one that doesn't involve the compiler stripping bits of your code out on an unanticipated technicality that requires ten paragraphs of legalese to explain. Especially not when the justification is something like "this would be hard to support on 1s complement" ;)
Yes, and this is why some of those others have designed the Rust language so that they can write programs that run fast without worrying about those tens of paragraphs of legalese.
Same motivations for D, Swift and Go, except you get a bit less performance due to need for GC.
> 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?