Constant Folding

Constant folding eliminates entire arithmetic operations from the runtime execution graph. For example, an expression like (batch_size * 32) / 8 where batch_size=64 is computed once during compilation, replacing the runtime calculation with the constant value 256. This directly reduces the number of floating-point operations (FLOPs) the NPU must execute, freeing computational units for dynamic, data-dependent calculations.

By collapsing subgraphs of constant operations into single constant nodes, the compiler produces a leaner, more optimized intermediate representation (IR). This simplification enables more effective application of subsequent optimization passes, such as common subexpression elimination (CSE) and dead code elimination (DCE), by removing unnecessary nodes that can obscure optimization opportunities.

Folding constant expressions allows the compiler to statically determine the exact size of resulting tensors. This enables precise static memory planning, where the compiler can pre-allocate buffers for all intermediate tensors at compile time. Knowing that a tensor shape is fixed (e.g., [256, 128]) allows for optimal buffer reuse strategies, reducing peak memory usage and eliminating runtime allocation overhead.

A graph with folded constants presents a cleaner structure for the graph fusion pass. Operations that become simple element-wise broadcasts or scalar additions after folding are prime candidates for fusion into adjacent, more complex kernels. This reduces kernel launch overhead and minimizes data movement between global and shared memory on the NPU, which is often a major performance bottleneck.

By moving computation from runtime to compile time, constant folding removes variable-latency arithmetic operations from the critical execution path. This leads to more predictable and deterministic inference latency, a critical requirement for real-time and embedded AI applications. The execution time of the folded graph is less susceptible to fluctuations caused by data-dependent control flow that has been resolved at compile time.

Constant folding acts as an enabler for other sophisticated compiler techniques:

• Propagates constants for static shape inference, allowing the compiler to reason about tensor dimensions throughout the graph.
• Reveals opportunities for algebraic simplification (e.g., x * 1 → x).
• Allows strength reduction, where expensive operations are replaced with cheaper equivalents (e.g., x * 2 → x + x or x << 1). These cascading benefits collectively contribute to a highly optimized final binary.

Common Subexpression Elimination is a compiler optimization that identifies and eliminates redundant calculations of identical expressions within a computational graph. It analyzes the dataflow to find subgraphs that compute the same value and replaces all but one instance with a reference to a single stored result.

• Key Mechanism: The compiler builds a hash of expression trees. Identical hashes indicate a common subexpression.
• Interaction with Constant Folding: CSE often creates new opportunities for constant folding by consolidating computations, which may then be evaluated at compile time if all inputs are constant.
• Example: In the expression (a * b) + (a * b) / c, the subexpression (a * b) is computed twice. CSE computes it once, stores it in a temporary variable t0, and rewrites the expression as t0 + t0 / c.

Dead Code Elimination is a compiler pass that identifies and removes code that does not affect the final output of a program. In a neural network graph, this includes operations whose outputs are never consumed by any path leading to a graph output.

• Prerequisite: Requires precise dataflow analysis and often depends on optimizations like constant folding and constant propagation to reveal which branches or operations are truly unreachable.
• Impact on NPUs: Removing dead code reduces kernel launch overhead, decreases binary size, and frees up valuable on-chip memory and compute resources for essential operations.
• Example: If constant folding evaluates a conditional to always be false, the entire 'false' branch and any operations solely within it become dead code and are eliminated.

Static Single Assignment is a property of a compiler's Intermediate Representation (IR) where each variable is assigned exactly once. It is a foundational representation that enables powerful and simpler dataflow analyses, which are prerequisites for many advanced optimizations.

• Role in Constant Propagation/Folding: SSA form makes it trivial to track how constant values flow through the graph. If the single assignment to a variable is a constant, then all uses of that variable can be replaced with that constant (constant propagation), often leading to further constant folding.
• Compiler Use: Most modern ML compilers (like TVM's Relay, XLA, MLIR) use an SSA-based IR to perform optimizations cleanly and efficiently.

Peephole Optimization is a low-level compiler technique that examines short, consecutive sequences of instructions (or IR operations) and replaces them with more efficient sequences without changing semantics. It acts as a final, pattern-based cleaning pass.

• Relationship to Constant Folding: Constant folding is a classic and common type of peephole optimization. The 'peephole' might see a sequence like load_const 5, load_const 3, add and replace it with a single load_const 8 instruction.
• Scope: Operates on a very local window of the code, making it fast and predictable. It targets inefficiencies introduced by earlier transformation passes or inherent in the IR.
• NPU Example: Replacing a pattern of operations that implement a simple activation (like max(x, 0)) with a single, hardware-specific intrinsic call for ReLU.

Graph Canonicalization is a compiler transformation that rewrites a computational graph into a standard, simplified, and predictable form. It eliminates syntactic variations that represent the same semantic operation, ensuring subsequent optimization passes behave consistently.

• Purpose: Creates a uniform foundation for pattern matching in other passes like constant folding, CSE, and fusion. For example, it ensures Add(A, B) and Add(B, A) are represented identically if addition is commutative.
• Process: Involves sorting commutative operation inputs, flattening nested structures, and replacing compound operations with their canonical decomposed forms (or vice-versa).
• Benefit: Makes the compiler more reliable and deterministic, as optimizations don't miss patterns due to irrelevant syntactic differences.

Constant Propagation is a compiler analysis that tracks the flow of constant values through variables and operations in a program. When it determines that a variable or operation input will always have a known constant value at runtime, it substitutes that value.

• Symbiosis with Constant Folding: These are sister optimizations that feed each other. Constant propagation replaces variables with constants, creating new opportunities for constant folding (e.g., now an operation has all constant inputs). Conversely, constant folding creates new constants that can be propagated further.
• Dataflow Analysis: Typically implemented as an iterative algorithm that traverses the graph until a fixed point is reached, propagating constants along edges until no more changes occur.
• Critical for Specialization: Enables the creation of highly specialized graph variants where configuration parameters (like batch size, hidden dimensions) are baked in as constants, allowing for aggressive downstream optimizations.