Reaching definitions and constant propagation

Why it exists

Two basic questions about a variable at some point of the program: which assignments could have produced the value it has now? (reaching definitions) and is that value always the same known constant? (constant propagation). The first supports many checks and optimisations (a use with exactly one reaching definition can be replaced by the value of that definition; a use with none may read an uninitialised variable). The second lets the compiler replace variables by constants and fold the arithmetic, which often removes whole branches.

Prerequisites

You need the framework of data flow analysis: values at points, transfer functions, meet and the iterative algorithm (data flow framework).

Precise definitions

Definition. An instruction that may assign a value to a variable $x$ (here x = ...; also reads into $x$, and assignments through pointers in full languages). The definitions of the program are numbered $d_1, d_2, \ldots$ in program order.

Reaching definition. A definition $d$ of $x$ reaches a point $p$ if there is a path from the point after $d$ to $p$ along which $x$ is not redefined (killed). It is a may property: one path is enough. A definition of $x$ kills every other definition of $x$.

Gen and kill of a block. $\text{gen}_B$: the definitions in $B$ that reach the end of $B$, that is, for each variable defined in $B$ only the last definition of it in the block. $\text{kill}_B$: all other definitions (in the whole program) of the variables that $B$ defines.

Equations (forward, union).

$\text{IN}[B] = \bigcup_{P\ \text{pred of}\ B} \text{OUT}[P],\qquad \text{OUT}[B] = \text{gen}_B \cup (\text{IN}[B] - \text{kill}_B),\qquad \text{OUT}[\text{ENTRY}] = \emptyset.$

Uses of reaching definitions. Use-definition chains (for each use of a variable, the definitions that may supply its value): the basis of constant folding and copy propagation (if a single definition x = 5 reaches a use of x, the use can be replaced by 5), of detecting possibly-uninitialised variables (no definition reaches the use), and of loop-invariant code motion.

Constant propagation. For each variable at each program point the analysis tracks a value from a three-level lattice:

$\text{UNDEF}\ \ (\text{no information yet})\quad >\quad c\ (\text{a particular constant})\quad >\quad \text{NAC}\ (\text{not a constant}).$

The meet $\wedge$ of two values: $\text{UNDEF} \wedge v = v$; $c \wedge c = c$; $c_1 \wedge c_2 = \text{NAC}$ for $c_1 \ne c_2$; $\text{NAC} \wedge v = \text{NAC}$. At a join the meet is taken variable by variable. The data flow value at a point is a map from each variable to such a value, and the forward analysis starts with UNDEF everywhere except for variables whose value is not known at compile time (inputs), which are NAC.

Transfer function. Run the assignments of the block in order on the map. For x = c (a constant) set $x$ to $c$; for x = y give $x$ the value of $y$; for x = y op z: if both values are constants $c_1$, $c_2$ the value is $c_1 \,\text{op}\, c_2$; if either is NAC, NAC; if one is UNDEF and the other a constant, UNDEF (not yet known). A read from memory or a call gives NAC.

Properties. The framework is monotone (so the iterative algorithm terminates), but not distributive: the value of $x + y$ computed after the meet of two paths can be worse than the meet of the values computed along each path. The iterative (MFP) answer is therefore a safe but possibly less precise approximation of the meet over paths.

How it works

First the bookkeeping of reaching definitions on the loop program with six definitions (d1: i = m - 1, d2: j = n, d3: a = u1, d4: i = i + 1, d5: j = j - 1, d6: a = u2). The animation computes gen and kill for each block. In B2 the definition d4 of i is generated, and it kills the other definition of i, namely d1; in B3, d5 kills d2; in B4, d6 kills d3. B1 generates all three of its definitions and, since it defines i, j and a, kills d4, d5 and d6.

The iterative solution of the equations for this program is shown in the animation on the framework page: IN[B2] = {d1, d2, d3, d4, d5, d6} (the first three come from B1, the last three round the loop), so every definition of i, j and a reaches the start of B2.

Constant propagation on a graph with a branch. B1 sets x = 2 and y = 3 and tests c. If c > 0 control goes directly to the join; otherwise B2 sets y = 5. At the join z = x + y, w = x + 1 and print z. The variable c is an input (NAC). At the join x = 2 from both paths (so 2 ∧ 2 = 2), but y is 3 on one and 5 on the other: 3 ∧ 5 = NAC. Therefore z = x + y is NAC and w = x + 1 = 3 is a constant that can be folded.

Finally the example showing that constant propagation is not distributive. On one path the code sets x = 2, y = 3, on the other x = 3, y = 2, then z = x + y. The meet of the values at the join gives x = NAC and y = NAC, so z = NAC. But along both paths z = 5: applying the transfer function on each path and then taking the meet would have given the constant 5. The analysis loses this constant; it is safe (it does not claim anything false) but not as precise as it could be.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The framework is the data flow framework; the other bit-vector problems are liveness (the same machinery backwards) and available expressions (intersection). Within a single block the same effect is obtained by value numbering in local optimisation.

PYQs

Self-check

Revision card

References