Trace cache with filter for internal control transfer inclusion
Disclosed techniques relate to trace caches. Trace cache circuitry may identify traces that satisfy one or more criteria. Generally, internal branches of a trace should satisfy a threshold bias level in a particular direction. To achieve this goal, the processor may initially assume that branches meet the threshold, track their usefulness in the trace context over time, and prevent inclusion of branches that fall below a usefulness threshold (which indicates that those branches are not sufficiently biased). Branches that do not meet the threshold may be added to a Bloom filter, for example. Usefulness may be tracked during trace training, when valid in a trace cache, or both.
1. An apparatus, comprising:
processor circuitry configured to execute control transfer instructions;
prediction circuitry configured to predict directions of control transfer instructions;
trace cache circuitry configured to identify and store traces of instructions that satisfy one or more criteria, including that a given trace includes at least one internal taken control transfer instruction; and
filter control circuitry configured to:
for a given internal control transfer instruction in a trace stored in the trace cache circuitry, adjust a counter in a first direction in response to the given control transfer instruction executing toward the next portion of the stored trace and adjust the counter in a second direction in response to the given control transfer instruction executing away from the next portion of the stored trace; and
prevent inclusion of the given control transfer instruction as an internal instruction of traces in the trace cache in response to the counter reaching a threshold in the second direction.
2. The apparatus of claim 1 , further comprising control circuitry configured to:
in response to a determined direction for a non-terminating control transfer instruction that exits a trace, discard one or more subsequent instructions of a fetch group that included the non-terminating control transfer instruction and redirect front-end circuitry of the processor circuitry to fetch other instructions.
3. The apparatus of claim 1 , wherein the one or more criteria further include:
that only control transfer instructions of a first category are allowed at one or more positions within a given trace, wherein control transfer instruction of the first category meet a first threshold bias level toward a given direction and control transfer instructions of a second category do not meet the first threshold bias level; and
that control transfer instructions of the second category are allowed only at one or more other positions within the given trace.
4. The apparatus of claim 3 , wherein a given entry in the trace cache circuitry includes a field indicating whether the trace has a non-terminating control transfer instruction in the second category.
5. The apparatus of claim 4 , wherein a given entry in the trace cache circuitry includes a field indicating a position within the trace of the non-terminating control transfer instruction in the second category.
6. The apparatus of claim 1 , wherein:
the filter control circuitry is configured to adjust the counter by a greater amount in the second direction than in the first direction.
7. The apparatus of claim 1 , further comprising:
an instruction cache;
wherein:
the prediction circuitry is configured to share prediction table entries and prediction lane circuitry for instruction cache and trace cache hits; and
the apparatus includes selection circuitry configured to select a prediction lane output from the prediction circuitry based on a position of a corresponding control transfer instruction within a trace.
8. The apparatus of claim 1 , wherein:
to prevent inclusion of the given control transfer instruction, the filter control circuitry is configured to access a Bloom filter using a program counter associated with the given control transfer instruction; and
the filter control circuitry is configured to clear the Bloom filter periodically.
9. 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.
10. A method, comprising:
executing, by a computing device, control transfer instructions;
predicting, by the computing device, directions of executed control transfer instructions;
identifying and storing in a trace cache, by the computing device, traces of instructions that satisfy one or more criteria, including that a given trace includes at least one internal taken control transfer instruction;
for a given internal control transfer instruction in a trace stored in the trace cache, the computing device adjusting a counter in a first direction in response to the given control transfer instruction executing toward the next portion of the stored trace and adjusting the counter in a second direction in response to a given control transfer instruction executing away from the next portion of the stored trace; and
preventing, by the computing device, inclusion of the given control transfer instruction as an internal instruction of traces in the trace cache in response to the counter reaching a threshold in the second direction.
11. The method of claim 10 , further comprising:
in response to a determined direction for a non-terminating control transfer instruction that exits a trace, discard one or more subsequent instructions of a fetch group that included the non-terminating control transfer instruction and redirect front-end circuitry of the computing device to fetch other instructions.
12. The method of claim 10 , wherein the one or more criteria further include:
that only control transfer instructions of a first category are allowed at one or more positions within a given trace, wherein control transfer instruction of the first category meet a first threshold bias level toward a given direction and control transfer instructions of a second category do not meet the first threshold bias level; and
that control transfer instructions of the second category are allowed only at one or more other positions within the given trace.
13. The method of claim 12 , wherein a given entry in the trace cache includes a field indicating whether the trace has a non-terminating control transfer instruction in the second category.
14. The method of claim 13 , wherein a given entry in the trace cache includes a field indicating a position within the trace of the non-terminating control transfer instruction in the second category.
15. The method of claim 10 , wherein the adjusting the counter in the first direction is by a greater amount than the adjusting the counter in the second direction.
16. The method of claim 10 , further comprising:
sharing a prediction table field in a branch predictor for instruction cache and trace cache hits.
17. The method of claim 10 , wherein the preventing includes accessing a Bloom filter using a program counter associated with the given control transfer instruction.
18. 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;
trace cache circuitry configured to identify and store traces of instructions that satisfy one or more criteria, including that a given trace includes at least one internal taken control transfer instruction; and
filter control circuitry configured to:
for a given internal control transfer instruction in a trace stored in the trace cache circuitry, adjust a counter in a first direction in response to the given control transfer instruction executing toward the next portion of the stored trace and adjust the counter in a second direction in response to the given control transfer instruction executing away from the next portion of the stored trace; and
prevent inclusion of the given control transfer instruction as an internal instruction of traces in the trace cache in response to the counter reaching a threshold in the second direction.
19. The non-transitory computer-readable medium of claim 18 , wherein the one or more criteria further include:
that only control transfer instructions of a first category are allowed at one or more positions within a given trace, wherein control transfer instruction of the first category meet a first threshold bias level toward a given direction and control transfer instructions of a second category do not meet the first threshold bias level; and
that control transfer instructions of the second category are allowed only at one or more other positions within the given trace.
20. The non-transitory computer-readable medium of claim 18 , wherein:
to prevent inclusion of the given control transfer instruction, the filter control circuitry is configured to access a Bloom filter using a program counter associated with the given control transfer instruction; and
the filter control circuitry is configured to clear the Bloom filter periodically.