Branch prediction unit for high-performance processor

A method of branch prediction, comprising the steps of:

• a) storing a record of whether a conditional branch is taken or not taken for each conditional branch instruction executed by a processor, said record including a plurality of occurrences of either a taken indicator or a not-taken indicator or both for each conditional branch instruction at each memory address;
• wherein said record is a plurality of bits, each bit providing one of said taken or not taken indicators for a branch instruction at an instruction address;
• b) when a conditional branch instruction is executed, predicting whether or not the branch will be taken based upon said record and upon a prediction pattern using said taken and not-taken indicators;
• wherein said record is used to address a register containing said prediction pattern;
• c) fetching instructions in an instruction stream in response to said prediction.

A method of operating a computer, comprising the steps of:

• a) fetching a sequence of instructions using a sequence of addresses, wherein said instructions may include conditional branch instructions;
• b) detecting a conditional branch instruction in said sequence, and, when a conditional branch instruction is detected, selecting an entry in a branch history table in response to the address of said branch instruction in said sequence, the branch history table containing a plurality of the entries, each entry containing a plurality of indicators of taken or not taken, each indicator being the result of one of a plurality of occurrences of each branch instruction at a given memory address;
• c) in response to said plurality of indicators in said branch history table, predicting whether or not a branch will be taken when said conditional branch instruction is executed, and, if it is predicted that the branch will be taken, fetching instructions of a sequence different from said sequence, said predicting being by selecting from a multi-bit programmable prediction value using said plurality of indicators as an index for selecting within said multi-bit prediction value;
• said prediction value being in an internal location in said computer writable by said computer for dynamically changing said multi-bit prediction;
• d) executing said conditional branch instruction in a processing unit and updating said branch history table to indicate whether or not said branch was actually taken.

A method of operating a computer, comprising the steps of:

• a) fetching a sequence of instructions using a sequence of addresses, wherein said instructions may include conditional branch instructions;
• b) detecting a conditional branch instruction in said sequence, and, when a conditional branch instruction is detected, selecting an entry in a branch history table in response to the address of said branch instruction in said sequence, the branch history table containing a plurality of indicators of taken or not taken, each indicator being the result of one of a plurality of occurrences of each branch instruction;
• wherein said branch history table includes an entry for each address in a range of addresses which is less than the addressing range for said instructions, each entry containing said plurality of indicators;
• wherein each said entry contains a plurality of branch-history bits, each bit being one of said indicators of whether a branch was taken or not in a previous execution of a conditional branch at an address in said range;
• c) in response to said plurality of indicators in said branch history table, predicting whether or not a branch will be taken when said conditional branch instruction is executed, and, if it is predicted that the branch will be taken, fetching instructions of a sequence different from said sequence, said predicting being based upon a programmable prediction algorithm using said plurality of indicators;
• wherein said step of predicting includes selecting a value from a register using bits from said history table as an index to said register;
• d) executing said conditional branch instruction in a processing unit and updating said branch history table to indicate whether or not said branch was actually taken.

A processor, said processor fetching and executing a sequence of instructions, wherein said instructions may include conditional branch instructions, said processor having a branch predictor comprising:

• a) a branch history table storing a plurality entries, each entry containing a plurality of indicators of whether a branch was taken or not taken for each of said conditional branch instructions in a range of addresses for said instructions;
• b) a detector detecting a conditional branch instruction in said sequence, and, when a conditional branch in instruction is detected, selecting one of said entries in said branch history table in response to the address of said branch instruction in said sequence;
• c) a predictor generating an output indicating a programmable empirically-based prediction of whether or not a branch will be taken when said conditional branch instruction is executed, said prediction being responsive to said plurality of indicators of an entry, and, if it is predicted that the branch will be taken, generating a new address sequence for fetching instructions differing from said sequence;
• wherein said predictor includes a register containing a plurality of bits, said register being addressed by said indicators for said selected one of said entries, each bit of said register being said prediction for a pattern of said indicators as recorded in one of said entries in said history table;
• d) a processing unit executing said conditional branch instruction and updating said branch history table to indicate whether or not said branch was actually taken.

A processor for executing instructions including conditional branch instructions, having a branch prediction comprising:

• a) means for storing a record of entries containing indicators of whether a conditional branch is taken or not taken for each conditional branch instruction executed by said processor, said record including a plurality of entries, each said entry containing a plurality of said indicators for a plurality of occurrences of each conditional branch instruction at each memory address;
• b) means responsive to a conditional branch instruction being executed, for predicting whether or not the branch will be taken responsive to one of said entries of said record and based upon a stored programmable prediction pattern;
• said prediction pattern being a multi-bit value addressed by said one of said entries and selection from said multi-bit value being in response to the value of said one of said entries, said multi-bit value being in a location in said processor writable by an instruction executed by said processor;
• c) and means for fetching instructions in an instruction stream in response to said prediction.

A processor for executing instructions including conditional branch instructions, having a branch prediction comprising:

• a) means for storing a record of entries containing indicators of whether a conditional branch is taken or not taken for each conditional branch instruction executed by said processor, said record including an entry containing a plurality of said indicators for a plurality of occurrences of each conditional branch instruction at each memory address;
• wherein each said entry of said record is a plurality of bits, each bit being one of said indicators indicating taken or not taken for a branch instruction at an instruction address
• b) means responsive to a conditional branch instruction being executed, for predicting whether or not the branch will be taken responsive to one of said entries of said record and based upon a stored programmable prediction pattern;
• wherein a selected one of said entries of said record is used to address a register containing said prediction pattern;
• c) and means for fetching instructions in an instruction stream in response to said prediction.