Next fetch predictor for trace cache
Disclosed techniques relate to next fetch predictor circuitry configured to operate in conjunction with a trace cache. The trace cache circuitry may identify and store traces of instructions based on predicted directions of one or more control transfer instructions. Trace next fetch predictor circuitry may predict a next fetch address based on a current fetch address for a current cycle, which may include predicting a next fetch address following execution of a first trace stored in the trace cache circuitry. The first trace may include multiple fetch groups and multiple control transfer instructions. Arbitration circuitry may select from among multiple predictors and the trace next fetch predictor may have priority in response to a trace cache hit. Disclosed techniques may advantageously improve overall fetch bandwidth in the context of trace cache hits.
1. An apparatus, comprising:
processor circuitry configured to execute control transfer instructions;
prediction circuitry configured to predict directions of control transfer instructions based on branch history values;
trace cache circuitry configured to identify and store traces of instructions based on predicted directions of one or more control transfer instructions; and
trace next fetch predictor circuitry configured to predict a next fetch address based on a current fetch address, including to predict a next fetch address following execution of a first trace stored in the trace cache circuitry, wherein the first trace includes multiple fetch groups and multiple taken control transfer instructions; wherein:
the prediction circuitry is configured to track directions of executed control transfer instructions, including:
a first category of control transfer instructions that meet a threshold bias level toward a given direction; and
a second category of control transfer instructions that do not meet the threshold bias level;
the trace cache circuitry is configured to identify and store traces of instructions that satisfy a set of criteria, including:
a given trace includes at least one internal taken control transfer instruction;
a conditional control transfer instruction is allowed as an internal trace instruction only if it meets the threshold bias level; and
a control transfer instruction in the second category is allowed only as a last control transfer instruction in a given trace.
2. The apparatus of claim 1 , further comprising:
control circuitry configured to:
pre-compute branch history update information based on multiple taken branches in the first trace;
store the branch history update information in the trace next fetch predictor circuitry; and
retrieve the branch history update information in response to a hit in the trace next fetch predictor circuitry.
3. The apparatus of claim 2 , wherein the control circuitry is further configured to:
hash the retrieved branch history update information with a current branch history value to generate an updated branch history value.
4. The apparatus of claim 3 , wherein pre-computation includes to perform:
one or more hash operations on address information associated with a given taken branch; and
one or more left-shift operations.
5. The apparatus of claim 3 , wherein the stored branch history update information is encoded using a smaller number of bits than the current branch history value.
6. The apparatus of claim 1 , wherein the trace cache circuitry and the trace next fetch predictor circuitry are indexed and tagged using at least a portion of the same sets of bits of the current fetch address.
7. The apparatus of claim 1 , wherein:
the trace next fetch predictor circuitry is configured to predict the next fetch address in response to a hit for the current fetch address on a trace stored in the trace cache circuitry; and
the trace next fetch predictor circuitry is configured to initiate a tag check to the trace cache circuitry based on the predicted next fetch address.
8. The apparatus of claim 1 , further comprising:
non-trace next fetch predictor circuitry configured to predict the next fetch address based on the current fetch address; and
control circuitry configured to select a prediction by the trace next fetch predictor circuitry in response to hits in both the trace next fetch predictor circuitry and the non-trace next fetch predictor circuitry.
9. The apparatus of claim 1 , wherein the trace next fetch predictor circuitry is configured to predict a next fetch address for an immediately-subsequent cycle to the cycle in which a fetch is performed using the current fetch address.
10. The apparatus of claim 1 , wherein the apparatus is a computing device that further includes:
a central processing unit;
a display; and
network interface circuitry.
11. A method, comprising:
executing, by a computing system, a program that includes control transfer instructions;
predicting, by the computing system, directions of control transfer instructions based on branch history values;
identifying and storing in a trace cache, by the computing system, traces of instructions based on predicted directions of one or more control transfer instructions;
predicting, by the computing system, a next fetch address based on a current fetch address, wherein the predicting predicts a next fetch address following execution of a first trace stored in the trace cache, wherein the first trace includes multiple fetch groups and multiple taken control transfer instructions; and
tracking directions of executed control transfer instructions, including:
a first category of control transfer instructions that meet a first threshold bias level toward a given direction; and
a second category of control transfer instructions that do not meet the first threshold bias level;
wherein the identifying includes identifying traces of instructions that satisfy a set of criteria, including:
a given trace includes at least one internal taken control transfer instruction;
a conditional control transfer instruction is allowed as an internal trace instruction only if it meets the threshold bias level; and
a control transfer instruction in the second category is allowed only as a last control instruction in a given trace.
12. The method of claim 11 , further comprising:
pre-computing, by the computing system, branch history update information based on multiple taken branches in the first trace;
storing, by the computing system, the branch history update information; and
retrieving, by the computing system, the branch history update information in response to a hit in a next fetch predictor table.
13. The method of claim 12 , further comprising:
hashing, by the computing system, the retrieved branch history update information with a current branch history value to generate an updated branch history value.
14. The method of claim 13 , wherein the pre-computing includes performing one or more left shift operations and one or more hash operations.
15. The method of claim 13 , wherein the stored branch history update information is encoded using a smaller number of bits than the current branch history value.
16. The method of claim 11 ,
wherein the predicting is in response to a hit for the current fetch address on a trace stored in the trace cache; and
wherein the method further includes initiating a tag check to the trace cache based on the predicted next fetch address.
17. The method of claim 11 , further comprising:
predicting multiple next fetch addresses based on the current fetch address using multiple different next fetch predictors; and
selecting a prediction from a trace next fetch predictor based on a hit in the trace cache.
18. The method of claim 11 , wherein the predicting is of a next fetch address for an immediately-subsequent cycle to the cycle in which a fetch is performed using the current fetch address.
19. A non-transitory computer-readable medium having instructions of a hardware description programming language stored thereon that, when processed by a computing system, program the computing system to generate a computer simulation model, wherein the model represents a hardware circuit that includes:
processor circuitry configured to execute control transfer instructions;
prediction circuitry configured to predict directions of control transfer instructions based on branch history values;
trace cache circuitry configured to identify and store traces of instructions based on predicted directions of one or more control transfer instructions; and
trace next fetch predictor circuitry configured to predict a next fetch address based on a current fetch address, including to predict a next fetch address following execution of a first trace stored in the trace cache circuitry, wherein the first trace includes multiple fetch groups and multiple taken control transfer instructions; wherein:
the prediction circuitry is configured to track directions of executed control transfer instructions, including:
a first category of control transfer instructions that meet a threshold bias level toward a given direction; and
a second category of control transfer instructions that do not meet the threshold bias level;
the trace cache circuitry is configured to identify and store traces of instructions that satisfy a set of criteria, including:
a given trace includes at least one internal taken control transfer instruction;
a conditional control transfer instruction is allowed as an internal trace instruction only if it meets the threshold bias level; and
a control transfer instruction in the second category is allowed only as a last control transfer instruction in a given trace.
20. The non-transitory computer-readable medium of claim 19 , wherein the model further represents a hardware circuit that includes:
control circuitry configured to:
pre-compute branch history update information based on multiple taken branches in the first trace;
store the branch history update information in the trace next fetch predictor circuitry; and
retrieve the branch history update information in response to a hit in the trace next fetch predictor circuitry.