Common Subexpression Elimination: short notes (Compiler Design)

Introduction

An occurrence of an expression $x \mathbin{op} y$ is a common subexpression if the same expression was computed earlier and neither $x$ nor $y$ has changed since. Recomputing it wastes time; reusing the earlier value is common subexpression elimination (CSE). Within a basic block, the DAG finds such reuse directly. Across blocks, the compiler needs to know that the expression was computed on every path to the current point, which is the available expressions analysis.

This note covers the global case: the definition of availability, the $e\_gen$ and $e\_kill$ sets, the forward-intersection equations and their initialisation, and the transformation that introduces a temporary. Questions ask whether an expression is available at a point, for the IN and OUT sets of a small flow graph, or for the code after global CSE.

Prerequisites

Local Optimisation and DAG Representation of Basic Blocks: local common subexpressions and why a redefined operand prevents reuse.
Data-Flow Analysis Framework: forward analyses, meet by intersection, the iterative algorithm.

Core concepts

Available expression. $x + y$ is available at point $p$ if every path from the entry to $p$ evaluates $x + y$ , and after the last such evaluation on each path there is no assignment to $x$ or $y$ .
Generates. A block generates $x + y$ if it evaluates $x + y$ and does not afterwards redefine $x$ or $y$ .
Kills. A block kills $x + y$ if it assigns $x$ or $y$ and does not afterwards recompute $x + y$ .
Universe $U$ . All expressions appearing on the right of instructions in the program.
Equations.

OUT[\text{entry}] = \emptyset, \qquad IN[B] = \bigcap_{P \in pred(B)} OUT[P], \qquad OUT[B] = e\_gen_B \cup (IN[B] - e\_kill_B)

Initialisation. $OUT[B] = U$ for every $B$ other than the entry. Starting at $U$ and shrinking finds the largest solution.

How it works

Computing $e\_gen$ and $e\_kill$ within a block

Scan the block forward. For each instruction $z = x \mathbin{op} y$ :

Add $x \mathbin{op} y$ to $e\_gen$ (and remove it from $e\_kill$ ).
Remove from $e\_gen$ every expression that has $z$ as an operand, and add those expressions (from $U$ ) to $e\_kill$ .

The order matters: in x = x + y the expression $x + y$ is generated and then killed by the assignment to $x$ , so the block does not generate it.

Example 1: one expression available, one not

Text

B1: a = x + y
    p = x * y
B2: if a > 0 goto B4        (B1 -> B2; B2 -> B3; B2 -> B4)
B3: x = a - 1
    q = x * y               (B3 -> B4)
B4: c = x + y
    e = x * y

Take $U = \{x + y,\ x * y,\ a - 1\}$ .

Block	$e\_gen$	$e\_kill$
$B_1$	$x + y,\ x * y$	$a - 1$
$B_2$	none	none
$B_3$	$a - 1,\ x * y$	$x + y$
$B_4$	$x + y,\ x * y$	none

In $B_3$ , x = a - 1 kills both expressions over $x$ , but q = x * y then generates $x * y$ again; $x + y$ stays killed.

Solving (one pass already gives the fixed point here, a second confirms it):

Block	$IN$	$OUT$
$B_1$	$\emptyset$	$x + y,\ x * y$
$B_2$	$x + y,\ x * y$	$x + y,\ x * y$
$B_3$	$x + y,\ x * y$	$a - 1,\ x * y$
$B_4$	$OUT[B_2] \cap OUT[B_3] = x * y$	$x + y,\ x * y$

So in $B_4$ , $x * y$ is available but $x + y$ is not: along the path through $B_3$ , $x$ changes after $x + y$ was computed. Note that $x * y$ holds different values on the two paths (it was recomputed in $B_3$ after $x$ changed); availability only requires that the most recent evaluation on each path is still valid.

Available expressions and global CSE on the four-block example — Figure 1. Available expressions on the four-block example: x + y and x * y are available after B1, B3 kills x + y but recomputes x * y, so at the entry of B4 only x * y is available, and global CSE replaces e = x * y in B4 by e = u1, with u1 set in both B1 and B3.

The global CSE transformation

For each instruction $s: z = x \mathbin{op} y$ such that $x \mathbin{op} y$ is available at $s$ (and not killed earlier in $s$ 's block):

Search backward along the flow graph from $s$ to find the evaluations $w = x \mathbin{op} y$ that reach $s$ (stopping at each such evaluation).
Create a new temporary $u$ .
Replace each such evaluation $w = x \mathbin{op} y$ by $u = x \mathbin{op} y$ followed by $w = u$ .
Replace $s$ by $z = u$ .

For Example 1, the evaluations of $x * y$ reaching $B_4$ are in $B_1$ and $B_3$ :

Text

B1: a  = x + y
    u1 = x * y
    p  = u1
B3: x  = a - 1
    u1 = x * y
    q  = u1
B4: c  = x + y
    e  = u1

One multiplication is saved on every execution of $B_4$ . The copies p = u1 and q = u1 are candidates for copy propagation: if later uses of p and q can read u1 instead, the copies become dead and are removed. In $B_4$ , c = x + y must stay: the expression is not available on the path through $B_3$ .

Example 2: why the initial value is $U$

Text

B1: a = x + y               (B1 -> B2)
B2: (loop header; no code)  (B2 -> B3, B2 -> B4)
B3: b = 2                   (B3 -> B2, the back edge)
B4: c = x + y

Nothing in the loop touches $x$ or $y$ , so $x + y$ is available at $B_4$ . Starting from $OUT[B] = U$ , the first pass gives $IN[B_2] = \{x + y\} \cap U = \{x + y\}$ , and the value survives every pass. Starting instead from $OUT[B] = \emptyset$ , $IN[B_2] = \{x + y\} \cap OUT[B_3] = \emptyset$ on the first pass and stays empty forever, because nothing in the loop regenerates $x + y$ . The empty start is safe but loses this common subexpression. Intersection problems start at the top, $U$ , so that back edges do not erase facts prematurely.

Example 3: a loop that redefines an operand

Text

B1: t = a + b               (B1 -> B2)
B2: c = a + b               (B2 -> B3, B2 -> B4)
B3: a = c + 1               (B3 -> B2, the back edge)
B4: d = a + b

Take $U = \{a + b,\ c + 1\}$ . $B_1$ generates $a + b$ ; $B_2$ generates $a + b$ and kills $c + 1$ ; $B_3$ generates $c + 1$ and kills $a + b$ .

Block	$IN$	$OUT$
$B_1$	$\emptyset$	$a + b$
$B_2$	$OUT[B_1] \cap OUT[B_3] = \emptyset$	$a + b$
$B_3$	$a + b$	$c + 1$
$B_4$	$a + b$	$a + b$

c = a + b in $B_2$ is not redundant, although $B_1$ computed $a + b$ just before: on the second and later iterations control arrives from $B_3$ , where $a$ has changed.
d = a + b in $B_4$ is redundant: the only way into $B_4$ is from $B_2$ , which has just evaluated $a + b$ with the current $a$ . The backward search from $B_4$ stops at $B_2$ , so only that evaluation gets the temporary: $B_2$ becomes u = a + b; c = u, and $B_4$ becomes d = u. $B_1$ is unchanged.

What else kills an expression

Commutativity is not assumed. $a + b$ and $b + a$ are different expressions for the basic analysis; a compiler that normalises operand order (for commutative operators only) can treat them as one.
Stores through pointers and procedure calls. *p = w may assign any variable p can point to, and a call may assign any variable the callee can reach. Without alias information, such an instruction kills every expression whose operands might be affected.
Array element assignments kill expressions that read the same array, as in local CSE.

Local and global CSE together

Local CSE (the DAG of a block) handles repetitions inside a block; global CSE handles expressions whose earlier evaluation is in another block. A compiler usually runs local CSE first, so that each block evaluates each expression at most once before its operands change, then global CSE, then copy propagation and dead-code elimination to clean up the copies.

Related material. Partial-redundancy elimination handles expressions available on some paths but not all, as $x + y$ at $B_4$ in Example 1, by inserting evaluations on the paths that lack them (here, after x = a - 1 in $B_3$ ) so that the expression becomes fully redundant. It also subsumes loop-invariant code motion. It is the subject of Dragon Book Section 9.5 (lazy code motion).

Important properties and observations

Forward and intersection: an expression must be available along all paths; one killing path suffices to make it unavailable.
Initialise to $U$ (except at the entry). Initialising to $\emptyset$ is safe but can lose availability around loops (Example 2).
Availability is about expressions, not values: $x * y$ at $B_4$ has different values on the two paths, and the temporary handles that.
Kill by operand assignment: any assignment to $x$ or $y$ kills every expression over $x$ or $y$ unless it is recomputed later in the block.
Order inside a block matters for $e\_gen$ and $e\_kill$ , as in x = x + y.
CSE introduces copies, which copy propagation and dead-code elimination then remove.

Common misconceptions.

"Available means computed on some path." That is a may property; availability is must.
"An expression whose operands have the same values is available." Availability is defined by the absence of reassignment, not by equal values.
"Global CSE replaces the later evaluation by the variable of the earlier one." That is wrong if that variable is reassigned in between; a fresh temporary is used.

GATE examination perspective

Is $x \mathbin{op} y$ available at a given point? Check every path for an evaluation not followed by an operand assignment.
Compute $e\_gen$ , $e\_kill$ , IN and OUT. Work on a small flow graph, intersecting at joins and initialising to $U$ .
Which expressions can be eliminated. Also consider what the code looks like after introducing a temporary.
Loops that redefine an operand. An evaluation just before the loop does not make the same expression available at the loop header if the loop body changes an operand (Example 3).
Hidden kills. Calls, pointer stores and array stores can kill an expression without naming its operands.
Local versus global. DAG for one block; available expressions for the flow graph.
Distinguish the classic analyses. Available expressions (forward, intersection) versus reaching definitions (forward, union) versus liveness (backward, union).

Summary

$x \mathbin{op} y$ is available at $p$ if every path to $p$ evaluates it with no later assignment to $x$ or $y$ .
$IN[B] = \bigcap OUT[pred]$ , $OUT[B] = e\_gen_B \cup (IN[B] - e\_kill_B)$ , $OUT[\text{entry}] = \emptyset$ , other OUTs start at $U$ .
Example 1: at $B_4$ , $x * y$ is available and $x + y$ is not; $e = x * y$ becomes $e = u_1$ with $u_1$ set in $B_1$ and $B_3$ .
Example 2: starting from $\emptyset$ loses the availability of $x + y$ around a loop.
Example 3: $IN[B_2] = \emptyset$ because the back edge brings a changed $a$ ; $d = a + b$ after the loop reuses $B_2$ 's value.
Global CSE introduces a temporary at every reaching evaluation, then copy propagation cleans up.

Local Optimisation and DAG Representation of Basic Blocks: prerequisite. Common subexpressions inside one block.
Data-Flow Analysis Framework: prerequisite. The forward-intersection framework that available expressions instantiates.

Common Subexpression Elimination

Introduction

Prerequisites

Core concepts

How it works

Computing $e\_gen$ and $e\_kill$ within a block

Example 1: one expression available, one not

The global CSE transformation

Example 2: why the initial value is $U$

Example 3: a loop that redefines an operand

What else kills an expression

Local and global CSE together

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

How it works

Computing e_gene\_gene_gen and e_kille\_kille_kill within a block

Example 1: one expression available, one not

The global CSE transformation

Example 2: why the initial value is UUU

Example 3: a loop that redefines an operand

What else kills an expression

Local and global CSE together

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Computing $e\_gen$ and $e\_kill$ within a block

Example 2: why the initial value is $U$