Loop Fusion

Loop fusion eliminates the prologue and epilogue instructions of the fused loops, along with the associated branch and increment operations for each iteration. This directly reduces the total number of executed instructions. For deep loops or loops within hot code paths, this reduction in control flow overhead can yield significant performance gains, especially on architectures where branch prediction misses are costly.

This is the most significant benefit. By combining loops, intermediate results produced by the first loop can be consumed immediately by the second loop while the data is still in a fast memory hierarchy.

• Register Locality: Values can be kept in processor registers across the fused operations, avoiding spills to slower memory.
• Cache Locality: Data accessed by both loops may remain in the L1 or L2 cache, drastically reducing accesses to high-latency global memory (DRAM). Example: Fusing an element-wise multiplication loop with a subsequent summation loop keeps the multiplied value 'hot' for the addition.

A single, larger fused loop often presents more uniform and predictable work for the compiler's auto-vectorizer and parallelization engines.

• Vectorization: The combined loop body may expose longer sequences of contiguous, data-parallel operations amenable to SIMD or SIMT execution.
• Parallel Loop Scheduling: Runtime systems (e.g., OpenMP, TBB) incur less overhead when scheduling one large parallel loop versus multiple smaller ones, improving core utilization. This reduces the ratio of parallel region management overhead to useful computation.

Fusion minimizes traffic between the processor and main memory. Without fusion, the output of the first loop is written to memory, only to be immediately read back as input for the second loop. This store/load redundancy consumes precious memory bandwidth. Fusion bypasses this by keeping the data on-chip. In memory-bound applications—where performance is limited by the speed of data movement—this bandwidth saving directly translates to higher execution speed and lower power consumption.

Loop fusion creates new opportunities for downstream compiler passes by creating a larger, unified code block for analysis.

• Common Subexpression Elimination (CSE): Expressions computed in the first loop and used in the second can now be identified as common within the single loop body.
• Dead Store Elimination: Temporary arrays that only served to pass data between loops may be eliminated entirely.
• Constant Propagation & Folding: Constants can propagate more freely across the formerly separate loop boundaries. Fusion effectively lowers the abstraction barrier between sequential operations.

Loop fusion is not always applicable or beneficial. Compilers must perform legality and profitability analysis.

• Legality: Loops must have the same iteration space (start, stop, step) and no loop-carried dependencies that fusion would violate.
• Register Pressure: Fusing large loop bodies can increase live variable counts, potentially causing register spilling, which harms performance.
• Cache Behavior: If the fused loop's working set exceeds cache capacity, performance can degrade due to capacity misses. Thus, fusion is often applied as part of a broader loop nest optimization strategy.

A classic example where separate loops performing independent calculations on the same arrays are fused.

Before Fusion:

cCopy
for (int i = 0; i < N; i++) {
    C[i] = A[i] + B[i];
}
for (int i = 0; i < N; i++) {
    D[i] = C[i] * scale;
}

After Fusion:

cCopy
for (int i = 0; i < N; i++) {
    float temp = A[i] + B[i];
    D[i] = temp * scale;
}

• Key Benefit: The intermediate result C[i] is kept in a register (temp), eliminating a full write and read of array C to/from main memory or cache.
• Performance Impact: Reduces memory bandwidth pressure and loop control overhead by 50% for these operations.

Fusing a map-like operation with a subsequent reduction (like a sum) is highly effective.

Before Fusion:

cCopy
// Map: Compute squares
for (int i = 0; i < N; i++) {
    squares[i] = data[i] * data[i];
}
// Reduce: Sum the squares
float sum = 0.0f;
for (int i = 0; i < N; i++) {
    sum += squares[i];
}

After Fusion:

cCopy
float sum = 0.0f;
for (int i = 0; i < N; i++) {
    sum += data[i] * data[i];
}

• Key Benefit: Completely eliminates the allocation, writing, and reading of the temporary squares array.
• Memory Savings: Transforms an O(N) memory operation into an O(1) operation, crucial for large N.
• Common Use: Found in computations like variance, L2 norm, and dot products.

In signal or image processing, consecutive filters are prime candidates for fusion.

Scenario: Applying a blur then an edge detection kernel to an image. Before Fusion: Two separate passes over the image.

1. Loop over pixels to compute blurred image B.
2. Loop over B to compute edge image E.

After Fusion: A single pass computing edges directly from original pixels.

• Mechanism: The fused loop's body expands to compute the local blur for a pixel and immediately apply the edge detector to that intermediate value.
• Benefit: The intermediate blurred image B never exists in full in memory. Data stays in cache/registers.
• Challenge: Increases register pressure as more live variables are needed simultaneously. May conflict with other optimizations like tiling.

A foundational optimization in ML compilers for layers like activation functions.

Common Pattern: Linear layer followed by a non-linear activation (e.g., ReLU). Before Fusion (Two Kernels):

1. GEMM or MatMul kernel: Z = X * W + B
2. ReLU kernel: A = max(Z, 0)

After Fusion (One Fused Kernel):

• A single kernel computes A = max(X * W + B, 0).
• Impact: Eliminates the global memory round-trip for the large tensor Z.
• Extended to Operation Fusion: This is often called operator fusion or kernel fusion, where loops are fused at the granularity of tensor operators (convolution, bias add, activation).
• Framework Support: Performed automatically by compilers like XLA, TVM, and MLIR.

Understanding when not to fuse is critical. Loop fission (distribution) is the inverse transformation.

When Fusion May Hurt Performance:

• Excessive Register Pressure: Fusing large loop bodies may require more live variables than physical registers, causing register spilling to slower memory.
• Reduced Parallelism: A single fused loop may offer less independent work for parallelization compared to distributing work across multiple loops.
• Impedes Other Optimizations: A fused loop may have complex access patterns that prevent effective vectorization or tiling.

Compiler Heuristic: Modern compilers analyze trade-offs using cost models. They may:

• Fuse loops with low arithmetic intensity to improve data locality.
• Apply fission to loops with high register pressure to enable better instruction-level parallelism (ILP).
• Use profile-guided optimization (PGO) data to make informed decisions.

Not all adjacent loops can be fused. The compiler must prove the transformation is safe and semantics-preserving.

Key Requirements:

1. Identical Iteration Space: Loops must have the same bounds and stride. for(i=0;i<N;i++) can fuse with for(i=0;i<N;i++) but not with for(i=0;i<M;i++).
2. No Loop-Carried Dependencies: The first loop must not write to a variable read in the second loop's later iterations (a true dependency).
   • Fusible: A[i]=...; B[i]=A[i]; (flow dependency within same iteration).
   • Not Fusible: A[i]=...; B[i]=A[i-1]; (dependency crosses iterations).
3. No Reverse Dependencies: The second loop must not write to a variable read by the first loop.

Compiler Analysis: Uses dependence analysis to construct a dependence graph. Loops are fused only if no violating dependencies exist between them.

Kernel fusion is a compiler optimization that merges multiple, separate computational kernels—often launched via separate API calls—into a single, larger kernel. This directly reduces the overhead of repeated kernel launch latency and eliminates unnecessary transfers of intermediate results between global memory and on-chip storage. It is a broader, often coarser-grained optimization than loop fusion, typically applied at the level of entire operator graphs in frameworks like TensorFlow or PyTorch.

• Primary Benefit: Minimizes launch overhead and global memory traffic.
• Scope: Applied across separate function/kernel boundaries.
• Example: Fusing a convolution, batch normalization, and ReLU activation into one monolithic kernel.

Loop fission (or loop distribution) is the inverse transformation of loop fusion. It splits a single loop containing multiple independent statements into two or more separate loops. This is performed to:

• Reduce register pressure: By separating statements, the compiler may require fewer live variables per loop, avoiding register spilling.
• Enable parallelization: Isolating a parallelizable statement in its own loop.
• Facilitate other transforms: Creating smaller loops that can then be individually targeted for fusion, tiling, or vectorization.

It highlights that fusion is not always beneficial; the compiler must analyze dependencies and resource constraints to decide between fission and fusion.

Loop tiling partitions a loop's iteration space into smaller blocks or tiles. The primary goal is to improve data locality by ensuring a tile of data fits into a faster, limited memory hierarchy (e.g., an NPU's shared memory or scratchpad).

• Mechanism: Adds extra levels of loops to iterate over tiles, then within tiles.
• Synergy with Fusion: Tiling is often applied before fusion. Fusing tiled loops can keep producer-consumer data within the same tile in fast memory, drastically reducing accesses to slow global memory.
• Key Parameter: Tile size, which is auto-tuned based on hardware memory capacities.

Loop interchange swaps the order of nested loops (e.g., changing from i-outer, j-inner to j-outer, i-inner). This transformation optimizes memory access patterns for multi-dimensional arrays.

• Goal: Enable memory coalescing on parallel architectures by ensuring consecutive threads access consecutive memory addresses.
• Impact on Fusion: When fusing nested loops, the chosen loop order dictates the stride of fused memory accesses. Interchange may be applied first to create a favorable, contiguous access pattern for the fused loop.
• Example: Transforming a column-major access pattern to row-major to match memory layout.

Common subexpression elimination is a compiler optimization that identifies and computes redundant expressions only once. Within loops targeted for fusion, CSE is crucial.

• Role in Fusion: When fusing loops, identical index calculations or address computations in the original separate loops become redundant in the fused body. CSE removes these duplicates.
• Benefit: Reduces arithmetic intensity and register usage in the fused kernel.
• Example: If two loops compute base_addr + i * stride, the fused loop computes it once and reuses the result.

Loop nest optimization is the overarching discipline that encompasses loop fusion, tiling, interchange, unrolling, and fission. LNO frameworks use polyhedral models or affine transformation theory to automatically explore a vast space of legal loop transformations.

• Objective: Find the optimal combination of transformations for a given computation kernel and hardware target.
• Process: Analyzes data dependencies, builds a transformation space, and uses a cost model (often related to the Roofline Model) to select the best sequence.
• Tools: LLVM's Polly, Pluto, and vendor-specific NPU compilers employ advanced LNO.