Performing at least two branch predictions for non-contiguous instruction blocks at the same time using a prediction mapping
An apparatus is provided to perform branch prediction in respect of a plurality of instructions divided into a plurality of blocks. Receiving circuitry receives references to at least two blocks in the plurality of blocks. Branch prediction circuitry performs at least two branch predictions at a time. The branch predictions are performed in respect of the at least two blocks and the at least two blocks are non-contiguous.
1. An apparatus to perform branch prediction in respect of a plurality of instructions divided into a plurality of blocks, the apparatus comprising:
receiving circuitry to receive references to at least two blocks in the plurality of blocks;
branch prediction circuitry to perform at least two branch predictions at a time in respect of the at least two blocks; and
branch sequence circuitry comprising a lookup table comprising a plurality of mappings, each of the mappings comprising a tag and a mapped prediction comprising a reference to an origin block and a reference to a destination block, wherein the branch sequence circuitry is adapted to provide, by accessing the lookup table, a reference to one of the at least two blocks to the branch prediction circuitry in dependence on a reference to a most recently encountered block relating to a predicted taken branch, wherein
the at least two blocks are non-contiguous.
2. The apparatus according to claim 1 , wherein
the reference to the most recently encountered block relating to the predicted taken branch comprises an address of the predicted taken branch.
3. The apparatus according to claim 1 , wherein
the lookup table is fully associative.
4. The apparatus according to claim 1 , wherein
the branch sequence circuitry is adapted to return the reference to the destination block of one of the mappings where the tag corresponds with the reference to the most recently encountered block.
5. The apparatus according to claim 4 , wherein
the branch sequence circuitry is adapted to add a new mapping comprising one of the at least two branch predictions as the mapped prediction to the lookup table in the absence of the mappings already comprising the one of the at least two branch predictions; and
the tag of the new mapping corresponds with the reference to the most recently encountered block.
6. The apparatus according to claim 1 , wherein
each of the mappings comprises a confidence that is one of a plurality of levels; and
for a given one of the mappings, the branch sequence circuitry is adapted to return the reference to the destination block of the given one of the mappings in further dependence on the confidence of the given one of the mappings.
7. The apparatus according to claim 6 , wherein
the branch sequence circuitry is adapted to return the reference to the destination block of the given one of the mappings in further dependence on the confidence of the given one of the mappings being higher than the lowest of the plurality of levels.
8. The apparatus according to claim 6 , wherein
the confidence of a mapping is increased in response to the branch prediction circuitry subsequently correctly predicting the mapped prediction of that mapping; and
the confidence of the mapping is decreased in response to the branch prediction circuitry subsequently incorrectly predicting the mapped prediction of that mapping.
9. The apparatus according to claim 1 , wherein
each of the mappings comprises branch prediction configuration data; and
in response to the branch sequence circuitry providing the reference to the one of the at least two blocks, the branch prediction circuitry is configured to perform a prediction for the reference to the one of the at least two blocks using the corresponding branch prediction configuration data.
10. The apparatus according to claim 1 , wherein
the branch sequence circuitry is adapted to provide the reference to the one of the at least two blocks to the branch prediction circuitry in a cycle before the reference to the one of the at least two blocks is provided to the branch prediction circuitry by circuitry other than the branch sequence circuitry.
11. The apparatus according to claim 1 , wherein
the branch prediction circuitry is adapted to perform N branch predictions at a time in respect of N blocks in the plurality of blocks; and
the branch sequence circuitry is adapted to provide references to M of the N blocks in dependence on the reference to the most recently encountered block, wherein
M<N; and
the N blocks are non-contiguous such that at least one of the N blocks is separated from another block of the N blocks by at least one block which is not part of the N blocks.
12. A method of performing branch prediction in respect of a plurality of instructions divided into a plurality of blocks, the method comprising:
receiving references to at least two blocks in the plurality of blocks;
performing at least two branch predictions at a time in respect of the at least two blocks in the plurality of blocks; and
accessing a lookup table in order to provide a reference to one of the at least two blocks to perform the at least two branch predictions in dependence on a reference to a most recently encountered block relating to a predicted taken branch, wherein
the at least two blocks are non-contiguous, and
the lookup table comprises a plurality of mappings, each of the mappings comprising a tag and a mapped prediction comprising a reference to an origin block and a reference to a destination block.