Liveness analysis: live variables at each point; what liveness is used for

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• In constant propagation, what is 4 meet 5? from Lesson 6.3
• When is an assignment dead code? from Lesson 6.1
• What is A − B for sets A = {a, b, c} and B = {b}? from Lesson 0.2.1

1 · The Story

📖

Still needed?

The printers have only a few scratch slates for figures. Ishaan asks, for every point in the draft: which figures will still be read later, before being overwritten? Those must stay on a slate. Others can be wiped, and a figure that is never read again need not be computed at all.

He works backwards from the end. A figure is needed just before a sentence if the sentence reads it, or if it is needed just after the sentence and the sentence does not overwrite it. At a detour, a figure is needed if it is needed on any route that may follow.

2 · Predict First

🤔

In the straight-line code p = a + b; q = p * c; r = q − a; s = r + p; t = s * q with only t needed at the end, what is the largest number of values needed at the same time? Write your guess down. The answer is in the vault.

3 · Core Concept

Definition

A variable x is live at point p if the value of x at p may be used along some path starting at p, before x is redefined. Otherwise x is dead at p. These are the live variables.

Equations (backward, union)

Per block: use[B] = variables read in B before any assignment to them in B; def[B] = variables assigned in B. (Some books put in def only variables assigned before any read; IN comes out the same, because a variable read first is in use anyway.)

IN[B]  = use[B] ∪ (OUT[B] − def[B])
OUT[B] = ∪ over successors S of IN[S]        (OUT[EXIT] = ∅, or the variables used after the program)

Iterate to a fixed point, visiting blocks in reverse order to converge faster.

Inside a block

Walk backwards from OUT[B]: before the statement x = y op z, live = (live after − {x}) ∪ {y, z}. This gives the live set at every point.

What liveness is used for

• Dead-code elimination: an assignment x = … where x is dead just after it can be removed (no side effects).
• Register allocation: two variables live at the same point cannot share a register. In straight-line code the largest live set is the number of registers needed without spilling (for this simple model). Globally, variables that are live at the same time interfere and get different registers.
• Warnings about variables used before being set (live at the entry).

Story → compiler term

4 · Visual

Live variables (computed, 3 rounds in reverse order). e is live at the start of B1 because B4 reads it before writing it.

Live sets inside the straight-line block, computed backwards; the largest has 3 variables.

5 · Worked Examples

Example 1 Easy

Compute use, def, IN and OUT for B2 in the flow graph above.

Solution

B2: c = a + b; d = c − a. use = { a, b } (c is defined before it is used), def = { c, d }. OUT[B2] = IN[B3] = { a, b, c, d, e }; IN[B2] = use ∪ (OUT − def) = { a, b, e }. Working backwards, like Ishaan.

Example 2 Medium

Give the live variables before each statement of p = a + b; q = p * c; r = q − a; s = r + p; t = s * q (only t needed after), and the number of registers needed.

Solution

See the table: before p = a + b: { a, b, c }; … before t = s * q: { q, s }. Maximum 3, so 3 registers suffice. Note that after p is computed, b is dead: its register can hold p.

Example 3 GATE

B1: x = a + b, y = x * 2; B2: a = y − 1 (B2 loops back to B1); B3: z = x + y; edges B1→B2, B1→B3, B2→B1. Find IN[B1], OUT[B1], OUT[B2].

Solution

B3 needs x, y; B2 needs y and, via the back edge, whatever B1 needs. Computed: IN[B1] = { a, b }, OUT[B1] = { b, x, y }, OUT[B2] = { a, b }. a is live after B2 because B1 reads it again on the next pass.

6 · Shortcuts

⚡

Backward sweep inside a block: start with OUT; for each statement from the bottom, remove its target, add its operands. Valid when: live sets at every point and register counts.

⚡

use/def per block: scan top to bottom; a variable read before any write to it in the block is in use; every variable written is in def. Valid when: setting up the global equations.

7 · GATE Traps

⚠️

• Liveness is backward: OUT comes from successors.
• use[B] contains only variables read before being written in B.
• x = x + 1 uses x before defining it: x ∈ use.
• A variable can be live on exit even if B never mentions it (it just passes through).
• Meet is union: live if needed on some path.

8 · Memory Hook

🧠

Live = will be read before being overwritten. Go backwards; union at forks.

9 · Connect the Dots

Liveness asks about the future of variables. The last data-flow analysis asks about the past of expressions: has x + y already been computed on every path to here, with x and y unchanged? That powers common-subexpression elimination across blocks.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markDirection

Live-variable analysis is:

• (A) forward with ∩
• (B) backward with ∪
• (C) forward with ∪
• (D) backward with ∩

Q2NAT2 marksRegisters

For straight-line code m = x + y; n = m * x; o = n − y; p = o + m with only p needed after it, what is the largest number of variables live at any point?

Numerical answer: ________

Q3MCQ1 markuse

For the block x = y + 1; y = x * z, use[B] is:

• (A) { y, z }
• (B) { x, y, z }
• (C) { z }
• (D) { x, y }

Q4MSQ1 markUses

Liveness information is used for:

• (A) dead-code elimination
• (B) register allocation
• (C) constant folding
• (D) detecting variables used before being set

Q5NAT2 marksRegisters

For b = a + 1; c = b * 2; d = c + a; e = d − b with only e needed after it, how many registers are needed without spilling (max live)?

Numerical answer: ________

11 · Rule Card

• x live at p: its value may be used on some path from p before redefinition.
• use[B]: read before written in B; def[B]: assigned in B.
• IN = use ∪ (OUT − def); OUT = ∪ IN of successors; backward; start ∅.
• Inside a block, backwards: remove target, add operands.
• Uses: dead code (dead after assignment), register allocation (max live, interference).

12 · Concept Ledger

live variabledead variableuse[B] / def[B]liveness analysis (backward, ∪)register allocationinterferencespilling

13 · Answer Vault