Go to the previous, next section.

Unimodular Transforms

A unimodular transformation is a transformation of the loops' iteration space that can be represented as a unimodular matrix. A unimodular matrix is a square, integer matrix where the absolute value of the determinant is 1.

The method unimodular_transform in the loop_transform class is used to generate unimodular loop transformations. This method takes a unimodular integer_matrix as a parameter. It returns a boolean to indicate if the transformation was successful. If a non-skew unimodular transformation (e.g. interchange) is specified, then the loops must be perfectly nested.

The routine transforms the bounds and body of the code, but the index names are left in place. For example, given the code:

for (i = 0; i <= N; i++) {
    for (j = i+1; j <= N; j++) {
        A[i][j] = ...;
    }
}

If we apply loop interchange, specified by the following unimodular matrix:

[ 0 1 ]
[ 1 0 ]

The resulting code is:

for (i = 0; i <= N; i++) {
    for (j = 1; j <= i-1; j++) {
        A[j][i] = ...;
    }
}

Note that the position of tree_fors nodes in SUIF code is not changed. In particular, any annotations attached to a tree_for remain with that tree_for after the transformation.

For another example, given the following code:

for (i = 0; i <= M; i++) {
    for (j = 0; j <= N; j++) {
        A[j+1] = .333 * (A[j] + A[j+1] + A[j+2]);
    }
}

If we skew the loops using the unimodular matrix:

[ 1 0 ]
[ 1 1 ]

The resulting code is:

for (i = 0; i <= M; i++) {
    for (j = i; j <= N+i; j++) {
        A[j-i+1] = .333 * (A[j-i] + A[j-i+1] + A[j-i+2]);
    }
}

Go to the previous, next section.