12.1 Constant Folding and Constant Propagation

Optimization changes how a program is implemented while preserving its observable behavior. The simplest examples replace work whose result is already known. Constant folding evaluates an operation at compile time, while constant propagation replaces a variable or SSA value with a constant proved to reach that use.

These transformations reinforce each other. Propagation exposes new constant operands; folding reduces those operations; the new result may make a branch constant and expose unreachable code.

%x = const 4
%y = mul %x, 2       ; propagation gives mul 4, 2
%c = icmp.eq %y, 8   ; folding gives true
br %c, yes, no       ; becomes br yes

The optimized result is not merely shorter. It has one multiplication, one comparison, and one conditional branch removed. A later dead-code pass can delete the now-unreachable no block.

Facts flow through the CFG

Within one basic block, an environment such as {x → 4, y → 8} is enough. Across a control-flow graph, a value may arrive from several predecessors. A constant-propagation analysis therefore uses a small lattice for every SSA value:

• UNDEF means no executable path has supplied a value yet;

• CONST(c) means every observed executable path supplies the same constant c;

• NAC or overdefined means the value is not one provable constant.

At a merge, CONST(4) joined with CONST(4) remains CONST(4), but CONST(4) joined with CONST(9) becomes NAC. UNDEF does not mean zero; it means the analysis has not learned a value from an executable path.

Sparse conditional constant propagation

Sparse conditional constant propagation (SCCP) tracks both value facts and executable CFG edges. If a branch condition becomes constant, SCCP marks only the selected edge executable. Facts from an impossible predecessor no longer pollute a phi node.

Consider:

entry:
  %flag = const true
  br %flag, left, right
left:
  br join(5)
right:
  br join(runtime_value)
join(%x):
  %y = add %x, 3

A path-insensitive analysis might merge 5 with runtime_value and conclude %x = NAC. SCCP first proves the right edge unreachable, so %x = 5 and %y = 8. This interaction between reachability and values is why SCCP is stronger than a simple textual replacement pass.

Folding must preserve source semantics

The compiler may evaluate an operation early only if it reproduces the behavior required at runtime. Important hazards include:

• checked integer overflow versus wrapping arithmetic;

• integer division by zero and invalid shift counts;

• floating-point NaN, infinities, signed zero, and rounding mode;

• operations that trap, throw, allocate, or change observable state;

• target-dependent sizes such as pointer width.

For a checked six-bit signed integer, 31 + 1 traps; folding it to -32 would silently use wrapping semantics. For IEEE floating point, 0.0 / 0.0 may fold to NaN, but replacing x * 0.0 with 0.0 is generally unsafe because x may be NaN or negative zero. Fast-math flags deliberately relax some rules, but they are part of the optimization contract and must not be assumed globally.

Implementing the pass

A practical pass maintains a worklist of values or instructions whose facts changed. When an operand becomes constant, revisit its users. Recompute an instruction only when an input fact changes, and stop when no lattice value or executable edge changes. Monotonic movement from UNDEF through CONST to NAC guarantees termination for a finite function.

After rewriting, run an IR verifier and then dead-code elimination. Constant propagation often leaves unused definitions and untaken blocks behind; separating analysis, rewriting, and cleanup keeps each pass easier to reason about and test.