5 ms·
LLVM has been doing this optimization since 2008, and it contains justification in the commit message. LLVM commit #60470: Teach jump threading some more s
by pcwalton 11y ago
LLVM has been doing this optimization since 2008, and it contains justification in the commit message. LLVM commit #60470:
Teach jump threading some more simple tricks:
1) have it fold "br undef", which does occur with
surprising frequency as jump threading iterates.
...
Chris didn't cite any specific numbers in the log, but I believe him when he says it actually happens. You should be able to run "opt -O2 -debug-only=jump-threading" and see where it does :)
Related, with some actual numbers to prove it helps, LLVM commit #138618:
SimplifyCFG: If we have a PHI node that can evaluate to NULL and do a load or
store to the address returned by the PHI node then we can consider this
incoming value as dead and remove the edge pointing there, unless there are
instructions that can affect control flow executed in between.
In theory this could be extended to other instructions, eg. division by zero,
but it's likely that it will "miscompile" some code because people depend on
div by zero not trapping. NULL pointer dereference usually leads to a crash so
we should be on the safe side.
This shrinks the size of a Release clang by 16k on x86_64.
- Dylan16807 11y agoFor the price of removing some of the rusty nails sticking out of C, I'll happily pay a few 16KB on a binary as large as clang. Plus in most or all of those cases, the optimization would still be possible even with stable uninitialized values. It just needs to be done in a different way. You might be able to get 13 of those 16KB back with a very minor amount of work.
- pcwalton 11y ago> For the price of removing some of the rusty nails sticking out of C, I'll happily pay a few 16KB on a binary as large as clang. Lots of LLVM users won't. The competition between LLVM and GCC is (or was) pretty brutal. > Plus in most or all of those cases, the optimization would still be possible even with stable uninitialized values. It just needs to be done in a different way. I doubt that's possible without justification. How? Are you familiar with all of the passes of LLVM, how they interact, and with the code patterns generated by the STL? I trust Chris in that he didn't add the jump threading optimization for no reason, which is the main one that matters here. If he says that this occurs with "surprising frequency", sorry, but I'm going to trust him. Compiler developers are usually right about the impact of their optimizations. Submit a patch to LLVM if you like to remove it, but I highly doubt it'll go through. If it did go through, Rust (and perhaps Swift) would probably revert it, as we ensure that we don't emit UB in the front end, so losing the optimization hurts us for no reason.
- Dylan16807 11y agoThe goal is to refine the semantics of C. Removing a valid optimization doesn't help that. It's not that I think the Chris is wrong, it's that I think other optimizations related to dead code have gotten better in the last many years, and focused effort could improve them more.
- pcwalton 11y agoI think "refining the semantics of C" is a doomed effort that we shouldn't undertake. We'll lose performance for very little benefit, if market game theory even made it possible (and it doesn't: benchmarks of C compiler performance are much more important to customers than friendliness of the C dialect). We should just be moving away from C instead, or if we must stick with C we should invest in dynamic checks for undefined behavior. My position, by the way, is hardly uncommon among longtime C compiler developers.
- Dylan16807 11y agoDo you think C managed to get things exactly right? Or should we add more kinds of undefined behavior? What do we do about the fact that undefined behavior actually makes it harder or impossible to write efficient code in some cases, like checking for integer overflow? Even if your goal is performance over anything, there are a whole lot of undefined behaviors that have absolutely zero performance benefit.
- pcwalton 11y ago> What do we do about the fact that undefined behavior actually makes it harder or impossible to write efficient code in some cases, like checking for integer overflow? This is a good example of why we should be moving away from C. :) Signed overflow being undefined is basically necessary due to a self-inflicted wound from 1978: the fact that "int" is the easiest thing to type for the loop index when iterating over arrays. Nobody is going to go through and fix all the C code in existence to use unsigned, so we're stuck with that UB forever. The realistic solution is to start migrating away from C (and I have no illusions about how long that will take, but we'll never get there if we don't start now). > Even if your goal is performance over anything, there are a whole lot of undefined behaviors that have absolutely zero performance benefit. Sure. But compilers don't exploit those in practice (because compiler authors are not language lawyers for fun), so they're basically harmless in practice. They're essentially just spec bugs for the committee to fix in the next revision.