THE SEA OF NODES data and control, one graph, no schedule until the end
Most IRs fix an order: instructions sit in basic blocks in a line. Cliff Click's sea of nodes refuses to, until it must. Every operation is a node whose edges are its data dependencies; control is just another kind of edge; and a node floats anywhere its inputs allow — no committed order. This makes optimizations that need reordering (global CSE, code motion) fall out almost for free, because the IR never over-specified the schedule. Only at the very end does a scheduler place the floating nodes back into blocks.
THE TECHNIQUE nodes = operations, edges = dependencies; schedule last
For (a+b)*(a+b), the sea-of-nodes shares the single + node (global CSE for free); a linear IR emits the add twice. The demo counts nodes vs linear ops: live demo
HISTORY & CREDIT Click & Paleczny, 1995
“An IR is a list of instructions in order.” — the order is a decision you can defer. The sea of nodes keeps only the dependencies that are real and lets everything else float, so reordering optimizations become graph facts, not rewrites. Schedule last, optimize freely. cited
1995 · Cliff Click & Michael Paleczny — “A Simple Graph-Based Intermediate Representation”: the sea of nodes, unifying data and control in one floating graph — the IR inside HotSpot's C2 JIT. lineage · program dependence graphs (Ferrante-Ottenstein-Warren 1987) as the ancestor. now · HotSpot C2 and Java's Graal use it; a canonical modern optimizing IR.
By keeping only real dependencies, the sea makes value-identity global: two identical subexpressions are literally the same node, so CSE is not a pass but a fact. The cost is a scheduler that must put the float back in order. Click-Paleczny 1995
RECOMMEND FOR I-13 sea nodes vs linear ops, computed
On the canonical compiler, (a+b)*(a+b) evaluates to 49; i13's linear IVM lowers it to 8 ops that compute a+b twice, where a sea-of-nodes shares one + node (5 nodes):
$ i13 run sea.i13 # (a+b)*(a+b), a=3 b=4
v = 49
$ i13 dump sea.i13 --ivm # fn e: code=8 (a+b computed twice; no CSE)
Recommend: i13 makes the opposite choice, on purpose — and the contrast names why. The sea of nodes exists to float code and reorder it invisibly; i13's IVM is a linear, scheduled instruction list you can read in source order (its dump --ivm shows a+b computed twice, no CSE). The sea optimizes by hiding the schedule; i13 verifies by fixing it. For a JIT chasing peak throughput the sea wins; for a compiler whose product is a proof that EXECUTION ≠ COMMIT, the visible linear IR is the point. Different goals, opposite IRs.