Patent ID: 8453134

Claim:
A method to optimize object code, comprising: processing source code including an array of elements referenced using at least two indices, wherein the array is nested within multiple loops, wherein at least two of the loops perform iterations with respect to the indices of the array, wherein the loops comprise multiple innermost loops, and wherein the index incremented in at least one of the innermost loops does not comprise a leftmost index in the array; transforming the source code to object code by performing operations, including: identifying a least loop among the innermost loops, wherein the least loop has a least number of iterations of the innermost loops; identifying a not-least loop among the innermost loops, wherein the not-least loop has more iterations than the least loop; determining a loop iteration difference denoting how many more iterations the not-least loop has, relative to the least loop; performing code replication for the not-least loop, wherein the operation of performing code replication comprises: replacing the not-least loop with a replacement loop, wherein the replacement loop has the least number of iterations, and the replacement loop comprises: an original copy of statements from the not-least loop; and N modified copies of the statements from the not-least loop, where N equals the loop iteration difference; fusing the least loop and the replacement loop into a fused innermost loop; and performing loop interchange to have the fused innermost loop provide iterations with respect to the leftmost index in the array; parallelizing an outer loop in the object code following the loop interchange without data dependency, wherein the source code includes at least one statement including at least one one-dimensional array within at least one of the innermost loops that prevents parallelization on the outer loop; and transforming the source code by performing array contraction to transform the one dimensional array that inhibits parallelization to a scalar variable.