Lesson 17.1 — Constant propagation: Kildall, sparse, and conditional¶

Techniques: Kildall's dense constant propagation (1973); sparse simple constant propagation on SSA (Reif–Lewis 1977, Wegman–Zadeck's SSC); sparse conditional constant propagation, SCCP (Wegman–Zadeck 1991), with dense conditional CP (Wegbreit 1975) as its ancestor and interprocedural SCCP as a preview of Ch 20 · Pebble implements: pebble-sccp (exercise E1); simple CP and SCCP side by side in the comparison lab (labs/ch17-scalar, Part A) · Prerequisites: lattices and fixed points (Lesson 14.1), constant propagation as a dataflow problem (Lesson 14.3), sparse propagation (Lesson 14.6), SSA (Ch 16) · Time: 6–8 hours

Lesson 14.6 introduced SCCP as one example of sparse analysis. This lesson treats constant propagation as a family: four algorithms that differ along two independent axes, dense vs sparse (facts per program point or per SSA value) and unconditional vs conditional (every edge assumed executable, or edges discovered as the analysis runs). The running example of the whole chapter is the function below, compiled by clang-23 -O0 and promoted to SSA by mem2reg. It always returns 1, but no single classic pass can prove it; this lesson proves x = 1, Lesson 17.5 proves i = j, and Lesson 17.8 shows why you need both.

int run(int n) {
  int x = 1, i = 0, j = 0;
  while (i < n) {
    if (x != 1)
      x = 2;
    i = i + 1;
    j = j + 1;
  }
  int t = i * 4, u = j * 4;
  return t - u + x;
}

In the chapter's compact SSA notation (the format of the drills and of tools/course/lib/scalaropt.py; value and block names are exactly LLVM's, lt is icmp slt):

fn run(n):
entry:
  br while.cond
while.cond:
  i.0 = phi [0, entry], [add, if.end]
  x.0 = phi [1, entry], [x.1, if.end]
  j.0 = phi [0, entry], [add2, if.end]
  cmp = lt i.0, n
  cbr cmp, while.body, while.end
while.body:
  cmp1 = ne x.0, 1
  cbr cmp1, if.then, if.end
if.then:
  br if.end
if.end:
  x.1 = phi [2, if.then], [x.0, while.body]
  add = add i.0, 1
  add2 = add j.0, 1
  br while.cond
while.end:
  mul = mul i.0, 4
  mul3 = mul j.0, 4
  sub = sub mul, mul3
  add4 = add sub, x.0
  ret add4

flowchart TD
  entry([entry]) --> wc[while.cond]
  wc -->|T| wb[while.body]
  wc -->|F| we[while.end]
  wb -->|T| it[if.then]
  wb -->|F| ie[if.end]
  it --> ie
  ie --> wc

1. Problem and motivation¶

A value is a constant if every execution that computes it computes the same number. Knowing that lets the compiler fold the instruction, delete branches whose condition it decides, and feed smaller programs to every later pass; LLVM runs sccp in its function pipeline and ipsccp once per module at -O2 [LLVM-Pipelines], GCC runs CCP several times [GCC-CCP]. The question is undecidable in general, so each algorithm computes a sound approximation, and the four algorithms of this lesson form a precision ladder.

Kildall's dense constant propagation¶

Kildall's 1973 paper introduced iterative dataflow analysis with constant propagation as its first example [Kil73]: keep, at every program point, a map from variables to "constant \(c\) or not a constant", and iterate the transfer functions around the CFG until nothing changes. It works on any IR, needs no SSA, and is the specification against which later algorithms are measured. Its cost is density: every map is copied through every block, whether or not the block mentions the variable.

Sparse simple constant propagation¶

Reif and Lewis observed that constant facts only need to travel from a definition to its uses [RL77, RL86]. On SSA, def-use edges are the SSA edges, so the fact for a value is stored once and each instruction is re-evaluated only when one of its operands changes. Wegman and Zadeck call this the sparse simple constant algorithm (SSC) [WZ91, §3]. It finds exactly the constants Kildall finds on the same SSA program (Theorem 17.1.11), in time proportional to the number of SSA edges instead of blocks × variables.

Sparse conditional constant propagation¶

Both previous algorithms assume every CFG edge can execute. In the running example they conclude that x.0 is not a constant, because the dead block if.then merges the value 2 into x.1. Wegbreit showed in 1975 that a dense analysis can instead discover which branches are possible as it goes [Weg75]; Wegman and Zadeck combined that idea with sparseness into SCCP [WZ91]. SCCP proves x.0 = 1, deletes if.then, and is strictly more powerful than running constant propagation and unreachable-code elimination to a fixed point (Theorem 17.1.12). pebble-sccp (exercise E1) implements it on LLVM IR; the lab measures the gap between simple CP and SCCP on a corpus.

2. Definitions and algorithms¶

Definition 17.1.1 (Constant lattice)

The constant lattice is the flat lattice \(L_c = \mathbb{Z}_{32} \cup \{\bot, \top\}\) over the 32-bit integers \(\mathbb{Z}_{32}\), ordered by \(\bot \sqsubseteq c \sqsubseteq \top\) for every \(c \in \mathbb{Z}_{32}\) and with distinct integers incomparable. Its join is \(c \sqcup c = c\), \(c \sqcup d = \top\) for \(c \neq d\), \(\bot \sqcup x = x\), \(\top \sqcup x = \top\). \(\bot\) means "no evidence yet" (the optimistic start), \(\top\) means "not a constant" (overdefined). The height is \(h(L_c) = 2\). This is Ch 14's orientation (facts rise); LLVM calls the elements unknown, constant and overdefined, GCC UNDEFINED, CONSTANT and VARYING.

Definition 17.1.2 (Constant value, abstract evaluation)

Let \(F\) be a function and \(v\) one of its SSA values (or variables). \(v\) is a constant \(c\) if every execution of \(F\), on every input, that evaluates the definition of \(v\) yields \(c\). The concretization of \(\ell \in L_c\) is \(\gamma(\bot) = \emptyset\), \(\gamma(c) = \{c\}\), \(\gamma(\top) = \mathbb{Z}_{32}\). For an operator \(\mathit{op}\) the abstract evaluation \(\widehat{\mathit{op}}(\ell_1, \ell_2)\) is \(\top\) if some \(\ell_i = \top\), else \(\bot\) if some \(\ell_i = \bot\), else \(\mathit{op}(\ell_1, \ell_2)\) computed in \(\mathbb{Z}_{32}\). It is monotone, and sound: \(\mathit{op}(a_1, a_2) \in \gamma(\widehat{\mathit{op}}(\ell_1, \ell_2))\) whenever \(a_i \in \gamma(\ell_i)\).

Abstract evaluation

\(\widehat{\mathrm{add}}(20, 1) = 21\); \(\widehat{\mathrm{mul}}(\top, 0) = \top\) (Definition 17.1.2 is deliberately simple; LLVM refines this case to 0, see §6); \(\widehat{\mathrm{lt}}(\bot, 5) = \bot\): an operand without evidence produces no evidence.

Definition 17.1.3 (Dense constant-propagation framework)

Let \(\mathit{Vars}\) be the variables of \(F\). An environment is a map \(\rho : \mathit{Vars} \to L_c\), ordered pointwise; \(\rho_\bot\) maps every variable to \(\bot\). The transfer function of a statement \(x \gets e\) is \(\rho \mapsto \rho[x \mapsto \hat{e}(\rho)]\), where \(\hat{e}\) evaluates \(e\) with Definition 17.1.2; a block's transfer function \(f_B\) composes those of its statements; branches do not change \(\rho\). The boundary value \(\iota\) maps parameters to \(\top\) and everything else to \(\bot\). The dense CP solution is the least fixed point of \(\mathrm{IN}[r] = \iota\), \(\mathrm{IN}[B] = \bigsqcup_{P \in \mathrm{preds}(B)} \mathrm{OUT}[P]\), \(\mathrm{OUT}[B] = f_B(\mathrm{IN}[B])\) (Ch 14, Definition 14.2.9).

Algorithm 17.1.4 (Kildall's dense constant propagation)

Input: a CFG \(G = (N, E, r)\) with statements in each block; parameters.
Output: \(\mathrm{OUT}[B] : \mathit{Vars} \to L_c\) for every block.
Precondition: \(G\) has one entry \(r\) without predecessors.
Postcondition: \(\mathrm{OUT}\) is the least solution of Definition 17.1.3 (Theorem 17.1.14).
Invariant: after every visit, \(\mathrm{OUT}[B] \sqsubseteq\) the least solution, and \(\mathrm{OUT}[B]\) only rises.

function KildallCP(G, params):
    for each block B: OUT[B] ← ρ⊥
    order ← ReversePostorder(G)
    changed ← true
    while changed:                                  # one round-robin pass
        changed ← false
        for B in order:
            ρ ← (B = r) ? ι : join of OUT[P] over P in preds(B)    # pointwise ⊔
            for each statement x ← e in B, in order:
                ρ[x] ← AbstractEval(e, ρ)            # Definition 17.1.2
            if ρ ≠ OUT[B]: OUT[B] ← ρ; changed ← true
    return OUT

Definition 17.1.5 (SSA value graph; sparse CP equations)

Let \(F\) be in strict SSA form (Ch 16) with values \(\mathit{Val}\) and parameters \(\mathit{Par} \subseteq \mathit{Val}\). The SSA edges are the pairs \((d, u)\) where value \(d\) is an operand of instruction \(u\). For each non-parameter value \(v\) the sparse CP equation is \(V(v) = \widehat{\mathit{op}}(V(a_1), V(a_2))\) if \(v = \mathit{op}\ a_1, a_2\), and \(V(v) = \bigsqcup_{k} V(a_k)\) if \(v = \phi(a_1\!:\!P_1, \dots, a_m\!:\!P_m)\), with \(V(p) = \top\) for parameters and \(V(c) = c\) for literals. The sparse simple CP (SSC) solution is the least solution.

Algorithm 17.1.6 (Sparse simple constant propagation, SSC)

Input: a strict SSA function.
Output: \(V : \mathit{Val} \to L_c\).
Precondition: strict SSA (every use is dominated by its definition).
Postcondition: \(V\) is the least solution of Definition 17.1.5.
Invariant: \(V \sqsubseteq\) the least solution; every instruction whose equation is not satisfied by the current \(V\) is on the worklist.

function SSC(F):
    V[p] ← ⊤ for parameters;  V[v] ← ⊥ for every other value
    W ← every instruction that defines a value, in program order
    while W ≠ []:
        I ← pop front of W
        new ← (I is a phi) ? ⊔ over all operands a of I: Eval(a)
                           : AbstractEval(I, V)
        if new ≠ V[I]:
            V[I] ← new
            append every user of I that is not already in W
    return V
function Eval(a): return (a is a literal) ? a : V[a]

The conditional algorithms add one more unknown per CFG edge: is it executable, i.e. can some execution traverse it?

Definition 17.1.7 (SCCP equations)

Let \(X \subseteq E \cup \{(\ast, r)\}\) be a set of executable edges and call a block executable if some edge of \(X\) enters it. The SCCP system over \((V, X)\) is:

\((\ast, r) \in X\).
If \(B\) is executable and ends in br S, then \((B, S) \in X\). If \(B\) ends in cbr c, T, F: \((B, T) \in X\) if \(V(c) = \top\) or \(V(c)\) is a nonzero constant; \((B, F) \in X\) if \(V(c) = \top\) or \(V(c) = 0\); if \(V(c) = \bot\), neither.
For a value \(v\) in an executable block: \(V(v) = \widehat{\mathit{op}}(\dots)\) as in Definition 17.1.5 for operations, and \(V(v) = \bigsqcup \{\, V(a_k) \mid (P_k, B) \in X \,\}\) for a phi in block \(B\). For a value in a non-executable block, \(V(v) = \bot\).

Order pairs by \((V, X) \sqsubseteq (V', X')\) iff \(V \sqsubseteq V'\) pointwise and \(X \subseteq X'\). The SCCP solution is the least \((V, X)\) satisfying the system. The dense conditional CP of Wegbreit [Weg75] (Wegman–Zadeck's CC) solves the same system with Kildall's environments.

Algorithm 17.1.8 (Sparse conditional constant propagation, Wegman–Zadeck)

Input: a strict SSA function \(F\).
Output: \(V : \mathit{Val} \to L_c\), the executable edges \(X\) and blocks.
Precondition: strict SSA; every block ends in br, cbr or ret.
Postcondition: \((V, X)\) is the least solution of Definition 17.1.7 (Theorem 17.1.9 (b)).
Invariant: (I1) \(V \sqsubseteq V^\ast\) and \(X \subseteq X^\ast\) for the least solution \((V^\ast, X^\ast)\); (I2) every edge that rule 2 requires but that is not in \(X\) is on FlowWL; (I3) every instruction in an executable block whose equation the current \(V\) violates is on SSAWL.

function SCCP(F):
    V[p] ← ⊤ for parameters;  V[v] ← ⊥ otherwise
    X ← ∅;  Exec ← ∅
    FlowWL ← [(∗, entry)];  SSAWL ← []                 # FIFO queues
    while FlowWL ≠ [] or SSAWL ≠ []:
        if FlowWL ≠ []:                                  # edges first
            (P, B) ← pop FlowWL
            if (P, B) ∈ X: continue
            X ← X ∪ {(P, B)}
            for each phi φ of B: Visit(φ)                # a new operand may count now
            if B ∉ Exec:
                Exec ← Exec ∪ {B}
                for each non-phi instruction I of B, in order: Visit(I)
        else:
            I ← pop SSAWL
            if block(I) ∈ Exec: Visit(I)                 # otherwise wait for an edge

function Visit(I):
    if I is φ in block B:     Update(I, ⊔ { Eval(a_k) : (P_k, B) ∈ X })
    else if I = br S:         PushEdge(block(I), S)
    else if I = cbr c, T, F:
        if Eval(c) = ⊤:            PushEdge(block(I), T); PushEdge(block(I), F)
        else if Eval(c) ≠ ⊥:       PushEdge(block(I), Eval(c) ≠ 0 ? T : F)
    else if I defines a value: Update(I, AbstractEval(I, V))
function Update(v, new):
    if new ≠ V[v]: V[v] ← new; append each user of v not already in SSAWL
function PushEdge(P, S): if (P, S) ∉ X and (P, S) ∉ FlowWL: append (P, S) to FlowWL

scalaropt.sccp in tools/course/lib/ is this algorithm line by line (FIFO queues, edges drained first), and so is the drill sccp-trace; pebble-sccp implements it on LLVM IR with ConstantInt values (exercise E1).

3. Worked example¶

Kildall's dense constant propagation¶

Kildall's algorithm needs no SSA, so run it on the running example before mem2reg: variables x i j, one assignment per statement. As a Ch 14 program (the if conditions do not matter to an unconditional analysis; t u r s are the temporaries of while.end):

A: x = 1; i = 0; j = 0 -> B          # entry
B: if i < n -> C, F                  # while.cond
C: if x < 1 -> D, E                  # while.body (the test x != 1)
D: x = 2 -> E                        # if.then
E: i = i + 1; j = j + 1 -> B         # if.end
F: t = i * 4; u = j * 4; r = t - u; s = r + x; ret s

Round-robin in RPO (A, B, F, C, D, E), OUT sets of x i j (variables not listed are \(\bot\); bold = changed in that pass). Computed with dataflow.cp_problem + dataflow.solve(..., "round-robin") from tools/course/lib:

block	pass 1	pass 2	pass 3
A	{i=0, j=0, x=1}	{i=0, j=0, x=1}	{i=0, j=0, x=1}
B	{i=0, j=0, x=1}	{i=⊤, j=⊤, x=⊤}	{i=⊤, j=⊤, x=⊤}
F	{…, r=0, s=1, t=0, u=0}	{all ⊤}	{all ⊤}
C	{i=0, j=0, x=1}	{i=⊤, j=⊤, x=⊤}	{i=⊤, j=⊤, x=⊤}
D	{i=0, j=0, x=2}	{i=⊤, j=⊤, x=2}	{i=⊤, j=⊤, x=2}
E	{i=1, j=1, x=⊤}	{i=⊤, j=⊤, x=⊤}	{i=⊤, j=⊤, x=⊤}

Pass 1: B sees only A (E is still \(\rho_\bot\)), so everything looks constant; E joins C (\(x = 1\)) and D (\(x = 2\)) into \(x = \top\).
Pass 2: B joins A (\(i = 0\)) with E (\(i = 1\)): \(\top\), and the same for \(j\) and \(x\); everything downstream becomes \(\top\).
Pass 3 changes nothing (3 passes, 18 block evaluations). Result: no constants at all. The value 2 from D reaches E even though D never runs.

Sparse simple constant propagation¶

SSC (Algorithm 17.1.6) on the SSA form. The worklist starts with the twelve values in program order; bold = changed. Computed by scalaropt.sparse_cp (27 visits):

step	visit	new value	changed?	worklist after
1	`i.0`	0	yes	x.0 j.0 cmp cmp1 x.1 add add2 mul mul3 sub add4
2	`x.0`	1	yes	j.0 cmp cmp1 x.1 add add2 mul mul3 sub add4
3	`j.0`	0	yes	cmp cmp1 x.1 add add2 mul mul3 sub add4
4	`cmp`	⊤	yes	cmp1 x.1 add add2 mul mul3 sub add4
5	`cmp1`	0	yes	x.1 add add2 mul mul3 sub add4
6	`x.1`	⊤	yes	add add2 mul mul3 sub add4 x.0
7	`add`	1	yes	add2 mul mul3 sub add4 x.0 i.0
8	`add2`	1	yes	mul mul3 sub add4 x.0 i.0 j.0
9	`mul`	0	yes	mul3 sub add4 x.0 i.0 j.0
10	`mul3`	0	yes	sub add4 x.0 i.0 j.0
11	`sub`	0	yes	add4 x.0 i.0 j.0
12	`add4`	1	yes	x.0 i.0 j.0
13	`x.0`	⊤	yes	i.0 j.0 cmp1 x.1 add4
14	`i.0`	⊤	yes	j.0 cmp1 x.1 add4 cmp add mul
15	`j.0`	⊤	yes	cmp1 x.1 add4 cmp add mul add2 mul3
16	`cmp1`	⊤	yes	x.1 add4 cmp add mul add2 mul3
17	`x.1`	⊤	no	add4 cmp add mul add2 mul3
18	`add4`	⊤	yes	cmp add mul add2 mul3
19	`cmp`	⊤	no	add mul add2 mul3
20	`add`	⊤	yes	mul add2 mul3 i.0
21	`mul`	⊤	yes	add2 mul3 i.0 sub
22	`add2`	⊤	yes	mul3 i.0 sub j.0
23	`mul3`	⊤	yes	i.0 sub j.0
24	`i.0`	⊤	no	sub j.0
25	`sub`	⊤	yes	j.0 add4
26	`j.0`	⊤	no	add4
27	`add4`	⊤	no	—

Step 1 is the optimism of sparse propagation: i.0 = phi [0, entry], [add, if.end] ignores its second operand while add is still \(\bot\). Step 6 is where SSC loses x: the phi x.1 joins the literal 2 from if.then although cmp1 is already known to be 0. The final solution is the same as Kildall's (every value \(\top\)), as Theorem 17.1.11 predicts.

Sparse conditional constant propagation¶

SCCP (Algorithm 17.1.8) on the same function, computed by scalaropt.sccp and printed by the drill's worked solution. "Visited" lists the instructions evaluated in the step (cbr/br/ret are terminators); B.term in the worklists is block B's terminator:

step	pop	visited	lattice changes	flow worklist	SSA worklist
1	edge ∗→entry	`br`	none	entry→while.cond	—
2	edge entry→while.cond	`i.0`, `x.0`, `j.0`, `cmp`, `cbr`	`i.0` ⊥→0, `x.0` ⊥→1, `j.0` ⊥→0, `cmp` ⊥→⊤	while.cond→while.body while.cond→while.end	cmp add mul cmp1 x.1 add4 add2 mul3 while.cond.term
3	edge while.cond→while.body	`cmp1`, `cbr`	`cmp1` ⊥→0	while.cond→while.end while.body→if.end	cmp add mul cmp1 x.1 add4 add2 mul3 while.cond.term while.body.term
4	edge while.cond→while.end	`mul`, `mul3`, `sub`, `add4`, `ret`	`mul` ⊥→0, `mul3` ⊥→0, `sub` ⊥→0, `add4` ⊥→1	while.body→if.end	… sub while.end.term
5	edge while.body→if.end	`x.1`, `add`, `add2`, `br`	`x.1` ⊥→1, `add` ⊥→1, `add2` ⊥→1	if.end→while.cond	… x.0 i.0 j.0
6	edge if.end→while.cond	`i.0`, `x.0`, `j.0`	`i.0` 0→⊤, `j.0` 0→⊤	—	cmp add mul cmp1 x.1 add4 add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
7	use cmp	`cmp`	none	—	add mul cmp1 x.1 add4 add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
8	use add	`add`	`add` 1→⊤	—	mul cmp1 x.1 add4 add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
9	use mul	`mul`	`mul` 0→⊤	—	cmp1 x.1 add4 add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
10	use cmp1	`cmp1`	none	—	x.1 add4 add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
11	use x.1	`x.1`	none	—	add4 add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
12	use add4	`add4`	none	—	add2 mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
13	use add2	`add2`	`add2` 1→⊤	—	mul3 while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
14	use mul3	`mul3`	`mul3` 0→⊤	—	while.cond.term while.body.term sub while.end.term x.0 i.0 j.0
15	use while.cond.term	`cbr`	none	—	while.body.term sub while.end.term x.0 i.0 j.0
16	use while.body.term	`cbr`	none	—	sub while.end.term x.0 i.0 j.0
17	use sub	`sub`	`sub` 0→⊤	—	while.end.term x.0 i.0 j.0 add4
18	use while.end.term	`ret`	none	—	x.0 i.0 j.0 add4
19	use x.0	`x.0`	none	—	i.0 j.0 add4
20	use i.0	`i.0`	none	—	j.0 add4
21	use j.0	`j.0`	none	—	add4
22	use add4	`add4`	`add4` 1→⊤	—	while.end.term
23	use while.end.term	`ret`	none	—	—

(In steps 3–5 the SSA worklist is abbreviated with …; it only grows, and step 6 shows it in full.) Both queues are empty after step 23: 37 instruction visits. The decisive steps:

Step 3: cmp1 = ne x.0, 1 evaluates to 0 because x.0 is 1 so far, so the cbr pushes only while.body→if.end. The edge into if.then is never pushed.
Step 5: x.1 = phi [2, if.then], [x.0, while.body] joins only the operand on its executable edge: \(V(\text{x.1}) = V(\text{x.0}) = 1\). SSC joined the 2 here.
Step 6: the back edge makes i.0 and j.0 overdefined (0 ⊔ 1); x.0 stays \(1 \sqcup 1 = 1\).
Step 15–16: re-visiting the branches changes nothing: cmp was already \(\top\), cmp1 is still 0.

Result: \(V(\text{x.0}) = V(\text{x.1}) = 1\), \(V(\text{cmp1}) = 0\); everything else \(\top\); if.then is not executable. pebble-sccp therefore rewrites add4 = add sub, x.0 to add sub, 1 and deletes if.then (the lit test tests/ch17/lit/sccp-running.ll).

CP + DCE iterated does not get there. Run SSC, fold every branch whose condition is a constant, delete unreachable blocks, repeat (scalaropt.cp_dce_fixpoint): round 1 finds no constant condition (SSC says cmp1 is \(\top\)), so nothing is folded and the fixed point is reached after one round with no constants. This is the witness for the strictness part of Theorem 17.1.12.

Try it

./course drill sccp-trace --seed 4 --difficulty medium --solution traces SCCP on a random function in the same format; --difficulty hard also asks which constants simple CP misses.

4. Invariants and correctness¶

Theorem 17.1.9 (SCCP: termination, bound, least solution)

Let \(U\) be the number of SSA edges, \(e\) the number of CFG edges and \(I\) the number of instructions. (a) Every value's lattice element changes at most twice, and every edge is added to \(X\) at most once. (b) Algorithm 17.1.8 terminates after at most \(2U + e + I + \sum_\phi \lvert \mathrm{preds}(\phi) \rvert\) instruction visits and returns the least solution of Definition 17.1.7.

Proof

(a) Update only changes \(V[v]\) to the value of its equation; by (I1) every value computed is below the least solution, and by induction on steps the values only rise: an equation's right-hand side is monotone in \(V\) and in \(X\), both of which only grow. A rising chain in \(L_c\) has at most two steps (\(\bot \sqsubset c \sqsubset \top\)). An edge enters \(X\) once (the continue on re-pops). (b) Visits. A value change appends at most the value's users: at most \(2U\) SSA-worklist pops in total. Each edge is popped as new at most once and then visits the phis of its target, and each block's non-phi instructions are visited once when the block first becomes executable: at most \(\sum_\phi \lvert\mathrm{preds}\rvert + I\) visits, plus at most \(e\) edge pops. Invariants. Initially (I1) holds (\(V\) is \(\bot\) except parameters, \(X = \emptyset\)), (I2) holds (only rule 1 applies, and \((\ast, r)\) is queued) and (I3) holds (no block is executable). An edge pop adds an edge that rule 2 requires (by (I2) it was queued only when required) and re-evaluates exactly the equations that mention it (the phis of its target, and on first entry all instructions of the block); an SSA pop re-evaluates one equation. Each re-evaluation sets \(V[v]\) to a value \(\sqsubseteq\) the least solution (monotonicity, (I1)), and pushes every equation or edge that may have become violated, restoring (I2) and (I3). At termination both queues are empty, so by (I2) and (I3) every equation holds: \((V, X)\) is a solution, and by (I1) it is below the least one, so it is the least one.

Lemma 17.1.10 (No ⊥ in executable code)

In the SCCP solution, every value defined in an executable block has \(V(v) \neq \bot\).

Proof

Order the executable instructions by the time their block became executable in the run of Algorithm 17.1.8, then by position in the block, and use induction on this order (values only rise, so "\(\neq \bot\) at the end" is what is proved). The edges of \(X\) form paths from the entry (rule 2 adds an edge only out of an executable block), so every dominator of an executable block \(B\) lies on such a path and became executable no later than \(B\). If \(v\) in \(B\) is an operation, each operand is a literal, a parameter (\(\top\)) or a value defined earlier in \(B\) or in a strict dominator of \(B\) (strict SSA), hence earlier in the order and \(\neq \bot\); \(\widehat{\mathit{op}}\) of non-\(\bot\) arguments is \(\neq \bot\). If \(v\) is a phi, take the edge \((P, B)\) that first made \(B\) executable. \(P\) was executable before \(B\), and the phi's operand on that edge is a literal, a parameter, or defined in a block \(D\) that dominates \(P\). \(D \neq B\) (otherwise \(B\) would dominate \(P\), and \(P\) could not become executable before \(B\)), so \(D\) became executable no later than \(P\), before \(B\): the operand is \(\neq \bot\), and so is the join over the executable edges, which includes \((P, B)\). (This order also covers irreducible CFGs, where RPO would not.)

Theorem 17.1.11 (Dense and sparse simple CP agree on SSA)

On a strict SSA function, for every value \(v\) and every block \(B\) dominated by the definition of \(v\), Kildall's solution (Algorithm 17.1.4 with SSA values as variables) has \(\mathrm{OUT}[B](v) = V_{\mathrm{SSC}}(v)\), the SSC solution. In particular they report the same constants.

Proof sketch (full proof: [WZ91, §3])

Wegman and Zadeck prove that SC and SSC find the same constants. On SSA the argument is short. A value \(v\) is assigned only in its defining block \(D\), so on every path from \(D\) to a block \(B\) that \(D\) dominates, the environment's entry for \(v\) is carried unchanged; at a join inside \(D\)'s dominance region every predecessor is also dominated by \(D\) (or contributes \(\bot\) for \(v\), which is the unit of \(\sqcup\)), so the dense join never mixes two different facts for the same SSA value. Hence the dense system restricted to the entries \((B, v)\) with \(D \mathrel{\mathrm{dom}} B\) is equivalent to the sparse system with one unknown per value, and a phi's dense evaluation reads exactly the operands' values at the ends of the predecessors. Both least solutions are then equal by induction on the Kleene iterates of the equivalent systems (the test ConstantPropagation.test_dense_equals_sparse checks it on 250 random functions).

Theorem 17.1.12 (SCCP ⊇ constant propagation and dead-code elimination, iterated)

Let CP+DCE be: solve SSC on the edges \(E_k\) (initially all edges), delete the edges out of every conditional branch whose condition SSC finds constant, except the selected one, delete blocks that became unreachable, and repeat until no edge is deleted, ending with edges \(E^\ast\) and values \(V^\ast\). Let \((V_S, X)\) be the SCCP solution. Then (a) every SCCP-executable block is reachable in \(E^\ast\), and (b) every value in an SCCP-executable block that CP+DCE finds equal to \(c\) has \(V_S(v) = c\). (c) The inclusion is strict on the running example.

Proof

Write \(\Phi\) for the monotone operator whose least fixed point is the SCCP solution (Definition 17.1.7, rules 1–3 applied once to a pair \((V, Y)\)). Let \(V_k\) be the SSC solution on \(E_k\) and \(Y_k\) the edges of \(E_k\) whose source is reachable through \(E_k\) (plus \((\ast, r)\)). Step 1: \(V_{k} \sqsubseteq V_{k-1}\). The SSC operator on \(E_k\) joins each phi over a subset of the operands the operator on \(E_{k-1}\) joins and gives \(\bot\) to values in blocks that became unreachable, so it is pointwise below it; if \(F \sqsubseteq G\) pointwise and both are monotone then \(F(\mathrm{lfp}\,G) \sqsubseteq G(\mathrm{lfp}\,G) = \mathrm{lfp}\,G\), so \(\mathrm{lfp}\,G\) is a pre-fixed point of \(F\) and \(\mathrm{lfp}\,F \sqsubseteq \mathrm{lfp}\,G\) (the least fixed point lies below every pre-fixed point: Knaster–Tarski, Ch 14, Theorem 14.1.12). Step 2: \((V_k, Y_k)\) is a pre-fixed point of \(\Phi\). Edges: take \((B, S)\) produced by rule 2 from \((V_k, Y_k)\). \(B\) is entered by an edge of \(Y_k\), so it is reachable in \(E_k\). If \((B, S) \notin E_k\), it was deleted in some round \(j < k\) because \(V_j(c_B)\) was a constant selecting another successor; by Step 1 \(V_k(c_B) \sqsubseteq V_j(c_B)\), so \(V_k(c_B)\) is \(\bot\) (rule 2 produces nothing) or that same constant (rule 2 produces only the other successor): contradiction. So \((B, S) \in E_k\) with \(B\) reachable: \((B, S) \in Y_k\). Values: for \(v\) in a block entered by \(Y_k\), rule 3 is SSC's equation on \(E_k\), whose solution is \(V_k\), so it returns \(V_k(v)\); for other \(v\) it returns \(\bot \sqsubseteq V_k(v)\). Hence \(\Phi(V_k, Y_k) \sqsubseteq (V_k, Y_k)\). Step 3. By the same principle the least fixed point is below every pre-fixed point: \(X \subseteq Y^\ast\) and \(V_S \sqsubseteq V^\ast\) for the final round. (a) follows from \(X \subseteq Y^\ast\). For (b), if \(V^\ast(v) = c\) and \(v\)'s block is SCCP-executable, then \(V_S(v) \in \{\bot, c\}\), and by Lemma 17.1.10 \(V_S(v) \neq \bot\). (c) On the running example CP+DCE stops after one round with \(V^\ast(\text{x.0}) = \top\) (§3), while \(V_S(\text{x.0}) = 1\). The unit test ConstantPropagation.test_sccp_contains_cp_dce_fixpoint checks (a) and (b) on 250 random functions and finds strict cases.

Theorem 17.1.13 (SCCP is sound)

In every execution of \(F\) on any inputs, every traversed edge is in \(X\), and every value \(v\) computed has its concrete value in \(\gamma(V_S(v))\). In particular a value with \(V_S(v) = c\) is the constant \(c\) (Definition 17.1.2), and a non-executable block never runs.

Proof

By induction on the number of executed instructions. Initially only the entry edge \((\ast, r) \in X\) has been traversed. Executing an operation whose operands have concrete values in \(\gamma\) of their lattice elements gives, by soundness of \(\widehat{\mathit{op}}\), a value in \(\gamma\) of the right-hand side of its equation, which is \(\sqsubseteq V_S(v)\) because \((V_S, X)\) is a solution. Arriving at a phi's block over edge \((P, B)\): that edge was traversed, so it is in \(X\); the phi takes the operand \(a_k\) for \(P\), whose value lies in \(\gamma(V_S(a_k)) \subseteq \gamma(\bigsqcup_{(P_k,B) \in X} V_S(a_k))\). A cbr c whose condition has concrete value \(z \in \gamma(V_S(c))\): \(V_S(c) \neq \bot\) because \(z\) exists; if \(V_S(c) = \top\) both successors' edges are in \(X\) (rule 2), and if \(V_S(c)\) is a constant it equals \(z\) and rule 2 put exactly the taken edge in \(X\). br is rule 2 directly.

Theorem 17.1.14 (Kildall's CP terminates and computes the least solution)

Algorithm 17.1.4 terminates after at most \(2 \lvert \mathit{Vars} \rvert \cdot n + 1\) passes, where \(n = \lvert N \rvert\), and returns the least solution of Definition 17.1.3. Every constant it reports is a constant in the sense of Definition 17.1.2.

Proof

Monotonicity. Each statement's transfer function is monotone because \(\widehat{\mathit{op}}\) is monotone (Definition 17.1.2) and environment update is monotone in both arguments; joins are monotone. The equation system of Definition 17.1.3 is therefore a monotone function on the finite-height lattice \((\mathit{Vars} \to L_c)^N\). Least fixed point. The algorithm is round-robin iteration from \(\bot\), so by Ch 14, Theorem 14.4.4 it computes \(\mathrm{lfp}\), the least solution. Bound. Each pass that is not the last changes at least one \(\mathrm{OUT}[B](x)\), which only rises (by induction on passes, each new value is computed from larger inputs by monotone functions), and each such entry can rise at most \(h(L_c) = 2\) times; there are \(n \lvert \mathit{Vars} \rvert\) entries, so at most \(2 n \lvert \mathit{Vars} \rvert\) changing passes plus one confirming pass. Soundness. Let \(\sigma_B\) be the concrete environment at the end of \(B\) in some execution. By induction on the execution length, \(\sigma_B(x) \in \gamma(\mathrm{OUT}[B](x))\) for every variable the execution has assigned: the entry satisfies it by \(\iota\) (parameters are \(\top\)), a statement preserves it by soundness of \(\widehat{\mathit{op}}\), and control arriving at \(B\) from \(P\) satisfies it because \(\mathrm{OUT}[P] \sqsubseteq \mathrm{IN}[B]\). Hence if \(\mathrm{OUT}[B](x) = c\) then every execution reaching the end of \(B\) has \(x = c\).

Which precondition breaks it. Without strict SSA the sparse equations are not the program's semantics (a use could see a definition from another path). With undefined behavior in the IR the soundness argument changes: LLVM's SCCP may exploit undef/poison (it may treat an undef operand as any constant it likes, a refinement), whereas this lesson's \(\widehat{\mathit{op}}\) treats them as \(\top\); pebble-sccp follows the lesson and never folds to poison (tests/ch17/lit/sccp-no-fold.ll).

5. Complexity¶

Variables: \(n\) blocks, \(e\) CFG edges, \(\lvert \mathit{Vars} \rvert\) variables, \(I\) instructions, \(U\) SSA edges (operand uses).

Algorithm	Time (worst)	Time (typical)	Space	Justification
Kildall dense CP (17.1.4)	\(O(\lvert\mathit{Vars}\rvert^2 \cdot n \cdot e)\) map operations	a few passes (\(d(G) + 3\) on reducible CFGs)	\(O(n \lvert \mathit{Vars} \rvert)\)	\(2 n \lvert\mathit{Vars}\rvert\) changing passes (Theorem 17.1.14), each pass joins \(e\) maps of size \(\lvert\mathit{Vars}\rvert\)
Sparse simple CP (17.1.6)	\(O(U + I)\) evaluations	linear	\(O(I)\)	each value rises twice and pushes its users (as Theorem 17.1.9 (a))
Dense conditional CP [Weg75]	as Kildall, plus \(e\) edge flags	a few passes	\(O(n \lvert\mathit{Vars}\rvert + e)\)	same argument, with one more lattice per edge
SCCP (17.1.8)	\(O(U + e + I)\) visits	linear, ~2–3 visits per instruction	\(O(I + e)\)	Theorem 17.1.9 (b)

Pathological family for dense CP. Let \(P_k\) be the loop A: x1 = 0; …; xk = 0 → B, B: if c < n → C, E, C: xk = x(k−1); …; x2 = x1; x1 = xk + 1 → B, E: ret x1 (the copies in \(C\) are listed against the dependence order). On the first pass \(x_1\) becomes 1 in \(C\); each later pass pushes the \(\top\) created at \(B\)'s join one copy further through \(C\), because within \(C\) the copy that would carry it runs before its source is updated. Round-robin therefore needs exactly \(k + 2\) passes over 4 blocks, each joining maps of \(k\) variables: \(\Theta(k^2)\) map-entry operations for a loop of \(k + 1\) statements (5, 7 and 10 passes for \(k = 3, 5, 8\), measured with dataflow.solve(cp_problem(P_k), "round-robin")). On the SSA form of the same loop, each SSA value rises at most twice and each rise re-queues only its one or two users, so SSC needs \(\Theta(k)\) visits. On real code the difference is small: the lab's ch17-compare --table --time analyzes the whole 12-function corpus with each of its four algorithms in about 0.03–0.12 ms in total on this container.

Real-world scale. SCCP is one of the cheapest scalar passes: LLVM runs it once in the function simplification pipeline and IPSCCP once per module at -O2 [LLVM-Pipelines], and GCC 14 runs CCP five times at -O2 (ccp1–ccp5 in gcc-14 -O2 -fdump-passes, [GCC-TreeSSAPasses]).

Constant folding through \(\top\) — \(\widehat{\mathrm{mul}}(\top, 0) = 0\), \(\widehat{\mathrm{and}}(\top, 0) = 0\): LLVM's SCCPInstVisitor folds these [LLVM-SCCP]. Trade-off: still monotone, but every operator needs its own rules; this chapter's oracles and pebble-sccp leave them out so that the lab's Python and C++ agree exactly.
Richer lattices — LLVM's ValueLatticeElement is not flat: it also holds constantrange (with a widening after MaxNumRangeExtensions steps, Ch 14 Lesson 14.7) and "not a constant" [LLVM-SCCP]; this is SCCP with the interval domain of Lesson 17.2. Trade-off: more constants (the range(...) attributes in the §7 box) for a taller lattice.
Undef as "any constant" — LLVM's SCCP lets undef merge with any constant (refinement: undef may be chosen equal to it) and resolves branches on undef at the end. Trade-off: more folding, subtle correctness rules (Ch 13's poison/undef lesson).
Predicate-aware SCCP — x == 3 on the true edge of if (x == 3) is a constant. LLVM's PredicateInfo inserts ssa.copy per edge so SCCP can use it (e-SSA, Ch 14 Lesson 14.6 §6); GVN does the same (Lesson 17.5 §6). Trade-off: more SSA values.
Combining with value numbering — Click and Cooper solve constants, reachability and congruences together and show it beats any order of separate passes [CC95, Cli95t]; Lesson 17.8.
Interprocedural SCCP (IPSCCP, preview of Ch 20) — run the same solver over all internal functions of a module at once: a call's arguments join into the callee's parameters, the callee's returned values join into the call's result, and a function's blocks become executable when a call to it does [LLVM-IPSCCP]. Trade-off: needs all callers visible (internal linkage), and the lattice is only as good as the call graph.
Dense conditional CP (Wegbreit) — the dense twin of SCCP, same result as SCCP (checked by test_conditional_dense_equals_sccp) and \(\Theta(n \lvert\mathit{Vars}\rvert)\) space; historically first [Weg75].

7. In real compilers¶

Kildall's dense constant propagation¶

Dense constant propagation survives where values are not in SSA: GCC's RTL pass cprop propagates constants and copies over available assignments, a dense bit-vector problem solved with the same compute_available routine as RTL CSE [GCC-CPROP]. On GIMPLE (SSA) GCC uses sparse CCP instead, so by the time RTL cprop runs there is usually nothing left.

GCC: dense global constant propagation on RTL, after sparse CCP

Reproduce (gcc 14.2.0 for the dump; the source is gcc 15.1.0's cprop.cc, fetched from the gcc-mirror repository on GitHub):

cat > kd.c <<'EOF'
int kildall(int p, int q) {
  int k = 3;
  int r;
  if (p)
    r = k + q;
  else
    r = k * q;
  return r + k;
}
EOF
gcc-14 -O2 -fdump-rtl-cprop1-details -S kd.c -o /dev/null
grep -h '^CPROP of' kd.c.*r.cprop1
curl -sSfL https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15.1.0/gcc/cprop.cc |
  sed -n '/^compute_cprop_data/,/^}/p' | head -6

Output:

CPROP of kildall, 6 basic blocks, 224 bytes needed, 0 local const props, 0 local copy props, 0 global const props, 0 global copy props
compute_cprop_data (void)
{
  basic_block bb;

  compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table);
  compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);

What to notice: RTL cprop computes per-block available assignments (cprop_avin, cprop_avout) exactly as Kildall does per program point, and found 0 global const props: GIMPLE's sparse CCP already replaced k by 3 everywhere. Dense and sparse CP find the same constants (Theorem 17.1.11), so the second, dense run is only useful for constants that appear later, during RTL expansion.

Sparse simple constant propagation¶

No production compiler ships the unconditional sparse algorithm on its own; its role today is played by pessimistic sparse folding along def-use chains, which gives up SSC's optimism at loop phis. LLVM's instsimplify folds constants operand by operand, SCCP's solver is the optimistic version.

Pessimistic vs optimistic sparse folding: instsimplify vs sccp

Reproduce (opt 23.1.2):

cat > opt.ll <<'EOF'
define i32 @chain(i32 %n) {
entry:
  %a = add i32 20, 1
  %b = mul i32 %a, 2
  %c = sub i32 %b, %a
  br label %loop
loop:
  %k = phi i32 [ 3, %entry ], [ %k2, %loop ]
  %i = phi i32 [ 0, %entry ], [ %i2, %loop ]
  %odd = trunc i32 %i to i1
  %k2 = select i1 %odd, i32 %k, i32 3   ; 3 or k: optimistically 3
  %i2 = add i32 %i, 1
  %more = icmp slt i32 %i2, %n
  br i1 %more, label %loop, label %exit
exit:
  %r = add i32 %k2, %c
  ret i32 %r
}
EOF
opt -passes=instsimplify -S opt.ll | sed -n '/^exit:/,/^}/p'
opt -passes=sccp -S opt.ll | sed -n '/^exit:/,/^}/p'

Output:

exit:                                             ; preds = %loop
  %r = add i32 %k2, 21
  ret i32 %r
}
exit:                                             ; preds = %loop
  ret i32 24
}

What to notice: both fold the straight-line chain (%c = 21) by following def-use edges. Only the optimistic solver proves %k = 3: it assumes the back-edge operand %k2 is \(\bot\) on the first visit (step 1 of the SSC trace in §3 does the same), gets %k2 = select(⊤, 3, 3) = 3, and the loop phi stays 3. A pessimistic folder would need %k2 folded before it can fold %k, and vice versa.

Sparse conditional constant propagation¶

LLVM: llvm/lib/Transforms/Utils/SCCPSolver.cpp — SCCPInstVisitor::solve drains BBWorkList (the flow worklist) and the instruction worklists, markEdgeExecutable adds an edge and re-visits the target's phis, visitPHINode joins only feasible incoming values [LLVM-SCCP]; llvm/lib/Transforms/Scalar/SCCP.cpp — runSCCP rewrites the function [LLVM-SCCPPass]; llvm/lib/Transforms/IPO/SCCP.cpp — runIPSCCP [LLVM-IPSCCP]. GCC: gcc/tree-ssa-ccp.cc, a four-level lattice (ccp_lattice_t: UNINITIALIZED, UNDEFINED, CONSTANT, VARYING) over GCC's generic SSA propagation engine; likely_value is the operand rule of Definition 17.1.2 [GCC-CCP] (Lesson 14.6 prints its trace). The production versions differ from Algorithm 17.1.8 in three ways: ranges in the lattice, special folding with \(\top\) operands, and undef handling (§6).

LLVM SCCP on the running example

Reproduce (clang 23.1.2, opt 23.1.2):

cat > run.c <<'EOF'
int run(int n) {
  int x = 1, i = 0, j = 0;
  while (i < n) {
    if (x != 1)
      x = 2;
    i = i + 1;
    j = j + 1;
  }
  int t = i * 4, u = j * 4;
  return t - u + x;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm run.c -o run.O0.ll
opt -passes=mem2reg -S run.O0.ll -o run.ll
opt -passes=sccp -S run.ll | sed -n '/^define/,/^}/p'

Output:

define dso_local range(i32 -2147483647, -2147483648) i32 @run(i32 noundef %n) #0 {
entry:
  br label %while.cond

while.cond:                                       ; preds = %if.end, %entry
  %i.0 = phi i32 [ 0, %entry ], [ %add, %if.end ]
  %j.0 = phi i32 [ 0, %entry ], [ %add2, %if.end ]
  %cmp = icmp slt i32 %i.0, %n
  br i1 %cmp, label %while.body, label %while.end

while.body:                                       ; preds = %while.cond
  br label %if.end

if.end:                                           ; preds = %while.body
  %add = add nsw i32 %i.0, 1
  %add2 = add nsw i32 %j.0, 1
  br label %while.cond, !llvm.loop !5

while.end:                                        ; preds = %while.cond
  %mul = mul nsw i32 %i.0, 4
  %mul3 = mul nsw i32 %j.0, 4
  %sub = sub nsw i32 %mul, %mul3
  %add4 = add nsw i32 %sub, 1
  ret i32 %add4
}

What to notice: exactly the result of the §3 trace: %x.0 and %x.1 are gone (constant 1), %cmp1 folded, the branch in while.body became br label %if.end and if.then was deleted. %i.0 and %j.0 are overdefined, so %sub survives. The range(...) return attribute comes from the range part of LLVM's lattice (Lesson 17.2): %sub + 1 with nsw can be anything but INT_MIN.

IPSCCP (preview of Ch 20): constants across calls

Reproduce (clang 23.1.2, opt 23.1.2):

cat > ip.c <<'EOF'
static int scale(int x, int factor) {
  if (factor == 0)
    return -1;
  return x * factor;
}

int api(int a) { return scale(a, 4) + scale(a + 1, 4); }
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm ip.c -o ip.O0.ll
opt -passes='function(mem2reg),ipsccp' -S ip.O0.ll -o - | sed -n '/^define internal/,/^}/p'

Output:

define internal i32 @scale(i32 noundef %x, i32 noundef %factor) #0 {
entry:
  br label %if.end

if.end:                                           ; preds = %entry
  %mul = mul nsw i32 %x, 4
  br label %return

return:                                           ; preds = %if.end
  ret i32 %mul
}

What to notice: scale is internal and every call passes 4, so the parameter %factor joins to the constant 4, the test factor == 0 is false, and the return -1 block is never executable — SCCP's executable-edge reasoning, applied across the call graph.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/SCCPSolver.cpp and find the class that holds one lattice value per SSA value (the argument type of markOverdefined). What is it called, and which states can it hold besides "constant" and "overdefined"? (Quiz llvm-where-sccp-lattice.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Kildall dense CP	Constants valid on all paths, every edge assumed executable; equals SSC on SSA	\(O(\lvert\mathit{Vars}\rvert^2 n e)\) · slow on large functions	A map per program point; works without SSA	Low (one generic solver)	Non-SSA IRs (GCC RTL `cprop`), teaching
Sparse simple CP (SSC)	Same constants as Kildall (Theorem 17.1.11); optimistic at phis	\(O(U + I)\) · linear	One lattice value per SSA value	Low	Folding along def-use chains; the base of SCCP
SCCP	Strictly more than CP + DCE iterated (Theorem 17.1.12); proves blocks unreachable	\(O(U + e + I)\) · linear, ~2–3 visits per instruction	Constants plus executable edges; drives branch folding	Medium (two worklists, edge bookkeeping)	LLVM `sccp`/`ipsccp`, GCC CCP, MLIR `-sccp`

Choose Kildall's dense CP when the IR is not in SSA and variables are few, or when constant propagation is one instance of an existing generic dense solver. Choose sparse simple CP when you only need folding along def-use chains and branches are handled elsewhere. Choose SCCP when you optimize SSA code at all: it is as cheap as SSC and strictly more precise; add ranges (Lesson 17.2) and predicates when you can afford the taller lattice.

The comparison lab measures the difference on the C corpus (ch17-compare --table labs/ch17-scalar/corpus/*.ll): simple CP finds 7 constants and SCCP 12, and SCCP proves 5 of the 48 blocks unreachable; on the running example alone, 0 vs 3 (x.0, cmp1, x.1).

9. Assessment¶

Quiz (./course quiz 17): kildall-passes, kildall-lattice-height (tag kildall-cp); sparse-cp-values, sparse-vs-dense (tag sparse-cp); sccp-values, sccp-vs-cpdce, llvm-where-sccp-lattice (tag sccp).
Drill: ./course drill sccp-trace (all difficulties; hard also asks for the constants simple CP misses). Kildall's tables: ./course drill dataflow-table from Ch 14 exercises the same round-robin mechanics.
Flashcards: tags kildall-cp, sparse-cp, sccp in flashcards.tsv.
Exercises: E1 pebble-sccp; lab Part A (labs/ch17-scalar/SPEC.md).

References¶

See the chapter references.

Lesson 17.1 — Constant propagation: Kildall, sparse, and conditional¶

1. Problem and motivation¶

Kildall's dense constant propagation¶

Sparse simple constant propagation¶

Sparse conditional constant propagation¶

2. Definitions and algorithms¶

3. Worked example¶

Kildall's dense constant propagation¶

Sparse simple constant propagation¶

Sparse conditional constant propagation¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Kildall's dense constant propagation¶

Sparse simple constant propagation¶

Sparse conditional constant propagation¶

8. Comparison¶

9. Assessment¶

References¶