Sea of Nodes: Scheduling Without a Fixed Instruction Order

Every IR discussed so far keeps an instruction list. Even SSA form, which makes values explicit, preserves a linear order inside each block, and passes walk that order. The order is a convenience for the programmer and a constraint for the optimiser: it encodes scheduling decisions that were made before any optimisation ran, and every pass that wants to move an instruction must prove the move legal.

Sea of nodes removes the order. The program is a graph in which instructions are nodes and dependences are edges. Data edges run from definitions to uses. Control edges run from a control node to the operations that must execute under it. Memory edges run between operations that touch memory, in the order they must execute. There is no block structure at all in the representation; blocks are reconstructed when a schedule is needed, which is at the very end.

The idea is radical in a specific way. It is not that the order is unknown; it is that the order is not represented, so no pass can accidentally depend on it. Optimisation becomes a graph rewrite problem, and scheduling becomes a separate, explicit step whose cost model can be applied once with full knowledge of the final graph.

Three Kinds of Edge

A node in the sea has inputs typed by their role. The data inputs are the values it computes from. The control input is the control token that must be active for it to execute. The memory input is the memory state it reads or writes, and for a store or a call the node produces a new memory state as an output.

The control token is the mechanism that replaces block structure. A branch node takes a control token and a predicate, and produces two control tokens, one for each successor. Every operation that has side effects or can trap takes a control token as an input, which places it after the branch. Operations that are pure take no control input, which is what makes them movable: a pure arithmetic node can be duplicated, sunk, or hoisted anywhere its data inputs are available, and the graph remains valid.

The memory token plays the same role for memory that the control token plays for control, and it is what makes the alias reasoning explicit. A load takes a memory input and produces both a value and a new memory token; a store takes a memory input and produces a new one. Two loads that do not alias can be made independent by routing them from the same memory input rather than from each other, which lets the scheduler interleave them; a pass that wants to forward a store to a load redirects the load’s memory input to the store’s own input and replaces the loaded value with the stored one, leaving the token chain itself untouched. This is the same information that Memory SSA and Alias-Partitioned Heaps encodes with versions and phis, expressed as graph edges rather than as numbered names.

Loops are represented by a phi-like node with a back edge. A loop’s control token is produced by the loop’s own back branch, and the graph is cyclic at that point. The representation tolerates cycles because the scheduler and the analyses that walk it use a worklist with a visited set rather than a recursive descent that would not terminate.

Global Value Numbering as the Main Rewrite

With no order and explicit data edges, the dominant optimisation is a hash-consing pass: assign each node a value number derived from its opcode and the value numbers of its inputs, and replace any node whose number already exists with the existing node. Two additions of the same operands become one addition, and every consumer of the second is rewired to the first.

The rewiring is the interesting part. Because uses are edges, replacing a node is a pointer update on each consumer’s input slot, and the consumers are immediately known. There is no need to search for uses, no need to repair a linear order, and no need to re-run a liveness computation. The pass is a single traversal with a hash table, and its cost is proportional to the number of nodes and edges.

Phi nodes complicate the numbering. A phi’s value depends on the values on each incoming path, so its number must incorporate all of them, and a cyclic phi’s number depends on itself. The standard treatment is to assign each phi a unique number initially and to iterate the numbering to a fixed point, merging phis whose inputs become equal. On a loop with a phi that is provably redundant, the iteration discovers the equality and removes the phi; on a loop where the phi genuinely varies, the numbers stay distinct and the iteration terminates because the number of distinct values is finite.

The combination of value numbering with the graph form is what gives the approach its power. Because pure nodes have no control dependence, a computation can be moved out of a loop by rewiring its inputs to values available outside, without consulting block structure for permission; the remaining obligations are that the inputs are available on every path into the loop and that the move does not make the value live somewhere it was not. Because memory nodes carry explicit tokens, the legality of moving a load is encoded in the token graph rather than inferred from the block order.

Scheduling Is Deferred, Not Avoided

The graph must eventually become machine code, and machine code is sequential. The scheduler’s job in this design is to partition the graph into blocks and order instructions within them, using the control edges to determine which operations belong to which branch and the memory edges to determine ordering constraints.

The partition is not unique, which is the point. A pure node can be placed in any block where its inputs are available and from which all its consumers are reachable, and the choice affects register pressure and code size. Placing it in the block where it is computed in the source is one option; placing it as late as possible, just before its first consumer, shortens live ranges; sinking it into a block that dominates the consumers but executes less often reduces dynamic instruction count, provided such a block exists on every path from the inputs to the consumers. The scheduler picks among these with a cost model, and the model has more freedom than a block-local scheduler because it can move a computation across block boundaries as long as the data edges permit.

The global scheduler in this design works by a set of local scheduling rules that walk the graph from the end backwards, placing each node as late as the reconstructed control flow allows, which for a pure node means the block that dominates all its consumers and is itself dominated by every input, taken as late as possible along the dominator chain. Nodes whose placement is ambiguous are then moved by a heuristic that prefers blocks with lower execution frequency, subject to the constraint that the move does not lengthen a live range past what the register budget allows. The result is a block partition that did not exist in the IR, derived from the graph and the cost model rather than inherited from the front end.

This is the deepest difference from a block-based IR. In a block-based IR, the block structure is a fact that passes must preserve or repair, and moving code across a boundary requires updating the CFG, the phis, and the liveness. In the sea of nodes, block structure is an output of scheduling, so there is nothing to preserve, and the only invariant is that the graph’s edges are respected.

What Becomes Harder

The absence of order is not free. Analyses that are naturally expressed as a forward walk over a sequence become graph traversals with worklists, and the termination argument is less obvious. Liveness, for instance, is a backward problem over the graph, and a value is live at a point if some path from that point reaches a use without an intervening definition; in a graph with cycles, the computation is a fixed point rather than a single pass.

Debug information is harder. Source positions attach to nodes, and the mapping from a machine instruction back to a source line depends on where the scheduler placed the node. When a node is duplicated, the copies share a source position; when a node is moved into a colder block, its position moves with it, and a debugger stepping through the source may see a value computed at a point that does not correspond to the source order. The information is recoverable but requires care that a linear IR gets for free.

Determinism is a third issue. A hash-consing pass that iterates over a hash table produces a graph whose node identity depends on iteration order, and if that order varies between runs, the resulting code can vary. Compilers that use this design must impose a deterministic traversal order, usually by numbering nodes in creation order and iterating in that order rather than over the hash table. The requirement is not specific to this IR, but it is more visible because so much of the compilation is graph rewriting.

Verification is the fourth. A linear IR has a natural verifier that walks instructions in order and checks each against the current state. A graph IR has no current state to check against; verifying it means checking that every edge connects nodes of compatible types, that every cycle through a phi has a definition on the entry path, and that every side-effecting node is reachable from a control token. Those checks are expressible but they are structural rather than sequential, and a verifier bug is harder to localise.

Where the Design Fits

The design is most attractive for a just-in-time compiler, where the graph is built from a bytecode or a high-level IR, optimised aggressively, and scheduled once for the target. The freedom to move computations across blocks pays off in the optimisations that matter most for dynamic languages: inlining, escape analysis, and the elimination of redundant type checks all benefit from a representation where the moved operations have no block affiliation to repair.

It is less attractive for a compiler that must produce predictable code quickly. The graph rewriting passes are simple individually but there are many of them, and the scheduling step at the end is where the cost concentrates. A block-based IR with a fixed order can be optimised with local passes that are cheap and predictable, and the code quality is often close enough that the extra machinery does not pay.

The two designs also differ in how they handle the boundary between optimisation and allocation. A sea-of-nodes compiler typically schedules late, after all graph rewrites, and then allocates; the schedule is chosen with pressure in mind but the allocation runs on the scheduled form. A block-based compiler typically allocates on the SSA form and schedules after, with the constraints described in Instruction Scheduling and Its Dependence on the Graph. Neither order is strictly better, and the choice follows from which representation the optimiser is built around.