Efficient branch predictor history recovery in pipelined computer architectures employing branch prediction and branch delay slots of variable size

An apparatus for controlling a pipelined processor having a plurality of serially connected processing stages including a first stage and a branch evaluation stage, wherein one of the processing stages other than the branch evaluation stage is a prediction start stage that supplies information for making branch predictions, wherein the pipelined processor is operatively coupled to a memory that comprises a plurality of addressable storage locations, each storage location being for storing one unit of data, wherein the pipelined processor executes instructions from an instruction set that includes a branch instruction and each branch instruction is associated with a set of branch delay slots whose size can be greater than or equal to zero and whose size can be different from one instance of a branch instruction to another, the apparatus comprising:

• a controller configured to cause the pipelined processor to perform:
• in a first processing cycle, supplying a first branch prediction history as input to a branch predictor that requires N cycles to produce an output;
• in an Nth processing cycle after the first processing cycle, loading a memory unit of data into the first stage of the pipelined processor, wherein the memory unit of data includes a branch instruction;
• as the memory unit of data progresses through the processing stages from one cycle to a next, building a set of N branch prediction histories that are associated with the memory unit of data, wherein the N branch prediction histories comprise the first branch prediction history and N−1 branch prediction histories used to predict N−1 subsequently fetched memory units of data;
• maintaining a history of evaluated branch outcomes of branch instructions that reached the branch evaluation stage;
• detecting, based on a present evaluation of the branch instruction included in the memory unit of data and an earlier predicted outcome, whether a branch misprediction occurred;
• and
• in response to a detection that the branch misprediction occurred:
• selecting values of each one of N recovery histories from the history of evaluated branch outcomes and the set of branch prediction histories;
• and
• supplying respective ones of the N selected recovery histories as input to the branch predictor when each one of N next memory units of data are loaded into the prediction start stage of the pipeline,
• wherein a last one of the branch delay slots is a branch source of the associated branch instruction.

A pipelined processor comprising:

• a plurality of serially connected processing stages including a first stage and a branch evaluation stage, wherein one of the processing stages other than the branch evaluation stage is a prediction start stage that supplies information for making branch predictions, wherein the pipelined processor executes instructions from an instruction set that includes a branch instruction and each branch instruction is associated with a set of branch delay slots whose size can be greater than or equal to zero and whose size can be different from one instance of a branch instruction to another, wherein a last one of the branch delay slots is a branch source of the associated branch instruction;
• a memory that comprises a plurality of addressable storage locations, each storage location being for storing one unit of data, wherein the pipelined processor is operatively coupled to the memory;
• and
• a controller configured to cause the pipelined processor to perform:
• in a first processing cycle, supplying a first branch prediction history as input to a branch predictor that requires N cycles to produce an output;
• in an Nth processing cycle after the first processing cycle, loading a memory unit of data into the first stage of the pipelined processor, wherein the memory unit of data includes a branch instruction;
• as the memory unit of data progresses through the processing stages from one cycle to a next, building a set of N branch prediction histories that are associated with the memory unit of data, wherein the N branch prediction histories comprise the first branch prediction history and N−1 branch prediction histories used to predict N−1 subsequently fetched memory units of data;
• maintaining a history of evaluated branch outcomes of branch instructions that reached the branch evaluation stage;
• detecting, based on a present evaluation of the branch instruction included in the memory unit of data and an earlier predicted outcome, whether a branch misprediction occurred;
• and
• in response to a detection that the branch misprediction occurred:
• selecting values of each one of N recovery histories from the history of evaluated branch outcomes and the set of branch prediction histories;
• and
• supplying respective ones of the N selected recovery histories as input to the branch predictor when each one of N next memory units of data are loaded into the prediction start stage of the pipeline.