List Scheduling

List scheduling is the dominant heuristic algorithm for instruction scheduling in production compilers. It operates by maintaining a list of instructions ready to execute (those whose dependencies have been satisfied) and selecting the next instruction to schedule based on a priority function — typically latency to completion, critical path length, or resource pressure. At each step, the scheduler picks the highest-priority ready instruction that does not conflict with already-scheduled instructions for hardware resources, advancing a simulated clock when no ready instruction can issue.

The algorithm is greedy: it makes locally optimal decisions without backtracking. This is why it is fast — typically linear or near-linear in the number of instructions — and why it is suboptimal. The priority function is the compiler writer's best guess at what makes a schedule good, but it cannot anticipate the downstream consequences of each local choice. List scheduling with a critical-path priority function mimics the intuition that delaying instructions on the longest dependency chain hurts completion time most, but this intuition fails when resource conflicts create bottlenecks that the priority function does not see.

Despite its limitations, list scheduling dominates because the NP-completeness of optimal scheduling makes exact algorithms infeasible, and the quality gap between list scheduling and optimal scheduling is small enough for most practical purposes — though it can be arbitrarily large on contrived examples. The algorithm is a compromise between the formal impossibility of perfection and the engineering necessity of finishing compilation in finite time.