Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 61 ยท Code Generation and Runtimes

Instruction Scheduling and Software Pipelining

See how compilers reorder instructions to hide latency: dependence graphs, pipeline stalls, list scheduling, register pressure and software pipelining of loops, with runnable models.

A processor does not execute one instruction at a time from start to finish. It works like an assembly line: while one instruction is being executed, the next is being decoded and a third is being fetched. This pipeline keeps the machine busy, but only if the instructions do not get in each other's way. A load from memory may take three or more cycles before its value is ready. If the very next instruction needs that value, the pipeline has to stall, wasting cycles doing nothing.

The compiler can help. The order of instructions in a basic block is often only one of many that give the same result. Instruction scheduling chooses an order that avoids stalls, by moving independent instructions into the gaps. This is one of the most valuable back-end optimizations on modern processors, and it complements what register allocation and peephole improvements do. In this lesson you will compute dependences, simulate stalls, build a list scheduler and see how software pipelining overlaps the iterations of a loop.

Latency and stalls

Every instruction has a latency: the number of cycles until its result can be used by a dependent instruction. Typical values on a simple pipelined core are 1 cycle for an add or a subtract, 3 or more for a multiplication, and 3 to 4 for a load that hits the cache (many more for a miss).

On an in-order processor, instructions issue in program order, one after another. If an instruction's operands are not ready, it waits, and everything behind it waits too. For example:

TEXT
r1 = load a        cycle 0
r2 = r1 + 1        cycle 3   (waits for the load: two idle cycles)

The compiler knows the latencies of the target, so it can place independent work between a load and its use. The scheduler must not change the meaning of the program, though. That depends on which instructions are really independent.

Dependences

Two instructions conflict if they touch the same register or memory location and at least one writes it. There are three kinds:

Kind Also called Pattern Why it matters
True dependence Read after write (RAW) r1 = ... then ... = r1 + ... The second instruction needs the first one's result, so it must wait for the full latency
Anti dependence Write after read (WAR) ... = r1 + ... then r1 = ... The write must not overtake the read, or the read sees the wrong value
Output dependence Write after write (WAW) r1 = ... then r1 = ... The writes must finish in order

Only the true dependence is a real flow of data. The anti and output dependences exist because registers are reused. They disappear if the registers are renamed, which is a reason why scheduling and register allocation interact. For memory, the compiler must also assume dependences between loads and stores unless it can prove that the addresses differ.

The scheduler builds a dependence graph for the basic block: a node per instruction and an edge from i to j for each dependence, labelled with the minimum number of cycles that must separate their issue times. Any order that respects all edges (a topological order) preserves the program's meaning.

flowchart LR
    I0["0: r1 = load a"] -- "3" --> I1["1: r2 = r1 + 1"]
    I2["2: r3 = load b"] -- "3" --> I3["3: r4 = r3 * 2"]
    I1 -- "1" --> I4["4: r5 = r2 + r4"]
    I3 -- "3" --> I4
    I4 -- "1" --> I5["5: store c, r5"]

Part of the dependence graph of the program below. Edge labels show latencies. The two loads do not depend on each other and can overlap.

List scheduling

Finding the best order is NP-hard in general, so compilers use a greedy method called list scheduling:

  1. Compute a priority for every instruction. The standard choice is the length of the critical path from the instruction to the end of the block, counting latencies: instructions that start long chains of dependent work should go first.
  2. Keep a ready list of instructions whose predecessors have all been scheduled and whose operands will be available at the current cycle.
  3. At each cycle, issue the ready instruction with the highest priority. If nothing is ready, the cycle is a stall.
  4. Move on to the next cycle until every instruction is scheduled.

The method works from the top of the block downward (forward scheduling). Some compilers schedule backward from the end of the block instead, and many do both and take the better result.

A runnable scheduler

The program below describes a block of nine instructions with latencies (load 3, multiply 3, add and subtract 1). It computes the dependences of all three kinds, runs the block on a simple one-instruction-per-cycle in-order pipeline in its original order, then builds a list schedule and runs that, reporting the cycle count and the number of registers that are live at the same time.

Python List scheduling a basic block

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The original order issues every load and then immediately waits for it: the whole block takes 17 cycles, with long idle gaps. The list scheduler starts the load of b first, because it begins the longest chain (load, multiply, add, store), and then issues the other independent loads while the multiply is still running. The block now takes 9 cycles, almost twice as fast, with the same results.

There is a price, and the last lines of the output show it: the scheduled version has four registers live at once instead of three. Moving loads early lengthens the time in which their results sit in registers waiting to be used. This is the central conflict between scheduling and allocation:

  • Schedule before allocating registers (prepass scheduling): maximum freedom, but the schedule may need more registers than exist, forcing spills (stores and reloads) that eat the gains.
  • Schedule after allocating registers (postpass): the register assignment is fixed, which adds false dependences and limits the schedule, but it never causes spills.
  • Many compilers do both: a prepass scheduler that is aware of register pressure, then a postpass cleanup.

Beyond one instruction per cycle

The scheduler above issues one instruction per cycle. Modern processors do more:

  • Superscalar and out-of-order cores issue several instructions per cycle and reorder them in hardware. They hide a lot of latency without help from the compiler, but a good static schedule still makes their job easier, and cores for phones and embedded systems are often in-order and rely on the compiler.
  • VLIW (very long instruction word) processors, and many DSPs and GPUs, pack several operations into one wide instruction. All the scheduling is done by the compiler, because the hardware does not check dependences at all.
  • Functional units are limited: only so many loads or multiplies can start per cycle. The scheduler keeps a resource table and refuses to issue more than the machine can do.
  • Branch delay slots on some older architectures: the instruction after a branch always executes, so the scheduler tries to fill the slot with useful work.

Because a basic block is short, there is often not enough independent work inside it. Bigger regions help: trace scheduling and superblock scheduling move instructions across branches along the most likely path, adding compensation code on the other paths, and loop optimizations such as unrolling create longer blocks to schedule.

Software pipelining

Loops give the best opportunity. Take a loop whose body takes 9 cycles because of long latency chains. Running the iterations one after another wastes the functional units for most of the time. Software pipelining starts a new iteration before the previous one has finished, as an assembly line does, so that different iterations work in different stages at the same time.

The key number is the initiation interval (II): the number of cycles between the starts of two consecutive iterations. A lower II means a faster loop. Two limits apply:

  • Resource bound. With n operations and u units that can run them, II >= ceil(n / u).
  • Recurrence bound. If a value computed in one iteration is needed d iterations later, and the chain of operations from its start to its use takes c cycles in total, then II >= ceil(c / d). A running sum or a running product carries a value from each iteration to the next (d = 1).

The scheduler finds the smallest II that satisfies both and a schedule for one iteration that works when copies of it overlap every II cycles. The generated code has three parts: a prologue that fills the pipeline, the kernel that is repeated and contains parts of several iterations, and an epilogue that drains it.

Python Initiation interval and the pipeline timeline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three small loops show how the bounds interact. Loop A has plenty of operations but a trivial recurrence, so the resource limit decides (II = 3). Loop B is limited by its 3-cycle multiply that feeds the next iteration (II = 3), even though two units could do more. Loop C is the same code, but the value comes from two iterations back, which halves the recurrence bound, and II drops to 2.

The timeline shows what software pipelining buys: five iterations of a 9-cycle body take 21 cycles instead of 45. During the kernel, three iterations are in flight, each in a different stage. The longer the loop runs, the closer the speed-up gets to LENGTH / II, which is 3 here. Compilers use this technique heavily on VLIW and DSP processors, and in a limited form on others; the register cost is high, since several iterations hold live values at once, which may need rotating registers or unrolling of the kernel.

Where scheduling fits

Technique Scope Purpose
Peephole optimization A few adjacent instructions Remove local waste
List scheduling One basic block Hide latency and use units
Trace and superblock scheduling Several blocks along a hot path More independent work to schedule
Software pipelining A loop body Overlap iterations
Out-of-order hardware Dynamic window Hide latency at run time

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which dependence represents a real flow of data between two instructions?

    A read-after-write dependence means the second instruction consumes the value that the first produced. The other two come from reusing a register and can be removed by renaming.
  2. 2. In list scheduling, what is a typical priority for an instruction?

    Instructions that start long dependent chains are scheduled early so that the chain finishes sooner, a critical-path heuristic.
  3. 3. Why can instruction scheduling increase the number of live registers?

    Overlapping independent work means more values are alive at the same time, which is why scheduling and register allocation must be coordinated.
  4. 4. A loop has 8 operations and 4 functional units, and a recurrence of 3 cycles carried over one iteration. What is the minimum initiation interval?

    The resource bound is ceil(8 / 4) = 2 and the recurrence bound is ceil(3 / 1) = 3. The II must satisfy both, so it is 3.
  5. 5. In software pipelining, what is the kernel?

    The prologue starts the first iterations, the kernel is the steady state with several iterations overlapping, and the epilogue finishes the last ones.

Summary

  • Instructions have latencies, and an in-order pipeline stalls when an instruction needs a result that is not ready. The compiler can fill the gaps with independent instructions.
  • Dependences come in three kinds: true (RAW), anti (WAR) and output (WAW). Only the true dependence carries data. Memory accesses need conservative treatment.
  • List scheduling is a greedy algorithm: prioritize by critical path, issue the best ready instruction each cycle, stall when none is ready.
  • Scheduling and register allocation conflict: overlapping work raises register pressure and may force spills. Compilers schedule before and after allocation.
  • Wider machines (superscalar, VLIW) and bigger scheduling regions (traces, superblocks, unrolled loops) expose more parallelism.
  • Software pipelining starts a new loop iteration every II cycles, bounded by the available resources and by loop-carried recurrences. The code has a prologue, a kernel and an epilogue.

Next, move on to memory management at run time in Garbage Collection.