Chris Fallin

We actually take a fairly unconventional approach to e-graphs: we have a few linear passes and we do all rewrites eagerly, so we use them to provide a general framework for the fixpoint problem into which we plug in all our rewrites, but we don't have the usual "apply as much CPU time as you want to get better results" property of conventional equality saturation. I gave a talk about this approach, aegraphs (acyclic e-graphs), here: slides (https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf), video (https://vimeo.com/843540328) (disclosure: Cranelift tech lead 2020-2022 and main author of the e-graphs mid-end, as well as regalloc, isel and its custom DSL, and other bits, along with the excellent team)

Those interested in this type of work can also visit https://cfallin.org/blog/2024/08/28/weval/. The difference is that they use this technique to derive an AOT compiler.

For sure. And I do find https://cfallin.org/blog/2024/06/12/rust-path-generics , for example, interesting. It’s certainly not like what Rust does today is the only way things could ever be. Heck, I’m sad we never got elision on structs in 2018 like we were talking about.

QuickJS and SpiderMonkey in WASM don't use JIT though - they're both just interpreters. WASM itself is often JIT'ed so a JS-to-WASM compiler that functions like the common JS baseline compilers would still get some benefit of JIT'ing even though the types available to the ICs in WASM may not be as useful as in JS. https://cfallin.org/blog/2023/10/11/spidermonkey-pbl/#future-compiled-… has some interesting ideas on enabling the SpiderMonkey baseline compiler for WASM and possibly using partial evaluation to see better types.

We have already made big improvements in using SpiderMonkey on WASM, and have more work in progress that will enable SpiderMonkey to have "native"-like codegen for WASM: https://cfallin.org/blog/2023/10/11/spidermonkey-pbl/ An additional benefit of using a fast JS runtime inside of WASM, even on a WASM engine that natively supports JS, is to use a Wasm Component as a security boundary around JS code. This could be used as an means of isolating supply-chain security issues, or allowing users to provide (untrusted) JS code that extends an existing system while having a clear and strong boundary on how untrusted JS code can affect the host JS code.

Zig did go on to apply the same style to their two later IRs, ZIR (https://github.com/ziglang/zig/pull/8266) and AIR (https://github.com/ziglang/zig/pull/9353). These don't look as thoroughly benchmarked (at least not on the PRs) but it looks like they got significant wins there as well. Of course Zig is a very different language and its compiler handles a rather different workload. It's totally possible that their approach makes more sense in younger codebases, or with a different source language design, or whatever else. But I also don't think node size tells the whole story- there's a synergy between memory usage, memory layout, and memory access patterns. For example Cranelift gets a lot of mileage from tweaking their algorithms in combination with their data structures, e.g. the "half-move" design mentioned in https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/#performance

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 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…