Patent ID: 6247173
Filing Date: 2001-06-12
Classification: G06F

Abstract:
A computer implemented method for optimizing a computer program which analyzes data dependence of memory reference pairs in software loops, and unrolls software loops by an unroll factor, comprising the steps of:a. analyzing the computer program for data dependence to determine whether two computer instructions access independent memory references or exactly dependent memory references;b. determining a data dependence distance for each pair of the exactly dependent memory references;c. generating a plurality of memory reference pairs from each exactly dependent memory reference pair; andd. tagging the plurality of memory reference pairs as related to the exactly dependent memory reference pair from which they were generated during the software loop unrolling based on the data dependence distance and the unroll factor;e. determining which pair of the tagged as related plurality of loop unrolled memory reference pairs is exactly dependent at an integral distance greater than zero and when the exactly dependent memory reference pair is found, the computer implemented method further comprising the steps of:a. terminating further determination of the distance for the tagged as related plurality of loop unrolled memory reference pairs;b. assigning the independent state to the tagged as related plurality of loop unrolled memory reference pairs which were not identified as exactly dependent at an integral distance greater than zero; andc. executing the dependence distance determination for a memory reference pair from the plurality of loop unrolled memory reference pairs which was generated by a different exactly dependent memory reference pair.