4 ms·
One thing I learned about optimizers is some optimizations undo earlier optimizations. The state of the optimized program will sometimes flip-flop back and fort
by WalterBright 2y ago
One thing I learned about optimizers is some optimizations undo earlier optimizations. The state of the optimized program will sometimes flip-flop back and forth and never converge on a solution. Then you have to rely on a heuristic to guess at the better form, and live with it. The optimizer has a counter in it so it will "pull the plug" if it fails to converge, and will just go with the last state.
My optimizer first appeared in Datalight C around 1984 or so. It was the first DFA optimizer for any C compiler on the PC. C compiler benchmark roundups were popular articles in programming magazines at the time. We breathlessly waited for the next roundup article.
When it came, Datalight C was omitted from it! The journalist said they excluded Datalight C because it was buggy, as it deleted the benchmark code and just printed the success message. The benchmarks at the time consisted of things like:
for (i = 0; i < 1000; ++i) a = 3;
so of course it deleted the useless code.
I was really angry about that, as the journalist never bothered to call us and ask about DLC's behavior. Our sales tanked after that article.
But it wasn't long until the industry realized that optimizers were the future, the benchmarks were revised, and the survivors in the compiler business all did optimizers. DLC recovered, but as you can tell, I am still annoyed at the whole incident.
- pizlonator 2y ago> One thing I learned about optimizers is some optimizations undo earlier optimizations. The state of the optimized program will sometimes flip-flop back and forth and never converge on a solution. Then you have to rely on a heuristic to guess at the better form, and live with it. The optimizer has a counter in it so it will "pull the plug" if it fails to converge, and will just go with the last state. The way every optimizer I've worked on (and written) deals with this is canonical forms. Like, you decree that the canonical form of "multiply integer by 2" is "x << 1", and then you make sure that no optimization ever turns "x << 1" into anything else (though the instruction selector may then turn "x << 1" into "x + x" since that's the best thing on most CPUs). But that doesn't necessarily make this problem any easier. Just gives you a principled story for how to fix the problem if you find it. I think that usually the canonical forms aren't even that well documented, and if you get it wrong, then you'll still have valid IR so it's not like the IR verifier will tell you that you made a mistake - you'll just find out because of some infinite loop. And yeah, lots of compiler optimization fixpoints have a counter to kill them after some limit. The LLVM inliner fixpoint is one example of such a thing. > I was really angry about that, as the journalist never bothered to call us and ask about DLC's behavior. Our sales tanked after that article. Whoa! That's a crazy story! Thanks for sharing!
- saagarjha 2y agoI'm not sure if any "real" optimizers are using them yet but in theory e-graphs can store a set of forms and avoid this kind of issue.
- Sesse__ 2y agoCranelift, the (perenially?) up-and-coming Rust compiler, is based on e-graphs.
- saagarjha 2y agoI guess it's borderline "real" ;)
- pizlonator 2y agoCranelift's reason for using e-graphs is, in my view, that Rust sucks. Seriously. Consider the slides here, particularly slides 27-30: https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf They show code for pattern matching IR in their Rust code, and it's awful. I think it's because they can't just have an IR with pointers, because that would violate Rust's rules. So, they need to call goofy helpers to deconstruct the IR. Consequently, a super simple rewrite rule ends up being a full page of gnarly code. That code would be less than half as long, and much easier to parse, if it was in LLVM IR or B3 IR or any other sensible C++ IR. Then they show that the egraph rule is "simple". It's certainly shorter than C++ code. But while it is conceptually simpler than their Rust code, it is no conceptually simpler than the same rewrite written in C++. The C++ code for rewrites in either LLVM or B3 is not that much more verbose than the egraph rule, but in a way that makes it easy to understand. Plus, it's code, so it can call any API in the compiler and do any logic it likes - making it inherently more flexible than an egraph. So, if they had used a sensible programming language to write their compiler then they wouldn't have needed egraphs as an escape hatch from how bad Rust is. And the phase ordering argument for e-graphs is baloney because: - Their example of alias analysis, GVN, and RLE assumes the strawman that you put those things in separate phases. Most compilers don't. LLVM does alias analysis on demand and combines GVN and RLE. Ditto in B3. - The difficulty of phase ordering in LLVM's pass builders (and in any pipeline I've ever worked on) is that you've got passes that are not expressible as egraphs. Until someone can demonstrate an egraph based inliner, SCCP, SROA, coroutine lowerings, and heck an egraph-based FilPizlonator (the pass I use in the Fil-C version of clang to make it memory safe), then you'll be left with those passes having to run the classic way and then you'll still have phase ordering problems.
- WalterBright 2y agoRecently, a D user remarked that a non-optimized build took a few seconds, but turning on the optimizer caused it to take 35 minutes. I was wondering how this was possible. It turns out his code had a function with 30,000 lines of code in it! Some things one just doesn't anticipate. Working on compilers is never dull.
- subharmonicon 2y agoI’m honestly a bit surprised if that’s the first time you’ve seen something like that. I’ve been working on compilers 30 years, primarily on optimizers (although some frontend work as well). Learned C from Borland C and C++ from…Zortech C++ 1.0, so thank you for that! Within a few years of working on compilers I came across my first examples of 50k+ line functions. These were often (but not always) the result of source code generators that were translating some kind of problem description to code. It taught me very early on that you really need to focus on scalability and compile time in compilers, whether it’s the amount of code within a function, or across functions (for IPO / LTO). And yes, working on compilers is never dull. 25 years ago I thought we’d end up in a monolithic world with x86, C++, and Java being the focus of all work. Instead, there’s been an absolute explosion of programming models, languages, and architectures, as well as entirely new problem spaces like graph compilers for ML.
- WalterBright 2y agoI did see slow optimize builds before, but that was on much, much slower machines. I thought that was a thing of the past with modern CPUs.
- badmintonbaseba 2y ago> Within a few years of working on compilers I came across my first examples of 50k+ line functions. These were often (but not always) the result of source code generators that were translating some kind of problem description to code. Like the issue in the Linux kernel recently where they had some simple looking min/max macros that generated megabytes of source code.
- ajb 2y ago
- cryptonector 2y agoThat is a horrible story. I would have been as livid as you.