Consider this code sequence: `x = 5; y = x + 1; x = 10; return y;`. Is x live immediately after the statement `x = 5`?
ANo, because x is eventually overwritten by `x = 10` before the function returns
BNo, because only y is returned, so x's value is irrelevant throughout
CYes, because x holds a value that was just assigned and therefore must be live
DYes, because the next statement `y = x + 1` uses x before x is overwritten
Liveness asks: is there a path from this point to a use of x along which x is not redefined? After `x = 5`, the next statement uses x (in `y = x + 1`) before x is overwritten by `x = 10`. So x is live after the first assignment. The fact that x is later overwritten is irrelevant — what matters is whether the current value will be read first, and it will be.
Question 2 Multiple Choice
Why does live variable analysis propagate information backward through the control flow graph, unlike most forward dataflow analyses?
ABecause register allocation is performed in reverse program order by convention
BBecause dead code elimination removes instructions starting from the end of basic blocks
CBecause a variable's liveness at a point depends on whether future statements use it, which requires knowing what comes after
DBecause the gen and kill sets can only be computed after the interference graph is constructed
Liveness is inherently future-oriented: 'will this value be used before it's overwritten?' To answer this at any point, you need liveness information from the points that follow. The definition propagates backward: a use of x at a statement makes x live at that statement and at all preceding points until x is redefined. Forward analysis propagates information from definitions toward uses; backward analysis propagates from uses toward definitions.
Question 3 True / False
Two variables that are assigned values at different points in a program cannot interfere with each other in register allocation, since they are live at different times.
TTrue
FFalse
Answer: False
Interference depends on simultaneous liveness, not on where assignments occur. If both variables are live at the same program point — meaning both values might be needed at that moment — they interfere and cannot share a register. Variables assigned at different places can easily be simultaneously live if their live ranges overlap. Liveness analysis specifically computes this overlap to build the interference graph.
Question 4 True / False
An assignment to a variable that is not live after the assignment can always be safely removed, because the assigned value will never be read.
TTrue
FFalse
Answer: True
This is the foundation of dead code elimination using liveness. If a variable is not live after an assignment — meaning no path from that point reads the value before it is overwritten — then the assignment produces a result that is never consumed. Removing it preserves the program's observable semantics. This is safe precisely because liveness guarantees the value is unreachable, not merely unlikely to be reached.
Question 5 Short Answer
Explain why live variable analysis flows backward rather than forward through the control flow graph, and how the definition of liveness determines this direction.
Think about your answer, then reveal below.
Model answer: Liveness is defined in terms of the future: a variable is live at a point if its value will be read on some future execution path before being overwritten. 'Future' means the analysis needs information about what comes after — which requires working backwards from uses toward definitions. Starting at program exits (where nothing is live) and propagating backward, each use makes the used variable live, and each definition kills it. The backward direction is not a convention but a consequence of what liveness means.
Contrast with reaching definitions analysis, which flows forward because a definition 'reaches' a later point. Liveness flows backward because a use 'reaches back' to make earlier values needed. The gen/kill framework is the same; only the direction and the interpretation flip.