Loop Transformations

This is the first of a blog series to dive into the loop transformations that are necessary for an automatic parallelizing compiler.

Resources

Loop transformations https://homes.luddy.indiana.edu/achauhan/Teaching/B629/2006-Fall/LectureNotes/27-loop-transformations.html

https://www.cse.iitk.ac.in/users/swarnendu/courses/autumn2020-cs610/loop-transformations.pdf

Transformation Type

• Unimodular transformation

  • Transformation matrix A has integral components and $

    det(A)

    =1$

  • Properties
    • The product of two unimodular matrices is unimodular
    • The inverse of a unimodular matrix is unimodular
  • Lemma: all combination of unimodular transformation is a compound unimodular transformation

Loop Interchange

Exchange the inner loop and outer loop.

Loop Permutation

A generalization of loop interchange for beyond two loops.

Loop Reversal

Reverse the iteration space of one loop. $[0-N]$ becomes $[N-0]$

Loop Skewing

“Skew” the loop nest to iterate in a different (e.g, diagonal) way so one of the loop level can be parallelized.

Loop Inversion

Transform a while loop into a if-do-while loop. Good for pipelining and loop-invariant code motion

Loop Peeling

Get the first couple of loop iterations outside of the loop.

Loop Splitting

Split out several iteration of the loop as sequential code, and the rest into multiple loop bodies.

Loop Alignment

Adjust one or more statement so the loop-carried dependence become intra-iteration dependence.

Loop Tiling (Blocking/Strip-Mine and Interchange/Chunking)

Partition the loop iteration space into smaller chunks. To improve the cache performance or for parallelization.

Loop Fusion (Jamming)

Inverse of loop distribution. Sometimes used to increase the granularity of the loop after distribution.

Loop Fission (Distribution)

Break the loop body and separate a loop into several ones.

Loop Unrolling (Unwinding)

Combine several iterations of a loop into one loop body. Reduce the number of iterations. Straight-line code optimizations.

Scalar Expansion

Break a scalar operation $T=T+xxx$ to an array operation $T[i]=T[i-1]+xxx$. Almost like privatization.

Dependence

What is a dependence that can be broken by loop rotation?

for i in [0..N] {
    res = a[i-1];
    a[i] = cos[i];
}

while node {
    load(node->value);
    node = node->next;
}

Ziyang Xu

6th year Ph.D. student @ Liberty Research Group, Princeton University

Tweet Share