Common Subexpression Elimination (CSE)

CSE operates on the principle of computational redundancy. It scans the computational graph to find subexpressions—sequences of operations—that produce identical results. When a duplicate is found, the compiler replaces all subsequent instances with a reference to the first computed value. This transforms the graph from a structure with repeated calculations into one with shared intermediate results, directly reducing the number of floating-point operations (FLOPs) executed at runtime.

The effectiveness of CSE depends on its scope of analysis:

• Local CSE: Operates within a single basic block or a small, contiguous sequence of operations. It is fast and common in early optimization passes.
• Global CSE: Analyzes the entire function or computational graph, tracking values across control flow boundaries (like loops and conditionals). This is more powerful but requires sophisticated dataflow analysis.
• Inter-Procedural CSE: Extends analysis across function boundaries, potentially inlining functions to expose more redundancy. This is complex and often used in link-time optimization (LTO).

CSE is heavily influenced by the graph's Intermediate Representation (IR). In an SSA (Static Single Assignment) form, where each variable is assigned once, value identity is explicit, making CSE more straightforward. The compiler often performs CSE after graph canonicalization, which standardizes operator forms (e.g., rewriting (a + b) and (b + a) as identical if addition is commutative), ensuring maximum redundancy is detected. It is a prerequisite for many subsequent optimizations like constant folding and dead code elimination.

While primarily beneficial, CSE introduces trade-offs that compilers must balance:

• Increased Memory Pressure: Storing a computed value for reuse consumes register or stack memory. Aggressive CSE can increase register pressure, potentially causing spills to slower memory.
• Instruction Scheduling Impact: Creating a single, shared computation point may lengthen a critical path if the value is needed early by multiple consumers.
• Side Effects and Purity: CSE can only be applied to pure functions—operations without side effects (e.g., sin(x), a + b). It cannot be applied to stateful operations like random number generation or memory writes.

For Neural Processing Units (NPUs), CSE is critical but interacts uniquely with hardware:

• Fusion Opportunities: Eliminating a redundant subgraph may remove a candidate for kernel fusion, as the operations are no longer adjacent. The compiler must evaluate the cost-benefit of CSE vs. fusion.
• Precision and Rounding: On hardware using mixed-precision (e.g., FP16, INT8), reusing a value stored in a lower-precision register may propagate rounding errors differently than recomputing in higher precision.
• Scheduling for Parallelism: On massively parallel NPUs, recomputing a value in two separate processing elements (PEs) might be faster than broadcasting it from a single source, depending on data movement costs.

Consider the expression y = (a*b) + (a*b) + c. A naive computation performs (a*b) twice.

Original Computation Graph: MUL1 = a * b MUL2 = a * b ADD1 = MUL1 + MUL2 y = ADD1 + c

After CSE: MUL1 = a * b // The single, common subexpression ADD1 = MUL1 + MUL1 // Reuse the result y = ADD1 + c

The optimization reduces one MUL operation. In a neural network, this pattern occurs with repeated weight multiplications or activation function applications across identical tensor slices.

A compiler optimization that evaluates expressions consisting solely of compile-time constants during compilation, replacing them with their computed result. This eliminates runtime computation entirely.

• Example: An expression like (2.0 * 3.14) + 1.0 is replaced with the constant 7.28 in the compiled graph.
• Interaction with CSE: Often runs before CSE, as folding constants can create new opportunities to identify identical subexpressions.

A compiler pass that identifies and removes code that does not affect the program's final output. This includes operations whose results are never consumed, or variables that are never read.

• Purpose: Reduces binary size, execution time, and memory footprint.
• Relation to CSE: CSE can sometimes create 'dead' code—values that are computed and stored but then never used if all references to the original subexpressions are replaced. A subsequent DCE pass is required to clean this up.

A compiler optimization that merges multiple adjacent operators or nodes within a computational graph into a single, compound kernel. This is a key strategy for NPU acceleration.

• Primary Benefit: Drastically reduces kernel launch overhead and minimizes costly intermediate memory writes and reads between operators.
• Contrast with CSE: While CSE targets identical expressions (often within a single operator or across similar ops), fusion targets different but adjacent operators to create a new, more efficient monolithic operation.

An intermediate representation (IR) property where each variable is assigned exactly once. This form is foundational for modern compiler optimizations.

• Key Advantage: Simplifies dataflow analysis, making it trivial to see where values are defined and used.
• Enabler for CSE: CSE is far more straightforward to implement on an SSA-form IR. Identifying identical expressions that produce the same value is simplified because each value has a unique definition point.

A low-level, local optimization that examines short sequences of instructions (a 'peephole') and replaces them with faster or shorter sequences without changing semantics.

• Scope: Operates on a very localized, instruction-by-instruction level, often in the compiler backend.
• Comparison to CSE: CSE is a global optimization that analyzes the entire graph or function. Peephole optimizations are local patterns (e.g., replacing x * 2 with x << 1). They can be applied after CSE to further optimize the generated low-level code.

A compiler pass that allocates memory buffers for all tensors in a computational graph, aiming to minimize peak memory usage through intelligent reuse and in-place operations.

• Critical for Edge AI: Essential for deploying models on memory-constrained NPUs and edge devices.
• Synergy with CSE: CSE directly reduces the number of unique intermediate tensors that need to be allocated. By computing a value once and reusing it, memory planning has fewer buffers to manage and can achieve a lower overall peak memory footprint.