Available expressions and common sub-expression elimination

Why it exists

Local common subexpression elimination finds a repeated computation inside one block. But a value computed in an earlier block may still be valid when a later block computes it again: if on every path to that later computation the expression has already been evaluated and its operands have not changed since, the second computation is redundant and can use the saved result. Available expressions analysis finds exactly these expressions.

Prerequisites

You need the data flow framework (data flow framework), with intersection as the meet.

Precise definitions

Available expression. An expression $x \,\text{op}\, y$ is available at a point $p$ if every path from the entry to $p$ evaluates $x \,\text{op}\, y$, and after the last such evaluation on the path there is no assignment to $x$ or $y$. It is a must property: all paths, not just one. If an expression is available where it is computed again, the new computation can reuse the earlier value.

Generating and killing.

• A block generates (e_gen) an expression if it evaluates it and does not redefine any of its operands afterwards in the block.
• A block kills (e_kill) an expression if it assigns to an operand of the expression and does not subsequently re-evaluate it (in the same block, after the assignment).

Within a block the instructions are taken in order: evaluating x + y adds the expression; assigning to x or y removes every expression that uses that variable. An instruction x = x + y evaluates x + y but also assigns x, so the expression is not generated (its operand changes).

Equations (forward, intersection).

$\text{IN}[B] = \bigcap_{P\ \text{pred of}\ B} \text{OUT}[P],\qquad \text{OUT}[B] = e\_gen_B \cup (\text{IN}[B] - e\_kill_B),\qquad \text{IN}[\text{ENTRY}] = \emptyset.$

The initial value of OUT[$B$] for every block other than the entry is the set $U$ of all expressions of the program (the identity of intersection). The iteration then removes the expressions that are not really available; it converges to the largest solution. Starting from the empty set would wrongly give an empty answer in loops.

Global common subexpression elimination. For an evaluation of $x \,\text{op}\, y$ at a point where it is available:

1. Find the evaluations of the expression that reach this point (the ones that make it available: going backwards along every path, the nearest evaluation).
2. Introduce a new temporary $s$; replace each of those evaluations u = x op y by s = x op y; u = s.
3. Replace the redundant evaluation v = x op y by v = s.

This is safe when the expression is available at the redundant evaluation and the temporary $s$ is not otherwise changed. It saves a computation at the cost of a copy, which a later copy-propagation pass may remove.

Difference from reaching definitions. Reaching definitions is a may analysis (union, one path is enough); available expressions is a must analysis (intersection, every path). Both are forward; the transfer functions have the same gen-kill form.

How it works

The program is t = a + b; u = c * d; if p > 0 goto B3 (block B1), a = 1; v = c * d; goto B4 (B2), w = c * d; e = 0 (B3, which falls through into B4) and z = a + b; y = c * d (B4). The animation solves the equations. After B1, OUT = {a + b, c * d}. B2 kills a + b (it assigns a), and c * d is evaluated after that assignment: OUT[B2] = {c * d}. B3 changes nothing that matters: OUT[B3] = {a + b, c * d}. At the join, IN[B4] = OUT[B2] ∩ OUT[B3] = {c * d}: c * d is available on both paths, a + b only on one. So in B4 the evaluation y = c * d is redundant, but z = a + b is not.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Within a single block the same redundancy is found by value numbering or by a DAG (local optimisation); available expressions extends it across blocks. The machinery is the data flow framework with intersection as the meet; the other forward problem, reaching definitions, uses union, and liveness runs backwards.

PYQs

Consider the control flow graph shown in the
figure.

Which one of the following options correctly lists
the set of redundant expressions (common
subexpressions) in the basic blocks B4 and B5?

Note: All the variables are integers.

Which one of the following is FALSE?

Self-check

Revision card

References