LIST SCHEDULING reorder instructions to hide latency, respect the DAG
An instruction that starts a multi-cycle operation (a load, a multiply) leaves the result unavailable for several cycles; issue its consumer too soon and the pipeline stalls. List scheduling builds the data-dependency DAG, then greedily issues from a ready list (instructions whose inputs are all available), picking by priority — usually the critical-path distance to the end — so long chains start early and independent work fills the stall slots.
THE TECHNIQUE ready list, priority = critical path
Five instructions with latencies and dependencies: issued in program order they stall; scheduled by critical-path priority the stalls fill. The critical path is the hard lower bound — no schedule beats it. Compute both: live demo
HISTORY & CREDIT Graham 1966; compiler use 1980s
“List scheduling finds the shortest schedule.” — no. Optimal instruction scheduling is NP-hard; list scheduling is a greedy heuristic that is fast and usually near-optimal, and Graham’s 1966 result even bounds how bad it can get (and its anomalies). cited
1966 · Ronald L. Graham — “Bounds for Certain Multiprocessing Anomalies”: list scheduling and its worst-case bound (and the counter-intuitive anomalies where more resources make it slower). 1986 · Gibbons & Muchnick — bring list scheduling to instruction scheduling for pipelined processors. 1991 · Bernstein & Rodeh and others — global / cross-block scheduling.
The critical path (longest latency-weighted chain in the DAG) is the schedule’s hard floor; list scheduling’s whole game is filling every other cycle with independent work so the total approaches that floor. Graham 1966
RECOMMEND FOR I-13 the critical path, computed
The critical-path length — the lower bound every schedule must respect — runs on the canonical compiler:
$ i13 run sched.i13 # longest latency-weighted path through the dependency DAG
critical = 7 -- the hard floor: no schedule is shorter than the critical path
serial = 8 -- issuing in naive program order costs more (a stall)
Recommend: list scheduling is LIT at its core — the canonical compiler computes the critical path = 7 (the schedule’s hard lower bound) against a naive serial cost of 8, by the longest-weighted-path recurrence over an array-encoded DAG (native I-13 recursion). For an I-13 back-end targeting any pipelined VM, this is the pass that decides issue order; the DAG and priorities are plain arrays, and the greedy ready-list loop is bounded. Follows instruction selection (158) and register allocation (161) — scheduling and allocation famously fight (schedule widens live ranges), so order them deliberately.