Loop interchange

In

array are accessed in the order in which they are present in memory, improving locality of reference

For example, in the code fragment:

for j from 0 to 20
  for i from 0 to 10
    a[i,j] = i + j

loop interchange would result in:

for i from 0 to 10
  for j from 0 to 20
    a[i,j] = i + j

On occasion, such a transformation may create opportunities to further optimize, such as automatic vectorization of the array assignments.

The utility of loop interchange

The major purpose of loop interchange is to take advantage of the

Cache misses

occur if the contiguously accessed array elements within the loop come from a different cache block, and loop interchange can help prevent this. The effectiveness of loop interchange depends on and must be considered in light of the cache model used by the underlying hardware and the array model used by the compiler.

In

FORTRAN programs store array elements from the same column together (a[1,1], a[2,1], a[3,1]), using column-major. Thus the order of two iteration variables in the first example is suitable for a C program while the second example is better for FORTRAN.^[1] Optimizing compilers

can detect the improper ordering by programmers and interchange the order to achieve better cache performance.

Caveat

Loop interchange may lead to worse performance because cache performance is only part of the story. Take the following example:

 do i = 1, 10000
   do j = 1, 1000
     a[i] = a[i] + b[j,i] * c[i]
   end do
 end do

Loop interchange on this example can improve the cache performance of accessing b(j,i), but it will ruin the reuse of a(i) and c(i) in the inner loop, as it introduces two extra loads (for a(i) and for c(i)) and one extra store (for a(i)) during each iteration. As a result, the overall performance may be degraded after loop interchange.

Safety

It is not always safe to exchange the iteration variables due to dependencies between statements for the order in which they must execute. To determine whether a compiler can safely interchange loops, dependence analysis is required.

References

^ "Loop interchange" (PDF). Parallel Programming Guide for HP-UX Systems. HP. August 2003.

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Use-define chain
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

Loop interchange

The utility of loop interchange

Caveat

Safety

See also

References

Further reading