Constant Propagation over a Flat Lattice

The transformation is easy to state: if a variable provably holds the same constant at a use, replace the use with the constant. The analysis is where the difficulty lives, because “provably” needs a domain that can represent three distinct situations — the variable holds this specific value, the variable holds different values on different paths, and nothing is known yet — and because loops make the propagation circular.

Getting the domain wrong produces one of two failures. A domain without a distinct “unknown” element propagates the wrong constant from an uninitialised point. A domain without a distinct “not constant” element either fails to converge or merges distinct constants into an arbitrary one of them. The flat lattice solves both by construction, and the sparse conditional solver built on top of it is the standard production algorithm.

The flat lattice

For each variable the domain is {⊥} ∪ C ∪ {⊤}, where C is the set of constants of the type, ⊥ means “no information yet, this point has not been reached”, and ⊤ means “definitely not a single constant”. The order is: ⊥ is below every constant, and every constant is below ⊤. Constants are mutually incomparable.

Meet — the merge operator, since this is a forward may-analysis of values — is:

• ⊥ ∧ x = x, because bottom contributes nothing.
• c ∧ c = c, because the same constant on both paths stays constant.
• c ∧ d = ⊤ for c ≠ d, because two different constants on two paths mean the value is not constant.
• ⊤ ∧ x = ⊤, because once the value is not constant no later information recovers it.

The height of the lattice is two: a variable can go from ⊥ to a constant, and from a constant to ⊤. That bound is what makes the fixpoint cheap. A variable’s state changes at most twice, so the total number of state changes across a procedure is at most twice the number of variables, regardless of how the control flow loops.

The critical detail is that ⊤ is absorbing and distinct from ⊥. An implementation that uses a single “unknown” value for both cannot distinguish “this point was never reached, so there is no information” from “this point was reached, and the value is not a single constant”. Collapsing them makes one of the two situations unrepresentable: the analysis either keeps a constant the program cannot justify or discards one it could have kept.

typedef enum { BOT, CONST, TOP } kind;
typedef struct { kind k; int64_t v; } lat;

static lat meet(lat a, lat b) {
    if (a.k == BOT) return b;
    if (b.k == BOT) return a;
    if (a.k == TOP || b.k == TOP) return (lat){TOP, 0};
    return (a.v == b.v) ? a : (lat){TOP, 0};   /* different constants collapse to TOP */
}

Transfer functions that must not guess

The transfer function for an assignment x = e evaluates e in the current state and writes the result to x. Evaluation is where the lattice discipline pays off: an operation on constants produces a constant, an operation on ⊤ produces ⊤, and an operation on ⊥ produces ⊥. Division by a constant zero produces ⊤ rather than a trap, because the analysis must not introduce a value the program does not have — the trap either exists in the program or it does not, and folding a branch on the assumption that it does is a separate decision.

Two operations deserve explicit handling because they are easy to get wrong.

Conditional branches. A branch on a constant condition has exactly one executable successor. If the analysis marks both successors reachable, it will merge states at joins that no execution reaches and lose constants it could have kept. Marking only the taken successor is what makes the analysis conditional, and it is the difference between folding a chain of if statements on a configuration flag and failing to.

Phi nodes. A phi merges its operands, so the meet of the operands’ values, but only over the predecessor edges that are actually executable. A phi with two operands where one arrives on an unreachable edge evaluates to the other operand’s value, not to ⊤. This single rule accounts for most of the practical power of the algorithm on code with early exits and error paths.

Calls. A call to an unknown function clobbers every variable whose address it could reach. Variables whose address never escapes are unaffected, which is why the analysis is usually run after escape analysis has identified them, as described in Escape Analysis and Scalar Replacement of Aggregates.

Sparse conditional constant propagation

The dense formulation stores a lattice value at every program point for every variable, which is O(blocks × variables) and does far more work than necessary. Wegman and Zadeck’s sparse conditional constant propagation (SCCP) stores one value per SSA name and propagates along def-use edges, visiting only the code that the current knowledge says can execute.

The algorithm interleaves two worklists:

A flow worklist of CFG edges known to be executable. Initially only the entry edge. Popping an edge means the target block becomes reachable and its phis must be re-evaluated.

An SSA worklist of instructions whose operand values changed. Popping an instruction means re-evaluate it and, if its result changed, push its uses.

The interleaving is the point. A branch whose condition becomes constant causes only one outgoing edge to be pushed, so the other successor never becomes reachable and its instructions are never visited. That is how the analysis proves code dead without a separate reachability pass, and it is why the result is strictly better than running constant propagation and dead-code elimination in sequence.

/* Sketch of the interleaving. Values live per SSA name, not per program point. */
while (flow_work || ssa_work) {
    if (flow_work) {
        edge e = pop(flow_work);
        if (mark_executable(e))                     /* first visit only */
            for (phi p in e->target->phis) push(ssa_work, p);
    } else {
        inst *i = pop(ssa_work);
        lat nv = evaluate(i);
        if (!equal(nv, value_of(i->dst))) {
            value_of(i->dst) = nv;
            for (use *u = uses_of(i->dst); u != NULL; u = u->next) push(ssa_work, u->inst);
            if (is_branch(i) && nv.k == CONST)
                push(flow_work, nv.v ? i->true_edge : i->false_edge);
        }
    }
}

Two implementation constraints follow from the structure. First, marking an edge executable must be idempotent, because a block with several predecessors can have the same edge offered more than once as different constants flow in. Second, evaluating a phi requires knowing which incoming edges are executable at that moment, so phi evaluation cannot be done when the phi is first created — it is done each time a predecessor edge becomes executable, and the meet accumulates.

The cost is proportional to the number of SSA edges plus the number of CFG edges, each traversed a bounded number of times because each name’s value changes at most twice. That is linear in program size up to the constant factor, which is why SCCP is affordable as an early pass on every function.

What it cannot fold

SCCP is a forward value analysis and inherits the limits of that model. It has no notion of a value being constant on a condition, only of a variable being constant. A branch guarded by x == 3 in which x is not constant leaves the body unfolded, even though within the body x is provably 3. Capturing that requires either a path-sensitive analysis or a value-range domain, and the usual production answer is to run a separate range analysis that carries the guard condition into the dominated block.

It also cannot see through memory. A store followed by a load from the same address is not folded unless the load can be promoted to an SSA name, which requires knowing the address is not modified by anything in between. Store-to-load forwarding is a separate pass, and its precision is bounded by the alias analysis.

Finally, the analysis is intraprocedural unless a compiler invests in interprocedural summaries. A function that returns a constant for all inputs is not folded at its call sites by SCCP alone; the caller sees an opaque call. Interprocedural constant propagation, and the inlining that often makes it unnecessary, is discussed in Inlining Decisions and the Cost Model Behind Them.

Interaction with the rest of the optimizer

The output of SCCP is three things at once: folded operands, dead blocks, and dead SSA names. All three are consumed by cleanup passes that remove unreachable blocks, delete instructions with no uses, and simplify trivial phis. Running SCCP before those cleanups and again after is common, because the first run exposes dead code whose removal makes more constants visible — a fixed-point over passes rather than within one analysis.

The lattice discipline also constrains what a compiler is allowed to assume about undefined behaviour. Folding a branch on a value that the language says is uninitialised is a transformation that changes program meaning for programs that read it; compilers handle this by treating such reads as producing ⊤ and letting the language’s rules decide whether the program had a defined meaning at all. Getting this wrong produces the notorious class of optimizations that delete code containing an out-of-bounds access on the grounds that the access cannot happen, which is defensible only under a reading of the language standard that the compiler must be able to justify.

The sparse machinery itself — one value per name, def-use edges as the propagation channel — is reusable for any forward property whose domain is small. That generality is the reason SSA is worth its construction cost, and the construction is examined in SSA Construction and the Cost of Phi Placement.