Systems and methods for reducing branch misprediction penalty
View Patent ↗In a processing system capable of single and multi-thread execution, a branch prediction unit can be configured to detect hard to predict branches and loop instructions. In a dual-threading (simultaneous multi-threading) configuration, one instruction queues (IQ) is used for each thread and instructions are alternately sent from each IQ to decode units. In single thread mode, the second IQ can be used to store the “not predicted path” of the hard-to-predict branch or the “fall-through” path of the loop. On mis-prediction, the mis-prediction penalty is reduced by getting the instructions from IQ instead of instruction cache.
1. In a data processing system having an instruction fetch unit, a decode unit, and a branch execution unit, the instruction fetch unit being coupled to a branch target buffer (BTB), and having a first instruction queue for providing instructions to the decode unit, and a second instruction queue for providing instructions to the decode unit, the decode unit issuing instructions for execution, a method comprising:
in single thread mode:
providing a first instruction address to the instruction fetch unit;
fetching a first instruction from the first instruction address and storing the first instruction in the first instruction queue;
determining whether the first instruction address hits in the BTB;
in response to determining that the first instruction address hits in the BTB, using an entry in the BTB which resulted in the hit to determine whether the first instruction is a conditional branch and whether it is predicted as a taken branch or a non-taken branch;
in response to determining that the first instruction is a conditional branch and predicted as a taken branch:
providing a target address from the entry in the BTB to the instruction fetch unit;
fetching a second instruction from the target address and storing the second instruction in the first instruction queue; and
fetching one or more sequential instructions which are sequential to the first instruction and storing the one or more sequential instructions in the second instruction queue; and
in response to determining that the first instruction is a conditional branch and predicted as a non-taken branch:
providing the target address from the entry in the BTB to the instruction fetch unit;
fetching a third instruction fetched from the target address and storing the third instruction in the second instruction queue;
providing a sequential address to the first instruction to the instruction fetch unit; and
storing a fourth instruction fetched from the sequential address in the first instruction queue;
providing the first instruction from the first instruction queue to the decode unit; and
issuing the first instruction from the decode unit for execution, wherein
the branch execution unit resolves the first instruction to determine if the prediction made using the entry in the BTB is correct or mispredicted, and
if the first instruction is a conditional branch, providing an identifier with the first instruction to the decode unit and the branch execution unit, wherein the identifier identifies a location in the second instruction queue of one or more instructions which are to be executed if the first instruction is mispredicted.
2. The method of claim 1 , wherein: if the first instruction is a conditional branch and predicted as a taken branch, the identifier identifies a location in the second instruction queue of the one or more sequential instructions; and if the first instruction is a conditional branch and predicted as a not-taken branch, the identifier identifies a location in the second instruction queue of the fourth instruction.
3. The method of claim 1 , further comprising: if the branch execution unit determines that the first instruction is mispredicted, using the identifier to provide the one or more instructions from the second instruction queue to the decode unit for execution.
4. The method of claim 3 , further comprising:
if the branch execution unit determines that the first instruction is predicted correctly, invalidating the one or more instructions in the second instruction queue indicated by the identifier.
5. Them method of claim 4 , further comprising:
if the branch execution unit determines that the first instruction is predicted correctly, invalidating the identifier.
6. The method of claim 1 , wherein the conditional branch is further characterized as one of a hard-to-predict branch or a loop instruction.
7. The method of claim 6 , wherein the first instruction is determined to be a conditional branch that is characterized as one of a hard-to-predict branch or a loop instruction based on the entry in the BTB which resulted in the hit.
8. The method of claim 1 , further comprising:
in response to determining that the first instruction misses in the BTB, fetching one or more sequential instructions which are sequential to the first instruction and storing the one or more sequential instruction in the first instruction queue.
9. A data processing system, comprising:
a branch execution unit;
a decode unit coupled to the branch execution unit, the decode unit issuing instructions for execution;
an instruction fetch unit coupled to a branch target buffer (BTB), the instruction fetch unit having a first instruction queue for providing instructions to the decode unit, and a second instruction queue for providing instructions to the decode unit, wherein during single thread mode, the instruction fetch unit:
fetches a first instruction from a first instruction address and stores the first instruction in the first instruction queue;
determines whether the first instruction address hits in the BTB, and in response to determining that the first instruction address hits in the BTB, using an entry in the BTB which resulted in the hit to determine whether the first instruction is a conditional branch and whether it is predicted as a taken branch or a non-taken branch;
in response to determining that the first instruction is a conditional branch and predicted as a taken branch:
obtaining a target address from the entry in the BTB;
fetching a second instruction from the target address and storing the second instruction in the first instruction queue; and
fetching one or more sequential instructions which are sequential to the first instruction and storing the one or more sequential instruction in the second instruction queue; and
in response to determining that the first instruction is a conditional branch and predicted as a non-taken branch:
obtaining the target address from the entry in the BTB;
fetching the second instruction from the target address and storing the second instruction in the second instruction queue;
fetching a third instruction from a sequential address that is sequential to the first instruction address; and
storing the third instruction in the first instruction queue,
wherein:
the instruction fetch unit provides the first instruction from the first instruction queue to the decode unit; and
the decode unit issues the first instruction for execution, wherein the branch execution unit resolves the first instruction to determine if the prediction made using the entry in the BTB is correct or mispredicted; and
storage circuitry, wherein when the instruction fetch unit determines that the first instruction is a conditional branch, an identifier is stored in the storage circuitry to identify a location in the second instruction queue of one or more instructions which are to be executed if the first instruction is resolved as mispredicted.
10. The data processing system of claim 9 , wherein: if the branch execution unit determines that the first instruction is mispredicted, the instruction fetch unit uses the identifier to provide the one or more instructions from the second instruction queue to the decode unit for execution; and if the branch execution unit determines that the first instruction is predicted correctly, the instruction fetch unit uses the identifier to invalidate the one or more instructions in the second instruction queue.
11. The data processing system of claim 9 , wherein the conditional branch is further characterized as one of a hard-to-predict branch or a loop instruction, wherein the instruction fetch unit uses the entry in the BTB which resulted in the hit to characterize the conditional branch as one of a hard-to-predict branch or a loop instruction.
12. In a data processing system having an instruction fetch unit, a decode unit, and a branch execution unit, the instruction fetch unit having a branch target buffer (BTB), a first instruction queue for providing instructions to the decode unit, and a second instruction queue for providing instructions to the decode unit, the decode unit issuing instructions for execution, a method comprising:
in single thread mode:
providing a first instruction address to the instruction fetch unit;
fetching a first instruction from the first instruction address and storing the first instruction in the first instruction queue;
determining whether the first instruction address hits in the BTB;
in response to determining that the first instruction address hits in the BTB:
using an entry in the BTB which resulted in the hit to determine whether the first instruction is predicted as a taken branch or a non-taken branch, and
determining whether the first instruction is a hard-to-predict branch;
in response to determining that the first instruction is predicted as a taken branch and is a hard-to-predict branch:
providing a target address from the entry in the BTB to the instruction fetch unit;
fetching a second instruction from the target address and storing the second instruction in the first instruction queue; and
fetching one or more sequential instructions which are sequential to the first instruction and storing the one or more sequential instruction in the second instruction queue; and
in response to determining that the branch instruction is predicted as a non-taken branch and is a hard-to-predict branch:
providing the target address from the entry in the BTB to the instruction fetch unit;
fetching a third instruction fetched from the target address and storing the third instruction in the second instruction queue;
providing a sequential address to the first instruction to the instruction fetch unit; and
storing a fourth instruction fetched from the sequential address in the first instruction queue;
providing the first instruction from the first instruction queue to the decode unit, and if the first instruction is a hard-to-predict branch, providing an identifier with the first instruction to the decode unit and the branch execution unit, wherein the identifier identifies a location in the second instruction queue of one or more instructions which are to be executed if the first instruction is mispredicted; and
issuing the first instruction from the decode unit for execution, wherein the branch execution unit resolves the first instruction to determine if the prediction made using the entry in the BTB is correct or mispredicted.
13. The method of claim 12 , wherein: if the first instruction is a hard-to-predict branch and predicted as a taken branch, the identifier identifies a location in the second instruction queue of the one or more sequential instructions; and if the first instruction is a hard-to-predict branch and predicted as a not-taken branch, the identifier identifies a location in the second instruction queue of the fourth instruction.
14. The method of claim 12 , further comprising: if the branch execution unit determines that the first instruction is mispredicted, using the identifier to provide the one or more instructions from the second instruction queue to the decode unit for execution; and if the branch execution unit determines that the first instruction is predicted correctly, invalidating the one or more instructions in the second instruction queue indicated by the identifier.