Constant Propagation

Constant propagation is a classic forward data flow analysis problem. The compiler analyzes the program's control flow graph (CFG), propagating known constant values from variable definitions (assignments) forward along possible execution paths to their uses.

• Initialization: Variables are typically initialized to a special lattice value like ⊤ (top), meaning "unknown" or "could be any value."
• Transfer Function: At each assignment statement (e.g., x = 5), the compiler updates its knowledge state for that variable.
• Meet Operator: At points where control flow merges (e.g., after an if statement), the compiler combines information from incoming paths. If a variable has different constant values from different paths, its value becomes ⊥ (bottom), meaning "not a constant."

The primary power of constant propagation is not just in replacing variables with literals, but in unlocking powerful secondary optimizations.

• Constant Folding: Expressions composed entirely of constants (e.g., 3 + 5 * 2) can be evaluated at compile time.
• Dead Code Elimination: Branches conditioned on constants that are always false (if (false) { ... }) can be entirely removed, along with the unreachable code inside.
• Strength Reduction: Operations can be replaced with cheaper equivalents (e.g., x * 2 becomes x << 1).
• Improved Alias Analysis: Knowing a pointer holds a constant address can simplify memory dependency analysis.

Constant propagation operates at different scopes with varying complexity and payoff.

• Intraprocedural: Analyzes and optimizes within a single function or procedure. This is common, fast, and forms the basis of most implementations.
• Interprocedural (IPA): Extends the analysis across function boundaries. If a function is called with constant arguments, those constants can be propagated into the function body. This is more powerful but requires whole-program analysis or sophisticated link-time optimization (LTO) and incurs higher compile-time cost.

Sparse Conditional Constant Propagation (SCCP) is a highly efficient and precise algorithm that combines constant propagation with unreachable code detection.

• Sparse: It operates on the SSA (Static Single Assignment) form of the program, tracking values directly instead of exhaustively analyzing every program point, which drastically improves speed.
• Conditional: It uses the CFG to understand how conditional branches affect constant values. It can prove a branch is always taken based on a constant condition, prune the unreachable path from the CFG, and continue propagating constants in the remaining live code.
• This makes SCCP strictly more powerful than simple constant propagation, as it discovers constants during the optimization by simplifying the program structure.

Propagating constants through memory operations and pointers is a significant challenge that limits the optimization's scope.

• Memory Stores: A store through a pointer (e.g., *p = 10) can potentially change the value of any variable whose address has been taken. Conservative analysis must assume such a store could change any variable, limiting propagation.
• Pointer Analysis: To safely propagate constants via pointers, the compiler needs accurate alias analysis to determine if two pointers can refer to the same memory location. Without this, optimizations may be missed or, worse, incorrect code may be generated.
• This is a key reason why constants declared with const and stored in read-only memory are easier for the compiler to reason about and optimize.

Within the context of Neural Processing Unit (NPU) compilation and kernel fusion, constant propagation plays a vital role in enabling aggressive optimizations.

• Fusion Parameter Specialization: When fusing kernels (e.g., convolution + bias + ReLU), many parameters like filter sizes, strides, or activation function types are often compile-time constants. Propagating these allows the fused kernel to be specialized, eliminating conditional checks and enabling optimal loop unrolling and vectorization.
• Memory Access Simplification: Constant array indices or loop bounds allow the compiler to precisely analyze memory access patterns, enabling optimizations like perfect loop nesting and memory coalescing for the fused kernel.
• Dead Code Pruning in Fused Graphs: It helps eliminate entire branches of a computational graph that are not used for a specific model configuration, resulting in a leaner, faster fused kernel.

Constant folding is the compile-time evaluation of expressions whose operands are all constants, replacing the expression with its computed result. This is a direct enabler and beneficiary of constant propagation.

• Example: The expression int x = 3 * 4 + 5; is folded to int x = 17; at compile time.
• Impact: Eliminates runtime arithmetic operations, reduces instruction count, and can create new constants for further propagation.

Dead code elimination removes code that does not affect the program's output. Constant propagation often creates dead code by making control flow decisions deterministic or rendering variable assignments unused.

• Process: After propagation, an if (false) { ... } block or a variable assigned but never read can be safely deleted.
• Benefit: Reduces binary size, minimizes memory accesses, and eliminates unnecessary instructions, freeing hardware resources for critical computation.

Common subexpression elimination identifies and computes redundant identical expressions once, storing the result in a temporary variable for reuse. Constant propagation simplifies expressions, making more subexpressions identical and thus eligible for CSE.

• Mechanism: If a = x * 5 and b = x * 5 appear, CSE computes t = x * 5 and sets a = t; b = t.
• NPU Relevance: Crucial for reducing redundant computation in unrolled loops and complex tensor operations, preserving arithmetic units for essential work.

Copy propagation is a simpler form of constant propagation that tracks assignments of the form x = y and replaces subsequent uses of x with y. It simplifies the data flow graph, enabling further optimizations.

• Difference from Constant Propagation: Propagates variable names, not just literal values.
• Synergy: Often runs iteratively with constant propagation. If y is later discovered to be a constant, the propagated copy enables the constant to be substituted directly.

Sparse conditional constant propagation is an advanced, iterative dataflow algorithm that combines constant propagation, constant folding, and dead code elimination. It can discover constants in branches by tracking control flow paths.

• Key Strength: It can determine that a variable is constant only along certain execution paths, enabling more aggressive optimization than simple forward propagation.
• Use Case: Highly effective for optimizing computational graphs with conditionals that become static based on model hyperparameters or input shapes.

Interprocedural constant propagation extends the analysis across function boundaries. It propagates constant arguments and global values into function bodies, enabling optimizations within called functions.

• Scope: Operates on the whole program or compilation unit, not just a single function.
• NPU Application: Essential for optimizing library kernels and runtime functions where launch parameters (e.g., fixed tensor dimensions, activation types) are known at compile time for a specific model.