METHOD FOR UNROLLING TWO-DEEP LOOPS WITH CONVEX BOUNDS AND IMPERFECTLY NESTED CODE, AND FOR UNROLLING ARBITRARILY DEEP NESTS WITH CONSTANT BOUNDS AND IMPERFECTLY NESTED CODE

A compiler for compiling source code whereby the compiled source code is optimized by performing outer loop unrolling (a generalization of “unroll and jam” on selected loop nests. The present invention allows any arbitrarily deep loop nests with non-varying loop bounds to be properly unrolled even in the presence of imperfectly nested code. This is accomplished for two-deep loop nests by transforming the code into multiple adjacent loop nests. In the transformed code, the imperfect code is isolated so that one of the adjacent loops nests has none, and thus can be unrolled and jammed. For three-deep or greater loop nests, the process is repeated recursively from the outer-most loop. The present invention also allows outer loop unrolling for two-deep loop nests with convex bounds, even with the presence of imperfectly nested code. This is accomplished by identifying strips of code which do not contain imperfectly nested code. An unroll and jam operation is executed for the identified strips. Code falling outside of the identified strips as well as wind-down code, are executed according to their original, untransformed order.