Sparse Conditional Constant Propagation Across the SSA Graph

Constant propagation sounds like a local rewrite: if an operand is a literal, fold the operation. It is not, because folding one operation can make a branch condition constant, which makes one side of the branch unreachable, which means the phis at the merge lose an input, which can make the merged value constant. The order in which those facts are discovered changes how much work is done, and a dense propagation that treats every program point independently will rediscover the same facts many times.

Sparse conditional constant propagation is the algorithm that resolves this by tracking two things at once: the lattice value of each SSA name, and the reachability of each block and edge. The two are mutually informing. A block is reachable only if some incoming edge is reachable, and an edge is reachable only if its source block is reachable and the branch condition does not rule it out. A phi takes an input only from a reachable edge, so unreachable edges stop constraining values.

The Lattice and the Meet

Each value is assigned one of three states. Undefined means nothing has been established yet, and is the initial state for every name. Constant means the name has a known literal value. Overdefined means the name is not a single known constant, either because several constants reach it or because it is computed from something the analysis cannot represent, and it is the element that absorbs every meet.

The lattice is ordered so that it starts at Undefined, the element carrying no information, moves down through the constant values, which are incomparable to one another, and ends at Overdefined, the element that says only “not a single known constant”. The meet operation therefore moves downward: two different constants meet to Overdefined, a constant meets Undefined to the constant itself, and anything meets Overdefined to Overdefined. The lattice is finite in height — three levels — which bounds the number of times a single name can be updated, and that bound is what makes the worklist algorithm terminate without a separate iteration limit.

The critical rule is that a name only becomes Constant when a single constant reaches it. Two different constants reaching the same name produce Overdefined, not a guess. This is what distinguishes constant propagation from a value-range analysis: no attempt is made to represent the set of possible values, only whether there is exactly one.

Two Worklists, One Fixed Point

The algorithm maintains a worklist of SSA edges (definitions whose value changed and whose users need revisiting) and a worklist of CFG edges (edges newly discovered to be executable). Processing an SSA edge re-evaluates the user. Processing a CFG edge marks its target block reachable and evaluates the phis there.

UNDEF, OVER = object(), object()

def sccp(cfg, defs):
    val = {n: UNDEF for n in defs}
    executable_edge = set()
    flow = [cfg.entry_edge]
    ssa = list(cfg.entry_block.instructions)

    def set_val(name, v):
        new = meet(val[name], v)
        if new != val[name]:
            val[name] = new
            ssa.extend(defs[name].users)

    while flow or ssa:
        if flow:
            edge = flow.pop()
            if edge in executable_edge:
                continue
            executable_edge.add(edge)
            block = edge.target
            if not block.marked:
                block.marked = True
                for phi in block.phis:
                    ssa.append(phi)
            for ins in block.non_phis:
                ssa.append(ins)
        else:
            ins = ssa.pop()
            evaluate(ins)                   # may call set_val, may add flow edges
    return val, executable_edge

The evaluate step is where the two mechanisms couple. For an arithmetic instruction, it meets the lattice values of the operands and, if all are constant, computes the result and calls set_val on the destination. For a conditional branch whose condition is a known constant, it pushes only the edge that the constant selects. For a phi, it meets only the values from executable predecessor edges, ignoring inputs from edges that were never reached.

Ignoring those inputs is the whole point. A dense analysis would compute the meet over all predecessors and conclude Overdefined whenever any path carried a different value, even if that path is dead. SCCP concludes Constant when the only executable path carries one value, and that conclusion can then make the branch that excluded the other path redundant.

Why Sparse Beats Dense Here

A dense formulation would maintain a lattice value at every program point and iterate to a fixed point over all points. Its cost per iteration is proportional to the number of program points, and the number of iterations can grow with the lattice height and with how information flows around loops. On a function with many blocks, most of that work touches points whose values never change.

The sparse formulation does work proportional to the number of SSA edges whose source value actually changed, plus the number of CFG edges that become executable. Each name changes at most twice — from Undefined to a constant, and from a constant to Overdefined — so the total number of SSA edge processings is bounded by twice the number of def-use edges. Each CFG edge is processed at most once. The bound is independent of the nesting depth, which is the property that matters on real code with deep loops.

The price is a dependency on SSA form. Without def-use chains, there is no sparse edge set to walk, and the algorithm degenerates into the dense version. This is the concrete payoff of the construction described in Minimal SSA Construction from Dominance Frontiers: the analysis cost becomes proportional to the size of the use lists rather than to the size of the program text times the number of iterations.

Interaction with Loops

A loop header phi is the case where the sparse algorithm earns its keep and also where it needs care. Consider a counter initialised to zero and incremented by one each iteration, with a comparison that exits at ten. On the first pass, the header phi has one executable input (the entry value zero), so it is Constant zero. The increment produces one, which flows back along the back edge. The phi now has two inputs: zero and one, which meet to Overdefined, and the analysis can no longer prove the loop bounded.

This is correct: without induction-variable analysis, a phi that changes each iteration is not constant. The algorithm does not attempt to reason about the number of iterations, and it should not, because that reasoning belongs to a different analysis with a different lattice. The consequence is that SCCP alone cannot eliminate a loop whose trip count is statically known; it can only propagate constants that are stable across iterations.

The reverse case is more interesting. A loop whose body is never entered because the entry condition is constant false: the entry edge to the body is not executable, the body is never marked reachable, and the back edge never becomes executable. The loop’s phis keep only their entry inputs, and if those are constant, the values after the loop are constant too. A dense analysis would have to iterate the body to a fixed point before discovering that the loop is dead, and it would discover the same constants after doing the work.

Nested loops compound the effect. A dense analysis on a loop at depth d may need on the order of d passes over the body; SCCP needs one pass over the body’s edges if the body is reachable, and none if it is not.

What the Result Justifies

The output is a mapping from names to lattice values plus a set of executable edges. Several transformations read it directly.

Branches whose condition is a known constant are replaced by unconditional branches, and the dead successor edge is removed. Blocks that are no longer reachable from the entry are deleted, along with their phis. Instructions whose result is a known constant are replaced by the constant, which lets the front end’s literal handling disappear and lets later folding see the value directly. Instructions that compute a value no longer used by anything reachable are removed, which is dead code elimination driven by the same reachability information.

The ordering of those rewrites matters. Removing a dead branch can make a phi’s remaining input constant, which enables more folding, which can make another branch constant. A single SCCP run computes the fixed point for all of these at once, but the rewrites that consume the result must either be applied in a way that preserves the analysis or be followed by another SCCP run. Most compilers run the pair — analyse, simplify, analyse again — a small number of times and stop when the graph stops changing.

A second consumer is interprocedural propagation. If a function is only ever called with constant arguments and the call is inlined, the constants are substituted into the inlined body as ordinary SSA values and the analysis runs again, which is how a chain of trivial wrapper functions collapses to nothing. That requires the call graph and the inlining decision, which are outside this analysis; the boundary is that SCCP reasons about one function’s SSA graph and treats a call that has not been inlined as an opaque operation whose result is Overdefined unless a summary says otherwise.

Limits

The lattice has no notion of a set of constants, so a value that is one of two literals is Overdefined and nothing further is learned. Adding a set-valued lattice would let more branches be resolved, at the cost of a much larger state space and a much weaker termination bound.

The analysis is flow-insensitive about memory. A load from a location that was stored earlier is Overdefined unless a separate analysis proves the store is the only one, and that analysis needs alias information. Constants that flow through memory rather than through SSA names are therefore invisible, which is why the same source program compiled with values kept in locals optimises better than one that keeps them in an escaped structure. Recovering some of that precision requires the memory versioning described in Memory SSA and Alias-Partitioned Heaps, which turns a store-to-load pair into a def-use edge the sparse walk can follow.

Finally, the result is only as good as the reachability it discovers. An edge that is executable because the analysis cannot prove the branch condition constant will keep the other side alive, and every value that flows along it will be Overdefined. The practical consequence is that the order in which branches are simplified determines how much of the graph becomes provably dead, which is why the analyse-and-simplify loop is not a formality but the mechanism by which the analysis reaches its best answer.