Hi all -- I have some updates. It's kind of a mixed bag -- tl;dr, code quality matches existing Cranelift (all optimizations have been reproduced), compilation speed is ~1-5% slower. Theoretical benefits of everything-in-one-fixpoint (GVN and alias analysis and LICM and algebraic simplifications all cooperating) work in filetests, but don't seem to do much to Wasm-based benchmarks in Sightglass.

So the current status of the WIP branch is:

• "acyclic egraph" (ægraph) implementation is working;
• producing and lowering out of this aegraph works fine;
• ISLE-based rewrite rules operate on this aegraph, and cost-based extraction picks the best option for each node after rewrites are done;
  • rewrites in the aegraph apply immediately (because of acyclicity, there's no need to revisit a node);
  • ISLE itself has been extended to support "multiplicity" in extractors and constructors, so multiple rules can match and matchers on eclass IDs see all available enodes for each eclass;
• The aegraph construction and "scoped elaboration" subsume GVN (global value numbering, a form of common-subexpression elimination) by means of the deduplication map;
• The aegraph elaboration automatically does LICM (loop-invariant code motion) implicitly, by way of loop-nest awareness when traversing the domtree;
• The alias analysis feeds into the rewrite rules and there are rules for redundant-load elimination and store-to-load forwarding;
• Rewrite rules have been written for a bunch of constant-propagation and algebraic-simplification cases, and some other slightly more ad-hoc ones (e.g. reassociating loads to try to make LICM on partially-loop-invariant sums work)
• A simple form of rematerialization has been implemented, where adds-with-one-immediate, and immediates themselves, are regenerated in the block they are used rather than maximally hoisted by GVN, in order to reduce register pressure.

All this works -- and IMHO the data structures and algorithms are pretty beautiful actually! -- but it's not any faster. It is nicer to update with more rewrite rules -- see cprop.isle and algebraic.isle -- and if it were completely at parity performance-wise, this would be an interesting benefit still IMHO. But there is still a small compile-time penalty, around 5% on average, with everything above incorporated.

I have some more thoughts in my running TODO list but most of the remaining ones are for compile speed, not code quality (runtime speed).

Given all that, I think I'm running up against a wall that's actually mostly supported by some other limits:

• There is actually not a ton of remaining "low-hanging fruit" when running Wasm modules produced by an optimizing compiler. (Any strength reduction or other clever "instcombine"-type optimization I would expect to be done by LLVM before producing the .wasm.)
• Lowering, once it occurs, disallows any further optimizations, because we can't edit VCode currently.

The first is just a fact of our benchmarking conditions (but we're oriented this way because we care very much about Wasm performance -- we can't just choose to focus on poorly-optimized CLIF instead and say "see look opts work!"). But the second is where a lot of my thoughts are going lately. In other words, from first principles, if we start with highly-optimized Wasm bytecode, where do we expect inefficiencies and redundancies to creep in? Probably one of the three areas:

• The semantic gap between Wasm bytecode and CLIF, and how it is bridged (heap bounds checks, table accesses, and the like);
• The semantic gap between CLIF and the machine, and how it is bridged (our lowering rules in our backends);
• regalloc quality.

My forehead is already dented from banging against item 3 (regalloc quality) for a long time, and item 1 (Wasm to CLIF) is largely addressed already by designing CLIF semantics to be close to those of Wasm; but item 2 (lowering) presents unharvested opportunities IMHO.

In looking at disassemblies of "hot blocks" when profiling runtime I see a lot of not-great code, and it comes in several varieties: redundant flags computations (cmp / setnp / cmp / sete for float comparisons is a common one); redundant trap conditions that cprop could optimize away, or GVN could combine between multiple ops; address-mode junk produced by our "match up the operand tree and then regenerate an add tree for the parts we can't incorporate" logic in both x64 and aarch64; a bunch of "spill x+1, x+3, x+10, x+15 to separate spillslots for use later" (hence my attempt at remat above); and others. A lot of this comes from the inability to optimize code once we lower a CLIF op into multiple MachInsts, or one pseudo-MachInst.

(Those who have been around a while might be screaming: legalization and post-opt! Yes, you're right. I think we threw out some of the value of those in exchange for the speed and simplicity of the single-pass lowering, and the real value that we do get from a two-level IR. But we lost something too.)

So: I'm taking a little time to think about what might make sense as a way to optimize VCode. I don't think this means throwing out the aegraph and ISLE-based mid-end framework; I think instead there may be a way to write some mid-end legalizations that do a lot of expansion that we currently do in lowering, and then let lowering be simpler; or in the extreme, even have a Node::MachInst { ... } in the aegraph, though that has potential efficiency issues. More thought needed.

Anyway, I'd love to hear more thoughts on this, and we can talk about it more in the next Cranelift meeting, but there's my report on what I've learned in the last few weeks :-)