Block B1 assigns `x = 5` and block B2 assigns `x = 10`. Both B1 and B2 are predecessors of block B3, which contains the expression `y = x + 1`. Can constant propagation replace `x` with a constant value in B3?
AYes — x = 5 should be used because B1 is likely executed first
BYes — x = 10 should be used because it is the more recent assignment
CNo — both definitions reach B3, so the compiler cannot determine a unique constant value for x
DNo — reaching definitions cannot track variables across multiple blocks
Reaching definitions uses union at join points (it is a may-analysis): IN[B3] contains definitions from ALL predecessor blocks. Since both `x = 5` from B1 and `x = 10` from B2 reach B3, the compiler cannot assume x has a single constant value there — constant propagation requires exactly one reaching definition with a constant. Options A and B reflect the common mistake of assuming execution order determines which definition 'wins'; a dataflow analysis must conservatively account for all possible execution paths.
Question 2 Multiple Choice
Why does reaching definitions analysis use union (not intersection) to combine facts from predecessor blocks at a join point?
ABecause it is a must-analysis: a definition must reach via all paths to be considered live
BBecause it is a may-analysis: a definition reaches a point if it arrives via at least one path
CBecause the kill sets require union to correctly remove overwritten definitions
DBecause intersection would make the analysis unsound, producing too few reaching definitions
Reaching definitions is a may-analysis — it tracks which definitions *might* reach a given point along some path. A definition is included in IN[B] if it can arrive via ANY predecessor path, hence union. Intersection would compute the must-analysis dual: definitions that reach via ALL paths. Using intersection for reaching definitions would cause unsoundness in the opposite direction — it would miss valid reaching definitions, incorrectly enabling optimizations like constant propagation when a definition only sometimes reaches a use.
Question 3 True / False
If a variable x is assigned in every predecessor block of block B, then every one of those definitions appears in IN[B].
TTrue
FFalse
Answer: True
Because reaching definitions uses union at join points, IN[B] = union of OUT[pred] for all predecessors. If x is defined in every predecessor, each predecessor's OUT set includes that definition, and the union includes all of them. This is precisely why reaching definitions cannot enable constant propagation when multiple different definitions reach a point — all of them are tracked, even if the same variable is defined everywhere.
Question 4 True / False
A basic block's kill set contains definitions that occur after that block in the control flow graph and that assign to the same variable.
TTrue
FFalse
Answer: False
The kill set contains definitions that occur BEFORE the current block (anywhere else in the program) that assign to the same variable as a definition in this block. When a block defines x, it 'kills' (overwrites) any earlier reaching definition of x, because the old value of x can no longer reach points after this block unchanged. The kill set looks backward, not forward — it identifies what the current block's assignments destroy, not what later blocks might overwrite.
Question 5 Short Answer
Explain why reaching definitions is classified as a 'may-analysis' and what practical consequence this has for how compilers use its results.
Think about your answer, then reveal below.
Model answer: Reaching definitions is a may-analysis because a definition is considered to reach a point if there EXISTS at least one control-flow path from the definition to that point without an intervening kill — not if all paths carry the definition. The practical consequence is conservatism: the analysis over-approximates, potentially reporting more definitions as reaching than actually execute at runtime. Compilers using the results for optimization (e.g., constant propagation) must treat a use as safe to optimize only if exactly one definition reaches it — any ambiguity blocks the optimization. May-analyses are sound for this use case because they never miss a real reaching definition.
The may/must distinction in dataflow analysis determines how join points combine information. May-analyses (union) are appropriate when any reachable path matters — for reaching definitions, a definition that can arrive on even one path must be considered because the compiler cannot rule out that path being taken at runtime. Must-analyses (intersection) would only retain definitions guaranteed to arrive regardless of which path executes, which is overly restrictive for most forward dataflow problems.