Branch target look up suppression

Patent metadata

Field	Value
Publication number	US-11029959-B2
Application number	US-201816120674-A
Country	US
Kind code	B2
Filing date	Sep 4, 2018
Priority date	Sep 4, 2018
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

Branch prediction circuitry processes blocks of instructions and provides instruction fetch circuitry with indications of predicted next blocks of instructions to be retrieved from memory. Main branch target storage stores branch target predictions for branch instructions in the blocks of instructions. Secondary branch target storage caches the branch target predictions from the main branch target storage. Look-ups in the secondary branch target storage and the main branch target storage are performed in parallel. The main branch target storage is set-associative and an entry in the main branch target storage comprises multiple ways, wherein each way of the multiple ways stores a branch target prediction for one branch instruction. The branch prediction circuitry stores a way prediction for which of the multiple ways contain the branch target predictions for a predicted next block of instructions and stores a flag associated with the way prediction indicating whether all branch target predictions stored for the predicted next block of instructions in the main branch target storage are also stored in the secondary branch target storage. An active value of the flag suppresses the look-up in the main branch target storage for the predicted next block of instructions.

First claim

We claim:

1. An apparatus comprising:
instruction fetch circuitry to fetch a block of instructions from memory;
branch prediction circuitry to process the block of instructions and provide the instruction fetch circuitry with an indication of a predicted next block of instructions to be retrieved from memory, the branch prediction circuitry comprising:
main branch target storage to store branch target predictions for branch instructions in the block of instructions; and
secondary branch target storage to cache the branch target predictions from the main branch target storage, wherein the branch prediction circuitry is configured to initiate a look-up in the secondary branch target storage in parallel with a look-up in the main branch target storage,

wherein the main branch target storage is set-associative and an entry in the main branch target storage corresponding to the block of instructions comprises multiple ways, wherein each way of the multiple ways is configured to store a branch target prediction for one branch instruction in the block of instructions; and
wherein the branch prediction circuitry is arranged to store a way prediction for which of the multiple ways contain the branch target predictions for the predicted next block of instructions and to store a flag associated with the way prediction indicating whether all branch target predictions stored for the predicted next block of instructions in the main branch target storage are also stored in the secondary branch target storage,
and wherein the branch prediction circuitry is responsive to an active value of the flag to suppress the look-up in the main branch target storage for the predicted next block of instructions,
wherein the branch prediction circuitry comprises branch outcome prediction circuitry to generate a prediction of whether each of the branch instructions in the block of instructions will be taken or not-taken, and wherein the predicted next block of instructions to be processed:
begins at the branch target prediction for a first branch instruction in the block of instructions predicted to be taken by the branch outcome prediction circuitry; and
begins at a next sequential instruction after the block of instructions, when the branch target prediction does not predict any taken branch instructions in the block of instructions;

the apparatus further comprising way prediction storage and the branch prediction circuitry is arranged to store the way prediction and the flag in an entry of the way prediction storage associated with the block of instructions when the predicted next block of instructions sequentially follows the block of instructions,
wherein the branch prediction circuitry comprises multiple pipelined stages and the branch prediction circuitry is arranged to read out entries in parallel from the secondary branch target storage and the way prediction storage at a first stage of the multiple pipelined stages, and the branch prediction circuitry is responsive to the prediction generated by the branch outcome prediction circuitry to select between the entries read out in parallel from the secondary branch target storage and the way prediction storage.

2. The apparatus as claimed in claim 1 , comprising way prediction storage and the branch prediction circuitry is arranged to store the way prediction and the flag in an entry of the way prediction storage associated with the block of instructions when the predicted next block of instructions sequentially follows the block of instructions.

3. The apparatus as claimed in claim 1 , wherein the branch prediction circuitry is arranged to store the way prediction and the flag in association with a branch target prediction cached in the secondary branch target storage when the predicted next block of instructions begins with a target instruction of the branch target prediction and a source branch instruction of the branch target prediction in the block of instructions is predicted to be taken.

4. The apparatus as claimed in claim 1 , wherein the branch prediction circuitry is arranged to determine a flag setting condition to be true when the main branch target storage has at most one branch target prediction for one branch instruction in the block of instructions and the at most one branch target prediction is cached in the secondary branch target storage, and the branch prediction circuitry is responsive to the flag setting condition being true to set the active value of the flag associated with the way prediction.

5. The apparatus as claimed in claim 1 , wherein a storage capacity of the secondary branch target storage is less than a storage capacity of the main branch target storage.

6. The apparatus as claimed in claim 5 , wherein each entry in the secondary branch target storage comprises a single branch target prediction for the block of instructions.

7. The apparatus as claimed in claim 1 , wherein the branch prediction circuitry is responsive to the way prediction indicating that none of the multiple ways contains branch target predictions for the predicted next block of instructions to suppress the look-up in the main branch target storage for the predicted next block of instructions.

8. The apparatus as claimed in claim 1 , wherein the branch prediction circuitry is responsive to the way prediction to suppress activation of ways indicated by the way prediction as not containing branch target predictions for the predicted next block of instructions when the predicted next block of instructions is processed by the branch prediction circuitry.

9. The apparatus as claimed in claim 1 , wherein the branch prediction circuitry comprises multiple pipelined stages, wherein the multiple pipelined stages comprise at least two pipelined stages following the branch outcome prediction circuitry, wherein the at least two pipelined stages comprises a first stage following the branch outcome prediction circuitry and a second stage following the first stage, and wherein each pipelined stage holds information relating to a single block of instructions.

10. The apparatus as claimed in claim 9 , wherein the branch prediction circuitry comprises update circuitry responsive to an indication that an earlier block of instructions in the second stage is terminated by the first branch instruction in the block of instructions predicted to be taken by the branch outcome prediction circuitry
and that the secondary branch target storage comprises an entry for the first branch instruction in the block of instructions predicted to be taken, to cause the entry to be updated to comprise the way prediction and the flag for a later block of instructions in the first stage.

11. The apparatus as claimed in claim 10 , wherein the update circuitry is responsive to an indication that the earlier block of instructions in the second stage comprises at most a single branch target prediction for a single branch instruction in the earlier block of instructions and the single branch target prediction is cached in the secondary branch target storage, to set the active value of the flag in the way prediction entry for the earlier block of instructions in the way prediction storage.

12. The apparatus as claimed in claim 9 , comprising way prediction storage and the branch prediction circuitry is arranged to store the way prediction and the flag in an entry of the way prediction storage associated with the block of instructions when the predicted next block of instructions sequentially follows the block of instructions,
wherein the branch prediction circuitry comprises update circuitry responsive to an indication that an earlier block of instructions in the second stage comprises no predicted

Assignees

• Advanced Risc Mach Ltd

Inventors

• Ishii Yasuo
• Farooq Muhammad Umar
• Abernathy Chris

Classifications

• G06F9/3806 Primary

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/3851

  from multiple instruction streams, e.g. multistreaming · CPC title