Patent ID: 7234136

Claim:
A method for generating code to perform anticipatory prefetching for data references, comprising: receiving code to be executed on a computer system; analyzing the code to identify data references to be prefetched, wherein the data references are identified from basic blocks within if conditions regardless of whether the basic blocks are likely to execute, and wherein analyzing the code involves, performing a first marking phase in which only data references located in blocks that are certain to execute are considered in determining which data references are covered by preceding data references, and performing a second marking phase in which data references that are located in blocks that are not certain to execute are considered; calculating a prefetch ahead distance, wherein the prefetch ahead distance indicates the number of loop iterations ahead to prefetch for, and wherein the prefetch ahead distance is calculated as a function of loop characteristics within the code, as well as processor characteristics of the computer system; and inserting prefetch instructions into the code in advance of the identified data references based upon the prefetch ahead distance, wherein inserting prefetch instructions includes inserting multiple redundant prefetch instructions for a given data reference; wherein inserting multiple redundant prefetch instructions involves inserting the multiple redundant prefetch instructions into unused instruction slots, and wherein executing multiple redundant prefetch instructions potentially avoids a cache miss.