Chapter 23 · Instruction Scheduling & Machine-Level Optimization¶

Part 5 · Back End · about 3 weeks · Previous: Ch 22 · Next: Ch 24

The problem¶

After instruction selection (Ch 21) and around register allocation (Ch 22), the back end holds machine instructions in some order, and that order is a performance decision. The input of this chapter is machine code (straight-line blocks, acyclic regions of blocks, innermost loops) together with a machine model: latencies, functional units, issue width, reservation tables. The output is an order and timing of the same operations that respects every dependence and never oversubscribes a resource, and is as short as possible. Scheduling a block is NP-hard (Theorem 23.3.4), so compilers use list scheduling with provable bounds, regions to find more parallelism than a block holds, and modulo scheduling to overlap loop iterations. The chapter then covers the machine-level passes that run around the scheduler: if-conversion, block placement and branch folding, machine peepholes and code motion, and post-link layout with BOLT and Propeller. In LLVM 23 these are MachineScheduler, PostMachineScheduler, MachinePipeliner, EarlyIfConversion, IfConverter, MachineBlockPlacement, BranchFolder, PeepholeOptimizer, MachineCSE, MachineLICM and MachineSink. pebblec uses them as they are, and your lab builds its own list and modulo schedulers for a toy VLIW with a cycle-accurate checker.

What you will be able to do¶

Read a machine model (reservation tables, LLVM's per-operand SchedMachineModel) and predict an llvm-mca throughput bound by hand.
Build a block's dependence DAG with true, anti, output and memory edges and their latencies, and compute heights, the critical path and the resource bound.
Run top-down and bottom-up list scheduling by hand, prove Graham's \(2 - 1/m\) bound, and explain why optimal scheduling is NP-hard.
Form traces, superblocks, treegions and hyperblocks from a profile, and if-convert a region with exact predicates.
Compute ResMII and RecMII, run iterative modulo scheduling, and generate prologue, kernel and epilogue code with rotating registers.
Explain the phase-ordering problem between scheduling and register allocation, and read what GenericScheduler::tryCandidate decides.
Lay out blocks with Pettis–Hansen and ext-TSP, and say what branch folding, MachineCSE/LICM/Sink and BOLT or Propeller change in a binary.
Implement list and modulo schedulers that a cycle-accurate simulator accepts, and measure them against lower bounds.

Prerequisites: Ch 21 (MachineInstrs, SelectionDAG, TableGen), Ch 22 (interference, pressure, spilling), Ch 15 (dominance, post-dominance, control dependence), Ch 18 (dependence distances), Ch 20 (profiles). Ch 19's alias analysis explains the memory edges.

Notation¶

Shared notation follows the house notation: §1 (sets, functions), §3 (graphs and CFGs), §4 (dominance), §8 (complexity). In this chapter:

Symbol	Meaning
\(\mathrm{RT}(o)\), \(\mathrm{cap}(r)\), \(W\)	reservation table of operation \(o\) (pairs (resource, offset)); capacity of resource \(r\); issue width (Definitions 23.1.1–23.1.2)
\(\mathrm{lat}(v)\), \(\ell(u, v)\)	latency of operation \(v\); latency of the DAG edge \(u \to v\) (Definition 23.2.3)
\(t\), \(t(v)\), \(L\)	a schedule: the issue cycle of every operation; its length \(\max_v t(v) + \mathrm{lat}(v)\) (Definition 23.2.4)
\(h(v)\), \(\mathrm{CP}\), \(\mathrm{RB}\)	height (longest latency path to the end); critical path \(\max_v h(v)\); resource bound \(\max_r \lceil \mathrm{uses}(r) / \mathrm{cap}(r) \rceil\) (Definition 23.2.8, Corollary 23.2.13)
\(m\)	number of identical units in Graham's model \(P \mid \mathrm{prec} \mid C_{\max}\) (Theorem 23.3.3)
\(\mathrm{MaxLive}(t)\), \(K\)	largest number of values live in one cycle under \(t\); a register limit (Definition 23.3.9)
\(p(B)\), \(c_X\), \(\mathrm{CD}(B)\)	execution predicate of block \(B\); condition of branch \(X\); control-dependence set (Definitions 23.5.2, 23.5.4)
\(d\), \(\mathit{II}\), \(\sigma(v)\), \(S\)	dependence distance in iterations; initiation interval; modulo schedule time; number of stages \(\lfloor \max \sigma / \mathit{II} \rfloor + 1\) (Definitions 23.6.1–23.6.2)
\(\mathrm{ResMII}\), \(\mathrm{RecMII}\), \(\mathrm{MII}\)	resource, recurrence and overall lower bounds on \(\mathit{II}\) (Definition 23.6.3)
\(\mathrm{HeightR}(v)\)	height with loop-carried edges weighted \(\ell - \mathit{II}\,d\) (Definition 23.6.8)
\(s(b)\), \(a(b)\)	size and address of block \(b\) in a layout (Definition 23.9.5)

Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.

Technique map¶

Family	Techniques (origin)	Lesson
Machine models	reservation tables, collision vectors and pipeline automata (Davidson et al. 1975; Proebsting & Fraser 1994; Bala & Rubin 1995; GCC `genautomata`, Makarov 2003); LLVM's per-operand machine model (`SchedMachineModel`); static throughput analysis with `llvm-mca` (Di Biagio & Davis 2018)	23.1
Dependence DAGs	dependence-DAG construction (Bernstein 1966; Landskov et al. 1980; table-driven: Gibbons & Muchnick 1986); memory and control dependences; critical-path analysis (heights, depths, slack)	23.2
List scheduling	top-down cycle-driven list scheduling (Graham 1966/1969; Gibbons & Muchnick 1986; Warren 1990); bottom-up list scheduling by reversal; register-pressure-aware list scheduling (Goodman & Hsu 1988)	23.3
Region scheduling	trace scheduling with compensation code (Fisher 1981; Ellis 1985; Lowney et al. 1993); superblocks by tail duplication (Hwu et al. 1993); treegions (Havanki, Banerjia & Conte 1998); region scheduling (Bernstein & Rodeh 1991)	23.4
If-conversion	if-conversion and predicate assignment (Allen, Kennedy, Porterfield & Warren 1983; RK algorithm: Park & Schlansker 1991); hyperblocks (Mahlke et al. 1992); LLVM's `EarlyIfConversion` and `IfConverter`	23.5
Software pipelining	ResMII/RecMII and the modulo reservation table (Rau & Glaeser 1981); iterative modulo scheduling (Rau 1994); swing modulo scheduling (Llosa et al. 1996; LLVM `MachinePipeliner`, GCC SMS); modulo variable expansion (Lam 1988) and rotating registers (Dehnert, Hsu & Bratt 1989)	23.6
LLVM's schedulers	SelectionDAG list schedulers (`source`, `list-burr` after Sethi & Ullman 1970, `list-hybrid`, `list-ilp`); MachineScheduler with `GenericScheduler`; post-RA scheduling with anti-dependence breaking	23.7
Scheduling and allocation	prepass vs postpass (Hennessy & Gross 1983); integrated prepass scheduling (Goodman & Hsu 1988; Bradlee, Eggers & Henry 1991); scheduler-sensitive allocation (Pinter 1993; Norris & Pollock 1993) and post-allocation renaming	23.8
Code layout	Pettis–Hansen code positioning (Pettis & Hansen 1990; LLVM `MachineBlockPlacement`); ext-TSP block placement (Newell & Pupyrev 2020); branch folding and tail merging (LLVM `BranchFolder`)	23.9
Machine-level peepholes and post-link	machine peepholes and MachineCSE; MachineLICM and MachineSink; post-link optimization with BOLT (Panchenko et al. 2019) and Propeller (Shen et al. 2023), function ordering (Ottoni & Maher 2017)	23.10

flowchart LR
  RT[Reservation tables<br/>Davidson 1975] -->|compiled to| AUT[Pipeline automata<br/>Proebsting-Fraser 1994]
  RT -->|per-operand latency| SMM[LLVM SchedMachineModel]
  SMM --> MCA[llvm-mca]
  DAG[Dependence DAG<br/>Landskov 1980] --> LS[List scheduling<br/>Graham 1966]
  LS -->|reverse and mirror| BU[Bottom-up]
  LS -->|watch live values| IPS[Pressure-aware / IPS<br/>Goodman-Hsu 1988]
  LS -->|beyond one block| TR[Trace scheduling<br/>Fisher 1981]
  TR -->|single entry by tail duplication| SB[Superblocks<br/>Hwu 1993]
  TR -->|tree-shaped, no joins| TG[Treegions 1998]
  SB -->|predicate the hot region| HB[Hyperblocks<br/>Mahlke 1992]
  IC[If-conversion<br/>Allen et al. 1983] --> HB
  LS -->|overlap iterations| MS[Modulo scheduling<br/>Rau-Glaeser 1981]
  MS --> IMS[IMS<br/>Rau 1994]
  MS --> SMS[SMS<br/>Llosa 1996]
  SMS --> MP[LLVM MachinePipeliner]
  IPS --> GS[LLVM GenericScheduler]
  BU --> GS
  PH[Pettis-Hansen 1990] -->|model distances| EXT[ext-TSP 2020]
  EXT --> BOLT[BOLT / Propeller]

Who uses what¶

System	Technique	Notes
LLVM 23	`MachineScheduler` (`GenericScheduler`, bidirectional, pressure-aware) before allocation; `PostMachineScheduler` or `PostRAScheduler` after it on in-order and VLIW targets; SelectionDAG linearization (`source` by default); `MachinePipeliner` (SMS) on Hexagon, AArch64, PowerPC, ARM, RISC-V; `EarlyIfConversion`, `IfConverter`; `MachineBlockPlacement` with optional ext-TSP; `BranchFolder`; `PeepholeOptimizer`, `MachineCSE`, `MachineLICM`, `MachineSink`; `llvm-mca`	23.7, 23.6, 23.9, 23.10
GCC 14/15	Haifa list scheduler (`-fschedule-insns`, `-fschedule-insns2`, `-fsched-pressure`) with DFA hazard recognizers from `genautomata`; interblock region scheduling (`sched-rgn.cc`); selective scheduling (`-fselective-scheduling`); SMS (`-fmodulo-sched`); `-ftracer`; `ifcvt.cc`; `bb-reorder.cc`; `regrename`	23.1–23.6, 23.8
BOLT (LLVM monorepo)	post-link block reordering with ext-TSP, function splitting, hfsort/C³ function ordering, by binary rewriting	23.10
Propeller (LLVM + lld)	post-link layout by relinking with basic-block sections and cluster directives	23.10
Multiflow TRACE, Bulldog, IMPACT, Trimaran	trace scheduling, superblocks, hyperblocks, IMS (research and historical VLIW compilers)	23.4–23.6
AMDGPU, Hexagon back ends	execution masks for divergent branches; multi-block early if-conversion and DFA packetization	23.5
Pebble	uses LLVM's schedulers; the lab's own td/bu list schedulers, ★ pressure scheduler and IMS with rotating-register code generation, validated by a cycle-accurate simulator	exercises, lab

Comparison¶

The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8. Each lesson repeats its own rows and defines its variables.

Machine models (lesson 23.1)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Reservation tables and hazard recognizers	exact structural-hazard test for any pipeline describable by tables (Lemma 23.1.13, Proposition 23.1.14)	\(O(\rho)\) per query (table), \(O(1)\) (automaton, up to \(2^{D}\) states)	exact yes/no; nothing about latency	table: trivial; automaton: a generator	the lab's scheduler, GCC's DFA scheduler, LLVM's VLIW packetizer and scoreboards
LLVM per-operand machine model	resources with occupancy plus per-operand latency and forwarding (Proposition 23.1.9); approximate for out-of-order cores	lookups are \(O(1)\) per instruction	only as accurate as the TableGen description	large per processor (Skylake model: thousands of lines)	every LLVM scheduler, `llvm-mca`, MachinePipeliner, MachineCombiner
Static throughput analysis (`llvm-mca`)	cycle-level simulation of the model; respects both bounds of Theorem 23.1.12	\(O(N \lvert B \rvert \rho)\) · milliseconds for small loops	timelines, pressure, bottlenecks; blind to caches and branches	none for users (a tool)	debugging models and kernels without hardware; CI performance checks

Dependence DAGs (lesson 23.2)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Dependence-DAG construction	exact for registers; the same schedules either way (Proposition 23.2.10); sound (Theorem 23.2.11)	pairwise \(\Theta(n^2)\) · table-driven \(O(n + e + m^2)\)	a DAG; wrong edges are silent miscompiles or lost ILP	table-driven: moderate (subregisters, physical registers)	every scheduler: LLVM `buildSchedGraph`, GCC `sched-deps.cc`
Memory and control dependences	as precise as the alias oracle; sound if conservative	\(O(m^2)\) pairs, capped in practice	`restrict` / TBAA visibly change the schedule (the §7 box)	low (all-pairs) to high (AA-based, huge-region handling)	every scheduler; AA in MachineScheduler off by default on most targets
Critical-path analysis	exact longest path; lower bound, tight without resources (Theorem 23.2.12)	\(O(n + e)\)	a number per node; the best single priority	trivial	list-scheduling priorities (LLVM, GCC), `-misched-dcpl`, lower bounds in the lab

List scheduling (lesson 23.3)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Top-down list scheduling	any priority is within \(2 - 1/m\) of optimal on identical units (Theorem 23.3.3); `td-cp` 4.2 % above the lower bound on the lab corpus	\(O((n + e)\log n)\) with a heap · lab: tens of µs per block (20–90 µs measured; varies with machine load)	good latency hiding; can raise register pressure	low	GCC `haifa-sched`, post-RA schedulers, VLIW packers
Bottom-up list scheduling	same guarantee by mirroring (Corollary 23.3.8); `bu-cp` 5.3 % above the bound on the corpus	the same plus reversal · lab: tens of µs per block (20–85 µs measured)	shorter live ranges; can stall early loads (the A55 box)	low, once reversal is understood	SelectionDAG (`list-burr`, `list-ilp`), MachineScheduler bottom zone
Register-pressure-aware list scheduling	never exceeds \(K\) registers (Proposition 23.3.12); corpus: MaxLive 1079 vs 1224 for `td-cp`, length +4.6 %	same order · lab: 40–150 µs per block (measured)	fewer spills, sometimes longer schedules	moderate: live-value tracking, kill counts	LLVM GenericScheduler pre-RA, GCC `-fsched-pressure`, SelectionDAG `list-burr`

Region scheduling (lesson 23.4)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Trace scheduling	any motion along the trace, repaired by compensation (Theorem 23.4.10)	list scheduling per trace plus copies	excellent on the hot path; compensation slows cold paths and grows code	very high (bookkeeping rules, liveness, frozen ops)	Multiflow, Bulldog; GCC selective scheduling (IA-64)
Superblock scheduling	motion within a single-entry trace; only exits need care (Theorem 23.4.11)	tail duplication linear in the tail; list scheduling	good on the hot path; code growth from copies (37 % of the loop in the tracer box)	moderate	IMPACT; GCC `-ftracer`, `-fsched2-use-superblocks`; LLVM tail duplication in block placement
Treegion scheduling	motion to ancestors on every path of a tree; no join repair (Proposition 23.4.12)	formation \(O(n + e)\)	helps all paths of a branch, not only the likely one	moderate	research compilers (HBC98); GCC's acyclic region scheduler is the production analog

If-conversion (lesson 23.5)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
If-conversion and predicate assignment	removes all branches of an acyclic region, exactly (Theorem 23.5.9)	\(O(n + e)\)	no mispredictions; issues both arms; guards every side effect	moderate: predicates, control dependence, register pressure on predicates	vectorizers, GPUs (execution masks), IA-64
Hyperblock formation	converts only frequent, safe blocks; single entry by tail duplication	linear plus duplication	keeps the benefit, avoids the rare long arm	high: selection heuristics plus tail duplication plus predication	IMPACT, Itanium compilers; partial forms in Hexagon, GPU structurizers
LLVM's machine if-converters	small diamonds and triangles; selects (Early) or full predication (post-RA)	per-diamond trace metrics	converts only when the critical path grows by less than half the mispredict penalty	moderate; target hooks	AArch64 `csel` (Early, default on), x86 `cmov` (opt-in), ARM/Thumb-2 predication (IfConverter)

Software pipelining (lesson 23.6)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Modulo-schedule bounds (ResMII, RecMII)	exact lower bounds (Theorem 23.6.5); RecMII exactly the dependence-feasible threshold (Theorem 23.6.7)	\(O(n\rho)\) and \(O(n^3 \log)\)	a target and a yardstick; MII is not always achievable	low	every modulo scheduler (LLVM, GCC), the lab's checker
Iterative modulo scheduling	backtracking; reaches MII on 120 of 150 lab loops, and on almost all loops in Rau's study	\(O(\beta n(n + \mathit{II}\rho))\) per \(\mathit{II}\) · lab: 0.1–0.25 ms per loop including code generation (measured)	minimal \(\mathit{II}\), lifetimes not minimized	moderate: MRT, eviction, budget	VLIW/DSP compilers, Trimaran; the lab
Swing modulo scheduling	no backtracking; lifetime-aware ordering (Proposition 23.6.14)	one pass per \(\mathit{II}\)	near-minimal \(\mathit{II}\) and short lifetimes (fewer registers)	moderate: SCC ordering, windows	LLVM MachinePipeliner (Hexagon, AArch64, PPC, RISC-V, ARM), GCC `-fmodulo-sched`
Modulo code generation (MVE, rotating registers)	correct for \(N \ge S\) (Theorem 23.6.15); fallback loop otherwise	linear in \(S \cdot n\)	rotating: no code growth; MVE: \(u\) kernel copies plus remainder	high: renaming, stages, trip-count guards	LLVM `ModuloScheduleExpander(MVE)`, IA-64 rotating registers, the lab's toy machine

LLVM's schedulers (lesson 23.7)

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)

Scheduling and register allocation (lesson 23.8)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Prepass vs postpass scheduling	postpass is limited by false edges (Proposition 23.8.2); prepass may spill	the sum of the phases	incomparable: the A55 box loses 12 cycles postpass; Lesson 23.3's box spills prepass	low (ordering passes)	LLVM and GCC: both, with pressure tracking prepass
Integrated prepass scheduling (IPS)	latency until registers run short, then register reduction	list scheduling	fewer spills at small cost in length (lab: MaxLive −12 %, length +4.6 %)	moderate: live-value accounting	LLVM GenericScheduler, SelectionDAG `list-hybrid`, GCC `-fsched-pressure`
Scheduler-sensitive register allocation	coloring \(I_P\) adds no restricting false dependence (Theorem 23.8.6)	\(\Theta(v^2)\) extra edges	best schedules when registers suffice; degrades to plain coloring otherwise	high: allocator changes	research compilers; renaming passes (GCC `regrename`, LLVM anti-dep breakers) in production

Code layout (lesson 23.9)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Pettis–Hansen code positioning	greedy maximum fall-through; every merge is a fall-through (Proposition 23.9.3); optimum is NP-hard (Theorem 23.9.4)	\(O(e \log e)\)	280/400 fall-through weight on the running region vs 130 in source order	low (LLVM's loop-aware version: high)	LLVM `MachineBlockPlacement`, GCC `bb-reorder`, linkers' function ordering
Ext-TSP block placement	models jump distance too (Definition 23.9.5); NP-hard (Corollary 23.9.7)	greedy with cached gains, near-linear in practice	score 298 vs 158 on the running region; better I-cache use on large binaries [NP20]	moderate (a library)	BOLT's default, LLVM with profiles (`-enable-ext-tsp-block-placement`)
Branch folding and tail merging	removes duplicate tails and jump chains; semantics-preserving (Proposition 23.9.10)	\(O(p^2 k)\) per join worst case, capped	smaller code; one extra jump per merged predecessor	moderate	LLVM `BranchFolder` (twice per pipeline), GCC cross-jumping

Machine-level peepholes, code motion and post-link optimization (lesson 23.10)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Machine peephole optimization and machine CSE	target-specific local rewrites; identical-instruction CSE over dominance (Proposition 23.10.4)	linear	small, reliable wins where selection duplicated work	low per rule; target hooks	every LLVM target, pre-RA; GCC `compare-elim`, RTL CSE
Machine code motion (MachineLICM and MachineSink)	hoist invariant and sink partially dead MachineInstrs (Proposition 23.10.8)	\(O(n\ell)\)	fewer instructions in loops and on cold paths; pressure-limited	moderate	early (SSA) and post-RA instances in LLVM
Post-link optimization (BOLT, Propeller)	whole-binary layout from production profiles (Theorem 23.10.11, Proposition 23.10.13)	reading the binary and the profile; Propeller: a rebuild	several percent on large data-center binaries [PAN+19, SPL+23]	high (BOLT: a binary rewriter); moderate for Propeller users	Meta (BOLT), Google (Propeller), Linux kernel and large services

Comparison-lab results (reproduce with build/<preset>/bin/ch23-compare tests/ch23/Inputs/blocks.txt tests/ch23/Inputs/loops.txt tests/ch23/Inputs/loops-hard.txt on a solution build): on 240 corpus blocks the total lengths are 4110 (td-cp), 4118 (td-succ), 4153 (bu-cp), 4171 (bu-succ) and 4298 (★ pressure) against a lower bound of 3943; total MaxLive is 1224 for td-cp, 1079 for pressure and 1086 for the in-order schedule. Iterative modulo scheduling reaches \(\mathit{II} = \mathrm{MII}\) on 120 of 150 loops (sum of II 985 against sum of MII 944), with 2.22 stages on average.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 23.1	reservation tables, LLVM machine models, `llvm-mca`	quiz; `llvm-mca` boxes
2	Lesson 23.2	dependence DAGs, memory edges, critical path	drill `critical-path`
3	Lesson 23.3	top-down, bottom-up and pressure-aware list scheduling	drill `list-schedule`; lab E1–E3
4	Lesson 23.4	traces, superblocks, treegions	drill `trace-select`
5	Lesson 23.5	if-conversion, hyperblocks, LLVM's if-converters	drill `ifconvert`
6	Lesson 23.6	MII, IMS, SMS, modulo code generation	drills `mii`, `modulo-table`; lab E4–E5
7	Lesson 23.7	SelectionDAG schedulers, MachineScheduler, post-RA	quiz ("find it in LLVM")
8	Lesson 23.8	phase ordering, IPS, scheduler-sensitive allocation	quiz; lab ★ E3
9	Lesson 23.9	Pettis–Hansen, ext-TSP, branch folding	drill `code-layout`
10	Lesson 23.10	machine peepholes, MachineCSE/LICM/Sink, BOLT, Propeller	quiz; MIR boxes
11	Comparison lab `labs/ch23-sched/` (exercises)	list scheduling (td/bu, two priorities, ★ pressure) vs lower bounds; IMS vs MII	`./course test 23`; `ch23-compare`
12	Theory test	all	`./course quiz 23` (≥ 80 % to finish)

Practice and check¶

./course drill critical-path --difficulty easy   # warm up; --solution shows every step
./course drill list-schedule                     # ready lists cycle by cycle; hard: bottom-up
./course drill trace-select                      # traces, tail duplication, treegions
./course drill ifconvert                         # exact predicates; any equivalent formula counts
./course drill mii                               # ResMII per resource, RecMII per recurrence
./course drill modulo-table                      # iterative modulo scheduling by hand
./course drill code-layout                       # Pettis-Hansen, fall-through weight, ext-TSP
./course flash 23                                # daily, a few minutes
./course quiz 23                                 # after the lessons
./course test 23                                 # after the lab
./course status                                  # done = quiz ≥ 80 % and tests pass

References¶

The chapter's annotated bibliography (papers, textbook sections, pinned LLVM and GCC source files and documentation) is in references.md. Start with: [EaC3] (the textbook companion), [GM86] and [LDSM80] (DAGs and list scheduling), [Rau94] and [LGAV96] (the two modulo schedulers), [HMC+93] (superblocks), [PH90] and [NP20] (code layout), and [LLVM-MISched] (LLVM's scheduler). [Dragon2] Ch. 10 is the rigorous treatment of software pipelining.