Single cycle predictor

1. A predictor, comprising:

a memory comprising:

a plurality of entries, wherein each of the plurality of entries comprises a prediction of:

a hash of a next fetch address produced by a fetch block J of a series of successive fetch blocks in program execution order; and

a branch direction produced by the fetch block J; and

an output; and

an input that selects an entry of the plurality of entries for provision on the output;

wherein at least a portion of the output is fed back to the input such that the output provides the prediction of the hash of the next fetch address and the branch direction produced by each fetch block of the series of successive fetch blocks over a series of successive clock cycles; and

wherein the hash of the next fetch address produced by the fetch block J is insufficient for use by an instruction fetch unit to fetch from an instruction cache a fetch block J+1 of the series of successive fetch blocks, whereas the next fetch address produced by the fetch block J is sufficient for use by the instruction fetch unit to fetch from the instruction cache the fetch block J+1.

2. The predictor of claim 1 ,

wherein the hash of the next fetch address produced by the fetch block J is usable to initiate a lookup in one or more predictors of a prediction unit that provides a prediction of a next fetch address produced by the fetch block J+1.

3. The predictor of claim 2 ,

wherein the one or more predictors comprises a branch target buffer.

4. The predictor of claim 2 , further comprising:

a shift register configured to hold a current global branch history;

wherein for each clock cycle of the series of successive clock cycles:

the current global branch history and the branch direction of the entry selected for output are used to form an updated global branch history usable in conjunction with the hash of the next fetch address to initiate the lookup; and

the branch direction of the selected entry is shifted into the shift register.

5. The predictor of claim 2 , further comprising:

a shift register configured to hold a current path history;

wherein the one or more predictors comprises a conditional branch predictor; and

wherein for each clock cycle of the series of successive clock cycles:

the current path history and one or more bits of the hash of the next fetch address of the entry selected for output are used to form an updated path history usable in conjunction with the hash of the next fetch address to initiate the lookup in the conditional branch predictor; and

the one or more bits of the hash of the next fetch address are shifted into the shift register.

6. The predictor of claim 2 ,

wherein each of the plurality of entries further comprises:

an indicator that predicts whether the previous fetch block is terminated by an indirect branch instruction.

7. The predictor of claim 6 , further comprising:

a shift register configured to hold a current indirect path history;

wherein the one or more predictors comprises an indirect branch predictor; and

wherein for each clock cycle of the series of successive clock cycles in which the indicator predicts that the previous fetch block is terminated by an indirect branch instruction:

the current indirect path history and one or more bits of the hash of the next fetch address of the entry selected for output are used to form an updated indirect path history usable in conjunction with the hash of the next fetch address to initiate the lookup in the indirect branch predictor; and

the one or more bits of the hash of the next fetch address are shifted into the shift register.

8. The predictor of claim 2 ,

wherein each of the plurality of entries further comprises:

a second hash of the fetch address of the current fetch block for use as a tag, wherein the first hash and the second hash are of at least partially different sets of bits of the fetch address.

9. The predictor of claim 8 ,

wherein at least one of the one or more predictors is arranged in a set-associative manner;

wherein the lookup comprises:

using the hash of the next fetch address to select a set in the set-associative predictor; and

using the tag in a tag comparison with tags of ways of the selected set.

10. The predictor of claim 8 ,

wherein the plurality of entries of the memory are arranged in a set-associative fashion as a plurality of sets each having N ways, wherein N is at least two; and

wherein each of the plurality of entries of the memory further comprises a tag comprising a hash of the fetch address of fetch block J.

11. The predictor of claim 1 ,

wherein the hash of the next fetch address is further hashed with a virtual machine identifier.

12. The predictor of claim 1 ,

wherein the hash of the next fetch address is further hashed with a privilege mode.

13. A method, comprising:

with respect to a memory comprising:

a plurality of entries, wherein each of the plurality of entries comprises a prediction of:

a hash of a next fetch address produced by a fetch block J of a series of successive fetch blocks in program execution order; and

a branch direction produced by the fetch block J; and

an output; and

an input that selects an entry of the plurality of entries for provision on the output:

feeding back at least a portion of the output to the input such that the output provides the prediction of the hash of the next fetch address and the branch direction produced by each fetch block of the series of successive fetch blocks over a series of successive clock cycles;

wherein the hash of the next fetch address produced by the fetch block J is insufficient for use by an instruction fetch unit to fetch from an instruction cache a fetch block J+1 of the series of successive fetch blocks, whereas the next fetch address produced by the fetch block J is sufficient for use by the instruction fetch unit to fetch from the instruction cache the fetch block J+1.

14. The method of claim 13 , further comprising:

using the hash of the next fetch address produced by the fetch block J to initiate a lookup in one or more predictors of a prediction unit that provides a prediction of a next fetch address produced by the fetch block J+1.

15. The method of claim 14 ,

wherein the one or more predictors comprises a branch target buffer.

16. The method of claim 14 , further comprising:

wherein the predictor further comprises a shift register configured to hold a current global branch history; and

for each clock cycle of the series of successive clock cycles:

using the current global branch history and the branch direction of the entry selected for output to form an updated global branch history usable in conjunction with the hash of the next fetch address to initiate the lookup; and

shifting the branch direction of the selected entry into the shift register.

17. The method of claim 14 , further comprising:

wherein the predictor further comprises a shift register configured to hold a current path history; and

wherein the one or more predictors comprises a conditional branch predictor; and

for each clock cycle of the series of successive clock cycles:

using the current path history and one or more bits of the hash of the next fetch address of the entry selected for output to form an updated path history usable in conjunction with the hash of the next fetch address to initiate the lookup in the conditional branch predictor; and

shifting the one or more bits of the hash of the next fetch address into the shift register.

18. The method of claim 14 ,

wherein each of the plurality of entries further comprises:

an indicator that predicts whether the previous fetch block is terminated by an indirect branch instruction.

19. The method of claim 18 , further comprising:

wherein the predictor further comprises a shift register configured to hold a current indirect path history;

wherein the one or more predictors comprises an indirect branch predictor; and

for each clock cycle of the series of successive clock cycles in which the indicator predicts that the previous fetch block is terminated by an indirect branch instruction:

using the current indirect path history and one or more bits of the hash of the next fetch address of the entry selected for output to form an updated indirect path history usable in conjunction with the hash of the next fetch address to initiate the lookup in the indirect branch predictor; and

shifting the one or more bits of the hash of the next fetch address into the shift register.

20. The method of claim 14 ,

wherein each of the plurality of entries further comprises:

a second hash of the fetch address of the current fetch block for use as a tag, wherein the first hash and the second hash are of at least partially different sets of bits of the fetch address.

21. The method of claim 20 ,

wherein at least one of the one or more predictors is arranged in a set-associative manner;

wherein the lookup comprises:

using the hash of the next fetch address to select a set in the set-associative predictor; and

using the tag in a tag comparison with tags of ways of the selected set.

22. The method of claim 20 ,

wherein the plurality of entries of the memory are arranged in a set-associative fashion as a plurality of sets each having N ways, wherein N is at least two; and

wherein each of the plurality of entries of the memory further comprises a tag comprising a hash of the fetch address of fetch block J.

23. The method of claim 13 ,

wherein the hash of the next fetch address is further hashed with a virtual machine identifier.

24. The method of claim 13 ,

wherein the hash of the next fetch address is further hashed with a privilege mode.

25. A non-transitory computer-readable medium having instructions stored thereon that are capable of causing or configuring a predictor comprising:

a memory comprising:

a plurality of entries, wherein each of the plurality of entries comprises a prediction of:

a hash of a next fetch address produced by a fetch block J of a series of successive fetch blocks in program execution order; and

a branch direction produced by the fetch block J; and

an output; and

an input that selects an entry of the plurality of entries for provision on the output;

wherein at least a portion of the output is fed back to the input such that the output provides the prediction of the hash of the next fetch address and the branch direction produced by each fetch block of the series of successive fetch blocks over a series of successive clock cycles; and

wherein the hash of the next fetch address produced by the fetch block J is insufficient for use by an instruction fetch unit to fetch from an instruction cache a fetch block J+1 of the series of successive fetch blocks, whereas the next fetch address produced by the fetch block J is sufficient for use by the instruction fetch unit to fetch from the instruction cache the fetch block J+1.