Loop Fusion

Loop fusion enhances temporal locality by keeping data in fast cache or register memory across multiple operations. When two separate loops read and write the same array, the data must be loaded twice from slow main memory. Fusing the loops allows the intermediate result to be consumed immediately while still 'hot' in the cache.

• Example: A loop computing B[i] = A[i] * 2 followed by C[i] = B[i] + 1 requires writing and then reading array B. After fusion, the single loop computes C[i] = (A[i] * 2) + 1, eliminating the round-trip to memory for B.

This benefit directly decreases the instruction count and control flow complexity. Each loop has inherent overhead: initializing an induction variable, performing a conditional branch check each iteration, and incrementing the counter. Fusing N loops into one eliminates N-1 sets of this overhead.

• Impact: For loops with a small trip count (number of iterations) or lightweight loop bodies, this overhead can constitute a significant portion of total execution time. Elimination is especially valuable on NPUs where fine-grained kernel launch latency can be high.

Fusion minimizes the intermediate memory footprint of a computation. Without fusion, the full output tensor of the first loop must be allocated and stored before the second loop begins. Fusion computes and consumes values element-by-element, often allowing the intermediate result to reside only in a register or a small temporary buffer.

• Critical for NPUs: NPUs often have constrained on-chip SRAM (e.g., scratchpad memory). Reducing peak memory usage allows larger models or batch sizes to fit, or frees memory for other optimizations like double buffering.

A single, larger fused loop often presents a more substantial and contiguous parallel workload to the hardware scheduler. This can improve load balancing across NPU cores and increase instruction-level parallelism (ILP).

• Contrast: Two small, separate kernels may not fully utilize all compute units, leading to idle hardware. A fused kernel with more operations per iteration provides a richer set of instructions for the scheduler to issue concurrently. This also reduces synchronization points between kernels.

Loop fusion creates a larger, unified code block that exposes new opportunities for downstream compiler passes. These include:

• Common Subexpression Elimination (CSE): Identical computations from the original separate loops can now be found and computed once.
• Constant Propagation & Folding: Constants can be propagated across the fused operation sequence.
• Vectorization: A longer loop body with consistent memory access patterns is often more amenable to SIMD or vector unit optimization.
• Strength Reduction: Replacing expensive operations (like multiplication) with cheaper ones (like bit-shifts) across the combined computation.

Fusion is not always legal or beneficial. The compiler must perform dependency analysis to ensure transformations preserve program semantics. Key constraints include:

• Iteration Space Match: Loops must have the same bounds and step size.
• Data Dependencies: Fusion is illegal if it creates a loop-carried dependency that didn't exist before. For example, fusing loops where the second reads from an index written by the first in a later iteration (an anti-dependency) is prohibited.
• Profitability Heuristics: The compiler may decide not to fuse if the combined loop body becomes too large for the instruction cache, or if fusion inhibits other optimizations like loop unrolling.

Graph fusion is a higher-level compiler optimization that merges multiple adjacent operators or nodes within a computational graph into a single, compound kernel. While loop fusion operates on the low-level loop nests within a single kernel, graph fusion decides which operators to combine at the graph level.

• Primary Goal: Reduce kernel launch overhead and minimize intermediate memory accesses (tensor writes/reads).
• Example: Fusing a Convolution, Batch Normalization, and ReLU activation into one kernel.
• Relation to Loop Fusion: Graph fusion creates the opportunity for subsequent loop fusion within the generated compound kernel.

Loop tiling (or loop blocking) is a loop transformation that partitions a loop's iteration space into smaller blocks or tiles. This is often a prerequisite or complementary optimization to loop fusion.

• Primary Goal: Improve data locality and reuse within cache hierarchies (L1, L2, shared memory).
• Mechanism: Transforms loop nests to operate on sub-blocks of data that fit in faster memory.
• Synergy with Fusion: Tiling can make fused loops more effective by ensuring the working set of the combined loop fits in cache, preventing performance degradation from cache thrashing.

Common Subexpression Elimination is a compiler optimization that identifies and eliminates redundant computations of identical expressions.

• Primary Goal: Avoid repeated calculation of the same value.
• How it Works: The compiler detects identical expressions, computes the value once, stores it in a temporary variable, and reuses that variable.
• Relation to Loop Fusion: When loops are fused, new opportunities for CSE often arise within the combined loop body, as computations from the original separate loops may now be redundant. The compiler must apply CSE after fusion to realize these gains.

Operator reordering is a compiler pass that changes the execution sequence of independent operators in a computational graph.

• Primary Goal: Create adjacency between operators that are candidates for fusion (like loop or graph fusion) or to improve data locality.
• Constraint: Must respect the data dependencies of the original graph. Only independent operators can be reordered.
• Example: Moving a transpose operation earlier in the graph to enable the fusion of subsequent matrix multiplications. This reordering can create the 'adjacent loops with the same iteration space' required for loop fusion.

Kernel auto-tuning is an automated process that searches for optimal parameters for a kernel's implementation, such as tile sizes, unroll factors, and fusion decisions.

• Primary Goal: Find the configuration that delivers peak performance for a specific hardware target (NPU/GPU).
• Methodology: Uses empirical search (e.g., genetic algorithms, gradient-free search) to compile and benchmark many kernel variants.
• Role in Fusion: Auto-tuners often evaluate the performance impact of fusing vs. not fusing specific loops or operators, making the fusion decision data-driven rather than purely heuristic-based.

Memory planning is a compiler optimization pass that allocates memory buffers for tensors in a computational graph, aiming to minimize peak memory usage.

• Primary Goal: Reduce device memory footprint through buffer reuse and in-place operations.
• Key Technique: Liveness Analysis to determine when a tensor's memory can be safely overwritten.
• Critical Interaction with Fusion: Loop fusion directly reduces the number of intermediate tensors that need to be allocated in memory. Effective memory planning can further reuse the memory of fused-out tensors for other purposes, compounding the memory savings achieved by fusion.