Instruction Scheduling and Its Dependence on the Graph

An optimised IR has more instruction-level parallelism than the source expressed, and the hardware has less than the IR implies. Bridging the gap is scheduling: choosing an order for instructions that respects the true dependences, hides the latency of operations that take several cycles, and does not blow up the number of values that must be kept live at once.

The scheduler is the first pass whose decisions are dominated by machine facts rather than program facts. It needs to know how many cycles a multiply takes, which functional units can issue in the same cycle, how many instructions the front end can decode per cycle, and how many registers exist. Those facts are not in the IR and are not derivable from it. Supplying them is most of the work of writing a scheduler, and getting them wrong produces code that is either slow or incorrect.

Dependence Edges, Not Control Edges

Scheduling operates on a single basic block in the common case. Within a block, control flow is straight-line, so the only constraints are dependences between instructions. The dependence graph has one node per instruction and an edge from a to b whenever b must execute after a.

Three kinds of dependence produce those edges. A true dependence (read-after-write) exists when b reads a value that a defines. An anti-dependence (write-after-read) exists when b writes a location that a reads, and b cannot move before a or a would read the wrong value. An output dependence (write-after-write) exists when both write the same location, and the final value must be the one the program intends.

In SSA form, true dependences are explicit: the def-use edge is the dependence. Anti- and output dependences vanish for register values, because SSA names are never redefined. They reappear the moment registers are assigned, which is why the scheduler must run before allocation, or must be aware of the allocation’s decisions. This is the core phase-ordering problem of the back end, and it has no clean solution: scheduling before allocation has freedom but no knowledge of spills, scheduling after allocation has knowledge but no freedom.

Memory introduces dependences that SSA does not remove. Two stores to locations that may alias are ordered by an output dependence. A load after a store to a may-aliasing location is a true dependence through memory. A store after a load from a may-aliasing location is an anti-dependence. The alias analysis described in Memory SSA and Alias-Partitioned Heaps is what lets the scheduler drop edges between accesses that provably do not overlap; without it, every memory access is ordered against every other, and a block with many loads and stores has almost no freedom.

Calls are barriers in the simple model, because a call may read and write any memory and may have side effects the scheduler cannot see. Modelling a call as a node with edges to every memory operation in the block is sound and pessimistic. Summaries that say which memory a call touches reduce the edge count, and inlining removes the barrier entirely.

List Scheduling and the Priority Function

The classic algorithm is greedy. Compute, for each instruction, the earliest cycle at which it could issue given its predecessors’ completion times and their latencies. Maintain a ready set of instructions whose predecessors have all completed. At each cycle, pick the highest-priority ready instruction whose functional unit is free, issue it, update the times, and add newly ready instructions.

The priority function determines the quality. The most common is the critical path length: the longest latency-weighted path from the instruction to any sink in the dependence graph. Issuing the instruction on the longest remaining path first is a heuristic for minimising total schedule length, and it is optimal for a single-issue machine with unit latencies and no resource conflicts, where any topological order achieves the critical path length and no order can beat it. With multiple issue and resource conflicts it is a heuristic with no guarantee, and the gap from optimal can be large on adversarial graphs.

A second priority is the number of successors, which favours instructions that unlock more of the graph. A third is source order, which preserves the front end’s arrangement and keeps the emitted block close to the address order the source implied, which helps instruction fetch on machines that prefetch sequentially. Production schedulers combine these into a weighted sum whose weights are tuned per target, which is a way of saying that no single priority is right for every machine.

def list_schedule(insns, lat, units, issue_width):
    # insns: nodes with .preds/.succs/.unit/.remaining (initially len(.preds))
    ready = [i for i in insns if not i.preds]
    finish = {}                 # node -> cycle at which it completes
    sched = []
    cycle = 0
    while ready or len(sched) < len(insns):
        ready.sort(key=lambda i: -critical_path(i, lat))
        issued = 0
        for ins in list(ready):
            if issued == issue_width:
                break
            if units[ins.unit] <= 0:
                continue
            if any(finish[p] > cycle for p in ins.preds):
                continue        # a predecessor has not completed yet
            units[ins.unit] -= 1
            ready.remove(ins)
            sched.append((cycle, ins))
            finish[ins] = cycle + lat[ins.op]
            issued += 1
            for s in ins.succs:
                s.remaining -= 1
                if s.remaining == 0:
                    ready.append(s)
        cycle += 1
        replenish(units)        # give each functional unit its issue slots back
    return sched

The latency check is the part that is easy to leave out and produces a schedule that issues an instruction before its operand exists. The real algorithm is more careful than this: it recomputes priorities after an issue invalidates them, treats superscalar ports as sets rather than as counters, and wraps the whole loop in the pressure check described below.

The sketch omits the part that matters most in practice: the check that issuing an instruction does not extend a live range past the register budget. A scheduler that only minimises length will happily interleave several independent chains, keeping many values live at once, and the allocator will then spill. Since the spill code has a store and a reload of its own, and the reload sits on the critical path between the definition and its first use after the spill, the schedule that looked shortest becomes slower after allocation.

Register Pressure as a Scheduling Constraint

The standard remedy is to make pressure an explicit part of the decision. Before issuing an instruction, compute the number of live values if it were issued, and refuse to issue it when that number would exceed a threshold below the register count. The threshold is not the register count itself, because the allocator needs slack to colour the interference graph without spilling; a common choice leaves a margin for values that live across the block boundary.

The check requires liveness at each point, which the scheduler can compute incrementally as it builds the schedule: issuing a definition adds one live value, issuing the last use of a value removes one, and issuing an instruction that both defines and uses keeps the count constant. Tracking the count is cheap; deciding what to do when the preferred instruction would exceed it is not. The threshold itself comes from the allocator: the interference graph built in Building the Interference Graph from SSA Live Ranges determines how much slack exists, and a schedule that ignores it will hand the allocator a graph it cannot colour.

The alternative is to schedule for latency and let the allocator spill, then reschedule the spill code. That loop can be run to convergence and is what some compilers do, but it can oscillate: a schedule that minimises pressure may have a long critical path, and rescheduling after spilling may reintroduce pressure. Bounding the number of iterations is necessary, and the bound is a compile-time knob rather than a correctness requirement.

Latency Tables and Their Lies

A latency table maps an opcode and a set of operand kinds to a cycle count. The table is a simplification of the pipeline: a load’s latency depends on whether it hits in L1, which the compiler cannot know, so the table holds a single number that is right for some accesses and wrong for others. A multiply’s latency may depend on the operand values on some architectures, and an instruction’s throughput may depend on which other instructions are in flight.

The simplification is unavoidable and its consequences are predictable. Scheduling for a cache-miss latency produces code that is good when the miss happens and wastes issue slots when it does not. Scheduling for a cache-hit latency produces code that stalls on misses. Since the compiler cannot distinguish the two, most targets schedule for a value between them, or rely on out-of-order hardware to absorb the difference and schedule mainly to reduce the dynamic instruction count.

The resource table has a similar character. It records how many instructions of each class can issue per cycle, and the scheduler treats that as a hard constraint. Real machines have bypass networks, port conflicts, and writeback limits that the table does not model, so a schedule that satisfies the table can still stall. The table is a conservative approximation, and being conservative costs issue slots; being optimistic produces code that the hardware serialises anyway.

Beyond a Single Block

Trace scheduling and superblock scheduling extend the graph across branches by predicting the likely path and scheduling the merged region, with compensation code inserted on the unlikely paths to preserve correctness. The compensation is the hard part: moving an instruction above a branch requires either duplicating it on the other path or proving it is safe to execute speculatively, and the latter requires knowing that it cannot trap.

Software pipelining goes further and overlaps iterations of a loop, so that the steady state issues work from several iterations per cycle. The dependence graph must be analysed for recurrence: a loop-carried dependence with latency L and distance d bounds the initiation interval at L/d, and no schedule can beat that bound. The modulo scheduling algorithm searches for an initiation interval at or above the bound and then assigns each instruction a cycle modulo that interval, which is why the resulting code has a prologue, a kernel, and an epilogue.

Both techniques change the relationship between the IR and the machine. The IR’s block structure is no longer the scheduling unit, and the scheduler’s output no longer corresponds to a contiguous region of the source. That is why schedulers are usually the last pass before emission and why they consume a machine-level IR rather than the optimiser’s IR: by that point the transformations that need block structure have already run, and the transformations that remain are about resources and timing.

The scheduler also has to respect the constraints the register allocator imposed. After allocation, values live in fixed registers, and an instruction that writes a register the next instruction reads must be ordered accordingly. Pre-allocation scheduling has none of those constraints but must not create them gratuitously; post-allocation scheduling has all of them and almost no freedom. The intermediate position, scheduling with an allocation-aware pressure model, is where most production compilers sit, and the quality of the pressure model is the main determinant of whether the result is better than source order.