Method and apparatus for predicting multiple conditional branches

A system for predicting branch outcome where a group of instructions is fetched per slot, comprising:

• a register indicative of recent program control flow;
• a predictor table, further comprising a plurality of saturating counters, a particular counter being updated when a branch is encountered, each group of instructions being associated with a program counter (PC), a saturating counter being referenced by hashing the register with the group's PC;
• a hash function for generating an index from the register and the group's PC, wherein the index is used to access naturally aligned predictions in the predictor table;
• and
• a shuffler for reordering the predictions based on value of the lower portion of the register.

A system for predicting branch outcome where a group of instructions is fetched per slot, comprising:

• register means for indicating recent program control flow;
• a plurality of prediction means, a particular prediction means being updated when a branch is encountered, each branch instruction being associated with a program counter (PC), the prediction means being referenced by hashing the register means with the group's PC;
• hashing means for generating an index from the register means and the group's PC, wherein the index is used to access naturally aligned prediction means;
• and
• shuffling means for reordering the predictions based on value of the lower portion of the register means.

A method of branch prediction, comprising the steps of:

• maintaining a register which provides a pattern of program control flow;
• modifying the register based on control flow activity;
• hashing a value held in the resister with a program counter (PC) of an instruction fetched in a given slot to generate an index;
• applying the index to access naturally aligned branch predictions which correspond to the given slot of instructions;
• and
• reordering the branch predictions based on a portion of the register, into the same order as the instructions.

A method of branch prediction, comprising the steps of:

• maintaining a register which provides a pattern of program control flow;
• modifying the register based on a summary of control flow activity of instructions fetched in a given slot;
• generating an index based on the register;
• and
• using the index to select a branch prediction from a plurality of branch predictions.

A method of branch prediction, comprising the steps of:

• fetching a block of instructions in a given slot;
• maintaining a register indicative of recent program control flow;
• maintaining a predictor table comprising a plurality of branch predictions, a particular prediction being updated when a branch is encountered, each instruction block being associated with a program counter (PC), the prediction being referenced by hashing the register with the PC of the instruction block;
• hashing the register with the PC of the fetched instruction block to form an index;
• accessing, with the index, naturally aligned predictions in the predictor table;
• and
• reordering the predictions based on value of a portion of the register.