Branch target buffer allocation
View Patent ↗A data processing system and method are provided for allocating an entry in a branch target buffer (BTB). The method comprises: receiving a branch instruction to be executed in a data processor; determining that the BTB does not include an entry corresponding to the branch instruction; identifying an entry in the BTB for allocation, the identified entry in the BTB comprising a target identifier and a first prediction value for a previously received branch instruction; determining whether to allocate the branch instruction to the identified entry in the BTB based on a comparison of the first prediction value to a second prediction value, wherein the second prediction value is generated from a branch history table (BHT); and allocating the branch instruction to the identified entry if the second prediction value indicates a more strongly taken prediction than the first prediction value.
1. A method for allocating an entry of a plurality of entries in a branch target buffer (BTB), the method comprising:
receiving a branch instruction to be executed in a data processor;
determining that the BTB does not include an entry corresponding to the branch instruction;
identifying an entry in the BTB for allocation, the identified entry in the BTB comprising a target identifier and a first prediction value for a previously received branch instruction; and
determining whether to allocate the branch instruction to the identified entry in the BTB based on a comparison of the first prediction value to a second prediction value,
wherein the second prediction value is based on outcomes of a plurality of previous instruction branches.
2. The method of claim 1 , wherein the step of determining is further characterized by the second prediction value being generated from a branch history table (BHT).
3. The method of claim 2 , further comprising allocating the branch instruction to the identified entry if the second prediction value indicates a more strongly taken prediction than the first prediction value.
4. The method of claim 2 , further comprising shifting a plurality of bits into a branch history register, wherein each bit of the plurality of bits indicates a result of a branch instruction, and wherein one or more of the plurality of bits are used in creating an index to address the BHT.
5. The method of claim 2 , further comprising updating the BHT when a change-of-instruction-flow occurs as a result of the branch instruction.
6. The method of claim 1 , wherein allocating the branch instruction to the identified entry further comprises not allocating the branch instruction to the identified entry if the second prediction value indicates that the branch is not likely to be taken.
7. The method of claim 1 , further comprising:
generating a prediction confidence value based on a number of correct predictions;
combining the prediction confidence value with the second prediction value to generate a third prediction value; and
using the third prediction value to determine whether to allocate the branch instruction to the identified entry.
8. The method of claim 1 , wherein the second prediction value comprises a two-bit prediction value for indicating one of a strongly not-taken state, a weakly not-taken state, a weakly taken state, and a strongly taken state.
9. A method for allocating an entry of a plurality of entries in a branch target buffer (BTB), the method comprising:
receiving a branch instruction to be executed in a data processor;
determining that the BTB does not include an entry corresponding to the branch instruction;
identifying an entry in the BTB for allocation, the identified entry in the BTB comprising a target identifier and a first prediction value for a previously received branch instruction; and
determining whether to allocate the branch instruction to the identified entry in the BTB based on a comparison of the first prediction value to a second prediction value,
wherein the first prediction value comprises a two-bit prediction value for indicating one of a strongly not-taken state, a weakly not-taken state, a weakly taken state, and a strongly taken state.
10. A method for allocating an entry of a plurality of entries in a branch target buffer (BTB) in a data processing system, the method comprising:
receiving a plurality of instructions to be executed in the data processing system, the plurality of instructions comprising one or more branch instructions;
generating a branch history table (BHT), wherein the BHT is based on an accumulation of change-of-instruction-flow results during instruction execution of the plurality of instructions, wherein the accumulation of change-of-instruction-flow results are used to generate a first prediction value;
receiving a first branch instruction to be executed in the data processing system;
determining that the BTB does not include an entry corresponding to the first branch instruction;
identifying an entry in the BTB for allocation, the identified entry in the BTB comprising a second prediction value for a second branch instruction;
determining whether to allocate the first branch instruction to the identified entry in the BTB based on a comparison of the first prediction value to the second prediction value; and
allocating the first branch instruction to the identified entry if the first prediction value indicates a more strongly taken prediction than the second prediction value, and not allocating the entry to the second branch instruction if the first prediction value indicates a more strongly not taken prediction than the second prediction value.
11. The method of claim 10 , further comprising:
generating a prediction confidence value based on a number of correct predictions in the data processing system;
combining the prediction confidence value with the first prediction value to generate a third prediction value; and
using the third prediction value to determine whether to allocate the branch instruction to the identified entry.
12. The method of claim 10 , wherein the first prediction value comprises a two-bit prediction value for indicating one of a strongly not-taken state, a weakly not-taken state, a weakly taken state, and a strongly taken state.
13. The method of claim 10 , wherein the second prediction value comprises a two-bit prediction value for indicating one of a strongly not-taken state, a weakly not-taken state, a weakly taken state, and a strongly taken state.
14. The method of claim 10 , further comprising shifting a plurality of bits into a branch history register, wherein each bit of the plurality of bits indicates a result of a branch instruction, and wherein at least one of the plurality of bits is used to generate an index to address the BHT.
15. A data processing system comprising:
processing logic for executing instructions;
a branch target buffer (BTB) coupled to the processing logic, the BTB having a plurality of entries, an entry of the plurality of entries comprising a first prediction value corresponding to a first branch instruction;
a BTB controller, coupled to the BTB, for selecting an entry of the plurality of entries is to be replaced;
a branch history table (BHT), coupled to the processing logic, for providing a second prediction value based on an accumulation of change-of-instruction-flow results during execution of the plurality of instructions, the second prediction value corresponding to a second branch instruction; and
BTB replacement allocation logic coupled to the BTB for receiving the first prediction value and to the BHT for receiving the second prediction value, the BTB replacement allocation logic for performing a comparison of the first prediction value to the second prediction value, and for causing the entry of the plurality of entries to be allocated to the second branch instruction based on the comparison.
16. The data processing system of claim 15 , further comprising a confidence predictor coupled to the BTB replacement allocation logic, the confidence predictor for generating a prediction confidence value based on a number of correct branch predictions, wherein the prediction confidence value is combined with the second prediction value to generate a third prediction value, and wherein the third prediction value is used to determine whether to allocate the entry of the plurality of entries to the second branch instruction.
17. The data processing system of claim 15 , wherein the first prediction value comprises a two-bit prediction value for indicating one of a strongly not-taken state, a weakly not-taken state, a weakly taken state, and a strongly taken state.
18. The data processing system of claim 15 , wherein the second prediction value comprises a two-bit prediction value for indicating one of a strongly not-taken state, a weakly not-taken state, a weakly taken state, and a strongly taken state.
19. The data processing system of claim 15 , wherein when the comparison determines that if the second prediction value indicates a more strongly taken value than the first prediction value, the entry of the plurality of entries is allocated for the second branch instruction.