The acyclic e-graph: Cranelift's mid-end optimizer

An interesting move in this direction is the Tamagoyaki project: https://github.com/jumerckx/Tamagoyaki that supports equality saturation directly in MLIR.

I'd say there were a lot more things problematic in practice with SoN than not relaxing effect edges enough - I'd argue that the bigger problem was that a single effect chain was not enough to represent the flexibility that SoN promised, while keeping the costs, and getting that flexibility would mean effectively extending the effect chain to one effect colour per object per field. Maybe this was a JS specific idiosyncrasy, but my experience was that the effect chain became almost homomorphic to the control chain (and when it wasn't, we had bugs), and then you may as well merge the two into a CFG - if you have to skip over links in your effect chain to skip over certain kinds of effect then you can equally well skip over zero effect nodes too. With SoN, we got all the costs and (almost none) of the benefits, hoisting really isn't so difficult that you have to design your whole IR around it.

As for IR design and TFs good architectural decision, idk, I don't think it's all that different from what we ended up with in maglev. All those classes are just convenience views onto a consistent node layout (with e.g. the same trick as TF of putting inputs behind the node), and so far we haven't had issues with it - time will tell I suppose.

Overall, this narrative that TF, with it's SoN and other serial decisions, was super clever and built by very smart senior engineers that just all moved on and left behind just us dummies that don't get it -- I've honestly never argued against it. Hell, I can even agree with it, same as I totally believe Cliff when he says that he could easily solve every problem we struggled with (likely by doing it in the scheduler). Tony Stark built one in a cave with a bunch of scraps, but unfortunately I'm not Tony Stark, and we've ended up choosing human comprehension (instead of superhuman) as a design constraint so that us dummies can still work on it after all the senior engineers got promoted away or bored. I think this is a good decision and I stand by it.

I don't know if Cliff is on the same page w.r.t. how much speculation is necessary (and when) to make JS go fast. In particular, inserting speculative guards has the nice property of improving downstream information for dominated control flow paths. Dominated control flow paths are few and far between when the control chain is very relaxed (in fact, that's the point of a relaxed dependency representation--the graph doesn't have induced dominance information, just dependencies). So relaxing ordering actually works against making use of speculation decisions, because speculation decisions have all these downstream (forward) benefits. It actually makes a lot of sense to work out what speculations are going to be done and propagate their effects on a fully-scheduled CFG[1].

The case is not the same in Java. In C2, afaict, all speculation happens at graph build time, which is driven by abstract interpretation of the bytecode, which follows the control flow order. That means it can make use of dominance information.

AFAIK Graal does scheduling multiple times, whenever it needs to know explicit control information. This allows its speculations to propagate forward to dominated paths.

> Maybe this was a JS specific idiosyncrasy, but my experience was that the effect chain became almost homomorphic to the control chain (and when it wasn't, we had bugs), and then you may as well merge the two into a CFG - if you have to skip over links in your effect chain to skip over certain kinds of effect then you can equally well skip over zero effect nodes too. With SoN, we got all the costs and (almost none) of the benefits, hoisting really isn't so difficult that you have to design your whole IR around it.

I think this is the core of the problem. Control and effects are different things and it wasn't until long after TurboFan that I understood this well enough to even articulate it to myself, let alone to others. The only nodes that really need control inputs are those that have write effects or could diverge (not terminate). Reads of mutable state don't need control, they just need to have an effect input to order them w.r.t. writes. Writes don't need to depend on reads, like they did in TF IR; they are anti-dependencies that can be treated differently. From conversations with Cliff, I think C2 does treat antidependencies differently. Truth be told, writes don't even need to have control dependencies if the scheduler replicates code to make sure that different versions of the world are not simultaneously live (i.e. they are affine resources). The control dependencies in TF graphs were basically a CFG embedded in the graph and making writes depend on control more or less achieved that affine-ness.

While JS has far too many things that can change the world, it's clearly not the case that all the effect chains were linear, because load elimination would never happen, and no code motion would ever be possible. While it's hard to know how you think of "multiple effect chains"--it doesn't have to be represented by a multiple of edges in the graph. You can still have a single effect edge per node in most cases.

In the end it seemed like some people were really intent on only thinking about optimization from a CFG perspective and chaining a CFG through all effectful things, completely defeating the purpose of a dependency graph. People think about IRs in different ways, sure, but the dependency graph view and mindset is inherent in the sea of nodes representation. "Walking the code forward" is a common mental mode for CFG optimizations but is just alien to sea of nodes.

[1] To cut to the chase, and hindsight is 20/20, I think the best design for JS optimization is to use a CFG for a lot of frontend and middle optimizations, before lowering, to use it to insert speculations, and then to thread only a minimal effect / control chain to make a sea of nodes graph, run all the optimizations again, and reschedule it to a CFG. TBH I am not sure whether lowering should happen on a CFG or SoN--it does matter, but I don't think there's a definitive answer. But definitely run GVN on SoN after lowering--there's a bazillion common subexpressions to find then. It'd be great if optimizations can be written to be independent of whether a node is hooked up in a CFG or a SoN, to allow reuse between the two different representations. Or if the representation was sufficiently parametric that nodes could be hooked up in either configuration.