Lesson 23.1 — Machine models: pipelines, latency, throughput and reservation tables

Techniques: reservation tables and hazard recognizers (collision vectors, pipeline automata); LLVM's per-operand machine model (SchedMachineModel, scheduling classes); static throughput analysis with llvm-mca · Lab: labs/ch23-sched §3 (the toy machine) · Prerequisites: Ch 21 (MachineInstrs, TableGen, the code generator pipeline) · Time: 4–5 hours

A scheduler reorders instructions so that a processor wastes fewer cycles. To do that it needs a model of the processor: how many instructions it can start per cycle, which units each instruction occupies and for how long, and how many cycles pass before a result can be used. With too simple a model, the scheduler optimizes the wrong thing. With too detailed a model, the scheduler is slow and the model is hard to maintain for dozens of processors. This lesson builds the model the rest of the chapter uses. It is small enough to reason about exactly, and it maps one to one onto what LLVM describes in TableGen and what llvm-mca simulates.

Take one example throughout. The lab's toy machine (labs/ch23-sched/inputs/running.txt) issues two instructions per cycle. It has two ALUs, one memory unit and one multiplier. A load's result is ready three cycles after issue, a multiply's also after three, and a divide's after six. The divide keeps the multiplier busy for four cycles, while a multiply occupies it for one. Two divides can therefore never start closer than four cycles apart, even when they are independent. Two multiplies can start on consecutive cycles, and each result still takes three cycles. That is the difference between latency (how long until the result is ready) and throughput (how often a unit accepts new work), and every scheduler must respect both.

1. Problem and motivation

Reservation tables and hazard recognizers

Early pipelined machines (the IBM 360/91, the CDC 6600) forced hardware designers to answer the question "when may the next operation start?". Davidson described each pipeline by a reservation table, a grid of stages × cycles marking which stage an operation uses in which cycle after it starts. From the table he derived forbidden latencies and a collision vector that a controller consults before it starts an operation [DSTP75]; Kogge's book collects the theory [Kog81]. Compiler writers adopted the same tables to describe structural hazards to a scheduler, that is, two operations wanting the same unit in the same cycle. Proebsting and Fraser [PF94], and Bala and Rubin [BR95], compiled the tables into finite automata so that a scheduler can ask "does this instruction fit in this cycle?" with one table lookup. GCC's genautomata builds such automata from define_insn_reservation descriptions [Mak03, GCC-genautomata], and LLVM's VLIW packetizer uses a DFA built the same way. In pebblec you meet reservation tables through LLVM's machine model and through the lab, whose toy machine gives every operation a table (Definition 23.1.2).

LLVM's per-operand machine model

LLVM first described processors with itineraries, which are reservation tables in all but name: a list of stages, each with a set of functional units and a cycle count. Itineraries were verbose and hard to write for out-of-order cores, whose "pipeline" is a pool of ports behind a large buffer. In 2012 LLVM added the per-operand machine model (SchedMachineModel), which describes each instruction by the resources it consumes (and for how many cycles) and by the latency of each result operand, plus a handful of global parameters: issue width, reorder-buffer size, load latency and mispredict penalty [LLVM-TargetSchedTD]. Every modern LLVM target (x86, AArch64, RISC-V, PowerPC) uses it, and the MachineScheduler (Lesson 23.7), the MachinePipeliner (Lesson 23.6) and llvm-mca read the same tables.

Static throughput analysis (llvm-mca)

A model is only useful if it is right, and it is hard to check by reading TableGen. llvm-mca (the LLVM Machine Code Analyzer) runs a sequence of instructions through a cycle-level simulation of the model and reports cycles, throughput, resource pressure and a timeline [LLVM-MCA, DD18]. It descends from Intel's IACA (no longer maintained) and has cousins in uiCA [AR22] and OSACA. Compiler engineers use it to debug machine models and to ask "why is this loop slow?" without running it. In this chapter it is the tool that makes latency, throughput and resource bounds visible on real processors.

2. Definitions and algorithms

Definition 23.1.1 (Machine model)

A machine model \(M = (W, \mathcal{R}, \mathrm{cap}, \mathcal{O}, \mathrm{lat}, \mathrm{RT})\) consists of an issue width \(W \ge 1\), a finite set \(\mathcal{R}\) of resources with capacities \(\mathrm{cap} : \mathcal{R} \to \mathbb{N}_{\ge 1}\) (among them the pseudo-resource \(\mathsf{issue}\) with \(\mathrm{cap}(\mathsf{issue}) = W\)), a set \(\mathcal{O}\) of operation classes, a latency \(\mathrm{lat} : \mathcal{O} \to \mathbb{N}_{\ge 1}\) and a reservation table \(\mathrm{RT}(o) \subseteq \mathcal{R} \times \mathbb{N}\) for each class. An operation of class \(o\) issued in cycle \(t\) reads its operands in cycle \(t\), occupies resource \(r\) in cycle \(t + k\) for every \((r, k) \in \mathrm{RT}(o)\), and its result is visible from cycle \(t + \mathrm{lat}(o)\).

Definition 23.1.2 (Reservation table, occupancy, usage)

In the lab's machines every class \(o\) has \(\mathrm{RT}(o) = \{(\mathsf{issue}, 0)\} \cup \{(u_o, k) \mid 0 \le k < \mathrm{occ}(o)\}\) for one unit \(u_o\) and an occupancy \(1 \le \mathrm{occ}(o) \le \mathrm{lat}(o)\). A unit with \(\mathrm{occ}(o) = 1\) for every class is fully pipelined. The usage of resource \(r\) by a multiset \(S\) of operations is \(U_r(S) = \sum_{x \in S} \lvert \{ k \mid (r, k) \in \mathrm{RT}(\mathrm{cls}(x)) \} \rvert\).

The toy machine

\(W = 2\); \(\mathrm{cap}(\mathsf{alu}) = 2\), \(\mathrm{cap}(\mathsf{mem}) = \mathrm{cap}(\mathsf{mul}) = 1\). Latencies and occupancies (unit in brackets): add, sub, li, … \(1/1\) [alu]; load \(3/1\) [mem]; store \(1/1\) [mem]; mul \(3/1\) [mul]; div \(6/4\) [mul]. So \(\mathrm{RT}(\mathtt{div}) = \{(\mathsf{issue},0), (\mathsf{mul},0), (\mathsf{mul},1), (\mathsf{mul},2), (\mathsf{mul},3)\}\): a div issued at cycle 5 blocks the multiplier in cycles 5–8, and its quotient is visible at 11.

Definition 23.1.3 (Resource-feasible placement)

A placement of operations \(x_1, \dots, x_n\) assigns issue cycles \(t_i \in \mathbb{N}\). It is resource-feasible if for every resource \(r\) and cycle \(c\), \(\lvert \{ (i, k) \mid (r, k) \in \mathrm{RT}(\mathrm{cls}(x_i)),\ t_i + k = c \} \rvert \le \mathrm{cap}(r)\).

The scheduler of Lesson 23.3 places operations one by one and asks, each time, whether the next one fits. The direct implementation keeps a global table of counts.

Algorithm 23.1.4 (Global reservation table)

• Input: a machine model; a sequence of queries Fits(o, c) and commands Place(o, c).
• Output: the answer to each query.
• Precondition: Place(o, c) is only called after Fits(o, c) returned true.
• Postcondition: Fits(o, c) is true iff adding an operation of class \(o\) at cycle \(c\) keeps the placement resource-feasible.
• Invariant: used[r][c] equals the number of pairs \((i, k)\) with \((r, k) \in \mathrm{RT}(x_i)\) and \(t_i + k = c\) over the operations placed so far, and used[r][c] \(\le \mathrm{cap}(r)\).

used[r][c] ← 0 for all r, c                 # a hash map in practice

function Fits(o, c):
    for (r, k) in RT(o):
        if used[r][c + k] + 1 > cap(r): return false
    return true

function Place(o, c):
    for (r, k) in RT(o):
        used[r][c + k] ← used[r][c + k] + 1

Fits assumes that a class uses each \((r, k)\) at most once, which holds for Definition 23.1.2. A table that lists the same pair twice must count multiplicities instead.

A hazard recognizer answers the same question without a table indexed by absolute cycle. It keeps only the future reservations relative to the current cycle. For one resource of capacity 1, this relative state is Davidson's collision vector.

Definition 23.1.5 (Forbidden latencies, collision vector)

Let \(r\) have capacity 1 and write \(K_r(o) = \{ k \mid (r, k) \in \mathrm{RT}(o) \}\). The forbidden latencies from class \(o\) to class \(o'\) are \(F(o, o') = \{ d \in \mathbb{N} \mid (K_r(o) - d) \cap K_r(o') \ne \emptyset \}\), where \(K - d = \{ k - d \mid k \in K \}\). The state of \(r\) at cycle \(c\) is the set \(s_c = \{ k \ge 0 \mid r \text{ is reserved in cycle } c + k \}\); as a bit vector it is the collision vector.

Lemma 23.1.6 (Forbidden latencies)

An operation \(x\) of class \(o\) issued at \(t\) and an operation \(x'\) of class \(o'\) issued at \(t' = t + d\), \(d \ge 0\), both use \(r\) in some cycle iff \(d \in F(o, o')\). In particular, with only these two operations on \(r\), the placement is feasible for \(r\) iff \(d \notin F(o, o')\).

Proof

\(x\) uses \(r\) in cycles \(t + K_r(o)\) and \(x'\) in cycles \(t + d + K_r(o')\). They share a cycle iff there are \(k \in K_r(o)\), \(k' \in K_r(o')\) with \(t + k = t + d + k'\), i.e. \(k - d = k'\), i.e. \((K_r(o) - d) \cap K_r(o') \neq \emptyset\), which is Definition 23.1.5. With capacity 1, sharing a cycle is exactly an overflow (Definition 23.1.3).

Algorithm 23.1.7 (Hazard recognizer as an automaton)

• Input: a machine model; a stream of events Issue(o) and Advance.
• Output: for each Issue(o), accept or reject.
• Precondition: every resource of interest has capacity 1 (for capacity \(m\), keep a count per future cycle instead of a bit).
• Postcondition: Issue(o) is accepted iff issuing \(o\) now keeps the placement of all accepted operations resource-feasible (Proposition 23.1.14).
• Invariant: for each \(r\), s[r] is the set of offsets \(k \ge 0\) such that \(r\) is reserved in cycle (now \(+ k\)) by an accepted operation.

s[r] ← ∅ for every resource r

function Issue(o):
    for r in resources:
        if s[r] ∩ K_r(o) ≠ ∅: return reject
    for r in resources: s[r] ← s[r] ∪ K_r(o)
    return accept

function Advance():                          # move to the next cycle
    for r in resources: s[r] ← { k − 1 | k ∈ s[r], k ≥ 1 }

The reachable tuples (s[r])_r are finitely many (each \(s[r] \subseteq \{0, \dots, D-1\}\) with \(D\) the largest offset in any table), so they can be enumerated once, numbered, and the two transition functions stored as arrays: this is the pipeline automaton of [PF94] and GCC's genautomata.

LLVM's per-operand machine model

LLVM does not store a table per instruction. It stores a scheduling class per instruction (derived from its SchedRW list), and per processor a mapping from those classes to resources and latencies.

Definition 23.1.8 (LLVM per-operand model)

A SchedMachineModel fixes IssueWidth (the \(W\) of Definition 23.1.1), MicroOpBufferSize (the reorder window of an out-of-order core; 0 means in-order), LoadLatency and MispredictPenalty. A ProcResource<n> is a resource with \(\mathrm{cap} = n\); a ProcResGroup is a set of resources any one of which may be used. Each SchedWrite (the "kind" of a defined operand) is mapped by WriteRes / SchedWriteRes to a latency and a list of resources with ReleaseAtCycles (occupancy, default 1) and optional AcquireAtCycles (the first offset, default 0). Each SchedRead (the kind of a used operand) may carry a ReadAdvance \(a \ge 0\): the use reads its operand \(a\) cycles late, so the producer may be \(a\) cycles later.

Proposition 23.1.9 (Operand latency in LLVM)

With the per-operand model, the latency that LLVM's schedulers put on the dependence from the definition in DefMI to the use in UseMI is \(\max(0, L_w - a)\), where \(L_w\) is the latency of the definition's SchedWrite and \(a\) is the ReadAdvance of the use's SchedRead for that write (0 if none).

Proof sketch (full proof: the code of TargetSchedModel::computeOperandLatency, [LLVM-TargetSched])

The function resolves the scheduling class of DefMI, looks up the write-latency entry of the defining operand (\(L_w\), capped) and returns it when there is no use. Otherwise it resolves the class of UseMI, looks up getReadAdvanceCycles(UseDesc, UseIdx, WriteID) \(= a\) and returns \(0\) if \(a > L_w\) and \(L_w - a\) otherwise, which is \(\max(0, L_w - a)\). The itinerary path and the missing-operand fallback (default latency) are separate branches and do not apply here.

Occupancy in a real model

Skylake's model (X86SchedSkylakeClient.td) declares def SKLFPDivider : ProcResource<1> and defm : SKLWriteResPair<WriteFDiv64Y, [SKLPort0, SKLFPDivider], 14, [1,8], 1, 7>: a 256-bit double divide has latency 14, uses port 0 for one cycle and the divider for eight. In the terms of Definition 23.1.2 it is the toy machine's div with \(\mathrm{lat} = 14\) and \(\mathrm{occ} = 8\) on a unit of capacity 1.

Static throughput analysis (llvm-mca)

Definition 23.1.10 (Throughput of a loop body)

Let a loop body \(B\) (a sequence of operations) run \(N\) times back to back on a machine, taking \(C(N)\) cycles. Its steady-state cycles per iteration is \(\lim_{N \to \infty} C(N)/N\). Its block reciprocal throughput in the model is

\[ \mathrm{RThr}(B) = \max\Big( \frac{\mu(B)}{W},\ \max_{r \in \mathcal{R}} \frac{U_r(B)}{\mathrm{cap}(r)} \Big) \]

where \(\mu(B)\) is the number of micro-operations and \(U_r\) counts occupied cycles (ReleaseAtCycles). A dependence cycle of \(B\) is a cycle of producer–consumer edges in the graph whose edges carry a latency \(\ell\) and an iteration distance \(d\) (0 inside one iteration, 1 from one iteration to the next).

Algorithm 23.1.11 (llvm-mca's simulation, simplified)

• Input: a sequence \(B\) of machine instructions, a processor model, an iteration count \(N\).
• Output: the total cycles \(C(N)\) and per-instruction timelines.
• Precondition: every instruction has a scheduling class in the model (else it is rejected, or skipped with -skip-unsupported-instructions).
• Postcondition: each instruction instance is dispatched, issued when its operands are ready (latency, Proposition 23.1.9) and its resources are free, executed and retired in order.
• Invariant: at most \(W\) micro-ops dispatch per cycle; the reorder buffer holds at most MicroOpBufferSize micro-ops; a resource with capacity \(n\) serves at most \(n\) micro-ops per cycle, each for its ReleaseAtCycles.

function Simulate(B, model, N):
    stream ← B repeated N times; cycle ← 0
    while some instance is not retired:
        Retire(): remove from the ROB head every executed instance, in order
        Execute(): advance executing instances; mark those whose latency elapsed as executed
                    (their results become available to readers, minus ReadAdvance)
        Issue(): for each dispatched instance in age order whose operands are available
                    and whose resources are free this cycle: reserve the resources
                    (for ReleaseAtCycles cycles) and start it
        Dispatch(): move up to W micro-ops from the stream into the ROB and the scheduler
                    queues, if there is room
        cycle ← cycle + 1
    return cycle

Theorem 23.1.12 (Two lower bounds on cycles per iteration)

In any execution consistent with a machine model, the steady-state cycles per iteration of a loop body \(B\) satisfy

\[ \lim_{N \to \infty} \frac{C(N)}{N} \ \ge\ \max\Big( \mathrm{RThr}(B),\ \max_{\text{dependence cycles } Z} \frac{\ell(Z)}{d(Z)} \Big), \]

where \(\ell(Z)\) and \(d(Z)\) are the sums of the latencies and of the distances on \(Z\) (cycles with \(d(Z) = 0\) cannot exist in a valid program).

Proof

Resources. In \(C(N)\) cycles a resource \(r\) can provide at most \(\mathrm{cap}(r) \cdot C(N)\) occupied cycles, and the \(N\) iterations need \(N \cdot U_r(B)\) of them, so \(C(N) \ge N \cdot U_r(B) / \mathrm{cap}(r)\). Likewise at most \(W\) micro-ops dispatch per cycle, so \(C(N) \ge N \mu(B) / W\). Divide by \(N\) and take the maximum.

Recurrences. Let \(Z\) visit operations \(z_0 \to z_1 \to \dots \to z_m = z_0\). Following \(Z\) once from instance \(j\) of \(z_0\) reaches instance \(j + d(Z)\) of \(z_0\), and each edge forces the consumer to start at least \(\ell\) cycles after the producer, so \(t(z_0, j + d(Z)) \ge t(z_0, j) + \ell(Z)\). By induction on \(q\), \(t(z_0, q \cdot d(Z)) \ge q \cdot \ell(Z)\), so running \(N \ge q\, d(Z)\) iterations takes at least \(q\, \ell(Z)\) cycles, and \(C(N)/N \ge \lfloor N/d(Z) \rfloor \ell(Z) / N \to \ell(Z)/d(Z)\).

The second bound is the one that dominates the dot-product box in §7: the resource bound is 1 cycle per iteration, but the accumulator makes a dependence cycle of latency 4 and distance 1. Lesson 23.6 turns exactly these two bounds into ResMII and RecMII.

3. Worked example

Reservation tables and hazard recognizers

Place the running block of Lesson 23.2 in the order the top-down list scheduler of Lesson 23.3 chooses: c at 0, a at 1, b at 2, e at 3, f at 4, d and g at 5, h at 6, i at 8, j at 9. The global table of Algorithm 23.1.4 after all placements (. = free, capacity in the header):

cycle	issue (2)	alu (2)	mem (1)	mul (1)	placed
0	1	.	c	.	c (load)
1	1	.	a	.	a (load)
2	1	.	b	.	b (load)
3	1	e	.	.	e (add)
4	1	.	.	f	f (mul)
5	2	.	g	d	d (mul), g (load)
6	1	.	h	.	h (store)
7	0	.	.	.	—
8	1	i	.	.	i (sub)
9	1	j	.	.	j (add)

• The memory unit is busy in cycles 0, 1, 2, 5 and 6: five memory operations on a unit of capacity 1 need five distinct cycles, which is the resource bound \(\lceil 5/1 \rceil = 5\) of Theorem 23.1.12.
• In cycle 5 the issue slots are full (2 of 2) but d and g use different units, so Fits succeeds for both.
• Cycle 7 is empty: nothing is ready (Lesson 23.3 explains why).

Now suppose f were a div instead of a mul. Its table reserves the multiplier in cycles 4–7, so Fits(mul, 5) for d fails at \((\mathsf{mul}, 5)\), and d cannot issue before cycle 8. The hazard recognizer of Algorithm 23.1.7 sees the same thing through the state of the multiplier:

event	\(s[\mathsf{mul}]\) before	action	\(s[\mathsf{mul}]\) after
cycle 4: Issue(div)	\(\emptyset\)	\(K = \{0,1,2,3\}\), no overlap: accept	\(\{0,1,2,3\}\)
Advance	\(\{0,1,2,3\}\)	shift	\(\{0,1,2\}\)
cycle 5: Issue(mul)	\(\{0,1,2\}\)	\(K = \{0\}\) overlaps at 0: reject	\(\{0,1,2\}\)
Advance, Advance		shift twice	\(\{0\}\)
cycle 7: Issue(mul)	\(\{0\}\)	overlaps at 0: reject	\(\{0\}\)
Advance	\(\{0\}\)	shift	\(\emptyset\)
cycle 8: Issue(mul)	\(\emptyset\)	accept	\(\{0\}\)

The forbidden latencies agree (Lemma 23.1.6): \(F(\mathtt{div}, \mathtt{mul}) = \{0, 1, 2, 3\}\) because \(K(\mathtt{div}) - d\) contains \(0 \in K(\mathtt{mul})\) exactly for \(d \le 3\), while \(F(\mathtt{mul}, \mathtt{div}) = \{0\}\) and \(F(\mathtt{mul}, \mathtt{mul}) = \{0\}\). The multiplier's automaton has five reachable states: \(\emptyset, \{0\}, \{0,1\}, \{0,1,2\}, \{0,1,2,3\}\).

Try it

./course drill list-schedule --seed 4 --solution prints a reservation table like the one above for a random block, and ./course drill mii --seed 2 --solution counts resource usage for a loop (Lesson 23.6).

LLVM's per-operand machine model

Take vdivpd %ymm2, %ymm1, %ymm0 on Skylake. Its scheduling class maps to WriteFDiv64Y, which the example after Proposition 23.1.9 resolves to latency 14 and resources [SKLPort0, SKLFPDivider] with ReleaseAtCycles = [1, 8]. In Definition 23.1.1 terms: \(\mathrm{lat} = 14\), \(\mathrm{RT} = \{(\mathsf{issue}, 0), (\mathsf{p0}, 0), (\mathsf{fpdiv}, 0..7)\}\). Two independent vdivpd in a row: the second fails Fits on \(\mathsf{fpdiv}\) for \(d = 0, \dots, 7\) and starts 8 cycles after the first, so its result appears at \(8 + 14 = 22\) cycles. The timeline box in §7 shows exactly this: the second divide waits eight cycles.

A consumer that reads the quotient through an operand with ReadAdvance 0 sees latency \(\max(0, 14 - 0) = 14\) (Proposition 23.1.9). A ReadAdvance of 2 on some other operand kind (typical for accumulator inputs of multiply–add units) would shorten the edge to 12.

Static throughput analysis (llvm-mca)

The loop body vdivpd; vdivpd; vmulpd; vmulpd (four independent instructions) on Skylake has \(\mu = 4\), \(W = 6\) and \(U_{\mathsf{fpdiv}} = 2 \cdot 8 = 16\), \(\mathrm{cap} = 1\), so

\[ \mathrm{RThr} = \max\big(4/6,\ 16/1,\ \dots\big) = 16 . \]

There is no dependence cycle, so Theorem 23.1.12 predicts about 16 cycles per iteration: the simulated 100 iterations take 1609 cycles (the §7 box). For the dot-product loop of the other §7 box, \(\mathrm{RThr} = 1\) (six micro-ops, six-wide), but vfmadd231pd … %ymm0 feeds itself with latency 4 and distance 1, so the recurrence bound is \(4/1 = 4\) and the simulation reports 410 cycles for 100 iterations.

4. Invariants and correctness

Reservation tables and hazard recognizers

Lemma 23.1.13 (Algorithm 23.1.4 is correct)

After any sequence of Place calls, each preceded by a successful Fits, the invariant of Algorithm 23.1.4 holds, and Fits(o, c) returns true iff the placement extended by \(o\) at \(c\) is resource-feasible.

Proof

Invariant, by induction on the number of Place calls. Initially all counts are 0 and no operation is placed. Place(o, c) adds exactly one to used[r][c + k] for each \((r, k) \in \mathrm{RT}(o)\), which is the contribution of the new operation to the count of Definition 23.1.3; since Fits(o, c) held, each incremented count is at most \(\mathrm{cap}(r)\), and the other counts do not change. Query. Adding \(o\) at \(c\) increases the count of \((r, c + k)\) by one for each \((r, k) \in \mathrm{RT}(o)\) and leaves all others; the extended placement is feasible iff each of those counts stays \(\le \mathrm{cap}(r)\), which is what Fits tests using the invariant.

Proposition 23.1.14 (The automaton recognizes feasible issue sequences)

Under the precondition of Algorithm 23.1.7, Issue(o) accepts iff issuing \(o\) in the current cycle keeps the placement of all accepted operations resource-feasible, and the invariant holds after every event.

Proof

By induction on the number of events. Initially no operation is accepted and every s[r] is empty. Advance: the current cycle moves from \(c\) to \(c + 1\); an offset \(k \ge 1\) relative to \(c\) is the offset \(k - 1\) relative to \(c + 1\), and offset 0 lies in the past, which is exactly the update. Issue(o) at cycle \(c\): the new operation needs \(r\) in cycles \(c + K_r(o)\); by the invariant \(r\) is already reserved in cycle \(c + k\) iff \(k \in\) s[r]. With capacity 1 the extension is feasible iff no \(k \in K_r(o)\) is already reserved for any \(r\), i.e. iff s[r] \(\cap K_r(o) = \emptyset\) for all \(r\), which is the accept test; on acceptance the reserved offsets become s[r] \(\cup K_r(o)\).

The automaton can only look forward. It assumes that operations are issued in nondecreasing cycle order, as a top-down scheduler does. A bottom-up scheduler needs the automaton of the reversed tables [PF94] (Lesson 23.3 mirrors tables the same way, Definition 23.3.5).

LLVM's per-operand machine model

The model is a description, not an algorithm, so the correctness question is "is the computed latency the one the hardware needs?". Proposition 23.1.9 pins down what LLVM computes. Whether that matches silicon is an empirical question: llvm-exegesis measures latencies and throughputs on the host to validate models, and wrong models are ordinary bugs that the LLVM repository fixes regularly.

Latency is per operand, not per instruction

An instruction does not have "a latency" in LLVM's model: each defined operand has one, and each use can shorten it with ReadAdvance. llvm-mca's "Latency" column is the largest write latency of the instruction; the dependence edge to a particular consumer may be shorter (Proposition 23.1.9). A load-op instruction such as vfmadd231pd (%rsi), %ymm1, %ymm0 adds the load latency on the memory operand only, not on the register accumulator.

Static throughput analysis (llvm-mca)

Theorem 23.1.12 is the correctness statement a simulator must never violate: a simulation reporting fewer cycles per iteration than \(\max(\mathrm{RThr}, \ell/d)\) would contradict the model it simulates. llvm-mca is not a proof of performance on real hardware. It ignores the front end (decoding and the µop cache, unless modeled), caches (every load hits with LoadLatency), branch prediction and memory disambiguation. Its figures are those of the model, and they are only as good as the model.

5. Complexity

Let \(n\) be the number of operations placed, \(\rho = \max_o \lvert \mathrm{RT}(o) \rvert\) the size of the largest reservation table, \(D\) the largest offset in any table, and \(\lvert\mathcal{R}\rvert\) the number of resources.

Technique	Time per query	Space	Notes
Global reservation table (Alg. 23.1.4)	\(O(\rho)\) for Fits and Place	\(O(\lvert\mathcal{R}\rvert \cdot T)\) counts for a schedule of length \(T\) (or \(O(n\rho)\) in a hash map)	one pass over the table per query
Collision-vector recognizer (Alg. 23.1.7), interpreted	\(O(\lvert\mathcal{R}\rvert \cdot D / w)\) per event with \(w\)-bit words	\(O(\lvert\mathcal{R}\rvert D)\) bits	shifts and ANDs of bit vectors
Pipeline automaton (precomputed)	\(O(1)\) per event	\(O(\lvert Q \rvert \cdot \lvert\mathcal{O}\rvert)\) transitions, \(\lvert Q \rvert \le 2^{\lvert\mathcal{R}\rvert D}\)	built once per processor
llvm-mca simulation	\(O(N \cdot \lvert B \rvert \cdot \rho)\) plus queue management	\(O(\text{ROB size})\)	\(N\) iterations of a body of \(\lvert B \rvert\) instructions

Justification. Fits and Place loop once over \(\mathrm{RT}(o)\). The recognizer's state is one set of offsets below \(D\) per resource, and each event touches every resource once. The automaton bound counts all tuples of subsets.

Pathological family (automaton size). Take one resource \(r\) of capacity 1 and \(D\) classes \(o_0, \dots, o_{D-1}\) with \(K_r(o_j) = \{j\}\), and let the issue width be \(D\). In one cycle you can issue any subset \(J\) of classes with distinct offsets, reaching state \(s = J\). So all \(2^D\) subsets of \(\{0, \dots, D-1\}\) are reachable, and the automaton has at least \(2^D\) states. Real processors are far from this worst case, but automata for VLIW cores with many units still grow large. GCC therefore factors the automaton into one per group of units (define_automaton) and keeps their product implicit [Mak03, BR95].

Scale. The Skylake model declares a dozen port resources and groups, and llvm-mca simulates 100 iterations of a 5-instruction loop in well under a second. The global table is what the lab and LLVM's MachineScheduler use. LLVM's ScheduleHazardRecognizer and the Hexagon packetizer use automata.

6. Variants and refinements

Reservation tables and hazard recognizers

• Resource classes instead of individual units (the lab, LLVM's ProcResource<n>): one count per class instead of choosing a specific unit. This is simpler and exact when all units of a class are interchangeable, but it cannot express "port 0 or port 1" as flexibly as groups (next bullet).
• Alternative resources (ProcResGroup, GCC's | in reservations): an operation needs any one of several units. The query becomes a small matching problem. LLVM's ResourceManager in llvm-mca picks a unit greedily, which is fast but may be suboptimal when groups overlap.
• Factored automata [BR95, Mak03]: one automaton per subset of resources, combined by product. They are much smaller but need one lookup per factor. GCC's define_automaton / automata_option implement this.
• Reverse automata [PF94]: the same construction on mirrored tables, for bottom-up schedulers (Definition 23.3.5 mirrors the tables the same way).

LLVM's per-operand machine model

• Itineraries (InstrItinData, stages with units and cycles): the older, table-based model. Some in-order and VLIW targets (Hexagon, older ARM cores) still use them. They are precise for in-order pipelines and verbose for out-of-order ones.
• Variant scheduling classes (SchedVariant, SchedPredicate): the class depends on operands, e.g. a zero idiom xor %eax, %eax has latency 0. More accurate, but more TableGen to maintain.
• Buffers (BufferSize per resource, MicroOpBufferSize): model reservation stations and in-order units. The MachineScheduler uses them to decide whether latency even matters: in a large out-of-order window it mostly doesn't (Lesson 23.7).

Static throughput analysis (llvm-mca)

• uiCA [AR22]: a more detailed simulator of Intel front ends and µop fusion, with lower error than llvm-mca on the authors' benchmarks, but only for Intel cores.
• Analytic bounds only (OSACA, and llvm-mca's "Block RThroughput" line): compute \(\mathrm{RThr}\) and the critical path without simulating. This is instant, but it misses interactions such as port contention between iterations.
• Measurement (llvm-exegesis, perf): ground truth on real hardware, needed to calibrate the models. (perf counters are not available in the container this course was built in, so no measured numbers appear here.)

7. In real compilers

Reservation tables and hazard recognizers

LLVM's generic hazard interface is ScheduleHazardRecognizer (llvm/include/llvm/CodeGen/ScheduleHazardRecognizer.h), with a scoreboard implementation for itinerary models (ScoreboardHazardRecognizer.cpp) and the automaton-based DFAPacketizer for VLIW bundling. The MachineScheduler instead books per-resource cycles in SchedBoundary::getNextResourceCycle (llvm/lib/CodeGen/MachineScheduler.cpp), which is the global-table idea of Algorithm 23.1.4 [LLVM-MISched]. GCC generates automata from define_insn_reservation patterns in gcc/genautomata.cc (the header comment cites the construction and the factoring) [GCC-genautomata].

A non-pipelined divider in the Skylake model

Reproduce (llvm-mca 23.1.2; any host):

cat > div.s <<'EOF'
vdivpd %ymm0, %ymm1, %ymm2
vdivpd %ymm0, %ymm1, %ymm3
vmulpd %ymm0, %ymm1, %ymm4
vmulpd %ymm0, %ymm1, %ymm5
EOF
llvm-mca -mtriple=x86_64-unknown-linux-gnu -mcpu=skylake -iterations=1 -timeline \
  -instruction-info=false -resource-pressure=false div.s | sed -n '/^Timeline view/,/ymm5$/p'
for c in skylake znver4; do echo "== $c"
  llvm-mca -mtriple=x86_64-unknown-linux-gnu -mcpu=$c -iterations=100 div.s \
    | grep -E 'Total Cycles|Block RThroughput'; done

Output (complete):

Timeline view:
                    0123456789     
Index     0123456789          01234

[0,0]     DeeeeeeeeeeeeeeER   .   .   vdivpd    %ymm0, %ymm1, %ymm2
[0,1]     D========eeeeeeeeeeeeeeER   vdivpd    %ymm0, %ymm1, %ymm3
[0,2]     DeeeeE------------------R   vmulpd    %ymm0, %ymm1, %ymm4
[0,3]     D=eeeeE-----------------R   vmulpd    %ymm0, %ymm1, %ymm5
== skylake
Total Cycles:      1609
Block RThroughput: 16.0
== znver4
Total Cycles:      1011
Block RThroughput: 10.0

What to notice: D is dispatch, = waiting, e executing. The second vdivpd is independent of the first, yet it waits eight cycles (========): the divider's forbidden latencies are \(\{0, \dots, 7\}\) (Lemma 23.1.6). The two vmulpd start one cycle apart, because the multiplier ports are pipelined. Over 100 iterations Skylake needs \(16.09\) cycles per iteration, at the resource bound \(2 \times 8 = 16\) of Theorem 23.1.12. Zen 4's model books its divide resources for 5 cycles, hence 10.

LLVM's per-operand machine model

The classes are declared in llvm/include/llvm/Target/TargetSchedule.td (SchedMachineModel, ProcResource, ProcResGroup, WriteRes, SchedWriteRes, ReadAdvance) [LLVM-TargetSchedTD]. Per-processor models live next to the targets, e.g. llvm/lib/Target/X86/X86SchedSkylakeClient.td (SkylakeClientModel: IssueWidth = 6, MicroOpBufferSize = 224, LoadLatency = 5) [LLVM-SKLSched] and llvm/lib/Target/AArch64/AArch64SchedNeoverseV2.td (NeoverseV2Model: IssueWidth = 6, MicroOpBufferSize = 320) [LLVM-NV2Sched]. TargetSchedModel::computeOperandLatency in llvm/lib/CodeGen/TargetSchedule.cpp computes the edge latencies of Proposition 23.1.9 [LLVM-TargetSched]. GCC describes the same information with define_cpu_unit and define_insn_reservation in each config/<cpu>/*.md file.

What the Skylake model says about three instructions

Reproduce (llvm-mca 23.1.2; --instruction-tables=full prints the model instead of simulating):

cat > model.s <<'EOF'
imulq %rsi, %rdi
vdivpd %ymm2, %ymm1, %ymm0
movq (%rdi), %rax
EOF
llvm-mca -mtriple=x86_64-unknown-linux-gnu -mcpu=skylake --instruction-tables=full model.s \
  | sed -n '/^\[1\]    \[2\]/,/^$/p'

Output (complete):

[1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]                                        [9]                        Instructions:
 1      3     1.00                         3     SKLPort1,SKLPort01,SKLPort15,SKLPort16,SKLPort015,SKLPort0156,SKLPortAny IMUL64rr imulq    %rsi, %rdi  
 1      14    8.00                         14    SKLFPDivider[8],SKLPort0,SKLPort01,SKLPort04,SKLPort05,SKLPort06,SKLPort015,SKLPort056,SKLPort0156,SKLPortAny VDIVPDYrr vdivpd %ymm2, %ymm1, %ymm0 
 1      5     0.50    *                    5     SKLPort23,SKLPort237,SKLPortAny            MOV64rm                    movq (%rdi), %rax    

What to notice: column [2] is the latency, [3] the reciprocal throughput and [8] the resources with ReleaseAtCycles in brackets (Definition 23.1.8). vdivpd has latency 14 and SKLFPDivider[8], hence reciprocal throughput 8.00: the occupancy of Definition 23.1.2. The load's latency 5 is the model's LoadLatency. The groups (SKLPort01, …) are listed because a micro-op on port 1 also counts against every group that contains port 1.

Static throughput analysis (llvm-mca)

llvm/tools/llvm-mca/llvm-mca.cpp drives the pipeline built in llvm/lib/MCA/ (stages DispatchStage, ExecuteStage, RetireStage; resources in HardwareUnits/ResourceManager.cpp). The "Block RThroughput" line is computeBlockRThroughput in llvm/lib/MCA/Support.cpp: the maximum of micro-ops over dispatch width and, for every resource, occupied cycles over units, which is Definition 23.1.10 [LLVM-MCASrc]. The tool is documented in [LLVM-MCA].

The same dot-product loop on four processor models

Reproduce (llvm-mca 23.1.2):

cat > dot-x86.s <<'EOF'
.Lloop:
  vmovupd (%rdi,%rax), %ymm1
  vfmadd231pd (%rsi,%rax), %ymm1, %ymm0
  addq $32, %rax
  cmpq %rcx, %rax
  jne .Lloop
EOF
cat > dot-a64.s <<'EOF'
.Lloop:
  ldr q1, [x0, x8]
  ldr q2, [x1, x8]
  fmla v0.2d, v1.2d, v2.2d
  add x8, x8, #16
  cmp x8, x9
  b.ne .Lloop
EOF
for c in skylake znver4; do echo "== x86-64 $c"
  llvm-mca -mtriple=x86_64-unknown-linux-gnu -mcpu=$c -iterations=100 dot-x86.s \
    | grep -E 'Total Cycles|IPC|Block RThroughput'; done
for c in neoverse-v2 apple-m1; do echo "== aarch64 $c"
  llvm-mca -mtriple=aarch64-unknown-linux-gnu -mcpu=$c -iterations=100 dot-a64.s \
    | grep -E 'Total Cycles|IPC|Block RThroughput'; done

Output (complete):

== x86-64 skylake
Total Cycles:      410
IPC:               1.22
Block RThroughput: 1.0
== x86-64 znver4
Total Cycles:      411
IPC:               1.22
Block RThroughput: 1.0
== aarch64 neoverse-v2
Total Cycles:      211
IPC:               2.84
Block RThroughput: 1.0
== aarch64 apple-m1
Total Cycles:      513
IPC:               1.17
Block RThroughput: 2.0

What to notice: on all four models the loop runs well above its resource bound (Block RThroughput). The binding constraint is the accumulator recurrence of Theorem 23.1.12: the FMA latency is 4 on Skylake and Zen 4, so about 4.1 cycles per iteration. Neoverse V2's model forwards the accumulator early (a ReadAdvance, Proposition 23.1.9), so 2.1 cycles. The apple-m1 model (LLVM's Cyclone-derived model) is slower still. The cure is to break the recurrence with several accumulators, which is what unrolling plus reassociation does (Ch 18), or to overlap iterations (Lesson 23.6).

8. Comparison

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

Choose reservation tables when you control the scheduler and the machine is in-order or VLIW: they are exact and cheap. Compile them to an automaton when queries dominate compile time. Choose the per-operand model when you target out-of-order cores with LLVM. There is no alternative in-tree for new targets. Choose llvm-mca when you need to understand why a kernel runs at the speed it does, or whether a model change helps, before (or instead of) measuring on hardware.

9. Assessment

• Quiz (./course quiz 23): mca-rthroughput (number: compute RThroughput), forbidden-latencies (set), operand-latency (number), find-skl-divider (find it in LLVM: ReleaseAtCycles of the divider), tables-vs-automaton (single). Tags reservation-tables, machine-model, llvm-mca.
• Drills: ./course drill list-schedule (every placement checks a reservation table with occupancy); ./course drill mii (resource usage counted from reservation tables). The per-operand model and llvm-mca are read, not computed by hand, so they have no drill of their own: the §7 boxes and the quiz's "find it in LLVM" questions cover them.
• Flashcards (./course flash 23): tags reservation-tables, machine-model, llvm-mca.
• Lab: the toy machine of labs/ch23-sched/SPEC.md §3; every lab test checks resource feasibility with Algorithm 23.1.4.

References

See the chapter references.