Method and apparatus for inserting prefetch instructions in an optimizing compiler

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for generating code to perform anticipatory prefetching for data references, the method comprising:

• receiving code to be executed on a computer system;
• analyzing the code to identify data references to be prefetched;
• calculating an execution time of a single loop iteration which includes the identified data references, wherein the execution time includes an adjustment for the execution probability of the identified data references;
• calculating a prefetch ahead distance, wherein the prefetch ahead distance includes the ratio of outstanding prefetches to the number of prefetch streams and considers the probabilistically adjusted execution time of the single loop iteration, and wherein the prefetch ahead distance indicates how many loop iterations ahead to prefetch for;
• and
• inserting prefetch instructions into a preceding basic block of the code in advance of the identified data references based upon the prefetch ahead distance, wherein inserting prefetch instructions involves inserting multiple prefetch instructions for a given cache line, and wherein inserting the prefetch instructions involves,
• attempting to calculate a stride value for a given data reference within a loop,
• if the stride value cannot be calculated, setting the stride value to a default stride value, and
• inserting a prefetch instruction to prefetch the given data reference for a subsequent loop iteration based on the stride value;
• wherein the stride value is constant for some but not necessarily all loop iterations.

An apparatus that generates code to perform anticipatory prefetching for data references, comprising:

• a receiving mechanism that is configured to receive code to be executed on a computer system;
• an analysis mechanism that is configured to analyze the code to identify data references to be prefetched;
• a calculating mechanism that is configured to calculate an execution time of a single loop iteration which includes the identified data references, wherein the execution time includes an adjustment for the execution probability of the identified data references;
• a calculating mechanism that is configured to calculate a prefetch ahead distance, wherein the prefetch ahead distance includes the ratio of outstanding prefetches to the number of prefetch streams and considering the probabilistically adjusted execution time of the single loop iteration, and wherein the prefetch ahead distance indicates how many loop iterations ahead to prefetch for;
• and
• an insertion mechanism that is configured to insert prefetch instructions into a preceding basic block of the code in advance of the identified data references based upon the prefetch ahead distance, wherein the insertion mechanism facilitates inserting multiple prefetch instructions for a given cache line;
• wherein the insertion mechanism is configured to,
• attempt to calculate a stride value for a given data reference within a loop,
• set the stride value to a default stride value if the stride value cannot be calculated, and to
• insert a prefetch instruction to prefetch the given data reference for a subsequent loop iteration based on the stride value;
• wherein the stride value is constant for some but not necessarily all loop iterations.