Lesson 8.5 — Graph IRs beyond the CFG: sea of nodes, dependence graphs, e-graphs¶

Techniques: sea of nodes (Click–Paleczny; HotSpot C2, Graal, V8 TurboFan) and why V8 moved to a CFG (Turboshaft), dependence-graph IRs (PDG, VSDG, RVSDG), e-graphs as an IR (equality saturation, egg, Cranelift's aegraph) · Pebble uses: none of them directly; Ch 17 implements equality saturation, Ch 15 control dependence · Prerequisites: Lesson 8.4, post-dominance (Lesson 15.4) · Time: 5–7 hours

The CFG + SSA design fixes an order: every instruction sits at a position in a block. That order is often an accident of the source. i % 3 is computed where the programmer wrote it, not where it is cheapest. This lesson covers three IRs that drop part of the order. The sea of nodes keeps only the dependences an instruction really has. Dependence graphs (PDG, VSDG, RVSDG) replace control flow by dependence entirely. E-graphs go further and keep many equivalent programs at once.

1. Problem and motivation¶

The problem. Represent a function so that transformations that move or rewrite code (code motion, value numbering, algebraic rewriting) need no separate analysis to know what may move where, and choose the final order or form of the code as late as possible.

Sea of nodes¶

Click and Paleczny's "simple graph-based IR" [CP95], developed in Click's thesis [Cli95t], merges the CFG and SSA into one graph. Control is a chain of nodes (Start, If, Region, Loop), and pure computations are floating nodes with only data edges. A pure node has no block: its position is computed by global code motion (GCM) [Cli95] when the optimizations are done, which gives loop-invariant code motion and partial dead-code sinking for free. HotSpot's server compiler C2 [HS-GCM], Graal [GRAAL-SG] and V8's TurboFan [V8-Scheduler] were built on it. In 2025, V8 explained why it replaced TurboFan's sea of nodes with Turboshaft, a CFG-based IR [Mer25].

Dependence graphs: PDG, VSDG, RVSDG¶

The program dependence graph (PDG) of Ferrante, Ottenstein and Warren connects statements by data dependences and by control dependences, a relation derived from post-dominance, and drops the CFG [FOW87]. The value dependence graph [WCES94] and the value state dependence graph (VSDG) [JM03] turn this into an executable, SSA-like graph with explicit state edges for side effects. The regionalized VSDG (RVSDG) of Reissmann et al. [RMBS20] makes it hierarchical: conditionals and loops become structured nodes (γ and θ) containing regions, so the graph is acyclic at every level. The research compiler jlm implements it [JLM-RVSDG].

E-graphs¶

An e-graph stores a set of terms, factored into e-classes of equivalent terms, where each e-node points to e-classes rather than to single terms. It comes from congruence closure in theorem provers [NO80]. Equality saturation [TSTL09] applies rewrite rules non-destructively until nothing new appears, then extracts the best term. That avoids the phase-ordering problem of destructive rewriting. The egg library made it fast with rebuilding [WNW+21]. Cranelift's mid-end uses an acyclic variant (the "aegraph") on CLIF [CL-Egraph]. Chapter 17 implements equality saturation.

2. Definitions and algorithms¶

Sea of nodes¶

Definition 8.5.1 (Sea-of-nodes graph)

A sea-of-nodes graph is a directed graph of nodes with ordered inputs. Each node has a kind. Control nodes (Start, If, IfTrue, IfFalse, Region, Loop, Return) have one control input (a Region or Loop has one per incoming path) and form a graph isomorphic to a CFG (Lesson 8.2). Phi nodes have a Region or Loop control input and one data input per path. Pinned nodes (loads, stores, calls, If) have a control input and, for side effects, an effect input. Floating nodes (pure arithmetic, constants) have only data inputs. A schedule maps every non-control node to a block of the control graph.

Definition 8.5.2 (Legal schedule)

Let \(\mathcal{D}\) be the dominator tree of the control graph, and \(\mathrm{depth}(b)\) the loop depth of block \(b\). A schedule \(\mathrm{blk}\) is legal if for every data edge \(x \to y\) (value \(x\) used by \(y\)): \(\mathrm{blk}(x)\) dominates the use block \(u(x, y)\), which is \(\mathrm{blk}(y)\) for an ordinary use and the \(j\)-th predecessor of \(y\)'s region for the \(j\)-th data input of a phi \(y\). Pinned nodes keep their control block.

Algorithm 8.5.3 (Global code motion, Click 1995)

Input: a sea-of-nodes graph whose control part has dominator tree \(\mathcal{D}\) and loop depths; pinned nodes already placed.
Output: a legal schedule (Definition 8.5.2) that places each floating node at the least loop depth possible, and as late as possible among those.
Precondition: the graph comes from a strict SSA program, so every node's inputs dominate some legal position of it.
Postcondition: \(\mathrm{early}(x) \mathrel{\mathrm{dom}} \mathrm{blk}(x) \mathrel{\mathrm{dom}} \mathrm{late}(x)\) for every floating \(x\), and the schedule is legal (Theorem 8.5.9).
Invariant: (early pass) when \(x\) is placed, every input already has \(\mathrm{early}\); (late pass) when \(x\) is placed, every user already has its final block.

function ScheduleEarly(x):                    # postorder over inputs
    if x is pinned or visited: return
    mark x; b ← Start's block
    for each input y of x:
        ScheduleEarly(y)
        if depth_D(blk(y)) > depth_D(b): b ← blk(y)       # the deepest input block
    early(x) ← b; blk(x) ← b

function ScheduleLate(x):                     # postorder over users
    if x is pinned or visited: return
    mark x; lca ← none
    for each use (x → y):
        ScheduleLate(y)
        lca ← LCA_D(lca, u(x, y))                   # u: use block (Definition 8.5.2)
    late(x) ← lca; best ← lca; b ← lca
    while b ≠ early(x):                              # walk up the dominator tree
        b ← idom(b)
        if loopdepth(b) < loopdepth(best): best ← b
    blk(x) ← best
# LCA_D(none, b) = b; LCA_D(a, b) = nearest common ancestor in the dominator tree.

Dependence graphs: PDG, VSDG, RVSDG¶

Definition 8.5.4 (Data and control dependence; PDG)

In a CFG \(G\) with post-dominator tree (Ch 15, Definition 15.4.2), block \(Y\) is control dependent on block \(X\) if \(X\) has an edge \(X \to Z\) such that \(Y\) post-dominates \(Z\), and \(Y\) does not strictly post-dominate \(X\) (Definition 15.4.4). Statement \(t\) is data dependent on \(s\) if \(s\) defines a variable \(v\) and some path from \(s\) to \(t\) contains no other definition of \(v\) before \(t\) uses \(v\). In SSA form this is exactly the def-use edge. The program dependence graph has the statements (and one entry node) as nodes and both kinds of dependence as edges.

Definition 8.5.5 (VSDG and RVSDG)

A VSDG is an acyclic graph of operation nodes with value edges and state edges. The state edges order side effects. Conditionals are \(\gamma\) nodes (a predicate selects one of several value tuples), and loops are \(\theta\) nodes. An RVSDG makes the structure hierarchical. A region is an acyclic graph with arguments and results. A \(\gamma\) node holds one region per alternative and routes its inputs to the chosen region. A \(\theta\) node holds one region that is executed repeatedly: its results are the next iteration's arguments, plus a predicate that says whether to repeat. \(\lambda\) (function), \(\delta\) (global) and \(\phi\) (mutual recursion) nodes complete the language. Every region is acyclic, so loops appear only as \(\theta\) nesting.

Algorithm 8.5.6 (PDG construction)

Input: a CFG in SSA form (Lesson 8.4) with a unique exit.
Output: the PDG: control-dependence edges \(X \to Y\) and data edges def → use.
Precondition: every block reaches the exit (else post-dominance is augmented with a virtual exit, Ch 15, Definition 15.4.1).
Postcondition: the edges are exactly the dependences of Definition 8.5.4 (Theorem 8.5.10).
Invariant: (control part) after processing edge \(A \to B\), every block on the post-dominator-tree path from \(B\) up to, but not including, \(\mathrm{ipdom}(A)\) has the edge \(A \to Y\).

function BuildPDG(G):
    ipdom ← post-dominator tree of G                     # Ch 15
    for each edge A → B of G:
        Y ← B
        while Y ≠ ipdom(A):                               # Ferrante–Ottenstein–Warren walk
            add control edge A → Y; Y ← ipdom(Y)
    for each SSA definition d and each use u of d: add data edge d → u
    return the graph

E-graphs¶

Definition 8.5.7 (E-graph)

Let \(\Sigma\) be a ranked alphabet (Definition 8.3.1). An e-graph is a union-find structure over e-class ids plus a set of e-nodes \(f(c_1, \dots, c_k)\) with \(f \in \Sigma\) and children \(c_i\) that are e-class ids. Each e-node belongs to exactly one e-class. The e-graph represents a term \(f(t_1, \dots, t_k)\) in class \(c\) if \(c\) contains an e-node \(f(c_1, \dots, c_k)\) and each \(t_i\) is represented in \(\mathrm{find}(c_i)\). The congruence invariant: if two e-nodes \(f(c_1, \dots, c_k)\) and \(f(c'_1, \dots, c'_k)\) have \(\mathrm{find}(c_i) = \mathrm{find}(c'_i)\) for all \(i\), they are in the same e-class. The hashcons maps each canonical e-node to its class.

Algorithm 8.5.8 (Equality saturation with rebuilding, egg-style)

Input: a term \(t\), rewrite rules \(\ell_i \to r_i\) (each sound: \(\ell_i\sigma = r_i\sigma\) for every substitution), a cost function, node and iteration limits.
Output: a term of least cost (for a monotone, local cost such as size) among those the final e-graph represents in \(t\)'s class.
Precondition: rules are sound for the semantics.
Postcondition: the output equals \(t\) semantically (Theorem 8.5.12).
Invariant: after every Rebuild, the congruence invariant holds and the hashcons contains exactly the canonical e-nodes.

function Add(f(c1..ck)):
    n ← f(find(c1)..find(ck)); if n ∈ hashcons: return hashcons[n]
    c ← new class {n}; hashcons[n] ← c; for each ci: parents(ci) += (n, c); return c
function Merge(a, b):
    if find(a) = find(b): return
    union(a, b); worklist += find(a)                     # repair later, in batches
function Rebuild():
    while worklist is not empty:
        todo ← { find(c) : c ∈ worklist }; worklist ← []
        for c in todo:
            for (n, pc) in parents(c):                    # re-canonicalize users
                remove n from hashcons; n' ← canonical(n)
                if n' ∈ hashcons: Merge(pc, hashcons[n'])  # congruence found
                hashcons[n'] ← find(pc)
function Saturate(t, rules):
    root ← AddTerm(t)
    repeat until no rule adds anything, or a limit is hit:
        matches ← [ (rule, class, σ) for every e-matching of every ℓ_i ]    # read-only phase
        for (ℓ → r, c, σ) in matches: Merge(c, AddTerm(r σ))              # write phase
        Rebuild()
    return Extract(root)
function Extract(root):                                # bottom-up least cost, to a fixed point
    cost[c] ← ∞ for all classes; repeat: for each class c, for each e-node n = f(c1..ck) in c:
        cost[c] ← min(cost[c], cost_f + Σ cost[ci]);  until no change
    return the term built from the argmin e-nodes, starting at root

3. Worked example¶

Sea of nodes on the running example¶

The running example's loop in sea-of-nodes form (the data edges of the pure computations; || is evaluated as a non-short-circuit or, as arith.ori does in Lesson 8.4's MLIR box, so it is pure):

flowchart BT
  START([Start]) --> LOOP[Loop]
  LOOP --> IFL["If (i ≤ n)"]
  IFL --> BODY[IfTrue: body]
  BODY --> IFC["If (c)"]
  IFC --> THEN[IfTrue: then]
  IFC --> ELSE[IfFalse]
  THEN --> MERGE[Region]
  ELSE --> MERGE
  MERGE -->|back edge| LOOP
  PI[/"φ_i (Loop)"/] -.-> REM3["rem i, 3"]
  PI -.-> REM5["rem i, 5"]
  PI -.-> ADD["add s, i"]
  PI -.-> INC["add i, 1"]
  PS[/"φ_s (Loop)"/] -.-> ADD
  ADD -.-> PS2[/"φ_s' (Region)"/]
  PS -.-> PS2
  INC -.->|back edge| PI
  PS2 -.->|back edge| PS
  REM3 -.-> OR["or (eq … 0) (eq … 0)"]
  REM5 -.-> OR
  OR -.-> IFC

Solid arrows are control, dotted arrows are data. The arithmetic nodes have no control input. Their blocks come from Algorithm 8.5.3. Blocks: S (Start, depth 0), H (Loop header, depth 1), Bd (loop body), T (then), E (else), M (merge region), X (exit, depth 0). Dominator tree: S → H → {Bd, X}, Bd → {T, E, M}.

node	inputs' blocks	early (deepest input)	use blocks	late (LCA)	chosen (min loop depth on H…late)
constants 3, 5, 0, 1	none	S	Bd, M	Bd / M	S (depth 0: hoisted out of the loop)
`rem i, 3`	H (φ_i)	H	Bd (`eq`)	Bd	Bd (H and Bd both depth 1; latest wins)
`rem i, 5`	H	H	Bd	Bd	Bd
`or (…) (…)`	Bd	Bd	Bd (`If c`)	Bd	Bd
`add s, i`	H	H	T (φ_s' input 1 comes from T)	T	T: computed only on the path that needs it
`add i, 1`	H	H	M (φ_i input 2 comes from M, the back-edge source)	M	M

add s, i sank into the then block: the source wrote it there anyway, but GCM would sink it there even if the source had computed it before the if. The constants rose to Start, which is loop-invariant code motion. Had the body contained n * 3 (inputs: the parameter n, block S), GCM would have placed it at depth 0 in S, outside the loop.

Dependence graphs on the running example¶

Control dependences of the running example's CFG (Lesson 8.2), from the post-dominator tree (\(\mathrm{ipdom}\): B0→B1, B1→B9, B2→B6, B3→B6, B4→B6, B5→B6, B6→B8, B7→B8, B8→B1, B9→exit), computed by Algorithm 8.5.6 (control_dependence in tools/course/lib/cfa.py):

edge \(A \to B\)	\(\mathrm{ipdom}(A)\)	walk from \(B\) up to \(\mathrm{ipdom}(A)\)	control edges added
B1→B2	B9	B2, B6, B8, B1	B1→B2, B1→B6, B1→B8, B1→B1
B1→B9	B9	(stops at once)	none
B2→B5	B6	B5	B2→B5
B2→B3	B6	B3	B2→B3
B3→B5	B6	B5	B3→B5
B3→B4	B6	B4	B3→B4
B6→B7	B8	B7	B6→B7
B6→B8	B8	(stops at once)	none
unconditional edges		the target post-dominates the source	none

So the loop body (B2, B6, B8) and the loop test B1 itself are control dependent on B1 (a loop test controls its own next execution). s = add s, i in B7 depends on B6's test of t.1, and B5 (t.1 = 1) depends on both tests of the ||. In an RVSDG the same program is one \(\theta\) node (the while), whose region contains a \(\gamma\) node for the if and a nested \(\gamma\) for the ||, with no control edges at all.

E-graphs on a small term¶

Rules: comm-mul \((\ast\ ?a\ ?b) \to (\ast\ ?b\ ?a)\), mul-shl \((\ast\ ?a\ 2) \to (\ll\ ?a\ 1)\), div-canc \((/\ (\ast\ ?a\ ?b)\ ?b) \to (\ast\ ?a\ (/\ ?b\ ?b))\), div-self \((/\ ?a\ ?a) \to 1\), mul-one \((\ast\ ?a\ 1) \to ?a\) (div-canc and div-self are sound only for mathematical integers with a non-zero divisor, not for wrapping 64-bit arithmetic; this example, like the egg paper's, assumes both). Input \((/\ (\ast\ a\ 2)\ 2)\). The egg run (the real-world box in §7) reports:

iteration	e-nodes / e-classes before	rules applied	effect
1	4 / 4	comm-mul, div-canc, mul-shl	\((\ast\ 2\ a)\) and \((\ll\ a\ 1)\) join \((\ast\ a\ 2)\)'s class; the root class gains \((\ast\ a\ (/\ 2\ 2))\)
2	9 / 6	comm-mul, div-self	\((/\ 2\ 2)\) is merged with the new class of \(1\)
3	11 / 5	mul-one	\((\ast\ a\ 1) = a\): the root class merges with \(a\)'s class
4	11 / 4	none	saturated

Final: 4 e-classes, 10 e-nodes. The root class \(e_0\) contains \(a\), \((\ast\ e_0\ e_7)\), \((\ast\ e_7\ e_0)\) and \((/\ e_2\ e_1)\), where \(e_7 = \{1, (/\ e_1\ e_1)\}\). The e-graph is cyclic: \(e_0\) contains an e-node whose child is \(e_0\). It represents infinitely many terms (\(a\), \(a \cdot 1\), \((a \cdot 1) \cdot 1\), …). Extraction by size picks \(a\) (cost 1).

Try it

No drill: GCM and equality saturation have no small closed-form answers worth grading. The quiz asks for the GCM placement of one node (gcm-late-placement) and the class count of a small e-graph (egraph-classes). Chapter 17's lab implements equality saturation.

4. Invariants and correctness¶

Sea of nodes¶

Theorem 8.5.9 (GCM produces a legal schedule)

If the input graph comes from a strict SSA program, Algorithm 8.5.3 assigns every floating node \(x\) a block \(\mathrm{blk}(x)\) with \(\mathrm{early}(x) \mathrel{\mathrm{dom}} \mathrm{blk}(x) \mathrel{\mathrm{dom}} \mathrm{late}(x)\), and the resulting schedule is legal. Among the blocks on the dominator-tree path from \(\mathrm{early}(x)\) to \(\mathrm{late}(x)\), it chooses one of minimal loop depth, the latest such.

Proof sketch (full proof: [Cli95]; background in [Cli95t])

Early. In a strict SSA program each input \(y\) of \(x\) dominates \(x\)'s original position \(p\), so the input blocks all lie on the dominator-tree path from the root to \(p\) (the dominators of a block form a chain, Ch 15, Theorem 15.1.6). The deepest of them, \(\mathrm{early}(x)\), is dominated by all the others. Every input is therefore available in \(\mathrm{early}(x)\) and in every block it dominates. By induction over the postorder, the same holds after inputs have themselves been moved early, because moving an input up the chain keeps it dominating. Late. \(\mathrm{late}(x)\) is the LCA of all use blocks, so it dominates every use block, and \(\mathrm{early}(x)\) dominates it: \(p\) lies between them (the original position dominates all uses, and early dominates \(p\)). Choice. The walk visits exactly the dominator-tree path from \(\mathrm{late}(x)\) up to \(\mathrm{early}(x)\). Any block \(b\) on it dominates \(\mathrm{late}(x)\), hence every use, and is dominated by \(\mathrm{early}(x)\), hence by every input. That is legality for the edges into and out of \(x\). Users are placed before \(x\) in the late pass, so their blocks are final when \(\mathrm{late}(x)\) is computed. The strict < keeps the latest block among those of minimal depth.

Dependence graphs: PDG, VSDG, RVSDG¶

Theorem 8.5.10 (Algorithm 8.5.6 computes exactly the control dependences)

\(A \to Y\) is added iff \(Y\) is control dependent on \(A\) (Definition 8.5.4).

Proof

This is Theorem 15.4.6 and the correctness of Algorithm 15.4.10 in Ch 15, restated. For an edge \(A \to B\), the blocks \(Y\) that post-dominate \(B\) are the post-dominator-tree ancestors of \(B\) (including \(B\)). \(Y\) does not strictly post-dominate \(A\) iff \(Y\) is not a proper ancestor of \(A\) in the tree. The ancestors of \(B\) that are not proper ancestors of \(A\) are exactly the nodes on the path from \(B\) up to, but not including, \(\mathrm{ipdom}(A)\), since \(\mathrm{ipdom}(A)\) is an ancestor of \(B\) whenever \(B\) does not post-dominate \(A\) (every path from \(B\) to the exit continues a path from \(A\)). If \(B\) post-dominates \(A\), then \(B = \mathrm{ipdom}(A)\) or \(B\) is above it, and the walk adds nothing, correctly. The data part is the definition of SSA def-use edges.

Theorem 8.5.11 (PDGs are adequate: equal dependences, equal behavior)

If two programs (in a structured language with assignment, conditionals and loops) have isomorphic PDGs, they compute the same final values of all variables on every input [HPR88].

Proof sketch (full proof: [HPR88])

Horwitz, Prins and Reps show that a PDG determines, for each statement, which statements must precede it (data and control dependences), and that any two orders consistent with these dependences execute each statement the same number of times with the same operand values. The proof is by induction on loop nesting: inside a loop body, the executions of each statement are matched by their iteration numbers, and control dependence fixes which iterations run. The result needs the language restrictions: with arbitrary gotos, or with aliasing that the dependences do not record, isomorphic PDGs do not guarantee equivalence. VSDG and RVSDG build semantics directly into the graph (the state edge and the γ/θ nodes), so there adequacy holds by construction, since the graph is the program [RMBS20].

E-graphs¶

Theorem 8.5.12 (Equality saturation is sound; extraction finds the cheapest represented term)

(a) After each iteration of Algorithm 8.5.8, every term represented in the root class is semantically equal to \(t\). (b) After Rebuild, the congruence invariant holds. (c) Extract returns a least-cost term among those represented in the root class, for a cost that is a sum over e-nodes.

Proof sketch (full proofs: congruence closure [NO80]; rebuilding [WNW+21, §3]; saturation [TSTL09])

(a) Induction on merges: each merge joins the class of a match \(\ell\sigma\) with the class of \(r\sigma\), which are equal by soundness of the rule. Congruence merges join \(f(\vec{c})\) and \(f(\vec{c}')\) with equal children, and substituting equals for equals preserves equality. Equality is an equivalence relation, so all terms in a class are equal. (b) Merges only make classes larger, which can make two parents' canonical forms equal. Rebuild re-canonicalizes every parent of every changed class and merges parents whose canonical forms collide. It loops until the worklist is empty, at which point no two canonical e-nodes collide in the hashcons, which is the invariant. Deferring this repair to the end of an iteration (instead of after every merge, as in classical congruence closure) is egg's contribution: it does the same work once per batch. (c) The cost fixed point is the Bellman–Ford-style least solution of \(\mathrm{cost}(c) = \min_{n \in c} (\mathrm{cost}_f + \sum_i \mathrm{cost}(c_i))\). Costs are non-negative, so cycles never lower a cost, and the argmin e-nodes form a finite term.

Proposition 8.5.13 (E-graphs can represent exponentially many terms in linear space)

With the rule \((\ast\ ?a\ ?b) \to (\ast\ ?b\ ?a)\) and the term \(x_1 \ast (x_2 \ast (\cdots \ast x_k))\), the saturated e-graph has \(O(k)\) e-classes and e-nodes but represents \(2^{k-1}\) distinct terms in the root class.

Proof

Each product \(p_j = x_j \ast p_{j+1}\) gets one class containing two e-nodes, \((\ast\ x_j\ p_{j+1})\) and \((\ast\ p_{j+1}\ x_j)\). There are \(k-1\) product classes and \(k\) leaf classes, so \(O(k)\) in total. A represented term chooses one of the two orders independently at each of the \(k - 1\) products, which gives \(2^{k-1}\) distinct terms. With commutativity alone the e-graph stays linear. Adding associativity makes the e-graph itself exponential (the pathological family of §5), which is the blow-up that node limits exist to contain.

5. Complexity¶

Variables: \(N\) = nodes, \(E\) = edges, \(m\) = CFG blocks, \(d\) = dominator-tree depth, \(\lvert\mathcal{E}\rvert\) = e-nodes.

Technique	Time (worst)	Time (typical)	Space	Justification
Sea of nodes: GCM (Alg. 8.5.3)	\(O(N \cdot d + E)\)	near-linear	\(O(N + E)\)	each node visited once per pass; the walk up the dominator tree is at most \(d\) steps
PDG construction (Alg. 8.5.6)	\(O(m^2)\) control edges	\(O(m + e)\)	\(O(m^2)\) worst	[FOW87]; the walk may add \(O(m)\) edges per CFG edge (a chain of nested ifs)
RVSDG construction from a CFG	linear after restructuring	linear		[RMBS20]; irreducible graphs must first be restructured, which can grow the code
E-graphs: equality saturation	unbounded (may not terminate)	limited by node and time limits	\(O(\lvert\mathcal{E}\rvert)\)	Proposition 8.5.13 and the family below; one iteration is one e-matching pass plus one `Rebuild` over the changed classes [WNW+21, §3]

Pathological family. For e-graphs, take associativity and commutativity of \(+\) and the term \(x_1 + (x_2 + (\cdots + x_k))\). Rearranging with the two rules produces, for every non-empty subset \(S \subseteq \{x_1, \dots, x_k\}\), a term that sums exactly \(S\) (bring the elements of \(S\) together by commuting, then re-associate). Terms with different sets of summands are never merged, so the saturated e-graph has at least \(2^k - 1\) e-classes. Saturation is exponential in \(k\) for a linear-size input, which is why production users set node limits. For sea of nodes, the pathological case is compile time, not size: V8 reports that TurboFan's load elimination had to bail out on large graphs, and that the replacement CFG-based version is up to 190 times faster on them [Mer25].

Sea of nodes¶

Multiple effect chains (one per memory region) let more nodes float. V8 kept a single chain because "managing a single effect chain is already very error prone" [Mer25].
Graal's graph keeps fixed nodes in a linked control list and floating nodes separate, with a scheduler that can run several times [GRAAL-SG]. The trade-off: simpler in-order traversal at the cost of a heavier node class hierarchy.
Back to a CFG (V8 Turboshaft, 2022–2025): pure computations are positioned in blocks, and a separate value-numbering and code-motion pass does what GCM did. V8 reports compile time divided by 2 and about 3× fewer L1 data-cache misses [Mer25].

Dependence graphs: PDG, VSDG, RVSDG¶

System dependence graphs extend PDGs across procedures for interprocedural slicing (Horwitz, Reps and Binkley). The trade-off is a more complex construction.
Gated SSA keeps the CFG but annotates phis with predicates (γ functions), which is half-way to the VSDG.
RVSDG trades the need to restructure irreducible control flow for a representation in which dead-code elimination, common-node elimination and invariant motion are simple graph operations [RMBS20].

E-graphs¶

E-class analyses (egg) attach lattice facts (constants, intervals) to classes and merge them on union, which makes constant folding part of saturation [WNW+21, §4].
Acyclic e-graphs (Cranelift's aegraph) keep the graph acyclic, rewrite eagerly when nodes are created, and elaborate the chosen nodes back into a CFG with scoped value numbering. That bounds the cost for a production JIT [CL-Egraph].
Rule scheduling and limits (backoff schedulers in egg, iteration and node limits) trade completeness for predictable compile time.

7. In real compilers¶

Sea of nodes¶

HotSpot C2: class Node in src/hotspot/share/opto/node.hpp; GCM as PhaseCFG::schedule_early, PhaseCFG::schedule_late and PhaseCFG::global_code_motion in src/hotspot/share/opto/gcm.cpp (OpenJDK tag jdk-21-ga) [HS-GCM]. Graal: StructuredGraph in compiler/src/jdk.internal.vm.compiler/src/org/graalvm/compiler/nodes/StructuredGraph.java (tag vm-23.1.0) [GRAAL-SG]. V8 TurboFan: Scheduler::ScheduleEarly and Scheduler::ScheduleLate in src/compiler/scheduler.cc; Turboshaft's CFG in src/compiler/turboshaft/graph.h (V8 12.4.254.21, the version in Node.js 22) [V8-Scheduler]. The product builds of OpenJDK 21 in the course container do not print C2's graph (-XX:+PrintIdeal is a debug-build flag), so the box below uses V8.

V8 12.4: TurboFan's sea of nodes, then Turboshaft's CFG, in one compilation

Reproduce (Node.js 22.22.2, V8 12.4.254.21-node.39; Python 3.11 to summarize the JSON trace):

cat > hot.js <<'EOF'
function euler1(n) {
  let s = 0;
  for (let i = 1; i <= n; i++)
    if (i % 3 === 0 || i % 5 === 0) s += i;
  return s;
}
let t = 0;
for (let k = 0; k < 20000; k++) t += euler1(1000 + (k & 7));
console.log(t);
EOF
node --trace-turbo --trace-turbo-filter=euler1 --no-maglev hot.js
cat > summarize.py <<'EOF'
import collections, glob, json
d = json.load(open(glob.glob("turbo-euler1-*.json")[0]))
for ph in d["phases"]:
    if ph.get("type") == "graph":                      # Turbofan: a sea of nodes
        es = collections.Counter(e["type"] for e in ph["data"]["edges"])
        print(f"{ph['name']:<32} sea of nodes: {len(ph['data']['nodes']):>3} nodes, edges {dict(sorted(es.items()))}")
    elif ph.get("type") == "schedule":
        print(f"{ph['name']:<32} (the scheduler assigns every node to a block)")
    elif ph.get("type") == "turboshaft_graph":         # Turboshaft: a CFG of blocks
        print(f"{ph['name']:<32} CFG: {len(ph['data']['blocks']):>2} blocks, {len(ph['data']['nodes']):>3} operations")
EOF
python3 summarize.py

Output (complete; node also prints "Concurrent recompilation has been disabled for tracing.", the begin/finish lines, and the result 4705927500):

V8.TFBytecodeGraphBuilder        sea of nodes:  60 nodes, edges {'context': 4, 'control': 43, 'effect': 21, 'frame-state': 10, 'value': 66}
V8.TFInlining                    sea of nodes:  58 nodes, edges {'context': 4, 'control': 41, 'effect': 21, 'frame-state': 10, 'value': 63}
V8.TFEarlyGraphTrimming          sea of nodes:  58 nodes, edges {'context': 4, 'control': 41, 'effect': 21, 'frame-state': 10, 'value': 63}
V8.TFTyper                       sea of nodes:  58 nodes, edges {'context': 4, 'control': 41, 'effect': 21, 'frame-state': 10, 'value': 63}
V8.TFTypedLowering               sea of nodes:  57 nodes, edges {'context': 2, 'control': 41, 'effect': 21, 'frame-state': 10, 'value': 61}
V8.TFLoopPeeling                 sea of nodes:  89 nodes, edges {'context': 3, 'control': 68, 'effect': 37, 'frame-state': 18, 'value': 106}
V8.TFLoadElimination             sea of nodes:  87 nodes, edges {'context': 3, 'control': 66, 'effect': 36, 'frame-state': 18, 'value': 106}
V8.TFEscapeAnalysis              sea of nodes:  87 nodes, edges {'context': 3, 'control': 66, 'effect': 36, 'frame-state': 18, 'value': 106}
V8.TFSimplifiedLowering          sea of nodes:  98 nodes, edges {'context': 3, 'control': 60, 'effect': 30, 'frame-state': 18, 'value': 115}
V8.TFGenericLowering             sea of nodes: 125 nodes, edges {'control': 81, 'effect': 40, 'frame-state': 15, 'value': 145}
V8.TFEarlyOptimization           sea of nodes: 124 nodes, edges {'control': 81, 'effect': 40, 'frame-state': 15, 'value': 141}
schedule                         (the scheduler assigns every node to a block)
V8.TFTurboshaftBuildGraph        CFG: 27 blocks,  83 operations
V8.TFTurboshaftMachineLowering   CFG: 42 blocks, 191 operations
V8.TFTurboshaftStoreStoreElim    CFG: 31 blocks, 130 operations
V8.TFTurboshaftOptimize          CFG: 27 blocks, 124 operations
V8.TFTurboshaftCodeEliminationAndSimplification CFG: 27 blocks, 117 operations
V8.TFTurboshaftDecompressionOpt  CFG: 27 blocks, 117 operations
before instruction selection     CFG: 27 blocks, 117 operations

What to notice: the front half of the pipeline is a sea of nodes with separate value, effect and control edges (Definition 8.5.1). frame-state edges carry the deoptimization state (Ch 0). Then the schedule phase, TurboFan's GCM, places every node in a block, and from TFTurboshaftBuildGraph on the IR is a CFG in which every operation has a block. This is the state of the migration the V8 blog describes: JavaScript's "frontend of the … pipeline" still uses sea of nodes, and the backend uses Turboshaft [Mer25]. LoopPeeling grows the graph from 57 to 89 nodes: it duplicates the first iteration of the loop.

Dependence graphs: PDG, VSDG, RVSDG¶

LLVM has a loop-level data dependence graph, DataDependenceGraph with PiBlockDDGNode for dependence cycles, in llvm/include/llvm/Analysis/DDG.h and llvm/lib/Analysis/DDG.cpp (LLVM 23.1.2) [LLVM-DDG]. Control dependence comes from post-dominance (Ch 15). jlm implements the RVSDG: GammaNode in jlm/rvsdg/gamma.hpp and ThetaNode in jlm/rvsdg/theta.hpp (commit 4da82da0) [JLM-RVSDG]. No production compiler uses a PDG as its main IR. PDGs live on in slicing tools and in loop transformations, which is where LLVM's DDG is used.

LLVM's data dependence graph of a loop

Reproduce (clang 23.1.2, opt 23.1.2; awk renames the run-dependent node addresses to N1, N2, … in order of appearance):

cat > ddg.c <<'EOF'
void prefix(long *a, const long *b, long n) {
  for (long i = 1; i < n; i++)
    a[i] = a[i - 1] + b[i];
}
EOF
clang-23 -O1 -fno-discard-value-names -S -emit-llvm -fno-unroll-loops -fno-vectorize ddg.c -o ddg.ll
opt -passes='print<ddg>' -disable-output ddg.ll 2>&1 \
  | awk '{ while (match($0, /0x[0-9a-f]+/)) { a = substr($0, RSTART, RLENGTH); if (!(a in m)) m[a] = "N" (++k); $0 = substr($0, 1, RSTART-1) m[a] substr($0, RSTART+RLENGTH) } print }'

Output (complete):

'DDG' for loop 'for.body':
Node Address:N1:root
 Edges:
  [rooted] to N2
  [rooted] to N3

Node Address:N3:pi-block
--- start of nodes in pi-block ---
Node Address:N4:single-instruction
 Instructions:
    %i.09 = phi i64 [ 1, %for.body.preheader ], [ %inc, %for.body ]
 Edges:
  [def-use] to N5

Node Address:N5:single-instruction
 Instructions:
    %inc = add nuw nsw i64 %i.09, 1
 Edges:
  [def-use] to N4
--- end of nodes in pi-block ---
 Edges:
  [def-use] to N6
  [def-use] to N7
  [def-use] to N8

Node Address:N8:multi-instruction
 Instructions:
    %exitcond.not = icmp eq i64 %inc, %n
    br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body, !llvm.loop !11
 Edges:none!

Node Address:N7:single-instruction
 Instructions:
    %arrayidx1 = getelementptr inbounds nuw [8 x i8], ptr %b, i64 %i.09
 Edges:
  [def-use] to N2

Node Address:N6:single-instruction
 Instructions:
    %0 = getelementptr [8 x i8], ptr %a, i64 %i.09
 Edges:
  [def-use] to N2

Node Address:N2:pi-block
--- start of nodes in pi-block ---
Node Address:N9:single-instruction
 Instructions:
    %store_forwarded = phi i64 [ %load_initial, %for.body.preheader ], [ %add, %for.body ]
 Edges:
  [def-use] to N10

Node Address:N11:single-instruction
 Instructions:
    %1 = load i64, ptr %arrayidx1, align 8, !tbaa !9
 Edges:
  [def-use] to N10
  [memory] to N12

Node Address:N10:single-instruction
 Instructions:
    %add = add nsw i64 %1, %store_forwarded
 Edges:
  [def-use] to N12
  [def-use] to N9

Node Address:N12:single-instruction
 Instructions:
    store i64 %add, ptr %0, align 8, !tbaa !9
 Edges:
  [memory] to N11
--- end of nodes in pi-block ---
 Edges:none!

What to notice: the nodes are LLVM instructions and the edges are dependences, with no CFG. def-use edges are SSA data dependences, and memory edges link the load of b[i] and the store to a[i], which may alias. A pi-block groups a dependence cycle (a strongly connected component): the induction variable (%i.09 ↔ %inc) and the recurrence through %store_forwarded, the carried value of a[i-1] that LoopLoadElimination already forwarded from the previous store. The graph between pi-blocks is acyclic, which is what a vectorizer or loop distribution needs. This is the VSDG idea of a graph whose only cycles are explicit loops (θ), applied to one loop.

E-graphs¶

egg: EGraph::add, EGraph::union and EGraph::rebuild in src/egraph.rs, and Runner in src/run.rs (tag v0.11.0) [EGG-Src]. Cranelift: EgraphPass in cranelift/codegen/src/egraph.rs, with the rewrite rules written in ISLE under cranelift/codegen/src/opts/ and loaded from cranelift/codegen/src/opts.rs (wasmtime v37.0.2) [CL-Egraph]. The v11 -> v35 alias lines in Lesson 8.4's Cranelift box are what that pass leaves behind after rewriting srem v6, 3 into a multiplication by a magic constant.

egg saturates (a·2)/2 and extracts a

Reproduce (Rust 1.94.1 / cargo; the crate egg 0.11.0 from crates.io):

cargo new --quiet eggdemo && cd eggdemo
echo 'egg = "=0.11.0"' >> Cargo.toml
cat > src/main.rs <<'EOF'
use egg::{rewrite as rw, *};

fn main() {
    let rules: &[Rewrite<SymbolLang, ()>] = &[
        rw!("comm-mul";  "(* ?a ?b)"        => "(* ?b ?a)"),
        rw!("mul-shl";   "(* ?a 2)"         => "(<< ?a 1)"),
        rw!("div-canc";  "(/ (* ?a ?b) ?b)" => "(* ?a (/ ?b ?b))"),
        rw!("div-self";  "(/ ?a ?a)"        => "1"),
        rw!("mul-one";   "(* ?a 1)"         => "?a"),
    ];
    let start: RecExpr<SymbolLang> = "(/ (* a 2) 2)".parse().unwrap();
    let runner = Runner::default().with_expr(&start).run(rules);
    let extractor = Extractor::new(&runner.egraph, AstSize);
    let (cost, best) = extractor.find_best(runner.roots[0]);
    println!("input:     {}", start);
    for (k, it) in runner.iterations.iter().enumerate() {
        let mut applied: Vec<String> = it.applied.iter().map(|(r, n)| format!("{}x{}", r, n)).collect();
        applied.sort();
        println!("iteration {}: {} e-nodes, {} e-classes before; applied: {}", k + 1,
                 it.egraph_nodes, it.egraph_classes, if applied.is_empty() { "-".to_string() } else { applied.join(", ") });
    }
    println!("stop:      {:?} after {} iterations", runner.stop_reason.unwrap(), runner.iterations.len());
    println!("e-graph:   {} e-classes, {} e-nodes", runner.egraph.number_of_classes(), runner.egraph.total_number_of_nodes());
    println!("best:      {} (cost {})", best, cost);
    let mut classes: Vec<_> = runner.egraph.classes().collect();
    classes.sort_by_key(|c| c.id);
    for c in classes {
        let mut ns: Vec<String> = c.iter().map(|n| {
            let kids: Vec<String> = n.children.iter().map(|k| format!("e{}", runner.egraph.find(*k))).collect();
            if kids.is_empty() { format!("{}", n) } else { format!("({} {})", n, kids.join(" ")) }
        }).collect();
        ns.sort();
        let root = if runner.egraph.find(runner.roots[0]) == c.id { "  <- root" } else { "" };
        println!("  e{} = {{ {} }}{}", c.id, ns.join(", "), root);
    }
}
EOF
cargo run --quiet --release

Output (complete):

input:     (/ (* a 2) 2)
iteration 1: 4 e-nodes, 4 e-classes before; applied: comm-mulx1, div-cancx1, mul-shlx1
iteration 2: 9 e-nodes, 6 e-classes before; applied: comm-mulx1, div-selfx1
iteration 3: 11 e-nodes, 5 e-classes before; applied: mul-onex1
iteration 4: 11 e-nodes, 4 e-classes before; applied: -
stop:      Saturated after 4 iterations
e-graph:   4 e-classes, 10 e-nodes
best:      a (cost 1)
  e0 = { (* e0 e7), (* e7 e0), (/ e2 e1), a }  <- root
  e1 = { 2 }
  e2 = { (* e0 e1), (* e1 e0), (<< e0 e7) }
  e7 = { (/ e1 e1), 1 }

What to notice: the trace of §3. Nothing is destroyed: the root class still contains the input \((/\ e_2\ e_1)\) next to \(a\), and \(e_2\) holds both \(a \cdot 2\) and \(a \ll 1\). So a cost model that preferred shifts could extract (/ (<< a 1) 2) instead, with no phase-ordering problem. The cycle \(e_0 \ni (\ast\ e_0\ e_7)\) is Definition 8.5.7's representation of \(a = a \cdot 1\). Class ids are egg's internal union-find ids.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Sea of nodes	code motion and value numbering for free; order only from real dependences	GCM \(O(N d + E)\) · V8 found SoN compile time about 2× that of its CFG replacement [Mer25]	hard to read and debug ("manually/visually inspecting … is hard" [Mer25]); needs a scheduler	high: effect chains, scheduling, deopt state	HotSpot C2, Graal; V8 TurboFan (being replaced by Turboshaft)
Dependence graphs: PDG, VSDG, RVSDG	only true dependences; RVSDG makes DCE, CSE and invariant motion graph operations	PDG \(O(m^2)\) control edges worst · RVSDG linear after restructuring	no CFG to print; needs a CFG reconstruction for code generation	high (restructuring, γ/θ regions)	slicing tools, LLVM's loop DDG, research compilers (jlm)
E-graphs	all rewrites at once, no phase ordering; cheapest-term extraction	exponential worst case; limited by node and iteration limits · the egg example saturates in 4 iterations	explanations (egg can explain why two terms are equal)	moderate with a library (egg), high for a production aegraph	superoptimizers, Herbie, Cranelift's mid-end (aegraph), Ch 17

Choose sea of nodes when the optimizer is dominated by code motion and value numbering over mostly pure code, and you can afford a scheduler (Java's C2 and Graal). For effect-heavy languages, the V8 experience argues for a CFG. Choose a dependence graph for analyses whose question is dependence itself (slicing, parallelization, loop distribution), or for research compilers that want the simplest possible optimizations. Choose e-graphs for algebraic rewriting where rule order matters. Contain them with limits, or use the acyclic variant, in a JIT.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch08.yaml`)	Drill	Flashcard tag	Exercises
Sea of nodes	`gcm-late-placement`, `son-why-v8-left`	none: GCM on hand-sized graphs is the table of §3; the quiz asks for a placement	`sea-of-nodes`	—
Dependence graphs: PDG, VSDG, RVSDG	`pdg-control-dep`, `rvsdg-theta`	`./course drill post-dominance` (Ch 15: control dependence)	`dependence-graphs`	—
E-graphs	`egraph-classes`, `egraph-extraction`	none: saturation is graded in Ch 17's lab	`egraphs`	Ch 17

Floating does not mean free

A floating node still has to be placed. GCM places add s, i in the then block, but a node used on every path through a switch floats up to the common dominator and is then computed on paths that do not need it. That is the V8 blog's a / b example [Mer25], and the reason GCM must pick the latest block of minimal loop depth, not the earliest.

References¶

See the chapter references.

Lesson 8.5 — Graph IRs beyond the CFG: sea of nodes, dependence graphs, e-graphs¶

1. Problem and motivation¶

Sea of nodes¶

Dependence graphs: PDG, VSDG, RVSDG¶

E-graphs¶

2. Definitions and algorithms¶

Sea of nodes¶

Dependence graphs: PDG, VSDG, RVSDG¶

E-graphs¶

3. Worked example¶

Sea of nodes on the running example¶

Dependence graphs on the running example¶

E-graphs on a small term¶

4. Invariants and correctness¶

Sea of nodes¶

Dependence graphs: PDG, VSDG, RVSDG¶

E-graphs¶

5. Complexity¶

6. Variants and refinements¶

Sea of nodes¶

Dependence graphs: PDG, VSDG, RVSDG¶

E-graphs¶

7. In real compilers¶

Sea of nodes¶

Dependence graphs: PDG, VSDG, RVSDG¶

E-graphs¶

8. Comparison¶

9. Assessment¶

References¶