Liveness analysis is a backward analysis because:

Liveness at a point depends on what happens after that point

It uses intersection as its meet operator

Registers are allocated from the end of the program

An assignment x = e is dead code when:

x is not live immediately after the assignment

x never appears again in the program text

Global data flow analysis needs an iterative fixpoint computation, whereas analysis within a basic block does not, because:

A loop makes a block’s input depend on its own output

Global analysis uses more variables

Basic blocks have no assignments

Available-expression analysis initialises the interior sets to the full set of expressions rather than to the empty set because:

It is a must analysis whose meet is intersection

There are usually many expressions

In the block a = b + c; d = a * 2; b = d + 1; e = a + b with b and e live on exit, over which range is d live?

From statement 2 to the end of the block

Local Optimisation and Data Flow Analysis

Optimisation is where a compiler stops translating and starts reasoning, and the reasoning is always the same shape: compute a fact at every program point, then use it to justify a rewrite. The facts come from data flow analysis, and the syllabus names three, which between them cover both directions the analysis can run. Liveness is a backward analysis: a variable is live at a point if some path from there reads it before writing it, and the information therefore flows from the end of the program towards the beginning. That single fact licenses two optimisations — a value that is not live need not be kept in a register, and an assignment to a variable that is never live afterwards is dead code and can be deleted outright. Available expressions, which is what justifies common subexpression elimination, is a forward analysis: an expression is available at a point if it has been computed on every path reaching that point and none of its operands has changed since. Constant propagation is forward too, replacing a variable by a literal wherever the analysis can prove only one value reaches. The direction matters more than it sounds: it determines whether you meet at the start or the end of a block and whether you iterate towards the entry or the exit, and getting it backwards produces a confident answer that is simply about the wrong thing. And one boundary is worth fixing early: local optimisation works inside a single basic block, where control flow is straight-line and the analysis is a walk; global optimisation works across the control-flow graph and needs the fixpoint iteration, because a loop means a block's input depends on its own output.

Which Way Does the Analysis Run?

The three analyses the syllabus names, by direction
Analysis	Direction	What it licenses
Liveness	Backward — from the exit	Register allocation, and dead-code elimination
Available expressions	Forward — from the entry	Common subexpression elimination
Constant propagation	Forward	Replacing a variable by a literal; constant folding
Reaching definitions	Forward	Copy propagation, and use–def chains

🎯 Why liveness has to run backwards

The definition of live is about the future: a variable is live at a point if some path from there onwards uses its current value before overwriting it. So the question at each point can only be answered once the answer for its successors is known, and the computation must start at the exit and work back. Every analysis whose definition mentions later use is backward for the same reason. Contrast available expressions, whose definition is about the past — has this been computed on every path reaching here — so it starts at the entry and moves forward. The practical test, when you cannot remember which is which, is to read the definition and ask whether it says "will be used" or "has been computed": the tense gives the direction away, and getting it right is most of the work.

A Liveness Computation, Run

Take the block a = b + c, d = a * 2, b = d + 1, e = a + b, and suppose b and e are live on exit. Work upwards, and at each statement remove the variable being defined and add the variables being used:

Live sets, computed from the bottom up
Statement	Live OUT	Live IN
`e = a + b`	{ b, e }	{ a, b }
`b = d + 1`	{ a, b }	{ a, d }
`d = a * 2`	{ a, d }	{ a }
`a = b + c`	{ a }	{ b, c }

🧠 The live-in of the whole block is what it needs from outside

Reading the last row: at the top of the block only b and c are live, which says the block needs exactly those two values from its predecessors and nothing else. Everything else — a, d, e — is produced inside. That is the useful output of the whole computation, because it is what a register allocator and an inter-block analysis actually consume. Two details worth noticing in the table. b appears in both the live-out and the live-in for different reasons: it is read at the top before being redefined at the third statement. And d is live only between statements 2 and 3 — a very short range, which is exactly what makes it a good candidate to keep in a register rather than memory. A variable's live range, not its scope, is what determines whether it needs storage.

⚠️ Dead code is defined by liveness, not by looking unused

An assignment is dead when the variable it writes is not live immediately afterwards, and that is a statement about all paths from that point rather than about the surrounding lines. So an assignment can look used — the variable appears again later — and still be dead, if every path to that later use passes through another assignment first. Conversely a variable used only on one rare branch is still live and its assignment cannot be removed. In the block above nothing is dead: d is read at statement 3 and a at statements 2 and 4. But add d = 7 at the end and that becomes dead, because d is not in the block's live-out set — which is only knowable from the liveness computation, and is why the analysis comes before the optimisation rather than after it.

Local, Global, and Why Loops Force Iteration

Local optimisation stays inside one basic block. A basic block has no branches in or out except at its ends, so control flow is a straight line and the analysis is a single walk — which is why common subexpression elimination within a block is cheap and needs no iteration. Global optimisation works over the control-flow graph, and there a loop means a block's input set depends on its own output set. The only way through that circularity is a fixpoint iteration: initialise, propagate repeatedly, and stop when nothing changes.

🎯 Why the iteration terminates, and which way to initialise

The sets are subsets of a finite universe — the variables, or the expressions in the program — and each iteration only moves in one direction: monotonically growing for a may analysis, monotonically shrinking for a must one. A monotone sequence in a finite lattice cannot go forever, so the iteration reaches a fixpoint. Which direction it moves in decides the initialisation, and this is where questions catch people. Liveness is a "may" analysis — live if some path uses the value — so the meet is union and the sets start empty and grow. Available expressions is a "must" analysis — available only if computed on every path — so the meet is intersection and the interior sets start full and shrink. Initialising a must-analysis to empty gives a fixpoint immediately and the answer is trivially wrong, which is the failure mode worth recognising: the iteration converges, quickly, on nothing.

Key takeaways

Every optimisation is a fact computed by data flow analysis plus a rewrite that fact licenses.
Liveness is backward; available expressions and constant propagation are forward.
Read the definition’s tense: "will be used" is backward, "has been computed" is forward.
On a = b+c; d = a*2; b = d+1; e = a+b with live-out {b,e}, the block’s live-in is {b, c}.
An assignment is dead when its target is not live immediately after — a fact about all later paths.
A variable’s live range, not its scope, decides whether it needs storage.
Local optimisation is one walk through a basic block; global needs fixpoint iteration because loops.
A may-analysis meets by union and starts empty; a must-analysis meets by intersection and starts full.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

For the block a = b + c; d = a * 2; b = d + 1; e = a + b with b and e live on exit, the set of variables live at the START of the block is:
1. { a, b, c }
2. { b, c }
3. { b, e }
4. { a, d }
Show answer
Answer: B — { b, c }
{ b, c }. Work upwards, removing each defined variable and adding each used one. From live-out { b, e }: statement 4 gives { a, b }; statement 3 gives { a, d }; statement 2 gives { a }; statement 1 defines a and uses b and c, giving { b, c }. That set is the useful product of the whole computation — it says the block needs exactly b and c from its predecessors, and produces a, d and e internally. Option A wrongly keeps a live at the top, but statement 1 defines a, so anything live in a before this block is irrelevant. Option C is the live-out set offered as the live-in, which is the commonest slip when the direction of the analysis is not fixed first.
Liveness analysis is a backward analysis because:
1. It is computed after parsing
2. Liveness at a point depends on what happens after that point
3. It uses intersection as its meet operator
4. Registers are allocated from the end of the program
Show answer
Answer: B — Liveness at a point depends on what happens after that point
A variable is live at a point if some path from there onwards reads its current value before overwriting it — a statement about the future — so the answer at each point requires the answers at its successors, and the computation must start at the exit. Option C is wrong on the specifics and is worth correcting: liveness is a may analysis (live if some path uses it), so its meet is union, and it is available expressions that meets by intersection. Option A confuses the phase ordering of a compiler with the direction of an analysis; plenty of forward analyses also run after parsing. The reliable test is the tense of the definition — "will be used" is backward, "has been computed" is forward.
Common subexpression elimination is justified by which analysis?
1. Liveness
2. Available expressions
3. Reaching definitions
4. Constant propagation
Show answer
Answer: B — Available expressions
Available expressions. To replace a recomputation of b * c by a previously computed value, you need to know that b * c has been evaluated on every path reaching this point and that neither b nor c has been assigned since — which is exactly what availability asserts. Liveness answers a different question, about whether a value will still be needed, and licenses dead-code elimination and register allocation instead. The "every path" in the definition is what makes availability a must analysis, so its meet is intersection and its sets are initialised full rather than empty — a detail that decides whether the fixpoint iteration gives the right answer or converges instantly on nothing.
Which of the following are forward data flow analyses? (More than one may be correct.)
1. Available expressions
2. Reaching definitions
3. Constant propagation
4. Live variable analysis
Show answer
Answer: A — Available expressions; B — Reaching definitions; C — Constant propagation
A, B and C. All three ask about the past — has this expression already been computed, which definitions have already reached here, what value has already been established — so information flows from the entry towards the exit. D is the backward one: liveness asks whether a value will be used later, so it flows from the exit backwards. The other axis is independent and worth keeping separate: available expressions is a must analysis (intersection, initialise full) while reaching definitions is a may analysis (union, initialise empty), even though both are forward. Direction and meet operator are two separate choices, and a question can test either.
An assignment x = e is dead code when:
1. e has no side effects
2. x is not live immediately after the assignment
3. x never appears again in the program text
4. e is a constant
Show answer
Answer: B — x is not live immediately after the assignment
x is not live immediately after. That is the definition, and it is a statement about all paths forward from that point rather than about the surrounding text — which is exactly why option C is not equivalent. x can appear again later and the assignment still be dead, if every path to that later use passes through another assignment to x first; and conversely a use on one rare branch keeps x live. Option A is a necessary side condition for actually deleting the statement rather than a criterion for deadness: if e calls a function with side effects, the value is dead but the statement cannot simply be removed. Distinguishing "the value is unused" from "the statement is removable" is the practical content here.
Global data flow analysis needs an iterative fixpoint computation, whereas analysis within a basic block does not, because:
1. Basic blocks are shorter
2. A loop makes a block’s input depend on its own output
3. Global analysis uses more variables
4. Basic blocks have no assignments
Show answer
Answer: B — A loop makes a block’s input depend on its own output
A basic block is straight-line code, so one walk in the right direction computes every fact exactly once. A control-flow graph with a loop is circular: the facts entering a loop body depend on the facts leaving it, which depend in turn on those entering. The only way through is to iterate to a fixpoint — and it terminates because the sets are subsets of a finite universe and each step moves monotonically in one direction. Option A is true and irrelevant: length is not what forces iteration, circularity is, and a very long straight-line block still needs only one pass. The initialisation is what the direction of that monotonic movement decides — empty for a may analysis, full for a must one.
Available-expression analysis initialises the interior sets to the full set of expressions rather than to the empty set because:
1. It is a forward analysis
2. It is a must analysis whose meet is intersection
3. There are usually many expressions
4. It runs before liveness
Show answer
Answer: B — It is a must analysis whose meet is intersection
Availability requires an expression to be computed on every path reaching a point, so the sets are combined by intersection and can only shrink as the iteration proceeds. Starting them empty would make every intersection empty, the iteration would stop immediately, and the analysis would report that nothing is ever available — a fixpoint, reached fast, and wrong. Starting full lets the intersections cut away only what is genuinely unavailable. Option A names the right property of the wrong axis: direction and meet operator are independent choices, and reaching definitions is forward while meeting by union and initialising empty. Reading the definition for "every path" against "some path" is what settles the initialisation.
In the block a = b + c; d = a * 2; b = d + 1; e = a + b with b and e live on exit, over which range is d live?
1. Throughout the block
2. Only between statements 2 and 3
3. From statement 2 to the end of the block
4. It is never live
Show answer
Answer: B — Only between statements 2 and 3
Only between statements 2 and 3. d is defined at statement 2 and read at statement 3, and it appears in no later statement and not in the live-out set — so its live range is that single gap. Option C is the natural error, from assuming a variable stays live to the end of its scope; live range and scope are different things, and the whole value of the analysis is that it computes the former. The practical consequence is that d is an excellent candidate to keep in a register, because its range does not overlap much: two variables can share a register precisely when their live ranges are disjoint, which is why register allocation is a graph-colouring problem on the interference of these ranges.