Patent ID: 7581215

Claim:
A method of identifying cross-iteration dependence of code that includes at least two loops with an enclosing loop enclosing an enclosed loop and generating executable code based thereon, the method comprising: for the enclosing loop that includes at least two indexed accesses to storage, wherein at least one of the indexed accesses is a write access and wherein at least one of the indexed accesses indexes the storage using an index-association function that is a non-linear function of the enclosing loop index, generating a set of linear expressions equivalent to the non-linear function; evaluating, using the equivalent set of linear expressions, whether any index instance for the write access coincides with an index instance for any other access to the storage; evaluating, using the equivalent set of linear expressions, whether any index instance for the write access coincides with an index instance for any other access to the storage; parallelizinq the enclosing loop if, based on the evaluating, no dependence exists between the two indexed accesses to storage; and generating executable code corresponding to the parallelized loop.