Device for performing branch target buffer entry prefetching
A branch prediction device includes a hierarchy of successively slower to access branch target buffers that store branch target buffer entries identifying branch instructions, branch prediction circuitry configured to predict future branch instructions, and a branch target buffer prefetch table coupled to receive candidate entries corresponding to predicted future branch instruction branch target buffer misses, each entry of the candidate entries corresponding to a precursor branch instruction, and to receive predicted precursor branch instructions that trigger promotion of an entry in a branch target buffer of the branch target buffers to a faster branch target buffer of the branch target buffers.
1 . A branch prediction device comprising:
a hierarchy of successively slower to access branch target buffers that store branch target buffer entries identifying branch instructions;
branch prediction circuitry configured to predict future branch instructions; and
a branch target buffer prefetch table configured to:
in response to a branch instruction missing from a faster level of the branch target buffers, allocate a candidate entry that stores a reference to a branch target buffer entry corresponding to the branch instruction that missed and identifies a precursor branch instruction that precedes the branch instruction that missed in a sequence of branch predictions; and
trigger promotion of the branch target buffer entry from a slower level branch target buffer to a branch target buffer that is faster when the precursor branch instruction is subsequently encountered.
2 . The branch prediction device of claim 1 wherein the branch prediction circuitry is further configured to promote the branch target buffer entry to the branch target buffer in response to the branch target buffer entry being in a slowest branch target buffer.
3 . The branch prediction device of claim 1 and further comprising a victim cache configured to store evicted entries from one of the branch target buffers, wherein the branch prediction circuitry is further configured to promote the branch target buffer entry from the victim cache to one of the branch target buffers in response to the branch target buffer entry not being in any of the branch target buffers.
4 . The branch prediction device of claim 1 and further comprising a trace buffer configured to hold a program counter value and a branch history register entry corresponding to the branch prediction circuitry predicted branch instructions.
5 . The branch prediction device of claim 4 wherein the branch prediction circuitry is configured to identify the precursor branch instruction as an ancestor of a corresponding candidate, such that encountering the precursor branch instruction acts as the trigger for promoting the corresponding candidate.
6 . The branch prediction device of claim 5 wherein branch prediction circuitry is configured to select the precursor branch instruction dynamically as a function of minimum and maximum ancestor distance parameters.
7 . The branch prediction device of claim 6 and further comprising a branch target buffer prefetch miss queue configured to store a program counter value associated with an instruction for which miss indications from each branch target buffer of the branch target buffers is received.
8 . The branch prediction device of claim 7 wherein a prefetch distance identifying the precursor branch instruction has a value bounded by the minimum and maximum ancestor distance parameters.
9 . The branch prediction device of claim 8 wherein a number of non-prefetch branch target buffer misses hitting inflight prefetch branch target buffer accesses in a last N prefetch cycles surpasses a programmable threshold, the prefetch distance is increased by one, up to, and including, the maximum ancestor distance parameter value.
10 . The branch prediction device of claim 8 wherein in response to a number of branch target buffer evictions from prefetched-but-not-used entries in a last M prefetch cycles surpassing a programmable threshold, the prefetch distance is decreased by one, up to, and including, the minimum ancestor distance parameter value.