Reducing instruction miss penalties in applications
Embodiments include systems and methods for reducing instruction cache miss penalties during application execution. Application code is profiled to determine “hot” code regions likely to experience instruction cache miss penalties. The application code can be linearized into a set of traces that include the hot code regions. Embodiments traverse the traces in reverse, keeping track of instruction scheduling information, to determine where an accumulated instruction latency covered by the code blocks exceeds an amount of latency that can be covered by prefetching. Each time the accumulated latency exceeds the amount of latency that can be covered by prefetching, a prefetch instruction can be scheduled in the application code. Some embodiments insert additional prefetches, merge prefetches, and/or adjust placement of prefetches to account for scenarios, such as loops, merging or forking branches, edge confidence values, etc.
1. A system for reducing instruction cache miss penalties in application code execution, the system comprising:
a processor; and
a non-transient storage medium having instructions stored thereon, which, when executed, cause the processor to instantiate a compiler comprising:
a code profiler, operable to:
determine an instruction cache miss penalty for each of a plurality of code sections of application code, the instruction cache miss penalty indicating a likelihood that execution of the corresponding code section in the target execution environment will result in an instruction cache miss; and
generate execution traces from the application code, each execution trace comprising at least one of the plurality of code sections; and
an instruction prefetcher operable, for each execution trace having a code section with a corresponding instruction cache miss penalty that exceeds a predetermined penalty threshold, to:
traverse a set of code blocks of the execution trace in reverse starting from a source code block of the execution trace until an accumulated instruction latency exceeds a prefetch latency by, for each of the set of code blocks, adding a latency covered by the code block to latencies of previously traversed code blocks of the set of code blocks to calculate the accumulated instruction latency, the prefetch latency corresponding to a predicted time to prefetch into an instruction cache a number of code blocks defined by a prefetch chunk size; and
insert an instruction prefetch ahead of a last-traversed code block in the execution trace when the accumulated instruction latency exceeds the prefetch latency.
2. The system of claim 1 , wherein the computer-implemented code profiler comprises a hardware counter based profiler operable to calculate the likelihood that execution of the corresponding code section will to result in an instruction cache miss.
3. The system of claim 1 , wherein the computer-implemented code profiler is operable to determine the instruction cache miss penalty for each of the plurality of code sections of the application code by identifying each code section as likely to result in an instruction cache miss during execution when the code section is targeted by a programmer user for instruction prefetching.
4. The system of claim 1 , wherein:
each execution trace comprises a sequence of instruction chunks each having the number of code blocks defined by the prefetch chunk size;
the source code block is a last code block of a second instruction chunk that directly precedes a first instruction chunk; and
the computer-implemented prefetcher is operable to insert the instruction prefetch as a first prefetch instruction that prefetches the first instruction chunk, thereby scheduling at least the prefetch latency between execution of the first prefetch instruction and execution of a first code block of the first instruction chunk.
5. The system of claim 4 , wherein the computer-implemented prefetcher is further operable to:
reset the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continue traversing the set of code blocks of the execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
insert a second instruction prefetch that prefetches the second instruction chunk in the execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second instruction prefetch and execution of a first code block of the second instruction chunk.
6. The system of claim 4 , wherein the execution trace is a first execution trace, and the computer-implemented prefetcher is further operable to:
reset the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continue traversing the set of code blocks of the first execution trace until a starting point of the execution trace is reached without the accumulated instruction latency from the reset source block exceeding the prefetch latency;
identify a second execution trace of the application code that is a predecessor of the first execution trace according to a function call graph of the application code;
traverse the set of code blocks of the second execution trace from a last code block of the second execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
insert a second instruction prefetch that prefetches the second instruction chunk in the first execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second instruction prefetch and execution of a first code block of the second instruction chunk.
7. The system of claim 1 , further comprising:
a computer-implemented cache analyzer operable to determine the prefetch latency and the prefetch chunk size according to cache characteristics of a target execution environment for the application code.
8. A computer-implemented method for reducing instruction cache miss penalties in application code execution, the method comprising:
determining, at compile time, an instruction cache miss penalty for each of a plurality of code sections of application code, the instruction cache miss penalty indicating a likelihood that execution of the corresponding code section will result in an instruction cache miss;
generating, at compile time, execution traces from the application code, each execution trace comprising at least one of the plurality of code sections;
determining, at compile time, a prefetch latency corresponding to a predicted time to prefetch into an instruction cache a number of code blocks defined by a prefetch chunk size according to a target execution environment for the application code; and
for each execution trace having a code section with a corresponding instruction cache miss penalty that exceeds a predetermined penalty threshold:
traversing, at compile time, a set of code blocks of the execution trace in reverse starting from a source code block of the execution trace until an accumulated instruction latency exceeds the prefetch latency by, for each of the set of code blocks, adding a latency covered by the code block to latencies of previously traversed code blocks of the set of code blocks to calculate the accumulated instruction latency; and
inserting, at compile time, a prefetch instruction ahead of a last-traversed code block in the execution trace when the accumulated instruction latency exceeds the prefetch latency.
9. The computer-implemented method of claim 8 , wherein determining the instruction cache miss penalty for each of the plurality of code sections of application code comprises:
profiling each code section using a hardware counter based profiler to calculate the likelihood that execution of the corresponding code section will result in an instruction cache miss.
10. The computer-implemented method of claim 9 , wherein the hardware counter based profiler calculates the likelihood that execution of the corresponding code section will result in an instruction cache miss by calculating a likelihood that the corresponding code section will be executed during execution of the application code.
11. The computer-implemented method of claim 8 , wherein determining the instruction cache miss penalty for each of the plurality of code sections of application code comprises:
identifying each code section as likely to result in an instruction cache miss during execution when the code section is targeted by a programmer user for instruction prefetching.
12. The computer-implemented method of claim 11 , wherein the code section is targeted by a programmer user for instruction prefetching unless the code section includes an indication by the programmer user that the corresponding code section is unlikely to be executed during execution of the application code.
13. The computer-implemented method of claim 8 , wherein determining the instruction cache miss penalty for each of the plurality of code sections of application code comprises:
using feedback directed optimization to empirically calculate a likelihood that the corresponding code section will be executed during execution of the application code.
14. The computer-implemented method of claim 8 , further comprising:
computing whether instruction prefetching will reduce instruction cache miss penalties; and
performing the traversing and inserting steps only when instruction prefetching will reduce instruction cache miss penalties according to the computing step.
15. The computer-implemented method of claim 14 , wherein computing whether instruction prefetching will reduce instruction cache miss penalties comprises:
computing a total working size of all execution traces determined to have a code section with a corresponding instruction cache miss penalty that exceeds the predetermined threshold; and
determining that instruction prefetching will reduce instruction cache miss penalties only when the total working size exceeds a threshold size predetermined according to a capacity of at least one target cache.
16. The computer-implemented method of claim 8 , wherein:
each execution trace comprises a sequence of instruction chunks each having the number of code blocks defined by the prefetch chunk size;
the source code block is a last code block of a second instruction chunk that directly precedes a first instruction chunk; and
inserting the prefetch instruction ahead of the last-traversed code block in the execution trace comprises inserting the prefetch instruction as a first prefetch instruction that prefetches the first instruction chunk, thereby scheduling at least the prefetch latency between execution of the first prefetch instruction and execution of a first code block of the first instruction chunk.
17. The computer-implemented method of claim 16 , further comprising:
resetting the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continuing traversing the set of code blocks of the execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
inserting a second prefetch instruction that prefetches the second instruction chunk in the execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second prefetch instruction and execution of a first code block of the second instruction chunk.
18. The computer-implemented method of claim 16 , wherein the execution trace is a first execution trace, and further comprising:
resetting the source code block to a last code block of a third instruction chunk that directly precedes the second instruction chunk;
continuing traversing the set of code blocks of the first execution trace until a starting point of the execution trace is reached without the accumulated instruction latency from the reset source block exceeding the prefetch latency;
identifying a second execution trace of the application code that is a predecessor of the first execution trace according to a function call graph of the application code;
traversing the set of code blocks of the second execution trace from a last code block of the second execution trace until the accumulated instruction latency from the reset source block exceeds the prefetch latency; and
inserting a second prefetch instruction that prefetches the second instruction chunk in the first execution trace according to where the accumulated instruction latency from the reset source block exceeds the prefetch latency, thereby scheduling at least the prefetch latency between execution of the second prefetch instruction and execution of a first code block of the second instruction chunk.
19. The computer-implemented method of claim 8 , wherein, inserting the prefetch instruction ahead of the last-traversed code block in the execution trace comprises:
determining that the last-traversed code block is inside a body of a loop having a pre-header; and
inserting the prefetch instruction in the pre-header of the loop.
20. The computer-implemented method of claim 8 , wherein the execution trace is one of a plurality of execution traces, and further comprising:
calculating, at each edge between a child execution trace in the plurality of execution traces and one or more parent execution traces in the plurality of execution traces as defined by a function call graph, an edge confidence level that the child execution trace will be called by each of its parent execution traces;
calculating an accumulated confidence level as a function of the edge confidence level of each edge crossed while traversing the set of code blocks of the execution trace in reverse; and
inserting the prefetch instruction after a last-traversed edge when the accumulated confidence level falls below a predetermined confidence threshold before the accumulated instruction latency exceeds the prefetch latency.