Linear loop transforms are a memory hierarchy optimization that transform loops for better data locality and to remove dependencies. The algorithms being implemented are based on Wei Li's work on non-singular loop transforms. Non-singular transforms include all of the unimodular transforms (skewing, interchange, and reversal), plus scaling.
Transforms are specified as a matrix that is applied to a given loop nest.
Example matrices:
<?plugin TeX2png text="$\left(\begin{array}{cc} 1 & 0\\ 0 & 2 \end{array}\right)$"?> is a scaling matrix
<?plugin TeX2png text="$\left(\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right)$"?> is a interchange matrix
<?plugin TeX2png text="$\left(\begin{array}{cc} 1 & 0\\ 0 & -1 \end{array}\right)$"?> is a reversal matrix
<?plugin TeX2png text="$\left(\begin{array}{cc} 1 & 1\\ 1 & 0 \end{array}\right)$"?> is skewing matrix
Work can be see in [gccsource:lambda.h], [gccsource:lambda-mat.c], [gccsource:lambda-code.c], and [gccsource:tree-loop-linear.c]