Lesson 23.3 — List scheduling: top-down, bottom-up and register-pressure-aware¶

Techniques: top-down (cycle-driven) list scheduling; bottom-up list scheduling (by reversal); register-pressure-aware list scheduling · Lab: labs/ch23-sched E1–E3 (td-cp, td-succ, bu-cp, bu-succ, ★ pressure) · Prerequisites: Lesson 23.2 (DAGs, heights, the running block) · Time: 5–6 hours

Finding a shortest valid schedule of a block is NP-hard as soon as the machine has more than one unit or latencies differ (Theorem 23.3.4). Yet every production compiler schedules every block, in linear-ish time, with results close to the lower bound. The method they share is list scheduling: walk through the cycles, keep a list of operations whose predecessors are done, and each cycle start the most urgent ones that fit. The "most urgent" test is a priority function, and that is where schedulers differ: the height of Lesson 23.2, the number of successors, the register pressure. The direction differs too. Top-down schedulers fill cycles from the first. Bottom-up schedulers (LLVM's default for most targets before register allocation) fill them from the last. This lesson gives all three variants in full, proves Graham's classic guarantee that any list schedule is within a factor $2 - 1/m$ of optimal, and traces them on the running block.

1. Problem and motivation¶

Top-down list scheduling¶

Given a block, its dependence DAG and a machine model, find a valid schedule (Definition 23.2.4) of minimum length. List scheduling comes from the scheduling of tasks on parallel processors. Graham analyzed it in 1966 and 1969 and showed that it can never be worse than twice the optimum [Gra66, Gra69]. Compiler writers adopted it for microcode compaction [LDSM80] and then for pipelined RISC processors. Gibbons and Muchnick's top-down scheduler for the HP Precision Architecture [GM86] and Warren's for the IBM RS/6000 [War90] are the classic examples. GCC's haifa-sched.cc is a top-down list scheduler to this day [GCC-haifa]. pebblec gets its schedules from LLVM's MachineScheduler (Lesson 23.7), which can run top-down, bottom-up or both. You implement all of them in the lab.

Bottom-up list scheduling¶

A top-down scheduler decides the order of the first instructions first, and those decisions are made with the least information about what follows. A bottom-up scheduler starts at the end of the block and works backwards. Two advantages come out of this. First, the last use of a value is scheduled before its definition, so the scheduler knows when a register becomes free. Second, operations feeding the block's results are placed close to where they are needed, which keeps live ranges short. SelectionDAG's schedulers are bottom-up (Ch 21, Lesson 21.5), and LLVM's GenericScheduler defaults to scheduling from both ends and meeting in the middle.

Register-pressure-aware list scheduling¶

A scheduler that races along the critical path starts all loads early, and all their results are live at once. If they don't fit in the registers, the allocator spills, and the spill code can cost more than the latency the scheduler hid. Goodman and Hsu made the scheduler watch the number of live values and switch priorities when it approaches the register count [GH88]. Minimizing registers exactly is itself NP-complete for DAGs [Set75], although for expression trees Sethi and Ullman's numbering gives the optimum [SU70]. Every production pre-allocation scheduler tracks pressure today. LLVM's GenericScheduler has "excess" and "critical-max" pressure heuristics, and SelectionDAG's default list-burr is "bottom-up register reduction" (Lesson 23.7).

2. Definitions and algorithms¶

Definition 23.3.1 (Ready operation, priority function, list schedule)

During a top-down construction that has placed some operations, an unplaced operation $v$ is ready at cycle $c$ if every predecessor $u$ is placed with $t(u) + \ell(u, v) \le c$. A priority function is a total order $\prec$ on operations (the lab encodes it as sort keys, smaller first). A list schedule is one produced by Algorithm 23.3.2 for some priority.

The lab's priorities (SPEC R3–R4), with $h$ the height and $\mathrm{idx}$ the position in the block:

name	key (sorted ascending)	idea
`cp` (critical path)	$(-h(v), \mathrm{idx}(v))$	longest remaining path first (Hu's "level")
`succ` (successor count)	$(-\lvert \mathrm{succs}(v) \rvert, -h(v), \mathrm{idx}(v))$	unlock the most work first

Top-down list scheduling¶

Algorithm 23.3.2 (Cycle-driven top-down list scheduling)

Input: a DAG $G = (V, E, \ell)$ with node latencies and reservation tables; a machine model; a priority (sort keys).
Output: issue cycles $t(v)$ for every $v$.
Precondition: $\ell \ge 0$ on every edge; every reservation table fits an empty machine.
Postcondition: $t$ is a valid schedule (Theorem 23.3.3).
Invariant: (I1) the placement so far is resource-feasible and satisfies every edge between placed operations; (I2) at the end of cycle $c$, no unplaced operation that is ready at $c$ fits at $c$.

function TopDown(G, keys):
    c ← 0
    while some v is unplaced:
        loop:
            cand ← { v unplaced | Ready(v, c) and Fits(v, c) }      # Fits: Algorithm 23.1.4
            if cand = ∅: break
            v ← the element of cand with the smallest key
            Place(v, c); t(v) ← c                                   # may make zero-latency
        c ← c + 1                                                   #   successors ready at c

function Ready(v, c):
    return every predecessor u of v is placed and t(u) + ℓ(u, v) ≤ c

The inner loop re-evaluates readiness after every placement. So a successor across a zero-latency (anti) edge can start in the same cycle as its predecessor, as the ISA's read-at-issue semantics allows. The trace in §3 shows it happening.

Theorem 23.3.3 (Graham's bound)

Consider the special machine $P \mid \mathrm{prec} \mid C_{\max}$: one unit class with $m$ identical units, issue width $W \ge m$, every class non-pipelined ($\mathrm{occ} = \mathrm{lat}$), and only true edges ($\ell(u, v) = \mathrm{lat}(u)$). Every schedule produced by Algorithm 23.3.2, for any priority, has length

\[ L \ \le\ \frac{1}{m}\sum_{v} \mathrm{lat}(v) + \Big(1 - \frac{1}{m}\Big)\mathrm{CP}(G) \ \le\ \Big(2 - \frac{1}{m}\Big)\mathrm{OPT}. \]

Proof

Call a cycle $c \in [0, L)$ full if all $m$ units are occupied at $c$ in the final schedule, and partial otherwise. We build a chain $v_1, v_2, \dots, v_k$, a path of $G$ read backwards, such that every partial cycle lies in an execution interval $I_i = [t(v_i), t(v_i) + \mathrm{lat}(v_i))$.

Let $v_1$ be an operation with $t(v_1) + \mathrm{lat}(v_1) = L$. Given $v_i$: if it has no predecessors, stop; otherwise let $v_{i+1}$ be a predecessor with the largest completion time $f = t(v_{i+1}) + \mathrm{lat}(v_{i+1})$. We claim no cycle $c$ with $f \le c < t(v_i)$ is partial. At such a $c$ every predecessor $u$ of $v_i$ was placed (it started before $f \le c$) and $t(u) + \mathrm{lat}(u) \le f \le c$, so $v_i$ was ready at $c$. If $c$ were partial, some unit would be free at $c$, already when the inner loop for cycle $c$ ended (later placements start after $c$ and never occupy it). At that moment it would also be free in each later cycle $c + k$: every operation placed so far that occupies a unit at $c + k$ was placed at a cycle $\le c$ (placements happen in cycle order) and its occupancy is contiguous from its issue, so it also occupies $c$. Hence the usage at $c + k$ is at most the usage at $c$, which is below $m$. The issue slots are not full either, because every operation issued at $c$ occupies a unit at $c$ and fewer than $m \le W$ units are busy. So $v_i$ was ready and fit at $c$ when the inner loop ended, which contradicts invariant (I2). The same argument with $f = 0$ shows that no cycle before $t(v_k)$ is partial when $v_k$ has no predecessors.

So every partial cycle lies in some $I_i$. The intervals are disjoint because $t(v_i) \ge t(v_{i+1}) + \mathrm{lat}(v_{i+1})$, and $v_k \to \dots \to v_1$ is a path, so the number of partial cycles is $\lvert P \rvert \le \sum_i \mathrm{lat}(v_i) \le \mathrm{CP}(G)$. Each partial cycle lies in some $I_i$ and therefore has at least one busy unit, so counting occupied unit-cycles gives $\sum_v \mathrm{lat}(v) \ge m (L - \lvert P \rvert) + \lvert P \rvert$, i.e. $mL \le \sum_v \mathrm{lat}(v) + (m - 1)\lvert P \rvert \le \sum_v \mathrm{lat}(v) + (m-1)\mathrm{CP}(G)$. Finally $\mathrm{OPT} \ge \sum_v \mathrm{lat}(v) / m$ (Corollary 23.2.13) and $\mathrm{OPT} \ge \mathrm{CP}(G)$ (Theorem 23.2.12), so $L \le \mathrm{OPT} + (1 - 1/m)\mathrm{OPT}$.

Theorem 23.3.4 (Optimal scheduling is NP-hard)

Deciding whether a DAG of unit-latency operations has a schedule of length $\le T$ on $m$ identical units is NP-complete when $m$ is part of the input [Ull75; GJ79, SS9]. Finding a shortest order for a single-issue pipeline with arbitrary latencies (interlocks) is NP-complete as well [HG83]. It is polynomial for $m = 2$ with unit latencies (Coffman and Graham [CG72]) and for in-trees with unit latencies and any $m$ (Hu [Hu61]).

Proof sketch (full proofs: [Ull75], [HG83], [CG72], [Hu61])

Ullman reduces 3-SAT to scheduling unit tasks: the construction adds chains of tasks that fill all $m$ processors except in slots a satisfying assignment can use, so a schedule of length $T$ exists iff the formula is satisfiable. Membership in NP is immediate, because a schedule is checked in linear time. Hennessy and Gross reduce a known NP-complete sequencing problem to ordering instructions with latencies so that the interlock delays stay below a bound. For the polynomial cases, Coffman–Graham labels nodes in reverse topological order by the lexicographic order of their successors' labels and list-schedules by label: an exchange argument shows that on two processors no idle slot can be removed. Hu's "highest level first" rule is optimal on in-trees because, when a level-$\lambda$ slot is idle, all remaining work lies on paths of length below $\lambda$.

Bottom-up list scheduling¶

Bottom-up scheduling is top-down scheduling of the reversed problem, followed by mirroring the result in time. Making this precise also makes the correctness proof one line.

Definition 23.3.5 (Reversed instance)

The reverse of an instance $(V, E, \ell, \mathrm{lat}, \mathrm{RT})$ has the same operations and latencies, each reservation table mirrored inside the operation's latency, $\mathrm{RT}'(v) = \{ (r, \mathrm{lat}(v) - 1 - k) \mid (r, k) \in \mathrm{RT}(v) \}$, and an edge $(w, v)$ for every $(v, w) \in E$ with latency $\ell'(w, v) = \mathrm{lat}(w) - \mathrm{lat}(v) + \ell(v, w)$. The lab numbers the operations of the reverse in reverse order, so "smaller index first" in the reverse means "later in the block".

Theorem 23.3.6 (Mirroring)

Let $s$ be a valid schedule of the reversed instance and $L' = \max_v (s(v) + \mathrm{lat}(v))$. Then $t(v) = L' - s(v) - \mathrm{lat}(v)$ is a valid schedule of the original with $t(v) \ge 0$ and $L(t) \le L'$ (with equality when some operation has $s(v) = 0$).

Proof

Nonnegative: $s(v) + \mathrm{lat}(v) \le L'$. Edges: for $(v, w) \in E$ the reversed edge gives $s(v) \ge s(w) + \mathrm{lat}(w) - \mathrm{lat}(v) + \ell(v, w)$, hence $t(w) - t(v) = s(v) + \mathrm{lat}(v) - s(w) - \mathrm{lat}(w) \ge \ell(v, w)$. Resources: $v$ uses $r$ in original cycle $t(v) + k$ for $(r, k) \in \mathrm{RT}(v)$; under the bijection $c \mapsto L' - 1 - c$ this is cycle $L' - 1 - t(v) - k = s(v) + (\mathrm{lat}(v) - 1 - k)$, exactly where the reversed schedule books $(r, \mathrm{lat}(v) - 1 - k) \in \mathrm{RT}'(v)$. So the counts per (resource, cycle) are the same, and capacities hold. Length: $\max_v (t(v) + \mathrm{lat}(v)) = L' - \min_v s(v) \le L'$.

Algorithm 23.3.7 (Bottom-up list scheduling)

Input: as Algorithm 23.3.2; a priority for the reversed instance.
Output: issue cycles $t(v)$.
Precondition: as Algorithm 23.3.2.
Postcondition: $t$ is valid (Theorems 23.3.3's validity part and 23.3.6).
Invariant: the invariants of Algorithm 23.3.2 on the reversed instance.

function BottomUp(G, prio):
    G' ← Reverse(G)                                   # Definition 23.3.5
    keys ← prio computed on G'                        # cp: heights of G'; succ: #succs in G'
    s ← TopDown(G', keys)                             # Algorithm 23.3.2
    L' ← max over v of s(v) + lat(v)
    return t(v) = L' − s(v) − lat(v) for every v

In the lab, bu-cp sorts by $(-h'(v), \mathrm{idx}'(v))$ and bu-succ by $(-\lvert \mathrm{succs}'(v) \rvert, -h'(v), \mathrm{idx}'(v))$, where $h'$ is the height in $G'$ (the longest path from the start of the block through $v$) and $\mathrm{succs}'(v)$ are $v$'s predecessors in $G$.

Corollary 23.3.8 (Graham's bound holds bottom-up)

On the machine of Theorem 23.3.3, Algorithm 23.3.7 also returns $L \le \frac{1}{m}\sum \mathrm{lat} + (1 - \frac1m)\mathrm{CP}(G)$.

Proof

Mirroring a full occupancy $[0, \mathrm{lat})$ gives full occupancy, and a true edge gets $\ell' = \mathrm{lat}(w)$, the latency of its new source. The issue slot moves to offset $\mathrm{lat} - 1$, but every operation using an issue slot in a cycle also occupies a unit in that cycle, so with $W \ge m$ issue never binds and the proof of Theorem 23.3.3 applies verbatim to the reversed instance. The reversed instance has the same $\sum \mathrm{lat}$ and the same critical path (paths reverse, and the latency of a path, $\sum \ell + \mathrm{lat}$ of its last node, is preserved: $\sum_i \mathrm{lat}(v_i)$ in both directions). So $L' \le$ the bound, and $L(t) \le L'$ by Theorem 23.3.6.

Register-pressure-aware list scheduling¶

Definition 23.3.9 (Values, live ranges, MaxLive)

A value is either an operation's result or a register read before any definition in the block (a live-in). Under schedule $t$ of length $L$, the value defined by $v$ is live in the cycles $[t(v), e]$ where $e$ is the largest issue cycle of a use it reaches, or $L - 1$ if it is live out, or $t(v)$ if it has neither. A live-in is live in $[0, e]$. $\mathrm{MaxLive}(t)$ is the largest number of values live in one cycle. This is the lab's definition (SPEC §5.4), and it is the number of registers an allocator needs for the block, up to copies (Ch 22).

Algorithm 23.3.10 (Pressure-capped top-down scheduling, after Goodman and Hsu)

Input: as Algorithm 23.3.2; a register limit $K$ (default: $\mathrm{MaxLive}$ of the single-issue in-order schedule).
Output: a valid schedule $t$ with $\mathrm{MaxLive}(t) \le K$.
Precondition: $K \ge \mathrm{MaxLive}$ of the in-order schedule.
Postcondition: Proposition 23.3.12.
Invariant: live is the set of values live at the current cycle given the placements so far; after the cycle ends, it counts exactly the values of Definition 23.3.9 in that cycle.

function PressureSchedule(G, K):
    base ← InOrder(G)                            # single issue, program order, ASAP
    live ← live-in values that are used; c ← 0; idle ← 0
    while some v is unplaced:
        dying ← ∅
        loop:
            cand ← { v | Ready(v, c), Fits(v, c), |live| + defines(v) ≤ K }
            if cand = ∅: break
            if |live| ≥ K − 1: v ← argmin over cand of (−Kills(v), −h(v), idx(v))   # CSR mode
            else:              v ← argmin over cand of (−h(v), idx(v))              # CSP mode
            Place(v, c)
            for each value x read by v, not live out, all of whose uses are now placed:
                dying ← dying ∪ {x}
            if v defines a value y: live ← live ∪ {y}; if y has no use and is not live out:
                dying ← dying ∪ {y}
        progress ← (something placed) or dying ≠ ∅ or (some placed op still in flight)
        live ← live \ dying
        idle ← 0 if progress else idle + 1
        if idle > 1: return base                 # stuck: fall back
        c ← c + 1
    return t

function Kills(v): number of values v reads that are not live out and whose other uses are placed

3. Worked examples¶

Top-down list scheduling¶

td-cp on the running block (toy machine: issue 2, two ALUs, one memory unit, one multiplier). The heights come from Lesson 23.2 §3: c 9, a 8, b 8, e 6, d 5, f 5, g 5, i 2, h 1, j 1. "Ready at start" lists the ready operations at the beginning of the cycle in key order. Operations that become ready inside the cycle are shown in the notes.

cycle	ready at start (key order)	placed	notes
0	c, a, b	c	c ($h = 9$) takes the memory unit; a, b don't fit
1	a, b	a	tie $h = 8$: smaller index a
2	b	b
3	e	e	e needs c + 3
4	f	f	f needs e + 1 and c + 3
5	d, h	d, g	d first ($h$ 5 > 1); the anti edge d→g has latency 0, so g becomes ready inside cycle 5 and beats h ($h$ 5 > 1) for the memory unit; issue width now full
6	h	h
7	—	—	i needs f + 3 = 7 and g + 3 = 8
8	i	i
9	j	j

Result: $t = $ {a 1, b 2, c 0, d 5, e 3, f 4, g 5, h 6, i 8, j 9}, length $9 + 1 = 10$. This is exactly the reservation table drawn in Lesson 23.1 §3. The lower bound is $\max(\mathrm{CP}, \mathrm{RB}) = \max(9, 5) = 9$. Exhaustive search over all valid schedules finds no schedule of length 9, so 10 is optimal here. The one idle cycle is forced by the two three-cycle producers of i.

td-succ puts successor count first: a (3 successors) beats c (2), so the critical c→e→f→i→j chain starts a cycle late. The trace is 0: a; 1: c; 2: b; 3: —; 4: e; 5: d, g; 6: f, h; 7–8: —; 9: i; 10: j, length 11.

Try it

./course drill list-schedule --seed 5 --solution generates a block and prints this trace (ready list at the start of every cycle, placements, final length) for top-down or bottom-up.

Bottom-up list scheduling¶

The reversed instance (Definition 23.3.5) of the running block has the edges reversed. For example, j→i gets $\ell' = \mathrm{lat}(i) - \mathrm{lat}(j) + \ell(i, j) = 1 - 1 + 1 = 1$, d→a gets $3 - 3 + 3 = 3$, and h→a gets $1 - 3 + 0 = -2$ (the mem-anti edge from a load to a later store). The heights in the reverse are j 9, i 8, f 7, d 6, g 6, h 5, e 4, a 3, b 3, c 3. bu-cp on the reverse, in reverse cycles $s$:

$s$	ready at start (key order)	placed
0	j, h	j, h
1	i	i
2	f, g	f, g
3	d	d
4	—	—
5	e	e
6	c, b, a	c
7	b, a	b
8	a	a

$L' = \max(s + \mathrm{lat}) = 8 + 3 = 11$, and mirroring $t = 11 - s - \mathrm{lat}$ gives {a 0, b 1, c 2, d 5, e 5, f 6, g 6, h 10, i 9, j 10}, length 11. Bottom-up placed the store h as late as possible, which costs nothing here. But it also serialized the three loads in reverse priority order, so the load c, which heads the critical path, went last among them (cycle 2). On this block, top-down wins by one cycle. The lab's corpus shows the opposite on other blocks, and over 240 blocks the four variants stay within 1.5 % of each other in total length (§8).

Register-pressure-aware list scheduling¶

MaxLive of the td-cp schedule is 6 (in cycle 5, the values of a, b, e, f, d and g are all live). The in-order schedule has MaxLive 5, so Algorithm 23.3.10 runs with $K = 5$. "live" is the count after the cycle's placements:

cycle	live after	placed	notes
0	1	c	CSP mode, as `td-cp`
1	2	a
2	3	b
3	4	e
4	5	f	f is c's last use, so c dies at the end of the cycle (live 4 in cycle 5)
5	5	d, h	live $4 \ge K - 1$: CSR mode; d (kills a) and h (kills e) tie on kills, d wins on height; then g would make 6 > K, so the store h (defines nothing) takes the memory unit
6	3	g	values of a, b, e died in cycle 5
7–8	3	—	i waits for g + 3
9	4	i
10	3	j

Length 11 instead of 10, MaxLive 5 instead of 6: one cycle traded for one register.

4. Invariants and correctness¶

Top-down list scheduling¶

Lemma 23.3.11 (Algorithm 23.3.2 terminates with a valid schedule)

For any priority, Algorithm 23.3.2 terminates, and the returned $t$ is valid.

Proof

Invariant (I1): a placement happens only if Ready (every edge into $v$ satisfied, since $t(u) + \ell(u, v) \le c = t(v)$) and Fits (Lemma 23.1.13) hold. Edges out of $v$ are checked when their targets are placed. (I2) holds because the inner loop exits only when cand is empty. Termination: let $v$ be unplaced with all predecessors placed (a source of the unplaced sub-DAG exists because $G$ is acyclic). It is ready from cycle $c_0 = \max_u (t(u) + \ell(u, v))$ on. The placed operations occupy only finitely many (resource, cycle) pairs, so from some cycle on the machine is empty, $v$ fits, and something is placed. Each placement decreases the number of unplaced operations, and between placements only finitely many cycles pass.

Bottom-up list scheduling¶

Validity is Theorem 23.3.6 applied to Lemma 23.3.11 on the reversed instance. Graham's guarantee transfers by Corollary 23.3.8. The lab's Graham test checks $mL \le \sum \mathrm{lat} + (m-1)\mathrm{CP}$ for all four list algorithms on 240 random DAGs.

Bottom-up is not \"top-down on the reversed order of instructions\"

Scheduling the instructions of a reversed block top-down with the original latencies gives invalid schedules. In reverse time the consumer is placed first, and the separation it needs from its producer depends on both latencies (the producer's result must land before the consumer issues, and both are measured from their own issue cycles). Definition 23.3.5's $\ell' = \mathrm{lat}(w) - \mathrm{lat}(v) + \ell(v, w)$ and the mirrored reservation tables are what make the mirror image valid (Theorem 23.3.6).

Register-pressure-aware list scheduling¶

Proposition 23.3.12 (Algorithm 23.3.10 respects the limit)

If $K$ is at least the MaxLive of the in-order schedule, Algorithm 23.3.10 returns a valid schedule with $\mathrm{MaxLive} \le K$.

Proof

If it falls back, it returns the in-order schedule, which is valid and has $\mathrm{MaxLive} \le K$ by hypothesis. Otherwise every placement satisfies the conditions of Algorithm 23.3.2, so the result is valid (Lemma 23.3.11). For the pressure bound, fix a cycle $c$. By the invariant, live during cycle $c$ contains exactly the values defined at or before $c$ whose last use is not before $c$: a value leaves live only at the end of the cycle in which its last use is placed, and every later use would be placed later still. A placement at $c$ can only add the value it defines, and it is made only if $\lvert\mathrm{live}\rvert + 1 \le K$. Values that die at $c$ are still counted at $c$, and so is every value live at $c$ in Definition 23.3.9, since uses placed later only extend ranges forward. Hence the number of values live at $c$ is at most $K$.

The heuristic never promises a short schedule under the cap. With $K$ below what the DAG needs, no schedule exists (the in-order fallback is only guaranteed for $K \ge$ its own MaxLive). The general problem, fewest registers for a DAG, is NP-complete [Set75].

5. Complexity¶

Let $n$ be the operations, $e$ the edges, $L$ the schedule length and $\rho$ the reservation-table size.

Technique	Time (worst)	Time (typical, with a heap)	Space
Top-down (Alg. 23.3.2)	$O(L \cdot n \cdot (\text{deg} + \rho))$ as written; $O((n + e)\log n + L\rho n)$ with a ready heap and per-predecessor counters	$O((n + e) \log n)$	$O(n + e)$ plus the reservation table
Bottom-up (Alg. 23.3.7)	the same plus $O(n + e)$ to reverse	$O((n + e) \log n)$	$O(n + e)$
Pressure-aware (Alg. 23.3.10)	the same plus $O(\text{uses})$ per placement for kill counts	$O((n + e)\log n)$	$O(n + e)$

Justification. As written, each cycle scans all operations and their predecessors: $O(n \cdot \text{deg})$ per cycle, over $L \le \sum \mathrm{lat} + \rho n$ cycles. The standard implementation keeps a counter of unplaced predecessors per operation, moves an operation to a "pending" queue keyed by its earliest cycle when the counter reaches 0, and to a ready heap when that cycle arrives: each edge is touched once, each operation enters and leaves the heap once ($\log n$), and each attempted placement costs $O(\rho)$. An operation can be retried in several cycles only while resources are full.

Pathological family (quality). Graham's bound is tight for list scheduling. Take $m$ units, $m(m-1)$ independent unit tasks and one chain of $m$ unit tasks, with the priority that prefers the independent tasks. The list schedule first runs the $m(m-1)$ independent tasks, $m$ per cycle, for $m - 1$ cycles, then the chain alone for $m$ cycles: $L = 2m - 1$. The optimum runs the chain from cycle 0 and packs the rest alongside: $\mathrm{OPT} = m$. The ratio is $(2m - 1)/m = 2 - 1/m$. The height priority avoids this family (the chain has larger heights), but Graham's anomalies [Gra69] show that no fixed priority is safe on all inputs: adding a unit, or shortening a task, can make a list schedule longer.

Real-world scale. On the lab corpus (240 blocks of 3–18 operations on two machines), td-cp is 4.2 % above the lower bound $\max(\mathrm{CP}, \mathrm{RB})$ in total and meets it on 74 % of the blocks (ch23-compare, §8). Production schedulers see regions of thousands of instructions after unrolling, which is why LLVM limits the ready list (-misched-limit, default 256) and GCC limits the region size.

Top-down list scheduling¶

Operation scheduling vs cycle scheduling: instead of filling cycle by cycle, take operations in priority order and put each in the earliest cycle where it fits. This allows filling holes in earlier cycles (backfilling), but it is harder to combine with hazard automata, which want cycles in order.
Coffman–Graham labels [CG72]: a priority computed from lexicographic successor labels. It is optimal for two units and unit latencies, and costs $O(n^2)$ to compute naively.
Lookahead and backtracking (GCC's max_lookahead_tries, "DFA lookahead"): try several ready operations for the current cycle and keep the best cycle packing. Better packing on VLIW cores, in exchange for multiples of the base time.

Bottom-up list scheduling¶

Bidirectional scheduling (LLVM GenericScheduler default): schedule from both ends and pick, at each step, the more critical end. It gets the register benefits of bottom-up and the latency benefits of top-down, at the cost of a more complex model of "the current cycle".
Sethi–Ullman-numbered bottom-up (list-burr in SelectionDAG): the priority is the number of registers a subtree needs [SU70], which is exact on trees.

Register-pressure-aware list scheduling¶

Goodman–Hsu's two modes [GH88]: code scheduling for pipelines (latency first) until free registers fall below a threshold, then code scheduling to reduce registers. Algorithm 23.3.10 is a simple version of this idea (Lesson 23.8 has the original).
Pressure sets and limits per register class (LLVM RegPressureTracker, RegisterClassInfo::getRegPressureSetLimit): track pressure per class (GPR, FPR, vector) and prefer candidates that reduce "excess" or "critical-max" pressure. This is more precise with several register files.
Balanced scheduling (Kerns and Eggers 1993): spread loads so that each has as much independent work behind it as possible, which hides uncertain (cache-miss) latencies without assuming a fixed one.

7. In real compilers¶

Top-down list scheduling¶

GCC's scheduler is top-down: schedule_block in gcc/haifa-sched.cc keeps the ready list (ready_sort, rank_for_schedule) and a queue of operations waiting for latencies (queue_to_ready), and consults the pipeline automaton of Lesson 23.1 each cycle [GCC-haifa]. LLVM's GenericScheduler becomes top-down with -misched-prera-direction=topdown (SchedBoundary in llvm/lib/CodeGen/MachineScheduler.cpp) [LLVM-MISched].

GCC's top-down list scheduler, cycle by cycle

Reproduce (gcc 14.2.0 on x86-64 Linux; run.c from Lesson 23.2 §7):

gcc-14 -O2 -fschedule-insns -fsched-verbose=4 -fdump-rtl-sched1 -c run.c -o run.o
grep -E 'Ready list \(t|^;;\s+[0-9]+-->' run.c.*r.sched1 | sed -n 1,16p

Output (the first 16 matching lines):

;;  Ready list (t =   0):    24:3:prio=8  23:1:prio=8
;;    0--> b  0: i  23 r117=di                                 :hsw_decodern,hsw_p0156
;;  Ready list (t =   0):    24:3:prio=8
;;    0--> b  0: i  24 r118=si                                 :hsw_decodern,hsw_p0156
;;  Ready list (t =   0):  
;;  Ready list (t =   1):    3:4:prio=6  2:2:prio=6
;;    1--> b  0: i   2 r111=r117                               :hsw_decodern,hsw_p0156
;;  Ready list (t =   1):    3:4:prio=6
;;    1--> b  0: i   3 r112=r118                               :hsw_decodern,hsw_p0156
;;  Ready list (t =   1):  
;;  Ready list (t =   2):    9:7:prio=5  7:5:prio=5
;;    2--> b  0: i   7 r99=[r111+0x8]                          :hsw_decodern,hsw_p23
;;  Ready list (t =   2):    8:6:prio=4  9:7:prio=5
;;    2--> b  0: i   9 r100=[r112]                             :hsw_decodern,hsw_p23
;;  Ready list (t =   2):  
;;  Ready list (t =   3):    8:6:prio=4

What to notice: this is the trace of Algorithm 23.3.2. Each "Ready list (t = c)" line is the ready list during cycle $c$ (insn:luid:prio= with prio the critical-path height, printed with the head of the list on the right) and each c--> line a placement. The two argument copies (23, 24) go in cycle 0, then the loads of A[1] (7) and B[0] (9) in cycle 2, because they have the highest priority. Insn 8 (the multiply with a folded load of A[0]) became ready inside cycle 2 but waits: GCC's log says queued for 1 cycles (resource conflict) (the load ports of the Haswell automaton are taken).

Bottom-up list scheduling¶

LLVM's MachineScheduler schedules bottom-up with -misched-prera-direction=bottomup (SchedBoundary Bot, pickNodeFromQueue over Bot.Available); SelectionDAG's ScheduleDAGRRList.cpp is bottom-up only [LLVM-MISched, LLVM-RRList].

Top-down vs bottom-up on an in-order core

Reproduce (clang 23.1.2, llc 23.1.2, llvm-mca 23.1.2):

cat > poly.c <<'EOF'
long poly(long *a, long x) {
  long p0 = a[0] * x + a[1];
  long p1 = a[2] * x + a[3];
  long p2 = a[4] * x + a[5];
  long p3 = a[6] * x + a[7];
  return (p0 * p1) ^ (p2 * p3);
}
EOF
clang-23 --target=aarch64-linux-gnu -O2 -S -emit-llvm poly.c -o poly.ll
for d in topdown bottomup; do echo "== $d"
  llc -O2 -mtriple=aarch64-linux-gnu -mcpu=cortex-a55 -misched-prera-direction=$d \
    -enable-post-misched=false poly.ll -o - | grep -P '^\t(ldp|madd|mul|eor)' | tee p-$d.s
  llvm-mca -mtriple=aarch64-linux-gnu -mcpu=cortex-a55 -iterations=1 p-$d.s | grep 'Total Cycles'
done

Output (complete):

== topdown
    ldp x8, x9, [x0]
    ldp x10, x11, [x0, #16]
    ldp x12, x13, [x0, #32]
    madd    x8, x8, x1, x9
    ldp x9, x14, [x0, #48]
    madd    x10, x10, x1, x11
    madd    x11, x12, x1, x13
    madd    x9, x9, x1, x14
    mul x8, x10, x8
    mul x9, x9, x11
    eor x0, x9, x8
Total Cycles:      20
== bottomup
    ldp x8, x9, [x0]
    madd    x8, x8, x1, x9
    ldp x9, x10, [x0, #16]
    madd    x9, x9, x1, x10
    ldp x10, x11, [x0, #32]
    madd    x10, x10, x1, x11
    ldp x11, x12, [x0, #48]
    madd    x11, x11, x1, x12
    mul x8, x9, x8
    mul x9, x11, x10
    eor x0, x9, x8
Total Cycles:      32

What to notice: the Cortex-A55 is in-order, so the order in the file is the order of issue. Top-down starts the three loads first and hides their latency: 20 cycles, using registers x8–x14. Bottom-up puts each madd right after its ldp, so it keeps fewer values live (x8–x12) but every madd stalls on its load: 32 cycles. Neither direction is right in general. GenericScheduler's default, bidirectional, is meant to get the best of both.

Register-pressure-aware list scheduling¶

GenericScheduler::tryCandidate compares candidates by tryPressure on RegExcess, RegCritical and RegMax before latency (llvm/lib/CodeGen/MachineScheduler.cpp). The pressure comes from RegPressureTracker (llvm/lib/CodeGen/RegisterPressure.cpp) [LLVM-MISched, LLVM-RegPressure]. GCC has -fsched-pressure (sched_pressure in haifa-sched.cc) [GCC-haifa].

Turning off pressure tracking costs spills

Reproduce (clang 23.1.2, llc 23.1.2):

{ echo 'long pres(long *restrict a, long *restrict b) {'
  for i in $(seq 0 23); do echo "  long t$i = a[$i] * b[$i];"; done
  printf '  return t0'; for i in $(seq 1 23); do printf ' ^ t%d' $i; done; echo ';'
  echo '}'; } > pres.c
clang-23 --target=aarch64-linux-gnu -O2 -S -emit-llvm pres.c -o pres.ll
for f in bottomup topdown; do for p in true false; do
  printf '%-9s regpressure=%-5s spill/reload lines: ' $f $p
  llc -O2 -mtriple=aarch64-linux-gnu -mcpu=cortex-a55 -misched-prera-direction=$f \
    -misched-regpressure=$p pres.ll -o - | grep -cE 'Spill|Reload'
done; done

Output (complete):

bottomup  regpressure=true  spill/reload lines: 8
bottomup  regpressure=false spill/reload lines: 8
topdown   regpressure=true  spill/reload lines: 16
topdown   regpressure=false spill/reload lines: 32

What to notice: 48 loads feed 24 products. A top-down scheduler that only watches latency starts loads as early as it can and runs out of AArch64's registers: 32 spill and reload instructions (the allocator annotates them with Spill/Reload comments). Pressure tracking halves that. Bottom-up needs no help: each product is placed just before its use, so few values are live at once. (The 8 remaining lines save and restore callee-saved registers, which is the allocator's decision.)

8. Comparison¶

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

Lab numbers from build/<preset>/bin/ch23-compare tests/ch23/Inputs/blocks.txt tests/ch23/Inputs/loops.txt tests/ch23/Inputs/loops-hard.txt on this machine: total length of 240 blocks 4110 (td-cp), 4118 (td-succ), 4153 (bu-cp), 4171 (bu-succ), 4298 (pressure) against a total lower bound of 3943; timings vary with load.

Choose top-down after register allocation, when registers are fixed and latency is what is left to hide, and on in-order cores. Choose bottom-up before register allocation, or when the block's results matter more than its inputs. Choose pressure-aware scheduling whenever it runs before allocation. The spills it avoids cost more than the latency it gives up, as the A55 box shows.

9. Assessment¶

Quiz: td-trace-running (mapping), td-succ-length (number), graham-ratio (number), np-hard-sched (single), reverse-latency (number), maxlive-running (number), pressure-tradeoff (single), find-trycandidate (text). Tags list-top-down, list-bottom-up, pressure-aware.
Drills: ./course drill list-schedule (easy/medium: top-down cp; hard: bottom-up with the reversed latencies), ./course drill critical-path (the priorities).
Flashcards: tags list-top-down, list-bottom-up, pressure-aware.
Lab: E1 (top-down, both priorities), E2 (bottom-up), E3 ★ (pressure) in exercises; tests ch23.List/*, ch23.Pressure.*.

References¶

See the chapter references.

Technique	Time (worst)	Time (typical, with a heap)	Space
Top-down (Alg. 23.3.2)	\(O(L \cdot n \cdot (\text{deg} + \rho))\) as written; \(O((n + e)\log n + L\rho n)\) with a ready heap and per-predecessor counters	\(O((n + e) \log n)\)	\(O(n + e)\) plus the reservation table
Bottom-up (Alg. 23.3.7)	the same plus \(O(n + e)\) to reverse	\(O((n + e) \log n)\)	\(O(n + e)\)
Pressure-aware (Alg. 23.3.10)	the same plus \(O(\text{uses})\) per placement for kill counts	\(O((n + e)\log n)\)	\(O(n + e)\)

name	key (sorted ascending)	idea
`cp` (critical path)	\((-h(v), \mathrm{idx}(v))\)	longest remaining path first (Hu's "level")
`succ` (successor count)	\((-\lvert \mathrm{succs}(v) \rvert, -h(v), \mathrm{idx}(v))\)	unlock the most work first

cycle	ready at start (key order)	placed	notes
0	c, a, b	c	c (\(h = 9\)) takes the memory unit; a, b don't fit
1	a, b	a	tie \(h = 8\): smaller index a
2	b	b
3	e	e	e needs c + 3
4	f	f	f needs e + 1 and c + 3
5	d, h	d, g	d first (\(h\) 5 > 1); the anti edge d→g has latency 0, so g becomes ready inside cycle 5 and beats h (\(h\) 5 > 1) for the memory unit; issue width now full
6	h	h
7	—	—	i needs f + 3 = 7 and g + 3 = 8
8	i	i
9	j	j

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

Lesson 23.3 — List scheduling: top-down, bottom-up and register-pressure-aware¶

1. Problem and motivation¶

Top-down list scheduling¶

Bottom-up list scheduling¶

Register-pressure-aware list scheduling¶

2. Definitions and algorithms¶

Top-down list scheduling¶

Bottom-up list scheduling¶

Register-pressure-aware list scheduling¶

3. Worked examples¶

Top-down list scheduling¶

Bottom-up list scheduling¶

Register-pressure-aware list scheduling¶

4. Invariants and correctness¶

Top-down list scheduling¶

Bottom-up list scheduling¶

Register-pressure-aware list scheduling¶

5. Complexity¶

6. Variants and refinements¶

Top-down list scheduling¶

Bottom-up list scheduling¶

Register-pressure-aware list scheduling¶

7. In real compilers¶

Top-down list scheduling¶

Bottom-up list scheduling¶

Register-pressure-aware list scheduling¶

8. Comparison¶

9. Assessment¶

References¶