In a control flow graph, one branch of an if-statement assigns x = 5 and the other assigns x = 7. At the merge point after both branches, what does constant propagation's lattice assign to x?
Ax = 5 (the first assignment wins)
Bx = 6 (the average of the two values)
Cx = 'not a constant' (multiple different values may reach this point)
Dx = 'undefined' (the assignment is considered ambiguous)
At a merge point, constant propagation must account for all paths that could have been taken. If one path sets x = 5 and another sets x = 7, the value at runtime depends on which branch executed — information unavailable at compile time. The lattice rule is: if both paths agree on the same constant, x stays that constant; if they disagree, x becomes 'not a constant.' This is the correct conservative choice — propagating a value the compiler isn't certain about risks generating incorrect code.
Question 2 Multiple Choice
After constant propagation and folding replace a variable with a known constant in a branch condition, what further optimization typically becomes possible?
ALoop unrolling, because the loop bound is now statically known
BDead code elimination, because the branch condition is now statically true or false
CRegister allocation, because constants do not need to occupy registers
DFunction inlining, because constant arguments can be substituted at call sites
If constant propagation determines that x = 7, the condition `if (x > 5)` becomes statically true. The else-branch can never execute — it is dead code. Dead code elimination then removes it entirely, shrinking the program and potentially exposing more constants by removing conflicting assignments. This chain — propagation enables folding, folding enables dead code elimination — is why constant propagation is often run early in the optimization pipeline.
Question 3 True / False
Constant folding and constant propagation are the same operation: both replace program values with known constants.
TTrue
FFalse
Answer: False
They are complementary but distinct. Constant propagation replaces variable *uses* with known constant values: if x is known to be 5, every use of x is replaced with the literal 5. Constant folding evaluates constant *expressions* at compile time: if the code contains `5 + 3`, folding replaces it with `8`. They work together — propagation creates constant-only expressions that folding can then evaluate — and the result of folding may itself be propagated further.
Question 4 True / False
If every reaching definition of a variable assigns the same constant value, the compiler can safely replace all uses of that variable with that constant.
TTrue
FFalse
Answer: True
This is exactly what constant propagation does: it uses reaching definitions analysis to determine, for each variable at each program point, whether all possible prior assignments agree on one constant value. If they do, the variable's value is known at compile time and every use can be replaced with the literal constant. The runtime load instruction becomes unnecessary, and the compiler may eliminate storage for that variable entirely.
Question 5 Short Answer
Why do constant propagation and constant folding typically create cascading opportunities for further compiler optimizations, rather than being a self-contained pass with limited effect?
Think about your answer, then reveal below.
Model answer: When propagation replaces variables with literals, and folding evaluates the resulting constant expressions, the simplified code often reveals conditions or values that other optimizations can act on. A constant in a branch condition makes the condition statically evaluable, enabling dead code elimination of the unreachable branch. Removing dead code may expose more reaching definitions with constant values, enabling another round of propagation and folding. Each pass creates the conditions that the next pass needs.
This chaining behavior is why compilers often run optimization passes in multiple rounds. Constant propagation and folding are usually applied early because their simplifications are foundational — they reduce the program to a simpler form that reveals more opportunities for subsequent passes like dead code elimination, strength reduction, and loop optimization.