Common Subexpression Elimination (CSE)

The most direct benefit of CSE is the elimination of redundant arithmetic operations. By identifying identical expressions computed multiple times, the compiler computes the value once, stores it in a temporary register or variable, and reuses it. This directly reduces:

• Instruction count in the generated code.
• Execution cycles spent on floating-point or integer operations.
• Power consumption, especially critical in embedded systems and NPUs where energy efficiency is paramount.

For example, in a loop computing a = x*y + z; b = x*y - z;, the subexpression x*y is calculated once, halving the required multiplications.

CSE promotes better utilization of the processor's memory hierarchy. The result of a common subexpression is typically held in a fast storage location:

• Register Allocation: The computed value is kept in a CPU or NPU register, providing near-zero latency access for subsequent uses.
• Cache Efficiency: By reducing the number of distinct memory loads for the same data, it improves cache hit rates.
• Reduced Register Pressure: While it uses a register for the temporary, it often saves more registers by eliminating the need to reload operands for the redundant calculation. This is crucial for NPUs with limited register files per core.

CSE often creates opportunities for other compiler passes by simplifying the Intermediate Representation (IR).

• Constant Folding & Propagation: If the common subexpression evaluates to a constant, CSE makes this constant obvious, allowing it to be propagated.
• Dead Code Elimination: By consolidating computations, it can reveal calculations whose results are no longer needed.
• Loop-Invariant Code Motion: CSE can help identify expressions that are invariant within a loop, which can then be hoisted outside the loop body. This synergistic effect creates a compounding performance benefit.

In Neural Processing Unit compilation, CSE is vital for maximizing throughput and minimizing latency.

• Kernel Fusion Context: When fusing kernels (e.g., convolution + bias + ReLU), CSE identifies redundant operations across the original kernel boundaries in the fused code.
• Memory Bandwidth Reduction: NPUs are often memory-bandwidth constrained. By eliminating redundant loads of weight tensors or activation maps, CSE reduces traffic to high-bandwidth memory (HBM).
• Tensor Core Utilization: For operations targeting specialized units like Tensor Cores, ensuring identical matrix blocks are not recomputed saves highly efficient compute cycles.

While highly beneficial, CSE requires careful implementation to avoid negative impacts.

• Register Pressure vs. Compute Trade-off: Storing a result consumes a register. Aggressive CSE can cause register spilling if too many temporaries are live simultaneously, hurting performance more than the saved computation.
• Precision in Floating-Point: Reusing a computed floating-point value is not strictly equivalent to recomputing it due to non-associative operations and fused multiply-add (FMA) instructions. Compilers must respect language semantics (e.g., -ffp-contract in C/C++).
• Scope Analysis: Effective CSE must correctly analyze the scope and lifetime of expressions, ensuring the computed value is still valid (i.e., its operands haven't been modified) at the point of reuse.

CSE interacts closely with several sibling optimizations in the kernel fusion and optimization group.

• Loop-Invariant Code Motion: Often works before CSE, moving invariant expressions out of loops, after which CSE can eliminate duplicates of those hoisted expressions.
• Constant Propagation: Feeds into CSE; once a variable is known to be constant, expressions using it become candidates for elimination.
• Kernel Fusion: Creates a larger code region where CSE can find redundancies that were previously hidden across separate kernel boundaries.
• Dead Code Elimination: Runs after CSE to clean up any original computations that were made redundant by the elimination process.

At the highest level, CSE operates on the computational graph representation of a neural network. The compiler analyzes the Directed Acyclic Graph (DAG) to find identical subgraphs or tensor operations.

• Example: In a transformer block, the same layer normalization operation might be computed separately for queries, keys, and values before attention. CSE identifies this and computes the normalization once, reusing the result.
• Impact: Eliminates redundant forward passes of identical sub-networks, directly reducing FLOPs in the execution graph. This is critical in models with repeated structures, such as Vision Transformer (ViT) patches or recurrent cell unrolling.

CSE is a prerequisite and enabler for effective kernel fusion. Before fusing multiple operations into a single kernel, the compiler eliminates common subexpressions within the fusion candidate set.

• Process: When fusing a sequence like Conv2D → BiasAdd → ReLU, the compiler first checks for repeated calculations of the convolution's input padding or stride offsets. These intermediate address calculations are hoisted and computed once.
• Benefit: Reduces register pressure and instruction count within the fused kernel, allowing more resources for the core computation. This prevents the fused kernel from becoming bloated with duplicate address arithmetic.

Within a single computational kernel, CSE is applied during loop nest optimization. The compiler's scalar evolution analysis identifies invariant expressions inside loops.

• Classic Example: In a matrix multiplication kernel C[i][j] += A[i][k] * B[k][j], the address calculation for A[i][k] is invariant with respect to the inner j loop. CSE moves this calculation to an outer loop.
• AI/ML Specific: In a depthwise convolution, the same filter weight is used across all spatial positions for a given channel. CSE loads the weight into a register once per channel, rather than for each pixel calculation.
• Interaction: Works synergistically with loop-invariant code motion (LICM) and strength reduction.

A major source of redundancy in optimized kernels is address arithmetic for multi-dimensional tensor accesses. CSE is aggressively used to compute base pointers and offsets once.

• Scenario: Accessing a 4D tensor [N, C, H, W] at position [n, c, h, w] requires computing a linear index: ((n * C + c) * H + h) * W + w. If this tensor is accessed multiple times in a loop with the same n, c, h indices but varying w, the partial calculation ((n * C + c) * H + h) * W is a common subexpression.
• Hardware Impact: Eliminating these redundant calculations reduces integer ALU pressure, freeing units for the core floating-point or matrix operations (e.g., Tensor Core instructions).

CSE works in tandem with constant propagation and constant folding. After constants are propagated, new opportunities for CSE often emerge.

• Workflow:
  1. Constant Propagation: Identifies that a model hyperparameter (e.g., epsilon=1e-5 in LayerNorm) is a compile-time constant.
  2. Constant Folding: Pre-computes expressions involving only constants (e.g., 1.0 / sqrt(variance + 1e-5)).
  3. CSE: If this folded constant expression appears in multiple normalization layers, it is computed once and reused.
• Result: Moves work from runtime to compile-time, generating a more efficient binary. This is especially valuable for deploying static graphs where model parameters are fixed.

Applying CSE in Just-In-Time (JIT) compilation for dynamic graphs (e.g., PyTorch eager mode, control flow) presents unique challenges.

• Problem: The full computation graph is not known statically. Redundant expressions may only become apparent at runtime based on input-dependent control flow.
• Solution: Advanced JIT compilers (like TorchInductor or XLA) use tracing to capture a concrete graph from a sample execution. CSE is then applied to this traced graph.
• Limitation: If the trace is not representative, CSE might incorrectly eliminate an expression that is not truly redundant for all inputs. This requires careful guard insertion to ensure correctness.
• Trade-off: Balances optimization aggressiveness with the overhead of guard checks and re-compilation.

Dead Code Elimination is a compiler optimization that removes code which does not affect the program's observable output. This includes:

• Unreachable code: Statements that can never be executed due to control flow.
• Dead stores: Computations whose results are never subsequently read.

While CSE eliminates redundant computations, DCE removes unnecessary ones entirely. They are often applied in sequence: CSE may create temporary variables that become dead if their single use is also eliminated, allowing DCE to clean up the leftover code. This reduces binary size and execution time.

Constant Propagation is an optimization that replaces variables known to have constant values with those literal values. Constant Folding is the subsequent evaluation of expressions involving only constants at compile time.

Example: int x = 5; int y = x * 2; becomes int y = 10;.

This optimization directly enables CSE. By propagating constants, the compiler can identify more expressions as being identical. For instance, after propagation, a * 5 and b * 5 might be seen as common subexpressions if a and b are found to hold the same value, leading to their elimination.

Loop-Invariant Code Motion is a transformation that moves computations whose values do not change across loop iterations (loop-invariant expressions) from inside a loop to just before the loop begins.

Mechanism:

• The compiler analyzes expressions within a loop body.
• If an expression's operands are constant or defined outside the loop, it is marked invariant.
• The computation is hoisted to the loop preheader.

This is a powerful form of CSE applied specifically to loops. It eliminates the redundant re-computation of the same value in every iteration, trading repeated computation for a single computation and potentially a register store.

Global Value Numbering is a sophisticated compiler analysis that determines when two computations are equivalent (value-identical) across an entire function or compilation unit. It assigns a unique value number to each computed expression.

How it relates to CSE:

• Local CSE works within a single basic block.
• GVN enables global CSE, identifying redundant expressions across different blocks and complex control flow paths.
• It is a more general and powerful technique that subsumes local CSE, also enabling optimizations like copy propagation and partial redundancy elimination.

Partial Redundancy Elimination is an advanced optimization that generalizes both CSE and Loop-Invariant Code Motion. It eliminates computations that are redundant on some, but not all, paths through the control flow graph.

The Problem PRE Solves: An expression may be computed multiple times on a hot loop path, but not on a cold initialization path. Naive hoisting might execute it unnecessarily on the cold path.

PRE's Solution: It strategically inserts computations (fills) at points in the CFG to make the redundancy complete, then performs elimination. This minimizes the total number of times an expression is executed, making it a critical optimization for performance-critical code.

When a compiler represents a program's basic block as a Directed Acyclic Graph (DAG), CSE becomes a natural and efficient process.

Process:

1. Each node in the DAG represents a distinct operator (e.g., +, *, load).
2. The children of a node are its operand values.
3. The compiler constructs the DAG, and identical expressions naturally map to the same node.

This representation makes redundancy explicit. Code generation then emits instructions for each unique DAG node, automatically eliminating all common subexpressions within that block. This is the canonical implementation of local CSE in modern compilers like LLVM.