Method and system for the efficient unrolling of loop nests with an imperfect nest structure

A system for unrolling imperfect loop nests, comprising:

• a processor;
• a data bus coupled to said processor;
• and
• a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for:
• categorizing an iteration space associated with at least one dimension of a nested loop into a residual iteration space and a non-residual iteration space utilizing an unroll-and-jam transformation wherein said non-residual iteration space traverses a set of indices for a next dimension of said nested loop;
• recursively applying said unroll-and-jam transformation to said next dimension utilizing said non-residual iteration space of said at least one dimension and performing said unroll-and-jam transformation until a last dimension of said nested loops thereof;
• and
• removing said non-residual iteration space and generating code for said residual iteration space of said last dimension in order to obtain a perfect loop nest to thereby provide for an efficient compile time direct loop optimization transformation.

A computer-usable medium embodying computer program code, said computer program code comprising computer executable instructions configured for:

• categorizing an iteration space associated with at least one dimension of a nested loop into a residual iteration space and a non-residual iteration space utilizing an unroll-and-jam transformation wherein said non-residual iteration space traverses a set of indices for a next dimension of said nested loop;
• recursively applying said unroll-and jam transformation to said next dimension utilizing said non-residual iteration space of said at least one dimension and performing said unroll-and-jam transformation until a last dimension of said nested loops thereof;
• and
• removing said non-residual iteration space and generating code for said residual iteration space of said last dimension in order to obtain a perfect loop nest to thereby provide for an efficient compile time direct loop optimization transformation.