Lesson 23.6 — Software pipelining: modulo scheduling, MII, and code generation¶
Techniques: modulo-schedule bounds (ResMII, RecMII, the modulo reservation table); iterative modulo scheduling (Rau); swing modulo scheduling (Llosa et al.; LLVM's MachinePipeliner, GCC's SMS); code generation for modulo schedules (prologue/kernel/epilogue, modulo variable expansion, rotating registers) · Lab:
labs/ch23-schedE4–E5 (--algo=modulo) · Drills:mii,modulo-table· Prerequisites: Lesson 23.3, Ch 18 (loops, dependence distances) · Time: 6–8 hours
List scheduling a loop body treats each iteration as a separate block: iteration \(k+1\) cannot start until iteration \(k\) has drained, so a body whose critical path is 12 cycles takes 12 cycles per iteration even when the machine is idle most of that time. Software pipelining overlaps iterations. A new iteration starts every \(\mathit{II}\) cycles (the initiation interval), long before the previous ones finish, the way a hardware pipeline starts a new instruction before the previous one completes. Modulo scheduling finds such a schedule for one iteration, \(\sigma\), under the constraint that all iterations use the same schedule shifted by multiples of \(\mathit{II}\). It then generates a prologue that fills the pipeline, a kernel that runs in steady state, and an epilogue that drains it. Two lower bounds say how small \(\mathit{II}\) can be: the resources (ResMII) and the loop-carried dependence cycles (RecMII). The best algorithms reach \(\max(\mathrm{ResMII}, \mathrm{RecMII})\) on almost every loop.
The running example is the lab's loop (toy machine: issue 2, two ALUs, one memory unit, one multiplier; load and mul take 3 cycles, add and store 1). It computes \(x_k = x_{k-1} \cdot s + A[k] \cdot B[k]\) and stores \(C[k] = x_k\):
loop run # labs/ch23-sched/inputs/running.txt; s in r9
liveout r6
a: r1 = load A[i]
b: r2 = load B[i]
c: r3 = mul r1, r2
d: r4 = mul r6, r9 # r6 is read before e defines it: x_{k-1}, distance 1
e: r6 = add r4, r3
f: store C[i], r6
end
1. Problem and motivation¶
Modulo-schedule bounds (ResMII and RecMII)¶
Rau and Glaeser built the first modulo scheduler for a polycyclic VLIW processor and stated the resource bound [RG81]. Lam's software pipelining for the Warp systolic array made the approach practical for a real compiler, with modulo variable expansion for registers and hierarchical reduction for conditionals [Lam88]. Both rest on the same observation: if one iteration's schedule, repeated every \(\mathit{II}\) cycles, never asks for more resources than the machine has in any row of a table with \(\mathit{II}\) rows, and never violates a dependence into a later iteration, then the overlapped execution is valid (Theorem 23.6.6). The two lower bounds let a scheduler start its search at the right \(\mathit{II}\), and let you judge a result. In pebblec's pipeline, LLVM's MachinePipeliner uses exactly these bounds (§7).
Iterative modulo scheduling¶
Finding a valid modulo schedule at \(\mathit{II} = \mathrm{MII}\) is NP-hard in general, and a greedy list scheduler often fails when recurrences constrain the loop: an operation placed early can violate a dependence with an operation placed later in the next iteration. Rau's iterative modulo scheduling (IMS) keeps the list-scheduling structure but allows backtracking. An operation that finds no conflict-free slot is placed anyway, and the operations it conflicts with are evicted and rescheduled, within a budget [Rau94]. When the budget runs out, \(\mathit{II}\) grows by one. The lab asks you to implement IMS.
Swing modulo scheduling¶
IMS minimizes \(\mathit{II}\) but not register pressure. It happily places a producer far from its consumer, and every cycle of lifetime costs registers in the kernel. Llosa, González, Ayguadé and Valero's swing modulo scheduling (SMS) orders the operations so that each one has, when scheduled, only predecessors or only successors already placed, and then places each as close as possible to them. The result is short lifetimes with no backtracking [LGAV96]. SMS is the algorithm of GCC's modulo-sched.cc and of LLVM's MachinePipeliner (Hexagon, PowerPC, AArch64, RISC-V, ARM).
Modulo code generation¶
A modulo schedule is not yet code. Operations of one iteration are spread over \(S\) stages of \(\mathit{II}\) cycles each. The kernel contains stage 0 of iteration \(k\), stage 1 of iteration \(k-1\), and so on, so the loop must be entered through a prologue and left through an epilogue. And a value that lives longer than \(\mathit{II}\) cycles is overwritten by the next iteration's copy before its last use. Lam solved that in software by unrolling the kernel and renaming (modulo variable expansion, MVE) [Lam88]. The Cydra 5 and later Itanium solved it in hardware with rotating registers, whose names shift by one on every kernel iteration [DHB89]. The lab's toy machine has rotating registers (SPEC §6.4).
2. Definitions and algorithms¶
Definition 23.6.1 (Loop dependence graph)
The dependence graph of a loop body \(x_1, \dots, x_n\) has an edge \(x_i \to x_j\) with a latency \(\ell \ge 0\) and a distance \(d \ge 0\) whenever instance \(k + d\) of \(x_j\) depends on instance \(k\) of \(x_i\) (Lesson 23.2's kinds, across iterations). Edges with \(d = 0\) go forward in the body. In the lab: register flow edges only (renaming removes register anti and output dependences), with \(d = 0\) if the definition precedes the use in the body and \(d = 1\) otherwise; and memory edges between \(X[i + c_1]\) and \(X[i + c_2]\) (one a store) with \(d = \lvert c_1 - c_2 \rvert\) in the direction of execution (SPEC §6.1).
Definition 23.6.2 (Modulo schedule, stages, MRT)
A modulo schedule is an integer \(\mathit{II} \ge 1\) and \(\sigma : \{x_1..x_n\} \to \mathbb{N}\). Instance \(k\) of \(x_j\) issues at \(\sigma(x_j) + k \cdot \mathit{II}\). The stage of \(x_j\) is \(\lfloor \sigma(x_j)/\mathit{II} \rfloor\) and the stage count is \(S = \max_j \lfloor \sigma(x_j) / \mathit{II} \rfloor + 1\). The modulo reservation table (MRT) has \(\mathit{II}\) rows; operation \(x_j\) occupies resource \(r\) in row \((\sigma(x_j) + o) \bmod \mathit{II}\) for every \((r, o) \in \mathrm{RT}(x_j)\). The schedule is valid if
and no row of the MRT uses a resource \(r\) more than \(\mathrm{cap}(r)\) times.
Definition 23.6.3 (ResMII, RecMII, MII)
With \(U_r\) the usage of resource \(r\) by one iteration (Definition 23.1.2) and the cycles \(C\) of the dependence graph with total latency \(\ell(C)\) and total distance \(d(C) \ge 1\):
Modulo-schedule bounds (ResMII and RecMII)¶
Algorithm 23.6.4 (Computing MII)
- Input: a loop dependence graph; a machine model.
- Output: ResMII, RecMII, MII.
- Precondition: every cycle has total distance \(\ge 1\).
- Postcondition: the values of Definition 23.6.3 (Theorem 23.6.7).
- Invariant: in the RecMII loop, every \(\mathit{II}' < \mathit{II}\) has been shown infeasible (a positive cycle exists for the weights \(\ell - \mathit{II}' d\)).
function ResMII(body):
for each resource r: U[r] ← Σ over x in body of |{ o | (r, o) ∈ RT(x) }|
return max over r of ⌈U[r] / cap(r)⌉
function RecMII(G):
II ← 1
while PositiveCycle(G, II): II ← II + 1
return II
function PositiveCycle(G, II): # Floyd–Warshall on longest paths
D[u][v] ← max over edges u→v of (ℓ − II·d), or −∞
for k, u, v: D[u][v] ← max(D[u][v], D[u][k] + D[k][v])
return some D[v][v] > 0
Theorem 23.6.5 (Every valid modulo schedule has II ≥ MII)
If \((\mathit{II}, \sigma)\) is valid, then \(\mathit{II} \ge \mathrm{ResMII}\) and \(\mathit{II} \ge \mathrm{RecMII}\).
Proof
Resources. The MRT has \(\mathit{II}\) rows and each row holds at most \(\mathrm{cap}(r)\) uses of \(r\), so at most \(\mathit{II} \cdot \mathrm{cap}(r)\) uses fit. One iteration places all \(U_r\) of them, so \(U_r \le \mathit{II} \cdot \mathrm{cap}(r)\), and \(\mathit{II}\) is an integer: \(\mathit{II} \ge \lceil U_r / \mathrm{cap}(r) \rceil\) for every \(r\). Recurrences. Sum the validity inequality around a cycle \(C = v_0 \to v_1 \to \dots \to v_m = v_0\): the \(\sigma\) terms telescope to \(0 \ge \ell(C) - \mathit{II} \cdot d(C)\), so \(\mathit{II} \ge \ell(C) / d(C)\) and, being an integer, \(\mathit{II} \ge \lceil \ell(C)/d(C) \rceil\) for every cycle.
Theorem 23.6.6 (Validity of the overlapped execution)
If \((\mathit{II}, \sigma)\) is valid, then issuing instance \(k\) of every \(x_j\) at \(\sigma(x_j) + k\,\mathit{II}\) for \(k = 0, 1, \dots, N-1\) respects every dependence between all instances, and in every cycle no resource is used beyond its capacity.
Proof
Dependences. An edge \((x_i \to x_j, \ell, d)\) relates instance \(k\) of \(x_i\) to instance \(k + d\) of \(x_j\). Their issue times differ by \(\sigma(x_j) + (k + d)\mathit{II} - \sigma(x_i) - k\,\mathit{II} = \sigma(x_j) - \sigma(x_i) + d\,\mathit{II} \ge \ell\) by validity. Resources. Instance \(k\) of \(x_j\) uses \(r\) in absolute cycle \(t = \sigma(x_j) + o + k\,\mathit{II}\), whose row is \(t \bmod \mathit{II} = (\sigma(x_j) + o) \bmod \mathit{II}\), independent of \(k\). Two uses in the same absolute cycle therefore come from two distinct (operation, offset) pairs in the same MRT row: two instances of one pair differ in \(k\) and so land \(\mathit{II}\) cycles apart. So the number of uses in any cycle is at most the count of that MRT row, which is at most \(\mathrm{cap}(r)\).
Theorem 23.6.7 (Algorithm 23.6.4 computes RecMII, and every II ≥ RecMII is dependence-feasible)
The smallest \(\mathit{II} \ge 1\) for which the weights \(\ell - \mathit{II} d\) admit no positive cycle equals \(\mathrm{RecMII}\) of Definition 23.6.3. For every such \(\mathit{II}\), the longest-path values \(\sigma(v) = \max(0, \max_{u \leadsto v} \text{weight})\) satisfy every dependence constraint.
Proof
A cycle \(C\) is non-positive for weight \(\ell - \mathit{II} d\) iff \(\ell(C) \le \mathit{II}\,d(C)\) iff \(\mathit{II} \ge \ell(C)/d(C)\) (as \(d(C) \ge 1\)) iff \(\mathit{II} \ge \lceil \ell(C)/d(C) \rceil\). All cycles are non-positive iff \(\mathit{II}\) is at least the maximum of these, which is RecMII. Every cycle is a union of elementary cycles, so checking all cycles through Floyd–Warshall's diagonal is equivalent. The property is monotone in \(\mathit{II}\), so the upward search stops exactly at RecMII. With no positive cycles, longest paths from a virtual source (edges of weight 0 to every node) are finite, and for each edge \(\sigma(v) \ge \sigma(u) + \ell - \mathit{II} d\) by the definition of a longest path.
Iterative modulo scheduling¶
Definition 23.6.8 (HeightR)
For a candidate \(\mathit{II}\), \(\mathrm{HeightR}(x)\) is the length of the longest path from \(x\) to a virtual STOP node, with edge weights \(\ell - \mathit{II} d\) and an edge of weight \(\mathrm{lat}(x)\) from every \(x\) to STOP. It is Lesson 23.2's height with loop-carried edges discounted by \(\mathit{II}\).
Algorithm 23.6.9 (Iterative modulo scheduling, Rau 1994)
- Input: a loop dependence graph; a machine model; a budget ratio \(\beta\) (the lab uses 3).
- Output: \((\mathit{II}, \sigma)\) valid.
- Precondition: \(\mathrm{MII}\) from Algorithm 23.6.4.
- Postcondition: the returned schedule is valid (Proposition 23.6.13); \(\mathit{II} \ge \mathrm{MII}\).
- Invariant: the scheduled operations satisfy every edge among themselves, and the MRT holds exactly their reservations within capacity.
function ModuloSchedule(G):
for II from MII upwards:
σ ← IterativeSchedule(G, II, budget = β · n)
if σ ≠ failure: return (II, σ − min σ)
function IterativeSchedule(G, II, budget):
compute HeightR at II; σ ← all unscheduled; prev ← all undefined; MRT ← empty
while some op is unscheduled and budget > 0:
x ← the unscheduled op with the largest HeightR (ties: smaller index)
Estart ← max(0, max over scheduled preds p (edge p→x, p ≠ x) of σ(p) + ℓ − II·d)
t ← the first cycle in [Estart, Estart + II − 1] where x's reservations fit the MRT
if none: # force a slot
t ← Estart if prev(x) undefined or Estart > prev(x) else prev(x) + 1
while x does not fit at t: # resource conflicts
evict, from an over-full (resource, row), the op with the smallest HeightR
for every scheduled succ y (edge x→y) with σ(y) < t + ℓ − II·d: evict y
for every scheduled pred p (edge p→x) with t < σ(p) + ℓ − II·d: evict p
σ(x) ← t; prev(x) ← t; reserve x in the MRT; budget ← budget − 1
return σ if every op is scheduled else failure
Swing modulo scheduling¶
Algorithm 23.6.10 (Swing modulo scheduling, after Llosa et al.)
- Input: as Algorithm 23.6.9.
- Output: \((\mathit{II}, \sigma)\) valid, with short lifetimes.
- Precondition: MII known; ASAP, ALAP, height and mobility computed on the graph without its back edges (distance \(> 0\)).
- Postcondition: valid; each op is placed as close as possible to its already placed neighbors.
- Invariant: when an op is scheduled, its already scheduled neighbors are only predecessors, only successors, or (for ops on recurrences) both, and its window respects all of them.
function SMS(G):
sets ← recurrences (strongly connected components with a cycle), by decreasing RecMII,
then the remaining ops as one set (connected pieces in order of discovery)
order ← []
for S in sets: # 1. ordering
if order = ∅: R ← {the op of S with the largest ASAP}; dir ← bottom-up
elif preds(order) ∩ S ≠ ∅: R ← preds(order) ∩ S; dir ← bottom-up
else: R ← succs(order) ∩ S; dir ← top-down
loop:
while R ≠ ∅:
if dir = top-down: v ← op of R with the largest height (ties: smallest mobility)
add succs(v) ∩ S not yet ordered to R
else: v ← op of R with the largest depth (ties: smallest mobility)
add preds(v) ∩ S not yet ordered to R
append v to order; remove v from R
switch dir; R ← (succs or preds, per the new dir, of order) ∩ S \ order
if R = ∅: break
for II from MII upwards: # 2. scheduling
clear MRT; ok ← true
for v in order:
P ← scheduled preds of v; Q ← scheduled succs of v
if P ≠ ∅ and Q = ∅: scan t from Early(v) up to Early(v) + II − 1
elif Q ≠ ∅ and P = ∅: scan t from Late(v) down to Late(v) − II + 1
elif both: scan t from Early(v) up to min(Late(v), Early(v) + II − 1)
else: scan t from ASAP(v) up to ASAP(v) + II − 1
place v at the first t that fits the MRT, else ok ← false; break
if ok: return (II, σ − min σ)
Early(v) = max over scheduled preds p of σ(p) + ℓ − II·d
Late(v) = min over scheduled succs s of σ(s) − ℓ + II·d
Modulo code generation¶
Definition 23.6.11 (Prologue, kernel, epilogue; lifetimes)
For a valid schedule with \(S\) stages and a trip count \(N \ge S\), the code is a sequence of \(N + S - 1\) groups of \(\mathit{II}\) cycles: \(S - 1\) prologue groups (group \(g\) holds the ops with stage \(\le g\)), the kernel group repeated \(N - S + 1\) times (all ops), and \(S - 1\) epilogue groups (group \(e\) holds the ops with stage \(> e\)). In every group an op issues at offset \(\sigma \bmod \mathit{II}\). The lifetime of a value is the number of cycles from its definition's issue to its last use's issue, and a value whose lifetime exceeds \(\mathit{II}\) has several instances live at once.
Algorithm 23.6.12 (Rotating-register allocation for a modulo schedule)
- Input: a valid modulo schedule; a rotating register file of size \(R\) whose names shift by one at the end of every group (logical \(q_x\) in group \(g\) is physical \((x - g) \bmod R\)).
- Output: a base register \(b_v\) for every loop-defined value \(v\); the renamed group code; preheader and exit copies.
- Precondition: each register is defined once in the body (simple loops); \(N \ge S\).
- Postcondition: the code executes every instance at its scheduled time with the right operands (Theorem 23.6.15).
- Invariant: the windows \([b_v - \mathrm{pad}_v, b_v + \mathrm{span}_v]\) of different values are disjoint.
for each value v defined by op d in stage s_d:
span(v) ← max( ⌊(σ(d) mod II + lat(d)) / II⌋, # the group its write lands in
max over uses u (distance δ) of δ + stage(u) − s_d, # how many groups later it is read
S − s_d if v is live out )
pad(v) ← max(0, s_d − 1) if v has a distance-1 use else 0
allocate windows consecutively: b_v ← cursor + pad(v); cursor ← b_v + span(v) + 1 (fail if > R)
rename: the definition writes q[b_v]; a use by u with distance δ reads q[b_v + δ + stage(u) − s_d]
memory X[i + c] in op u becomes X[i + c − stage(u)] (i = the group number)
preheader: q[b_v + 1 − s_d] ← initial value, for every v with a distance-1 use
exit: r ← q[b_v + S − s_d] for every live-out register r defined by v
With modulo variable expansion instead of rotating registers, you unroll the kernel \(u = \max_v \lceil \mathrm{lifetime}(v)/\mathit{II} \rceil\) times and give each copy of \(v\) its own register. The copies then play the role of the rotation, at the cost of \(u\) copies of the kernel and a remainder loop when \(N - S + 1\) is not a multiple of \(u\) [Lam88].
3. Worked examples¶
Modulo-schedule bounds (ResMII and RecMII)¶
The running loop's graph (Definition 23.6.1): a→c (3, 0), b→c (3, 0), c→e (3, 0), d→e (3, 0), e→f (1, 0) and e→d (1, 1), because d reads r6 before e defines it.
| resource | uses per iteration | capacity | \(\lceil U/\mathrm{cap} \rceil\) |
|---|---|---|---|
| issue | 6 | 2 | 3 |
| mem (a, b, f) | 3 | 1 | 3 |
| mul (c, d) | 2 | 1 | 2 |
| alu (e) | 1 | 2 | 1 |
\(\mathrm{ResMII} = 3\). There is one cycle, d → e → d, with \(\ell = 3 + 1 = 4\) and \(d = 0 + 1 = 1\), so \(\mathrm{RecMII} = 4\) and \(\mathrm{MII} = 4\). Algorithm 23.6.4 confirms it: at \(\mathit{II} = 3\) the cycle has weight \(4 - 3 = 1 > 0\), and at \(\mathit{II} = 4\) it has weight 0. No schedule can start iterations faster than every 4 cycles: each \(x_k\) needs a multiply (3) and an add (1) after \(x_{k-1}\).
Try it
./course drill mii --seed 3 --solution computes ResMII (per resource), RecMII (per cycle) and
MII for a random loop; ./course drill modulo-table --seed 3 --solution then runs Algorithm 23.6.9.
Iterative modulo scheduling¶
At \(\mathit{II} = 4\), HeightR is a 8, b 8, c 5, d 5, e 2, f 1 (for instance \(\mathrm{HeightR}(d) = 3 + \mathrm{HeightR}(e) = 5\) and \(\mathrm{HeightR}(e) = \max(1 - 4 + 5,\ 1 + 1,\ 1) = 2\)). One row per step of Algorithm 23.6.9:
| step | op | Estart | slot scan | placed at | evicted | why |
|---|---|---|---|---|---|---|
| 1 | a | 0 | row 0 free | 0 | — | |
| 2 | b | 0 | row 0: mem taken by a | 1 | — | |
| 3 | c | 4 (a + 3, b + 3) | row 0: issue has a, room for 1 | 4 | — | |
| 4 | d | 0 (its pred e is unscheduled) | row 0: issue full (a, c) | 1 | — | |
| 5 | e | 7 (c + 3) | row 3 free | 7 | d | e→d: \(\sigma(d) = 1 < 7 + 1 - 4 = 4\) |
| 6 | d | 4 (e + 1 − 4) | row 0 full; row 1 ok | 5 | e | d→e: \(\sigma(e) = 7 < 5 + 3 = 8\) |
| 7 | e | 8 (d + 3) | rows 0, 1 full; row 2 ok | 10 | d | e→d: \(5 < 10 + 1 - 4 = 7\) |
| 8 | d | 7 | row 3 ok | 7 | — | d→e: \(10 \ge 7 + 3\) ✓ |
| 9 | f | 11 (e + 1) | row 3: issue has d, room | 11 | — |
Nine steps, within the budget of \(3 \cdot 6 = 18\). The result is \(\sigma\) = a 0, b 1, c 4, d 7, e 10, f 11 at \(\mathit{II} = 4 = \mathrm{MII}\), with \(S = \lfloor 11/4 \rfloor + 1 = 3\) stages. The MRT (issue part):
| row | ops (stage) | mem | mul |
|---|---|---|---|
| 0 | a (0), c (1) | a | c |
| 1 | b (0) | b | — |
| 2 | e (2) | — | — |
| 3 | d (1), f (2) | f | d |
The evictions in steps 5–7 are the point of IMS: a greedy modulo list scheduler would have kept d at 1 and produced a schedule that violates the recurrence.
Swing modulo scheduling¶
Ordering (Algorithm 23.6.10) at \(\mathit{II} = 4\): the only recurrence set is {d, e}. With ASAP a 0, b 0, c 3, d 0, e 6, f 7 on the graph without the back edge, the first set starts bottom-up at e, the op with the largest ASAP, then its predecessor d. For the remaining set {a, b, c, f}, predecessors of the ordered ops come first: c (bottom-up), then c's predecessors a and b. Then the direction swings to top-down for the successor f. Order: e, d, c, a, b, f. Scheduling:
| op | scheduled neighbors | window | placed |
|---|---|---|---|
| e | none | from ASAP 6 | 6 (row 2) |
| d | succ e (3, 0) and pred e (1, 1) | Early \(= 6 + 1 - 4 = 3\), Late \(= 6 - 3 = 3\) | 3 (row 3) |
| c | succ e | Late \(= 3\), scan down: row 3 mul taken by d; row 2 ok | 2 |
| a | succ c | Late \(= -1\), scan down: row 3 (issue d, room) | −1 |
| b | succ c | Late \(= -1\): row 3 full, row 2 full (e, c), row 1 | −3 |
| f | pred e | Early \(= 7\): row 3 full (d, a); row 0 | 8 |
Normalized (\(+3\)): b 0, a 2, c 5, d 6, e 9, f 11, again at \(\mathit{II} = 4\) with 3 stages, and without any backtracking. Both schedules pass the lab's checker. Each op sits next to its neighbor: c three cycles after a, e three after c.
Modulo code generation¶
The lab's reference solution (ch23-sched --algo=modulo) generates this code for the IMS schedule. Stages: a, b in 0; c, d in 1; e, f in 2. Windows (Algorithm 23.6.12): a [0, 1], b [2, 3], c [4, 5], d [6, 7], and e [9, 10] with one register of padding (q8), because e has a distance-1 use (by d) and is in stage 2.
loop run ii 4 resmii 3 recmii 4 stages 3
sigma a 0 | b 1 | c 4 | d 7 | e 10 | f 11 (one line each in the real output)
preheader
q8 = mov r6 # x_{-1}: b_e + 1 − s_e = 9 + 1 − 2
prologue 0
@0 a: q0 = load A[i]
@1 b: q2 = load B[i]
prologue 1
@0 a: q0 = load A[i]
@0 c: q4 = mul q1, q3 # a, b defined one group earlier: offset +1
@1 b: q2 = load B[i]
@3 d: q6 = mul q9, r9 # x of the previous iteration: 9 + 1 + 1 − 2 = 9
kernel
@0 a: q0 = load A[i]
@0 c: q4 = mul q1, q3
@1 b: q2 = load B[i]
@2 e: q9 = add q7, q5
@3 d: q6 = mul q9, r9
@3 f: store C[i-2], q9 # f is in stage 2: its iteration is i − 2
epilogue 0 … epilogue 1 # stages > 0, then > 1
exit
r6 = mov q10 # b_e + S − s_e = 9 + 3 − 2
end
In prologue 1 (group 1), d of iteration 0 reads q9, which in group 1 is physical \((9 - 1) \bmod 64 = 8\): the preheader's copy of r6. In the kernel, d reads q9 in the same group in which e writes q9, but e issues at offset 2 and its result lands at offset 3, when d reads it. That is the edge e→d with \(\ell = 1\), \(d = 1\), satisfied with equality (\(\sigma(d) = 7 = 10 + 1 - 4\)). The lab's checker simulates this code for trip counts 3 to 10 against the sequential loop.
4. Invariants and correctness¶
Modulo-schedule bounds (ResMII and RecMII)¶
Theorems 23.6.5–23.6.7 are the correctness statements: every schedule has \(\mathit{II} \ge \mathrm{MII}\), a valid \(\sigma\) gives a valid overlapped execution, and the computed RecMII is exactly the smallest dependence-feasible \(\mathit{II}\). \(\mathrm{MII}\) is a lower bound, not always achievable. With resources and recurrences both tight, the smallest feasible \(\mathit{II}\) can be larger (the lab's loops-hard.txt corpus: 30 loops where IMS needs \(\mathrm{MII} + 1\) or more).
Iterative modulo scheduling¶
Proposition 23.6.13 (IMS returns only valid schedules)
IterativeSchedule maintains its invariant, so a schedule it returns is valid; each call stops
after at most budget placements. ModuloSchedule tries finitely many \(\mathit{II}\) when the
search is capped (the lab caps it at \(\mathrm{MII} + \sum_x (\mathrm{lat}(x) + \mathrm{occ}(x))\) and
reports failure beyond; the cap was never reached on the lab corpus).
Proof (termination of the uncapped search: see [Rau94])
Invariant. Placing \(x\) at \(t\) first evicts ops until \(x\) fits the MRT, then evicts every scheduled successor or predecessor whose edge with \(x\) is violated. Edges between two ops that both stay scheduled were satisfied before and are untouched, so after the placement every edge among scheduled ops holds, and the MRT holds exactly the scheduled ops' reservations within capacity. If all ops are scheduled, this is Definition 23.6.2. Termination of a call: each iteration of the loop decrements the budget. Outer loop: with the cap, at most \(\sum_x (\mathrm{lat}(x) + \mathrm{occ}(x)) + 1\) values of \(\mathit{II}\) are tried.
Swing modulo scheduling¶
Proposition 23.6.14 (SMS returns only valid schedules)
Every op placed by Algorithm 23.6.10 satisfies all edges to already placed ops and fits the MRT, so a completed pass yields a valid schedule.
Proof sketch (full treatment: [LGAV96])
The window of each case is exactly the set of times allowed by the placed neighbors. \(t \ge \mathrm{Early}(v)\) satisfies every edge from a placed predecessor, and \(t \le \mathrm{Late}(v)\) every edge to a placed successor, by Definition 23.6.2. A scan over \(\mathit{II}\) consecutive cycles covers every MRT row once, so if no row fits, none will in a longer scan; the pass then fails and \(\mathit{II}\) grows. The ordering guarantees that, except for ops on recurrences, a node never has both predecessors and successors placed, which is what keeps the windows nonempty in practice. Llosa et al. prove that the ordering realizes this property for acyclic parts.
Modulo code generation¶
Theorem 23.6.15 (Prologue, kernel and epilogue run every instance once, correctly named)
For \(N \ge S\), the group sequence of Definition 23.6.11 issues instance \(k\) of op \(x\) exactly once, at cycle \(\sigma(x) + k\,\mathit{II}\), for \(0 \le k < N\). With the renaming of Algorithm 23.6.12, every instance reads the instance of each operand that the sequential loop reads.
Proof
Instances. Instance \(k\) of \(x\) with stage \(s\) must issue in group \(g = k + s\) at offset \(\sigma(x) \bmod \mathit{II}\), i.e. at cycle \(g\,\mathit{II} + \sigma(x) \bmod \mathit{II} = \sigma(x) + k\,\mathit{II}\). Group \(g < S - 1\) is prologue \(g\) and contains \(x\) iff \(s \le g\) iff \(k = g - s \ge 0\). Groups \(S - 1 \le g \le N - 1\) are kernels, which contain every op, with \(k = g - s \in [0, N-1]\) because \(0 \le s \le S - 1\). Group \(g = N + e\) is epilogue \(e\) and contains \(x\) iff \(s > e\) iff \(k = N + e - s < N\). Every pair \((x, k)\) with \(0 \le k < N\) has exactly one \(g = k + s\) in \([0, N + S - 2]\), so it is issued exactly once, and no other instances are issued.
Names. Instance \(k\) of \(v\) is written, at issue, to physical \((b_v - (k + s_d)) \bmod R\). A use by \(u\) with distance \(\delta\), in iteration \(k' = k + \delta\), issues in group \(k + \delta + s_u\) and reads logical \(b_v + \delta + s_u - s_d\), which is physical \((b_v + \delta + s_u - s_d - k - \delta - s_u) = (b_v - k - s_d) \bmod R\): the same register. It is not overwritten in between: another instance writing the same physical register would have to belong to a value whose window meets \([b_v, b_v + \mathrm{span}_v]\) (excluded by disjointness), or to \(v\) itself \(R\) groups later (excluded since \(\mathrm{span}_v < R\)). The write has landed because the schedule satisfies the edge. For \(k' = 0\) and \(\delta = 1\), the physical register is \((b_v + 1 - s_d) \bmod R\), which the preheader initializes; the padding keeps instances of other values written in groups \(0 .. s_d - 2\) out of it. At the exit, after \(N + S - 1\) rotations, logical \(b_v + S - s_d\) names the register of instance \(N - 1\).
The kernel alone is not the loop
Running only the kernel \(N\) times computes garbage: in the first \(S - 1\) kernel iterations the
later stages work on iterations \(-1, -2, \dots\) that never started, and at the end the last
iterations' later stages never run. Either emit a prologue and an epilogue, or use kernel-only
code with stage predicates (IA-64's br.ctop turns stages on and off with rotating predicates).
Either way, loops with \(N < S\) need a separate unpipelined version, as LLVM's AArch64 output in §7
shows.
5. Complexity¶
Let \(n\) be the ops, \(e\) the edges, \(\rho\) the reservation-table size, \(\beta\) the budget ratio, and \(\Delta = \mathit{II}_{\text{final}} - \mathrm{MII}\).
| Technique | Time | Space | Notes |
|---|---|---|---|
| ResMII | \(O(n\rho)\) | \(O(\lvert\mathcal{R}\rvert)\) | exact |
| RecMII (Alg. 23.6.4) | \(O(n^3)\) per candidate \(\mathit{II}\), \(O(n^3 \cdot \mathrm{RecMII})\); \(O(n^3 \log \ell_{\max})\) with binary search | \(O(n^2)\) | enumerating elementary cycles instead is exponential in the worst case |
| IMS (Alg. 23.6.9) | \(O(\beta n \cdot (n + \mathit{II}\rho))\) per \(\mathit{II}\), times \((\Delta + 1)\) | \(O(n + \mathit{II}\,\lvert\mathcal{R}\rvert)\) | Rau reports \(\beta = 3\) is enough in practice |
| SMS (Alg. 23.6.10) | ordering \(O(n + e)\) after SCCs; one pass \(O(n \cdot \mathit{II} \rho)\) per \(\mathit{II}\) | \(O(n + e)\) | no backtracking |
| Code generation (Alg. 23.6.12) | \(O(S \cdot n)\) code, \(O(n + \text{uses})\) allocation | \(\sum_v (\mathrm{span}_v + 1)\) rotating registers | MVE instead: \(u\) kernel copies |
Justification. Floyd–Warshall is \(\Theta(n^3)\) per test, and positivity is monotone in \(\mathit{II}\), so a binary search over \([1, \sum \ell]\) needs \(O(\log)\) tests. Each IMS step scans \(\mathit{II}\) rows of the MRT with \(\rho\) checks and inspects the op's edges. There are at most \(\beta n\) steps. SMS places each op once per pass. The code has \(2(S - 1) + 1\) groups, each with at most \(n\) ops.
Pathological family (cycles). A body whose dependence graph is complete (every op feeds every other at distance 1) has \(\sum_{k=1}^{n} \binom{n}{k}(k-1)!\) elementary cycles, more than \((n-1)!\). That is why production code either caps cycle enumeration (LLVM's findCircuits runs Johnson's circuit algorithm and stops a search after Circuits::MaxPaths, 5, circuits) or computes RecMII with the \(\mathit{II}\)-search of Algorithm 23.6.4. Pathological family (IMS). Resource-tight and recurrence-tight at the same time: the lab's loops-hard.txt has 30 such random loops where IMS needs \(\mathrm{MII} + 1\) or more. Over the lab's full corpus of 150 loops, IMS reaches MII on 120 (ch23-compare, §8).
6. Variants and refinements¶
Modulo-schedule bounds (ResMII and RecMII)¶
- Minimum cycle ratio algorithms (Karp 1978, Howard's policy iteration): compute \(\max_C \ell(C)/d(C)\) directly as a rational, instead of searching \(\mathit{II}\). Faster for large bodies, but more code.
- Fractional II by unrolling: if \(\mathrm{MII}\) is bounded by \(\lceil 7/2 \rceil = 4\), unrolling twice allows \(\mathit{II} = 7\) for two iterations (3.5 per iteration). Code grows, and
pragma unrollin LLVM feeds this.
Iterative modulo scheduling¶
- Eviction policies [Rau94]: evict all conflicting ops, or only the lowest priority. Rau evicts all ops in conflicting slots. The lab evicts the lowest-HeightR op per over-full row. Both terminate with the budget.
- Optimal modulo scheduling by ILP (Eichenberger and Davidson 1997; Altman et al. 1995): exact, and practical only for small loops. It is used to measure how far heuristics are from optimal.
Swing modulo scheduling¶
- Register-pressure filtering (LLVM
registerPressureFilter,-pipeliner-register-pressure): reject schedules whose pressure exceeds the register file. More robust than SMS's lifetime ordering alone. - Window scheduling (LLVM
WindowScheduler,-window-sched=on|force, LLVM 19+): search over rotations of an ordinary list schedule of the body. It is a cheaper alternative when SMS fails, and is used on Hexagon.
Modulo code generation¶
- Kernel-only code with predicates (Cydra 5, IA-64): rotating predicates switch stages on and off, so there is no prologue or epilogue. It needs hardware support.
- Peeling code generator (LLVM
PeelingModuloScheduleExpander,-pipeliner-experimental-cg) and MVE expander (ModuloScheduleExpanderMVE,-pipeliner-mve-cg, used by AArch64): different trade-offs between code size, register copies and the handling of short trip counts.
7. In real compilers¶
Modulo-schedule bounds (ResMII and RecMII)¶
LLVM's SwingSchedulerDAG::calculateResMII delegates to ResourceManager::calculateResMII (DFA-based for Hexagon), and SwingSchedulerDAG::calculateRecMII walks the circuits found by findCircuits (llvm/lib/CodeGen/MachinePipeliner.cpp) [LLVM-Pipeliner]. Its RecMII computation assumes every circuit has distance 1 (the code says unsigned Distance = 1), which is exact for the register recurrences it pipelines. GCC computes the same bounds in sms_schedule (gcc/modulo-sched.cc, res_MII, and the recurrence MII of the dependence graph) [GCC-sms].
The same recurrence, three MIIs
Reproduce (clang 23.1.2, llc 23.1.2; -pipeliner-max-mii=1 makes the pipeliner report its MII
and stop):
cat > rec.c <<'EOF'
void rec(int n, int s, const int *restrict a, const int *restrict b, int *restrict c) {
int x = 0;
for (int i = 0; i < n; i++) {
x = x * s + a[i] * b[i];
c[i] = x;
}
}
EOF
for t in "hexagon hexagonv68 " "aarch64-linux-gnu neoverse-v2 -aarch64-enable-pipeliner" \
"powerpc64le-linux-gnu pwr9 -ppc-enable-pipeliner"; do
set -- $t; echo "== $1 $2"
clang-23 --target=$1 -mcpu=$2 -O2 -fno-unroll-loops -fno-vectorize -S -emit-llvm rec.c -o rec-$2.ll
for x in "-pipeliner-max-mii=1" ""; do
llc -O2 -mtriple=$1 -mcpu=$2 $3 $x -pass-remarks=pipeliner -pass-remarks-analysis=pipeliner \
rec-$2.ll -o /dev/null
done
done 2>&1
Output (complete):
== hexagon hexagonv68
remark: <unknown>:0:0: Minimal Initiation Interval too large: 2 > 1.Refer to -pipeliner-max-mii.
remark: <unknown>:0:0: Schedule found with Initiation Interval: 2, MaxStageCount: 1
remark: <unknown>:0:0: Pipelined succesfully!
== aarch64-linux-gnu neoverse-v2
remark: <unknown>:0:0: Minimal Initiation Interval too large: 5 > 1.Refer to -pipeliner-max-mii.
remark: <unknown>:0:0: Schedule found with Initiation Interval: 5, MaxStageCount: 1
remark: <unknown>:0:0: Pipelined succesfully!
== powerpc64le-linux-gnu pwr9
remark: <unknown>:0:0: Minimal Initiation Interval too large: 6 > 1.Refer to -pipeliner-max-mii.
remark: <unknown>:0:0: Schedule found with Initiation Interval: 6, MaxStageCount: 1
remark: <unknown>:0:0: Pipelined succesfully!
What to notice: the loop is the running loop in C, and the recurrence \(x \to x \cdot s + \dots\)
is the d → e cycle. Each target's MII is \(\max(\mathrm{ResMII}, \mathrm{RecMII})\) under its own machine
model: Hexagon's multiply-accumulate r5 += mpyi(...) makes the recurrence short (MII 2), while the
multiply and add latencies of Neoverse V2 and POWER9 make it 5 and 6. In all three the pipeliner
reaches MII (Theorem 23.6.5 says it cannot do better). MaxStageCount: 1 is LLVM's zero-based count: two stages.
Iterative modulo scheduling¶
LLVM does not implement Rau's IMS, but its outer loop is the same: SwingSchedulerDAG::schedulePipeline tries \(\mathit{II} = \mathrm{MII}, \mathrm{MII} + 1, \dots\) up to MAX_II = MII + pipeliner-ii-search-range (default 10), and -pipeliner-force-ii pins it [LLVM-Pipeliner]. IMS itself is implemented in research compilers (Trimaran/Elcor) and in several production VLIW and DSP compilers. It is the lab's algorithm.
Below MII there is no schedule
Reproduce (llc 23.1.2; rec-hexagonv68.ll from the previous box):
for ii in 1 2; do echo "== II forced to $ii"
llc -O2 -mtriple=hexagon -mcpu=hexagonv68 -pipeliner-force-ii=$ii \
-pass-remarks=pipeliner -pass-remarks-analysis=pipeliner rec-hexagonv68.ll -o /dev/null
done 2>&1
Output (complete):
== II forced to 1
remark: <unknown>:0:0: Unable to find schedule
== II forced to 2
remark: <unknown>:0:0: Schedule found with Initiation Interval: 2, MaxStageCount: 1
remark: <unknown>:0:0: Pipelined succesfully!
What to notice: at \(\mathit{II} = 1\) the search fails, as Theorem 23.6.5 predicts for any \(\mathit{II} < \mathrm{MII} = 2\). At \(\mathit{II} = 2\) it succeeds. An iterative scheduler's outer loop is exactly this search, started at MII.
Swing modulo scheduling¶
MachinePipeliner (llvm/lib/CodeGen/MachinePipeliner.cpp: SwingSchedulerDAG::computeNodeOrder, SMSchedule::insert, SwingSchedulerDAG::schedulePipeline) implements SMS and runs by default on Hexagon, and with -aarch64-enable-pipeliner, -ppc-enable-pipeliner, -riscv-enable-pipeliner or -enable-pipeliner elsewhere [LLVM-Pipeliner]. GCC's -fmodulo-sched (gcc/modulo-sched.cc, sms_schedule, order_nodes_of_sccs) is SMS too, and it needs a counted-loop ("doloop") instruction, which x86 lacks: on x86-64, gcc-14 -O2 -fmodulo-sched -fdump-rtl-sms reports SMS doloop_register_get failed for rec.c [GCC-sms].
SMS output on Hexagon: prologue, kernel, epilogue
Reproduce (llc 23.1.2; rec-hexagonv68.ll from the first box):
llc -O2 -mtriple=hexagon -mcpu=hexagonv68 rec-hexagonv68.ll -o - \
| sed -n '/^.LBB0_1:/,/^.Lfunc_end0/p' | grep -v '^\s*$\|p2align'
Output (complete):
.LBB0_1:
{
r7 = add(r0,#-1)
p0 = cmp.gtu(r0,#1)
r5 = #0
r0 = memw(r2++#4)
}
{
loop0(.LBB0_2,r7)
if (!p0) jump:nt .LBB0_3
r6 = memw(r3++#4)
}
.LBB0_2: // %.preheader
// =>This Inner Loop Header: Depth=1
{
r5 = mpyi(r6,r0)
r7 = r5
r0 = memw(r2++#4)
r6 = memw(r3++#4)
}
{
r5 += mpyi(r7,r1)
memw(r4++#4) = r5.new
} :endloop0
.LBB0_3:
{
r0 = mpyi(r6,r0)
}
{
r0 += mpyi(r5,r1)
memw(r4++#4) = r0.new
}
{
r31:30 = dealloc_return(r30):raw
}
.Lfunc_end0:
What to notice: the kernel (.LBB0_2, two packets, \(\mathit{II} = 2\)) multiplies and
accumulates for iteration \(k\) while it loads a[k+1] and b[k+1] for the next one: two stages.
The prologue (.LBB0_1) issues the first iteration's loads, the epilogue (.LBB0_3) finishes the
last iteration's arithmetic and store (Definition 23.6.11). The loop runs \(n - 1\) times
(loop0(.LBB0_2, r7) with r7 = n - 1). The copy r7 = r5 keeps the old value of x alive
across the redefinition, which is the register-lifetime problem that modulo variable expansion
and rotating registers solve.
Modulo code generation¶
ModuloScheduleExpander (llvm/lib/CodeGen/ModuloSchedule.cpp) generates prologues, the kernel and epilogues with phi-based renaming. ModuloScheduleExpanderMVE in the same file implements modulo variable expansion (used by AArch64), and PeelingModuloScheduleExpander peels stages [LLVM-ModuloSchedule]. Itanium compilers (GCC's IA-64 back end, Intel's) used rotating registers and br.ctop.
Modulo variable expansion on AArch64
Reproduce (llc 23.1.2; rec-neoverse-v2.ll from the first box):
llc -O2 -mtriple=aarch64-linux-gnu -mcpu=neoverse-v2 -aarch64-enable-pipeliner -pipeliner-mve-cg \
rec-neoverse-v2.ll -o - | sed -n '/^rec:/,/^.Lfunc_end0/p' | grep -v '^\s*$\|p2align\|cfi\|^\s*//'
Output (complete):
rec: // @rec
cmp w0, #1
b.lt .LBB0_6
mov w8, w0
subs x10, x8, #1
mov w9, wzr
cset x11, eq
subs x10, x10, #1
cinc x10, x11, eq
cmp x10, #0
b.ne .LBB0_5
ldr w10, [x2], #4
ldr w11, [x3], #4
mul w9, w9, w1
subs x8, x8, #1
madd w9, w11, w10, w9
.LBB0_3: // =>This Inner Loop Header: Depth=1
ldr w11, [x2], #4
ldr w12, [x3], #4
mov x10, x8
subs x8, x8, #1
str w9, [x4], #4
mul w9, w9, w1
madd w9, w12, w11, w9
cset x11, eq
cmp x11, #0
b.eq .LBB0_3
subs x10, x10, #1
str w9, [x4], #4
cset x10, eq
cmp x10, #0
b.ne .LBB0_6
.LBB0_5: // =>This Inner Loop Header: Depth=1
ldr w10, [x2], #4
ldr w11, [x3], #4
mul w9, w9, w1
subs x8, x8, #1
madd w9, w11, w10, w9
str w9, [x4], #4
b.ne .LBB0_5
.LBB0_6:
ret
.Lfunc_end0:
What to notice: the MVE expander emits a trip-count check (subs … cinc … b.ne .LBB0_5),
a prologue that computes the first x, a kernel .LBB0_3 whose store writes the previous
iteration's x (stage 1) while the multiply-add computes the current one (stage 0), and an
epilogue store. Short trip counts go to the original loop .LBB0_5, because the pipelined version
needs \(N \ge S\) (the pitfall above). With \(u = 1\) no kernel unrolling was necessary here: every
lifetime fits in one \(\mathit{II}\).
8. Comparison¶
| 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 |
Lab numbers from build/<preset>/bin/ch23-compare tests/ch23/Inputs/blocks.txt tests/ch23/Inputs/loops.txt tests/ch23/Inputs/loops-hard.txt: 150 loops, sum of II 985 against sum of MII 944, II = MII on 120, 2.22 stages on average.
Choose IMS when minimum \(\mathit{II}\) matters most and registers are plentiful (rotating files, VLIW DSPs). Choose SMS in a general-purpose compiler, where register pressure decides whether pipelining helps at all. Choose rotating registers when the ISA has them. Otherwise, choose MVE or a phi-based expander and guard short trip counts with the original loop.
9. Assessment¶
- Quiz:
resmii-running(number),recmii-running(number),ims-evictions(sequence),ims-sigma(mapping),sms-order(sequence),mve-unroll(number),rotating-offset(number),find-recmii-distance(number: find it in LLVM). Tagsmii,ims,sms,modulo-codegen. - Drills:
./course drill mii(ResMII per resource, RecMII, MII),./course drill modulo-table(run IMS at MII: \(\sigma\), stages, MRT rows). SMS ordering and register allocation for the kernel are exercised by the lab (E5) and the quiz. - Flashcards: tags
mii,ims,sms,modulo-codegen. - Lab: E4 (MII and IMS) and E5 (prologue/kernel/epilogue with rotating registers) in exercises; tests
ch23.Modulo.*.
References¶
See the chapter references.