1. Field of the Invention
This invention relates to microprocessors and, more particularly, to branch prediction mechanisms employed by microprocessors.
2. Description of the Related Art
Many high performance pipelined microprocessors maintain their performance by keeping the various pipelines as full as possible. However, certain control transfer instructions may cause various stages within a pipeline to be flushed and the instructions in those stages to be canceled or discarded. One such instruction is a branch instruction. A branch instruction is an instruction which causes subsequent instructions to be fetched from a target address identifying an instruction stream beginning at an arbitrary location in memory. Unconditional branch instructions always branch to the target address, while conditional branch instructions may select either the next sequential address or the target address based on a condition such as the outcome of a prior instruction. Thus, when instructions are prefetched into a processor's instruction-processing pipeline sequentially, and a conditional branch is taken, the contents of early stages of the pipeline may contain instructions that should not be executed but rather should be flushed.
Accordingly, in conjunction with the pre-fetching of instructions, it is generally beneficial to predict whether a conditional branch instruction, when executed, will be taken or not. For this purpose, many pipelined microprocessors employ a branch prediction mechanism.
The branch prediction mechanism may indicate a predicted direction (taken or not-taken) for a branch instruction, allowing subsequent instruction fetching to continue within the predicted instruction stream indicated by the branch prediction. Instructions from the predicted instruction stream may be speculatively and/or executed prior to execution of the branch instruction, and are placed into the instruction-processing pipeline prior to execution of the branch instruction. If the predicted instruction stream is correct (which is generally well in excess of 90% for many current designs), then the efficiency of instruction execution may be advantageously improved. However, if the predicted instruction stream is incorrect (i.e. one or more branch instructions are predicted incorrectly), then the instructions from the incorrectly predicted instruction stream are discarded from the instruction-processing pipeline and the efficiency of instruction execution may be degraded.
To be effective, the branch prediction mechanism must be highly accurate such that the predicted instruction stream is correct as often as possible. Frequently, a history of prior executions of a branch or branches is used to form a more accurate prediction for a particular branch. Such a branch prediction history typically requires maintaining data corresponding to the branch instruction in a storage.
Many branch prediction mechanisms have been implemented that yield relatively good results. One such branch prediction mechanism is the GShare branch prediction mechanism. The GShare mechanism combines a global branch history and several bits of the program counter (PC) of a current branch instruction (e.g., fetch address of the current branch instruction) to form an index into a predictor table. Each entry in the predictor table typically stores a counter value that may be indicative of whether a branch should be taken or not. Although the GShare mechanism may be an effective prediction mechanism, aliasing of index values is a concern. For example, the GShare mechanism may produce the same index value and therefore an erroneous. prediction, when provided with different input combinations of the PC and global branch history that correspond to different branches.