Apparatus and method for making predictions for branch instructions

Abstract

An apparatus and method are provided for making predictions for branch instructions. The apparatus has a prediction queue for identifying instructions to be fetched for execution, and branch prediction circuitry for making predictions in respect of branch instructions, and for controlling which instructions are identified in the prediction queue in dependence on the predictions. During each prediction iteration, the branch prediction circuitry makes a prediction for a predict block comprising a sequence of M instructions. The branch prediction circuitry comprises a target prediction storage having a plurality of entries that are used to identify target addresses for branch instructions that are predicted as taken, the target prediction storage being arranged as an N-way set associative storage structure comprising a plurality of sets. Each predict block has an associated set within the target prediction storage. The branch prediction circuitry further comprises a high branch density (HBD) tracker arranged to identify, as a HBD predict block, a predict block whose sequence of M instructions contains more than N branch instructions. For each identified HBD predict block, at least one additional set is identified in the target prediction storage to be used in addition to the associated set to identify target addresses for branch instructions that are predicted as taken within that HBD predict block.