Go to the previous, next section.

Loop Transformations

Both unimodular and tiling loop transformations are part of the class loop_transform. The loop_transform class contains an array of tree_for nodes. The tree_fors must be nested within one another in the SUIF code, and are ordered from outermost to innermost. For example, given the code:

for (i = 0; i < N; i++) {
        ...
    for (j = 0; j < N; j++) {
            ...
        for (k = 0; k < N; k++) {
                    ...
        }
    }
}

The loops array would contain pointers to the tree_for nodes for loops in the order i, j and then k.

In most cases the loops need not be perfectly nested. There can be simple instructions between loops, but non-nested loops are not allowed. For example, the loops in the following code are not nested within one another, and thus cannot be transformed:

for (i = 0; i < N; i++) {
        ...
    for (j = 0; j < N; j++) {
            ...
    }
    for (k = 0; k < N; k++) {
            ...
    }
}

In order to be able to calculate the bounds after transformation, the transform library requires that the bounds of the loops define a polytope (a finite convex polyhedron) in the iteration space. Each lower and upper bound expression must be an affine function of any outer loop indices plus a constant. The function bounds_ok checks the upper and lower bound of a tree_for to make sure the bounds are legal. The constructor for the loop_transform class normalizes the bounds of the loops to have a unit step size and so that the test of the tree_for is less-than-or-equal.

The loop_transform class may also contain an array of booleans that specifies whether the corresponding tree_for in the loops array is a doall loop.

Go to the previous, next section.