Branch predictor using multiple prediction heuristics and a heuristic identifier in the branch instruction

A method of determining a prediction heuristic for a branch instruction in a computer program, the method comprising the steps of:

• locating the branch instruction in the program and adding profiling instructions for the branch instruction to the program, the profiling instructions, when executed, computing history information for the branch instruction and inputting the history information to a plurality of prediction heuristics, each prediction heuristic outputting a prediction of whether the branch instruction will be taken;
• executing the program with a sample data set, the execution of the program causing execution of the profiling instructions, the execution of the program further causing execution of the branch instruction, the execution of the branch instruction comprising a branch decision;
• and
• comparing the output of each prediction heuristic from the plurality of prediction heuristics to the branch decision to identify a prediction heuristic from the plurality of prediction heuristics which most accurately predicts the branch decision for the branch instruction.

An apparatus to determine a prediction heuristic for a branch instruction in a computer program, the apparatus comprising:

• a profiler to locate the branch instruction in the program, the profiler adding profiling instructions for the branch instruction to the program, the profiling instructions, when executed, to compute history information for the branch instruction and to input the history information to a plurality of prediction heuristics, each prediction heuristic to output a prediction of whether the branch instruction will be taken;
• an execution unit to execute the program with a sample data set, the execution of the program causing execution of the profiling instructions, the execution of the program further causing execution of the branch instruction, the execution of the branch instruction comprising a branch decision;
• and
• a comparator to compare the output of each prediction heuristic from the plurality of prediction heuristics to the branch decision, the comparator to identify a prediction heuristic from the plurality of prediction heuristics which most accurately predicts the branch decision for the branch instruction.

A system for predicting whether a branch specified by an instruction in a computer program will be taken during execution of the program by a computer, the instruction configured to cause selection of a prediction heuristic from a plurality of distinct heuristics to predict whether the branch specified by the instruction will be taken, the system comprising:

• a first storage device that stores a current pattern comprising a number of consecutive identical branch decisions for the instruction, said first storage device also storing a prior pattern comprising a number of consecutive identical prior branch decisions for the instruction, the prior branch decisions occurring prior to the branch decisions comprised by the current pattern;
• a circuit including a plurality of prediction heuristics comprising the selected prediction heuristic;
• a circuit configured to use the plurality of prediction heuristics, that use the current pattern and the prior pattern to generate a prediction of whether the branch will be taken;
• and
• an execution unit to execute the instruction, the execution unit to output a branch decision indicating whether the branch specified by the instruction was taken.

An apparatus to determine the prediction heuristic identified by a branch instruction in a computer program, the apparatus comprising:

• means for locating the branch instruction and adding profiling instructions for the branch instruction to the program, the profiling instructions, when executed, for computing history information for the branch instruction and for inputting the history information to a plurality of prediction means, each prediction means for outputing a prediction of whether the branch instruction will be taken;
• means for executing the program with a sample data set, the execution of the program causing execution of the profiling instructions, the execution of the program further causing execution of the branch instruction, the execution of the branch instruction comprising a branch decision;
• and
• means for comparing the output of each prediction means from the plurality of prediction means to the branch decision, the comparator means identifying a prediction means from the plurality of prediction means which most accurately predicts the branch decision for the branch instruction.

A system for predicting whether a branch specified by an instruction in a computer program will be taken during execution of the program by a computer, the instruction configured to cause selection from a distinct plurality of prediction means of a prediction means for predicting whether the branch specified by the instruction will be taken, the system comprising:

• means for storing a current pattern comprising a number of consecutive identical branch decisions for the instruction, the means for storing further storing a prior pattern comprising a number of consecutive identical prior branch decisions for the instruction, the prior branch decisions occurring prior to the branch decisions comprised by the current pattern;
• a circuit including a plurality of prediction means comprising the selected prediction means, the circuit configured to use the plurality of prediction means that use the current pattern and the prior pattern for generating a prediction of whether the branch will be taken;
• and
• means for executing the instruction, the execution means for outputting a branch decision indicating whether the branch specified by the instruction was taken.