Lesson 23.7 — LLVM's schedulers: SelectionDAG, MachineScheduler and post-RA scheduling¶

Techniques: SelectionDAG list schedulers (source, list-burr, list-hybrid, list-ilp); the MachineScheduler with GenericScheduler (bidirectional, pressure- and latency-aware); post-register-allocation scheduling (PostMachineScheduler, the legacy PostRAScheduler with anti-dependence breaking) · Prerequisites: Lessons 23.1–23.3, Ch 21 Lesson 21.5 (SelectionDAG) · Time: 3–4 hours

LLVM schedules the same code up to three times, and it helps to know which of the three is doing the work. The SelectionDAG scheduler turns each block's selected DAG into a list of MachineInstrs, because the DAG has no order of its own. On targets that enable the MachineScheduler (x86, AArch64, RISC-V, most others), it only linearizes, in source order where possible. The MachineScheduler runs on SSA machine code before register allocation. It is the list scheduler of Lesson 23.3, driven by the machine model of Lesson 23.1, with register-pressure tracking and a long chain of tie-breaking heuristics. The post-RA scheduler runs after register allocation, when registers are fixed and only latency and resources can still be improved. This lesson describes each as an instance of the chapter's algorithms, with the exact heuristics and source files.

1. Problem and motivation¶

SelectionDAG schedulers¶

A SelectionDAG is a DAG of nodes per block (Ch 21, Lesson 21.5), and the instruction emitter needs a sequence. The scheduling unit (SUnit) is a group of glued nodes that must stay together. The schedulers are bottom-up list schedulers (ScheduleDAGRRList.cpp) with different priority queues: register reduction (list-burr, Sethi–Ullman numbers [SU70]), source order where legal (source), a hybrid of latency and pressure (list-hybrid), and an ILP-oriented one (list-ilp). Before the MachineScheduler existed (it became the default for most targets during the LLVM 3.x series), these were LLVM's only pre-RA schedulers. Today they matter on targets without a MachineScheduler, at -O0, and when you ask for them.

MachineScheduler (GenericScheduler)¶

Scheduling on MachineInstrs rather than on SelectionDAGs has three advantages. It sees the whole block after selection, including instructions from several DAGs. It uses the per-operand machine model. And it can track register pressure precisely on SSA virtual registers. The MachineScheduler pass builds a DAG per scheduling region (Lesson 23.2), and the MachineSchedStrategy decides the order. GenericScheduler is the default strategy. It schedules from both ends at once, keeps register pressure below each register class's limit, and uses latency and resource heuristics, especially on in-order cores [LLVM-MISched]. Targets plug in their own strategies (GCNSchedStrategy for AMDGPU occupancy, ConvergingVLIWScheduler for Hexagon, PPCPreRASchedStrategy) and DAG mutations (macro-fusion, load/store clustering).

Post-RA scheduling¶

After register allocation, instructions use physical registers, and the allocator's reuse adds anti and output dependences (Lesson 23.8). Spill code has also appeared. A second scheduler can still hide latencies, fill VLIW packets or respect hazards the first scheduler did not see. The legacy PostRAScheduler is a top-down list scheduler with a hazard recognizer. It optionally breaks anti-dependences by renaming registers on the critical path (CriticalAntiDepBreaker, AggressiveAntiDepBreaker). The newer PostMachineScheduler reuses the MachineScheduler framework with PostGenericScheduler. Targets choose one (-misched-postra, enablePostRAScheduler, enablePostRAMachineScheduler).

2. Definitions and algorithms¶

SelectionDAG schedulers¶

Definition 23.7.1 (SUnit graph of a SelectionDAG)

The SUnit graph has one node per maximal set of nodes connected by glue edges, and an edge for every data or chain (ordering) edge between nodes of different SUnits. Chain edges carry memory and side-effect order (Lesson 23.2's memory and control dependences). The latency of a data edge comes from the machine model or from the itinerary.

Algorithm 23.7.2 (Bottom-up register-reduction list scheduling, list-burr)

Input: the SUnit graph of one block.
Output: a sequence of SUnits.
Precondition: acyclic (glue makes cycles impossible by construction).
Postcondition: every SUnit appears after all its predecessors (Proposition 23.7.3).
Invariant: the available queue holds exactly the unscheduled SUnits whose successors are all scheduled.

function BURR(G):
    number every SUnit with its Sethi–Ullman number SU(v):     # registers needed for v's subtree
        SU(v) ← 1 if v has no data predecessors, else
                max over preds p, sorted by SU descending, of SU(p) + (position of p)
    seq ← []; avail ← { v | v has no successors }
    while avail ≠ ∅:
        v ← the element of avail with the smallest SU (ties: fewer live-range extensions,
            then height, then source order)                  # pick to reduce registers
        seq.prepend(v)                                       # bottom-up
        for each pred p of v: if all successors of p are scheduled: avail ← avail ∪ {p}
    return seq

source uses the same queue but prefers source order whenever it is legal; list-hybrid switches to latency when pressure is low; list-ilp prefers ILP when pressure is low (all in ScheduleDAGRRList.cpp).

Proposition 23.7.3 (Bottom-up SUnit scheduling is valid; Sethi–Ullman on trees)

Algorithm 23.7.2 outputs a topological order of the SUnit graph, for any priority. On an expression tree with unit-cost registers, emitting subtrees in decreasing order of Sethi–Ullman number uses the minimum number of registers.

Proof sketch (second part, full proof: [SU70, §3])

Validity: a SUnit becomes available only when all its successors are in seq, and it is then prepended, so it precedes all of them. Every SUnit eventually becomes available because the graph is acyclic (a SUnit whose successors are all scheduled always exists among the unscheduled ones). Optimality on trees: evaluating the child that needs more registers first lets its result occupy one register while the other child uses the rest. The number \(\max(\ell, r)\) if \(\ell \ne r\), else \(\ell + 1\), is a lower bound for any order, by induction on the tree: whichever child is evaluated second needs its full count while the first child's value is held.

MachineScheduler (GenericScheduler)¶

Definition 23.7.4 (Scheduling region, zones)

A scheduling region is a maximal sequence of MachineInstrs inside a block that contains no scheduling boundary (calls, terminators, labels, and whatever TargetInstrInfo::isSchedulingBoundary says). Each region is scheduled independently. GenericScheduler keeps two zones (SchedBoundary), top and bottom. Each zone has a current cycle, an available queue of nodes ready in that cycle, a pending queue of nodes whose latency has not elapsed, and resource counters per ProcResource.

Definition 23.7.5 (GenericScheduler's candidate order)

GenericScheduler::tryCandidate compares a candidate \(T\) with the current best \(C\) in this order, stopping at the first criterion that distinguishes them: (1) physical-register bias (keep copies to or from physical registers near their boundary); (2) register excess (pressure over a class limit); (3) critical-max pressure (pressure in the region's critical sets); (4) latency, if the region is acyclically latency-limited and the zone has not issued yet; (5) fewer stall cycles; (6) memory-operation clustering; (7) fewer weak edges left; (8) current-max pressure; (9) fewer critical resources consumed; (10) more demanded resources; (11) latency, when the zone's policy asks to reduce it; (12) node order (source order in the top zone, reverse in the bottom). Criteria 2, 3 and 8 apply only while tracking pressure (pre-RA).

Algorithm 23.7.6 (Bidirectional scheduling of a region)

Input: a region's DAG (Lesson 23.2) with SUnits, the machine model, pressure trackers.
Output: a new order of the region's instructions.
Precondition: the DAG is acyclic and all edges are within the region.
Postcondition: a topological order (Theorem 23.7.7).
Invariant: the top zone's available nodes have all predecessors scheduled at the top; the bottom zone's have all successors scheduled at the bottom; every node is scheduled at most once.

function ScheduleRegion(DAG):
    Top.init(roots of DAG); Bot.init(leaves of DAG)
    while some node is unscheduled:
        if policy is top-down only: (v, atTop) ← (Top.pick(), true)
        elif bottom-up only:        (v, atTop) ← (Bot.pick(), false)
        else:
            ct ← best of Top.available by tryCandidate; cb ← best of Bot.available
            (v, atTop) ← the better of ct and cb by tryCandidate (no zone-specific criteria)
        if atTop: move v's instruction to the top insertion point; Top.bump(v)   # update cycle,
        else:     move v's instruction to the bottom insertion point; Bot.bump(v) # resources, pressure
        release successors (at top) or predecessors (at bottom) whose other edges are satisfied;
        they enter the pending queue until their latency elapses, then the available queue
    return the region in its new order

Theorem 23.7.7 (Bidirectional scheduling yields a valid order)

For any sequence of top/bottom picks, the final instruction order of Algorithm 23.7.6 is a topological order of the region's DAG.

Proof

The final order is the top list (in pick order) followed by the bottom list (in reverse pick order). Take an edge \(u \to v\). If both are picked at the top, \(v\) was available only after \(u\) was scheduled, so \(u\) precedes \(v\). If both are at the bottom, \(u\) became available only after \(v\) was scheduled at the bottom, so \(u\) was picked later, which puts it earlier in the reversed bottom list. If \(u\) is at the top and \(v\) at the bottom, \(u\) precedes \(v\) because the whole top list precedes the bottom list. The remaining case, \(u\) at the bottom and \(v\) at the top, is impossible: \(v\) could be picked at the top only after all its predecessors, including \(u\), were scheduled at the top. Each node is scheduled once, and the loop ends when all are, so the order is a permutation.

Post-RA scheduling¶

Definition 23.7.8 (Critical anti-dependence, renaming)

After register allocation, an anti edge \(u \to w\) on physical register \(R\) is critical if it lies on a longest path of the region's DAG. Renaming \(w\)'s definition of \(R\) to a register \(R'\) of the same class means rewriting \(w\)'s def and every use it reaches (up to the next definition of \(R\)) to \(R'\).

Algorithm 23.7.9 (Critical anti-dependence breaking)

Input: a scheduling region after register allocation; its DAG; liveness per register.
Output: the region with some registers renamed; the DAG rebuilt without those anti edges.
Precondition: the renamed definition and its uses are all in the region, and none is tied or implicit.
Postcondition: the program computes the same values (Proposition 23.7.10); the critical path does not grow.
Invariant: a register is a candidate \(R'\) only if it is not live, not referenced, and not reserved anywhere in the renamed range.

function BreakCriticalAntiDeps(region):
    walk the critical path bottom-up, maintaining per register its live range in the walk
    for each anti edge u → w on R encountered on the path:
        R' ← a register of R's class, free across [w's def, last use it reaches]
             and not live out of the region
        if R' exists: rename R to R' in w's def and the uses it reaches

AggressiveAntiDepBreaker renames anti edges off the critical path too.

3. Worked examples¶

SelectionDAG schedulers¶

With the MachineScheduler switched off (-enable-misched=false), the SelectionDAG scheduler's order survives to register allocation. On the 24-product function of Lesson 23.3 (48 loads) for the in-order Cortex-A55, the §7 box counts spill and reload instructions: source keeps the IR order (each product right after its loads) and needs 8, the callee-saved registers. list-burr and list-hybrid need none: register reduction interleaves the loads and multiplies so that at most a handful of values are live. list-ilp hoists loads for ILP and needs 12. The Sethi–Ullman number of each product t_i = a[i] * b[i] is 2 (two leaf loads), and of an xor of two products \(\max(2, 2) + 1 = 3\). list-burr therefore finishes one product before starting the next.

MachineScheduler (GenericScheduler)¶

Run Algorithm 23.7.6 on the running block of Lesson 23.2 with GenericScheduler's top-down-only policy, and it reduces to Lesson 23.3's td-cp whenever criteria 1–10 tie. On a real out-of-order target such as Skylake, most regions tie on pressure (plenty of registers) and on stalls (a large window), so the latency and resource criteria and node order decide. The §7 box shows four strategies (-enable-misched=false, default, ilpmax, ilpmin) producing four orders of the same poly function on x86-64. llvm-mca gives all four the same 20 cycles, because the core reorders them anyway.

Post-RA scheduling¶

On the in-order Atom, the legacy post-RA scheduler (forced with -post-RA-scheduler) takes the allocated code of poly, whose register allocator placed the three movq loads into %rcx, %rdx and %rax in source order, and hoists all three loads to the top, then the four multiplies. That is Lesson 23.3's top-down scheduling of the post-RA DAG. There are no anti-dependences to break here, because the allocator happened to use distinct registers for the three chains. When it reuses one register for two chains, the anti edge between them pins their order (Lesson 23.8's box shows exactly that on AArch64).

4. Invariants and correctness¶

SelectionDAG schedulers¶

Validity is Proposition 23.7.3. The heuristics only change quality. The one subtle invariant is glue: glued nodes form one SUnit, so they are emitted contiguously, which is what the targets that need glue (flags, call sequences) rely on.

MachineScheduler (GenericScheduler)¶

Theorem 23.7.7 gives validity for any mix of top and bottom picks. The pressure trackers must stay exact while instructions move: ScheduleDAGMILive updates live intervals (LiveIntervals) as it moves instructions, and -verify-misched checks the machine function before and after.

The MachineScheduler cannot fix what the region boundaries hide

Regions end at calls and at many target-specific boundaries, and memory dependences are conservative unless alias analysis is enabled in the DAG builder (Lesson 23.2). A load cannot be scheduled above a call, even if it is independent of it: the call is a boundary, not just an edge. If a profile shows a stall that crosses a call, the fix is in the IR (hoisting), not in the scheduler.

Post-RA scheduling¶

Proposition 23.7.10 (Renaming for anti-dependence breaking preserves semantics)

If \(R'\) satisfies the invariant of Algorithm 23.7.9, renaming \(w\)'s definition of \(R\) and the uses it reaches to \(R'\) does not change any value computed by the region.

Proof

The renamed uses read, after renaming, the register written by the renamed definition, and nothing writes \(R'\) in between (not referenced in the range), so they read the same value as before. No other instruction reads \(R'\) in the range (not referenced), and \(R'\) is not live after the range (not live out and not live across), so the new write to \(R'\) destroys no value anyone reads. \(R\) is no longer written by \(w\), so readers of \(R\) after the range that relied on \(w\)'s value would be affected, but the range extends to every use \(w\)'s value reaches, by definition, so there are none.

5. Complexity¶

Let \(n\) be the instructions of a region, \(e\) the DAG edges, \(\lvert\mathcal{R}\rvert\) the resources and \(p\) the number of pressure sets.

Technique	Time per region	Notes
SelectionDAG list schedulers	\(O((n + e)\log n)\) (priority queue)	Sethi–Ullman numbering \(O(n + e)\)
MachineScheduler (GenericScheduler)	\(O(n \cdot q \cdot (p + \lvert\mathcal{R}\rvert))\) with \(q \le\) `-misched-limit` (256) the queue size scanned per pick; DAG construction \(O(n + e)\) plus memory pairs	pressure deltas are computed per candidate
Post-RA scheduling	list scheduling \(O((n + e)\log n)\) plus anti-dependence breaking \(O(n \cdot \lvert\text{regs}\rvert)\)	renaming scans register classes

Justification. GenericScheduler::pickNodeFromQueue evaluates tryCandidate on every node of the available queue, and each comparison may compute a pressure delta over the pressure sets and a resource delta over the resources. With the queue capped at -misched-limit, a region of \(n\) instructions costs \(O(n \cdot \min(n, 256) \cdot (p + \lvert\mathcal{R}\rvert))\).

Pathological family. A region of \(n\) independent loads followed by \(n\) uses keeps all \(n\) loads in the available queue from the start: each pick scans \(\min(n, 256)\) candidates, so a 10 000-instruction unrolled region costs about \(2.5 \cdot 10^6\) candidate comparisons, each with pressure deltas. This is why LLVM caps the queue (-misched-limit). Debug builds can also stop scheduling after \(N\) instructions (-misched-cutoff), which is a bisection aid, not a compile-time limit.

SelectionDAG schedulers¶

fast and linearize (ScheduleDAGFast.cpp): no priority, for -O0 speed.
VLIW-oriented vliw-td (ScheduleDAGVLIW.cpp): top-down with a hazard recognizer, for targets without a MachineScheduler.

MachineScheduler (GenericScheduler)¶

Custom strategies: AMDGPU's GCNMaxOccupancySchedStrategy schedules for occupancy (fewer registers means more waves), not latency. Hexagon's converging VLIW scheduler packs packets.
DAG mutations (ScheduleDAGMutation): macro-fusion keeps cmp+jcc adjacent, and load/store clustering (-misched-cluster) groups memory operations so that later passes can pair them (ldp/stp).
Cyclic critical path (-misched-cyclicpath): for single-block loops, use the loop-carried critical path (RecMII of Lesson 23.6) to decide whether the region is latency-limited.

Post-RA scheduling¶

PostMachineScheduler with PostGenericScheduler: the MachineScheduler framework without pressure tracking. It is the modern default where targets enable it (AArch64 substitutes it for the legacy pass).
Aggressive anti-dependence breaking: renames more, at more cost, and can increase register traffic.

7. In real compilers¶

SelectionDAG schedulers¶

createDefaultScheduler in llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp returns the source scheduler whenever the subtarget enables the MachineScheduler (and at -O0), and otherwise follows the target's Sched::Preference (x86-64 sets Sched::ILP, AArch64 Sched::Hybrid). The schedulers are in ScheduleDAGRRList.cpp (createBURRListDAGScheduler, createSourceListDAGScheduler, createHybridListDAGScheduler, createILPListDAGScheduler) [LLVM-RRList].

SelectionDAG schedulers decide the spills when MachineScheduler is off

Reproduce (clang 23.1.2, llc 23.1.2; pres.ll from Lesson 23.3 §7):

for s in source list-burr list-ilp list-hybrid; do
  printf '%-12s spill/reload lines: ' $s
  llc -O2 -mtriple=aarch64-linux-gnu -mcpu=cortex-a55 -pre-RA-sched=$s -enable-misched=false \
    pres.ll -o - | grep -cE 'Spill|Reload'
done

Output (complete):

source       spill/reload lines: 8
list-burr    spill/reload lines: 0
list-ilp     spill/reload lines: 12
list-hybrid  spill/reload lines: 0

What to notice: the four bottom-up list schedulers differ only in the priority queue. Register reduction (list-burr, Proposition 23.7.3) and the hybrid needed no callee-saved registers and no spills. source needed the callee-saved registers, and list-ilp hoisted loads for parallelism and spilled.

MachineScheduler (GenericScheduler)¶

MachineSchedulerImpl and ScheduleDAGMILive::schedule in llvm/lib/CodeGen/MachineScheduler.cpp drive the loop of Algorithm 23.7.6. GenericScheduler::pickNode, pickNodeBidirectional and tryCandidate implement Definition 23.7.5, and SchedBoundary implements the zones [LLVM-MISched, LLVM-MISchedH]. GCC's equivalent is its first scheduling pass (sched1, -fschedule-insns), which is off by default on x86 and on for most RISC targets.

Four MachineScheduler strategies, one out-of-order core

Reproduce (clang 23.1.2, llc 23.1.2, llvm-mca 23.1.2; poly.c from Lesson 23.3 §7):

clang-23 --target=x86_64-linux-gnu -O2 -S -emit-llvm poly.c -o polyx.ll
for f in -enable-misched=false -misched=default -misched=ilpmax -misched=ilpmin; do
  echo "== $f"
  llc -O2 -mtriple=x86_64-linux-gnu -mcpu=skylake $f polyx.ll -o - \
    | grep -P '^\t(mov|imul|add|xor|lea)' | tee x.s | tr '\n' ';' | tr -s '\t ' ' '; echo
  llvm-mca -mtriple=x86_64-linux-gnu -mcpu=skylake -iterations=1 x.s | grep 'Total Cycles'
done

Output (complete):

== -enable-misched=false
 movq (%rdi), %rax; imulq %rsi, %rax; addq 8(%rdi), %rax; movq 16(%rdi), %rcx; imulq %rsi, %rcx; addq 24(%rdi), %rcx; imulq %rax, %rcx; movq 32(%rdi), %rax; imulq %rsi, %rax; addq 40(%rdi), %rax; imulq 48(%rdi), %rsi; addq 56(%rdi), %rsi; imulq %rsi, %rax; xorq %rcx, %rax;
Total Cycles:      20
== -misched=default
 movq (%rdi), %rcx; imulq %rsi, %rcx; addq 8(%rdi), %rcx; movq 16(%rdi), %rdx; imulq %rsi, %rdx; addq 24(%rdi), %rdx; movq 32(%rdi), %rax; imulq %rsi, %rax; addq 40(%rdi), %rax; imulq 48(%rdi), %rsi; addq 56(%rdi), %rsi; imulq %rcx, %rdx; imulq %rsi, %rax; xorq %rdx, %rax;
Total Cycles:      20
== -misched=ilpmax
 movq 16(%rdi), %rcx; imulq %rsi, %rcx; movq (%rdi), %rdx; imulq %rsi, %rdx; movq 32(%rdi), %rax; imulq %rsi, %rax; imulq 48(%rdi), %rsi; addq 56(%rdi), %rsi; addq 40(%rdi), %rax; imulq %rsi, %rax; addq 8(%rdi), %rdx; addq 24(%rdi), %rcx; imulq %rdx, %rcx; xorq %rcx, %rax;
Total Cycles:      20
== -misched=ilpmin
 movq (%rdi), %rax; movq 16(%rdi), %rcx; imulq %rsi, %rax; addq 8(%rdi), %rax; imulq %rsi, %rcx; addq 24(%rdi), %rcx; imulq %rax, %rcx; movq 32(%rdi), %rax; imulq %rsi, %rax; addq 40(%rdi), %rax; imulq 48(%rdi), %rsi; addq 56(%rdi), %rsi; imulq %rsi, %rax; xorq %rcx, %rax;
Total Cycles:      20

What to notice: without the MachineScheduler (the SelectionDAG source order) the first product p0 * p1 is computed as soon as possible, which reuses %rax. default (GenericScheduler) delays both final products to the end, a pressure-neutral order that keeps all four partial results in distinct registers. ilpmax and ilpmin (bottom-up by subtree ILP, ILPScheduler) interleave differently. llvm-mca runs all four in 20 cycles: a 224-entry reorder buffer (Lesson 23.1) finds the parallelism whatever the static order, so on big out-of-order cores the MachineScheduler's value is mainly register pressure and front-end effects.

Post-RA scheduling¶

PostRAScheduler (llvm/lib/CodeGen/PostRASchedulerList.cpp, SchedulePostRATDList) is top-down with a ScheduleHazardRecognizer. -break-anti-dependencies=critical|all selects CriticalAntiDepBreaker or AggressiveAntiDepBreaker (default none, unless the target asks) [LLVM-PostRA]. PostMachineScheduler with PostGenericScheduler is in MachineScheduler.cpp, and TargetPassConfig::addMachinePasses picks one of them (-misched-postra). GCC's sched2 (-fschedule-insns2, on at -O2) is its post-reload scheduler.

The legacy post-RA scheduler on an in-order Atom

Reproduce (llc 23.1.2; polyx.ll from the previous box):

for f in "" "-post-RA-scheduler"; do echo "== atom $f"
  llc -O2 -mtriple=x86_64-linux-gnu -mcpu=atom $f polyx.ll -o - | grep -P '^\t(mov|imul|add|xor)'
done

Output (complete):

== atom 
    movq    (%rdi), %rcx
    imulq   %rsi, %rcx
    addq    8(%rdi), %rcx
    movq    16(%rdi), %rdx
    imulq   %rsi, %rdx
    addq    24(%rdi), %rdx
    movq    32(%rdi), %rax
    imulq   %rsi, %rax
    addq    40(%rdi), %rax
    imulq   48(%rdi), %rsi
    addq    56(%rdi), %rsi
    imulq   %rcx, %rdx
    imulq   %rsi, %rax
    xorq    %rdx, %rax
== atom -post-RA-scheduler
    movq    (%rdi), %rcx
    movq    16(%rdi), %rdx
    movq    32(%rdi), %rax
    imulq   %rsi, %rcx
    imulq   %rsi, %rdx
    imulq   %rsi, %rax
    imulq   48(%rdi), %rsi
    addq    8(%rdi), %rcx
    addq    24(%rdi), %rdx
    addq    40(%rdi), %rax
    addq    56(%rdi), %rsi
    imulq   %rcx, %rdx
    imulq   %rsi, %rax
    xorq    %rdx, %rax

What to notice: after register allocation the three chains use %rcx, %rdx and %rax, so no anti-dependence ties them, and the top-down post-RA list scheduler (Lesson 23.3) starts all three loads, then all four multiplies, before the adds. The only register reused across chains is %rsi (the multiplier x, overwritten by imulq 48(%rdi), %rsi last): the three imulq %rsi must stay above it, an anti edge the schedule respects.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
SelectionDAG schedulers	one block's DAG; bottom-up with pressure/ILP/source priorities (Proposition 23.7.3)	\(O((n+e)\log n)\) per block	pressure-aware on trees; spills vary by priority (the §7 box)	in tree; target picks a preference	linearization before MachineScheduler; the real pre-RA scheduler on targets without one
MachineScheduler (GenericScheduler)	whole regions of MachineInstrs; bidirectional; pressure, latency, resources (Theorem 23.7.7)	\(O(n \min(n, 256)(p + \lvert\mathcal{R}\rvert))\)	good on in-order cores; mostly pressure effects on big OOO cores	high, but targets reuse `GenericScheduler` with mutations	default pre-RA scheduler on x86, AArch64, RISC-V, ARM, PowerPC
Post-RA scheduling	fixed registers; anti edges limit motion unless renamed (Proposition 23.7.10)	list scheduling plus renaming	hides latencies after spills; fills packets	moderate; hazard recognizers per target	in-order and VLIW cores, where it is enabled per subtarget (AArch64 A55, Hexagon packetization)

Choose the SelectionDAG scheduler only as a linearizer, unless the target has no MachineScheduler. Choose GenericScheduler as the base of any new target's pre-RA scheduling and adjust it with mutations or policy, not a new strategy. Choose a post-RA pass for in-order or VLIW cores, where latencies after spills and packet boundaries matter.

9. Assessment¶

Quiz: sdag-default-source (single), burr-su-number (number), bot-available-running (set), bidirectional-valid (single), postra-antidep (single), find-createdefaultscheduler (text), and find-trycandidate (Lesson 23.3). Tags sdag-sched, machine-scheduler, post-ra-sched.
Drills: none of their own. These are LLVM's implementations of the list scheduling practiced in ./course drill list-schedule, and reading the flags and the source is the skill. The quiz's "find it in LLVM" questions and the §7 boxes exercise them.
Flashcards: tags sdag-sched, machine-scheduler, post-ra-sched.

References¶

See the chapter references.

Lesson 23.7 — LLVM's schedulers: SelectionDAG, MachineScheduler and post-RA scheduling¶

1. Problem and motivation¶

SelectionDAG schedulers¶

MachineScheduler (GenericScheduler)¶

Post-RA scheduling¶

2. Definitions and algorithms¶

SelectionDAG schedulers¶

MachineScheduler (GenericScheduler)¶

Post-RA scheduling¶

3. Worked examples¶

SelectionDAG schedulers¶

MachineScheduler (GenericScheduler)¶

Post-RA scheduling¶

4. Invariants and correctness¶

SelectionDAG schedulers¶

MachineScheduler (GenericScheduler)¶

Post-RA scheduling¶

5. Complexity¶

6. Variants and refinements¶

SelectionDAG schedulers¶

MachineScheduler (GenericScheduler)¶

Post-RA scheduling¶

7. In real compilers¶

SelectionDAG schedulers¶

MachineScheduler (GenericScheduler)¶

Post-RA scheduling¶

8. Comparison¶

9. Assessment¶

References¶