Lesson 14.4 — Iterative solvers: round-robin, worklists and bit vectors¶

Techniques: round-robin (chaotic) iteration in reverse postorder and in postorder; worklist algorithms (FIFO, LIFO, priority by RPO, SCC-ordered); bit-vector implementations · Pebble implements: all five strategies of pebble::dataflow::solve (exercise E1) · Lab: ch14-solverbench Parts 1–2 (labs/ch14-dataflow) · Prerequisites: Lesson 14.2, Lesson 14.3, DFS orders (Ch 15, Lesson 15.1) · Time: 5–7 hours

Kildall's algorithm leaves one thing open: in which order to visit nodes. The fixed point does not depend on it (Theorem 14.4.4), but the cost does, dramatically. Liveness on the running example needs 18 block evaluations with round-robin in reverse postorder, 24 in postorder, 9 with a FIFO worklist and 8 with a worklist ordered by RPO. On a 1024-block loop the postorder sweep needs 1 049 600 evaluations where reverse postorder needs 3 072 (ch14-solverbench, Part 2). This lesson explains why, proves the Kam–Ullman \(d(G) + 2\) bound, and shows how production solvers make each evaluation cheap with bit vectors.

1. Problem and motivation¶

Given an instance of a monotone framework, compute its MFP solution (Definition 14.2.9) with as few transfer-function evaluations as possible, each as cheap as possible.

Round-robin iteration¶

The oldest strategy: sweep all nodes in a fixed order, recompute each from the newest values, repeat until a sweep changes nothing. Allen and Cocke's and Hecht and Ullman's analyses used it [AC76, HU75]; Kam and Ullman proved that for "rapid" frameworks such as bit-vector problems, sweeping in reverse postorder converges within \(d(G) + 2\) passes, where \(d(G)\) is the loop connectedness; the studies of real programs that the Dragon book reports find it rarely above 3 [Dragon2, §9.6]. Its simplicity keeps it alive: LLVM's StackLifetime still sweeps in a fixed order, with a TODO: Consider switching to worklist in its source [LLVM-SL].

Worklist algorithms¶

Round-robin re-evaluates nodes whose inputs have not changed. A worklist keeps only the nodes that may have to change [Kil73]. The data structure decides the order: a FIFO queue (rustc seeds its WorkQueue in RPO and then works first-in first-out), a stack, a priority queue keyed by RPO (Clang's ForwardDataflowWorklist), or, for analyses with widening, Bourdoncle's weak topological order over strongly connected components [Bou93] (Clang's WTODataflowWorklist).

Bit-vector implementations¶

When the lattice is a powerset of \(k\) facts, a set is a \(k\)-bit vector: union is OR, intersection AND, difference AND-NOT, and a gen/kill transfer function is two word operations per 64 facts. This is why the classic analyses were affordable on 1970s machines and why GCC's RTL dataflow framework (gcc/df-core.cc) still represents live registers as bitmaps [GCC-DF].

2. Definitions and algorithms¶

Visiting order

For an instance on a graph with nodes \(0, \dots, n-1\), the direction graph is \(G\) for a forward problem and \(G^{R}\) for a backward one. Its reverse postorder \(\mathrm{rpo}\) is computed by a depth-first search from each boundary node in turn, then from each node not reached yet, following successors (forward) or predecessors (backward) in listed order; each search tree's reverse postorder is appended in the order the searches started. This is directionOrder in Dataflow.h; on a forward problem whose nodes are all reachable it is the RPO of Ch 15. Dependents of a node are its successors (forward) or predecessors (backward). A node's output is OUT (forward) or IN (backward).

Round-robin iteration¶

Algorithm 14.4.1 (Round-robin iteration)

Input: an instance (Definition 14.2.4) and an order \(\pi\) of all nodes (RPO, or postorder = RPO reversed).
Output: IN and OUT for every node; the number of passes.
Precondition: monotone transfer functions; \(L\) satisfies ACC.
Postcondition: IN/OUT is the MFP solution (Theorem 14.4.4).
Invariant: every value is below its MFP value (Lemma 14.4.3); after a pass with changed = false, every equation holds.

function RoundRobin(instance, π):
    for n in N: IN[n] ← Init; OUT[n] ← Init
    passes ← 0
    repeat
        changed ← false
        passes ← passes + 1
        for n in π:                                    # in place: uses values of this pass
            if Visit(n): changed ← true
    until not changed
    return IN, OUT, passes

function Visit(n):                                     # forward version; backward swaps IN/OUT
    x ← Init
    if n is a boundary node: x ← x ⊔ BoundaryFact
    for p in preds(n): x ← x ⊔ EdgeTransfer(p, n, OUT[p])
    IN[n] ← x
    y ← f_n(IN[n])
    if y = OUT[n]: return false
    OUT[n] ← y
    return true

Round-robin with bit vectors in LLVM: StackLifetime

Reproduce (clang 23.1.2, opt 23.1.2):

cat > sl.c <<'EOF'
void use(int *);
void f(int c) {
  if (c) {
    int a;
    use(&a);
  } else {
    int b;
    use(&b);
  }
}
EOF
clang-23 -O1 -fno-discard-value-names -S -emit-llvm sl.c -o sl.ll
opt -passes='print<stack-lifetime><may>' -disable-output sl.ll 2>&1 | grep -E '^[a-z.]+:|Alive: <[ab]>|lifetime'

Output:

entry:
if.then:                                          ; preds = %entry
  call void @llvm.lifetime.start.p0(ptr nonnull %a) #3
  ; Alive: <a>
  ; Alive: <a>
  call void @llvm.lifetime.end.p0(ptr nonnull %a) #3
if.else:                                          ; preds = %entry
  call void @llvm.lifetime.start.p0(ptr nonnull %b) #3
  ; Alive: <b>
  ; Alive: <b>
  call void @llvm.lifetime.end.p0(ptr nonnull %b) #3
if.end:                                           ; preds = %if.else, %if.then

What to notice: StackLifetime computes, per stack slot, whether it may be alive at each point — a forward may-analysis with lifetime.start as gen and lifetime.end as kill. Its calculateLocalLiveness (llvm/lib/Analysis/StackLifetime.cpp) [LLVM-SL] is Algorithm 14.4.1 over BitVectors (BitsIn |= LiveOut of each predecessor, while (Changed) over all blocks). The result shows %a and %b never alive at the same point, so stack coloring may give them one slot.

Worklist algorithms¶

Algorithm 14.4.2 (Worklist iteration)

Input: an instance; a discipline: FIFO queue, LIFO stack, or priority by \(\mathrm{rpo}\) number.
Output: IN and OUT for every node; the number of evaluations.
Precondition: as Algorithm 14.4.1.
Postcondition: IN/OUT is the MFP solution (Theorem 14.4.4).
Invariant: Lemma 14.4.3; every node whose equation may be violated is in \(W\).

function Worklist(instance, discipline):
    for n in N: IN[n] ← Init; OUT[n] ← Init
    W ← all nodes, arranged so that the first removal is rpo[0]:
          FIFO: queue rpo[0], rpo[1], ...;  LIFO: stack with rpo[0] on top;  priority: the set N
    evals ← 0
    while W ≠ ∅:
        n ← Remove(W)            # FIFO: front; LIFO: top; priority: the smallest rpo number
        evals ← evals + 1
        if Visit(n):             # output changed
            for d in dependents(n), in listed order (LIFO: reversed, so the first is on top):
                if d ∉ W: Insert(W, d)
    return IN, OUT, evals

Visit is the function of Algorithm 14.4.1. With a priority queue, a node re-inserted by a back edge waits until everything earlier in RPO has been processed; this is the order Clang uses (ReversePostOrderCompare in DataflowWorklist.h) [CLANG-DFW].

GCC's worklist solver counts its block visits

Reproduce (gcc 14.2.0, x86-64 Linux):

cat > live.c <<'EOF'
int sum(int n) {
  int s = 0, i = 0, dead = 7;
  while (i < n) {
    s = s + i;
    i = i + 1;
  }
  dead = s;
  return s;
}
EOF
gcc-14 -O2 -fdump-rtl-all-details -c live.c -o /dev/null
cat live.c.*r.* | grep df_worklist_dataflow_doublequeue | sort | uniq -c

Output:

      5 df_worklist_dataflow_doublequeue: n_basic_blocks 10 n_edges 13 count 10 (    1)
      7 df_worklist_dataflow_doublequeue: n_basic_blocks 10 n_edges 13 count 11 (  1.1)
      1 df_worklist_dataflow_doublequeue: n_basic_blocks 7 n_edges 8 count 7 (    1)
      1 df_worklist_dataflow_doublequeue: n_basic_blocks 7 n_edges 8 count 8 (  1.1)
      7 df_worklist_dataflow_doublequeue: n_basic_blocks 8 n_edges 11 count 8 (    1)
      9 df_worklist_dataflow_doublequeue: n_basic_blocks 8 n_edges 11 count 9 (  1.1)
      6 df_worklist_dataflow_doublequeue: n_basic_blocks 8 n_edges 9 count 3 ( 0.38)
      3 df_worklist_dataflow_doublequeue: n_basic_blocks 8 n_edges 9 count 4 (  0.5)
      1 df_worklist_dataflow_doublequeue: n_basic_blocks 9 n_edges 12 count 10 (  1.1)
      2 df_worklist_dataflow_doublequeue: n_basic_blocks 9 n_edges 12 count 9 (    1)

What to notice: every RTL pass that needs dataflow facts calls df_analyze, which solves each problem (live registers, reaching definitions, ...) with df_worklist_dataflow_doublequeue (gcc/df-core.cc) [GCC-DF] — Algorithm 14.4.2 with the worklist ordered by postorder index. count is the number of block evaluations and the parenthesized number evaluations per block (the entry and exit blocks included in n_basic_blocks). Across 42 solves of this loop the solver needs between 0.38 and 1.1 evaluations per block: the worklist visits only blocks whose inputs changed (count 3 of 8 is an incremental re-solve), where round-robin would pay at least two full passes.

Correctness and the Kam–Ullman bound¶

Lemma 14.4.3 (Solver invariant)

Throughout both algorithms, \(\mathrm{IN}[n] \sqsubseteq \mathrm{MFP}_{\mathrm{in}}(n)\) and \(\mathrm{OUT}[n] \sqsubseteq \mathrm{MFP}_{\mathrm{out}}(n)\) for every node; each value only grows; and in Algorithm 14.4.2 every node \(m\) for which \(\mathrm{IN}[m] \neq\) (right-hand side of its equation evaluated on the current OUTs) is in \(W\).

Proof

Below MFP (induction on the number of Visit calls): initially all values are \(\mathrm{Init} = \bot\). Visit(n) computes the right-hand side of \(n\)'s equations from values that are below MFP by the induction hypothesis; by monotonicity of \(\sqcup\), the edge functions and \(f_n\), the results are below the right-hand side evaluated at MFP, which equals MFP. Growth: by induction the IN values form an ascending sequence (each new IN is a join of OUTs that only grew, by monotonicity), and so do OUTs. Worklist: initially every node is in \(W\). Visiting \(n\) makes \(n\)'s equation hold; the right-hand side of \(m\)'s equation can only change when an OUT it reads changes, i.e. when a predecessor (forward) of \(m\) changed its output — and then Visit inserts all dependents, \(m\) among them. \(\square\)

Theorem 14.4.4 (Every strategy computes MFP)

For every instance satisfying the precondition, Algorithms 14.4.1 (any order \(\pi\)) and 14.4.2 (any discipline) terminate and return exactly the MFP solution. The order affects only the number of evaluations.

Proof

Termination: by Lemma 14.4.3 every value ascends in \(L\), which satisfies ACC; each evaluation that reports a change strictly increases one OUT, so only finitely many evaluations report a change. A round-robin pass without change ends Algorithm 14.4.1; Algorithm 14.4.2 removes one node per iteration and inserts only after a change, so \(W\) empties after finitely many iterations. Result: at termination every equation holds — after the unchanged pass (round-robin, each node was visited with the final values of its inputs) or when \(W = \emptyset\) (worklist, by the invariant). So the result is a fixed point of \(\mathcal{E}\), hence \(\sqsupseteq \mathrm{MFP}\) (the least fixed point), and by Lemma 14.4.3 \(\sqsubseteq \mathrm{MFP}\): equal. \(\square\)

Definition 14.4.5 (Loop connectedness; rapid frameworks)

Fix a DFS spanning tree \(T\) of the direction graph \(G\) (the one defining \(\mathrm{rpo}\)). An edge \(u \to v\) is retreating if \(\mathrm{rpo}(v) \le \mathrm{rpo}(u)\) (\(v\) is an ancestor of \(u\) in \(T\) for reducible graphs: a back edge). The loop connectedness \(d(G, T)\) is the largest number of retreating edges on any cycle-free path of \(G\). A monotone framework is rapid if \(f(x) \sqsubseteq x \sqcup f(\bot)\) for every \(f \in \mathcal{F}\) and \(x \in L\) (Kam and Ullman's condition \(f(\top) \wedge x \le f(x)\) in their orientation [KU76]).

Theorem 14.4.6 (Kam–Ullman: \(d + 2\) passes)

For a rapid framework, Algorithm 14.4.1 in reverse postorder terminates after at most \(d(G, T) + 2\) passes, the last of which changes nothing.

Proof for gen/kill frameworks (the general rapid case: [KU76])

We prove the bound for gen/kill frameworks, the case every classic analysis and the course tests use; Kam and Ullman's proof for arbitrary rapid frameworks is longer [KU76]. Step 1 (witness paths are cycle-free). Take a may problem (\(\cup\)). In the least fixed point, a fact \(x\) is in \(\mathrm{OUT}[n]\) iff there is a path \(g = m_0 \to m_1 \to \cdots \to m_k = n\) such that \(x \in \mathrm{gen}[g]\) (or \(g\) is a boundary node and \(x\) is in the boundary fact) and \(x \notin \mathrm{kill}[m_i]\) for \(1 \le i \le k\) without being regenerated — the set so defined satisfies the equations and is contained in every solution (induction on \(k\)). If such a path repeats a node, cut out the cycle between the two occurrences: the remaining path has a subset of the nodes, hence no new kills, and is still a witness. So every fact of the fixed point has a cycle-free witness path, which by Definition 14.4.5 has at most \(d = d(G, T)\) retreating edges. For a must problem (\(\cap\), facts disappear from \(U\)) the same argument applies to the absence of \(x\), whose witness starts at a node that kills \(x\) (or at the boundary) and ends at \(n\). Step 2 (one pass per retreating edge). A pass in RPO carries information along every sequence of advancing edges (edges from smaller to larger rpo number) in one sweep, because each node is visited after all its advancing predecessors. A witness with \(j\) retreating edges splits into \(j + 1\) advancing segments; \(g\) produces \(x\) at its first visit, so \(x\) arrives at \(n\) by pass \(j + 1 \le d + 1\). Hence after \(d + 1\) passes every value equals its fixed-point value (values never exceed it, Lemma 14.4.3), and pass \(d + 2\) observes no change. The course test ch14.DataflowSolver.RoundRobinRPOWithinLoopConnectednessPlusTwo checks the bound on 200 random CFGs, and tools/course/tests/test_dataflow.py checks that it is attained.

Lemma 14.4.7 (Gen/kill frameworks are rapid)

\(f(X) = G \cup (X \setminus K)\) satisfies \(f(X) \subseteq X \cup f(\emptyset)\); the same holds in the dual order (\(\cap\)-join) for must problems.

Proof

\(f(\emptyset) = G\), and \(G \cup (X \setminus K) \subseteq G \cup X\). Dually, with join \(\cap\) and \(\bot = U\): \(f(U) = G \cup (U \setminus K)\) and \(X \cap f(U) \subseteq G \cup (X \setminus K) = f(X)\), because an element of \(X \cap f(U)\) is in \(G\) or in \(X \setminus K\). \(\square\)

Bit-vector implementations¶

Algorithm 14.4.8 (Word-parallel gen/kill transfer and join)

Input: sets over a universe of \(k\) facts numbered \(0..k-1\), stored as arrays of \(W = \lceil k / w \rceil\) words of \(w\) bits (fact \(j\) is bit \(j \bmod w\) of word \(\lfloor j / w \rfloor\)).
Output: \(G \cup (X \setminus K)\), and \(X \cup Y\) or \(X \cap Y\).
Precondition: all arrays have \(W\) words; bits above \(k\) are zero.
Postcondition: the result encodes the set operation exactly.
Invariant: after processing word \(i\), words \(0..i\) of the result are correct.

function GenKill(G, K, X):
    for i in 0 .. W-1:
        R[i] ← G[i] OR (X[i] AND NOT K[i])
    return R

function Join(X, Y, may):
    for i in 0 .. W-1:
        R[i] ← (X[i] OR Y[i]) if may else (X[i] AND Y[i])
    return R

The solution's solutions/pebble/lib/Analysis/Dataflow/BitSet.h implements exactly these on Fact (a vector of 64-bit words). Pebble's liveness (E2) numbers the SSA values and uses them as bit positions.

Proposition 14.4.9 (Bit-vector cost)

One transfer or join costs \(\Theta(\lceil k / w \rceil)\) word operations; a round-robin solution of a bit-vector problem costs \(O((d + 2)(n + e) \lceil k / w \rceil)\) word operations.

Proof

Each loop of Algorithm 14.4.8 does a constant number of word operations per word. A pass visits \(n\) nodes and joins over \(e\) edges; Theorem 14.4.6 and Lemma 14.4.7 bound the passes by \(d + 2\). \(\square\)

Bit vectors and a worklist in GCC's RTL dataflow framework

Reproduce (gcc 14.2.0, x86-64 Linux):

cat > live.c <<'EOF'
int sum(int n) {
  int s = 0, i = 0, dead = 7;
  while (i < n) {
    s = s + i;
    i = i + 1;
  }
  dead = s;
  return s;
}
EOF
gcc-14 -O2 -fdump-rtl-cse1-details -c live.c -o /dev/null
grep -E 'lr out|df_worklist' live.c.*r.cse1

Output:

df_worklist_dataflow_doublequeue: n_basic_blocks 7 n_edges 8 count 7 (    1)
processing block 6 lr out =  0 [ax] 6 [bp] 7 [sp] 16 [argp] 19 [frame]
processing block 4 lr out =  6 [bp] 7 [sp] 16 [argp] 19 [frame] 98 99 100
processing block 3 lr out =  6 [bp] 7 [sp] 16 [argp] 19 [frame] 98 99 100
processing block 5 lr out =  6 [bp] 7 [sp] 16 [argp] 19 [frame] 99
processing block 2 lr out =  6 [bp] 7 [sp] 16 [argp] 19 [frame] 100
df_worklist_dataflow_doublequeue: n_basic_blocks 7 n_edges 8 count 8 (  1.1)

What to notice: lr out is GCC's live-registers set at the end of each block, a bitmap indexed by register number (hard registers 0–91, pseudo-registers 98–100 for s, i, n): Algorithm 14.4.8's representation. The lines come from dead-code elimination, a liveness client. df_worklist_dataflow_doublequeue (gcc/df-core.cc) is GCC's worklist solver (two worklists of blocks indexed by postorder position, Algorithm 14.4.2): count 7 for 7 blocks means every block was evaluated exactly once — the loop converged without a second visit — and count 8 means one block was visited twice.

3. Worked example¶

The running example of Lesson 14.3 (blocks \(A\)–\(F\), successors in diagram order). For liveness (backward) the direction graph is the reverse CFG: \(\mathrm{rpo} = F\,B\,E\,D\,C\,A\) and postorder \(= A\,C\,D\,E\,B\,F\); dependents are predecessors. For reaching definitions (forward): \(\mathrm{rpo} = A\,B\,F\,C\,D\,E\).

flowchart TD
  A(["A: x = a * b<br/>i = 0<br/>s = 0"]) --> B["B: if i < n"]
  B --> C["C: t = a * b<br/>if t < s"]
  B --> F["F: ret s"]
  C --> D["D: s = s + t<br/>a = t - 1"]
  C --> E["E: u = a * b<br/>i = i + 1"]
  D --> E
  E --> B

Round-robin iteration on the running example¶

In RPO the liveness trace is the table of Lesson 14.3 §3: 3 passes = 18 evaluations. In postorder (\(A\,C\,D\,E\,B\,F\)), information about \(F\)'s read of \(s\) and B's test of \(i, n\) reaches A only after it has gone around the loop:

block	pass 1 IN	pass 1 OUT	pass 2 IN	pass 2 OUT	pass 3 IN	pass 3 OUT	pass 4 IN	pass 4 OUT
A	{a,b}	{}	{a,b,n}	{a,b,i,n,s}	{a,b,n}	{a,b,i,n,s}	{a,b,n}	{a,b,i,n,s}
C	{a,b,s}	{}	{a,b,i,s}	{a,b,i,s,t}	{a,b,i,n,s}	{a,b,i,n,s,t}	{a,b,i,n,s}	{a,b,i,n,s,t}
D	{s,t}	{}	{b,i,s,t}	{a,b,i}	{b,i,n,s,t}	{a,b,i,n,s}	{b,i,n,s,t}	{a,b,i,n,s}
E	{a,b,i}	{}	{a,b,i,n,s}	{a,b,i,n,s}	{a,b,i,n,s}	{a,b,i,n,s}	{a,b,i,n,s}	{a,b,i,n,s}
B	{a,b,i,n,s}	{a,b,s}	{a,b,i,n,s}	{a,b,i,s}	{a,b,i,n,s}	{a,b,i,n,s}	{a,b,i,n,s}	{a,b,i,n,s}
F	{s}	{}	{s}	{}	{s}	{}	{s}	{}

4 passes = 24 evaluations: in pass 1 every node is visited before the nodes it depends on (its successors), so it sees only \(\mathrm{Init}\) and its own UEVar. Reaching definitions: 3 passes = 18 evaluations in RPO (\(A\,B\,F\,C\,D\,E\)), 5 passes = 30 in postorder.

Here \(d(G, T) = 1\) (one retreating edge \(E \to B\) in the forward direction; one, \(B \to E\), in the reverse graph), so Theorem 14.4.6 promises at most 3 passes in RPO — attained by both analyses.

Worklist algorithms on the running example¶

Liveness with a FIFO queue initialized in RPO \(F\,B\,E\,D\,C\,A\) (output = IN; "joined" = OUT):

step	pop	OUT (joined)	IN = \(f(\mathrm{OUT})\)	changed	added	queue after
1	F	{}	{s}	yes	— (B already queued)	B E D C A
2	B	{s}	{i,n,s}	yes	—	E D C A
3	E	{i,n,s}	{a,b,i,n,s}	yes	—	D C A
4	D	{a,b,i,n,s}	{b,i,n,s,t}	yes	—	C A
5	C	{a,b,i,n,s,t}	{a,b,i,n,s}	yes	B	A B
6	A	{i,n,s}	{a,b,n}	yes	—	B
7	B	{a,b,i,n,s}	{a,b,i,n,s}	yes	A E	A E
8	A	{a,b,i,n,s}	{a,b,n}	no	—	E
9	E	{a,b,i,n,s}	{a,b,i,n,s}	no	—	(empty)

9 evaluations. At step 6 the FIFO processes A before the re-queued B, so A is computed from a stale \(\mathrm{IN}[B]\) and must be redone at step 8. With the priority discipline (smallest RPO number first) step 6 takes B instead:

step	pop	OUT (joined)	IN	changed	added	pending after (by RPO)
1–5	F B E D C	as above	as above	yes	C adds B	B A
6	B	{a,b,i,n,s}	{a,b,i,n,s}	yes	E	E A
7	E	{a,b,i,n,s}	{a,b,i,n,s}	no	—	A
8	A	{a,b,i,n,s}	{a,b,n}	yes	—	(empty)

8 evaluations (the LIFO stack happens to produce the same sequence here). For reaching definitions all three disciplines need 11. The five strategies' costs on the running example — (evaluations, passes): liveness RR-RPO (18, 3), RR-post (24, 4), FIFO 9, LIFO 8, priority 8; reaching definitions RR-RPO (18, 3), RR-post (30, 5), FIFO/LIFO/priority 11 — are exactly what ch14.DataflowSolver.RunningExampleCostsMatchLesson requires of your E1 solver.

Bit-vector implementations on the running example¶

Number the liveness facts \(a{=}0, b{=}1, i{=}2, n{=}3, s{=}4, t{=}5, u{=}6, x{=}7\): one byte suffices. For D: \(\mathrm{UEVar} = \{s, t\} = 0b00110000\), \(\mathrm{VarKill} = \{a, s\} = 0b00010001\). In pass 1, \(\mathrm{OUT}[D] = \mathrm{IN}[E] = \{a,b,i,n,s\} = 0b00011111\), so \(\mathrm{IN}[D] = 0b00110000 \mathbin{\mathrm{OR}} (0b00011111 \mathbin{\mathrm{AND}} \mathbin{\mathrm{NOT}} 0b00010001) = 0b00110000 \mathbin{\mathrm{OR}} 0b00001110 = 0b00111110 = \{b, i, n, s, t\}\) — the table's value, in three word operations.

Try it

./course drill worklist-trace --seed 4 --difficulty medium gives a gen/kill problem and a discipline and asks for the pop sequence; --solution prints tables like the ones above. Then run build/<preset>/bin/ch14-solverbench (after E1) to see the same effects on 10 000-node CFGs.

4. Invariants and correctness¶

Round-robin iteration¶

Lemma 14.4.3 and Theorem 14.4.4. When it breaks: updating IN from a copy of the previous pass's values (Jacobi iteration, Algorithm 14.1.15) is still correct but slower (7 applications on the running example instead of 3 passes); stopping when "IN did not change" instead of "OUT did not change" is wrong for nodes whose transfer function reads anything besides IN (edge functions, widening state).

Worklist algorithms¶

Lemma 14.4.3's worklist clause is the whole argument; it requires that every dependent of a changed node be inserted. When it breaks: inserting only when the dependent is not "done" (a visited flag) loses updates around loops; forgetting to seed \(W\) with all nodes leaves nodes whose value is \(f_n(\mathrm{Init}) \ne \mathrm{Init}\) unvisited (a node with a nonempty gen set but no changed predecessor).

Bit-vector implementations¶

The invariant of Algorithm 14.4.8 is per word; the precondition "bits above \(k\) are zero" matters for must problems: complementing a word (NOT) sets the unused high bits, and a universe built as all-ones words makes spurious facts appear. The solution's bits::full sets exactly \(k\) bits.

5. Complexity¶

Let \(n\) = nodes, \(e\) = edges, \(h = h(L)\), \(d = d(G, T)\), \(k\) = facts, \(w\) = word size.

Technique	Time (worst)	Time (typical)	Space	Variables
Round-robin, RPO	\(O((d + 2) \cdot (n + e))\) evaluations for rapid frameworks; \(O(n \cdot h \cdot (n + e))\) in general	3–6 passes (Part 1: 4–6)	\(O(n)\) values	\(n, e, d, h\)
Round-robin, postorder	\(O(n \cdot (n + e))\) even for bit vectors	35–69 passes (Part 1)	\(O(n)\)	\(n, e\)
Worklist (any discipline)	\(O(n + e \cdot h)\) evaluations (Proposition 14.2.15)	1.5–6 evaluations per node (Part 1)	\(O(n)\) + the worklist	\(n, e, h\)
Bit vectors	\(\Theta(\lceil k / w \rceil)\) per operation	same	\(O(n \lceil k / w \rceil)\)	\(k, w\)

Proposition 14.4.10 (The loop chain)

On the chain \(0 \to 1 \to \cdots \to n{-}1 \to 1\) (\(n \ge 3\)) with node \(j\) generating fact \(j\) (a forward may problem, \(\mathrm{OUT}[j] = \mathrm{IN}[j] \cup \{j\}\)), round-robin in RPO needs exactly 3 passes, round-robin in postorder exactly \(n + 1\) passes (\(\Theta(n^2)\) evaluations), and a FIFO worklist \(2n - 1\) evaluations.

Proof

RPO \(= 0, 1, \dots, n{-}1\). Pass 1 sets \(\mathrm{OUT}[j] = \{0, \dots, j\}\) (node 1 still sees \(\mathrm{OUT}[n{-}1] = \emptyset\) because \(n{-}1\) comes later). Pass 2: node 1 now receives \(\mathrm{OUT}[n{-}1] = \{0..n{-}1\}\), and every later node inherits all \(n\) facts. Pass 3 changes nothing. Postorder \(= n{-}1, n{-}2, \dots, 1, 0\): along the forward edges \(j \to j{+}1\) each node is visited before its predecessor, so a fact crosses one such edge per pass. Fact 0 is in \(\mathrm{OUT}[0]\) after pass 1 and enters \(\mathrm{IN}[j]\) in pass \(j + 1\), so pass \(n\) still changes \(\mathrm{IN}[n{-}1]\): at least \(n + 1\) passes. Conversely, fact \(j \ge 1\) reaches \(\mathrm{OUT}[n{-}1]\) in pass \(n - j\), crosses the back edge in the same pass (node 1 is visited after node \(n{-}1\)), and reaches \(\mathrm{IN}[k]\) (\(k \le j\)) by pass \(n - j + k - 1 \le n - 1\); so after pass \(n\) every IN is complete and pass \(n + 1\) confirms. Each pass costs \(n\) evaluations. FIFO: the initial queue evaluates the \(n\) nodes in RPO, giving pass 1's values; only node \(n{-}1\)'s change re-queues node 1 (its other dependents are already queued or evaluated with final inputs); node 1 then gains all facts, and the change runs once through nodes \(2, \dots, n{-}1\), the last of which already had all facts and stops the chain: \(n + (n - 1) = 2n - 1\). ch14-solverbench Part 2 measures 3, \(n + 1\) and \(2n - 1\) for \(n = 16, 256, 1024\). \(\square\)

At scale (ch14-solverbench, random CFGs with \(n/10\) back edges, 256 facts, this container): for \(n = 10\,000\), RPO round-robin needs 6 passes (60 000 evaluations, 16 ms), postorder 69 passes (690 000, 149 ms), a FIFO worklist 46 448 evaluations (18 ms). The evaluation counts are deterministic; the timings are from one run on the course container and vary by machine and run. GCC's dumps above show about one evaluation per block on real functions.

Round-robin iteration¶

Jacobi vs Gauss–Seidel [NNH, Ch. 6]: Jacobi uses only the previous pass's values (parallelizable), Gauss–Seidel (Algorithm 14.4.1) the newest — trade-off: Gauss–Seidel converges in fewer passes, Jacobi can be vectorized across nodes.
Two-pass loop traversal (LLVM LoopTraversal) [LLVM-RDA]: visit in RPO once, then revisit loop blocks exactly once — trade-off: exact only for problems that converge in 2 passes over each loop (post-RA reaching definitions of registers), no fixed-point test at all.

Worklist algorithms¶

Double worklist with ages (GCC df_worklist_dataflow_doublequeue) [GCC-DF]: process the current worklist in postorder-index order and collect new work in a second one; skip joins over edges whose source did not change since the last visit — trade-off: fewer joins, more bookkeeping.
SCC-ordered / weak topological order [Bou93]: solve strongly connected components in topological order, iterating each to stability before moving on — trade-off: never revisits a finished component; required to place widening points well (Clang's WTODataflowWorklist, Lesson 14.7).
Elimination methods (Lesson 14.5) replace iteration by solving loops in closed form.

Bit-vector implementations¶

Sparse bit vectors (LLVM SparseBitVector, GCC bitmap) — trade-off: memory proportional to set bits, slower random access; the right choice when \(k\) is large and sets are small (live registers).
Packed multi-bit lattices (Clang UninitializedValues stores 2 bits per variable in a PackedVector) [CLANG-UNINIT] — trade-off: lattices of height 2 per fact at bit-vector speed.

7. In real compilers¶

Round-robin iteration¶

LLVM

llvm/lib/Analysis/StackLifetime.cpp — StackLifetime::calculateLocalLiveness: while (Changed) over depth_first(&F) (LLVM 23.1.2) [LLVM-SL]. llvm/lib/CodeGen/LoopTraversal.cpp — the two-pass order used by ReachingDefInfo [LLVM-RDA].

GCC gcc/df-core.cc — df_worklist_dataflow falls back to iterating over blocks in postorder index order (GCC 15) [GCC-DF].

Find where LLVM does it. Open llvm/lib/Analysis/StackLifetime.cpp and read calculateLocalLiveness. Question: in which traversal order does each pass visit the blocks, and what does the TODO in the loop suggest? (Quiz llvm-where-stacklifetime-order.)

Worklist algorithms¶

Clang

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h — DataflowWorklistBase, ReversePostOrderCompare, ForwardDataflowWorklist, BackwardDataflowWorklist, WTODataflowWorklist (LLVM 23.1.2) [CLANG-DFW]; used by UninitializedValues.cpp and LiveVariables.cpp.

GCC gcc/df-core.cc — df_worklist_dataflow_doublequeue (GCC 15) [GCC-DF].
rustc compiler/rustc_mir_dataflow/src/framework/mod.rs — iterate_to_fixpoint seeds a WorkQueue with the blocks in reverse_postorder (rustc 1.90.0) [RUSTC-DF].
LLVM llvm/lib/Transforms/Utils/SCCPSolver.cpp — SCCPInstVisitor::solve drains instruction and block worklists (LLVM 23.1.2) [LLVM-SCCP].

Bit-vector implementations¶

LLVM

llvm/include/llvm/ADT/BitVector.h and SparseBitVector.h — the set types; StackLifetime's BlockLifetimeInfo holds BitVector Begin, End, LiveIn, LiveOut (LLVM 23.1.2) [LLVM-SL].

GCC gcc/df-problems.cc — DF_LR keeps in, out, use, def bitmaps per block (GCC 15) [GCC-DF].
Clang clang/lib/Analysis/UninitializedValues.cpp — CFGBlockValues with 2-bit packed values per variable [CLANG-UNINIT].

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Round-robin iteration	Exact MFP (Theorem 14.4.4)	\(\le d + 2\) passes in RPO for rapid problems; \(\Theta(n)\) passes in postorder on a loop chain	Pass count is a simple progress measure	Lowest	Small analyses; bit-vector problems with small \(d\) (LLVM StackLifetime)
Worklist algorithms	Exact MFP	Visits only nodes with changed inputs; priority-by-RPO is near-optimal on reducible CFGs	Evaluation count per node	Low–medium (a queue + membership bits)	Production solvers (GCC df, Clang, rustc, SCCP)
Bit-vector implementations	Same fixed point; only for powerset lattices	\(\lceil k / w \rceil\) word operations per set operation	—	Low	Classic analyses; any finite-universe powerset lattice

Choose round-robin in RPO when the problem is rapid and simplicity matters. Choose a worklist when changes are local (incremental re-analysis, large functions) or the lattice is tall. Choose a priority queue keyed by RPO as the default discipline; use postorder for backward problems (it is RPO of the reverse graph only for single-exit CFGs — compute RPO on \(G^{R}\) as Pebble's directionOrder does). Use bit vectors whenever the lattice is a powerset of a numbered universe.

Lab numbers (Part 1, 10 000 nodes, this container): RPO round-robin 6.0 evaluations/node, postorder round-robin 69.0, FIFO 4.6, LIFO 6.0, priority 5.9 (forward). Reproduce with build/<preset>/bin/ch14-solverbench.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Round-robin iteration	`rr-passes-postorder`, `d-plus-two`, `llvm-where-stacklifetime-order`	`./course drill worklist-trace --difficulty hard` (passes)	`round-robin`	E1
Worklist algorithms	`worklist-fifo-pops`, `llvm-where-uninit-worklist`	`./course drill worklist-trace`	`worklist`	E1, lab
Bit-vector implementations	`bitvector-genkill`, `bitvector-words`	`./course drill dataflow-table`	`bit-vector`	E2

Pitfall

"Postorder" is not the right order for backward problems in general. It coincides with RPO of the reverse graph only on some CFGs (single exit, no unreachable exits); an infinite loop or a second return changes it. Compute the order on the graph you iterate over.

References¶

See the chapter references.

Lesson 14.4 — Iterative solvers: round-robin, worklists and bit vectors¶

1. Problem and motivation¶

Round-robin iteration¶

Worklist algorithms¶

Bit-vector implementations¶

2. Definitions and algorithms¶

Round-robin iteration¶

Worklist algorithms¶

Correctness and the Kam–Ullman bound¶

Bit-vector implementations¶

3. Worked example¶

Round-robin iteration on the running example¶

Worklist algorithms on the running example¶

Bit-vector implementations on the running example¶

4. Invariants and correctness¶

Round-robin iteration¶

Worklist algorithms¶

Bit-vector implementations¶

5. Complexity¶

6. Variants and refinements¶

Round-robin iteration¶

Worklist algorithms¶

Bit-vector implementations¶

7. In real compilers¶

Round-robin iteration¶

Worklist algorithms¶

Bit-vector implementations¶

8. Comparison¶

9. Assessment¶

References¶