The invention relates to managing history information for branch prediction.
A processor pipeline includes multiple stages through which instructions advance, a cycle at a time. An instruction is fetched (e.g., in an instruction fetch (IF) stage or stages). An instruction is decoded (e.g., in an instruction decode (ID) stage or stages) to determine an operation and one or more operands. Alternatively, in some pipelines, the instruction fetch and instruction decode stages could overlap. An instruction has its operands fetched (e.g., in an operand fetch (OF) stage or stages). An instruction issues, which typically starts progression of the instruction through one or more stages of execution. Execution may involve applying the instruction's operation to its operand(s) for an arithmetic logic unit (ALU) instruction, storing or loading to or from a memory address for a memory instruction, or may involve evaluating a condition of a branch instruction to determine whether or not the branch will be taken. Finally, an instruction is committed, which may involve storing a result (e.g., in a write back (WB) stage or stages).
Instructions are fetched based on a program counter (PC), which is a pointer that is used to identify instructions within memory (e.g., within a portion of main memory, or within an instruction cache of the processor). The PC may advance through addresses of a block of compiled instructions (called a “basic block”), incrementing by a particular number of bytes (depending on how long each instruction is and on how many instructions are fetched at a time). At the end of that block of instructions there may be a branch instruction that has a condition that is to be evaluated to yield a Boolean result. For example, a ‘0’ result may indicate that the branch is not taken and the PC continues to advance sequentially to the next address in a current or subsequent block, and a ‘1’ result may indicate that the branch is taken and the PC jumps (i.e., non-sequentially) to a starting address of a new block of instructions.
There are various situations in which it may be useful to speculatively fetch an instruction that is dependent on the result of a branch instruction before that result has actually been determined. Processor architectures that support such speculation use branch prediction to determine a “predicted branch result” that is used in early stages of the pipeline (e.g., to determine which instruction to fetch next), which may or may not agree with the “actual branch result” that will eventually be determined in a later stage of the pipeline. If the predicted branch result does not agree with the actual branch result, then the pipeline is flushed of any incorrect instructions and the correct instructions are fetched.