Available Expressions
Programs recompute things. A loop body squares an index, an address calculation re-adds the same base
and stride, a bounds check re-evaluates n-1 for the third time this block.
Some of that repetition is genuinely necessary; much of it is not. Available-expressions
analysis is the compiler's tool for telling the two apart across the whole procedure,
and it is the engine behind global common-subexpression elimination (global CSE): if
the value of a+b is already sitting in a register when control reaches you,
do not compute a+b again — reuse it.
Locally, within one basic block, spotting a redundant a+b is easy — you just
read the block top to bottom (that is what the
value-numbering DAG
does). The hard, interesting question is global: at a point p buried
deep in the control-flow graph, with many paths flowing into it, is a+b
guaranteed to have been computed already, no matter which path execution actually took? That is
a job for the
dataflow framework.
What "available" means — precisely
-
An expression x \circ y (say a+b) is
available at a program point p if on every path
from the entry of the procedure to p, the expression is computed
at least once, and
-
after the last such computation on the path, no operand
(x or y) is redefined before reaching
p.
The word doing all the work is every. One path that fails to compute
a+b, or that clobbers a after computing it, is
enough to make the expression unavailable. This is a "must" property — it must
hold on all incoming paths — and that single fact dictates the entire shape of the analysis: the paths
are combined with intersection, and the iteration starts optimistic,
assuming everything is available until a path proves otherwise. It is a forward
analysis, because availability accumulates as control flows forward from the entry.
Local effect: e\text{-}gen and e\text{-}kill
Before we can talk about whole paths, we summarise each basic block B by two
sets over the fixed universe U of all candidate expressions in the
procedure:
| Set | Meaning |
|---|
| e\text{-}gen[B] |
expressions computed in B whose operands are
not subsequently redefined within B — the
block generates them and they survive to its exit |
| e\text{-}kill[B] |
expressions in U that use a variable
B redefines — assigning to
a kills every expression that mentions a |
With those, the transfer function of a block — how it turns the set available on entry
into the set available on exit — is the familiar dataflow shape "gen what you make, keep what survives":
\mathrm{OUT}[B] \;=\; e\text{-}gen[B] \;\cup\; \big(\mathrm{IN}[B] \setminus e\text{-}kill[B]\big).
And because availability must hold on all incoming edges, the value on entry is the
intersection (the meet, "\wedge") over predecessors:
\mathrm{IN}[B] \;=\; \bigcap_{P \,\in\, \mathrm{pred}(B)} \mathrm{OUT}[P], \qquad \mathrm{IN}[\text{entry}] = \varnothing.
The initialisation that trips everyone up
You solve those equations by iteration. But what do you start from? For a "must" analysis the
answer is counter-intuitive and it is the single most common bug: initialise
\mathrm{OUT}[B] = U \ \text{(the FULL universe)} \quad\text{for every block } B \neq \text{entry},\qquad \mathrm{OUT}[\text{entry}] = e\text{-}gen[\text{entry}].
Start by optimistically assuming every expression is available everywhere, then let the
intersections chip availability away as the iteration discovers paths that fail. This is exactly the
opposite of a "may" analysis such as
reaching definitions,
which unions and starts from \varnothing. Intersecting into an
\varnothing-initialised set would wrongly annihilate everything on the first
pass; you must start from the top element of the lattice, and for a
must/intersection analysis the top element is the full set U.
A worked example
Track three expressions, U = \{\,a+b,\ a\cdot c,\ b+c\,\}, over this small
control-flow graph. Block B_1 computes a+b and
a\cdot c; the graph then forks, and on the left arm B_3
redefines c (killing a\cdot c and
b+c), while on the right arm B_4 computes
b+c. Both arms merge at B_5, which uses
a+b and a\cdot c.
The per-block summaries are:
| Block | code | e\text{-}gen | e\text{-}kill |
|---|
| B_1 | t1 = a+b; t2 = a·c | {a+b, a·c} | { } |
| B_2 | (branch) | { } | { } |
| B_3 | c = … | { } | {a·c, b+c} |
| B_4 | t3 = b+c | {b+c} | { } |
| B_5 | use a+b, a·c | { } | { } |
Now iterate. Every non-entry \mathrm{OUT} begins at the full set
U=\{a{+}b, a{\cdot}c, b{+}c\}; one forward sweep already reaches the fixed
point:
| Block | Init OUT | Pass 1 · IN | Pass 1 · OUT |
|---|
| B_1 | {a+b, a·c} | { } (entry) | {a+b, a·c} |
| B_2 | U | {a+b, a·c} | {a+b, a·c} |
| B_3 | U | {a+b, a·c} | {a+b} |
| B_4 | U | {a+b, a·c} | {a+b, a·c, b+c} |
| B_5 | U | {a+b} | {a+b} |
The punchline is \mathrm{IN}[B_5]: the meet
\mathrm{OUT}[B_3] \cap \mathrm{OUT}[B_4] = \{a{+}b\} \cap \{a{+}b, a{\cdot}c, b{+}c\} = \{a{+}b\}.
So a+b is available at B_5 — its two uses are
redundant and CSE can replace them with the saved value. But
a\cdot c is not available, precisely because the left arm
B_3 redefined c; the intersection dropped it,
exactly as the "must on every path" rule demands.
Solving it in code
Represent each set as a bitset — one bit per expression in
U — so meet is bitwise AND, union is OR, and
difference is AND-NOT. The universal set is the all-ones mask. The solver below runs the exact
example above and prints the availability at each block's entry.
// Available expressions via bitsets. Bit i = expression i is available.
// Universe U = [a+b, a*c, b+c] -> bits 0,1,2.
const NAMES = ["a+b", "a*c", "b+c"];
const U = (1 << NAMES.length) - 1; // all-ones universal set = 0b111
interface Block {
name: string;
preds: number[];
eGen: number; // bitset
eKill: number; // bitset
}
const b = (...bits: number[]) => bits.reduce((m, i) => m | (1 << i), 0);
// B1 entry(0) -> B2(1) -> {B3(2), B4(3)} -> B5(4).
const blocks: Block[] = [
{ name: "B1", preds: [], eGen: b(0, 1), eKill: b() }, // t1=a+b; t2=a*c
{ name: "B2", preds: [0], eGen: b(), eKill: b() }, // branch
{ name: "B3", preds: [1], eGen: b(), eKill: b(1, 2) }, // c = ... kills a*c, b+c
{ name: "B4", preds: [1], eGen: b(2), eKill: b() }, // t3 = b+c
{ name: "B5", preds: [2, 3], eGen: b(), eKill: b() }, // uses a+b, a*c
];
const IN = new Array(blocks.length).fill(U);
const OUT = blocks.map((_, i) => (i === 0 ? 0 : U)); // MUST-analysis: init to FULL set
OUT[0] = blocks[0].eGen; // ...except entry's OUT
let changed = true, rounds = 0;
while (changed) {
changed = false;
rounds++;
for (let i = 0; i < blocks.length; i++) {
const B = blocks[i];
// meet = INTERSECTION over predecessors (empty preds -> entry gets empty set)
let inSet = B.preds.length ? U : 0;
for (const p of B.preds) inSet &= OUT[p];
IN[i] = inSet;
const out = B.eGen | (inSet & ~B.eKill & U); // gen ∪ (IN \ kill)
if (out !== OUT[i]) { OUT[i] = out; changed = true; }
}
}
const show = (m: number) => "{" + NAMES.filter((_, i) => m & (1 << i)).join(", ") + "}";
console.log(`converged in ${rounds} passes`);
for (let i = 0; i < blocks.length; i++) {
console.log(`${blocks[i].name}: available on entry = ${show(IN[i])}`);
}
The output confirms the hand-computation: only {a+b} is available entering
B5. Change B3's kill to b() and rerun — now
a*c survives the intersection and becomes redundant too. That one-line edit is the
difference between "the left path clobbers c" and "it doesn't".
The four textbook bit-vector analyses are the same algorithm with two independent switches:
direction (forward vs. backward) and meet (union "may" vs. intersection
"must"). Available expressions is forward + intersection. Reaching definitions is
forward + union. Live variables is backward + union. Very-busy (anticipable)
expressions is backward + intersection. Learn the two switches and you have not learned four
analyses — you have learned one framework with four settings, which is precisely the point of casting
them as a lattice
problem. The meet direction alone fixes the initial value: union analyses start empty, intersection
analyses start full.
Two mistakes recur, and both come from muscle memory built on union analyses. First, the
initialisation: for available expressions you must set every non-entry
\mathrm{OUT}[B] to the full universe
U, not to \varnothing. Seed with
\varnothing and the first intersection wipes out every expression and stays
there — you will "prove" nothing is ever available. Second, the meet is intersection
(bitwise AND), never union: an expression is available at a merge only if it is available on
every incoming edge. And keep the third rule in the front of your mind: a single redefinition
of any operand kills the expression — assigning to a removes
a+b, a\cdot c, and every other expression that
mentions a, no matter how the value of a was
computed.