Instruction Scheduling
A modern processor is a pipeline: it starts a new instruction most cycles, but each instruction's
result takes several cycles to appear. A load might not deliver its value for three or four
cycles; a multiply for two or three. If the very next instruction needs that result, the pipeline
stalls — it inserts bubbles and waits, wasting cycles. Instruction
scheduling reorders the instructions of a block so that independent work fills those waiting
cycles, hiding the latencies, without changing what the program computes.
The catch is the italic clause. You may reorder only in ways that preserve the results, which means
you must respect every data dependence between instructions. Those dependences form
a directed acyclic graph, and scheduling is the problem of laying the DAG's nodes out in time — one
legal topological order among many — so as to minimise stalls.
Three kinds of dependence pin instructions in order
An instruction B must stay after an instruction
A whenever moving it would change a value. There are exactly three ways
that happens:
- RAW (read-after-write, a true dependence):
A writes a value that B reads —
B must wait for A's result;
- WAR (write-after-read, an anti-dependence):
A reads a location that B overwrites —
B must not clobber it before A has read;
- WAW (write-after-write, an output dependence): both write the same
location — their order fixes which write survives.
Only RAW is a real flow of data; WAR and WAW are artefacts of reusing a register
or memory cell. That distinction matters enormously: RAW dependences are fundamental and cannot be
removed, but WAR and WAW can often be dissolved by renaming — giving the second
writer a fresh register so the false conflict disappears and the schedule gains freedom.
The dependence DAG
Draw one node per instruction and an edge A \to B whenever
B depends on A, weighting the edge by
A's latency — how many cycles before its result is
usable. Any topological order of this DAG is a correct program; scheduling picks the order
that runs fastest. Here is the DAG for a small block that computes
x = (a + b) \times c with loads of latency 3 and a multiply of latency 2:
The three loads i_1, i_2, i_4 have no incoming edges — they are
independent and can go in any order, or be spread out to overlap their long latencies. The
critical path i_1 \to i_3 \to i_5 \to i_6 (weight
3+1+2+1 = 7) is the longest latency-weighted chain; no schedule can finish
sooner than the critical path allows, so it sets the lower bound and tells the scheduler which
instructions are most urgent.
List scheduling: the workhorse heuristic
Optimal scheduling of a DAG is NP-hard, so compilers use list scheduling — a
greedy, cycle-by-cycle simulation of the pipeline. Maintain a ready list of
instructions all of whose predecessors have completed (their results are available). Each cycle,
issue the ready instruction of highest priority; the usual priority is the
critical-path length from that node, so the most latency-critical work goes first.
If nothing is ready, the cycle is a stall.
compute latency-weighted critical path from each node
cycle ← 0
while not all instructions scheduled:
ready ← instructions whose predecessors have all COMPLETED by `cycle`
if ready is empty:
cycle ← cycle + 1 // an unavoidable stall
else:
pick p ∈ ready with the greatest critical-path length
issue p at `cycle`; mark its result available at cycle + latency(p)
cycle ← cycle + 1
List scheduling is not guaranteed optimal, but with a good priority — critical path, ties broken by,
say, the number of successors an instruction unblocks — it comes very close and runs in near-linear
time. It is the scheduler in essentially every production compiler.
Scheduling the block, cycle by cycle
The code below builds the dependence DAG for our block, computes each node's critical-path length,
and list-schedules it on a single-issue in-order pipeline. Watch how it fires the three loads early
to cover their three-cycle latency, then stalls exactly where the data genuinely isn't ready yet:
interface Op { id: string; text: string; lat: number; deps: string[]; }
// x = (a+b)*c : loads have latency 3, the multiply latency 2, add/store latency 1.
const block: Op[] = [
{ id: "i1", text: "LD r1, a", lat: 3, deps: [] },
{ id: "i2", text: "LD r2, b", lat: 3, deps: [] },
{ id: "i3", text: "ADD r3, r1, r2", lat: 1, deps: ["i1", "i2"] },
{ id: "i4", text: "LD r4, c", lat: 3, deps: [] },
{ id: "i5", text: "MUL r5, r3, r4", lat: 2, deps: ["i3", "i4"] },
{ id: "i6", text: "ST x, r5", lat: 1, deps: ["i5"] },
];
const byId: Record<string, Op> = Object.fromEntries(block.map((o) => [o.id, o]));
const succ: Record<string, string[]> = {};
block.forEach((o) => (succ[o.id] = []));
block.forEach((o) => o.deps.forEach((d) => succ[d].push(o.id)));
// Latency-weighted critical path from each node to a sink.
const cp: Record<string, number> = {};
function crit(id: string): number {
if (cp[id] !== undefined) return cp[id];
const s = succ[id];
return (cp[id] = byId[id].lat + (s.length ? Math.max(...s.map(crit)) : 0));
}
block.forEach((o) => crit(o.id));
// List scheduling on a single-issue in-order pipeline.
const issuedAt: Record<string, number> = {};
const done = new Set<string>();
let cycle = 0, guard = 0;
while (done.size < block.length && guard++ < 100) {
const ready = block.filter((o) =>
!done.has(o.id) && o.deps.every((d) => done.has(d) && issuedAt[d] + byId[d].lat <= cycle));
if (ready.length === 0) { console.log(`cycle ${cycle}: (stall)`); cycle++; continue; }
ready.sort((a, b) => cp[b.id] - cp[a.id] || a.id.localeCompare(b.id));
const p = ready[0];
issuedAt[p.id] = cycle;
done.add(p.id);
console.log(`cycle ${cycle}: issue ${p.id} ${p.text} (crit=${cp[p.id]})`);
cycle++;
}
console.log(`finishes at cycle ${cycle - 1 + byId["i6"].lat}`);
The loads are hoisted to cycles 0–2, their latencies overlap, and only two genuine stalls remain —
far better than the source order, which would stall after every load. Change a latency or add a
dependence and the schedule reshapes itself around the new critical path.
Because the two goals fight each other — the notorious phase-ordering
problem. A scheduler hides latency by spreading independent computations out and keeping many values
in flight at once; but every value in flight occupies a register, so aggressive scheduling
drives up register pressure and can force
the allocator
to spill — and spills add loads and stores that create new latencies to schedule. Schedule
first and you may spill; allocate first and the allocator's register reuse adds WAR/WAW dependences
that shackle the scheduler. There is no universally right order; real compilers interleave the two,
use pressure-aware scheduling, or schedule–allocate–reschedule. It is one of the most-studied
tensions in back-end design.
It is tempting to think only RAW ("this reads what that wrote") limits reordering.
It does not. If instruction A reads register r5 and a later
B overwrites r5, you cannot hoist
B above A — that is a WAR
anti-dependence, and violating it makes A read the wrong value. Likewise
two writes to the same register carry a WAW output dependence fixing their order.
These false dependences are not about data flow at all — they exist only because a register got
reused — but ignore them and you produce a wrong program. The good news: because they are
false, register renaming can often remove them, which is exactly what
out-of-order hardware and SSA-based compilers do to unlock more scheduling freedom.