Patent ID: 8091079

Claim:
A method for implementing shadow versioning to improve data dependence analysis for instruction scheduling in compiling code, the method comprising: in a processor: identifying a plurality of loops within the code; for each loop of the plurality of loops: identifying an original shadow symbol accessed in the loop; initializing a dependence matrix having N rows and N columns for N accesses to the original shadow symbol in the loop, wherein an ith row vector represents a dependence relationship between the ith access to the shadow symbol and all the accesses to the same shadow in the loop; for each original shadow symbol accessed in the loop, performing: examining dependencies between an access pair X, Y to the original shadow symbol; storing dependence vectors for a given access in the dependence matrix as N row vectors, wherein the dependence matrix has two possible values, no-dependence and dependence, and wherein all diagonal matrix elements have the dependence value, and wherein each N row vectors is a dependence vector for access; comparing the dependence vectors; classifying the dependence vectors into an X-set and a Y-set based on the access pairs X, Y, wherein accesses in a common set includes common dependence vectors; generating a new shadow symbol for each set; replacing the original shadow symbol with the new shadow symbol for a corresponding access in the code, by examining dependencies of the corresponding access in the code, wherein the corresponding access is an element of an N×N dependence matrix and replacing the original shadow symbol with the new shadow symbol that shares a common dependency vector from the dependence matrix; generating alias relationships between the newly created shadow symbols; performing instruction scheduling for the code; and compiling the code.