Automated Code Optimization with E-Graphs
For those who are not compiler experts, let me try to give a simplified (but not really wrong) explanation.<p>About 10 years ago, a paper came out on using something called equality saturation to do compiler optimization.  This is a fancy term that really means &quot;generate all equivalences in the IR rather than destructive IR updates&quot;.<p>IE if you have<p>a = 5 + 5<p>&quot;Destructive&quot; optimizers will rewrite this to:<p>a = 10<p>&quot;Equality saturation&quot; would simply annotate this with<p>&lt;a = 10&gt;
a = 5 + 5<p>Rather than destroying the original program.<p>Each optimization generates sets of equivalences and equalities, rather than updating the IR.  Over time, equality saturation has moved to more formally expressed rewrite systems as the optimizers.<p>Something eventually comes through and picks the most &quot;optimal&quot; set of equivalent code for the program.<p>Note that almost all compilers already do this in various phases for various reasons -  LLVM and GCC both, for example, annotate the IR with inequalities and other equivalences prior to doing value optimizations, etc.<p>Equality saturation has it&#x27;s niceties:<p>1. phase ordering is less of an issue- assuming you do this well, you will have no missed optimizations due to alternative representations that were not chosen.<p>2. more formalized rewrite systems are often verifiable, simpler, and have less bugs<p>It also has downsides:<p>1. lots of memory<p>2. very complicated exploration of the optimization space - none of the optimizations know which set of equivalences will be chosen in the end, so if they want the best code, they have to explore optimizing <i>all</i> the equivalences that have been generated before.<p>3. Most rewrite passes (formally expressed or not) individually are not optimal enough (and some can be proven impossible to make optimal) that you <i>will</i> still end up with phase ordering issues, just less of them, whether you express your passes as formal rewrite rules or not.  In general, most of these problems end up as NP-hard constraint solving problems or equivalent.<p>Truthfully, it&#x27;s an approach that is interesting (I went down this rabbit hole myself in LLVM at one point), and if you applied good ML or heuristics to it, i bet you could find a reasonable tradeoff of what to explore vs not, and get better results than the compiler gets now.  Expressing them as formally verifiable rewrite rules rather than ad-hoc passes will also make for a lot less compiler bugs ;)<p>Note that the general notion of expressing optimizations in a equivalence&#x2F;rewrite language and applying those iteratively, is not new (Stratego was an example of such a thing, there are many). Lots of them were destructive, there were some non-destructive ones, but none (IMHO) as well formalized as equality saturation or e-graphs.  This is in part because the computational cost has historically been quite high.<p>In any case, fast forward 12 years, this paper generalizes equality saturation to a turing complete graph expression (the original paper used extended PEGs) and language for doing rewrites, and uses it to optimize Julia programs, and provide a way for folks to write their own rewrite&#x2F;equality&#x2F;etc rules.<p>This is awesome work.  It still has the same issues (matching is NP-hard, etc).<p>That is, as i said, likely solvable in a practical way by better guiding matching&#x2F;rewriting&#x2F;equivalence finding.  You can prove you can&#x27;t get optimal answers anyway (it would require the programs to be statically decidable, and none are), so no point in trying.<p>The basic problem with both approaches, at least historically is that it&#x27;s not better enough for the cost.  Those who know me know I am a total sucker for abstractly nice optimization algorithms that produce really great results.  I&#x27;m a big believer we&#x27;ve thrown away a lot of years of compiler <i>theory</i> in the pursuit of making &quot;good enough&quot; compilers. Lots of knowledge and theory is ignored when it would make things a lot better.<p>But even I have my limits, and pragmatically, like I said, these kinds of approaches have just never been better enough for the cost, nor have they caught on among compiler folks yet for their ability to have less buggy compilers (that part is sad, FWIW)<p>This is not a knock on the paper - it&#x27;s a bachelors thesis, and a good one at that.<p>But in terms of practicality of these approaches in real compilers, i&#x27;ll believe it when i see it :)