Common Subexpression Elimination (CSE) is a classic compiler optimization that removes redundant computations by identifying repeated expressions whose operands remain unchanged between evaluations. This reduces execution time and computasional overhead.

Consider the following code:

int temp = b * c;
int a = b * c + g;
int d = b * c + e;

Since b * c is computed once and stored in temp, and neither b nor c changes before its reuse, the subsequent occurrences can be replaced with temp:

temp = b * c;
a = temp + g;
d = temp + e;

CSE is categorized based on scope: local CSE operates within a single basic block, while global CSE spans multiple blocks across a control flow graph (CFG).

Local Value Numbering (LVN)

LVN is a local CSE technique that assigns a unique "value number" to each expression in a basic block using a hash table. The algorithm processes instructions sequentially:

1. For an operation like x op y, look up value numbers for x and y.
2. If either operand lacks a value number, assign one.
3. Compute a combined value number for VN(x) op VN(y).
4. If this composite value number already exists, replace the current expression with the previously computed result; otherwise, record it.

This ensures each unique computation is performed only once per block.

Lazy Code Motion (LCM)

LCM is a global CSE method that uses data-flow analysis to hoist expressions to their earliest safe point and then sink them as late as possible without introducing redundancy. It relies on three key analyses:

Available Expressions

An expression e is available at a program point if all paths leading to it have evaluated e, and none of its operands have been redefined since. The set AvailIn(n) for block n is computed as:

$$ AvailIn(n) = \bigcap_{m \in \text{preds}(n)} \left( \text{DEExpr}(m) \cup (AvailIn(m) \cap \overline{\text{ExprKill}(m)}) \right) $$

• DEExpr(m): expressions defined in m and not killed before its exit.
• ExprKill(m): expressions invalidated due to operand redefinition in m.

Anticipated (Predictable) Exprestions

An expression is anticipated at a point if it will be used along all paths to the exit and remains valid until then. The backward-propagated set AntOut(n) is:

$$ AntOut(n) = \bigcap_{m \in \text{succ}(n)} \left( \text{UEExpr}(m) \cup (AntOut(m) \cap \overline{\text{ExprKill}(m)}) \right) $$

• UEExpr(m): expressions used in m before any operand is redefined.

Earliest and Latest Placement

The earliest placement edge (i, j) for expression e is where e must be computed to ensure availability without redundancy:

$$ \text{Earliest}(i,j) = \text{AntIn}(j) \cap \overline{\text{AvailOut}(i)} \cap (\text{ExprKill}(i) \cup \overline{\text{AntOut}(i)}) $$

After determining earliest points, delayed placement pushes computations down as far as possible using forward analysis:

$$ \text{LaterIn}(j) = \bigcap_{i \in \text{preds}(j)} \text{Later}(i,j) $$ $$ \text{Later}(i,j) = \text{Earliest}(i,j) \cup (\text{LaterIn}(i) \cap \overline{\text{UEExpr}(i)}) $$

Finally, insertion and deletion sets guide code rewriting:

• Insert(i,j) = Later(i,j) - (LaterIn(j) ∩ ¬UEExpr(j))
• Delete(j) = UEExpr(j) ∩ ⋃_{i ∈ preds(j)} Insert(i,j)

Insertions occur at block boundaries or via new blocks on critical edges; deletions remove now-redundant computations.

CSE in AI Compilers

AI compilers apply CSE over computation graphs rather than linear IR. Identical subgraphs—sequences of operations with the same structure and inputs—are merged into a single instance. For example, if two operators Op3 and Op4 both depend on the subgraph {Op1 → Op2}, the compiler redirects both to share the same Op2 output. Redundant subgraphs are later removed via dead code elimination.

Example: TensorFlow’s Approach

1. Perform a reverse post-order traversal to process nodes after their inputs.
2. Compute a structural hash for each op node using attributes like input count, types, and op kind.
3. Maintain a hash-to-node map. On encountering a duplicate hash, reroute consumers to the existing node; the duplicate is eliminated later.

Example: Go Compiler (SSA-based)

Go’s SSA-form compiler uses equivalence partitioning:

1. Coarse partitioning: Group values by op type, data type, etc.
2. Fine partitioning: Within groups, sort by operand value numbers (accounting for commutativity, e.g., a + b == b + a). Split groups where operand sequences differ.
3. Assign equivalence IDs iteratively until stable.
4. Replace dominated duplicates: only substitute if the defining block dominates the use site.

This approach leverages SSA’s explicit data flow and φ-functions to safely eliminate redundancies across control paths.