Lesson 14.3 — The classic analyses¶

Techniques: reaching definitions, live variables (including SSA liveness), available expressions, very busy expressions, constant propagation, definite initialization · Pebble implements: SSA liveness (E2), reaching stores (E3), definite initialization (E4) and the pebble-uninit warning (E5) in pebble/lib/Analysis/Dataflow/ and pebble/lib/Passes/Dataflow/ · Lab: liveness as Datalog rules (labs/ch14-dataflow) · Prerequisites: Lesson 14.2 · Time: 6–8 hours

Four questions are older than SSA and still asked by every compiler: which assignments may produce the value read here (reaching definitions), which variables may still be read (liveness), which expressions have certainly been computed already (available expressions), and which will certainly be computed before their operands change (very busy expressions). Each is one monotone framework — a direction, a merge, and gen/kill sets — so each is ten lines on top of the solver of Lesson 14.4. Two more complete the lesson: constant propagation, the standard non-distributive framework, and definite initialization, which turns the must/may pair into a compiler warning.

1. Problem and motivation¶

All six analyses run in the middle end on a CFG of basic blocks. They became standard in the optimizing compilers of the early 1970s — Allen's and Cocke's work at IBM [All70, AC76], Ullman's common-subexpression algorithms [Ull73] — and were unified by Kildall's framework [Kil73]. The Dragon book and Engineering a Compiler still teach them in this form [Dragon2, §9.2; EaC3, Ch. 9]. In LLVM most of them survive in SSA-specialized form: SSA is reaching definitions for registers, so the IR-level analyses are about memory, liveness and values.

Reaching definitions¶

A definition \(d\) of \(v\) reaches a point \(p\) if some path from \(d\) to \(p\) does not redefine \(v\). The answer gives use-def chains: constant propagation, loop-invariant detection and SSA construction all start from it [All70]. Pebble uses it for memory: which stores to a local variable reach a load (E3) — exactly the question mem2reg answers when it turns loads into phis.

Live variables¶

\(v\) is live at \(p\) if some path from \(p\) reads \(v\) before writing it. Register allocation needs it (a register can be reused when its value is dead), dead-code elimination needs it (a store to a dead variable is useless), and SSA construction uses it to avoid useless phis (pruned SSA, Ch 16). Pebble computes liveness of SSA values (E2); the result is reused by SSA destruction (Ch 16) and register allocation (Ch 22).

Available expressions¶

\(e\) is available at \(p\) if every path from the entry to \(p\) computes \(e\) and does not redefine its operands afterwards. Then a recomputation at \(p\) is redundant: global common-subexpression elimination [Coc70, Ull73]. LLVM's GVN and EarlyCSE are its SSA descendants.

Very busy expressions¶

\(e\) is very busy (anticipable) at \(p\) if every path from \(p\) computes \(e\) before redefining its operands. Then \(e\) can be hoisted to \(p\) without adding work on any path: code hoisting, and the "anticipability" half of partial-redundancy elimination [MR79, KRS92].

Constant propagation¶

Which variables hold a known constant at \(p\)? Kildall's own example [Kil73]; the lattice \(\mathbb{Z}_\bot^\top\) makes it the canonical non-distributive framework (Lesson 14.2), and its sparse, conditional form SCCP (Lesson 14.6) is in every compiler.

Definite initialization¶

Is \(v\) assigned on every path from the entry to a read of \(v\)? Java and C# make this a language rule [JLS, Ch. 16]; C compilers turn its failure into -Wuninitialized and -Wsometimes-uninitialized. It is available expressions' twin: a forward must-analysis. Pebble's pebble-uninit pass (E5) combines it with reaching stores to say "is" or "may be" uninitialized.

2. Definitions and algorithms¶

Throughout, a program is a flowgraph \(G = (N, E, r)\) of basic blocks of three-address statements x = y op z, x = y, x = 7, if y < z, ret y (the format of tools/course/lib/dataflow.py and the dataflow-table drill). A block \(B\) with statements \(s_1, \dots, s_k\) has program points before \(s_1\) (the start, \(\mathrm{IN}[B]\)) and after \(s_k\) (the end, \(\mathrm{OUT}[B]\)).

Definition 14.3.1 (Definitions, uses, expressions)

A definition is a statement that assigns a variable; the definitions are numbered \(d_1, d_2, \dots\) in program order and \(\mathrm{var}(d)\) is the variable assigned. \(\mathrm{uses}(s)\) is the set of variables \(s\) reads. An expression is the right-hand side y op z of an assignment with at least one variable operand (written without spaces, a*b, i+1); an assignment to one of its variable operands kills it. For a block \(B\): \(\mathrm{defs}(B)\) = variables assigned in \(B\); \(\mathrm{UEVar}(B)\) = variables read in \(B\) before any assignment to them in \(B\) (upward exposed); \(\mathrm{VarKill}(B) = \mathrm{defs}(B)\).

Reaching definitions¶

Definition 14.3.2 (Reaching definitions)

A definition \(d\) reaches the start of block \(B\) if there is a path from the point just after \(d\) to the start of \(B\) containing no other definition of \(\mathrm{var}(d)\). \(\mathrm{RD}_{\mathrm{in}}(B)\) is the set of such \(d\); \(\mathrm{RD}_{\mathrm{out}}(B)\) likewise for the end of \(B\).

Algorithm 14.3.3 (Reaching definitions)

Input: a program; its definitions \(d_1, \dots, d_m\).
Output: \(\mathrm{IN}[B], \mathrm{OUT}[B] \subseteq \{d_1, \dots, d_m\}\) for every block.
Precondition: none (any CFG).
Postcondition: \(\mathrm{IN}[B] = \mathrm{RD}_{\mathrm{in}}(B)\) and \(\mathrm{OUT}[B] = \mathrm{RD}_{\mathrm{out}}(B)\) (Theorem 14.3.5).
Invariant: the solver's (Lesson 14.4): the current sets are below the least fixed point.

function ReachingDefinitions(G):
    for B in N:                                   # local sets, one pass over each block
        gen[B]  ← { the last definition of v in B : v ∈ defs(B) }
        kill[B] ← { d : var(d) ∈ defs(B) } ∖ gen[B]
    framework ← forward, may:
        join          = ∪                          # Init = {} everywhere
        boundary      = IN[r] = {}
        transfer f_B  = X ↦ gen[B] ∪ (X ∖ kill[B])
    return Solve(framework)                      # Algorithm 14.4.1 or 14.4.2

Pebble's E3 is the same algorithm over the store instructions to tracked allocas (pebble/include/pebble/Analysis/DataflowMemory.h).

Lemma 14.3.4 (Block transfer of reaching definitions)

For a set \(X\) of definitions reaching the start of \(B\), the definitions reaching the end of \(B\) through \(B\) are exactly \(f_B(X) = \mathrm{gen}[B] \cup (X \setminus \mathrm{kill}[B])\).

Proof

A definition outside \(B\) survives \(B\) iff \(B\) assigns no variable it defines, i.e. iff it is not in \(\mathrm{kill}[B]\) (a definition outside \(B\) of a variable in \(\mathrm{defs}(B)\) is in \(\mathrm{kill}[B]\) because \(\mathrm{gen}[B]\) contains only definitions in \(B\)). A definition in \(B\) reaches the end of \(B\) iff no later statement of \(B\) redefines its variable, i.e. iff it is the last one for its variable: exactly \(\mathrm{gen}[B]\). Definitions in \(B\) that are not last are in \(\mathrm{kill}[B]\) and are removed from \(X\) if they arrive around a loop. \(\square\)

Theorem 14.3.5 (Correctness of Algorithm 14.3.3)

The least fixed point of the reaching-definitions equations is \(\mathrm{RD}_{\mathrm{in}}, \mathrm{RD}_{\mathrm{out}}\) for every block reachable from \(r\).

Proof

By Lemma 14.3.4 and induction on path length, \(f_p(\emptyset)\) is the set of definitions that reach the end of path \(p\) along \(p\), so \(\mathrm{MOP}(B) = \bigcup_{p} f_p(\emptyset)\) is the set of definitions reaching \(B\) along some path — Definition 14.3.2. The framework is distributive (Lemma 14.1.10), so \(\mathrm{MFP} = \mathrm{MOP}\) for reachable blocks (Theorem 14.2.13). \(\square\)

Reaching stores become phis: LLVM's mem2reg

Reproduce (clang 23.1.2, opt 23.1.2):

cat > rd.c <<'EOF'
int sometimes(int c) {
  int x;
  if (c)
    x = 1;
  return x;
}
int both_paths(int c) {
  int z;
  if (c)
    z = 1;
  else
    z = 2;
  return z;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm rd.c -o rd.ll
grep -E 'store i32 [0-9]|load i32, ptr %[xz]' rd.ll
opt -passes=mem2reg -S rd.ll | grep -E 'phi|^  ret'

Output:

  store i32 1, ptr %x, align 4
  %1 = load i32, ptr %x, align 4
  store i32 1, ptr %z, align 4
  store i32 2, ptr %z, align 4
  %1 = load i32, ptr %z, align 4
  ret i32 1
  %z.0 = phi i32 [ 1, %if.then ], [ 2, %if.else ]
  ret i32 %z.0

What to notice: in both_paths two stores reach the load of %z (Definition 14.3.2), and mem2reg replaces the load by a phi of exactly those two stored values. In sometimes the store x = 1 and the uninitialized entry reach the load; mem2reg builds phi [1, undef] and folds it to 1, since undef may be chosen to be 1 — the reason C compilers warn about uninitialized variables (see Definite initialization below) instead of "helping". Run print<pebble-reaching-stores> on the same file after E3: it prints reached by {S1} and reached by {S1, S2}.

Live variables¶

Definition 14.3.6 (Liveness)

\(v\) is live at a point \(p\) if some path from \(p\) reaches a read of \(v\) with no assignment to \(v\) in between (the read may be at \(p\) itself). \(\mathrm{live\text{-}in}(B)\) and \(\mathrm{live\text{-}out}(B)\) are the variables live at the start and end of \(B\).

Algorithm 14.3.7 (Live variables)

Input: a program.
Output: \(\mathrm{IN}[B], \mathrm{OUT}[B] \subseteq \mathit{Vars}\) for every block.
Precondition: none.
Postcondition: \(\mathrm{IN}[B] = \mathrm{live\text{-}in}(B)\), \(\mathrm{OUT}[B] = \mathrm{live\text{-}out}(B)\) (Theorem 14.3.8).
Invariant: the solver's (Lesson 14.4).

function LiveVariables(G):
    for B in N:
        UEVar[B] ← ∅;  VarKill[B] ← ∅
        for s in B, top to bottom:
            UEVar[B]   ← UEVar[B] ∪ (uses(s) ∖ VarKill[B])
            if s assigns x: VarKill[B] ← VarKill[B] ∪ {x}
    framework ← backward, may:
        join = ∪;  boundary OUT[B] = {} for every exit B
        transfer f_B = X ↦ UEVar[B] ∪ (X ∖ VarKill[B])     # X = OUT[B], result = IN[B]
    return Solve(framework)

Theorem 14.3.8 (Correctness of Algorithm 14.3.7)

The least fixed point of the liveness equations is \(\mathrm{live\text{-}in}, \mathrm{live\text{-}out}\) for every block from which an exit is reachable; for blocks that reach no exit it is the set of variables read on some path before being written (Definition 14.3.6 read on infinite paths).

Proof

Backward version of Theorem 14.3.5: on \(G^{R}\), \(f_B\) is gen/kill (distributive), and by induction on path length \(f_p\) applied to \(\emptyset\) yields the variables read along the reversed path before being written; the join over paths is Definition 14.3.6, and distributivity gives MFP = MOP (Theorem 14.2.13 on \(G^{R}\)). For blocks that reach no exit, \(\mathrm{Paths}\) in \(G^{R}\) from the exits are empty; the least fixed point still collects every read reachable forward, because the equations propagate along every edge regardless of the boundary. \(\square\)

Definition 14.3.9 (Liveness of SSA values)

In SSA form (LLVM IR) the variables are the SSA values: arguments and value-producing instructions. Each has exactly one definition. A phi \(v = \phi(\dots, u_P, \dots)\) in block \(B\) defines \(v\) at the start of \(B\) and uses \(u_P\) at the end of predecessor \(P\), on the edge \(P \to B\). Hence

\[ \begin{aligned} \mathrm{live\text{-}out}(B) &= \bigcup_{S \in \mathrm{succs}(B)} \big( \mathrm{live\text{-}in}(S) \cup \mathrm{PhiUses}(B \to S) \big), \\ \mathrm{live\text{-}in}(B) &= \mathrm{UpwardExposed}(B) \cup \big( \mathrm{live\text{-}out}(B) \setminus \mathrm{Defs}(B) \big), \end{aligned} \]

with \(\mathrm{Defs}(B)\) including \(B\)'s phis and \(\mathrm{UpwardExposed}(B)\) the non-phi reads in \(B\). A phi result is therefore never live-in to its own block. (The SSA book's formulation of the same sets [SSAB, Ch. 9] is this one; some register allocators additionally treat phi results as live-in — Ch 22.) This is the contract of pebble/include/pebble/Analysis/Liveness.h (E2).

SSA liveness on the running example

After mem2reg, the running example's loop head %while.cond has phis %i.0, %s.0, %a.addr.0. print<pebble-liveness> (the solution, tests/ch14/lit/liveness.test) prints %while.cond: in = {%b, %n} out = {%b, %n, %i.0, %s.0, %a.addr.0}: the phis are live-out but not live-in, and %a (the parameter) is live-out of %entry only because the phi reads it on the edge %entry → %while.cond.

Liveness in Clang's static analyzer and its dead-store checker

Reproduce (clang 23.1.2):

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
clang-23 --analyze -Xclang -analyzer-checker=debug.DumpCFG live.c 2>&1 | grep -E '^ \[B|Succs'
clang-23 --analyze -Xclang -analyzer-checker=debug.DumpLiveVars,deadcode.DeadStores live.c

Output:

 [B6 (ENTRY)]
   Succs (1): B5
 [B1]
   Succs (1): B0
 [B2]
   Succs (1): B4
 [B3]
   Succs (1): B2
 [B4]
   Succs (2): B3 B1
 [B5]
   Succs (1): B4
 [B0 (EXIT)]

[ B0 (live variables at block exit) ]

[ B1 (live variables at block exit) ]

[ B2 (live variables at block exit) ]
 n <live.c:1:13>
 s <live.c:2:7>
 i <live.c:2:14>

[ B3 (live variables at block exit) ]
 n <live.c:1:13>
 s <live.c:2:7>
 i <live.c:2:14>

[ B4 (live variables at block exit) ]
 n <live.c:1:13>
 s <live.c:2:7>
 i <live.c:2:14>

[ B5 (live variables at block exit) ]
 n <live.c:1:13>
 s <live.c:2:7>
 i <live.c:2:14>

[ B6 (live variables at block exit) ]
 n <live.c:1:13>

live.c:7:3: warning: Value stored to 'dead' is never read [deadcode.DeadStores]
    7 |   dead = s;
      |   ^      ~
1 warning generated.

What to notice: Clang's CFG has the loop test in B4, the body in B3, the latch B2 and the return in B1. n, s, i are live at the exit of every loop block (Definition 14.3.6); after B1 (return s) nothing is live. dead is never live after dead = s, so the store is useless: deadcode.DeadStores is a liveness client. The analysis behind it is clang/lib/Analysis/LiveVariables.cpp, a backward worklist solver [CLANG-LV].

Available expressions¶

Definition 14.3.10 (Available expressions)

\(e\) is available at \(p\) if every path from \(r\) to \(p\) contains an evaluation of \(e\) that is not followed (on that path, before \(p\)) by an assignment to an operand of \(e\).

Algorithm 14.3.11 (Available expressions)

Input: a program; its expressions \(U\) (the universe).
Output: \(\mathrm{IN}[B], \mathrm{OUT}[B] \subseteq U\).
Precondition: none.
Postcondition: for every block reachable from \(r\), \(\mathrm{IN}[B]\) is the set of expressions available at its start (Theorem 14.3.12).
Invariant: the solver's, in the dual order: sets only shrink from \(U\).

function AvailableExpressions(G):
    for B in N:
        avail ← ∅
        for s in B, top to bottom:
            if s evaluates an expression e: avail ← avail ∪ {e}
            if s assigns x: avail ← { e ∈ avail : x is not an operand of e }
        DEExpr[B]   ← avail                        # downward exposed
        ExprKill[B] ← { e ∈ U : an operand of e ∈ defs(B) } ∖ DEExpr[B]
    framework ← forward, must:
        join = ∩;  Init = U;  boundary IN[r] = {}
        transfer f_B = X ↦ DEExpr[B] ∪ (X ∖ ExprKill[B])
    return Solve(framework)

Theorem 14.3.12 (Correctness of Algorithm 14.3.11)

For every block reachable from \(r\), the solution is the set of available expressions; for unreachable blocks it is \(U\) (vacuously: there is no path).

Proof

The lattice is \((\mathcal{P}(U), \supseteq)\) with join \(\cap\) and \(\bot = U\); gen/kill functions distribute over \(\cap\) just as over \(\cup\) (\(G \cup ((X \cap Y) \setminus K) = (G \cup (X \setminus K)) \cap (G \cup (Y \setminus K))\)). By induction along a path, \(f_p(\emptyset)\) is the set of expressions evaluated and not killed afterwards on \(p\), so MOP is the intersection over paths — Definition 14.3.10 — and Theorem 14.2.13 gives MFP = MOP on reachable blocks. An unreachable block has no path and keeps \(\mathrm{Init} = U\). \(\square\)

Available expressions in LLVM: EarlyCSE removes a recomputation

Reproduce (opt 23.1.2):

cat > ae.ll <<'EOF'
define i32 @ae(i1 %c, i32 %a, i32 %b) {
entry:
  %x = mul i32 %a, %b
  br i1 %c, label %then, label %join
then:
  %t = add i32 %x, 1
  br label %join
join:
  %p = phi i32 [ %t, %then ], [ 0, %entry ]
  %y = mul i32 %a, %b
  %r = add i32 %p, %y
  ret i32 %r
}
EOF
opt -passes=early-cse -S ae.ll | grep -E 'mul|%r ='

Output:

  %x = mul i32 %a, %b
  %r = add i32 %p, %x

What to notice: a*b is computed in %entry, which dominates %join, and SSA operands are never reassigned, so a*b is available at %join on every path (Definition 14.3.10). EarlyCSE keeps a scoped table of available expressions while walking the dominator tree (llvm/lib/Transforms/Scalar/EarlyCSE.cpp) [LLVM-EARLYCSE] and replaces %y by %x. In SSA the kill sets are empty, which is why a dominator-tree walk can replace the iterative solver.

Very busy expressions¶

Definition 14.3.13 (Very busy expressions)

\(e\) is very busy at \(p\) if every path from \(p\) to an exit evaluates \(e\) before any assignment to an operand of \(e\).

Algorithm 14.3.14 (Very busy expressions)

Input: a program; its expressions \(U\).
Output: \(\mathrm{IN}[B], \mathrm{OUT}[B] \subseteq U\).
Precondition: every block reaches an exit (otherwise see §4).
Postcondition: \(\mathrm{IN}[B]\) is the set of expressions very busy at the start of \(B\) (Theorem 14.3.15).
Invariant: the solver's, in the dual order.

function VeryBusyExpressions(G):
    for B in N:
        defined ← ∅;  UEExpr[B] ← ∅
        for s in B, top to bottom:
            if s evaluates e and no operand of e ∈ defined: UEExpr[B] ← UEExpr[B] ∪ {e}
            if s assigns x: defined ← defined ∪ {x}
        ExprKill[B] ← { e ∈ U : an operand of e ∈ defined } ∖ UEExpr[B]
    framework ← backward, must:
        join = ∩;  Init = U;  boundary OUT[B] = {} for every exit B
        transfer f_B = X ↦ UEExpr[B] ∪ (X ∖ ExprKill[B])
    return Solve(framework)

Theorem 14.3.15 (Correctness of Algorithm 14.3.14)

If every block reaches an exit, the solution is the set of very busy expressions.

Proof

Dual of Theorem 14.3.12 on \(G^{R}\): gen/kill over \((\mathcal{P}(U), \supseteq)\) is distributive, a path's function applied to \(\emptyset\) yields the expressions evaluated on the path before their operands change, and the intersection over all paths to an exit is Definition 14.3.13. \(\square\)

Very busy expressions in LLVM: GVNHoist hoists a*b above a branch

Reproduce (opt 23.1.2):

cat > vbe.ll <<'EOF'
define i32 @h(i1 %c, i32 %a, i32 %b) {
entry:
  br i1 %c, label %then, label %else
then:
  %x = mul i32 %a, %b
  %x1 = add i32 %x, 1
  br label %join
else:
  %y = mul i32 %a, %b
  %y1 = sub i32 %y, 1
  br label %join
join:
  %r = phi i32 [ %x1, %then ], [ %y1, %else ]
  ret i32 %r
}
EOF
opt -passes=gvn-hoist -S vbe.ll | sed -n '/^entry:/,/^then:/p'

Output:

entry:
  %x = mul i32 %a, %b
  br i1 %c, label %then, label %else

then:                                             ; preds = %entry

What to notice: a*b is evaluated on both paths out of %entry before a or b change, so it is very busy at the end of %entry (Definition 14.3.13) and can move there without adding work to any path. GVNHoist computes these "anticipable" (ANTIC) points on the post-dominator tree (llvm/lib/Transforms/Scalar/GVNHoist.cpp) [LLVM-GVNHOIST].

Constant propagation¶

Definition 14.3.16 (Constant-propagation lattice)

\(L_{\mathrm{CP}} = \mathit{Vars} \to \mathbb{Z}_\bot^\top\) (Definition 14.1.7), where \(\bot\) = "no value yet" (not reached, or not yet assigned) and \(\top\) = "not a constant" (NAC). The transfer function of x = y op z sets \(x\) to \(\hat{\mathrm{op}}(\sigma(y), \sigma(z))\) where \(\hat{\mathrm{op}}(c_1, c_2) = c_1 \mathbin{\mathrm{op}} c_2\) for constants, \(\bot\) if either operand is \(\bot\), and \(\top\) otherwise. Branches are ignored (both successors are assumed reachable).

Algorithm 14.3.17 (Simple constant propagation)

Input: a program.
Output: \(\sigma_B \in L_{\mathrm{CP}}\) at the start of every block.
Precondition: none.
Postcondition: the MFP solution; every \(x\) with \(\sigma_B(x) = c\) holds \(c\) at the start of \(B\) on every execution (Proposition 14.3.18).
Invariant: the solver's.

function ConstantPropagation(G):
    framework ← forward:
        join = pointwise join in ℤ⊥⊤;  Init = λx.⊥;  boundary IN[r] = λx.⊥
        transfer f_B = σ ↦ apply each statement of B in order:
            x = y op z :  σ[x ↦ op̂(σ(y), σ(z))]      # literals are their own constants
            x = y      :  σ[x ↦ σ(y)]
    return Solve(framework)

Proposition 14.3.18 (Constant propagation is monotone, not distributive)

Each \(f_B\) is monotone; \(h(L_{\mathrm{CP}}) = 2 \lvert \mathit{Vars} \rvert\); the framework is not distributive; the MFP solution is sound: if \(\mathrm{MFP}(B)(x) = c \in \mathbb{Z}\) then \(x = c\) at the start of \(B\) in every execution reaching \(B\) in which \(x\) has been assigned.

Proof

\(\hat{\mathrm{op}}\) is monotone in each argument on \(\mathbb{Z}_\bot^\top\) (case analysis: raising an argument from \(\bot\) to \(c\) raises the result from \(\bot\) to a constant or keeps it; raising to \(\top\) raises the result to \(\top\) or keeps it), and a sequence of updates of monotone maps is monotone. The height is Proposition 14.1.8. Non-distributivity: the example after Lemma 14.1.10. Soundness: the concrete execution along a path \(p\) is abstracted by \(f_p\) (each statement's abstract effect contains its concrete effect), and \(\mathrm{MOP} \sqsubseteq \mathrm{MFP}\) (Theorem 14.2.12). \(\square\)

Constant propagation in GCC: CCP folds a branch and a multiplication

Reproduce (gcc 14.2.0; LLVM's equivalent is opt -passes=sccp):

cat > cp.c <<'EOF'
int h(int n) {
  int k = 3;
  int r;
  if (k > 2)
    r = n + k;
  else
    r = n - k;
  return r * k;
}
EOF
gcc-14 -O1 -fdump-tree-ccp1 -S cp.c -o /dev/null
sed -n '/^Folding/,$p' cp.c.*t.ccp1

Output:

Folding predicate 1 != 0 to 1
Removing basic block 4
Merging blocks 2 and 3
Merging blocks 2 and 5
int h (int n)
{
  int r;
  int k;
  int _6;

  <bb 2> :
  r_5 = n_3(D) + 3;
  _6 = r_5 * 3;
  return _6;

}

What to notice: k is the constant 3 everywhere (Definition 14.3.16), so k > 2 folds to true, the else block disappears, and r * k becomes r_5 * 3. r itself is \(\top\): it depends on the parameter n. GCC's CCP is the conditional, sparse variant of Algorithm 14.3.17 (gcc/tree-ssa-ccp.cc, lattice ccp_lattice_t) [GCC-CCP]; Lesson 14.6 traces it.

Definite initialization¶

Definition 14.3.19 (Definite initialization)

A local variable \(v\) is definitely initialized at \(p\) if every path from \(r\) to \(p\) contains an assignment to \(v\). A read of \(v\) at a point where \(v\) is not definitely initialized is a possibly uninitialized use; if moreover no assignment to \(v\) reaches it (Definition 14.3.2), it is a definitely uninitialized use.

Algorithm 14.3.20 (Definite initialization and uninitialized-use warnings)

Input: a program with local variables \(V\) (in Pebble: the tracked allocas).
Output: \(\mathrm{IN}[B] \subseteq V\), and one warning per possibly uninitialized read.
Precondition: none.
Postcondition: \(\mathrm{IN}[B]\) = variables definitely initialized at the start of \(B\) for reachable \(B\) (Theorem 14.3.21); a warning says "is" iff no assignment reaches the read.
Invariant: the solver's, in the dual order (sets shrink from \(V\)).

function DefiniteInit(G, V):
    for B in N: stored[B] ← { v ∈ V : B assigns v }
    framework ← forward, must:
        join = ∩;  Init = V;  boundary IN[r] = {}
        transfer f_B = X ↦ X ∪ stored[B]
    IN ← Solve(framework)
    RD ← ReachingDefinitions(G)                  # Algorithm 14.3.3, for the "is/may" split
    for B in N:
        init ← IN[B]
        for s in B, top to bottom:
            if s reads v ∈ V and v ∉ init:
                if no definition of v reaches s: warn "v is uninitialized"
                else:                            warn "v may be uninitialized"
            if s assigns v ∈ V: init ← init ∪ {v}

Theorem 14.3.21 (Correctness of Algorithm 14.3.20)

For every block reachable from \(r\), \(\mathrm{IN}[B]\) is the set of variables definitely initialized at its start. A warning is issued exactly at the reads of Definition 14.3.19, and says "is" exactly for definitely uninitialized uses.

Proof

\(f_B\) is gen-only, distributive over \(\cap\); along a path \(p\), \(f_p(\emptyset)\) is the set of variables assigned on \(p\); the intersection over all paths is Definition 14.3.19, and Theorem 14.2.13 gives MFP = MOP for reachable blocks. The inner loop extends the block-entry fact statement by statement with the same function, so it tests the definition at each read. For the "is/may" split: if no definition reaches the read (Definition 14.3.2), then on every path the read happens before any assignment reachable along it, so every execution reading it reads an uninitialized value; if some definition reaches, the path it reaches along does initialize \(v\), and the path witnessing "not definitely initialized" does not: "may". \(\square\)

Uninitialized-variable warnings: Clang, GCC and pebble-uninit side by side

Reproduce (clang 23.1.2, gcc 14.2.0; pebble-uninit is your E5, run by tests/ch14/lit/uninit.c):

cat > uninit.c <<'EOF'
int never(void) { int y; return y + 1; }
int sometimes(int c) { int x; if (c) x = 1; return x; }
int in_loop(int n) { int last; for (int i = 0; i < n; i++) last = i; return last; }
EOF
clang-23 -fsyntax-only -Wuninitialized -Wsometimes-uninitialized -Wconditional-uninitialized uninit.c 2>&1 | grep ': warning:'
LC_ALL=C gcc-14 -O2 -Wall -c uninit.c -o /dev/null 2>&1 | grep ': warning:'

Output:

uninit.c:1:33: warning: variable 'y' is uninitialized when used here [-Wuninitialized]
uninit.c:2:35: warning: variable 'x' is used uninitialized whenever 'if' condition is false [-Wsometimes-uninitialized]
uninit.c:3:77: warning: variable 'last' may be uninitialized when used here [-Wconditional-uninitialized]
uninit.c:1:35: warning: 'y' is used uninitialized [-Wuninitialized]
uninit.c:3:77: warning: 'last' may be used uninitialized [-Wmaybe-uninitialized]

What to notice: Clang runs Algorithm 14.3.20's must-analysis on its source-level CFG (clang/lib/Analysis/UninitializedValues.cpp, a forward worklist over bit vectors) [CLANG-UNINIT] and grades the result the same way: "is" when no assignment reaches, "sometimes"/"may" otherwise. GCC warns from its optimized SSA form (gcc/tree-ssa-uninit.cc) [GCC-UNINIT], after sometimes has been simplified to return 1 (compare the mem2reg box above) — so it misses the second warning. pebble-uninit reports all three, like Clang with -Wconditional-uninitialized.

3. Worked examples¶

Running example (used for every technique in this lesson and in Lesson 14.4; tools/course/lib/dataflow.py, RUNNING_EXAMPLE). Successors are listed left to right in the order of the diagram.

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

Definitions: \(d_1\) x = a*b, \(d_2\) i = 0, \(d_3\) s = 0 (in A), \(d_4\) t = a*b (C), \(d_5\) s = s+t, \(d_6\) a = t-1 (D), \(d_7\) u = a*b, \(d_8\) i = i+1 (E). Expressions \(U = \{a{*}b, i{+}1, s{+}t, t{-}1\}\). Each trace is round-robin iteration (Algorithm 14.4.1) in reverse postorder of the analysis direction: forward \(A\,B\,F\,C\,D\,E\), backward \(F\,B\,E\,D\,C\,A\). Bold = changed in that pass; every trace ends with a pass that changes nothing.

Reaching definitions on the running example¶

block	gen	kill
A	{d1,d2,d3}	{d5,d8}
B	{}	{}
C	{d4}	{}
D	{d5,d6}	{d3}
E	{d7,d8}	{d2}
F	{}	{}

block	init	pass 1 IN	pass 1 OUT	pass 2 IN	pass 2 OUT	pass 3 IN	pass 3 OUT
A	{}	{}	{d1,d2,d3}	{}	{d1,d2,d3}	{}	{d1,d2,d3}
B	{}	{d1,d2,d3}	{d1,d2,d3}	{d1,...,d8}	{d1,...,d8}	{d1,...,d8}	{d1,...,d8}
F	{}	{d1,d2,d3}	{d1,d2,d3}	{d1,...,d8}	{d1,...,d8}	{d1,...,d8}	{d1,...,d8}
C	{}	{d1,d2,d3}	{d1,d2,d3,d4}	{d1,...,d8}	{d1,...,d8}	{d1,...,d8}	{d1,...,d8}
D	{}	{d1,d2,d3,d4}	{d1,d2,d4,d5,d6}	{d1,...,d8}	{d1,d2,d4,d5,d6,d7,d8}	{d1,...,d8}	{d1,d2,d4,d5,d6,d7,d8}
E	{}	{d1,d2,d3,d4,d5,d6}	{d1,d3,d4,d5,d6,d7,d8}	{d1,...,d8}	{d1,d3,d4,d5,d6,d7,d8}	{d1,...,d8}	{d1,d3,d4,d5,d6,d7,d8}

(\(\{d1,...,d8\}\) abbreviates all eight.) Pass 1 follows the forward edges; pass 2 brings \(d_5..d_8\) around the back edge \(E \to B\); pass 3 confirms. All eight definitions reach the loop head: \(s\) may come from \(d_3\) or \(d_5\), \(i\) from \(d_2\) or \(d_8\).

Live variables on the running example¶

block	UEVar	VarKill
A	{a,b}	{i,s,x}
B	{i,n}	{}
C	{a,b,s}	{t}
D	{s,t}	{a,s}
E	{a,b,i}	{i,u}
F	{s}	{}

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

Pass 1: in backward RPO, B is visited before its loop predecessor E, so \(\mathrm{OUT}[B]\) first sees only \(\mathrm{IN}[F] = \{s\}\) and \(\mathrm{IN}[C] = \bot\).
Pass 2: \(\mathrm{OUT}[B]\) picks up \(\mathrm{IN}[C] = \{a,b,i,n,s\}\); only B's IN changes, and E's and A's OUT follow.
Pass 3: nothing changes. \(x\) and \(u\) are never live: their assignments are dead code.

Available expressions on the running example¶

block	DEExpr	ExprKill
A	{a*b}	{i+1,s+t}
B	{}	{}
C	{a*b}	{s+t,t-1}
D	{t-1}	{a*b,s+t}
E	{a*b}	{i+1}
F	{}	{}

block	init	pass 1 IN	pass 1 OUT	pass 2 IN	pass 2 OUT
A	\(U\)	{}	*{ab}	{}	{a*b}
B	\(U\)	*{ab}	*{ab}	{a*b}	{a*b}
F	\(U\)	*{ab}	*{ab}	{a*b}	{a*b}
C	\(U\)	*{ab}	*{ab}	{a*b}	{a*b}
D	\(U\)	*{ab}	{t-1}	{a*b}	{t-1}
E	\(U\)	{}	*{ab}	{}	{a*b}

In pass 1 the back edge \(E \to B\) still carries \(\mathrm{Init} = U\), so \(\mathrm{IN}[B] = \{a{*}b\} \cap U\); that optimistic start is what makes the result the greatest solution in \(\subseteq\). \(a{*}b\) is available at C, so t = a * b in C is redundant with x = a * b in A — but not at E, because D reassigns a: the recomputation u = a * b in E is needed.

Very busy expressions on the running example¶

block	UEExpr	ExprKill
A	{a*b}	{i+1,s+t}
B	{}	{}
C	{a*b}	{s+t,t-1}
D	{s+t,t-1}	{a*b}
E	{a*b,i+1}	{}
F	{}	{}

block	init	pass 1 IN	pass 1 OUT	pass 2 IN	pass 2 OUT
F	\(U\)	{}	{}	{}	{}
B	\(U\)	{}	{}	{}	{}
E	\(U\)	*{ab,i+1}	{}	{a*b,i+1}	{}
D	\(U\)	{i+1,s+t,t-1}	*{ab,i+1}	{i+1,s+t,t-1}	{a*b,i+1}
C	\(U\)	*{ab,i+1}	{i+1}	{a*b,i+1}	{i+1}
A	\(U\)	*{ab}	{}	{a*b}	{}

\(i{+}1\) is very busy at the end of C (both successors compute it before changing \(i\)), so it could be hoisted into C; nothing is very busy at B because the path to F computes nothing.

Constant propagation on the running example¶

Parameters \(a, b, n\) are \(\top\) at the entry (unknown inputs); every other variable starts at \(\bot\). The table shows \(\mathrm{IN}[B]\) of each block for the three interesting variables as \((i, s, t)\); \(x\) and \(u\) are \(\top\) as soon as they are assigned, since a*b is \(\top\).

block	init	pass 1	pass 2	pass 3
A	\((\bot, \bot, \bot)\)	\((\bot, \bot, \bot)\)	\((\bot, \bot, \bot)\)	\((\bot, \bot, \bot)\)
B	\((\bot, \bot, \bot)\)	\((0, 0, \bot)\)	\((\top, \top, \top)\)	\((\top, \top, \top)\)
F	\((\bot, \bot, \bot)\)	\((0, 0, \bot)\)	\((\top, \top, \top)\)	\((\top, \top, \top)\)
C	\((\bot, \bot, \bot)\)	\((0, 0, \bot)\)	\((\top, \top, \top)\)	\((\top, \top, \top)\)
D	\((\bot, \bot, \bot)\)	\((0, 0, \top)\)	\((\top, \top, \top)\)	\((\top, \top, \top)\)
E	\((\bot, \bot, \bot)\)	\((0, \top, \top)\)	\((\top, \top, \top)\)	\((\top, \top, \top)\)

Pass 1: the back edge \(E \to B\) still carries \(\bot\), so B sees only A's constants \(i = 0, s = 0\); at E, \(s\) merges \(0\) (from C) with \(s + t = \top\) (from D).
Pass 2: B joins \(i = 0\) from A with \(i = 1\) from E: \(0 \sqcup 1 = \top\). Everything becomes \(\top\).
Pass 3: no change. No constant survives the loop, which is correct: \(i\) and \(s\) really change. The instructive instance for constant propagation is the non-distributive one of Lesson 14.2 §3 (\(z = 5\) on both paths, \(\top\) after the merge).

Definite initialization on the running example¶

Treat \(a, b, n\) as parameters (initialized). Every other variable is assigned before it is read on every path — i, s in A; t in C before D reads it; u, x are never read — so the analysis finds no uninitialized read. On tests/ch14/Inputs/c/uninit.c, print<pebble-definite-init> prints for in_loop:

Pebble definite initialization for function 'in_loop'
  %entry: in = {} out = {%n.addr, %i}
  %for.cond: in = {%n.addr, %i} out = {%n.addr, %i}
  %for.body: in = {%n.addr, %i} out = {%n.addr, %last, %i}
  %for.inc: in = {%n.addr, %last, %i} out = {%n.addr, %last, %i}
  %for.end: in = {%n.addr, %i} out = {%n.addr, %i}
  ...
  %4 = load %last in %for.end: maybe uninitialized

%last is in \(\mathrm{OUT}[\texttt{for.body}]\) but not in \(\mathrm{IN}[\texttt{for.cond}] = \mathrm{OUT}[\texttt{entry}] \cap \mathrm{OUT}[\texttt{for.inc}]\), so it is not definitely initialized at %for.end; since the store in %for.body reaches the load, the warning says "may be".

Try it

./course drill dataflow-table --seed 7 --difficulty medium --solution draws one of the four classics on a random program and prints the local sets and the round-robin table in this format. Check your own table for the running example with --difficulty hard seeds until the analysis you want comes up.

4. Invariants and correctness¶

Reaching definitions¶

Lemma 14.3.4 (block transfer) and Theorem 14.3.5 (MFP = definition). The solver's invariant is Lemma 14.4.3. When it breaks: with pointers, a store through p may or may not define x; treating it as a definition that kills other definitions of x (a strong update) is unsound unless p certainly points to x. Pebble's E3 avoids the problem by tracking only allocas whose address never escapes (isTrackedAlloca).

Live variables¶

Theorem 14.3.8. When it breaks: a volatile or escaped variable can be read by code the analysis cannot see; liveness must treat it as always live. In SSA, a phi's operand counted as live-in to the phi's block (instead of live-out of the predecessor) makes values live on edges that never carry them: with two predecessors both supplying different values, both values would appear live in both predecessors.

Available expressions¶

Theorem 14.3.12. The optimistic initialization \(\mathrm{Init} = U\) is essential. Take A: t = a*b -> B; B: -> C, X; C: (no assignment) -> B. The equations \(\mathrm{IN}[B] = \mathrm{OUT}[A] \cap \mathrm{OUT}[C]\) and \(\mathrm{OUT}[C] = \mathrm{IN}[B]\) have two solutions: \(\mathrm{IN}[B] = \{a{*}b\}\) (the right one: \(a{*}b\) is computed before the loop and never killed) and \(\mathrm{IN}[B] = \emptyset\). Starting from \(\emptyset\) the solver stops at the second — sound, but useless. Starting from \(U\) it finds the first, the greatest solution in \(\subseteq\), which is the least fixed point in the order the framework uses (\(\supseteq\)). When it breaks: calls that may modify operands (globals, memory) must kill the expressions that read them.

Very busy expressions¶

Theorem 14.3.15. When it breaks: blocks that reach no exit (infinite loops) keep \(\mathrm{Init} = U\) — "every path to an exit computes \(e\)" is vacuous — so hoisting based on it can move an expression onto a path that never needed it. Hoisting must also not move an expression that may trap (division) above the test that guards it, even when it is very busy.

Constant propagation¶

Proposition 14.3.18. MFP is sound but below MOP (Lesson 14.2 §3). When it breaks: treating \(\bot\) ("not yet assigned") as an ordinary constant makes a read of an uninitialized variable look constant; C's undefined behavior permits that, which is exactly why mem2reg folded phi [1, undef] to 1 above.

Definite initialization¶

Theorem 14.3.21. When it breaks: the analysis is flow-sensitive but path-insensitive: if (c) x = 1; ... if (c) use(x); is safe but warned about (a false positive, since the two conditions are correlated); Clang's -Wsometimes-uninitialized suppresses warnings it cannot attribute to a single branch for this reason, and GCC's -Wmaybe-uninitialized uses predicate analysis to prune such paths.

5. Complexity¶

Let \(n\) = blocks, \(e\) = edges, \(s\) = statements, \(k\) = size of the universe (definitions, variables or expressions), \(w\) = machine word size, \(d = d(G)\) the loop connectedness (Lesson 14.4).

Technique	Time (worst)	Time (typical)	Space	Variables
Reaching definitions	\(O((d + 2) \cdot e \cdot k / w)\)	\(\le 3\)–\(4\) passes	\(O(n k / w)\)	\(n, e, k, d, w\)
Live variables	\(O((d + 2) \cdot e \cdot k / w)\) on \(G^{R}\)	same	\(O(n k / w)\)	same
Available expressions	\(O((d + 2) \cdot e \cdot k / w)\)	same	\(O(n k / w)\)	same
Very busy expressions	\(O((d + 2) \cdot e \cdot k / w)\) on \(G^{R}\)	same	\(O(n k / w)\)	same
Constant propagation	\(O(2 \lvert \mathit{Vars} \rvert \cdot e \cdot \lvert \mathit{Vars} \rvert)\) (Kildall, height \(2\lvert \mathit{Vars} \rvert\))	2–3 passes	\(O(n \lvert \mathit{Vars} \rvert)\)	\(\mathit{Vars}\)
Definite initialization	as available expressions, \(k = \lvert V \rvert\)	same	\(O(n k / w)\)	\(V\)

Proposition 14.3.22 (Cost of the bit-vector classics)

Computing the local sets costs \(O(s + n k / w)\); solving costs \(O((d(G) + 2) \cdot (n + e) \cdot k / w)\) word operations with round-robin iteration in RPO.

Proof

Each statement updates one bit (or scans its operands) once: \(O(s)\), plus initializing \(2n\) vectors of \(\lceil k / w \rceil\) words. Gen/kill frameworks are rapid, so round-robin in RPO needs at most \(d(G) + 2\) passes (Theorem 14.4.6); each pass computes one join per edge and one transfer per node, each \(O(k / w)\) word operations. \(\square\)

Pathological input. For reaching definitions the universe itself can be quadratic: a program with \(m\) variables and \(m\) assignments to each in straight-line code followed by a loop has \(k = m^2\) definitions and \(O(n m^2)\) bits of IN/OUT storage; SSA replaces this by one definition per value (Lesson 14.6).

At scale: GCC's RTL passes compute live registers and reaching definitions this way on every function (gcc/df-core.cc, bitmaps per block) [GCC-DF]; the comparison lab (ch14-solverbench) solves 256-fact gen/kill problems on 10 000-block CFGs in milliseconds (reproduce with build/<preset>/bin/ch14-solverbench).

Reaching definitions¶

Use-def and def-use chains [Dragon2, §9.2.4]: store, per use, the reaching definitions — trade-off: quadratic space in the worst case; SSA's single definitions make them linear.
SSA [CFRWZ91]: renaming gives each use exactly one reaching definition, making the analysis unnecessary for registers — trade-off: requires construction and destruction (Ch 16).

Live variables¶

SSA liveness by path exploration [BBD+11]: one backward walk per value, from its uses to its definition — trade-off: no iteration, work proportional to live ranges (Lesson 14.6, the lab's computeLivenessSparse).
Liveness checking [BHG+08]: answer "is \(v\) live at \(p\)?" on demand using the dominator tree and loop forest, without computing sets — trade-off: fast queries, no sets to iterate.

Available expressions¶

Dominator-tree CSE (LLVM EarlyCSE): in SSA, an expression dominating a use is available — trade-off: misses redundancies along joins (an expression computed on both arms of an if).
Value numbering (GVN, Ch 17): available values rather than lexically equal expressions — trade-off: finds a*b = b*a = c*b after c = a, at higher cost.

Very busy expressions¶

Partial-redundancy elimination [MR79, KRS92]: combines availability and anticipability to move computations to where they are needed on every path; lazy code motion places them as late as possible — trade-off: several bit-vector problems per function.
SSA-based hoisting (GVNHoist): ANTIC on the post-dominator tree — trade-off: limited to hoisting through single-entry regions.

Constant propagation¶

Sparse conditional constant propagation [WZ91]: propagate along SSA edges only and treat branches with constant conditions as one-way — trade-off: finds strictly more constants, needs SSA (Lesson 14.6).
Interprocedural (IPSCCP) and IDE-based constant propagation [SRH96]: across calls — trade-off: context sensitivity costs time or precision (Lesson 14.8).

Definite initialization¶

Predicate-aware uninitialized analysis (GCC -Wmaybe-uninitialized) [GCC-UNINIT]: tracks the conditions guarding a definition and a use — trade-off: fewer false positives, exponential in the worst case.
Language-level definite assignment (Java, C#) [JLS, Ch. 16]: the same must-analysis on the AST with rules per construct — trade-off: must be conservative and simple enough to specify in a language standard.

7. In real compilers¶

Reaching definitions¶

LLVM

llvm/lib/CodeGen/ReachingDefAnalysis.cpp — ReachingDefInfo::run, reaching definitions of physical registers after register allocation, used by the x86 execution-domain fix and false-dependency breaking (LLVM 23.1.2) [LLVM-RDA]. At IR level mem2reg (llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp) answers the same question for promotable allocas.

GCC gcc/df-problems.cc — the DF_RD problem of the dataflow framework (GCC 15) [GCC-DF].

Find where LLVM does it. Open llvm/lib/CodeGen/ReachingDefAnalysis.cpp. Question: which method handles a block the second time LoopTraversal visits it because it is part of a loop? (Quiz llvm-where-reaching-defs.)

Live variables¶

LLVM

llvm/lib/CodeGen/LiveVariables.cpp — LiveVariables::analyze and MarkVirtRegAliveInBlock, SSA liveness of virtual registers on Machine IR, by the path-exploration of Lesson 14.6 (LLVM 23.1.2) [LLVM-LV]. clang/lib/Analysis/LiveVariables.cpp — LiveVariables::computeLiveness, a backward worklist on the source CFG [CLANG-LV].

GCC gcc/df-problems.cc — DF_LR (live registers) and DF_LIVE (GCC 15) [GCC-DF].
rustc compiler/rustc_mir_dataflow/src/impls/liveness.rs — MaybeLiveLocals, a backward analysis on MIR (rustc 1.90.0) [RUSTC-DF].
MLIR mlir/include/mlir/Analysis/DataFlow/LivenessAnalysis.h — LivenessAnalysis, a sparse backward analysis (LLVM 23.1.2) [MLIR-DF].

Available expressions¶

LLVM

llvm/lib/Transforms/Scalar/EarlyCSE.cpp — scoped hash tables of available expressions along the dominator tree (LLVM 23.1.2) [LLVM-EARLYCSE]; llvm/lib/Transforms/Scalar/GVN.cpp for full redundancy elimination with value numbers.

GCC gcc/tree-ssa-dom.cc (dominator-based redundancy elimination) and gcc/tree-ssa-pre.cc (GCC 15).

Very busy expressions¶

LLVM

llvm/lib/Transforms/Scalar/GVNHoist.cpp — class GVNHoist; the file comment: "This pass hoists expressions from branches to a common dominator. ... This is based on finding the ANTIC points in the CFG which do not change during hoisting" (LLVM 23.1.2) [LLVM-GVNHOIST].

GCC gcc/tree-ssa-pre.cc — ANTIC_IN/ANTIC_OUT sets of partial-redundancy elimination (GCC 15).

Constant propagation¶

LLVM

llvm/lib/Transforms/Utils/SCCPSolver.cpp — the conditional sparse variant; ValueLatticeElement is its lattice (LLVM 23.1.2) [LLVM-SCCP].

GCC gcc/tree-ssa-ccp.cc — ccp_lattice_t (UNINITIALIZED, UNDEFINED, CONSTANT, VARYING) (GCC 15) [GCC-CCP].
MLIR mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h — SparseConstantPropagation (LLVM 23.1.2) [MLIR-DF].

Definite initialization¶

Clang

clang/lib/Analysis/UninitializedValues.cpp — runUninitializedVariablesAnalysis (a ForwardDataflowWorklist over CFGBlockValues, bit vectors per block) (LLVM 23.1.2) [CLANG-UNINIT]; clang/lib/Sema/AnalysisBasedWarnings.cpp turns its results into -Wuninitialized and -Wsometimes-uninitialized.

GCC gcc/tree-ssa-uninit.cc — warn_uninitialized_vars (GCC 15) [GCC-UNINIT].
rustc compiler/rustc_mir_dataflow/src/impls/initialized.rs — MaybeUninitializedPlaces, which the borrow checker uses to reject reads of uninitialized places (rustc 1.90.0) [RUSTC-DF].

Find where Clang does it. Open clang/lib/Analysis/UninitializedValues.cpp and find runUninitializedVariablesAnalysis. Question: which worklist class does it instantiate? (Quiz llvm-where-uninit-worklist.)

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Reaching definitions	Exact (distributive): MFP = MOP	\(\le d + 2\) bit-vector passes	Use-def chains; quadratic sets without SSA	Low (gen/kill)	Memory SSA construction, post-RA register reasoning
Live variables	Exact (distributive)	\(\le d + 2\) passes on \(G^{R}\)	Live sets per block; SSA version needs phi conventions	Low	Register allocation, DCE, pruned SSA
Available expressions	Exact (distributive), must	\(\le d + 2\) passes	Redundant expressions to delete	Low	Global CSE; availability half of PRE
Very busy expressions	Exact (distributive), must, backward	\(\le d + 2\) passes	Hoisting points	Low	Code hoisting; anticipability half of PRE
Constant propagation	Sound, below MOP (not distributive)	\(\le 2\lvert \mathit{Vars} \rvert\) height; 2–3 passes	Constants per point	Low–medium (lattice of maps)	Folding; superseded by SCCP
Definite initialization	Exact for its definition; path-insensitive	as available expressions	Warnings with "is/may"	Low	`-Wuninitialized`, Java/C# definite assignment

Choose reaching definitions when you need use-def chains for memory or for code not in SSA. Choose liveness for any register or dead-store question. Choose available/very busy expressions when you implement CSE or PRE on a non-SSA IR (on SSA use GVN, Ch 17). Choose constant propagation only as the stepping stone to SCCP. Choose definite initialization to diagnose — and pair it with reaching definitions for good messages.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Reaching definitions	`rd-in-running`, `llvm-where-reaching-defs`	`./course drill dataflow-table`	`reaching-definitions`	E3
Live variables	`live-in-running`, `ssa-liveness-phi`	`./course drill dataflow-table`	`liveness`	E2, lab L4
Available expressions	`ae-in-running`, `classic-directions`	`./course drill dataflow-table`	`available-expressions`	—
Very busy expressions	`vbe-in-running`, `classic-directions`	`./course drill dataflow-table`	`very-busy-expressions`	—
Constant propagation	`mop-vs-mfp-const`, `cp-height`	`./course drill lattice-props`	`constant-propagation`	— (SCCP in Ch 17)
Definite initialization	`uninit-is-vs-may`, `llvm-where-uninit-worklist`	`./course drill dataflow-table` (available expressions has the same shape)	`definite-init`	E4, E5

Pitfall

Mixing up the direction and the merge: liveness is backward/may (∪), available expressions forward/must (∩), very busy expressions backward/must (∩), reaching definitions forward/may (∪). Getting either wrong still produces a fixed point — just of a different analysis. And a must analysis must start from the universe, not from \(\{\}\).

References¶

See the chapter references.

Lesson 14.3 — The classic analyses¶

1. Problem and motivation¶

Reaching definitions¶

Live variables¶

Available expressions¶

Very busy expressions¶

Constant propagation¶

Definite initialization¶

2. Definitions and algorithms¶

Reaching definitions¶

Live variables¶

Available expressions¶

Very busy expressions¶

Constant propagation¶

Definite initialization¶

3. Worked examples¶

Reaching definitions on the running example¶

Live variables on the running example¶

Available expressions on the running example¶

Very busy expressions on the running example¶

Constant propagation on the running example¶

Definite initialization on the running example¶

4. Invariants and correctness¶

Reaching definitions¶

Live variables¶

Available expressions¶

Very busy expressions¶

Constant propagation¶

Definite initialization¶

5. Complexity¶

6. Variants and refinements¶

Reaching definitions¶

Live variables¶

Available expressions¶

Very busy expressions¶

Constant propagation¶

Definite initialization¶

7. In real compilers¶

Reaching definitions¶

Live variables¶

Available expressions¶

Very busy expressions¶

Constant propagation¶

Definite initialization¶

8. Comparison¶

9. Assessment¶

References¶