Liveness analysis

Why it exists

A variable is only worth keeping if its current value will be read later. If it will not, the assignment that computed it is wasted (dead code), and the register or memory location can be reused for something else (register allocation). Liveness analysis finds, for every point of the program, the set of variables whose present value may still be used. It looks forward in the program but works backwards: whether $x$ is live now depends on what happens after.

Prerequisites

You need the data flow framework (data flow framework): gen-kill sets, meet, and iteration; liveness is its backward instance.

Precise definitions

Live variable. A variable $x$ is live at a point $p$ if the value of $x$ at $p$ may be used along some path starting at $p$, that is, there is a path from $p$ to a use of $x$ on which $x$ is not redefined before that use. Otherwise it is dead at $p$. (A may property: one path suffices.)

use and def of a block.

• $\text{use}_B$: the variables whose value is read in $B$ before any assignment to them in $B$.
• $\text{def}_B$: the variables assigned in $B$ (whether or not they are used afterwards).

For a block a = b + c; b = 1; d = a: reading b and c before assigning, so $\text{use} = \{b, c\}$ (the a read in d = a was assigned earlier in the block, so it is not in use); $\text{def} = \{a, b, d\}$.

Equations (backward, union).

$\text{IN}[B] = \text{use}_B \cup (\text{OUT}[B] - \text{def}_B),\qquad \text{OUT}[B] = \bigcup_{S\ \text{succ of}\ B} \text{IN}[S],\qquad \text{IN}[\text{exit}] = \emptyset\ \text{(nothing is live after the program ends)}.$

IN[$B$] is the set of variables live at the start of $B$; OUT[$B$] the set live at its end. A variable live on exit from $B$ is live on entry unless $B$ assigns it first; a variable used in $B$ before being assigned is live on entry. The initial value of every set is $\emptyset$, and the blocks are visited in the reverse of the order used for forward problems. (If some variables are live on exit from the whole program, such as the results returned, they are put into the boundary value.)

Applications.

1. Dead-code elimination. An assignment x = ... is dead if $x$ is not live immediately after it. Inside a block scan backwards from OUT[$B$], keeping the live set: for each instruction, if its destination is not in the live set the instruction is dead (remove it, if it has no side effects); otherwise remove the destination from the set and add the operands.
2. Register allocation. The number of variables live at the same time is a lower bound on the registers needed; two variables that are never live together can share a register (the interference graph is built from liveness).
3. Detecting uninitialised variables: a variable live on entry to the program is used before it is defined.
4. The live-on-exit set of a block is what local optimisation needs to remove dead assignments inside the block.

How it works

The flow graph has four blocks: B1 (a = 1; b = 2; c = a + b; if c > 5 goto B3), B2 (d = c * 2; goto B4), B3 (d = a - b) and B4 (print d), with edges B1 → B2, B1 → B3, B2 → B4, B3 → B4. The animation computes use and def, then iterates backwards, B4 first. B4 reads d, so IN[B4] = {d} and OUT[B4] = ∅. B3 defines d and reads a and b: IN[B3] = {a, b} (d is defined in B3 so it is removed from OUT[B3] = {d}). B2 reads c and defines d: IN[B2] = {c}. B1's OUT is the union of the IN sets of B2 and B3, {c} ∪ {a, b}, and since B1 defines a, b, c they are all removed from IN[B1], which is empty: nothing is live on entry to the program (good: no variable is used before it is defined).

Worked examples

Cheat box

Traps and GATE patterns

Connections

Liveness is the backward case of the data flow framework. It gives the live-on-exit sets that local optimisation needs to delete dead assignments, and the live ranges that decide register sharing in code generation. Reaching definitions asks the dual question about where a value came from (reaching definitions).

PYQs

Consider the control flow graph given below.

Which one of the following options is the set of live
variables at the exit point of each basic block?

Which ONE of the following techniques used in
compiler code optimization uses live variable
analysis?

For a statement S in a program, in the context of
liveness analysis, the following sets are defined:

USE (S) : the set of variables used in S

IN (S) : the set of variables that are live at the entry
of S

OUT(S) : the set of variables that are live at the exit
of S

Consider a basic block that consists of two
statements, S1 followed by S2. Which one of the
following statements is correct?

Which one of the following is FALSE?

The program below uses six temporary variables a,
b, c, d, e, f.

a = 1

b = 10

c = 20

d = a+b

e = c+d

f = c+e

b = c+e

e = b+f

d = 5+e

return d+f

Assuming that all operations take their operands
from registers, what is the minimum number of
registers needed to execute this program without
spilling?

Self-check

Revision card

References