System and method for insertion of prefetch instructions by a compiler

A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform a method for scheduling prefetch instructions and memory operation instructions in a code file having a plurality of instructions, the memory comprising:

• (a) identifying a first subset of memory operation instructions as cache hit memory operations;
• (b) identifying a second subset of memory operation instructions as cache miss memory operations;
• (c) determining if an associated prefetch instruction is needed for each of said memory operation instructions in said second subset of memory operations;
• (d) inserting an associated prefetch instruction for each of said memory operation instructions in said second subset of memory operations that has been determined to need an associated prefetch instruction;
• (e) identifying which memory operation instructions in said second subset of memory operations are martyr memory operations;
• and,
• (f) deleting inserted prefetch instructions “related” to said identified martyr memory operations.

A prefetch and memory instruction scheduler apparatus, in a computer system, for use in compiling a program, said apparatus comprising:

• an initial cache hit/miss assignment module operatively disposed within said apparatus and configured to:
• identify a first subset of memory operation instructions as cache hit memory operations;
• and
• identify a second subset of memory operation instructions as cache miss memory operations;
• a prefetch insertion module operatively disposed within said apparatus and configured to:
• determine if an associated prefetch instruction is needed for each of said memory operation instructions in said second subset of memory operations;
• and
• insert an associated prefetch instruction for each of said memory operation instructions in said second subset of memory operations that has been determined to need an associated prefetch instruction;
• and
• a scheduler module operatively disposed within said apparatus and configured to:
• identify which memory operation instructions in said second subset of memory operations are martyr memory operations;
• and
• delete inserted prefetch instructions “related” to said identified martyr memory operations.

A method of inserting prefetch instructions during compilation of a computer program, the method comprising:

• selecting a set of instructions in a computer program as likely cache-misses;
• inserting in the computer program a plurality of prefetch instructions associated with a subset of the set of instructions;
• scheduling said set of instructions;
• identifying one or more martyr instructions in said subset of instructions;
• and
• deleting any of said inserted prefetch instructions associated with said one or more martyr instructions.

A system for inserting prefetch instructions during compilation of a computer program, the system comprising:

• a cache hit/miss assignment module configured to select a set of instructions in a computer program as likely cache-misses;
• a prefetch insertion module configured to insert in the computer program a plurality of prefetch instructions associated with a subset of the set of instructions;
• a scheduler configured to schedule said set of instructions;
• and
• an operations module configured to:
• identify one or more martyr instructions in said subset of instructions;
• and
• delete any of said inserted prefetch instructions associated with said one or more martyr instructions.