Flashcards — Chapter 23¶
118 cards. Review them with spaced repetition in the terminal (./course flash 23) or export them to Anki (./course flash export 23). Here, click a card to reveal its back.
reservation-tables¶
What is a reservation table?
For one operation class: which resources (issue slot, units) it uses in which cycles after issue. Placement is feasible when no resource exceeds its capacity in any cycle (Definition 23.1.2).
What are the forbidden latencies F(x, y)?
The distances d ≥ 0 such that issuing y d cycles after x makes their reservation tables collide on some resource (Lemma 23.1.6).
Occupancy vs latency of a non-pipelined divider (toy machine: div latency 6, occupancy 4)
Latency 6: the result is visible 6 cycles after issue. Occupancy 4: the mul unit is busy for 4 cycles, so no mul or div can start there in that window.
Why compile reservation tables into an automaton?
Each state is the set of future reservations; issuing or advancing a cycle is one transition, so a fit query is O(1) instead of a scan (Proebsting–Fraser, Bala–Rubin; GCC genautomata).
machine-model¶
What does LLVM's SchedMachineModel describe per processor?
Global parameters (IssueWidth, MicroOpBufferSize, LoadLatency, MispredictPenalty) plus, per scheduling class, the resources consumed (ReleaseAtCycles) and the latency of each written operand.
What is ReadAdvance?
A per-operand reduction of the edge latency: the consumer reads that operand late, so the effective latency is max(0, write latency − advance) (Proposition 23.1.9).
Where do per-processor models live in LLVM?
In TableGen files next to each target, e.g. llvm/lib/Target/X86/X86SchedSkylakeClient.td and llvm/lib/Target/AArch64/AArch64SchedNeoverseV2.td.
Which function computes a dependence edge's latency from the model?
TargetSchedModel::computeOperandLatency (llvm/lib/CodeGen/TargetSchedule.cpp).
llvm-mca¶
What does llvm-mca do?
Simulates a sequence of machine instructions through LLVM's scheduling model (dispatch, scheduler, retire) and reports cycles, IPC, resource pressure and a timeline. It sees no caches or branch predictor.
What is llvm-mca's Block RThroughput?
max(micro-ops / dispatch width, max over resources of busy cycles / units): a resource lower bound on cycles per iteration (Definition 23.1.10, computeBlockRThroughput).
Two lower bounds on cycles per loop iteration (Theorem 23.1.12)
The resource bound (RThroughput) and the recurrence bound (latency of a loop-carried dependence cycle / its distance). The larger one wins.
Why does a dot-product loop with vfmadd run at 4 cycles/iteration on Skylake despite RThroughput 1?
The accumulator feeds itself: latency 4, distance 1, so the recurrence bound 4/1 = 4 dominates.
dag-construction¶
The three register dependences
True (read after write), anti (write after read), output (write after write). Only true dependences carry values; anti and output come from register reuse.
Latency of true, anti and output edges on the lab machine
True: lat(i). Anti: 0 (reads happen at issue). Output: max(1, lat(i) − lat(j) + 1), so the later write lands last.
Pairwise vs table-driven DAG construction
Pairwise compares every pair of instructions: Θ(n²). Table-driven (Gibbons–Muchnick) keeps the last definition and the uses of each register and adds only the necessary edges.
Why may transitive edges be omitted from a dependence DAG?
If u→w is implied by a path u→…→w with at least its latency, every schedule valid for the rest also satisfies it (Proposition 23.2.10).
What does ScheduleDAGInstrs::buildSchedGraph do?
Builds LLVM's MachineInstr scheduling DAG bottom-up with def/use maps and memory chains (SDep kinds Data, Anti, Output, Order).
memory-dependences¶
When do two memory operations get an edge?
When at least one is a store and they may alias. Load–load pairs never need an edge.
Lab rule: when may A[k] and A[k'] alias?
When the constant indices are equal, or when either index is a register. Different arrays never alias.
Why does restrict / TBAA visibly change a schedule?
It removes memory edges between loads and stores, so loads can move above stores and overlap their latency.
How do LLVM and GCC bound the cost of memory edges in huge regions?
LLVM: when the maps exceed -dag-maps-huge-region (default 500), it inserts a barrier chain and clears them. GCC: --param max-pending-list-length (default 32) flushes the pending lists.
critical-path¶
Height of a node
h(v) = max(lat(v), max over edges v→w of ℓ(v,w) + h(w)): the latency-weighted longest path from v to the end.
Critical path and the combined lower bound
CP = max height. Every schedule has length ≥ max(CP, RB), where RB is the resource bound (Corollary 23.2.13).
Slack of an operation
The difference between its latest and earliest start in an unconstrained schedule: zero on a critical path.
Why is height the classic list-scheduling priority?
It schedules first the operation that is furthest from being done, so critical chains start early (Landskov et al., Hu's levels).
list-top-down¶
When is an operation ready in cycle c (top-down)?
When all its predecessors are scheduled and t(p) + ℓ(p, v) ≤ c for each of them.
Cycle-driven top-down list scheduling in one sentence
Each cycle, repeatedly place the highest-priority ready operation whose reservation table fits, then advance the cycle (Algorithm 23.3.2).
Graham's bound
Any list schedule on m identical units is at most (2 − 1/m) times optimal: it never idles a unit while an operation is ready (Theorem 23.3.3).
Is optimal block scheduling hard?
Yes: NP-hard with precedence constraints (Ullman 1975). Polynomial cases: Hu's trees of unit tasks, Coffman–Graham for two units with unit latencies.
Lab priorities cp and succ
cp: largest height first, then block order. succ: most DAG successors first, then height, then order. On the running block td-cp gives 10 cycles, td-succ 11.
list-bottom-up¶
How is bottom-up list scheduling defined via reversal?
Reverse every edge with latency lat(j) − lat(i) + ℓ(i,j), mirror reservation tables inside [0, lat), schedule top-down, and map back with t_i = L' − s_i − lat_i (Definition 23.3.5, Theorem 23.3.6).
Why not reverse the instruction order and use the same latencies?
Latencies measure from issue to issue; in mirrored time they measure end to end, so the reversed edge needs lat(j) − lat(i) + ℓ(i,j).
Typical effect of bottom-up scheduling
Operations go as late as possible, close to their uses, which shortens live ranges; loads may start late, which can stall in-order cores.
Which LLVM schedulers work bottom-up?
All SelectionDAG list schedulers (ScheduleDAGRRList) and MachineScheduler's bottom zone.
pressure-aware¶
MaxLive of a schedule
The largest number of values live in one cycle: a value lives from its definition's issue to its last use's issue (to the end if live out) (Definition 23.3.9).
Why can latency-first scheduling cause spills?
It hoists independent loads early, so many values are live at once; beyond the register count the allocator must spill.
Algorithm 23.3.10 in one sentence
Top-down list scheduling that never starts a new value when K are live, prefers value-killing ops when pressure is high, and falls back to in-order when stuck.
Is minimizing registers for a DAG easy?
No: NP-complete (Sethi 1975). Sethi–Ullman numbering is optimal only on trees.
trace-scheduling¶
What is a trace?
A path of blocks through an acyclic region chosen from a profile, scheduled as if it were one block (Fisher 1981).
Mutual-most-likely trace growth
Extend from b to s only if b→s is b's most frequent out-edge and b is s's most frequent predecessor (Algorithm 23.4.3).
Compensation for moving an op upward across a join
Copy it onto the side entrance: the entering path no longer executes it (rule R3).
Compensation for moving an op downward across a split
Copy it onto the side exit, if its result is live there (rule R2).
Moving an op upward across a split
Speculation: no copy, but only if the op cannot trap, has no side effect and does not clobber a value live on the exit (rule R1).
superblock¶
What is a superblock?
A trace with a single entry and possibly several exits (Hwu et al. 1993).
How is a superblock formed?
Tail duplication: copy the trace from its first side entrance to the end and redirect side entrances to the copies (Algorithm 23.4.6).
Why are superblocks easier than traces?
No side entrances means no join compensation; only exits need care (Theorem 23.4.11).
Cost of superblocks
Code growth from the duplicated tails (in the lesson, 3 of 8 blocks).
treegion¶
What is a treegion?
A tree of blocks in which every block except the root has exactly one predecessor (Havanki, Banerjia, Conte 1998).
How are treegions formed?
Roots are the entry and every merge block; every other block joins its unique predecessor's treegion (Definition 23.4.8).
Why do treegions need no join compensation?
They contain no joins, so moving an op up to an ancestor is speculation on the other paths, never loss on an entering path (Proposition 23.4.12).
Treegions vs traces
Treegions help every path through the tree and need no profile; traces focus on the likely path.
if-conversion¶
What does if-conversion do?
Turns an acyclic region into straight-line predicated code: every operation is guarded by its block's predicate, so the branches disappear (Allen et al. 1983).
Exact predicate of a block
A formula over the branch conditions that holds exactly for the assignments whose path executes the block (Definition 23.5.2).
Predicate classes (RK assignment)
Blocks with the same control-dependence set execute together and share one predicate; blocks with an empty CD set need none (Park–Schlansker, Definition 23.5.4).
Control dependence
B is control dependent on (X, o) if B post-dominates X's o-successor but not X (Ferrante–Ottenstein–Warren).
hyperblock¶
What is a hyperblock?
A single-entry set of blocks containing the entry, chosen by frequency, size and hazards, if-converted into one predicated block (Mahlke et al. 1992).
Which blocks does hyperblock formation exclude?
Infrequent, large or hazardous blocks (calls, unsafe memory operations); they stay as ordinary blocks reached by exit branches.
How does a hyperblock stay single-entry?
By tail-duplicating the blocks reached from an excluded block (the lesson's E→G becomes E→G′).
Full vs partial predication
Full: every instruction takes a predicate (IA-64, ARM, GPUs). Partial: only conditional moves/selects, so the arms must be speculated (Mahlke et al. 1995).
llvm-ifcvt¶
EarlyIfConversion
LLVM pass on SSA MachineInstrs turning small diamonds/triangles into selects (cmov, csel) when MachineTraceMetrics says the critical path grows by less than half the mispredict penalty.
IfConverter
LLVM post-RA pass that predicates whole blocks on targets with predication (ARM/Thumb-2, Hexagon, some PowerPC patterns).
What can a select-based if-conversion not convert?
Stores, calls and trapping instructions: both arms execute unconditionally.
GCC's RTL if-converter
gcc/ifcvt.cc: noce_* for select/cmov forms, cond_exec_* for predicated execution.
mii¶
ResMII
max over resources of ⌈uses per iteration / capacity⌉ (counting occupancy and issue slots); a lower bound on II (Theorem 23.6.5).
RecMII
max over dependence cycles C of ⌈latency(C) / distance(C)⌉: the smallest II with no cycle of positive weight ℓ − II·d (Theorem 23.6.7).
How is RecMII computed without enumerating cycles?
Increase II from 1 until the graph with edge weights ℓ − II·d has no positive cycle (Floyd–Warshall or Bellman–Ford).
Is MII always achievable?
No: it is a lower bound. With tight resources and recurrences the smallest feasible II can be larger (the lab's loops-hard corpus).
ims¶
Modulo schedule
Times σ(v) with iteration k of v at k·II + σ(v); valid if σ(w) ≥ σ(v) + ℓ − II·d for every edge and the modulo reservation table fits (Definition 23.6.2).
HeightR
Height with loop-carried edges weighted ℓ − II·d: IMS's priority (Definition 23.6.8).
What makes IMS iterative?
An op that finds no free slot is placed anyway; conflicting ops are evicted and rescheduled, within a budget (Rau 1994). If the budget runs out, II grows by one.
Stages of a modulo schedule
S = ⌊max σ / II⌋ + 1; op v is in stage ⌊σ(v)/II⌋.
sms¶
Swing modulo scheduling in one sentence
Order nodes so each has only predecessors or only successors already placed (recurrences first), then place each as close as possible to them: short lifetimes, no backtracking (Llosa et al. 1996).
Who uses SMS?
LLVM's MachinePipeliner (Hexagon, AArch64, PowerPC, ARM, RISC-V) and GCC's -fmodulo-sched (modulo-sched.cc).
IMS vs SMS
IMS: minimal II with backtracking, lifetimes not minimized. SMS: one pass per II, near-minimal II with fewer registers.
How does MachinePipeliner compute RecMII?
SwingSchedulerDAG::calculateRecMII walks the circuits from findCircuits and assumes distance 1 for each.
modulo-codegen¶
Prologue, kernel, epilogue
S−1 prologue groups (ops with stage ≤ g), the kernel (all ops) run N−S+1 times, and S−1 epilogue groups (ops with stage > e) (Definition 23.6.11).
Why does a kernel need register renaming?
A value whose lifetime exceeds II has several instances live at once; one register would be overwritten by the next iteration before its last use.
Modulo variable expansion
Unroll the kernel u = max ⌈lifetime/II⌉ times and give each copy its own register (Lam 1988). Costs code size and a remainder loop.
Rotating registers
Register names shift by one each kernel iteration (logical q_x in group g is physical (x − g) mod R), so each iteration's value gets a fresh register without unrolling (Cydra 5, IA-64).
sdag-sched¶
SelectionDAG schedulers in LLVM
Bottom-up list schedulers in ScheduleDAGRRList.cpp: source, list-burr (register reduction), list-hybrid, list-ilp.
Default SelectionDAG scheduler when MachineScheduler is enabled
source: keep the IR order and let MachineScheduler do the real scheduling (createDefaultScheduler).
What priority does list-burr use?
Sethi–Ullman numbers: schedule to minimize the registers needed, which is exact on expression trees.
machine-scheduler¶
MachineScheduler with GenericScheduler
LLVM's default pre-RA scheduler: bidirectional list scheduling of MachineInstr regions, balancing register pressure, latency and resources.
Top and bottom zones
GenericScheduler grows a prefix top-down and a suffix bottom-up and picks from whichever zone its heuristics favor; both follow the DAG order, so the result is valid (Theorem 23.7.7).
GenericScheduler::tryCandidate
Compares two candidates by an ordered list of criteria (physical-register bias, excess and critical pressure, stalls, latency, clustering, node order); the first difference decides.
How do targets customize MachineScheduler?
Through DAG mutations (macro fusion, load/store clustering), a custom MachineSchedStrategy, and the scheduling model.
post-ra-sched¶
Why schedule again after register allocation?
Spill code and allocation change the code; a post-RA scheduler hides the new latencies, respects hazards and fills VLIW packets.
Anti-dependence breaking
The legacy post-RA scheduler can rename a register on the critical path to a free one so that an anti edge disappears (CriticalAntiDepBreaker, AggressiveAntiDepBreaker).
PostMachineScheduler vs PostRAScheduler
PostMachineScheduler reuses the MachineScheduler framework after allocation; PostRAScheduler is the legacy top-down list scheduler with hazard recognizers. Subtargets choose which one runs.
phase-ordering¶
The scheduling / allocation phase-ordering problem
Scheduling first can raise pressure and cause spills; allocating first adds false (anti/output) dependences that limit scheduling.
What does register reuse cost the running block?
Reusing r1 for g adds d→g (anti) and a→g (output): td-cp gets 10 cycles instead of 9.
Prepass vs postpass scheduling in LLVM and GCC
Both run a pressure-aware scheduler before allocation and optionally another after it.
integrated-prepass¶
Goodman–Hsu IPS
Schedule for latency (CSP) while registers are free, switch to register reduction (CSR) near the limit (1988).
What did Bradlee, Eggers and Henry find?
A loosely coupled prepass scheduler with pressure feedback gets most of the benefit of fully integrated approaches (1991).
Lab measurement of pressure-aware scheduling
MaxLive −12 % against td-cp for +4.6 % length on the corpus.
sched-sensitive-ra¶
Parallelizable interference graph
The interference graph plus an edge between any two values whose definitions could execute in parallel; coloring it adds no restricting false dependence (Pinter 1993).
Norris–Pollock scheduler-sensitive allocation
Add scheduling edges optimistically to a Chaitin-style allocator and remove them first when coloring would otherwise spill.
Post-allocation renaming
Rename a def–use chain to a free register after allocation to remove false dependences (GCC regrename, LLVM anti-dependence breakers).
pettis-hansen¶
Pettis–Hansen basic-block chaining
Visit edges by decreasing count; merge chain(u)+chain(v) when u ends its chain and v starts another (Algorithm 23.9.2).
Fall-through weight of a layout
The total count of edges u→v with v placed right after u (Definition 23.9.1).
LLVM's descendant of Pettis–Hansen
MachineBlockPlacement: greedy chains by edge probability with loop-aware rules and tail duplication.
ext-tsp¶
Ext-TSP score
Fall-throughs count 1.0 (conditional) or 1.05 (unconditional); forward jumps 0.1·(1 − d/1024), backward 0.1·(1 − d/640); each times the edge count (Newell–Pupyrev).
Why ext-TSP instead of fall-through weight?
It also rewards short jumps, which keeps hot code dense in the I-cache and I-TLB.
Complexity of optimal layout
Both maximum fall-through and maximum ext-TSP are NP-hard (Theorem 23.9.4, Corollary 23.9.7); production tools merge chains greedily.
Who uses ext-TSP?
BOLT by default, and LLVM's MachineBlockPlacement with -enable-ext-tsp-block-placement (CodeLayout.cpp).
branch-folding¶
Branch folding
Thread jumps through empty blocks, remove unreachable blocks and simplify branches (BranchFolder::OptimizeBlock).
Tail merging
Keep one copy of the common tail of several predecessors and branch into it; saves code size at the cost of a jump (BranchFolder::TailMergeBlocks).
When does LLVM run BranchFolder?
Before and after block placement: twice per code generator pipeline.
machine-peephole¶
Compare elimination in PeepholeOptimizer
Drop a compare/test when the instruction defining its operand already sets the needed flags and nothing in between clobbers them (optimizeCompareInstr).
MachineCSE
Scoped value numbering over the dominator tree on SSA MachineInstrs: replaces an instruction by an identical dominating one.
Why run peepholes on MachineInstrs at all?
Instruction selection duplicates constants and address computations and creates target patterns (flags, folded loads) the IR cannot see.
machine-code-motion¶
MachineLICM
Hoists loop-invariant MachineInstrs to the preheader: early (SSA, with pressure checks) and post-RA (only with free registers).
MachineSink
Moves an instruction into the successor that uses it, splitting critical edges if needed, so other paths do not pay for it.
When may MachineLICM hoist a load?
Only if nothing in the loop may write the loaded location (and it is safe to execute speculatively).
post-link¶
What is post-link optimization?
Re-laying out a whole linked binary from a production profile: block order, hot/cold splitting and function order.
BOLT
Meta's post-link optimizer: disassembles the binary, maps sampled profiles (LBR) to CFGs, reorders blocks (ext-TSP) and functions, splits cold code, and rewrites the binary (Panchenko et al. 2019).
Propeller
Google's relinking optimizer: turns the profile into basic-block cluster directives and regenerates code with -fbasic-block-sections (Shen et al. 2023).
hfsort / C³
Call-graph clustering for function order used by BOLT and linkers (Ottoni–Maher 2017).