Data Flowtypical

Constant Propagation

`x = 5; y = x + 3` becomes `y = 8`. A forward analysis over a three-level lattice — unknown, one specific constant, not constant — and its SSA-based descendant SCCP does something the dense version cannot: it kills unreachable branches while it propagates.

The question

How does a compiler know a variable holds a specific value, and how far can it carry that knowledge?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The CFG annotated with, at every program point, a map from each variable to a lattice element: unknown (nothing seen yet), a specific constant, or not constant (two different values reached here). It exists to answer "does this variable have one known value at this point?", which is the precondition for replacing a read with a literal and for folding the operation that reads it.

What this phase may assume or do

Substituting a literal for a variable is legal only if that variable has that value on every path reaching the use — which is precisely the lattice element "constant". The lattice's meet enforces it: two different constants meet to "not constant", never to one of them. Folding the resulting operation is a separate condition and needs [[constant-folding]]'s: the operation must not trap on those operands, and the compile-time evaluation must produce exactly the value the target would have produced at run time, which is why cross-compiling a floating-point expression is delicate. The analysis is entitled to assume it sees every assignment to the variable, which fails the moment the variable's address escapes.

Key points

The lattice has three levels — unknown, one specific constant, not constant — and the meet of two different constants is not-constant.
Height three means fast convergence: a variable can only be lowered twice.
Propagation makes operands into literals; folding evaluates operations whose operands already are. They are different passes and are run together to a fixed point.
Outside SSA the substitution needs reaching definitions to prove no other assignment interferes; in SSA it is guaranteed by construction.
The dense analysis is path-insensitive and loses correlations between variables — this is the canonical non-distributive framework example.
SCCP tracks value lattice and edge reachability together, starting optimistically, and finds constants that separate passes cannot.
Constants are valuable mostly for what they unlock: dead branches, unrolling, devirtualization, bounds-check removal.

The lattice is the analysis

Every previous analysis in this module had sets for facts. This one does not, and it is the instance that shows why the framework is stated in terms of lattices rather than bit vectors. A fact here is a map from variable to one of three things: ⊤ unknown, meaning no path has told us anything yet; a specific constant; or ⊥ not-constant, meaning two paths disagreed or the value came from somewhere unanalysable.

The meet is what makes it work. Unknown meets anything and yields that thing — an unvisited path constrains nothing. A constant meets the *same* constant and yields it. A constant meets a *different* constant and yields not-constant, because no single literal is correct on both paths. Not-constant meets anything and stays not-constant.

The lattice has height three, which is why the analysis converges quickly: any variable can be lowered at most twice. That is the same finite-height argument as [[fixed-point-iteration]], applied to a lattice that is not a set at all.

The meet, in full

meet	unknown (⊤)	constant c	constant d ≠ c	not constant (⊥)
unknown (⊤)	unknown	c	d	not constant
constant c	c	c	not constant	not constant
not constant (⊥)	not constant	not constant	not constant	not constant

The transformation, and the one it is not

specWhether an expression *must* be evaluated at compile time is a language question, not an optimizer question. A C++ constexpr in a constant expression is required by the standard to be evaluated at compile time; an ordinary expression that happens to be constant may be, at the implementation's discretion. Those are different obligations and only the first is guaranteed — see [[compile-time-evaluation]].

With the lattice computed, propagation is a substitution: a use of a variable whose element is a constant is replaced with that literal. Then [[constant-folding]] evaluates any operation all of whose operands are now literals, and the result is itself a constant for the next round — which is why the two are usually run together to a fixed point rather than once each.

The two are genuinely different and the distinction matters when reading a pass list. Folding evaluates an operation whose operands are *already* literals; it needs no analysis at all and can be done by the frontend. Propagation is what makes operands into literals, and outside SSA it needs reaching definitions to establish that no other assignment interferes.

Our optimizer's legality condition for propagation says exactly that, and names the SSA shortcut: *the value has exactly one definition and that definition is a literal. In SSA this is guaranteed by construction, which is most of why SSA exists.* The illegal case it names is the analysis this lesson describes doing its job — *the variable is reassigned on another path and the two definitions reach the same use.*

Propagate, then fold

Before

x = 5
y = x + 3
print y

After

y = 8
print 8

Legal only when

The variable has the value 5 on every path reaching the use — the lattice element is the constant 5, not merely "5 on some path". The operation 5 + 3 must not trap and must evaluate at compile time to exactly what the target would compute at run time, which for integer addition within range is unproblematic and for floating point requires the host and target to agree on format and rounding.

Illegal when

Another assignment to x reaches the same use — the classic case is an assignment inside a loop whose back edge reaches the read, where the lattice element is correctly not-constant. Also illegal when the operation would trap: x = 0; y = 10 / x must not be folded into a compile-time division, because the program's defined behavior is a run-time fault and the compiler is not entitled to move it to compile time or to assume it away.

Where the dense analysis loses precision

The classical analysis is path-insensitive, and constant propagation is the standard example of what that costs. Consider a branch that assigns x = 1; y = 2 on one side and x = 2; y = 1 on the other, followed by a use of x + y. On both paths the sum is 3. The analysis reports x not-constant and y not-constant, and concludes nothing about the sum, because merging discarded the correlation between them.

This is not a bug in the implementation; it is the gap between the iterative solution and the meet-over-all-paths answer that appears for non-distributive frameworks. Constant propagation is monotone but not distributive, which is exactly the condition under which the two answers differ, and it is the canonical example in the literature for that reason.

The other precision loss is more mundane and more common: a branch whose condition is a known constant. A dense analysis propagates facts along both edges of the branch regardless, so an assignment in a block that can never execute still contributes to the merge and can turn a constant into not-constant. Fixing that requires the analysis to track reachability, which is what the SSA version does.

SCCP: constants and reachability at once

typicalSCCP or a close relative ships in LLVM (-passes=sccp and the interprocedural ipsccp) and in GCC (-ftree-ccp). What differs between implementations is how far the constant range machinery goes beyond single values — LLVM's ipsccp propagates across function boundaries for internal functions, which our description does not cover and which changes what is discoverable considerably.

Sparse conditional constant propagation, from Wegman and Zadeck, is the SSA formulation and it is strictly stronger than the dense one — not merely faster. It maintains two worklists: one of SSA values whose lattice element changed, and one of CFG edges newly found to be reachable. It starts by assuming *every* block unreachable except the entry, and only marks an edge reachable when it proves the branch can take it.

The consequence is the interesting part. A phi only meets the operands arriving on edges currently known to be reachable, so an assignment in a block SCCP has not proved reachable contributes nothing. When a branch condition turns out to be a known constant, only one of its two edges is ever marked reachable, and the other block's assignments never enter any merge. So the analysis discovers constants that let it discover unreachable code, which lets it discover more constants.

That is why it is strictly stronger than running constant propagation and unreachable-block elimination separately to a fixed point: the interleaving finds things neither ordering of the two separate passes will. It is also the clearest single demonstration in the domain of [[why-ssa-helps]]'s claim, because the reachability tracking is only affordable because the def-use edges make the propagation sparse.

It has limits worth stating. It is still path-insensitive in the correlated-branches sense above — it will not discover that x + y is 3 in the earlier example. And it works on values, so it says nothing about memory unless a memory-SSA layer is present.

SCCP, in outline

1every SSA value  := unknown
2every CFG edge   := unreachable
3mark the entry edge reachable
4 
5while either worklist is non-empty:
6  take an item and re-evaluate what depends on it
7 
8  a phi meets ONLY the operands on reachable incoming edges
9  an instruction evaluates from its operands' lattice values
10  a branch on a KNOWN constant marks exactly one outgoing edge
11  a branch on a non-constant marks BOTH outgoing edges
12 
13at the end:
14  values still 'unknown' are in unreachable code -> delete
15  values that are constants          -> substitute and fold
16  edges never marked reachable       -> delete the blocks

The optimism is the whole trick: start by assuming everything is unreachable and every value unknown, then only ever lower. A pessimistic analysis that starts with everything reachable can never recover the branch it could have killed.

What it enables downstream

Constants are unusually valuable to an optimizer because they unlock other transformations rather than merely saving an instruction. A known branch condition removes a block and everything in it. A known loop bound enables unrolling and sometimes full evaluation. A known function pointer or type tag enables [[devirtualization]]. A known array index can eliminate a bounds check — [[bounds-check-elimination]].

This is why constant propagation runs early and repeatedly in a pass pipeline, and why [[phase-ordering]] discussions always feature it: nearly every other pass gets better inputs when it runs after propagation, and propagation gets better inputs after inlining. There is no ordering that is optimal for every program, which is the whole point of that lesson.

How it works

The steps, in the order the compiler takes them.

Assign every variable the lattice element "unknown" except the function's inputs, which are "not constant".
Iterate forward: at each instruction, compute the destination's element from the operands' elements; at each merge, apply the meet.
Meet rules: unknown with anything gives that thing; equal constants give the constant; unequal constants give not-constant; not-constant absorbs.
Stop at the fixed point, then substitute literals for every use whose variable is a constant.
Fold operations whose operands are now all literals, subject to the trapping and target-agreement conditions, and repeat until no further change.
For SCCP: additionally track which CFG edges are reachable, start with all unreachable, meet a phi only over reachable incoming edges, and mark a single outgoing edge for a branch on a known constant.
Delete blocks whose incoming edges were never marked reachable.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A constant is substituted where a second assignment also reached the use. The program computes with a value from the wrong path and produces a wrong answer with no diagnostic — the exact failure the reaching-definitions precondition exists to prevent.
A trapping operation is folded at compile time. 10 / 0 becomes a compile-time error or, worse, a silently chosen value, and a program whose defined behavior was a run-time fault now does something else entirely.
A floating-point expression is folded on a host whose rounding or precision differs from the target. The cross-compiled binary produces different results from a natively compiled one, and the discrepancy is in the last bits, which makes it look like a hardware problem.
The analysis is run over a variable whose address escaped. Assignments through the pointer are invisible, the variable is reported constant, and the substituted literal is stale.
SCCP is implemented pessimistically — starting with everything reachable — and quietly loses most of its power. Nothing is wrong, and the pass looks like it is working because it still folds the easy cases.

When it helps

After inlining, where a caller's literal argument becomes a constant inside the callee and can cascade through it. This is much of why inlining helps beyond removing the call.
Configuration-style code — feature flags, debug switches, generic code specialised to a type tag — where a constant kills whole branches.
Enabling other passes: known loop bounds for unrolling, known indices for bounds-check elimination, known targets for devirtualization.
Template and generic instantiation, where [[monomorphization]] produces code full of values that are constant in that instantiation and variable in general.

When it hurts

When the constants are only known at run time, which is most of the interesting cases in a static compiler. This is exactly the gap a JIT exploits — see [[why-runtime-information-helps]].
When propagation feeds aggressive specialisation and the code size grows without a matching gain, which shows up as instruction-cache pressure rather than as anything visible in the IR.
Debug builds, where folding a variable away means it no longer exists to inspect — a real reason -O0 exists and a real cost of running this pass.

What it costs

Every one of these is paid by something.

Propagation buys folded arithmetic and dead branches; it pays debuggability, because a variable folded to a literal has no storage and a debugger can only report "optimized out".
Running it repeatedly with folding to a fixed point buys the cascade — each folded value enabling the next; it pays compile time on every function, including the many where nothing is constant.
SCCP's optimistic start buys strictly more constants and dead code than any sequence of separate passes; it pays a more delicate implementation, because a pessimistic bug in it looks exactly like the pass working.
Interprocedural propagation buys constants across call boundaries; it pays whole-program visibility, which conflicts with separate compilation and forces the work into [[link-time-optimization]].

What else you could do

What a different compiler or language does instead, and when that is better.

Conditional constant propagation without sparsity — the dense version with reachability — which gets most of the precision at higher analysis cost and without needing SSA.
Range or interval analysis, which tracks a set of possible values rather than a single one. It proves more (bounds checks, in particular) and needs widening to terminate, which puts it outside the finite-height framework.
Partial evaluation and specialisation, which take the idea further by generating a version of a function specialised to known arguments. Much more powerful, and it costs code size and a policy decision about when it is worth it — see [[partial-evaluation]].
Defer to run time: a JIT can observe the value a variable actually takes and specialise on it behind a guard, which finds constants a static compiler provably cannot. The cost is the guard, the deoptimization path and the warmup — see [[speculative-optimization]].

See it for yourself

The flag, dump or tool that shows you this directly.

opt -passes=sccp -S t.ll runs the sparse conditional version alone, and -passes=ipsccp runs the interprocedural one; diffing them on a file with small internal functions is instructive.
gcc -fdump-tree-ccp writes the conditional constant propagation dump, showing the lattice values it settled on per SSA name.
clang -S -emit-llvm -O1 on a function with a const parameter and a branch on it: the branch usually disappears entirely, and the dump shows which block went with it.
Our pass-manager interactive toggles constant propagation and constant folding independently over the real AtlasLang optimizer, which makes the difference between the two passes visible rather than theoretical.

Plausible wrong readings

Stated the way a confident engineer states them.

"Constant propagation and constant folding are the same pass." Folding evaluates operations on literals; propagation makes operands into literals. Running only one of them leaves most of the work undone.
"If the value is a constant, the compiler will fold it." Only if the compiler can prove it is that constant on every path, the operation cannot trap, and folding it agrees with the target. Any of the three can fail — and stating it as a certainty is exactly the kind of claim this domain requires a caveat for.
"SCCP is just a faster constant propagation." It is also strictly more precise, because it tracks reachability at the same time and therefore ignores assignments in blocks it has not proved reachable.
"A variable assigned two different constants is not constant, so nothing can be done." Nothing can be done *by this analysis*. Path duplication, specialisation or a run-time guard can each recover it, at a cost.

Misconceptions

The claim, and what is actually true.

Anything the programmer can see is constant will be folded.

The compiler folds what it can prove on every path, without trapping, in agreement with the target. Escaping addresses, calls and floating-point subtleties each block it routinely.

The three-level lattice is a simplification of tracking actual values.

It is a deliberate choice of finite height. Tracking sets or ranges of values has infinite height and needs widening, which is a different and much more delicate analysis.

SCCP replaces dead code elimination.

It finds unreachable blocks as a side effect and removes them. Dead *code* — instructions whose results nobody uses — is a different question, answered by use counts.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Constant propagation figures out which variables hold a known fixed value at each point, then replaces reads of them with the literal. Each variable is either unknown, one specific constant, or not constant; when two paths meet and disagree, the answer becomes not constant. Folding then evaluates the operations whose operands are now all literals.

practical

When a compiler does not fold something you expected it to, check three things in order. Is there another assignment on some path — including a loop back edge? Could the value have escaped through a pointer or a call? And could the operation trap or, for floating point, differ between host and target? Those cover almost every "why did it not constant-fold this" question, and the IR dump answers all three faster than reasoning does.

internals

Constant propagation is the standard example of a monotone but non-distributive data-flow framework, and that is not a technicality — it is why the iterative answer is strictly weaker than the meet-over-all-paths answer. Merging two branches that set x = 1, y = 2 and x = 2, y = 1 loses the correlation, so x + y is not discovered to be 3 even though it is 3 on every path. Recovering it means either enumerating paths, which is exponential, or duplicating the code so that the framework sees two separate paths — which is what tail duplication and trace scheduling do, and why they help constant propagation as a side effect. SCCP attacks a different axis: rather than improving precision within a merge, it removes merges from consideration entirely by proving edges unreachable. The two are complementary, and neither subsumes the other, which is a good illustration of why a pass pipeline is a sequence of partial answers rather than one optimal analysis.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalSCCP or a close relative ships in LLVM (sccp, ipsccp) and GCC (-ftree-ccp), so this is the mainstream implementation rather than a research technique. How far each goes — single constants, ranges, across function boundaries — differs, and changes substantially what a given compiler will discover on the same source.

specA language may *require* compile-time evaluation in some contexts — C++ constexpr in a constant expression, or a const generic parameter in Rust — and that obligation is independent of the optimizer. Ordinary expressions that happen to be constant are folded at the implementation's discretion, and a program must not depend on it.

targetFolding must produce exactly what the target would compute. For integers within range that is straightforward; for floating point it requires the host to agree with the target on format, rounding mode and the handling of NaN and signed zero, which is why cross-compilers implement software floating point for constant folding rather than using the host FPU.

implementationAtlasLang implements constant propagation and constant folding as separate toggleable passes over SSA in src/compilers/sim/optimize.ts, and does not implement SCCP — branch simplification and unreachable-block elimination are separate passes, which is precisely the arrangement SCCP is stronger than.

If you were asked this in an interview

Describe the lattice constant propagation uses, and say why two different constants meet to "not constant".
What is the difference between constant propagation and constant folding?
What does SCCP do that running constant propagation and unreachable-block elimination separately does not?
Give a program where the analysis reports "not constant" even though the expression has the same value on every path.

Connections

DSAdirected-graph hash-table dfs

Performancejit-and-warmup

Domains that do not exist yet

Programming Languages & Runtime Internals — Values that are only constant at run time, and specialising on them behind a guard
A static compiler can only propagate what it can prove for every execution. A running system knows what the value actually was, and can specialise on it if it is willing to guard and deoptimize — which is a runtime mechanism owned there, even though the compiler-side guard is ours.