I've heard of "sea of nodes" intermediate representations mostly in the context of just-in-time compilation (JVM, V8, Graal) whereas intermediate representations such as LLVM IR are used in ahead-of-time, optimizing compilers. Projects like Cranelift are exploring egraphs which in my mind seem in-between these two designs in some ways. I'm not sure if the sea of nodes design is strictly a byproduct of needing to very quickly produce code with a small footprint or if the design materially effects the efficiency of the code. It seems that all the formats are in single-static form (at least initially) and many of the same optimizations are performed. Cliff Click (who wrote the paper on sea of nodes) has discussed an advantage of the sea of nodes not requiring a pass manager and instead doing all optimizations all at once. I'm not sure that it is strictly an advantage of the sea of nodes considering papers like the following which hint at using abstract interpretation to combine traditional basic block, SSA optimizations into a single pass (https://binsec.github.io/assets/publications/papers/2023-popl-full-with-appendices.pdf). What are the tradeoffs between these representations for ease, effectiveness (e.g. one inherently produce better code), and expressiveness (e.g. it is hard to express a given analyses for one) for compiler optimizations?
-
1$\begingroup$ That paper you link works by constructing a 'cyclic term graph' in the abstract domain, which shares many of the desirable properties of sea of nodes. Such an approach can, if combined with precise analyses, likely produce better results than plain sea of nodes, at the cost of implementation complexity and compile time. $\endgroup$– MoonchildCommented Sep 11, 2023 at 2:08
-
2$\begingroup$ E-graphs are not a program ir; they are a tool you can use within the design of a program ir. For example, cranelift is using an e-graph-based dataflow graph to do some basic-block-local optimisations (and it uses a traditional cfg to connect its blocks). So it's a category error to imply that e-graphs are at the same level as sea of nodes or cfgs. (Another way to think of it: e-graphs are a strategy for compactly encoding and operating on a large—or possibly even infinite—set of program irs, but they must still themselves be represented somehow.) $\endgroup$– MoonchildCommented Sep 11, 2023 at 6:03
1 Answer
Let's contrast sea-of-nodes and basic blocks with e-graphs. All three are graph representations of programs. The main feature of a graph representation is that intermediate values can be dependencies of multiple other values and also depend on multiple values, in contrast to the abstract syntax, which is usually a tree, DAG, or similarly restricted graph.
First, what's the difference between a control-flow/basic-blocks graph and a sea-of-nodes graph? Think of basic blocks as extending the sea of nodes. Typically, each node in the graph will represent a single atomic/primitive operation. Basic blocks augment this concept by allowing composite nodes which fuse multiple operations. In contrast, a sea of nodes simulates basic blocks with extra edges which indicate data dependencies; control flow is inferred from those dependency edges.
Optimization in both sea-of-nodes and basic-block graphs is done by examining each node and considering whether it can be transformed into a simpler node; in some sense, it's all about strength reduction. This leads to the phase ordering problem: we want to factor our transformations into simple steps, but this can lead to suboptimal graphs, because the output of one step may be suboptimal and also not transformable by latter steps. As a result, many compilers either fuse the steps into one single massive node-transforming case analysis, or repeatedly apply many small steps in an empirically-determined heuristic order.
E-graphs extend the graph-representation approach. The "e" is short for "equality"; in addition to either a sea of nodes or a basic-block graph, we add a union-finding structure which indicates whether two nodes are equal. The values computed by equal nodes are also equal (equality is extensional), so we may have a choice of which node to use when emitting our final output. This lets us work around the problem of ordering phases entirely! How?
When we apply node transformations to an e-graph, nodes are not mutated. Instead, new nodes are generated which represent the transformation, and these nodes are declared to be equal to the old nodes. As optimization progresses, the graph becomes saturated, heavy and full of many different possible ways of expressing equivalent computations. Then, we recursively extract a standard SSA graph and return to sea-of-nodes or basic blocks by choosing the least expensive node from each equivalence class of nodes. Note that, while this extraction process is not necessarily optimal, it can be configured so that the output is no worse than the input; the original nodes are still part of the e-graph.
Okay, that was a long answer. Five paragraphs in, what's the relevance to your question? Well, hopefully it is obvious now that all three graph representations are equivalent in expressiveness, since all optimizations are represented as graph operations. Similarly, they have around the same ease of implementation and use. They only differ in effectiveness, due to the phase ordering problem, and I consider e-graphs to be fundamentally at least as effective as other graph representations.
-
1$\begingroup$ Bb-cfgs are not augmented; they are overburdened: sea of nodes includes only true dependencies, while bb-cfgs contain redundant, spurious dependencies, the consequences of which pervade the typical basic-block-oriented compiler. Both cfgs and sea of nodes admit abstract interpretations, which do not have such phase-ordering problems. And since the edges in sea of nodes represent data dependencies, it is easy to imagine applying e-graphs to it directly; this would not make so much sense for a cfg. $\endgroup$ Commented Sep 11, 2023 at 2:02
-
1$\begingroup$ Do any e-graph approaches maintain the distinction between address equality and reference equivalence? Compilers like clang and gcc seem to unsoundly assume that two pointers that share the same address will have the same aliasing semantics, even when language rules would dictate otherwise. $\endgroup$– supercatCommented Sep 12, 2023 at 15:00
-
$\begingroup$ In the e-graph description, you mention adding one node as equivalent to another node, however loop transformations typically span many instructions, so it seems you would need to be able to denote one sub-graph as equivalent to another sub-graph. $\endgroup$ Commented Sep 12, 2023 at 15:11
-
1$\begingroup$ I find the wording about saturation a bit confusing. It may be useful to clarify that instead of ordering phases manually, the compiler can in theory repeatedly apply all transformations in a loop until a fixed point is reached (at which point the graph is saturated). But theory and practice differ. In practice, it is still likely that the order in which transformations are applied should be tuned, and potentially applying several optimizations multiple times, with the goal -- this time -- to minimize the number of iterations until the fixed point is reached... $\endgroup$ Commented Sep 12, 2023 at 15:15
-
1