Constant propagation: data flow and fixed points
Goal and analysis model
Compute facts across a control-flow graph (CFG), including joins and loops. We use a conventional forward, dense, nonrelational constant-propagation analysis over reachable CFG paths, without branch-feasibility pruning. Each variable has a fact UNDEF, a specific constant c, or NAC (not a single known constant). UNDEF means no defining information has yet reached this analysis point, not “the runtime value is safely zero” and not permission to use an uninitialized variable. Unknown input parameters have NAC at entry.
The information order is UNDEF below every constant, and every constant below NAC; different constants are incomparable. Some books reverse the lattice drawing and names of meet/join. Here the combination operator ⊔ has UNDEF⊔v=v, c⊔c=c, c⊔d=NAC for c≠d, and NAC⊔v=NAC. Use these explicit equations rather than guessing from a diagram.
1. Forward equations and transfer
For a block B, IN[B] combines OUT facts from predecessor blocks, component by component. OUT[B]=F_B(IN[B]), where F_B processes assignments in execution order. x=5 sets x to constant 5 regardless of its incoming fact. x=y copies y's current fact. For pure x=y+z, two constant operands yield their sum; an NAC operand gives NAC in this simple analysis; otherwise an UNDEF operand yields UNDEF. Unassigned variables keep their facts. The assignment overwrites x's old fact.
The entry boundary sets externally supplied unknown values to NAC and known initial values to their constants. Other computed facts start at UNDEF and are updated until stable. The facts for a block reflect its whole transfer, not just the last assignment in isolation. Keep unreachable-block treatment separate: if the CFG includes unreachable blocks, either remove them or model reachability explicitly before interpreting UNDEF joins as runtime guarantees.
2. A diamond with one preserved constant
Entry branches on unknown p. The left block assigns x=4; y=2. The right block assigns x=4; y=3. Both flow to J, which computes z=x+1; w=y+1. The branch is feasible in either direction, and no path bypasses these assignments.
Left OUT is x=4,y=2. Right OUT is x=4,y=3. At J, x is 4⊔4=4, while y is 2⊔3=NAC. Therefore J produces z=5 and w=NAC. Replace x by 4 in z=x+1, then fold 4+1 to 5. Do not choose either predecessor's y as the join fact, and do not average the two constants.
A nonrelational limitation: if the left path has x=1,y=2 and the right has x=2,y=1, then x and y individually become NAC at the join. The simple analysis cannot prove x+y=3, even though that relation holds on both paths. Lost correlation is an analysis limitation, not evidence that the program expression can take other values.
3. Loop fixed-point trace
Use entry E: x=0, followed by loop block H: x=x+1; if x<n goto H else Exit. n is an unknown positive integer input, fixed during the loop; x and n use mathematical-integer arithmetic without overflow or traps. H executes at least once, and the self-edge is retained. We analyze H's IN as the join of E.OUT and H.OUT.
Initialize H.OUT[x]=UNDEF. First update: H.IN=0⊔UNDEF=0, so H.OUT=1. Next update: H.IN=0⊔1=NAC, so H.OUT=NAC. Next update: H.IN=0⊔NAC=NAC, so H.OUT remains NAC. The analysis has reached a fixed point. The exit fact for x is NAC; the actual exit value is n, so across positive input values it can be 1,2,3,... . Stopping after the first pass and replacing x by 1 after the loop would be incorrect.
In this flat lattice each variable can ascend from UNDEF to a constant and then to NAC, so finite graphs with monotone transfer functions reach a fixed point. The number of source-level loop iterations need not be bounded for the analysis to terminate. A worklist revisits successors only when output facts change, reducing unnecessary processing.
4. Safe use of facts and limitations
The analysis is conservative: a reported constant must hold on every execution represented by the incoming paths and assumptions. NAC means “not proved constant by this analysis,” not necessarily “changes on every run.” Branch-aware sparse conditional constant propagation can sometimes retain more information by tracking executable edges, but that is a different, more precise analysis than the dense one specified here.
Calls, pointer stores and volatile reads require appropriate side-effect treatment. The scalar examples avoid those issues. Do not propagate values through a possible redefinition, invent a runtime meaning for UNDEF, use a single predecessor at a merge, or stop a loop computation before convergence. Soundness is more important than maximizing the number of replacements.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. With the stated join operator, 4⊔4 equals:
A. UNDEF B. 4 C. 8 D. NAC
Answer: B
A: Both paths provide information.
B: The same constant remains constant.
C: Joining facts is not arithmetic addition.
D: Equal constants do not conflict.
P02. With the stated join operator, 2⊔3 equals:
A. 2 B. 3 C. 2.5 D. NAC
Answer: D
A: Choosing only one path is unsound.
B: The other path has a different value.
C: A join is not an average.
D: Different constants lose a single-constant guarantee.
P03. At the diamond join, x=4 on both paths, y=2 or 3. For z=x+1 and w=y+1:
A. z=5,w=NAC B. z=NAC,w=3 C. z=5,w=4 D. Both UNDEF
Answer: A
A: x is preserved; y is not one constant.
B: x is known, and y is not always 2.
C: w is 3 on one path and 4 on another.
D: Both incoming definitions provide information.
P04. For E:x=0; H:x=x+1 with a self-edge, H.OUT[x] evolves as:
A. UNDEF→1→NAC B. UNDEF→1→1 C. 0→2→4 forever D. NAC→0→1
Answer: A
A: The back-edge value 1 conflicts with entry value 0 at IN.
B: This ignores the back edge at the next update.
C: The abstract lattice merges values rather than simulating forever.
D: Unknown information does not become these constants through this join.
P05. UNDEF in this analysis means:
A. Runtime zero B. Permission to read an uninitialized variable C. No defining information has reached the analysis point yet D. Every possible integer value is definitely observed
Answer: C
A: No zero value is implied.
B: Analysis initialization is not language permission.
C: It is the bottom analysis fact as defined here.
D: NAC represents loss of one constant, and does not claim every value occurs.
P06. Left path x=1,y=2; right path x=2,y=1. A nonrelational constant analysis at the join:
A. Always proves x+y=3 B. Sets both x and y to NAC, losing their correlation C. Sets x=y=1.5 D. Rejects the CFG
Answer: B
A: This simple domain does not retain the relation.
B: Individual joins lose the cross-variable fact.
C: Constants are not averaged.
D: The CFG is valid; the abstraction is imprecise.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in