I don't believe the performance difference between Cranelift and LLVM really has much to do with E-graphs. Cranelift had this same performance profile (faster than LLVM but generating slower output) before they switched to E-graphs.
Rather it's about how much effort Cranelift puts toward optimizing its output- it has fewer, less involved passes (regardless of whether those "passes" are expressed as part of the E-graph framework). More subtly, this means it is also written to generate "okay" code without as much reliance on those passes- while LLVM on the other hand generates a lot of naive code at -O0 which contributes to its slower compile times in that mode.
Right, it's about algorithmic tradeoffs throughout. A good example I wrote about is here: https://cfallin.org/blog/2021/01/22/cranelift-isel-2/ where we use a single-pass algorithm to solve a problem that LLVM has a multi-part fixpoint loop to solve.
Most CPU time during compile is in the register allocator and I took a really careful approach to optimization when I rewrote it a few years ago (more details https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/). We generally try to pay close attention to algorithmic efficiency and avoid altogether the fixpoint loops, etc that one often finds elsewhere. (RA2 does backtrack and have a worklist loop, though it's pretty minimal, and also we're planning to add a single-pass mode.)
(disclosure: I was Cranelift tech lead in 2020-2022)
Rather it's about how much effort Cranelift puts toward optimizing its output- it has fewer, less involved passes (regardless of whether those "passes" are expressed as part of the E-graph framework). More subtly, this means it is also written to generate "okay" code without as much reliance on those passes- while LLVM on the other hand generates a lot of naive code at -O0 which contributes to its slower compile times in that mode.