BRANCH PREDICTION IN A DATA PROCESSING APPARATUS

• US 20170139717A1
• Filed: 10/26/2016
• Published: 05/18/2017
• Est. Priority Date: 11/17/2015
• Status: Active Grant

• Current Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Original Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Inventors: HORNUNG, Alexander Alfred, POPESCU, Adrian Viorel
• Granted Patent: US 11,481,220 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/323 for indirect branch instructions
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

An apparatus comprises instruction fetch circuitry to retrieve instructions from storage and branch target storage to store entries comprising source and target addresses for branch instructions. A confidence value is stored with each entry and when a current address matches a source address in an entry, and the confidence value exceeds a confidence threshold, instruction fetch circuitry retrieves a predicted next instruction from a target address in the entry. Branch confidence update circuitry increases the confidence value of the entry on receipt of a confirmation of the target address and decreases the confidence value on receipt of a non-confirmation of the target address. When the confidence value meets a confidence lock threshold below the confidence threshold and non-confirmation of the target address is received, a locking mechanism with respect to the entry is triggered. A corresponding method is also provided.

Claims

1. Apparatus comprising:

instruction fetch circuitry to retrieve instructions from storage by reference to addresses at which the instructions are stored;

branch target storage to store entries comprising source and target addresses for branch instructions, wherein the branch target storage is capable of storing a confidence value associated with an entry and the branch target storage is responsive to a current address matching a source address in the entry and the confidence value exceeding a confidence threshold to issue a signal to the instruction fetch circuitry to retrieve a predicted next instruction from a target address in the entry; and

branch confidence update circuitry to increase the confidence value of the entry in response to receipt of a confirmation of the target address and to decrease the confidence value of the entry in response to receipt of a non-confirmation of the target address,

wherein the branch confidence update circuitry is responsive to the confidence value meeting a confidence lock threshold below the confidence threshold and receipt of the non-confirmation of the target address to trigger a locking mechanism with respect to the entry.

2. The apparatus as claimed in claim 1, wherein the locking mechanism marks the entry as a locked entry and the branch confidence update circuitry is responsive to the locked entry to cease further modification of the confidence value of the locked entry.

3. The apparatus as claimed in claim 1, the locking mechanism marks the entry as a locked entry and wherein the branch target storage is responsive to the current address matching the source address in the locked entry to prevent issuance of the signal to the instruction fetch circuitry to retrieve the predicted next instruction from the target address.

4. The apparatus as claimed in claim 1, wherein the locking mechanism comprises lock counter circuitry to hold a lock counter value for the entry and to update the lock counter value towards a lock trigger value in response to the triggering of the locking mechanism, wherein the lock counter value having the lock trigger value indicates that the entry is locked.

5. The apparatus as claimed in claim 4, wherein a range of the confidence value for the entry exceeds a range of the lock value for the entry.

6. The apparatus as claimed in claim 4, wherein the branch confidence update circuitry is responsive to the confidence value reaching a confidence lock release threshold above the confidence lock threshold to abort the locking mechanism and to cause the lock counter circuitry to update the lock value away from the lock trigger value in response to receipt of the confirmation of the target address.

7. The apparatus as claimed in claim 1, wherein the branch target storage is responsive to receipt of the non-confirmation of the target address to update the entry with a confirmed target address for the source address.

8. The apparatus as claimed in claim 1, wherein the branch target storage is responsive to receipt of the non-confirmation of the target address to update the entry with a replacement target address for the source address, wherein the replacement target address is determined from a history of more than one recent confirmed target addresses.

9. The apparatus as claimed in claim 1, further comprising branch target prediction circuitry comprising further branch target storage capable of storing entries comprising target addresses for branch instructions, wherein the further branch target storage is capable of storing at least two different target addresses in association with the source address,

and the branch target prediction circuitry is responsive to the current address corresponding to the source address to select between the at least two target addresses in dependence on history information stored for the current address to provide a target address prediction.

10. The apparatus as claimed in claim 9, wherein the apparatus has a pipeline arrangement and the branch target storage precedes the instruction fetch circuitry in the pipeline arrangement and the branch target prediction circuitry follows the instruction fetch circuitry in the pipeline arrangement.

11. The apparatus as claimed in claim 9, wherein the branch target prediction circuitry comprises target address comparison circuitry to perform a comparison of its target address prediction with the target address from the branch target storage and to signal either the confirmation of the target address or the non-confirmation of the target address in dependence on a result of the comparison.

12. The apparatus as claimed in claim 9, wherein the branch target prediction circuitry comprises a second further branch target storage to store entries comprising source and target addresses for branch instructions, wherein the branch target prediction circuitry is responsive to no entry in the further branch target storage being selected to provide the target address prediction from the second further branch target storage.

13. The apparatus as claimed in claim 9, wherein the branch target prediction circuitry is responsive to no entry in the further branch target storage being selected to provide the target address from the branch target storage as the target address prediction.

14. The apparatus as claimed in claim 1, further comprising branch resolution circuitry to signal the confirmation of the target address or the non-confirmation of the target address in dependence on a branch resolution of a branch instruction stored at the source address.

15. The apparatus as claimed in claim 1, wherein the branch target storage is responsive to the current address matching the source address in the entry and the confidence value not exceeding the confidence threshold to issue a signal to the instruction fetch circuitry to retrieve a next instruction from an address which sequentially follows the current address.

16. A method of data processing comprising:

retrieving instructions from storage by reference to addresses at which the instructions are stored;

storing entries comprising source and target addresses for branch instructions in a branch target storage;

storing a confidence value associated with an entry in the branch target storage;

retrieving a predicted next instruction from a target address in the entry, when a current address matches a source address in the entry and the confidence value exceeds a confidence threshold;

increasing the confidence value in response to receipt of a confirmation of the target address;

decreasing the confidence value of the entry in response to receipt of a non-confirmation of the target address;

triggering a locking mechanism which marks the entry as a locked entry in response to the confidence value meeting a confidence lock threshold below the confidence threshold and receipt of the non-confirmation of the target address.

17. Apparatus comprising:

means for retrieving instructions from storage by reference to addresses at which the instructions are stored;

means for storing entries comprising source and target addresses for branch instructions;

means for storing a confidence value associated with an entry in the means for storing entries;

means for retrieving a predicted next instruction from a target address in the entry, when a current address matches a source address in the entry and the confidence value exceeds a confidence threshold;

means for increasing the confidence value in response to receipt of a confirmation of the target address;

means for decreasing the confidence value of the entry in response to receipt of a non-confirmation of the target address;

means for triggering a locking mechanism which marks the entry as a locked entry in response to the confidence value meeting a confidence lock threshold below the confidence threshold and receipt of the non-confirmation of the target address.