Unrolling transformation of nested loops

摘要

The present invention is directed to a transformation technique for nested loops. A virtual iteration space may be determined based on an unroll factor (UF). The virtual iteration space, which includes the actual iteration space, is formed such that, the virtual iteration space may be evenly divided by a selected UF. Once the virtual iteration space has been calculated or determined, the virtual iteration space is “cut” into regular portions by one or more unroll factors. Portions of the actual iteration space which do not fill the cut portions of the virtual iteration space or which fall outside these cuts which have been evenly divided by the unroll factor form a residue which is calculated. The portions of the actual iteration space which remain are also evenly divided by the unroll factor(s). An outer loop for this remaining portion of the actual iteration space is then unrolled. This unrolled portion forms a perfect nested loop. Accordingly, the operations for the unrolled remaining portion of the actual iteration space when combined with the operations for the residue of the actual iteration space which was not evenly divided by the unroll factor is, in appropriate situations, semantically equivalent to the original nested loops. Aspects of the invention are applicable to rectangular and triangular loop nests, and combinations thereof. Moreover, the invention is applicable to loops having n-dimensions.