Arm Limited

Eddy Lapeyre

Guillaume Bolbenes

Houdhaifa Bouzguarrou

Luc Orion

Vincenzo Consales

An apparatus comprises: a prediction storage structure comprising a plurality of prediction state entries representing instances of predicted instruction behaviour; prediction training circuitry to perform a training operation to train the prediction state entries based on actual instruction behaviour; prediction circuitry to output at least one control signal for triggering a speculative operation based on the predicted instruction behaviour represented by a prediction state entry for which the training operation has provided sufficient confidence in the predicted instruction behaviour; an allocation filter comprising at least one allocation filter entry representing a failed predicted instruction behaviour for which the training operation failed to provide said sufficient confidence; and prediction allocation circuitry to prevent allocation of a new entry in the prediction storage structure for a failed predicted instruction behaviour represented by an allocation filter entry of the allocation filter.

Allocation filter for prediction storage structure

Branch prediction circuitry comprises: a return address prediction structure to store at least one predicted return address; and a branch target buffer (BTB) structure comprising entries each for specifying predicted branch information for a corresponding block of instructions. Within at least a subset of entries of the BTB structure, each entry specifies the predicted branch information with an encoding incapable of simultaneously indicating both: that the corresponding block of instructions is predicted to include a return branch instruction (for which the return address prediction structure is used to predict the target address); and the predicted target address for the return branch instruction. This can provide a more efficient BTB structure which requires less circuit area and power for a given level of branch prediction performance.

Branch prediction circuitry comprising a return address prediction structure and a branch target buffer structure

Circuitry comprises memory circuitry providing a plurality of memory locations;

Circuitry and method

A decoding apparatus has fetch circuitry, decode circuitry, and a decoded instruction cache. The decoded instruction cache comprises a plurality of cache blocks, where each cache block is arranged to store up to P decoded instructions from at least one fetch granule allocated to that cache block. When the corresponding decoded instruction for a required instruction is already stored in the decoded instruction cache, the decoded instruction is output in the stream of decoded instructions. Allocation circuitry is arranged, when a cache block is already allocated for existing decoded instructions from a particular fetch granule, and then additional decoded instructions from that particular fetch granule are subsequently produced by the decode circuitry due to a different path being taken through the fetch granule, to update the already allocated cache block to provide both the existing decoded instructions and the additional decoded instructions.

Apparatus and method for providing decoded instructions from a decoded instruction cache

An apparatus and method are provided for performing branch prediction. The apparatus has processing circuitry to execute instructions, and branch prediction circuitry for making branch outcome predictions in respect of branch instructions. The branch prediction circuitry includes loop minimum iteration prediction circuitry having one or more entries, where each entry is associated with a loop controlling branch instruction that controls repeated execution of a loop comprising a number of instructions. During a training phase for an entry, the loop minimum iteration prediction circuitry seeks to identify a minimum number of iterations of the loop. The loop minimum iteration prediction circuitry is then arranged, when the training phase has successfully identified a minimum number of iterations, to subsequently identify a branch outcome prediction for the associated loop controlling branch instruction for use during the minimum number of iterations. It has been found that such an approach can significantly improve prediction accuracy for loop controlling branch instructions associated with loops that do not have a stable total number of iterations.

Apparatus and method for performing branch prediction using loop minimum iteration prediction

An apparatus and method are provided for detecting regularity in a number of occurrences of an event observed during multiple instances of a counting period. The apparatus has regularity detection circuitry for seeking to detect such a regularity, and a storage providing a storage entry having a count value field to store a count value and a confidence indication field to indicate a confidence in the regularity. The regularity detection circuitry is arranged to consider the multiple instances of the counting period in pairs, for one instance in a given pair of the pairs the regularity detection circuitry incrementing the count value following each occurrence of the event, and for the other instance in the given pair the regularity detection circuitry decrementing the count value following each occurrence of the event. Check circuitry is then arranged, following completion of both counting periods in the given pair, to adjust the confidence indication to indicate an increased confidence when it is determined that the count value has returned to an initial value, and otherwise to adjust the confidence indication to indicate a decreased confidence and to reset the count value to the initial value. Such an approach provides a particularly storage efficient mechanism for seeking to detect regularity in a number of occurrences of an event.

Apparatus and method for detecting regularity in a number of occurrences of an event observed during multiple instances of a counting period

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.

Apparatus and method for making predictions for branch instructions

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.

Performing at least two branch predictions for non-contiguous instruction blocks at the same time using a prediction mapping

Data processing circuitry comprises fetch circuitry to fetch blocks, containing instructions for execution, defined by a fetch queue; and prediction circuitry to predict one or more next blocks to be fetched and to add the predicted next blocks to the fetch queue; the prediction circuitry comprising: branch prediction circuitry to detect a predicted branch destination for a branch instruction in a current block, the predicted branch destination representing either a branch target for a branch predicted to be taken or a next instruction after the branch instruction, for a branch predicted not to be taken; and sequence prediction circuitry to detect sequence data, associated with the predicted branch destination, identifying a next block following the predicted branch destination in the program flow order having a next instance of a branch instruction, to add to the fetch queue the identified next block and any intervening blocks between the current block and the identified next block, and to initiate branch prediction in respect of the predicted next instance of a branch instruction.

Data processing

Program flow prediction circuitry comprises a history register to store history data for at least one or more most recently executed branch instructions; a memory to store a plurality of sets of weight values, one set for each of a group of portions of one or more bits of the history data; access circuitry to access, for a current branch instruction to be predicted, a weight value for each of the portions of one or more bits of the history data by selecting from the set of weight values in dependence upon a current value of the portions of the history data; a combiner to generate a combined weight value by combining the weight values accessed by the access circuitry; a comparator to compare the combined weight value with a prediction threshold value to detect whether or not a branch represented by the current branch instruction is predicted to be taken; and weight modifier circuitry to modify the accessed weight values in dependence upon a resolution of whether the branch represented by the current branch instruction is taken or not.

Growing community of inventors

Antibes, France

Eddy Lapeyre