Instruction Scheduling
Reordering instructions so a pipeline has something to do while a long-latency operation completes — subject to every data dependence. On a big out-of-order core the hardware reorders anyway; static scheduling earns its keep on in-order cores and in what it does to register pressure.
Why would a compiler emit instructions in a different order than the IR, and does it still matter on modern hardware?
A basic block of machine instructions plus its dependence DAG: a node per instruction, an edge from each definition to every use, plus edges for memory ordering and for any shared implicit resource such as the flags register. The DAG exists to answer exactly one question — which reorderings preserve behavior — and every legal schedule is a topological order of it.
Two instructions may be exchanged only if neither writes something the other reads or writes, neither may trap in a way the other would then not observe, and neither has a side effect whose order is observable. That covers true dependences (write then read), anti-dependences (read then write) and output dependences (write then write) — including through implicit operands such as the condition flags. Memory adds a fourth condition: two accesses may be reordered only if [[alias-analysis]] can prove they cannot refer to the same location, and never at all if either is volatile or is an atomic whose ordering the memory model constrains.
Key points
- Every legal schedule is a topological order of the dependence DAG; scheduling is choosing among them under a cost model.
- The win is placing independent work in the shadow of a long-latency instruction so an in-order pipeline does not stall.
- On a big out-of-order core the hardware already does this over a much larger window with better information, so static scheduling for latency buys much less there.
- What static scheduling still decides everywhere is how many values are live at once — and that determines spilling, which no hardware can undo.
- Scheduling and register allocation want contradictory things and run in sequence, so backends run a scheduler on each side of the allocator.
The dependence DAG is the whole constraint
add does not write the condition flags unless you write adds, so the scheduler has strictly more freedom. Latencies also differ per microarchitecture — an integer multiply is roughly three cycles on recent x86 cores and was five on older ones, and the scheduler is tuned per CPU model.Scheduling starts by forgetting the instruction order and remembering only what forced it. Build a node per instruction and an edge whenever one instruction must precede another: %3 = add %1, %2 must precede any use of %3, a store must precede a load that might alias it, and on x86 an instruction that writes the flags must not move between a comparison and its branch.
What remains is a DAG, and every legal instruction order is a topological sort of it — which is [[topological-sort]] from the data-structures course doing real work. The scheduler is choosing among those orders using a cost model, most simply "list scheduling": repeatedly issue whichever ready instruction has the longest remaining dependence chain to the end of the block, because that one is on the critical path.
The reordering that helps is the one that puts independent work between a long-latency instruction and its consumer. A load that misses cache costs hundreds of cycles; a divide costs dozens. If the very next instruction consumes the result, an in-order machine stalls for the whole latency. If three unrelated instructions sit in between, three of those cycles are recovered.
1; unscheduled: the multiply's consumer is immediately behind it2 imul rax, rbx ; latency ~3 cycles3 add rax, rcx ; must wait for rax4 mov rdx, [rsi] ; independent5 add rdx, r8 ; depends on the load6 7; scheduled: independent work moved into the shadow8 imul rax, rbx9 mov rdx, [rsi] ; issued while the multiply is in flight10 add rax, rcx11 add rdx, r8Nothing was added or removed and no dependence was crossed — the second listing is a different topological order of the same DAG. On a strictly in-order core the second form is faster. On a wide out-of-order core the two are usually indistinguishable, because the hardware performs this reordering itself in its scheduling window.
The honest part: the hardware already does this
A modern high-performance core does not execute instructions in the order the compiler emitted them. It decodes them into micro-operations, renames their registers to break false dependences, buffers a few hundred of them in a reorder buffer, and issues each one as soon as its operands are ready and a suitable port is free. It is, in effect, running a list scheduler in hardware over a window far larger than a basic block, with information — actual cache hit or miss — that no compiler has.
So the honest claim is narrow. Static scheduling matters a great deal on in-order cores, which is most embedded processors, many DSPs, some efficiency cores and every VLIW machine. It matters much less for latency hiding on a big out-of-order core, where the hardware will recover most of what a bad schedule cost. What it still matters for even there is *register pressure*: a schedule that hoists many loads early to hide their latency extends all their live ranges simultaneously, and the allocator then spills. The spill is a real memory access that the hardware cannot reorder away.
This is why register-pressure-aware scheduling is a live research and engineering topic, and why LLVM schedules with a pressure tracker rather than purely by latency. The compiler is no longer primarily competing with the hardware at hiding latency; it is deciding how many values will be live at once, which is a decision the hardware cannot make at all — see [[out-of-order-execution]] and [[register-renaming]] for the hardware's half.
| Target | Latency hiding | Why |
|---|---|---|
| In-order core (many embedded, some efficiency cores)target | Large | Nothing else reorders. A stall the schedule did not avoid is a stall that happens. |
| VLIW / DSPtarget | Decisive | The compiler assigns instructions to issue slots explicitly; a bad schedule leaves slots empty and there is no hardware to fill them. |
| Big out-of-order coretarget | Small for latency, real for pressure | The reorder buffer already reorders across hundreds of instructions with knowledge of actual cache behavior. What it cannot do is un-spill. |
| GPUtarget | Large but different | Latency is hidden by switching warps rather than reordering, so the compiler optimises for occupancy, which register usage directly limits. |
Scheduling against allocation
The two phases want opposite things and they run one after the other, which is the clearest example of [[phase-ordering]] in the whole backend. Scheduling before allocation is free to reorder, because virtual registers have no false dependences — but the reordering it chooses determines how many values are live simultaneously, and it may create pressure that forces spills. Scheduling after allocation sees the real registers and the real pressure, but a physical register reused for two unrelated values now carries an anti-dependence the IR never had, and that dependence blocks the very reordering it wanted to do.
Most backends do both: a pre-allocation scheduler that is at least aware of pressure, then allocation, then a post-allocation scheduler that fixes up what the spill code disturbed. Neither pass gets the information it wants, and the two-pass structure is an admission that the problem does not decompose.
mov rax, [rsi] add rax, 1 mov rcx, [rdi] add rcx, 1
mov rax, [rsi] mov rcx, [rdi] add rax, 1 add rcx, 1
Only if the two loads cannot alias each other and neither aliases anything stored between them, and neither may fault on a path where the fault would not otherwise occur. With rsi and rdi proven to point at distinct objects — by type-based rules, by restrict, or by escape analysis — the exchange preserves every observable effect.
If a store to [rdi] sat between the two loads, hoisting the second load above it changes the value read. It is also illegal if either pointer is volatile, since the number and order of accesses is then observable, and if the loads are atomics whose ordering the memory model constrains. And note the cost even when legal: both loaded values are now live simultaneously, so under register pressure this schedule is what causes a spill.
How it works
The steps, in the order the compiler takes them.
- Build the dependence DAG for a basic block: true, anti- and output dependences on registers, plus memory edges wherever aliasing cannot be ruled out, plus edges for implicit operands such as the flags.
- Annotate each node with the target's latency and the execution ports it can issue on, from the scheduling model.
- Compute each node's height — the longest latency-weighted path from it to the end of the block — which identifies the critical path.
- List-schedule: maintain a ready set of instructions whose predecessors have issued, and at each cycle issue the ready instruction with the greatest height, subject to port availability.
- Track register pressure while doing so, and prefer a lower-height instruction when issuing the critical one would push the number of simultaneously live values past the register count.
- For loops, optionally software-pipeline: overlap iteration
i's tail with iterationi+1's head so the loop body has no stall, at the cost of a prologue, an epilogue and more live values.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A memory edge is omitted because alias analysis was too optimistic, a load moves above a store to the same location, and the program reads a stale value — intermittently, and only in optimized builds.
- An instruction that writes the flags is scheduled between a comparison and its branch, and the branch tests the wrong condition. The function takes the wrong path on inputs that exercise that branch.
- The schedule hoists loads to hide latency, register pressure exceeds the register count, and the allocator spills inside the hot loop. The function is measurably slower after "better" scheduling.
- The scheduling model is tuned for one CPU generation and the code ships on another, so the arrangement chosen to avoid a port conflict now creates one. Nothing is wrong; it is simply slower on half the fleet.
- A stepping debugger jumps back and forth between source lines because the instructions for line 12 and line 30 are interleaved, and engineers report the debugger as broken.
When it helps
- In-order targets, VLIW machines and DSPs, where an unfilled slot is lost work with nothing to recover it.
- Loops with long dependence chains where software pipelining can overlap iterations — the classic large win, and the one most dependent on having enough registers.
- Any code with high-latency operations — divides, square roots, likely cache misses — and independent work available to fill the gap.
When it hurts
- When it raises register pressure past the register count. A schedule that hides fifty cycles of latency and causes a spill in a loop executed a million times is a loss.
- Debug builds, where instruction order matching source order is worth more than any speed. This is a large part of what
-O0actually buys — see[[debug-vs-release]]. - When the model is wrong for the deployment CPU, which for portable binaries it usually partly is.
What it costs
Every one of these is paid by something.
- Scheduling for latency buys stall cycles back and costs register pressure, which is paid in spill code by a later phase that cannot refuse it.
- A precise scheduling model buys better arrangements and costs a per-microarchitecture latency and port table that must be maintained for every CPU the compiler targets, and that is wrong for every CPU it does not.
- Software pipelining buys near-full utilisation in a loop and costs code size (prologue and epilogue), many more live values, and debuggability so poor that stepping through the loop is meaningless.
What else you could do
What a different compiler or language does instead, and when that is better.
- Do not schedule at all and rely on the out-of-order engine. This is a defensible choice for a JIT baseline tier targeting big cores, and it is roughly what the Go compiler does — it keeps scheduling minimal on purpose to protect compile speed.
- Push the decision into the ISA: a VLIW machine has the compiler assign issue slots explicitly. Itanium tried this for general-purpose computing and the approach did not survive contact with unpredictable memory latency; it remains standard in DSPs, where latencies are known.
- Schedule after allocation only, which is simpler and sees real pressure but is constrained by the false dependences that allocation introduced.
- Let the hardware do more: register renaming already removes anti- and output dependences at run time, which is why the hardware's window beats the compiler's on any core big enough to afford it — see
[[register-renaming]].
See it for yourself
The flag, dump or tool that shows you this directly.
- LLVM's view of the schedule:
llc -mcpu=skylake -debug-only=machine-scheduler file.llprints the DAG, the pressure tracking and the chosen order (requires a debug build of LLVM). - Model a schedule without running it:
llvm-mca -mcpu=skylake file.ssimulates the pipeline for a block of assembly and reports throughput, port pressure and the critical path. - Compare orders directly: compile the same function with
-O2for an in-order target (-mcpu=cortex-a53) and an out-of-order one (-mcpu=neoverse-n1) and diff the assembly. - Measure rather than infer:
perf stat -e cycles,instructions,stalled-cycles-frontendtells you whether stalls are actually where the time goes before you spend any effort on scheduling.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The compiler reorders my code, so instruction order in the source does not matter." Instruction order in the *source* was already gone by the middle-end. What is being reordered here is machine instructions, subject to every dependence the language semantics imply.
- "Out-of-order execution makes scheduling obsolete." It makes scheduling-for-latency much less valuable on big cores. It does nothing about register pressure, and it does not exist on in-order targets.
- "A shorter critical path means faster code." Only if the critical path is what you were waiting on. A block bound by port throughput or by a cache miss does not care about its dependence height.
- "The scheduler knows the latencies." It knows the latencies in its model for the CPU it was told to target. Cache misses, which dominate real programs, are not in any static model.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Some instructions take a while, and anything waiting on the result has to wait too. Scheduling moves unrelated instructions into that gap so the machine has something to do. It may only move things that do not depend on each other — that constraint is absolute, and the set of legal orders is exactly the set of topological sorts of the dependence graph.
practical
Before assuming a schedule is your problem, measure whether stalls are where the time goes: perf stat will tell you in a minute. On a desktop or server CPU the answer is usually cache misses, not scheduling, and the fix is data layout rather than instruction order. Where scheduling does bite is embedded in-order targets and hot loops that spill — and for the second case the tell is stack traffic inside the loop body, which means the scheduler and allocator lost an argument with each other.
advanced
The interesting modern framing is that the compiler and the hardware are running the same algorithm with different information. The hardware has a window of hundreds of instructions, knows actual cache outcomes, and can rename away false dependences, but it cannot allocate registers or change how many values are live. The compiler has the whole function and the ability to decide liveness, but is guessing at every latency that matters. So the division of labour that has settled out is: the hardware handles dynamic latency, and the compiler handles register pressure and the targets where there is no hardware to help. Software pipelining is the one place the compiler still clearly beats the machine, because overlapping iterations requires renaming across a loop back edge in a way a reorder buffer will not reach.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
-mcpu.sched1 and sched2 passes with similar placement. The Go compiler deliberately keeps scheduling minimal to protect compile time, and baseline JIT tiers usually do none at all.If you were asked this in an interview
- What determines which reorderings of a basic block are legal, and how would you represent that?
- Given out-of-order execution, why do compilers still schedule at all?
- A scheduling change made a hot loop slower. Give the most likely mechanism.