SPARSE CONDITIONAL CONSTANT PROPAGATION fold the constants and prune the dead branch, together
Two analyses most compilers run separately — constant propagation and unreachable-code elimination — are strictly weaker apart than together. SCCP runs one lattice (⊤ · a constant · ⊥) over the SSA graph and the control-flow graph at once: a value that is constant proves a branch dead, and a dead branch stops a φ from meeting to ⊥. It finds constants neither pass finds alone.
THE TECHNIQUE one lattice over values AND reachability
When a is the constant 3, the test a>0 is always true, so the else-edge is never executed — and b’s φ meets only the live value, staying constant. Turn reachability off (plain constant propagation) and the same φ meets both arms and collapses to ⊥. Toggle it: live demo
“SCCP is just constant folding.” — no. Constant folding evaluates a constant expression; SCCP’s whole power is the conditional part — it uses discovered constants to kill branches, and killed branches to discover more constants. Drop the reachability half and it is strictly weaker. cited
1973 · Kildall — “A Unified Approach to Global Program Optimization” (POPL): the general constant-propagation lattice and meet framework SCCP specialises. 1985 · Mark Wegman & Kenneth Zadeck — “Constant Propagation with Conditional Branches” (POPL): the sparse, conditional algorithm. 1991 · Wegman & Zadeck — the journal version (TOPLAS), the canonical reference; runs on SSA with two worklists (flow edges + SSA edges).
“Sparse” = it propagates along SSA def-use edges, not by revisiting every statement; “conditional” = it tracks which CFG edges are executable. The lattice is 3-level (⊤ / a constant / ⊥) — a variable is lowered at most twice, so it terminates fast. Wegman-Zadeck, 1991
RECOMMEND FOR I-13 the constant survives the branch
The concrete result SCCP proves — that c is the constant 4, not ⊥ — runs on the canonical compiler:
$ i13 run sccp.i13 # a=3 is const; a>0 forces the then-arm; c stays constant
a = 3 cnd = 3
b = 4 -- pick(3>0, 4, 5): only the live arm reaches b
c = 4 -- SCCP proves c==4; a plain meet of {4,5} would give BOTTOM
Recommend: SCCP is LIT in its concrete effect and a real upgrade for an I-13 optimiser — verified that with a=3 the branch is determined and c is the constant 4 (a reachability-blind meet of the two arms would report ⊥ and emit a runtime select). On a bounded, branch-heavy language this is exactly the pass that turns a data-dependent if into a compile-time constant. It needs SSA (150) beneath it and pairs with GVN (152).