Locked prefetch scheduling in general cyclic regions

1. A method for locked prefetch scheduling in general cyclic regions of a computer program, comprising:

receiving source code for the computer program;

compiling the source code into intermediate code;

performing a trace detection on the intermediate code to identify a cyclic region in the intermediate code;

inserting prefetch instructions and corresponding locks into the intermediate code, wherein each prefetch instruction is paired with a lock, and wherein each lock is inserted a number of instructions after a corresponding prefetch instruction, wherein the number of instructions is computed based on at least one of a maximum number of outstanding prefetches allowed and a number of accesses in the cyclic region; and

generating executable code from the intermediate code;

wherein a lock for a given prefetch instruction prevents subsequent prefetches from being issued until the data value returns for the given prefetch instruction; and

wherein the method is implemented by a computer system that comprises a processor and a memory.

2. The method of claim 1 , wherein performing the trace detection involves:

gathering all accesses marked for prefetching;

inserting locks for selected prefetch operations; and

scheduling the prefetches and the locks.

3. The method of claim 2 , wherein identifying the cyclic region of the intermediate code involves locating general cyclic regions in the intermediate code that have a high probability of being executed repeatedly.

4. The method of claim 3 , further comprising performing training runs to determine a probability of a region of the intermediate code being executed repeatedly.

5. The method of claim 1 , wherein a lock for a given prefetch instruction is implemented as a non-faulting load instruction to the same address as the given prefetch instruction.

6. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for locked prefetch scheduling in general cyclic regions of a computer program, the method comprising:

receiving source code for the computer program;

compiling the source code into intermediate code;

performing a trace detection on the intermediate code to identify a cyclic region in the intermediate code;

inserting prefetch instructions and corresponding locks into the intermediate code, wherein each prefetch instruction is paired with a lock, and wherein each lock is inserted a number of instructions after a corresponding prefetch instruction wherein the number of instructions is computed based on at least one of a maximum number of outstanding prefetches allowed and a number of accesses in the cyclic region; and

generating executable code from the intermediate code;

wherein a lock for a given prefetch instruction prevents subsequent prefetches from being issued until the data value returns for the given prefetch instruction.

7. The computer-readable storage medium of claim 6 , wherein performing the trace detection involves:

gathering all accesses marked for prefetching;

inserting locks for selected prefetch operations; and

scheduling the prefetches and the locks.

8. The computer-readable storage medium of claim 7 , wherein identifying the cyclic region of the intermediate code involves locating general cyclic regions in the intermediate code that have a high probability of being executed repeatedly.

9. The computer-readable storage medium of claim 8 , the method further comprising performing training runs to determine a probability of a region of the intermediate code being executed repeatedly.

10. The computer-readable storage medium of claim 6 , wherein a lock for a given prefetch instruction is implemented as a non-faulting load instruction to the same address as the given prefetch instruction.

11. A computer system for locked prefetch scheduling in general cyclic regions of a computer program, comprising:

a processor;

a memory;

a receiving mechanism configured to receive source code for the computer program;

a compiling mechanism configured to compile the source code into intermediate code;

a trace detection mechanism configured to perform a trace detection on the intermediate code;

an identifying mechanism configured to identify a cyclic region of the intermediate code;

an inserting mechanism configured to insert prefetch instructions and corresponding locks into the intermediate code, wherein each prefetch instruction is paired with a lock, and wherein each lock is inserted a number of instructions after a corresponding prefetch instruction, wherein the number of instructions is computed based on at least one of a maximum number of outstanding prefetches allowed and a number of accesses in the cyclic region; and

a generating mechanism configured to generate executable code from the intermediate code;

wherein a lock for a given prefetch instruction prevents subsequent prefetches from being issued until the data value returns for the given prefetch instruction.

12. The computer system of claim 11 , further comprising:

a gathering mechanism configured to gather all accesses marked for prefetching;

an inserting mechanism configured to insert locks for selected prefetch operations; and

a scheduling mechanism configured to schedule the prefetches and the locks.

13. The computer system of claim 12 , wherein identifying the cyclic region of the intermediate code involves locating general cyclic regions in the intermediate code that have a high probability of being executed repeatedly.

14. The computer system of claim 13 , further comprising a training mechanism configured to perform training runs to determine a probability of a region of the intermediate code being executed repeatedly.

15. The computer system of claim 11 , wherein a lock for a given prefetch instruction is implemented as a non-faulting load instruction to the same address as the given prefetch instruction.