Constant Folding and Constant Propagation

Constant folding is a purely local, syntactic rewrite: whenever a compiler sees an operator applied to operands that are themselves compile-time constants, it replaces the whole expression with the single constant that results from evaluating it. `2 + 3` folds to `5`; `"ab" ++ "cd"` folds to `"abcd"`; `true && false` folds to `false`. Folding requires no analysis of program flow — it is a bottom-up evaluation of an expression tree (or its equivalent in an intermediate representation).

Constant propagation is the harder, non-local problem: determining, for a variable `v` at a program point `p`, whether every execution path reaching `p` assigns `v` the same value, and if so, what that value is. This requires reasoning about control flow, because a variable might be constant along one path and not another, or might become constant only after other variables have been shown constant (which is why the two optimizations are run as a single interleaved fixed-point rather than folding once and propagating once). Formally, propagation is stated over an abstract value lattice per variable: ``` ⊤ (undefined / not yet seen — "could become anything") / | \ .. c .. (a specific known constant c) \ | / ⊥ (definitely not a single constant — "overdefined") ``` `⊤` means "no information reaching this point yet" (optimistic starting assumption), a middle element `c` means "this variable holds exactly the constant `c` here," and `⊥` means "this variable is proven to take more than one possible value, or its value depends on runtime input." The meet operator `∧` combines information arriving from multiple predecessors: ``` ⊤ ∧ x = x (no info yet, so take the other side) c ∧ c = c (same constant from two paths agrees) c₁ ∧ c₂ = ⊥ if c₁ ≠ c₂ (different constants — no longer constant) x ∧ ⊥ = ⊥ (⊥ is absorbing — "poisons" the meet) ``` This lattice has height 3 (three "levels": `⊤`, the constants, `⊥`), which is the single most important fact used later to bound the running time of the algorithm.

The classical algorithm, due to Wegman and Zadeck (1991), is sparse conditional constant propagation (SCCP). It is usually presented over a program already in Static Single Assignment (SSA) Form, but the ideas apply, less cleanly, to non-SSA code too; we present it over SSA because that is how it is implemented in practice, and foreshadow that SSA itself is covered separately. SCCP maintains two data structures simultaneously, updated to a joint fixed point: 1. `Value[v]` — the current lattice value (`⊤`, a constant, or `⊥`) for each SSA variable `v`. 2. `ExecutableEdge[(b1, b2)]` — a boolean flag for each control-flow edge, marking whether that edge has been proven reachable. The key insight that makes SCCP more powerful than propagation alone: reachability and constancy are mutually dependent. A branch's condition can only be folded once we know the branch is reachable and its operands are constant; conversely, a block is only reachable if some edge into it has been marked executable. By computing both simultaneously, SCCP can prove branches unreachable (e.g. `if (false)`) and then ignore the values flowing along the dead branch when computing meets, which is strictly more precise than plain propagation run after a separate reachability pass. Two worklists drive the fixed-point iteration: a CFG worklist of edges to (re)examine for reachability, and an SSA worklist of variables whose value may have just changed and whose uses must be revisited. ``` PSEUDOCODE — Sparse Conditional Constant Propagation Input: control-flow graph G in SSA form, entry block B0 Output: Value[v] for every SSA variable v, and the set of executable edges for every variable v: Value[v] := TOP for every edge e in G: ExecutableEdge[e] := false CFGWorklist := { edges out of B0 } SSAWorklist := {} mark B0 as reachable while CFGWorklist is not empty or SSAWorklist is not empty: // ---- process a newly-reachable control-flow edge ---- if CFGWorklist is not empty: e = (pred, block) := CFGWorklist.remove() if not ExecutableEdge[e]: ExecutableEdge[e] := true // visit every phi-function in `block` for each phi node "v := phi(v1 from p1, v2 from p2, ...)" in block: VisitPhi(v, phi-args) // if this is the first time `block` becomes reachable, // process every non-phi statement in it once if block was not previously reachable: mark block reachable for each statement s in block (in order): VisitStatement(s) // ---- process a variable whose value changed ---- elif SSAWorklist is not empty: v := SSAWorklist.remove() for each statement s that uses v: if s is a phi node: VisitPhi(s) else if block containing s is reachable: VisitStatement(s) return Value, ExecutableEdge

function VisitStatement(s): if s is an assignment "v := op(a1, ..., ak)": newVal := Evaluate(op, Value[a1], ..., Value[ak]) // constant folding happens HERE if newVal != Value[v]: Value[v] := newVal SSAWorklist.add(v) else if s is a conditional branch "if c goto Lt else Lf": if Value[c] == TOP: // don't yet know — propagate no edges skip else if Value[c] is a constant TRUE: CFGWorklist.add(edge to Lt) // fold: only the true edge is live else if Value[c] is a constant FALSE: CFGWorklist.add(edge to Lf) // fold: only the false edge is live else // BOTTOM — condition truly unknown CFGWorklist.add(edge to Lt) CFGWorklist.add(edge to Lf) else if s is an unconditional jump "goto L": CFGWorklist.add(edge to L)

function VisitPhi(v, args): // args: list of (value, incoming-edge) newVal := TOP for (ai, edge_i) in args: if ExecutableEdge[edge_i]: newVal := Meet(newVal, Value[ai]) // ignore inputs from dead edges! if newVal != Value[v]: Value[v] := newVal SSAWorklist.add(v)

function Evaluate(op, v1, ..., vk): if any vi == BOTTOM: return BOTTOM if any vi == TOP: return TOP // all operands are known constants — this is constant FOLDING return foldConstant(op, v1, ..., vk)

function Meet(x, y): if x == TOP: return y if y == TOP: return x if x == y: return x // same constant return BOTTOM ``` The subtlety that gives SCCP its extra power over "propagation then folding" is the guarded phi rule: `VisitPhi` only takes the meet over incoming edges already proven executable. A phi with an unreachable predecessor never gets "poisoned" to `⊥` by a value coming down a dead path, which is exactly how `if (false) { x = readInput(); } else { x = 5; }` still lets `x` be folded to `5` after the branch merges.

Time complexity. Let `V` be the number of SSA variables, `E` the number of edges in the SSA def-use graph (i.e., total operand occurrences), and `C` the number of control-flow edges. Each `Value[v]` can only move downward through the lattice: `⊤ → constant → ⊥`, a chain of length at most 2 transitions, because the lattice has height 3. Every time `Value[v]` changes, `v` is pushed onto `SSAWorklist` at most once per change, and each pop triggers revisiting every use of `v`. So the total number of statement-visits attributable to value changes is bounded by `O(V)` changes `× O(deg(v))` uses each, summing to `O(E)` overall. Separately, each control-flow edge is added to `CFGWorklist` and processed to completion at most once (the `ExecutableEdge` flag is monotonic, set once from false to true and never reset), contributing `O(C)`. Each visit does `O(k)` work for a `k`-ary operation, and in typical IRs `k` is a small constant (2 for binary ops, or bounded by phi in-degree). Overall: ``` Time = O(E + C) (linear in program size / def-use edges) Space = O(V + C) (one lattice cell per variable, one flag per edge) ``` This linearity is the crucial payoff of formulating the analysis over a finite-height lattice with monotonic transfer functions — a direct instance of the general Data-Flow Analysis Framework fixed-point theorem, which guarantees termination in time proportional to (number of flow facts) × (lattice height) × (edges), and here the height is a constant (3), collapsing the bound to linear.

Correctness (safety). The central invariant maintained throughout the algorithm is: > At every point in the iteration, `Value[v]` is either `⊤`/`⊥`, or a constant `c` such that on every control-flow path from the entry to the current definition point that the algorithm has proven executable, `v` provably evaluates to `c`. This is an optimistic analysis: it starts by assuming every variable is `⊤` ("as constant as possible — no evidence against it yet") and only weakens toward `⊥` when concrete contradicting evidence (two different constants, or a genuinely input-dependent operand) arrives. Optimism is essential for soundness in the presence of loops: a phi node inside a loop header initially sees `⊤` from the not-yet-analyzed back edge, allowing the loop-invariant part of the meet to determine an initial constant guess, which is only retracted if a later iteration proves it wrong. A pessimistic analysis (starting everything at `⊥`) would never discover loop-carried constants; an unsound analysis (assuming constants without justification) could miscompile the program. The correctness proof is essentially: 1. Monotonicity: `Evaluate` and `Meet` never move a value up the lattice (`⊥` is absorbing, matching constants stay fixed, mismatches only push down to `⊥`, never back up to `⊤`). This guarantees the iteration is monotone decreasing, hence terminates (finite lattice, finite variable count) and converges to the unique least fixed point reachable from the all-`⊤` start, by the Knaster–Tarski argument underlying the general data-flow framework. 2. Reachability soundness: an edge is marked executable only after its guarding condition has been shown (by folding) to definitely take that branch, or shown unresolved (`⊥`), in which case both successor edges are conservatively marked live. So no reachable path is ever mismarked unreachable. 3. Substitution soundness: replacing a use of `v` by constant `c` is valid precisely because the invariant guarantees `v` equals `c` on every executable path reaching that use — dead (non-executable) paths are excluded from the guarantee by construction and are never actually taken at runtime, so ignoring them is sound, not merely convenient. Because the fixed point is the least one satisfying these monotone constraints, SCCP is also maximally precise for this lattice: it detects every constant that is provably constant relative to a 3-level (per-variable, non-relational) abstraction. It is not complete in an absolute sense — see pitfalls below — because real constancy can depend on relationships between variables that this lattice, by design, cannot express.

Consider this snippet (already lightly desugared), with SSA renaming applied at the merge point: ``` B0: a := 10 b := 2 goto B1 B1: c := a b // 10 2 if c > 15 goto B2 else B3 B2: d1 := c - 20 goto B4 B3: d2 := c + 100 goto B4 B4: d := phi(d1 from B2, d2 from B3) e := d / 2 return e ``` Trace of the worklist algorithm (rows show the state after each processing step):

Block `B3` is never added to `CFGWorklist`, so it stays unreachable, `d2` is never computed and correctly remains `⊤` (irrelevant, since dead), and the phi at `B4` never mixes in `d2`. The whole function collapses to: ``` return 0; ``` with blocks `B1`'s branch, `B2`'s subtraction, and all of `B3` deleted by a subsequent dead-code-elimination pass that consults the `ExecutableEdge` and `Value` tables SCCP produced. Notice this result — `d2` never merges into `d` — is more precise than running plain constant propagation (which would compute the phi's meet without excluding unreachable predecessors, forcing `d2 = c+100 = 120`, meeting `0 ∧ 120 = ⊥`, and losing the constant entirely). This is the concrete payoff of doing reachability and propagation together.

Every optimizing compiler runs constant folding and propagation as one of its earliest and most frequently repeated passes: LLVM's `InstCombine` and `SCCP` passes, GCC's tree-level constant propagation (`tree-ccp`), and javac/JIT constant folding in the JVM all implement close variants of the algorithm above. It is essential after inlining, since inlined function calls typically supply concrete arguments that only become "constant" once substituted into the callee's body — modern compilers deliberately interleave inlining, constant propagation, and dead-code elimination in a loop precisely because each unlocks the next. Interprocedural constant propagation extends the idea across function boundaries, letting a compiler specialize a function when all call sites pass the same literal argument. In hardware description languages and template metaprogramming (C++ `constexpr`, Rust `const fn`), aggressive constant folding is the mechanism that lets "compile-time computation" be a first-class language feature rather than a compiler curiosity. JIT compilers (V8, HotSpot's C2) run cheap constant-propagation passes at every tier, since discovering that a loaded object's field is monomorphic and constant can eliminate a virtual dispatch entirely. Finally, constant propagation is a prerequisite step that exposes dead branches for Loop Optimizations and Loop-Invariant Code Motion and is one of the canonical example analyses used to teach the Data-Flow Analysis Framework itself, since its lattice is small enough to reason about by hand yet rich enough to demonstrate every subtlety of fixed-point convergence.

:::quiz[In the worked example, why does Value[d2] remain ⊤ rather than becoming a concrete constant?]

• Because d2's defining block B3 is never proven reachable, so its statement is never visited ✓
• Because c+100 cannot be folded due to overflow rules
• Because phi nodes always ignore the second argument
• Because d2 depends on floating-point arithmetic

Ask the tutor: How would you extend SCCP's lattice to also detect linear relationships between variables, like `y = 2x + 1`?