Patent ID: 7185323

Claim:
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.