Patent ID: 7770162

Claim:
A method for statement shifting to increase parallelism of loops for compiler optimization, comprising: constructing a data dependence graph (DDG) to represent dependences between statements in a loop; constructing a basic equations group from the DDG; constructing a dependence equations group derived in part from the basic equations group by: generating a spanning tree for each maximal undirected connected sub-graph (MUCS) in the DDG; identifying one or more basic undirected circles for each dependence of the DDG that is in the MUCS and not in the spanning tree, wherein all other dependences in each basic undirected circle are in the spanning tree; and creating a dependence equation for the dependence equations group from each of the one or more basic undirected circles; and determining a shifting vector for the loop from the dependence equations group, wherein the shifting vector to represent an offset to apply to each statement in the loop for statement shifting.