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 fo

> 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 ago
I'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 ago
  Cranelift, the (perenially?) up-and-coming Rust compiler, is based on e-graphs.
  - saagarjha 2y ago
    I guess it's borderline "real" ;)
    - pizlonator 2y ago
      Cranelift'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.
      - saagarjha 2y ago
        Maybe we are looking at different slides? The rewrite rules seem fairly straightforward and not really related to Rust at all?
- pizlonator 2y ago
  As far as I can tell e-graphs can’t handle all of the kinds of transforms that a compiler does, so they’re likely to be avoided by real compilers.
  - nlewycky 2y ago
    Set e-graphs apart from e-matchers. An e-graph is a vector-of-sets, where each set contains equal representations of the same thing. What makes it space efficient is that your representation refers to things by index number in the vector, so if you have "3 * (x + 1)" as an expression, you store "x + 1" in vector #1 and "3 * #1". That way if "x + 1" is also known to equivalent to "load ptr" then you add that to #1 and don't need to add anything to #0. In e-graphs, #0 and #1 are e-classes, the sets holding equivalence classes. There's no limit to what transforms you can use, and let the e-graph hold them efficiently. E-matchers are an algorithm over e-graphs to efficiently search for a pattern in an e-graph, for instance if you want to find "(load ptr) * (load ptr)" then you have to find "#x * #x" for all x in all e-classes, then check whether "load ptr" is a member of e-class #x. This is where you get limits on what you can match. "Pattern matching" style transforms are easy and fast using e-matchers, things like "x * 2" -> "x << 1", but beyond that they don't help. There's an optimizer problem where you have "load ptr" and you solve ptr and figure out it's pointing to a constant value and you replace the load instruction with the constant value. Later, you get to code emission and you realize that you can't encode your constant in the CPU instruction, there's not enough bits. You now need to take the constant and stuff it into a constant pool and emit a load for it. If you had stored them in an e-graph, you could have chosen to use the load you already had. Suppose you wanted to do sparse conditional constant/constant-range propagation but your IR uses an e-graph. You could analyze each expression in the e-class, intersect them, and annotate the resulting constant-range on the whole e-class. Then do SCCP as normal looking up the e-class for each instruction as you go.
    - WalterBright 2y ago
      Haha, I have this issue with the Arch64 code generator I'm building.

saagarjha 2y ago

I'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 ago
Cranelift, the (perenially?) up-and-coming Rust compiler, is based on e-graphs.
- saagarjha 2y ago
  I guess it's borderline "real" ;)
  - pizlonator 2y ago
    Cranelift'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.
    - saagarjha 2y ago
      Maybe we are looking at different slides? The rewrite rules seem fairly straightforward and not really related to Rust at all?
pizlonator 2y ago
As far as I can tell e-graphs can’t handle all of the kinds of transforms that a compiler does, so they’re likely to be avoided by real compilers.
- nlewycky 2y ago
  Set e-graphs apart from e-matchers. An e-graph is a vector-of-sets, where each set contains equal representations of the same thing. What makes it space efficient is that your representation refers to things by index number in the vector, so if you have "3 * (x + 1)" as an expression, you store "x + 1" in vector #1 and "3 * #1". That way if "x + 1" is also known to equivalent to "load ptr" then you add that to #1 and don't need to add anything to #0. In e-graphs, #0 and #1 are e-classes, the sets holding equivalence classes. There's no limit to what transforms you can use, and let the e-graph hold them efficiently. E-matchers are an algorithm over e-graphs to efficiently search for a pattern in an e-graph, for instance if you want to find "(load ptr) * (load ptr)" then you have to find "#x * #x" for all x in all e-classes, then check whether "load ptr" is a member of e-class #x. This is where you get limits on what you can match. "Pattern matching" style transforms are easy and fast using e-matchers, things like "x * 2" -> "x << 1", but beyond that they don't help. There's an optimizer problem where you have "load ptr" and you solve ptr and figure out it's pointing to a constant value and you replace the load instruction with the constant value. Later, you get to code emission and you realize that you can't encode your constant in the CPU instruction, there's not enough bits. You now need to take the constant and stuff it into a constant pool and emit a load for it. If you had stored them in an e-graph, you could have chosen to use the load you already had. Suppose you wanted to do sparse conditional constant/constant-range propagation but your IR uses an e-graph. You could analyze each expression in the e-class, intersect them, and annotate the resulting constant-range on the whole e-class. Then do SCCP as normal looking up the e-class for each instruction as you go.
  - WalterBright 2y ago
    Haha, I have this issue with the Arch64 code generator I'm building.