Fetch ahead branch target buffer
View Patent ↗A fetch ahead branch target buffer is used by a branch predictor to determine a target address for a branch instruction based on a fetch pointer for a previous fetch bundle, i.e. a fetch bundle which is fetched prior to a fetch bundle which includes the branch instruction. An entry in the fetch ahead branch target buffer corresponds to one branch instruction and comprises a data portion identifying the target address of that branch instruction. In various examples, an entry also comprises a tag portion which stores data identifying the fetch pointer by which the entry is indexed. Branch prediction is performed by matching an index generated using a received fetch pointer to the tag portions to identify a matching entry and then determining the target address for the branch instruction from the data portion of the matching entry.
1. A branch predictor, comprising:
a fetch ahead branch target buffer having a plurality of data entries indexed using fetch pointers (X,Y), each entry corresponding to a branch instruction (X BR , Y BR ) and including a data portion arranged to store data identifying a target address (Y,Z) of the branch instruction (X BR , Y BR ) to which the entry corresponds, wherein an entry for a branch instruction (Y BR ) is indexed by a fetch pointer (X) of a starting instruction of a first fetch bundle comprising a plurality of instructions including a branch instruction (X BR ) which is fetched prior to another fetch bundle including the branch instruction (Y BR ) to which the entry corresponds;
an input configured to receive the fetch pointer (X) from a fetch stage in a processor;
branch prediction logic configured to determine a target address (Z) for the branch instruction (Y BR ) included in said another fetch bundle using the fetch ahead branch target buffer and the received fetch pointer (X); and
an output configured to provide the target address (Z) for the branch instruction (Y BR ) to the fetch stage, wherein the branch instruction (Y BR ) is part of said another fetch bundle that is fetched after the first fetch bundle identified by the received fetch pointer (X),
wherein a transition from the first fetch bundle to said another fetch bundle is due to a branch instruction (X BR ) in the first fetch bundle which has a target address (Y) of a starting instruction of said another fetch bundle.
2. A branch predictor according to claim 1 , wherein each entry further comprises a tag portion arranged to store data identifying the fetch pointer by which the entry is indexed.
3. A branch predictor according to claim 2 , wherein the branch prediction logic comprises:
index generator logic configured to generate an index using information relating to the received fetch pointer (X); and
target address prediction logic configured to identify a matching entry in the fetch ahead branch target buffer by matching the index to a tag portion and to determine the target address (Z) for the branch instruction (Y BR ) using the data portion of the matching entry.
4. A branch predictor according to claim 3 , wherein the index is at least part of the fetch pointer (X).
5. A branch predictor according to claim 3 , wherein the index is all of the fetch pointer (X).
6. A branch predictor according to claim 3 , wherein the information relating to the branch instruction (X BR ) which is fetched prior to said another fetch bundle including the branch instruction (Y BR ) to which the entry corresponds comprises history data.
7. A branch predictor according to claim 1 , further comprising:
update logic configured to update the data portion of an entry in the fetch ahead branch target buffer based on cached information relating to the received fetch pointer (X), the target address (Z) for the branch instruction (Y BR ) determined by the branch prediction logic and information relating to execution of the branch instruction (Y BR ) received from an execution stage in the processor.
8. A method of branch prediction implemented in hardware logic, the method comprising:
receiving, at an input of a branch predictor a fetch pointer (X) from a fetch stage in a processor;
determining a target address (Z) for a branch instruction (Y BR ) using a fetch ahead branch target buffer and the received fetch pointer (X), the fetch ahead branch target buffer comprising a plurality of data entries indexed using fetch pointers (X,Y), each entry corresponding to a branch instruction (X BR , Y BR ) and comprising a data portion arranged to store data identifying a target address (Z) of the branch instruction (Y BR ), wherein an entry is indexed by a fetch pointer (X) of a starting instruction of a first fetch bundle comprising a plurality of instructions which is fetched prior to another fetch bundle including the branch instruction (Y BR ) to which the entry corresponds; and
outputting, via an output of the branch predictor, the target address (Z) for the branch instruction (Y BR ) to the fetch stage, wherein the branch instruction (Y BR ) is part of said another fetch bundle that is fetched after the first fetch bundle comprising a plurality of instructions including a starting instruction identified by the received fetch pointer (X),
wherein a transition from the first fetch bundle to said another fetch bundle is due to a branch instruction (X BR ) in the first fetch bundle which has a target address (Y) of a starting instruction of said another fetch bundle.
9. The method according to claim 8 , wherein each entry further comprises a tag portion arranged to store data identifying the fetch pointer by which the entry is indexed.
10. The method according to claim 9 , wherein determining a target address (Z) for a branch instruction (Y BR ) using a fetch ahead branch target buffer comprises:
generating an index using information relating to the received fetch pointer (X);
comparing the index to tag portions in the fetch ahead branch target buffer; and
in response to identifying a match between the index and a tag portion of an entry in the fetch ahead branch target buffer, determining the target address (Z) for the branch instruction (Y BR ) using the data portion of the matching entry.
11. The method according to claim 8 , further comprising:
caching information relating to the fetch pointer (X) and the target address (Z) for the branch instruction (Y BR ); and
in response to receiving information relating to execution of the branch instruction (Y BR ) from an execution stage in the processor, updating the data portion of the matching entry in the fetch ahead branch target buffer based the information received.
12. A non-transitory computer readable storage medium having encoded thereon computer executable instructions that when executed cause a processor to perform the method of claim 8 .
13. A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when processed at a computer system for generating a manifestation of an integrated circuit, cause the computer system to generate a manifestation of an integrated circuit comprising a branch predictor, the branch predictor comprising:
a fetch ahead branch target buffer comprising a plurality of data entries indexed using fetch pointers (X,Y), each entry corresponding to a branch instruction (X BR , Y BR ) and comprising a data portion arranged to store data identifying a target address (Z) of the branch instruction (Y BR ) to which the entry corresponds, wherein an entry is indexed by a fetch pointer (X) of a starting instruction of a first fetch bundle comprising a plurality of instructions which is fetched prior to another fetch bundle comprising a plurality of instructions including the branch instruction (Y BR ) to which the entry corresponds;
an input configured to receive a fetch pointer (X) from a fetch stage in a processor;
branch prediction logic configured to determine a target address (Z) for the branch instruction (Y BR ) using the fetch ahead branch target buffer and the received fetch pointer (X); and
an output configured to provide the target address (Z) for the branch instruction (Y BR ) to the fetch stage, wherein the branch instruction (Y BR ) is part of said another fetch bundle comprising a plurality of instructions that is fetched after the first fetch bundle comprising a plurality of instructions having a starter instruction identified by the received fetch pointer, wherein a transition from the first fetch bundle to said another fetch bundle is due to a branch instruction (X BR ) in the first fetch bundle which has a target address (Y) of a starting instruction of said another fetch bundle.
14. The non-transitory computer readable storage medium according to claim 13 , wherein each entry further comprises a tag portion arranged to store data identifying the fetch pointer by which the entry is indexed.
15. A branch predictor as claimed in claim 1 , wherein said another fetch bundle comprises a plurality of instructions including at least a starting instruction and the branch instruction (Y BR ).
16. The method as claimed in claim 8 , wherein said another fetch bundle comprises a plurality of instructions including at least a starting instruction and the branch instruction (Y BR ).
17. A branch predictor according to claim 6 wherein the history data comprises history information for previous branch instructions.
18. The method according to claim 9 wherein determining a target address (Z) for a branch instruction (Y BR ) using a fetch ahead branch target buffer comprises:
generating an index using information relating to the received fetch pointer (X);
comparing the index to tag portions in the fetch ahead branch target buffer; and
in response to failing to identify a match between the index and a tag portion of an entry in the fetch ahead branch target buffer, stalling the fetch stage until a target address (Y) of a starting instruction of said another fetch bundle is available.
19. The method according to claim 10 wherein comparing the index to tag portions in the fetch ahead branch target buffer comprises comparing the index to tag portions of all entries in the branch target buffer.