Liveness, available expressions and global common-subexpression elimination
Goal and conventions
Solve two set-valued data-flow problems and explain why they use different directions and merge operators. Variables are scalars; arithmetic is pure and nontrapping, there are no aliasing stores or calls, and all CFG edges considered are reachable. A variable is live at a point if some possible continuation uses its current value before redefining it. An expression is available if every path to the point has already evaluated it and has not subsequently redefined any operand.
1. Liveness: backward may analysis
USE[B] contains variables used before any definition of that variable within B. DEF[B] contains variables assigned in B. A variable can belong to both: x=x+1 uses the incoming x before defining the outgoing x. Branch conditions and return expressions are uses.
OUT[B]=union of IN[S] over successors S. IN[B]=USE[B] ∪ (OUT[B]−DEF[B]). The union means one path with a future use is enough. With no values required after program exit, exit OUT is empty. Initialize other liveness sets empty and iterate backward to a fixed point. An empty successor union is empty. If the interface requires output variables at exit, include them in the boundary rather than assuming they are dead.
Worked loop:
B1: a=1; b=2; goto B2 B2: c=a+b; a=c+1; if a<10 goto B2 else B3 B3: return c
USE1=∅, DEF1={a,b}; USE2={a,b}, DEF2={a,c}; USE3={c}, DEF3=∅. Although B2 reads c in a=c+1, that c was already defined in B2, so it is not in USE2.
Start all IN/OUT empty. Process B3,B2,B1: IN3={c}; OUT2={c} and IN2={a,b}; OUT1={a,b} and IN1=∅. A second pass adds the loop successor: OUT2=IN2∪IN3={a,b,c}; IN2 remains {a,b}. These are stable. OUT3=∅. The backward instruction trace inside B2 starts from live-after={a,b,c}. Before the branch it remains {a,b,c}; before a=c+1 it becomes {b,c}; before c=a+b it becomes {a,b}. This agrees with the block result.
2. Available expressions: forward must analysis
Let the finite universe U be the relevant pure expressions. IN[B] is the intersection of predecessor OUT sets; OUT[B]=GEN[B] ∪ (IN[B]−KILL[B]). KILL contains expressions mentioning any variable assigned in B. GEN contains expressions evaluated in B whose operand values are not changed after that evaluation, including by the assignment receiving the result. For x=x+y, the RHS is evaluated using old x but x is then changed, so expression x+y with current operands is not generated as available at exit by that instruction.
At entry, IN=∅: nothing is assumed precomputed. For the usual reachable CFG formulation, initialize other must-analysis facts to U and iterate downward, holding the entry boundary fixed. This differs from liveness's empty initialization. Intersecting at a join requires the expression to survive every incoming path. A union would assert availability after merely one path and could cause an invalid replacement.
3. Diamond trace and safe global CSE
Entry branches to L and R, then both join J. Let U={a+b}. L computes t1=a+b. R computes t2=a+b. Neither path changes a or b. Thus OUT[L]=OUT[R]={a+b}; IN[J]={a+b}. A computation t3=a+b in J is redundant in value. However, neither t1 nor t2 alone necessarily dominates J: t1 is absent on the R path and t2 absent on L. To reuse safely in ordinary non-SSA IR, the compiler can arrange both paths to assign a fresh temporary t=a+b, then use t at J. In SSA form, a suitable phi merges the two available result values. Availability proves the value exists on each path, not that one arbitrary predecessor's temporary is usable everywhere.
Now change R to t2=a+b; a=0. R kills a+b after evaluating it, so OUT[R]=∅. IN[J]={a+b}∩∅=∅. The J expression cannot be eliminated by the earlier availability argument. Even if a happens to have been zero before on one execution, that coincidence is not a proof for all inputs.
4. How the analyses support optimization
Liveness helps identify dead assignments and allocate registers, but deletion must still preserve side effects and traps. Available expressions supports common-subexpression elimination when matching operand identities, operator semantics and a usable stored result are established. Constant propagation tracks value facts rather than these sets; mixing its lattice initialization with either analysis is an error.
Pitfalls
Use before definition, not every use, determines block USE. Liveness uses successor union and runs backward; availability uses predecessor intersection and runs forward. At joins distinguish may from must. Revisit loop edges until stable. Never assume a dead value makes its computation harmless, or an available expression makes every old result variable valid at the join.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. For B2: c=a+b; a=c+1; if a<10..., USE[B2] is:
A. {a,b,c} B. {c} C. {a,b} D. ∅
Answer: C
A: c is defined before its first use within B2.
B: The incoming c is never used here.
C: a,b are read before definition; c is not.
D: The first assignment reads incoming a,b.
P02. At the liveness fixed point for the worked loop, OUT[B2] is:
A. {a,b} B. {c} C. ∅ D. {a,b,c}
Answer: D
A: The exit successor also needs c.
B: The loop successor also needs a,b.
C: Successors have required values.
D: Union of IN2={a,b} and IN3={c} gives all three.
P03. Which direction and join are used for available expressions?
A. Backward union B. Forward intersection C. Forward union D. Backward intersection
Answer: B
A: This describes liveness.
B: Every predecessor path must supply the expression.
C: One predecessor is insufficient for a must property.
D: Availability flows from prior evaluations to later points.
P04. Does x=x+y generate available expression x+y at its own exit, in general?
A. Yes, because it was evaluated B. No, the assignment changes operand x C. Yes, only because y is unchanged D. Only if x is live
Answer: B
A: The result uses the old x, not current x.
B: Updating x invalidates the expression with current operands.
C: All operands must retain their values.
D: Liveness does not establish expression-value equality.
P05. Both diamond paths compute a+b into distinct temporaries. At the join, availability alone guarantees:
A. t1 from the left is defined on every path B. t2 from the right is defined on every path C. The expression value has been computed on every path; a usable merged result is still needed D. The computation can always be deleted without any replacement
Answer: C
A: The right path may never define t1.
B: The left path may never define t2.
C: A common temporary or appropriate merge supplies a valid result name.
D: Users still require the correct result.
P06. If L.OUT={a+b} and R.OUT=∅, availability at their join is:
A. {a+b} B. ∅ C. {a,b} D. Unknown because union is undefined
Answer: B
A: The expression must be available on both paths.
B: Their intersection is empty.
C: The domain contains expressions, not variable names.
D: Intersection is defined and gives an empty set.
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