1. A method of 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 method comprising: 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 N th 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.