Scheduling Before Allocation and the Pressure Trade

Instruction scheduling and register allocation both want to change the same thing: the order in which values are defined and used. Scheduling wants definitions early and uses late, so that dependent operations overlap. Allocation also prefers uses close to definitions, so that values do not stay live across work that fills the registers; the two goals agree on the second point and conflict on the first, because starting independent chains early is exactly what lengthens the distance between a definition and the work that follows it. Neither pass can be done well without knowing the other’s result, and the pipeline must run one before the other. That is the phase-ordering problem in its sharpest form, and every production compiler makes a different peace with it.

The consequences are not theoretical. A schedule that shortens a basic block by hiding latency can lengthen it by forcing spills, and the spills add memory traffic that the schedule did not model. The reverse also happens: a schedule that is conservative about pressure leaves latency exposed that the machine could have hidden. The compiler has to choose which error to make, and the choice is usually made per function rather than per program.

The Shape of the Conflict

Liveness is the shared quantity. A value is live from its definition to its last use, and the set of values live at any point is what the allocator must fit into registers. Scheduling moves definitions earlier and uses later, which lengthens live ranges and increases the size of the live set at the points in between.

The extreme case makes the mechanism clear. Take a block with ten independent loads and ten independent adds that consume them. The unscheduled order alternates load and add, so at most a couple of loaded values are live at once. A latency-hiding schedule issues all ten loads first, then the adds, so that the load latencies overlap. That schedule is much faster on a machine with a long load latency and enough registers, and much slower on a machine with eight registers, because the ten loaded values do not fit and two of them spill. The spill stores and reloads are themselves memory operations with latency, and they now sit on the critical path.

The scheduler cannot see this because it does not know the register count. Even if it did, the mapping from live values to registers is the allocator’s job, and the allocator may choose an assignment that fits a set of live values that the scheduler thought was too large, or may fail on a set the scheduler thought was small. The two passes are solving a joint problem with a lossy interface between them.

There is a second, less obvious conflict. The allocator inserts spill code, and spill code changes the dependence graph: a reload is a new definition that depends on a store, and both depend on the address computation. The copies that Two-Address Instructions and Destructive Operands forces into the stream arrive by the same route, as instructions the scheduler never priced. The scheduler has already run, so the spill code is scheduled by whatever local order the allocator emitted, which is usually the order that minimizes the spill’s own live range and ignores latency entirely. A function with many spills therefore has a schedule that is good where the allocator did not interfere and arbitrary where it did.

Pressure-Aware Scheduling

The standard mitigation is to give the scheduler a pressure model and a cap. As it builds the schedule, it tracks the number of values that would be live if the current prefix were executed, and it refuses to start a new independent chain when that number would exceed a threshold.

Computing the live count exactly requires knowing all future uses, which the scheduler does know, since it has the whole block. The count at a point in the schedule is the number of values defined before that point and used after it. A scheduler that simulates the block as it builds the schedule can maintain this set incrementally, and the cost is a data structure per instruction rather than per cycle.

The cap is the design decision. Setting it at the number of allocatable registers is too tight, because the allocator needs slack for its own temporaries, for call-clobbered values across a call, and for the copies that coalescing fails to remove. Setting it far below the register count wastes the register file. Compilers use a fraction of the register count, or a count reduced by a reserve for spill temporaries, and the fraction is tuned per target.

A pressure cap alone is not enough, because the scheduler must still choose which chain to delay, and the underlying greedy ordering is the one List Scheduling and the Critical Path sets out. The priority function is extended: among ready instructions, prefer the one on the longest remaining path, but only if issuing it does not push pressure over the cap. If every ready instruction would push pressure over the cap, the scheduler must either accept the excess or issue an instruction that shortens a live range — typically a use of a value that is already live, which reduces the live count. Choosing the use over the definition is the mechanism by which a pressure-aware scheduler trades latency for occupancy.

/* Pressure-limited issue: prefer the critical instruction that does not
   grow the live set; otherwise retire a live value by scheduling its use. */
int choose(int cap, int live) {
    int best = -1, best_h = -1;
    for (int n = 0; n < nready; n++) {
        int op = ready[n];
        int delta = ndefs[op] - nlast[op];   /* growth in live count */
        if (delta > 0 && live + delta > cap) continue;
        if (height[op] > best_h) { best_h = height[op]; best = op; }
    }
    if (best < 0) {                          /* every candidate grows the set */
        for (int n = 0; n < nready; n++) {
            int op = ready[n];
            if (ndefs[op] - nlast[op] < 0) return op;   /* a use frees a register */
        }
        return ready[0];                     /* must issue something: accept the excess */
    }
    return best;
}

The function above is a sketch of the decision, not a complete scheduler: it omits resource checks, and ndefs/nlast are per-instruction counts precomputed from the block. The structural point is that the cap is checked before the priority comparison, so pressure is a constraint and latency is an objective.

The Iterative Repair Loop

Pressure caps reduce the damage but do not eliminate it. The remaining errors are functions of the allocator’s actual behaviour, which the scheduler still cannot predict. Compilers therefore iterate: schedule, allocate, inspect the result, and reschedule with adjusted parameters if the allocation was bad.

The signal that triggers a reschedule is the spill count, or the number of instructions added by the allocator relative to the block’s original size. If the allocator spilled more than a threshold, the scheduler reruns with a tighter cap. If it spilled nothing and the block is latency-bound, the scheduler may rerun with a looser cap. The iteration is bounded to a small number of rounds because each round costs compile time and because the process does not necessarily converge: a tighter cap can produce a schedule that the allocator handles worse for reasons unrelated to the cap, and the loop can oscillate.

The more principled alternative is to integrate the two problems. Integrated allocators and schedulers treat the assignment of registers to values as part of the scheduling decision, so that a value is assigned a register at the moment it is defined and the scheduler can see when the file is full. The formulation is a constraint satisfaction problem over the block, and it is expensive enough that it is used only for the hottest regions or in research compilers. For general code, the iterative repair is the practical compromise.

A middle path is to schedule with the allocator’s structure in mind. If the allocator is graph-colouring based, the scheduler can compute an approximation of the interference graph incrementally as it builds the schedule and stop when the graph’s clique number exceeds the register count. That is closer to the allocator’s actual failure condition than a count of live values, because a graph with many live values but few conflicts still colours easily. The approximation is imperfect — the clique number is expensive to compute exactly — but it is a better predictor than the live count alone.

Live Range Splitting as the Escape Hatch

When the conflict is unavoidable, the allocator has one tool that the scheduler does not: it can split a live range. A value that is live across a long region can be kept in a register for the parts where it is used and spilled for the rest, with the spill and reload placed at the boundaries of the split. Splitting converts one long range into several short ones, and the short ones may fit where the long one did not.

Splitting interacts with scheduling because the split points are chosen to reduce pressure at specific program points, and those points are exactly the ones the scheduler created. An allocator that splits at the point of maximum pressure undoes the schedule’s intent there but preserves it elsewhere. The result is a compromise that neither pass would have chosen alone, and it is often better than either pure strategy.

The cost of splitting is the spill and reload instructions, plus the memory traffic. A split that saves one register at the cost of a store and a load is worthwhile only if the alternative was spilling a value with a longer live range, which is a comparison the allocator can make locally. The classical greedy splitting heuristics make that comparison with a cost estimate per split point, and the estimates are the part of the allocator most sensitive to the target’s memory latency.

What the Interface Loses

The reason the two passes cannot simply be merged is that the information each needs is not available at the other’s granularity. The scheduler needs latencies, which are per-opcode and per-target; the allocator needs the interference structure, which is per-live-range. Both need the loop structure, which is above the block. A single pass that tracked all three would have a state space too large to search, so the pipeline decomposes, and the decomposition is what creates the ordering problem.

Every mitigation described here is a way of passing more information across that interface than the decomposition formally allows: a pressure cap passes the allocator’s constraint to the scheduler, a spill count passes the scheduler’s result back, a clique estimate passes the allocator’s failure condition forward. Each of these is an approximation, and each was chosen because the exact information is either unavailable or too expensive to compute. The engineering question is which approximation is cheapest to maintain, not which is exact.

The visible symptom of a bad interface is a function whose optimized code is slower than its unoptimized code. That outcome is common enough that compilers provide per-function controls to disable scheduling, and the controls exist because no cost model reliably predicts when the interaction will go wrong.