Branch prediction

A method of predicting whether a branch specified by a branch instruction in a computer program will be taken or not during execution of said instruction by a digital computer, said digital computer having an instruction decoder for pre-processing instructions in said computer program prior to execution of said instructions, said branch instruction being located in said computer program at a respective instruction address, said branch instruction including a particular one of a plurality of predefined branch operation codes, said branch instruction specifying a branch displacement which determines a corresponding target address where execution of said computer program branches to when said branch instruction is executed and said branch is taken, said method comprising the steps of:

• searching a cache memory having prestored therein information indicating whether branches associated with respective instructions should be predicted taken or not and respective displacement information for the branches, and respective target addresses determined by the respective displacement information;
• and
• when information associated with the branch instruction is found in said cache memory, then
• (a) when said information indicates that said branch should be predicted not taken, predicting that said branch will not be taken, and
• (b) when said information indicates that said branch should be predicted taken, comparing the associated displacement information in said cache memory to the displacement specified by the branch instruction, and
• when the comparing indicates that the target address determined by the associated displacement information is the same as the target address determined by the displacement specified by the branch instruction, then
• (i) predicting that said branch will be taken, and
• (ii) pre-processing instructions in said computer program beginning from the respective target address in the cache memory associated with the branch instruction.

A method of predicting whether a branch specified by a branch instruction in a computer program will be taken or not during execution of said instruction by a digital computer, said digital computer having an instruction unit for pre-processing instructions in said computer program prior to execution of said instructions, said branch instruction being located in said computer program at a respective instruction address, said branch instruction including a particular one of a plurality of predefined branch operation codes, said branch instruction specifying a branch displacement which determines a corresponding target address where execution of said computer program branches to when said branch instruction is executed and said branch is taken, said instruction unit providing the operation code and address of said branch instruction during a first time interval, providing the branch displacement of said branch instruction during a second time interval, and computing the corresponding target address from said branch displacement during a third time interval, said method comprising the steps of:

• (a) prior to execution of said branch instruction, making a prediction of whether the branch of said branch instruction will be taken or not,
• (b) during said first time interval, searching a cache memory storing target addresses and displacement information associated with instruction addresses to obtain from said cache memory any displacement information and target address associated with said address of said branch instruction,
• (c) when associated displacement information and an associated target address are obtained from said cache memory, verifying during said second time interval that the associated target address is the same as the corresponding target address that will be computed during said third time interval, said verifying being performed by comparing the associated displacement information obtained from said cache memory to the branch displacement of said branch instruction, and when the associated target address is so verified and when it is predicted that said branch will be taken, beginning pre-processing of said instructions beginning at said target address, and
• (d) when said step of verifying determines that the associated target address is not the same as the target address that will be computed during said third time interval and when it is predicted that said branch will be taken, waiting for the target address being computer, and in said third time interval beginning pre-processing of said instructions beginning at the computed target address.

A method of predicting whether a branch specified by a branch instruction in a computer program will be taken or not during execution of said instruction by a digital computer;

• said digital computer having an instruction unit for pre-processing instructions in said computer program prior to execution of said instructions, and an execution unit for executing the instructions after pre-processing;
• said branch instruction being located in said computer program at a respective instruction address, said branch instruction including a particular one of a plurality of predefined branch operation codes, said branch instruction specifying a branch displacement which determines a corresponding target address where execution of said computer program branches to when said branch instruction is executed and said branch is taken;
• said instruction unit including means for decoding instructions providing a branch signal indicating the decoding of a branch instruction, and means for computing the target address corresponding to the branch instruction and providing a target signal indicating the computing of the target address;
• said execution unit providing a validation signal indicating whether or not a branch is taken during execution;
• said branch, target and validation signals occurring in various sequences for the pre-processing and execution of a respective branch instruction;
• said method comprising the steps of:
• (a) determining a primary state characteristic of the current sequence of branch, target, and validation signals,
• (b) predicting whether the respective branch instruction will be taken or not during execution, and in response to said branch signal, setting markers indicating what to do with the computed target address when it has been computed,
• (c) in response to said validation signal and the current primary state, either setting said markers in accordance with whether the branch is to be taken when a branch has not yet been predicted, or unwinding the instruction unit by discarding the results of pre-processed instructions in the incorrect path and taking the correct path in the event that a branch has been incorrectly predicted, and
• (d) in response to said target signal, disposing of the computed target address in the manner indicated by said markers.

A method of branch prediction for a pipelined processor having an instruction unit and an execution unit, said instruction unit including means for decoding instructions to obtain operands specified by said instructions, said execution unit including means for executing said instructions to perform specified operations upon said operands to obtain respective results, said instructions including conditional branch instructions wherein a decision whether the sequence of instruction execution is to branch or not is governed by said results, said method of branch prediction including:

• predicting the outcomes of the respective decisions whether to branch or not for said conditional branch instructions;
• said decoding means of said instruction unit decoding instructions in the predicted instruction streams following the conditional branch instructions;
• comparing the predicted outcomes to the respective results of said execution unit, and when the predicted outcomes are found to be contrary to the respective results, flushing from the instruction unit information from the instructions in the predicted instruction streams following the conditional branch instructions;
• and
• while said execution unit is executing a current instruction, looking ahead to the next instruction in the instruction stream and comparing the predicted outcome to the respective result for that next instruction in the event that said next instruction is a conditional branch instruction so that information from instructions in the predicted instruction stream following said conditional branch instruction is more quickly flushed from the instruction unit when the predicted outcome for the conditional branch instruction is found to be contrary to the respective result for the conditional branch instruction.

A pipelined processor having an instruction unit and an execution unit, said instruction unit including means for decoding instructions to obtain operands specified by said instructions, said execution unit including means for executing said instructions to perform specified operations upon said operands to obtain respective results, said instructions including branch instructions wherein a decision whether the sequence of instruction execution is to branch or not is governed by said results, said instruction unit including branch prediction means for predicting the outcome of the respective decisions whether to branch or not for said branch instructions and causing said instruction unit to decode instructions in the predicted instruction streams following the branch instructions, said execution unit including means for validating the predictions by said means for predicting and generating validation signals for flushing from the processor the operands obtained from the decoding of instructions in the predicted instruction streams following the conditional branch instructions in the event that the respective results are found to be contrary to the respective predictions, said branch instructions being located in said instruction stream at respective instruction address, said branch instructions including respective ones of a plurality of predefined branch operation codes, said branch instructions specifying respective corresponding target addresses where execution of said instruction stream is to branch to when said branch instructions are executed and said branch is taken, wherein said branch prediction means comprises:

• a cache memory having prestored therein information associated with instructions indicating whether branches associated with said instructions should be predicted taken or not;
• means for searching said cache memory for information associated with a current branch instruction being decoded;
• and
• means, selected when information associated with the branch instruction is not found in said cache memory, for predicting that said branch will be taken or not based upon a respective branch bias predetermined for the branch instruction's branch operation code, and
• means, selected when information associated with the branch instruction is found in said cache memory, for predicting that said branch will be taken or not in accordance with said information associated with said branch instruction indicating whether the branch associated with the branch instruction should be predicted taken or not.

A pipelined processor having an instruction unit and an execution unit, said instruction unit including means for decoding instructions to obtain operands specified by said instructions, said execution unit including means for executing said instructions to perform specified operations upon said operands to obtain respective results, said instructions including conditional branch instructions wherein a decision whether the sequence of instruction execution is to branch or not is governed by said results, said instruction unit including a branch prediction unit for predicting the outcome of the respective decisions whether to branch or not for said conditional branch instructions and causing said instruction execution unit to decode instructions in the predicted instruction streams following the conditional branch instructions, said execution unit including means for validating the predictions by said means for predicting and generating validation signals for flushing from the processor the operands obtained from the decoding of instructions in the predicted instruction streams following the conditional branch instructions when the respective results are found to be contrary to the respective predictions, wherein

• said execution unit includes means operative during the execution of a current instruction for looking ahead to the next instruction in the instruction stream and generating the respective validation signal for that next instruction in the event that said next instruction is a conditional branch instruction.