Go to the previous, next section.

Non-perfectly Nested Loops

The loops need not be perfectly nested for tiling. The only exception is that if the loops are non-perfectly nested and the iteration space is non-rectangular, then coalescing must be turned off.

Any non-perfectly nested regions of the code must be guarded. For example, applying the parameters:

trip[0] = 100; trip[1] = 50;
nregions = 1;
coalesce[0] = FALSE;
first[0] = 0; first[1] = 2;

To the following code:

for (i = 0; i <= N; i++) {

    statement1;
    for (j = 0; j <= N; j++) {
        ...
    }
    statement2;
}

The resulting code is:

for (i_tile = 0; i_tile <= N; i_tile += 100) {
    for (j_tile = 0; j_tile <= N; j_tile += 50) {
        for (i = i_tile; i <= min(N, i_tile + 99); i++) {

            if (j_tile == 0) {
               statement1;
            }

            for (j = max(0, j_tile); j <= min(N, j_tile + 49); j++) {
                ...
            }

            if (N < j_tile + 1) {
               statement2;
            }
        }
    }
}

Go to the previous, next section.