Lesson 23.2 — Dependence DAGs: true, anti, output, memory and control dependences¶

Techniques: dependence-DAG construction (pairwise and table-driven); memory and control dependences; critical-path analysis (heights, depths, slack) · Lab: labs/ch23-sched §5.1 (the canonical DAG) · Prerequisites: Lesson 23.1 (latency, reservation tables), Ch 14 (reaching definitions), Ch 19 (alias analysis) · Time: 3–4 hours

A scheduler may reorder instructions, but only in ways that do not change what the program computes. The dependence DAG of a block records every pair of instructions whose order matters and how many cycles must separate them. Every scheduler in this chapter (list scheduling, region scheduling, modulo scheduling, and LLVM's own) starts by building one. It also answers a first performance question. The longest latency-weighted path through the DAG, the critical path, is a lower bound on the length of any schedule, however many units the machine has.

The running example of the chapter is this block for the toy machine of Lesson 23.1. It computes r4 = A[0]*A[1] + ((B[0]+B[0])*B[0] - B[1]) and stores B[0]+B[0] through the register index A[r2]. The register r1 is reused for B[1] once A[0] is dead, as a register allocator would do:

block run                        # labs/ch23-sched/inputs/running.txt
  liveout r4
  a: r1 = load A[0]
  b: r2 = load A[1]
  c: r3 = load B[0]
  d: r4 = mul r1, r2
  e: r5 = add r3, r3
  f: r6 = mul r5, r3
  g: r1 = load B[1]
  h: store A[r2], r5
  i: r7 = sub r6, r1
  j: r4 = add r4, r7
end

1. Problem and motivation¶

Dependence-DAG construction¶

Two instructions can run in either order, or at the same time, when neither writes anything the other reads or writes. Bernstein stated these conditions for parallel processes in 1966 [Ber66]. The microcode-compaction literature of the 1970s turned them into graphs over the operations of a basic block [LDSM80], and every compiler scheduler since builds such a graph. The naive construction compares every pair of instructions in \(\Theta(n^2)\) time. Gibbons and Muchnick's scheduler for the HP Precision Architecture introduced a backward pass with per-register tables that adds only the necessary edges [GM86]. LLVM's ScheduleDAGInstrs::buildSchedGraph and GCC's sched-deps.cc both use table-driven constructions. In pebblec the DAG is built by LLVM on MachineInstrs, and in the lab you build it yourself (SPEC §5.1).

Memory and control dependences¶

Registers are named exactly, so their dependences are exact. Memory is not. A store to A[r2] may or may not write the location that a load of A[0] reads. A may-alias answer forces an edge, and a no-alias answer lets the scheduler move the load up past the store. This is where alias analysis (Ch 19) pays off in the back end, and where C's restrict changes the machine code. Inside a basic block, control flow reduces to a single constraint: the branch at the end must stay at the end, together with anything the branch or the next block needs. Calls, volatile accesses and barriers act as chain points that nothing crosses.

Critical-path analysis¶

Once the DAG exists, its longest path gives the classic lower bound on schedule length. The height of each node (the longest path from it to the end) is also the classic priority for list scheduling: schedule the op that is furthest from being done first [LDSM80, GM86]. Hu used the same "level" priority to prove optimality for trees of unit tasks [Hu61], and every production list scheduler uses heights, depths or both (Lesson 23.3).

2. Definitions and algorithms¶

Definition 23.2.1 (Block, definitions, uses, memory operands)

A block is a sequence \(x_1, \dots, x_n\) of operations executed in that order. Each \(x_i\) defines a set \(\mathrm{defs}(x_i)\) of registers (at most one in the lab), uses a set \(\mathrm{uses}(x_i)\) of registers (its operands and any register used in its address) and, if it is a load or store, accesses one memory location given by an operand \(\mathrm{mem}(x_i)\). A may-alias oracle \(\mathrm{MA}(x_i, x_j)\) is true whenever the two memory operands can denote the same location in some execution. It may also be true when they cannot (it is conservative).

Definition 23.2.2 (Dependence kinds)

For \(i < j\), \(x_j\) depends on \(x_i\) when their order is observable:

true (read after write, RAW): \(x_i\) defines a register \(r\), \(x_j\) uses \(r\), and no \(x_k\) with \(i < k < j\) defines \(r\) (\(x_i\) is the reaching definition of that use);
anti (write after read, WAR): \(x_i\) uses \(r\) and \(x_j\) is the first definition of \(r\) after \(x_i\);
output (write after write, WAW): \(x_i\) and \(x_j\) both define \(r\) and no \(x_k\) in between does;
memory true / anti / output: the same three with "defines" and "uses" read as "stores to" and "loads from", for every pair with \(\mathrm{MA}(x_i, x_j)\) and at least one store;
control: \(x_j\) is the block's terminator, a call or a barrier, or \(x_i\) is a call or barrier (nothing moves across it).

Anti and output dependences are false (name) dependences: they exist only because a register or location is reused, and renaming removes them.

Definition 23.2.3 (Edge latencies)

With the timing of Definition 23.1.1 (read at issue, result visible \(\mathrm{lat}\) cycles later), an edge \(x_i \to x_j\) gets the least separation \(\ell(i, j)\) that keeps the order observable: true: \(\mathrm{lat}(x_i)\); anti: \(0\); output: \(\max(1, \mathrm{lat}(x_i) - \mathrm{lat}(x_j) + 1)\); memory store \(\to\) load: \(\mathrm{lat}(\text{store})\); load \(\to\) store: 0; store \(\to\) store: as output. When several kinds relate the same pair, the edge carries the maximum.

Definition 23.2.4 (Canonical dependence DAG; schedule)

The dependence DAG \(G = (V, E, \ell)\) of a block has \(V = \{x_1, \dots, x_n\}\) and an edge \((x_i, x_j)\) with latency \(\ell(i, j)\) for every dependence of Definition 23.2.2 (merged by Definition 23.2.3). Every edge goes from a smaller to a larger index, so \(G\) is acyclic. A schedule \(t : V \to \mathbb{N}\) is valid if it is resource-feasible (Definition 23.1.3) and \(t(x_j) \ge t(x_i) + \ell(i, j)\) for every edge. Its length is \(L(t) = \max_i \big(t(x_i) + \mathrm{lat}(x_i)\big)\).

Dependence-DAG construction¶

Algorithm 23.2.5 (Pairwise DAG construction)

Input: a block \(x_1, \dots, x_n\); latencies; a may-alias oracle.
Output: a DAG with an edge for every pair in conflict.
Precondition: none.
Postcondition: \((x_i, x_j) \in E\) iff \(i < j\) and the two conflict on a register or (may-alias) memory location; this includes transitive edges, e.g. from a definition to every later redefinition.
Invariant: after iteration \(j\) of the outer loop, all pairs \((i, j')\) with \(j' \le j\) are decided.

function PairwiseDAG(x_1..x_n):
    E ← ∅
    for j in 1..n:
        for i in 1..j−1:
            L ← −∞
            for r in defs(x_i) ∩ uses(x_j):  L ← max(L, lat(x_i))                       # true
            for r in uses(x_i) ∩ defs(x_j):  L ← max(L, 0)                              # anti
            for r in defs(x_i) ∩ defs(x_j):  L ← max(L, max(1, lat(x_i)−lat(x_j)+1))    # output
            if x_i, x_j access memory, one is a store, and MA(x_i, x_j):
                L ← max(L, MemLatency(x_i, x_j))                                      # Definition 23.2.3
            if L > −∞: E ← E ∪ {(x_i, x_j, L)}
    return E

Algorithm 23.2.6 (Table-driven DAG construction, forward pass)

Input: as Algorithm 23.2.5.
Output: the canonical DAG of Definition 23.2.4.
Precondition: each operation defines at most one register (lift by looping over definitions).
Postcondition: register edges exactly as in Definition 23.2.2 (reaching definition, next definition), memory edges for every conflicting pair.
Invariant: before processing \(x_j\), lastdef[r] is the last definition of \(r\) among \(x_1..x_{j-1}\) (if any) and uses[r] lists the uses of \(r\) after that definition, in order.

function TableDAG(x_1..x_n):
    E ← ∅; lastdef ← {}; uses ← {} (default: empty list); memops ← []
    for j in 1..n:
        for r in uses(x_j):                                   # true edges
            if r ∈ lastdef: AddEdge(lastdef[r], j, lat(x_lastdef[r]))
            uses[r].append(j)
        for r in defs(x_j):
            for u in uses[r], u ≠ j: AddEdge(u, j, 0)         # anti: to the NEXT definition only
            if r ∈ lastdef:                                   # output
                AddEdge(lastdef[r], j, max(1, lat(x_lastdef[r]) − lat(x_j) + 1))
            uses[r] ← []; lastdef[r] ← j
        if x_j accesses memory:
            for i in memops:
                if (x_i or x_j is a store) and MA(x_i, x_j): AddEdge(i, j, MemLatency(x_i, x_j))
            memops.append(j)
    return E

function AddEdge(i, j, L):                                    # merge parallel edges
    E[(i, j)] ← max(E[(i, j)] if present else −∞, L)

Algorithm 23.2.6 produces fewer edges than Algorithm 23.2.5, because it never adds an edge that a path already implies (a definition to a later redefinition goes through the chain of intermediate ones). Proposition 23.2.10 shows that both DAGs allow exactly the same schedules. LLVM's buildSchedGraph runs the same idea backward, from the bottom of the region, which lets it attach each use to the definitions that follow it in reverse order [LLVM-SDInstrs].

Memory and control dependences¶

Definition 23.2.7 (Conservative memory and control edges)

With no alias information, every pair (store, load or store) gets a memory edge. With an oracle, only pairs with \(\mathrm{MA}\) true do. In the lab, \(\mathrm{MA}(A[c], A[c'])\) is \(c = c'\) for constant indices, and true whenever one index is a register (\(A[r2]\)) or the arrays are equal but the indices unknown; different array names never alias. Control edges: every operation gets an edge to the block's terminator (latency 0), and calls and barriers get edges from every earlier and to every later operation (LLVM calls these chain or barrier edges).

Critical-path analysis¶

Definition 23.2.8 (Height, depth, slack, critical path)

For a DAG \(G = (V, E, \ell)\) with node latencies \(\mathrm{lat}\):

\[ \begin{aligned} h(v) &= \max\Big(\mathrm{lat}(v),\ \max_{(v, w) \in E} \big(\ell(v, w) + h(w)\big)\Big) && \text{(height)} \\ d(v) &= \max\Big(0,\ \max_{(u, v) \in E} \big(d(u) + \ell(u, v)\big)\Big) && \text{(depth: earliest start, ASAP)} \\ \mathrm{CP}(G) &= \max_{v} h(v), \qquad \mathrm{alap}(v) = \mathrm{CP}(G) - h(v), \qquad \mathrm{slack}(v) = \mathrm{alap}(v) - d(v) \end{aligned} \]

A critical path is a path \(v_0 \to \dots \to v_k\) with \(\sum \ell + \mathrm{lat}(v_k) = \mathrm{CP}(G)\); its nodes have slack 0.

Algorithm 23.2.9 (Heights and depths)

Input: a DAG whose edges go from smaller to larger index.
Output: \(h(v)\) and \(d(v)\) for every \(v\).
Precondition: node indices are a topological order (true for Definition 23.2.4).
Postcondition: the values of Definition 23.2.8.
Invariant: when \(h(v_i)\) is computed, \(h(w)\) is final for every successor \(w\) (they have larger indices); when \(d(v_j)\) is computed, \(d(u)\) is final for every predecessor.

function Heights(G):
    for i from n down to 1:
        h[i] ← max(lat(x_i), max over (i, w) ∈ E of ℓ(i, w) + h[w])
function Depths(G):
    for j from 1 to n:
        d[j] ← max(0, max over (u, j) ∈ E of d[u] + ℓ(u, j))

3. Worked example¶

Dependence-DAG construction¶

Algorithm 23.2.6 on the running block. Each row processes one operation. "uses" shows only the registers that change.

step	op	true edges (from `lastdef`)	anti / output edges	memory edges	`lastdef` / `uses` changes
1	`a: r1 = load A[0]`	—	—	— (first memory op)	lastdef r1 = a
2	`b: r2 = load A[1]`	—	—	a–b: two loads, none	lastdef r2 = b
3	`c: r3 = load B[0]`	—	—	loads only	lastdef r3 = c
4	`d: r4 = mul r1, r2`	a→d 3, b→d 3	—	—	uses r1 = [d], uses r2 = [d]; lastdef r4 = d
5	`e: r5 = add r3, r3`	c→e 3	—	—	uses r3 = [e]; lastdef r5 = e
6	`f: r6 = mul r5, r3`	e→f 1, c→f 3	—	—	uses r5 = [f], uses r3 = [e, f]; lastdef r6 = f
7	`g: r1 = load B[1]`	—	anti d→g 0; output a→g \(\max(1, 3-3+1) = 1\)	loads only	uses r1 = []; lastdef r1 = g
8	`h: store A[r2], r5`	b→h 3 (address), e→h 1 (value)	—	mem-anti a→h 0 (\(A[0]\) vs \(A[r2]\)), b→h 0 (merged into 3); c, g: array B, none	uses r2 = [d, h], uses r5 = [f, h]
9	`i: r7 = sub r6, r1`	f→i 3, g→i 3	—	—	lastdef r7 = i
10	`j: r4 = add r4, r7`	d→j 3, i→j 1	output d→j \(\max(1, 3-1+1) = 3\) (merged with the true edge)	—	lastdef r4 = j

The result has 14 edges. The Mermaid drawing labels each edge with its latency and kind (t = true, a = anti, o = output, m = memory):

flowchart TD
  a[a: load A0] -->|3 t| d[d: mul]
  b[b: load A1] -->|3 t| d
  c[c: load B0] -->|3 t| e[e: add]
  c -->|3 t| f[f: mul]
  e -->|1 t| f
  a -->|1 o| g[g: load B1]
  d -->|0 a| g
  b -->|3 t+m| h[h: store A r2]
  a -->|0 m| h
  e -->|1 t| h
  f -->|3 t| i[i: sub]
  g -->|3 t| i
  d -->|3 t+o| j[j: add]
  i -->|1 t| j
  classDef hl fill:#fde68a,stroke:#b45309;
  class c,e,f,i,j hl;

Algorithm 23.2.5 adds no further edge on this block: r1 and r4 are each defined twice, and each second definition is the next one after the first. On a block with three definitions of the same register, the pairwise algorithm adds the first-to-third output edge, which the table algorithm leaves implied by the chain of adjacent output edges.

Try it

./course drill critical-path --seed 3 --difficulty hard --solution asks for the edges of a random block with register reuse and memory operations, and prints this table for it.

Memory and control dependences¶

Only one memory edge pair matters here: h stores through a register index into A, so it may overwrite A[0] or A[1]. The loads a and b must therefore read before h writes (mem-anti, latency 0). The loads of B are unaffected, because B and A are different arrays. If the store were store A[2], r5, the oracle would answer "no alias" for A[0] and A[1], and the two memory edges would disappear. In C the same distinction is the one between long *A, long *B and long *restrict A, long *restrict B: with restrict the load of B[1] may move above the store to A[...] (the §7 box).

Critical-path analysis¶

Algorithm 23.2.9 on the DAG, heights in reverse order and depths in forward order:

op	lat	\(d\) (ASAP)	\(h\)	alap \(= 9 - h\)	slack	#succs	#preds
a	3	0	8	1	1	3	0
b	3	0	8	1	1	2	0
c	3	0	9	0	0	2	0
d	3	3	5	4	1	2	2
e	1	3	6	3	0	2	1
f	3	4	5	4	0	1	2
g	3	3	5	4	1	1	2
h	1	4	1	8	4	0	3
i	1	7	2	7	0	1	2
j	1	8	1	8	0	0	2

\(h(j) = 1\) and \(h(h) = 1\) (no successors); \(h(i) = 1 + h(j) = 2\); \(h(f) = 3 + h(i) = 5\); \(h(g) = 3 + 2 = 5\); \(h(d) = \max(0 + h(g), 3 + h(j)) = \max(5, 4) = 5\); \(h(e) = \max(1 + h(f), 1 + h(h)) = 6\); \(h(c) = \max(3 + h(e), 3 + h(f)) = 9\); \(h(a) = \max(3 + h(d), 1 + h(g), 0 + h(h)) = 8\); \(h(b) = \max(3 + h(d), 3 + h(h)) = 8\).
\(\mathrm{CP} = 9\) along c → e → f → i → j (\(3 + 1 + 3 + 1 + 1\)). These are exactly the slack-0 nodes (highlighted).
The resource bound of Theorem 23.1.12 is 5 (five memory operations). So no schedule is shorter than \(\max(9, 5) = 9\) (Theorem 23.2.12). Lesson 23.3 finds one of length 10 and shows that 10 is optimal here.

4. Invariants and correctness¶

Dependence-DAG construction¶

The DAG is only useful if every valid schedule computes what the block computes. To state that precisely, fix the timing of Definition 23.1.1 as the cycle-accurate semantics (the lab's simulator, SPEC §7): in each cycle, first the writes that become visible in that cycle are committed, then every operation issued in that cycle reads its operands. Two writes to the same register or location that become visible in the same cycle are an error.

Proposition 23.2.10 (Transitive edges are redundant)

If \(G'\) adds to \(G\) an edge \((u, w)\) with latency \(\ell'\) and \(G\) already contains a path \(u \leadsto w\) whose latencies sum to at least \(\ell'\), then \(G\) and \(G'\) have the same valid schedules. In particular Algorithms 23.2.5 and 23.2.6 define the same set of valid schedules.

Proof

Every schedule valid for \(G'\) is valid for \(G\) (fewer constraints). Conversely, let \(t\) be valid for \(G\) and let \(u = v_0 \to \dots \to v_k = w\) be the path. Summing the edge constraints gives \(t(w) - t(u) \ge \sum_i \ell(v_i, v_{i+1}) \ge \ell'\), so the extra edge holds too. For the second claim, the pairwise algorithm's extra edges are (i) output edges \(x_i \to x_k\) between a definition and a non-adjacent later definition of the same register, implied by the chain of adjacent output edges, whose sum is at least the direct latency because each step contributes at least \(\mathrm{lat}(x_a) - \mathrm{lat}(x_b) + 1\) and these telescope to \(\mathrm{lat}(x_i) - \mathrm{lat}(x_k) + (\text{number of steps})\); (ii) anti edges from a use to a non-next definition, implied by the anti edge to the next definition (latency 0) followed by output edges (latency \(\ge 1\)); (iii) true edges from a definition that does not reach the use: that pair is ordered by the output chain from that definition to the reaching one and the true edge from it, with latencies at least \(\max(1, \cdot)\) and \(\mathrm{lat}\). Memory edges are identical in both algorithms.

Theorem 23.2.11 (Soundness of the dependence DAG)

Let \(t\) be a valid schedule of a block (Definition 23.2.4) whose memory edges come from a conservative oracle. Executing the block in the cycle-accurate semantics with issue times \(t\) raises no write conflict, every operation reads the same values as in sequential program order, and the final contents of every register and memory location equal those of sequential order.

Proof

Registers. Consider a use of \(r\) by \(x_j\) whose reaching definition is \(x_i\) (Definition 23.2.2). (1) \(x_i\)'s write is visible when \(x_j\) reads: the true edge gives \(t_j \ge t_i + \mathrm{lat}(x_i)\). (2) No other write to \(r\) is the latest visible one at \(t_j\). Let \(x_k\) define \(r\), \(k \ne i\). If \(k < i\), the output edges along the definitions of \(r\) between \(k\) and \(i\) give, by Proposition 23.2.10's telescoping, \(t_i + \mathrm{lat}(x_i) > t_k + \mathrm{lat}(x_k)\): \(x_i\)'s write lands strictly later and overwrites. If \(k > j\), let \(x_{k'}\) be the first definition after \(x_j\) (\(k' \le k\)); the anti edge gives \(t_{k'} \ge t_j\), so \(x_{k'}\)'s write is visible at \(t_{k'} + \mathrm{lat} \ge t_j + 1 > t_j\), and the output chain from \(x_{k'}\) to \(x_k\) makes \(x_k\)'s write later still. No \(k\) lies strictly between \(i\) and \(j\) because \(x_i\) reaches the use. Hence \(x_j\) reads \(x_i\)'s value, as in program order. A use with no reaching definition reads the initial value, and the anti edge to the first definition keeps every write invisible at \(t_j\). (3) Two definitions of \(r\) land in different cycles by the strict inequality of the output chain, so there is no write conflict, and the last definition in program order lands last, which gives the final value.

Memory. Every conflicting pair with \(\mathrm{MA}\) true has a memory edge. Pairs that actually access the same location in this execution have \(\mathrm{MA}\) true by conservativeness, so the argument for registers applies verbatim with the pairwise memory edges (a direct edge instead of a chain). Pairs that access different locations cannot interfere.

Induction. The two parts show that each operation reads the same operand values as in program order, provided the earlier operations computed the same values. Induction on program order then gives equal results for every operation and equal final state.

Anti edges are not free to drop

Anti and output dependences are false, but they are not optional. Dropping the anti edge d→g of the running example lets g overwrite r1 before d reads it: the simulator in the lab then computes a wrong r4. Renaming (a fresh register for B[1]) removes the edge legitimately, which is why schedulers prefer to run before register allocation (Lesson 23.8).

Memory and control dependences¶

The memory part of Theorem 23.2.11 needs only one property of the oracle: it never answers "no alias" for two accesses that can touch the same location. A more precise oracle removes edges and never adds any. So precision can only help schedule quality, and soundness needs only conservativeness. Control edges to the terminator keep the block a block: the branch still ends it and reads the condition after it is computed. The barrier edges keep calls, which may read or write any memory, in order with every memory access. LLVM uses the same argument for its chain edges.

Critical-path analysis¶

Theorem 23.2.12 (Critical-path lower bound)

For every valid schedule \(t\) of a block, \(t(v) \ge d(v)\) for all \(v\) and \(L(t) \ge t(v) + h(v) \ge \mathrm{CP}(G)\) for every \(v\). With unlimited resources, \(t = d\) is valid and \(L(d) = \mathrm{CP}(G)\).

Proof

Depth, by induction in index (topological) order: a node without predecessors has \(d = 0 \le t\); otherwise \(t(v) \ge t(u) + \ell(u, v) \ge d(u) + \ell(u, v)\) for every predecessor, so \(t(v) \ge d(v)\). Height, by induction in reverse order: if \(v\) has no successors, \(h(v) = \mathrm{lat}(v)\) and \(L(t) \ge t(v) + \mathrm{lat}(v)\) by the definition of length. Otherwise, for the successor \(w\) attaining the maximum, \(L(t) \ge t(w) + h(w) \ge t(v) + \ell(v, w) + h(w) = t(v) + h(v)\), and also \(L(t) \ge t(v) + \mathrm{lat}(v)\). Taking \(v\) with \(h(v) = \mathrm{CP}\) and \(t(v) \ge 0\) gives \(L(t) \ge \mathrm{CP}\). Tightness: with no resource constraints only the edge constraints matter, and \(d(w) \ge d(v) + \ell(v, w)\) by definition, so \(t = d\) is valid. Its length is \(\max_v (d(v) + \mathrm{lat}(v))\), and every \(d(v) + \mathrm{lat}(v)\) is the latency of a path ending in \(v\), hence at most \(\mathrm{CP}\); a path attaining \(\mathrm{CP}\) gives equality.

Corollary 23.2.13 (The combined bound)

Every valid schedule satisfies \(L(t) \ge \max\big(\mathrm{CP}(G),\ \max_r \lceil U_r / \mathrm{cap}(r) \rceil\big)\).

Proof

The first term is Theorem 23.2.12. For the second, every occupied cycle of \(r\) lies in \([0, L(t))\) because \(\mathrm{occ} \le \mathrm{lat}\) (Definition 23.1.2), so \(U_r \le \mathrm{cap}(r) \cdot L(t)\); \(L(t)\) is an integer, so \(L(t) \ge \lceil U_r / \mathrm{cap}(r) \rceil\).

5. Complexity¶

Let \(n\) be the number of operations, \(m\) the number of memory operations, \(e\) the number of edges and \(k\) the maximum number of registers an operation touches.

Technique	Time (worst)	Time (typical)	Space	Edges produced
Pairwise construction (Alg. 23.2.5)	\(\Theta(n^2 k)\)	\(\Theta(n^2)\)	\(O(n^2)\)	all conflicting pairs, up to \(\binom{n}{2}\)
Table-driven (Alg. 23.2.6)	\(O(nk + e + m^2)\)	linear plus memory pairs	\(O(n + e)\)	reaching/next only for registers; \(O(m^2)\) memory
Heights and depths (Alg. 23.2.9)	\(O(n + e)\)	\(O(n + e)\)	\(O(n)\)	—

Justification. The pairwise algorithm examines each of the \(\binom{n}{2}\) pairs and intersects register sets of size \(\le k\). The table algorithm touches each operand once. Each anti edge is added once, from a use to the next definition, and each use is cleared after it. The memory loop compares each memory operation with all earlier ones: \(O(m^2)\). Heights and depths visit each edge once in (reverse) topological order.

Pathological family. A block of \(m\) stores through register indices followed by \(m\) loads through register indices, all into the same array: every (store, load) pair and every (store, store) pair may alias, so there are \(m^2 + \binom{m}{2}\) memory edges, \(\Theta(m^2)\), whatever algorithm builds them. With \(m = 5000\) that is 37 million edges. Real compilers cap this. LLVM's buildSchedGraph counts the memory operations it has processed and, every -dag-maps-huge-region of them (default 500), makes the current instruction a barrier chain that all pending loads and stores are ordered against, then clears its maps [LLVM-SDInstrs]. GCC limits the pending lists with --param max-pending-list-length (default 32) [GCC-sched-deps].

Dependence-DAG construction¶

Backward construction (LLVM buildSchedGraph, [GM86]): walk from the last instruction up, keeping per-register maps of later uses and defs. Same edges, and a natural fit for bottom-up schedulers, which want successors first.
Transitive reduction (Proposition 23.2.10 in general): remove every edge implied by a path. This gives fewer edges and cheaper ready-list updates, but the reduction itself costs up to \(O(ne)\), so production compilers only avoid adding obvious ones.
Subregister and lane masks (LLVM): a use of a 32-bit subregister depends only on writes that overlap its lanes. It is more precise on x86 and AArch64, at the cost of per-lane bookkeeping.

Memory and control dependences¶

Alias-analysis-based chains (-enable-aa-sched-mi, -use-tbaa-in-sched-mi in LLVM): query AAResults for pairs of MachineInstrs with memory operands. This removes edges in loops of pointer code, but each query costs time, which is why it is off by default on most targets.
Speculative loads and data speculation (IA-64 ld.a/chk.a, advanced loads): let a load move above a possibly aliasing store and check afterwards. This needs hardware support.
Control speculation across blocks (Lessons 23.4–23.5): what a basic-block scheduler cannot do, region schedulers do with compensation code or predication.

Critical-path analysis¶

Resource-aware heights: add the operation's occupancy of the most-used unit to break ties. This is used in LLVM's SchedBoundary as "resource pressure".
Cyclic critical path (-misched-cyclicpath in LLVM): for loop bodies, the latency of the loop-carried recurrence, which is the RecMII of Lesson 23.6 applied to list scheduling.
ALAP and mobility-based priorities (force-directed scheduling in high-level synthesis, Paulin and Knight 1989): schedule by slack, which balances resource use over time instead of racing along the critical path.

7. In real compilers¶

Dependence-DAG construction¶

LLVM builds the DAG of a scheduling region in ScheduleDAGInstrs::buildSchedGraph (llvm/lib/CodeGen/ScheduleDAGInstrs.cpp), walking bottom-up with Defs/Uses maps (addPhysRegDeps, addVRegDefDeps, addVRegUseDeps) and SDep edges of kind Data, Anti, Output and Order (llvm/include/llvm/CodeGen/ScheduleDAG.h) [LLVM-SDInstrs, LLVM-ScheduleDAG]. GCC builds its dependence lists in gcc/sched-deps.cc (sched_analyze, add_dependence) [GCC-sched-deps].

GCC's dependence DAG for the running example in C

Reproduce (gcc 14.2.0 on x86-64 Linux; the dump name contains the pass number):

cat > run.c <<'EOF'
long run(long *A, long *B) {
  long r4 = A[0] * A[1];
  long r5 = B[0] + B[0];
  long r6 = r5 * B[0];
  A[A[1] & 7] = r5;
  return r4 + (r6 - B[1]);
}
EOF
gcc-14 -O2 -fschedule-insns -fsched-verbose=6 -fdump-rtl-sched1-details -c run.c -o run.o
sed -n '/Region Dependences/,/nothing/p' run.c.*r.sched1

Output (complete; the dump is run.c.312r.sched1 with gcc 14.2.0):

;;   --- Region Dependences --- b 2 bb 0 
;;      insn  code    bb   dep  prio  cost   reservation
;;      ----  ----    --   ---  ----  ----   -----------
;;       23    84     2     0     7     1   hsw_decodern,hsw_p0156  : 20 2 
;;        2    84     2     1     6     1   hsw_decodern,hsw_p0156  : 20 12 8 7 
;;       24    84     2     0     7     1   hsw_decodern,hsw_p0156  : 20 3 
;;        3    84     2     1     6     1   hsw_decodern,hsw_p0156  : 20 14 9 
;;        7    84     2     1     5     2   hsw_decodern,hsw_p23    : 20 12n 11 8 
;;        8   521     2     2     4     3   hsw_decodern,(hsw_p23+hsw_p1)   : 20 15 12n 
;;        9    84     2     1     5     2   hsw_decodern,hsw_p23    : 20 13 12n 10 
;;       10   912     2     1     3     1   hsw_decodern,hsw_p1|hsw_p5  : 20 13 12 
;;       11   613     2     1     3     1   hsw_decodern,hsw_p0156  : 20 12 
;;       12    84     2     6     2     3   hsw_decodern,(hsw_p4+(hsw_p2|hsw_p3|hsw_p7))    : 20 14n 
;;       13   521     2     2     2     3   hsw_decodern,hsw_p1 : 20 14 
;;       14   362     2     3     2     1   hsw_decodern,(hsw_p23+hsw_p0156)    : 20 15 
;;       15   272     2     2     1     1   hsw_decodern,hsw_p1|hsw_p5  : 20m 
;;       20    84     2    13     0     1   hsw_decodern,hsw_p0156  : 21 
;;       21    -1     2     1     0     0   nothing :

What to notice: each row is an RTL instruction with its number of predecessors (dep), its critical-path priority (prio, the height of Definition 23.2.8 in GCC's latency units), its latency (cost), its reservation (Lesson 23.1) and its successor list. The store is insn 12 ([r113*0x8+r111]=r107, the running block's h). The loads 7 (A[1]), 8 (the A[0] operand folded into the multiply) and 9 (B[0]) have a successor 12n: n marks a non-register, here memory, dependence. That is the mem-anti edge of the worked example, because the store's index is unknown. Insn 12 in turn has 14n: the load of B[1] inside sub may not move above the store, because without restrict A and B may overlap. Every insn has an edge to 20, the copy into the return register ax: GCC's add_branch_dependences keeps likely-spilled hard-register sets at the end of the block (a control dependence, Definition 23.2.7). GCC 15 also marks true dependences with a t.

Memory and control dependences¶

In buildSchedGraph, memory operations go through Stores/Loads maps keyed by underlying objects (getUnderlyingObjectsForInstr), with BarrierChain for calls and ordered memory references. MachineInstr::mayAlias answers pair queries, using alias analysis only with -enable-aa-sched-mi [LLVM-SDInstrs]. GCC's control edges are added by add_branch_dependences in gcc/sched-rgn.cc [GCC-sched-rgn].

restrict removes a memory edge (AArch64)

Reproduce (clang 23.1.2, llc 23.1.2; run.c from the previous box):

sed 's/long \*A, long \*B/long *restrict A, long *restrict B/' run.c > run-r.c
for f in run run-r; do
  clang-23 --target=aarch64-linux-gnu -O2 -S -emit-llvm $f.c -o $f.ll
  echo "== $f"
  llc -O2 -mtriple=aarch64-linux-gnu -mcpu=neoverse-v2 -misched-dcpl $f.ll -o /dev/null 2>&1
  llc -O2 -mtriple=aarch64-linux-gnu -mcpu=neoverse-v2 $f.ll -o - \
    | grep -E '^\s+(ldr|ldp|str|madd|neg|lsl|and|mov)\b'
done

Output (complete):

== run
run:%bb. 0  
Critical Path(GS-RR ): 16 
run:%bb. 0  
Critical Path(PGS-RR ): 15 
    ldp x12, x8, [x0]
    ldr x9, [x1]
    lsl x10, x9, #1
    and x11, x8, #0x7
    str x10, [x0, x11, lsl #3]
    ldr x11, [x1, #8]
    neg x11, x11
    madd    x8, x8, x12, x11
    madd    x0, x10, x9, x8
== run-r
run:%bb. 0  
Critical Path(GS-RR ): 12 
run:%bb. 0  
Critical Path(PGS-RR ): 11 
    ldp x9, x10, [x0]
    mov x8, x0
    ldp x12, x11, [x1]
    neg x11, x11
    madd    x9, x10, x9, x11
    lsl x11, x12, #1
    madd    x0, x11, x12, x9
    and x9, x10, #0x7
    str x11, [x8, x9, lsl #3]

What to notice: without restrict, ldr x11, [x1, #8] (B[1]) must follow the store str (a memory true edge). With restrict there is no edge: B[0] and B[1] are loaded together by one ldp at the top, and the store sinks to the end. -misched-dcpl prints the critical path that the pre-RA (GS, GenericScheduler) and post-RA (PGS) schedulers computed on their DAGs: removing the store→load edge shortens it from 16 to 12 cycles (Theorem 23.2.12's bound).

Critical-path analysis¶

LLVM computes depths and heights lazily (SUnit::getDepth, SUnit::getHeight in llvm/lib/CodeGen/ScheduleDAG.cpp) and uses them in GenericScheduler::tryCandidate through tryLatency [LLVM-ScheduleDAG, LLVM-MISched]. -misched-dcpl prints the critical path of each region. GCC computes INSN_PRIORITY in priority() (gcc/haifa-sched.cc) as the longest latency-weighted path to the end of the region [GCC-haifa].

The critical path in llvm-mca's timeline

Reproduce (clang 23.1.2, llc 23.1.2, llvm-mca 23.1.2; run.c from the first box):

clang-23 --target=x86_64-linux-gnu -O2 -S -emit-llvm run.c -o run-x86.ll
llc -O2 -mtriple=x86_64-linux-gnu -mcpu=skylake -misched-dcpl run-x86.ll -o - \
  | sed -n '/^# %bb.0/,/retq/p' | grep -v '^#\|retq' > run-body.s
llvm-mca -mtriple=x86_64-linux-gnu -mcpu=skylake -iterations=1 -timeline -noalias=false \
  -instruction-info=false -resource-pressure=false run-body.s | grep '^\[0,'

Output (complete; -misched-dcpl writes to standard error, which the pipe does not capture):

[0,0]     DeeeeeER  .    . .   movq 8(%rdi), %rcx
[0,1]     DeeeeeER  .    . .   movq (%rdi), %rax
[0,2]     D=====eeeER    . .   imulq    %rcx, %rax
[0,3]     D=eeeeeE--R    . .   movq (%rsi), %rdx
[0,4]     D======eE-R    . .   leaq (%rdx,%rdx), %r8
[0,5]     D=======eeeER  . .   imulq    %r8, %rdx
[0,6]     .D====eE----R  . .   andl $7, %ecx
[0,7]     .D======eE--R  . .   movq %r8, (%rdi,%rcx,8)
[0,8]     .D=======eeeeeeER.   subq 8(%rsi), %rax
[0,9]     .D=============eER   addq %rdx, %rax

What to notice: with -noalias=false llvm-mca orders loads after earlier stores, like the compiler's DAG. The last instruction retires at cycle 17 of the timeline, after the chain movq 8(%rdi) (5) → andl → store → subq 8(%rsi) (a load, then the subtraction) → addq. Each = is a cycle spent waiting for an operand: the waits line up along the critical path of Definition 23.2.8. The Critical Path(GS-RR ): 16 line that -misched-dcpl prints (dropped by the filter; run llc alone to see it) is the same chain measured on the scheduler's DAG.

8. Comparison¶

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

Choose table-driven construction always, unless the block is tiny. It produces the same schedules with fewer edges. Invest in memory precision when loads and stores of different objects interleave, as in pointer-heavy loops. A bad alias answer costs more ILP than any priority function recovers. Use heights as the default priority, and as the bound against which to judge a schedule.

9. Assessment¶

Quiz: dag-edges-running (set of edges), edge-latency-output (number), soundness-anti (single), heights-running (mapping), cp-bound (number), find-buildschedgraph (text: ScheduleDAGInstrs). Tags dag-construction, memory-dependences, critical-path.
Drills: ./course drill critical-path (easy/medium: heights, CP and a critical path from a DAG; hard: build the DAG of a block with register reuse and memory, then heights).
Flashcards: tags dag-construction, memory-dependences, critical-path.
Lab: E1 in exercises builds the canonical DAG (SPEC §5.1); the lab's goldens only match if every edge and latency is right.

References¶

See the chapter references.

op	lat	\(d\) (ASAP)	\(h\)	alap \(= 9 - h\)	slack	#succs	#preds
a	3	0	8	1	1	3	0
b	3	0	8	1	1	2	0
c	3	0	9	0	0	2	0
d	3	3	5	4	1	2	2
e	1	3	6	3	0	2	1
f	3	4	5	4	0	1	2
g	3	3	5	4	1	1	2
h	1	4	1	8	4	0	3
i	1	7	2	7	0	1	2
j	1	8	1	8	0	0	2

op	lat	\(d\) (ASAP)	\(h\)	alap \(= 9 - h\)	slack	#succs	#preds
a	3	0	8	1	1	3	0
b	3	0	8	1	1	2	0
c	3	0	9	0	0	2	0
d	3	3	5	4	1	2	2
e	1	3	6	3	0	2	1
f	3	4	5	4	0	1	2
g	3	3	5	4	1	1	2
h	1	4	1	8	4	0	3
i	1	7	2	7	0	1	2
j	1	8	1	8	0	0	2

Lesson 23.2 — Dependence DAGs: true, anti, output, memory and control dependences¶

1. Problem and motivation¶

Dependence-DAG construction¶

Memory and control dependences¶

Critical-path analysis¶

2. Definitions and algorithms¶

Dependence-DAG construction¶

Memory and control dependences¶

Critical-path analysis¶

3. Worked example¶

Dependence-DAG construction¶

Memory and control dependences¶

Critical-path analysis¶

4. Invariants and correctness¶

Dependence-DAG construction¶

Memory and control dependences¶

Critical-path analysis¶

5. Complexity¶

6. Variants and refinements¶

Dependence-DAG construction¶

Memory and control dependences¶

Critical-path analysis¶

7. In real compilers¶

Dependence-DAG construction¶

Memory and control dependences¶

Critical-path analysis¶

8. Comparison¶

9. Assessment¶

References¶

op	lat	\(d\) (ASAP)	\(h\)	alap \(= 9 - h\)	slack	#succs	#preds
a	3	0	8	1	1	3	0
b	3	0	8	1	1	2	0
c	3	0	9	0	0	2	0
d	3	3	5	4	1	2	2
e	1	3	6	3	0	2	1
f	3	4	5	4	0	1	2
g	3	3	5	4	1	1	2
h	1	4	1	8	4	0	3
i	1	7	2	7	0	1	2
j	1	8	1	8	0	0	2