CD Notes
Complete guide to constant propagation optimization covering forward analysis, conditional constant propagation, lattice framework, and practical implementation with dataflow analysis.
What is Constant Propagation?
Constant propagation is a compiler optimization that tracks variables known to hold constant values and substitutes those constants wherever the variables are used. This enables subsequent constant folding and dead code elimination, creating a cascade of simplifications.
Basic Mechanism
| Before constant propagation | After constant propagation: |
| y = x + 3 y = 5 + 3 | (fold to 8) |
| z = y * x z = 8 * 5 | (fold to 40) |
| if (z > 30) if (40 > 30) | (fold to true) |
| w = z - x w = 40 - 5 | (fold to 35) |
Dataflow Analysis for Constant Propagation
Lattice for each variable
⊤ (undefined / not yet seen)
/|\
/ | \
c1 c2 c3 ... (specific constant values)
\ | /
\|/
⊥ (not a constant / multiple possible values)
Meet operation (∧):
⊤ ∧ c = c (first definition wins)
c ∧ c = c (same constant from both paths)
c₁ ∧ c₂ = ⊥ (different constants → not constant)
⊥ ∧ x = ⊥ (once non-constant, stays non-constant)
Transfer function for x = y op z:
If val(y) and val(z) are both constants c₁, c₂:
val(x) = c₁ op c₂ (fold)
Else if either is ⊥:
val(x) = ⊥
Else
val(x) = ⊤ (not yet determined)
Example: Global Constant Propagation
| B2 | B3 | |
|---|---|---|
| z=x+y | z=x*2 | |
| a=10 | a=20 |
Conditional Constant Propagation (CCP)
Standard constant propagation is pessimistic at joins. CCP considers that some paths may be unreachable:
| B2 | B3 | |
|---|---|---|
| y=1 | y=2 |
Sparse Conditional Constant Propagation (SCCP)
| 1. Initialize | all variables = ⊤, all edges = not executable |
| 2. Worklist contains | entry edges + all SSA definitions |
| - For edge | mark executable, evaluate φ-functions at target |
| - For instruction | evaluate using current lattice values |
| If result changes | add uses to worklist |
| - For branch on constant | mark only taken edge executable |
| Key insight | Only evaluate φ-function inputs from executable edges! |
Copy Propagation
Closely related to constant propagation — propagates copies of variables:
| Before copy propagation | After copy propagation: |
| a = 5 constant prop | ... |
| b = a copy prop | b = 5 |
| c = b + 1 both | c = 5 + 1 → c = 6 |
Implementation Approaches
| Approach 1 | Iterative dataflow (general CFG) |
| Convergence | guaranteed because lattice has finite height |
| (⊤ | constant → ⊥, never goes back up) |
| Approach 2 | SSA-based (SCCP) |
| Worklist | only re-evaluate when inputs change |
| Much more efficient | O(n) for n instructions |
| Approach 3 | Interprocedural |
| f(5) | inside f, parameter has value 5 |
Interaction with Optimization Pipeline
Constant Propagation feeds
→ Constant Folding (x=5; y=x+3 → y=8)
→ Dead Code Elimination (if(true) removes else)
→ Branch Simplification (constant conditions)
→ Loop Optimization (constant trip counts)
Constant Propagation is fed by
← Inlining (brings constants to call sites)
← Specialization (generates constant-argument versions)
← Partial Evaluation (reduces dynamic to static)
Limitations
Interview Questions
- Q: What is the difference between constant propagation and constant folding?
A: Constant propagation substitutes variable uses with their known constant values (x=5; y=x → y=5). Constant folding evaluates expressions with constant operands at compile time (y=5+3 → y=8). They are complementary: propagation creates opportunities for folding, and folding creates new constants that can be propagated.
- Q: Why does constant propagation use a lattice?
A: The lattice provides a formal framework ensuring convergence. Values only move downward (⊤→constant→⊥), guaranteeing termination. The meet operation at control flow joins is well-defined and monotone, ensuring the analysis computes a safe approximation.
- Q: What is the advantage of SCCP over simple constant propagation?
A: SCCP recognizes that some branches are never taken (when the condition is a known constant). It avoids "polluting" constants at join points with values from unreachable paths. This can propagate significantly more constants, especially after initial constants determine branch directions.
- Q: Can constant propagation be done interprocedurally?
A: Yes. If all call sites pass the same constant for a parameter, that parameter can be treated as constant inside the function. This is interprocedural constant propagation. It enables function specialization and significant optimization of library-like code called with known arguments.
- Q: How does SSA form help constant propagation?
A: SSA's single-definition property means each variable has exactly one defining instruction. Finding whether a variable is constant requires checking only one place. Phi-functions explicitly show where values from different paths merge, making the meet operation straightforward. This reduces complexity from iterative to near-linear.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Constant Propagation in Compiler Optimization.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, code, optimization, constant, propagation
Related Compiler Design Topics