Method of efficient dynamic data cache prefetch insertion

A method of optimizing a program comprising a plurality of execution paths, the method comprising:

• collecting information describing a plurality of occurrences of a plurality of cache miss events during a runtime mode of the program;
• identifying a performance degrading execution path in the program;
• modifying the performance degrading execution path to define an optimized execution path, the optimized execution path comprising at least one prefetch instruction;
• storing the optimized execution path;
• and
• redirecting the performance degrading execution path in the program to include the optimized execution path.

A method of optimizing a program, the method comprising:

• receiving information describing a dependency graph for an instruction causing frequent cache misses, the instruction being included in the program;
• determining whether a cyclic dependency pattern exists in the graph;
• if the cyclic dependency pattern exists then, computing stride information derived from the cyclic dependency pattern;
• inserting an at least one prefetch instruction derived from the stride information, the at least one prefetch instruction being inserted into the program prior to the instruction causing the frequent cache misses;
• reusing the at least one prefetch instruction in the program for reducing subsequent cache misses;
• and
• performing said receiving, said determining, said computing, said inserting and said reusing during runtime of the program.

A computer-readable medium having a computer program accessible therefrom, wherein the computer program comprises instructions for:

• collecting information describing a frequency of occurrence of a plurality of cache misses caused by at least one instruction;
• identifying a performance degrading instruction;
• optimizing the computer program to provide an optimized sequence of instructions, the optimized sequence of instructions comprising at least one prefetch instruction;
• and
• modifying the computer program being executed to include the optimized sequence.

A computer system comprising:

• a processor;
• a memory coupled to the processor;
• a program comprising instructions, the program being stored in memory, the processor executing instructions to:
• collect information describing a frequency of occurrence of a plurality of cache misses caused by at least one instruction;
• identify a performance degrading instruction;
• optimize the program to provide an optimized sequence of instructions, the optimized sequence of instructions comprising at least one prefetch instruction;
• and
• modify the program being executed to include the optimized sequence.