Branch target buffer victim cache
Improved branch target buffer (BTB) structures are provided. A device can include branch target buffers storing entries corresponding to branch instructions and corresponding targets of the branch instructions. The device can include a victim cache storing a branch target buffer entry that has been evicted from a branch target buffer of the branch target buffers. The device can include branch prediction circuitry configured to access the victim cache responsive to receiving respective miss indications from each branch target buffer of the branch target buffers.
1 . A device comprising:
branch target buffers storing entries corresponding to branch instructions and corresponding targets of the branch instructions;
a victim cache storing a branch target buffer entry that has been evicted from a branch target buffer of the branch target buffers; and
branch prediction circuitry configured to access the victim cache only (i) after receiving miss indications from each branch target buffer of the branch target buffers and (ii) if indicator data from at least one branch target buffer of the branch target buffers indicates that an entry for a target of a current entry was previously present in one of the branch target buffers.
2 . The device of claim 1 , further comprising:
a program memory storing instructions of a compute application;
a processor; and
a compute pipeline coupled between the processor and the program memory, the compute pipeline configured to receive an instruction of the instructions and provide the instruction and data on which the instruction relies to the processor, wherein a first amount of time it takes to (i) receive the miss indications, access the victim cache, and receive a response from the victim cache is less than (ii) a second amount of time it takes to operate on the instruction by the compute pipeline.
3 . The device of claim 1 , further comprising:
a miss queue coupled between the branch prediction circuitry and the victim cache, the miss queue configured to store a program counter value associated with an instruction of the instructions for which respective miss indications from each branch target buffer of the branch target buffers is received.
4 . The device of claim 3 , further comprising an eviction queue coupled between the branch target buffers and the victim cache, the eviction queue configured to receive the entry that has been evicted.
5 . The device of claim 4 , wherein the eviction queue is further configured to write the entry that has been evicted into the victim cache.
6 . The device of claim 5 , wherein the write from the eviction queue has a lower priority than a read from the miss queue.
7 . The device of claim 3 , wherein the miss queue is further configured to update a branch target buffer of the branch target buffers to include the entry that has been evicted responsive to a successful read of the entry from the victim cache.
8 . The device of claim 1 , further comprising a return stack buffer that includes the indicator data and corresponding data indicating an entry in the branch target buffers that is a target of a corresponding return.
9 . The device of claim 1 , further comprising an indirect predictor that predicts a target of an indirect branch and includes the indicator data and corresponding data indicating an entry in the branch target buffers that is a target of the indirect branch.
10 . The device of claim 1 , further comprising:
a BTB prefetch table that stores BTB entries that are predicted, by the branch prediction circuitry to be respective targets of future branch instructions.
11 . A method comprising:
receiving, at a branch target buffer of branch target buffers, an entry indicating a first program counter value corresponding to a branch instruction and a second program counter value corresponding to an instruction executed immediately after the branch;
writing, to a victim cache, an entry that has been evicted from a branch target buffer of the branch target buffers;
receiving miss indications from each branch target buffer of the branch target buffers;
determining that indicator data from at least one branch target buffer of the branch target buffers indicates that an entry for a target of a current entry was previously present in one of the branch target buffers; and
accessing, by branch prediction circuitry, the victim cache only after (i) receiving miss indications from each branch target buffer of the branch target buffers and (ii) determining the indicator data from at least one branch target buffer of the branch target buffers indicates that an entry for a target of a current entry was previously present in one of the branch target buffers.
12 . The method of claim 11 , further comprising:
storing, by a program memory, instructions of a compute application;
receiving, by a compute pipeline coupled between a processor and the program memory, an instruction of the instructions;
providing, by the compute pipeline, the instruction and data on which the instruction relies to the processor; and
wherein a first amount of time it takes to (i) receive the respective miss indications, access the victim cache, and receive a response from the victim cache is less than (ii) a second amount of time it takes to operate on the instruction by the compute pipeline.
13 . The method of claim 11 , further comprising:
storing, by a miss queue coupled between the branch prediction circuitry and the victim cache, a program counter value associated with first instruction of instructions for which respective miss indications from each branch target buffer of the branch target buffers is received at the branch prediction circuitry.
14 . The method of claim 13 , further comprising receiving, by an eviction queue coupled between the branch target buffers and the victim cache, the entry that has been evicted.
15 . The method of claim 14 , further comprising writing, by the eviction queue, the entry that has been evicted into the victim cache.
16 . A device comprising:
a program counter configured to generate a program counter value corresponding to an instruction of an application to be executed;
branch target buffers including entries storing respective program counter values associated with respective branch instructions and respective program counter values that are respective targets of the respective branch instructions, the entries further including indicator data indicating whether an entry for a target of a present entry has been stored in one of the branch target buffers;
a victim cache configured to receive an entry that has been evicted from a branch target buffer of the branch target buffers; and
branch prediction circuitry configured to access the victim cache only (i) after receiving miss indications from each branch target buffer of the branch target buffers and (ii) if the indicator data from at least one branch target buffer of the branch target buffers indicates that an entry for a target of a current entry was previously present in one of the branch target buffers.
17 . The device of claim 16 , further comprising:
a miss queue coupled between the branch prediction circuitry and the victim cache, the miss queue configured to store a program counter value associated with an instruction of the instructions for which respective miss indications from each branch target buffer of the branch target buffers is received; and
an eviction queue coupled between the branch target buffers and the victim cache, the eviction queue configured to receive the entry that has been evicted.
18 . The device of claim 17 , wherein the miss queue is further configured to update a branch target buffer of the branch target buffers to include the entry that has been evicted responsive to a successful read of the entry that has been evicted from the victim cache.