Using value speculation to break constraining dependencies in iterative control flow structures
View Patent ↗One embodiment of the present invention provides a system that uses value speculation to break constraining dependencies in loops. The system operates by first identifying a loop within a computer program, and then identifying a dependency on a long-latency operation within the loop that is likely to constrain execution of the loop. Next, the system breaks the dependency by modifying the loop to predict a value that will break the dependency, and then using the predicted value to speculatively execute subsequent loop instructions.
1. A computer-implemented method that uses value speculation to break constraining dependencies in loops, comprising:
identifying a loop within a computer program;
identifying a dependency on a long-latency operation within the loop that is likely to constrain execution of the loop, wherein the long-latency operation is a missing load operation that is likely to generate a cache miss; and
breaking the dependency by modifying the loop to,
predict a value within the loop that will break the (DGPS) dependency, and to
use the predicted value to speculatively execute subsequent instructions within the loop, wherein speculatively executing subsequent instructions within the loop involves executing prefetching instructions for missing load operations based on predicted values;
wherein modifying the loop involves:
identifying loop variants, P, that are used to compute missing load addresses,
identifying a set of instructions, G, within the loop that are used to compute the loop variants, P, excluding missing loads and loop exit conditions,
identifying remaining instructions, F, in the loop body excluding G,
identifying conditions, C, and/or data, D, that are computed in F and are used in G,
generating a specialized version of F, PredF, that uses value speculation to obtain predicted values, PredC and/or PredD, for C and/or D,
generating a specialized version of G, PredG, that speculates the next value of P, SpecP, based on PredC and/or PredD, and
generating code for PredF, PredG, F and G, so that PredF generates PredC and/or PredD, PredG uses PredC and/or PredD to determine SpecP, and PredF uses SpecP to generate prefetches for the missing load operations.
2. The computer-implemented method of claim 1 , wherein the dependency can be one of:
a data dependency; and
a control flow dependency.
3. The computer-implemented method of claim 1 , wherein identifying the loop involves identifying a loop that generates a large number of cache misses during execution of the computer program.
4. The computer-implemented method of claim 1 , wherein generating code for PredF, PredG, F and G, involves:
generating a prologue loop that executes only PredF and PredG to generate initial prefetches; and
generating a subsequent kernel loop that executes PredF, PredG, F and G;
whereby prefetches generated by the prologue loop are likely to eliminate initial load misses generated by F and C in the kernel loop.
5. The computer-implemented method of claim 1 , wherein speculatively executing subsequent instructions in the loop involves performing the speculative execution in a committal manner by:
performing a checkpointing operation prior to commencing speculative execution; and
committing results of the speculative execution to the architectural state of the processor during the speculative execution.
6. The computer-implemented method of claim 1 , wherein speculatively executing subsequent instructions in the loop involves performing the speculative execution in a non-committal manner by:
performing prefetching operations during speculative execution, but not committing results of the speculative execution to the architectural state of the processor; and
executing the speculatively executed instructions again during non-speculative execution.
7. The computer-implemented method of claim 1 , wherein predicting the value within the loop that will break the dependency involves predicting:
a branch outcome;
a value of a missing load; or
an intermediate value computed from the missing load.
8. The computer-implemented method of claim 1 , wherein the method is performed by a compiler.
9. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method that uses value speculation to break constraining dependencies in loops, the method comprising:
identifying a loop within a computer program;
identifying a dependency on a long-latency operation within the loop that is likely to constrain execution of the loop, wherein the long-latency operation is a missing load operation that is likely to generate a cache miss; and
breaking the dependency by modifying the loop to,
predict a value within the loop that will break the dependency, and to
use the predicted value to speculatively execute subsequent instructions within the loop, wherein speculatively executing subsequent instructions within the loop involves executing prefetching instructions for missing load operations based on predicted values;
wherein modifying the loop involves:
identifying loop variants, P, that are used to compute missing load addresses,
identifying a set of instructions, G, within the loop that are used to compute the loop variants, P, excluding missing loads and loop exit conditions,
identifying remaining instructions, F, in the loop body excluding G,
identifying conditions, C, and/or data, D, that are computed in F and are used in G,
generating a specialized version of F, PredF, that uses value speculation to obtain predicted values, PredC and/or PredD, for C and/or D,
generating a specialized version of G, PredG, that speculates the next value of P, SpecP, based on PredC and/or PredD, and
generating code for PredF, PredG, F and G, so that PredF generates PredC and/or PredD, PredG uses PredC and/or PredD to determine SpeeP, and PredF uses SpecP to generate prefetches for the missing load operations.
10. The computer-readable storage medium of claim 9 , wherein the dependency can be one of:
a data dependency; and
a control flow dependency.
11. The computer-readable storage medium of claim 9 , wherein identifying the loop involves identifying a loop that generates a large number of cache misses during execution of the computer program.
12. The computer-readable storage medium of claim 9 , wherein generating code for PredF, PredG, F and G, involves:
generating a prologue loop that executes only PredF and PredG to generate initial prefetches; and
generating a subsequent kernel loop that executes PredF, PredG, F and G;
whereby prefetches generated by the prologue loop are likely to eliminate initial load misses generated by F and G in the kernel loop.
13. The computer-readable storage medium of claim 9 , wherein speculatively executing subsequent instructions in the loop involves performing the speculative execution in a committal manner by:
performing a checkpointing operation prior to commencing speculative execution; and
committing results of the speculative execution to the architectural state of the processor during the speculative execution.
14. The computer-readable storage medium of claim 9 , wherein speculatively executing subsequent instructions in the loop involves performing the speculative execution in a non-committal manner by:
performing prefetching operations during speculative execution, but not committing results of the speculative execution to the architectural state of the processor; and
executing the speculatively executed instructions again during non-speculative execution.
15. The computer-readable storage medium of claim 9 , wherein predicting the value within the loop that will break the dependency involves predicting:
a branch outcome;
a value of a missing load; or
an intermediate value computed from the missing load.
16. The computer-readable storage medium of claim 9 , wherein the method is performed by a compiler.
17. A computer apparatus that uses value speculation to break constraining dependencies in loops, comprising:
a loop identification mechanism configured to identify a loop within a computer program;
a dependency identification mechanism configured to identify a dependency on a long-latency operation within the loop that is likely to constrain execution of the loop, wherein the long-latency operation is a missing load operation that is likely to generate a cache miss; and
a dependency breaking mechanism configured to break the dependency by modifying the loop to,
predict a value within the loop that will break the dependency, and to
use the predicted value to speculatively execute subsequent instructions within the loop;
wherein the dependency breaking mechanism is configured to modify the loop to execute prefetching operations during speculative execution for missing load operations based on predicted values; and
wherein the dependency breaking mechanism is configured to modify the loop to:
identify loop variants, P, that are used to compute missing load addresses,
identify a set of instructions, G, within the loop that are used to compute the loop variants, P, excluding missing loads and loop exit conditions,
identify remaining instructions, F, in the loop body excluding G,
identify conditions, C, and/or data, D, that are computed in F and are used in G,
generate a specialized version of F, PredF, that uses value speculation to obtain predicted values, PredC and/or PredD, for C and/or D,
generate a specialized version of G, PredG, that speculates the next value of P, SpecP, based on PredC and/or PredD, and to
generate code for PpedF, PredG, F and G, so that PredF generates PredC and/or PredD, PredG uses PredC and/or PredD to determine SpecP, and PredF uses SpecP to generate prefetches for the missing load operations.
18. The computer apparatus of claim 17 , wherein the dependency can be one of:
data dependency; and
a control flow dependency.
19. The computer apparatus of claim 17 , wherein the loop identification mechanism is configured to identify a loop that generates a large number of cache misses during execution of the computer program.
20. The computer apparatus of claim 17 , wherein generating code for PredF, PredG, F and G involves:
generating a prologue loop that executes only PredF and PredG to generate initial prefetches; and
generating a subsequent kernel loop that executes PredF, PredG, F and G;
whereby prefetches generated by the prologue loop are likely to eliminate initial load misses generated by F and G in the kernel loop.
21. The computer apparatus of claim 17 , wherein the dependency breaking mechanism is configured to modify the loop to:
perform a checkpointing operation prior to commencing speculative execution; and to
commit results of the speculative execution to the architectural state of the processor during the speculative execution.
22. The computer apparatus of claim 17 , wherein the dependency breaking mechanism is configured to:
perform prefetching operations during speculative execution, but not committing results of the speculative execution to the architectural state of the processor; and to
execute the speculatively executed instructions again during non-speculative execution.
23. The computer apparatus of claim 17 , wherein the dependency breaking mechanism is configured to modify the loop to predict:
a branch outcome;
a value of a missing load; or
an intermediate value computed from the missing load.
24. The computer apparatus of claim 17 , wherein the apparatus is part of a compiler.