List Scheduling and the Critical Path

A basic block is a straight-line sequence with one entry and one exit. Within it, the only ordering constraints that matter are the ones the hardware imposes: an instruction cannot read a value before the instruction that defines it completes, two accesses to the same memory location cannot be reordered if either writes, and a branch cannot move before the computation of its condition. Everything else is free, and a scheduler’s job is to use that freedom to keep the pipeline full.

The measure of success is not the instruction count, which scheduling does not change. It is the number of cycles the block takes, and that number is bounded from below by the longest chain of dependent operations in the block. That chain is the critical path, and understanding why the bound is rarely achieved is most of understanding list scheduling.

Dependence Edges and Latency

The scheduler works on a dependence graph whose nodes are instructions and whose edges are constraints. Three kinds of edge appear.

A true dependence, or read-after-write, connects a definition to a use. Its length is the latency of the defining instruction: the number of cycles before the value is available. On a typical core, an integer add has a latency of one cycle, a load from L1 has several, a load that misses to memory has hundreds, and a multiply or divide has more than an add. These are the numbers the scheduler must know, and they are properties of the target’s pipeline rather than of the program.

An anti-dependence, or write-after-read, connects a use to a later definition of the same register. It exists because the register is being reused, not because the values are related. Renaming removes anti-dependences on a register-renaming core, which is why the scheduler’s model of them is different for out-of-order and in-order targets.

An output dependence, or write-after-write, connects two definitions of the same register. It too is a reuse artifact rather than a value relation, and it too disappears with renaming.

Memory dependences are the fourth kind and the hardest. Two accesses to memory conflict if they may refer to the same location and at least one writes. Proving that they do not conflict requires alias analysis, and in its absence the scheduler must assume conflict, which serializes all memory operations and leaves little to reorder. The quality of a scheduler on memory-heavy code is therefore largely the quality of the alias information it is given.

The Greedy Algorithm

List scheduling is the standard heuristic. It maintains a set of ready instructions — those whose predecessors in the dependence graph have all been scheduled — and at each cycle it chooses one or more of them to issue, subject to resource constraints such as the number of issue slots and the availability of particular functional units.

The choice among ready instructions is made by a priority function. The most common is the longest path to the end of the block, computed once from the dependence graph, sometimes called the critical-path length or the height of the node. Scheduling the highest-priority ready instruction first is a greedy heuristic for minimizing the makespan. It is optimal when the dependence graph is a tree of unit-latency operations and the processors are identical, which is the case the priority rule was first analysed for; with varying latencies, multiple functional units, and general graphs it is a heuristic, and the gap between its result and the optimum can be large on adversarial graphs.

A minimal version, ignoring resources, makes the shape clear:

/* Schedule a block given per-node latency and a successor list. */
int height[MAXN];               /* longest latency-weighted path to a sink */
void compute_height(int n) {
    if (height[n] >= 0) return;
    int h = latency[n];
    for (int s = 0; s < nsucc[n]; s++) {
        int m = succ[n][s];
        compute_height(m);
        int cand = latency[n] + height[m];
        if (cand > h) h = cand;
    }
    height[n] = h;
}
/* At each cycle, issue the ready node with the greatest height. */

The height computation is a post-order traversal with memoization, linear in nodes plus edges. The scheduling loop is quadratic in the worst case because each cycle scans the ready list, which is acceptable for basic blocks of the sizes compilers actually see.

Two refinements matter in practice. The first is that the priority should account for the machine’s issue width: if two instructions can issue per cycle, the scheduler should prefer pairs that use different functional units, and a pure height priority does not know about units. The second is that the height should be recomputed as scheduling proceeds, because the graph that remains after some nodes are placed is not the original graph. Recomputing is expensive, so implementations usually update incrementally or accept the static estimate.

Why the Critical Path Is Not Achieved

The lower bound from the critical path is rarely reached, and the reasons are worth separating.

Resource contention is the first. If a block has ten independent multiplies and the machine has one multiplier with a latency of three, the critical path says three cycles, but the multiplier can only start one per cycle and cannot accept a new operand until the previous one is done, so the block takes thirty. The scheduler cannot fix this; only the instruction selection, by choosing a cheaper operation or a different formulation, can reduce the number of multiplies.

Register pressure is the second and the most consequential, and it is the subject of Scheduling Before Allocation and the Pressure Trade. Reordering to hide latency means starting independent chains early, which means keeping their partial results live, which means occupying registers. A schedule that achieves the critical-path bound may require more live values than the register file holds, and the allocator then spills, and the spill code adds loads and stores that the scheduler did not account for. The result is a schedule that is optimal on paper and worse in practice than a more conservative one.

The interaction is a genuine phase-ordering problem, and it has no clean solution. Scheduling before allocation can produce unallocatable code; allocating before scheduling constrains the scheduler to the point where it cannot hide latency. Compilers handle it by scheduling with a pressure cap — refusing to start a new chain when the number of live values would exceed a threshold — and by iterating: schedule, allocate, and if the spill count is high, reschedule with a tighter cap. The iteration is a heuristic repair, not a guarantee.

Branch behaviour is the third. A block ends with a branch, and the scheduler cannot move instructions across it without knowing which way it goes. Speculating an instruction past a branch requires proving it cannot trap and that executing it early does not change observable behaviour, the condition that If-Conversion, Predication, and the Limits of Speculation exists to establish. Without that proof, the scheduler’s scope is one block, and the latency of the branch itself is exposed at the boundary.

Trace and Superblock Scheduling

The block boundary is the fundamental limit on what a basic-block scheduler can hide. A loop body that is three instructions long has almost nothing to reorder, and its latency is dominated by the loop-carried dependence rather than by within-block parallelism.

Trace scheduling addresses this by scheduling along a path rather than a block. A trace is a sequence of blocks that a profile says is likely to execute together, and the scheduler reorders instructions across the block boundaries within the trace. The cost is that the trace has entry and exit points, and instructions moved across a boundary must be undone or compensated when control leaves the trace by a different edge. The compensation code is the price of the freedom, and it is why trace scheduling produces larger binaries and why it is applied selectively.

Superblock scheduling is a simplification: the trace is chosen so that it has a single entry and multiple exits, and instructions are moved only in ways that do not require compensation at the exits. The restriction makes the transformation cheaper to verify and weaker in what it can hide. Both techniques were developed for VLIW machines, where the compiler must expose parallelism explicitly because the hardware will not, and both were later applied to in-order superscalar targets where the hardware’s window is small.

The common thread is that the scheduler needs a probability model. Reordering across a branch is only worth the compensation code if the branch is predictable, and the profile supplies the probability. Without a profile, static heuristics — loop back edges are taken, forward branches are not — substitute for measurement, and the resulting schedule is optimized for a program the compiler has guessed at rather than one it has seen.

What the Scheduler Cannot Know

The scheduler’s latency table is an approximation of a pipeline it does not control. On an out-of-order core, the hardware reorders at run time within a window of its own, and the compiler’s ordering matters mainly at the boundaries of that window and for the register pressure it creates. On such a core, an aggressive compiler schedule can be worse than no schedule, because it increases pressure without buying anything the hardware would not have done itself.

The second unknown is the memory hierarchy. A load’s latency depends on where its data is, which depends on the access pattern of the whole program, which the scheduler does not see. Treating every load as an L1 hit underestimates the cost of a miss by two orders of magnitude, and treating every load as a miss overestimates the cost of a hit by the same factor. Compilers choose a middle estimate and rely on out-of-order execution or on prefetching to absorb the difference.

The third is the interaction with the branch predictor. A schedule that fills a delay slot with a useful instruction is only useful if the branch is taken; if it is not, the filled slot is on the wrong path and the work is wasted. Some architectures make the delay slot annulled on not-taken branches, and the scheduler must know which, because an instruction with side effects cannot be placed in an annulled slot.