Address manipulation using indices and tags
Techniques are disclosed for address manipulation using indices and tags. A first index is generated from bits of a processor program counter, where the first index is used to access a branch predictor bimodal table. A first branch prediction is provided from the bimodal table, based on the first index. The first branch prediction is matched against N tables, where the tables contain prior branch histories, and where: the branch history in table T(N) is of greater length than the branch history of table T(N−1), and the branch history in table T(N−1) is of greater length than the branch history of table T(N−2). A processor address is manipulated using a greatest length of hits of branch prediction matches from the N tables, based on one or more hits occurring. The branch predictor address is manipulated using the first branch prediction from the bimodal table, based on zero hits occurring.
1. A processor-implemented method for address manipulation comprising:
generating a first index from one or more bits of a processor program counter, wherein the first index is used to access a branch predictor bimodal table;
providing a first branch prediction from the bimodal table, based on the first index;
matching the first branch prediction against N tables, wherein N is three or more, wherein the tables contain prior branch histories, and wherein:
the branch history in table T(N) is of greater length than the branch history of table T(N−1); and
the branch history in table T(N−1) is of greater length than the branch history of table T(N−2);
manipulating a processor address using a greatest length of hits of branch prediction matches from the N tables, based on one or more hits occurring; and
manipulating the branch predictor address using the first branch prediction from the bimodal table, based on zero hits occurring.
2. The method of claim 1 wherein the manipulating the branch predictor address is used for accessing a branch predictor array.
3. The method of claim 1 wherein the branch predictor bimodal table is direct mapped.
4. The method of claim 3 wherein the branch predictor bimodal table is tagless.
5. The method of claim 1 further comprising generating a second, a third, and a fourth index, wherein the second index is used in table T(N), the third index is used in table T(N−1), and the fourth index is used in table T(N−2).
6. The method of claim 5 wherein the second, third, and fourth indices are generated using hashing.
7. The method of claim 5 wherein the index for table T(N) is used as a tag for table T(N−1).
8. The method of claim 7 wherein a tag for table T(N−2) comprises a hashtag.
9. The method of claim 7 wherein the index for table T(N−1) is used as a tag for table T(N−2).
10. The method of claim 9 wherein the tag for table T(N−2) comprises a hashtag.
11. The method of claim 1 further comprising updating the contents of the N tables, based on the one or more hits occurring.
12. The method of claim 11 wherein the contents of the N tables include branch histories.
13. The method of claim 11 wherein the contents of the N tables include one or more hysteresis counters.
14. The method of claim 11 wherein the contents of the N tables include one or more prediction counters.
15. The method of claim 1 further comprising populating one or more of the N tables based on runtime sampling of instruction branches.
16. The method of claim 1 wherein the first branch prediction is based on a prediction model.
17. The method of claim 16 wherein the prediction model adapts over time based on a rate of prediction matches.
18. The method of claim 1 wherein the size of two or more of the N tables is different.
19. The method of claim 1 wherein the processor address that was manipulated is used as a fetch address.
20. A computer program product embodied in a non-transitory computer readable medium for address manipulation, the computer program product comprising code which causes one or more processors to perform operations of:
generating a first index from one or more bits of a processor program counter, wherein the first index is used to access a branch predictor bimodal table;
providing a first branch prediction from the bimodal table, based on the first index;
matching the first branch prediction against N tables, wherein N is three or more, wherein the tables contain prior branch histories, and wherein:
the branch history in table T(N) is of greater length than the branch history of table T(N−1); and
the branch history in table T(N−1) is of greater length than the branch history of table T(N−2);
manipulating a processor address using a greatest length of hits of branch prediction matches from the N tables, based on one or more hits occurring; and
manipulating the branch predictor address using the first branch prediction from the bimodal table, based on zero hits occurring.
21. A computer system for address manipulation comprising:
a memory which stores instructions;
one or more processors attached to the memory wherein the one or more processors, when executing the instructions which are stored, are configured to:
generate a first index from one or more bits of a processor program counter, wherein the first index is used to access a branch predictor bimodal table;
provide a first branch prediction from the bimodal table, based on the first index;
match the first branch prediction against N tables, wherein N is three or more, wherein the tables contain prior branch histories, and wherein:
the branch history in table T(N) is of greater length than the branch history of table T(N−1); and
the branch history in table T(N−1) is of greater length than the branch history of table T(N−2);
manipulate a processor address using a greatest length of hits of branch prediction matches from the N tables, based on one or more hits occurring; and
manipulate the branch predictor address using the first branch prediction from the bimodal table, based on zero hits occurring.