<p>I've heard of &quot;sea of nodes&quot; 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 (<a href="https://binsec.github.io/assets/publications/papers/2023-popl-full-with-appendices.pdf" rel="noreferrer">https://binsec.github.io/assets/publications/papers/2023-popl-full-with-appendices.pdf</a>). 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?</p>

<compilers><optimization><static-analysis><intermediate-representation><e-graphs>
What are the tradeoffs between using sea of nodes, CFG of basic blocks, and egraphs for compiler optimizations?
CC BY-SA 4.0
2023-09-11T02:08:24.100Z
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.
Moonchild
CC BY-SA 4.0
2023-09-11T06:03:36.110Z
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.)
Moonchild
<p>Let's contrast sea-of-nodes and basic blocks with e-graphs. All three are <strong>graph representations</strong> 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, <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noreferrer">DAG</a>, or similarly restricted graph.</p>
<p>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.</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Strength_reduction" rel="noreferrer">strength reduction</a>. This leads to the <strong>phase ordering problem</strong>: 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.</p>
<p>E-graphs extend the graph-representation approach. The &quot;e&quot; is short for &quot;equality&quot;; in addition to either a sea of nodes or a basic-block graph, we add a <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="noreferrer">union-finding structure</a> which indicates whether two nodes are equal. The values computed by equal nodes are also equal (equality is <a href="https://en.wikipedia.org/wiki/Extensionality" rel="noreferrer">extensional</a>), 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?</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Saturation_(graph_theory)" rel="noreferrer">saturated</a>, 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-09-10T11:57:21.420Z
2023-09-11T19:47:05.930Z
2023-09-11T19:47:05.930Z
Corbin
CC BY-SA 4.0
2023-09-11T02:02:58.147Z
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.
Moonchild
CC BY-SA 4.0
2023-09-12T15:00:31.007Z
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.
supercat
CC BY-SA 4.0
2023-09-12T15:11:10.613Z
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.
Matthieu M.
CC BY-SA 4.0
2023-09-12T15:15:42.773Z
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...
Matthieu M.
CC BY-SA 4.0
2023-09-12T16:03:51.373Z
@MatthieuM.: In the typical e-graph library (e.g. [egg](https://egraphs-good.github.io/)), the equivalence classes are defined on nodes, although you're correct that the rules match both a top-level node and also its various subnodes as a subgraph. We have to be careful here; e-graphs can have cycles, so there's no closed-downward reasoning available and we aren't just doing tree transformations.
Corbin
CC BY-SA 4.0
2023-09-12T21:29:00.127Z
@supercat the equivalence relation in use is operational equality, which is the same as subtitutability.  The existence of weaker comparison operators within the language is neither here nor there (for example, the language could also include floating-point equality, which doesn't distinguish -0 from +0).
Moonchild
CC BY-SA 4.0
2023-11-10T16:55:32.390Z
@Moonchild: The question is whether they recognize the fact that even if pointers based on `p` and pointers based on `q` could not be used to access the same region of storage within a particular context, and some pointer `r` identifies the same object as `p`, that would not imply that `r` not based upon `q`.   Both clang and gcc are prone to assume that if `p` is observed to be equal to `r`, then accesses to `*r` may be replaced with accesses to `*p`, without having to treat such accesses as potential accesses to `*q`.   Is this a limitation of sea-of-nodes, or just those compilers?
supercat
CC BY-SA 4.0
2023-11-10T22:44:46.120Z
those compilers
Moonchild
# What are the tradeoffs between using sea of nodes, CFG of basic blocks, and egraphs for compiler optimizations?
Posted by: username_0 on 2023-09-09
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?
**Tags:** compilers optimization static-analysis intermediate-representation e-graphs
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.)  
---
## 1 answers
### Answer by username_2 on 2023-09-10. Score: 8 | Accepted 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](https://en.wikipedia.org/wiki/Directed_acyclic_graph), 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) which indicates whether two nodes are equal. The values computed by equal nodes are also equal (equality is [extensional](https://en.wikipedia.org/wiki/Extensionality)), 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](https://en.wikipedia.org/wiki/Saturation_(graph_theory)), 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.
> **Comments:**
> **username_1** (2023-09-11): 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.  
> **username_3** (2023-09-12): 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.  
> **username_4** (2023-09-12): 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.  
> **username_4** (2023-09-12): 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...  
> **username_2** (2023-09-12): @MatthieuM.: In the typical e-graph library (e.g. [egg](https://egraphs-good.github.io/)), the equivalence classes are defined on nodes, although you're correct that the rules match both a top-level node and also its various subnodes as a subgraph. We have to be careful here; e-graphs can have cycles, so there's no closed-downward reasoning available and we aren't just doing tree transformations.  
> **username_1** (2023-09-12): @supercat the equivalence relation in use is operational equality, which is the same as subtitutability.  The existence of weaker comparison operators within the language is neither here nor there (for example, the language could also include floating-point equality, which doesn't distinguish -0 from +0).  
> **username_3** (2023-11-10): @Moonchild: The question is whether they recognize the fact that even if pointers based on `p` and pointers based on `q` could not be used to access the same region of storage within a particular context, and some pointer `r` identifies the same object as `p`, that would not imply that `r` not based upon `q`.   Both clang and gcc are prone to assume that if `p` is observed to be equal to `r`, then accesses to `*r` may be replaced with accesses to `*p`, without having to treat such accesses as potential accesses to `*q`.   Is this a limitation of sea-of-nodes, or just those compilers?  
> **username_1** (2023-11-10): those compilers  
---
