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 method 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 a plurality of N tables, wherein:
each of the plurality of N tables contain prior branch histories;
the branch history in table T(N) is of greater length than the branch history of table T(N-1);
determining, for each of the plurality of N tables, a number of hits for that table, each hit comprising a match between the prior branch history in that table and the first branch prediction;
when a number of hits for at least one table is greater than zero, then manipulating a processor address according to one or more predictions from the table that has the greatest number of hits.
2. The method of claim 1 , further comprising when the number of hits for each table is not greater than zero, then manipulating a branch predictor address according to the first branch prediction from the bimodal table.
3. The method of claim 1 , further comprising updating content in the plurality of N tables based on the hits.
4. The method of claim 3 , wherein the content comprises the prior branch histories.
5. The method of claim 3 , wherein the content comprises one or more hysteresis counters.
6. The method of claim 3 , wherein the content comprises one or more prediction counters.
7. A system comprising one or more processors and a non-transitory computer readable storage media embodying instructions coupled to the one or more processors, the one or more processors operable to execute the instructions 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 a plurality of N tables, wherein:
each of the plurality of N tables contain prior branch histories;
the branch history in table T(N) is of greater length than the branch history of table T(N-1);
determine, for each of the plurality of N tables, a number of hits for that table, each hit comprising a match between the prior branch history in that table and the first branch prediction;
when a number of hits for at least one table is greater than zero, then manipulate a processor address according to one or more predictions from the table that has the greatest number of hits.
8. The system of claim 7 , wherein the processors are further operable to execute the instructions to, when the number of hits for each table is not greater than zero, then manipulate a branch predictor address according to the first branch prediction from the bimodal table.
9. The system of claim 7 , wherein the processors are further operable to execute the instructions to update content in the plurality of N tables based on the hits.
10. The system of claim 9 , wherein the content comprises the prior branch histories.
11. The system of claim 9 , wherein the content comprises one or more hysteresis counters.
12. The system of claim 9 , wherein the content comprises one or more prediction counters.
13. The system of claim 7 wherein the processors are further operable to execute the instructions to populate one or more of the N tables based on runtime sampling of instruction branches.
14. One or more non-transitory computer readable storage media embodying instructions and coupled to one or more processors that are operable to execute the instructions 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 a plurality of N tables, wherein:
each of the plurality of N tables contain prior branch histories;
the branch history in table T(N) is of greater length than the branch history of table T(N-1);
determine, for each of the plurality of N tables, a number of hits for that table, each hit comprising a match between the prior branch history in that table and the first branch prediction;
when a number of hits for at least one table is greater than zero, then manipulate a processor address according to one or more predictions from the table that has the greatest number of hits.
15. The media of claim 14 , wherein the processors are further operable to execute the instructions to, when the number of hits for each table is not greater than zero, then manipulate a branch predictor address according to the first branch prediction from the bimodal table.
16. The media of claim 14 , wherein the processors are further operable to execute the instructions to update content in the plurality of N tables based on the hits.
17. The media of claim 16 , wherein the content comprises the prior branch histories.
18. The media of claim 16 , wherein the content comprises one or more hysteresis counters.
19. The media of claim 16 , wherein the content comprises one or more prediction counters.
20. The media of claim 14 , wherein the processors are further operable to execute the instructions to populate one or more of the N tables based on runtime sampling of instruction branches.