Static branch prediction mechanism for conditional branch instructions

• US 6,571,331 B2
• Filed: 04/03/2001
• Issued: 05/27/2003
• Est. Priority Date: 03/18/1999
• Status: Expired due to Term

• Current Assignee: IP-First LLC
• Original Assignee: IP-First LLC
• Inventors: Parks, Terry, Henry, G. Glenn
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US09/825,435
• Publication Number:
  US 20010032309A1
• Time in Patent Office: 784 Days
• Field of Search: 712/239, 712/234
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3846 using static prediction, e.g. branch taken strategy
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

An apparatus and method are provided for accurately predicting the outcome of branch instructions prior to their execution by a pipeline microprocessor. The apparatus has a static branch predictor, a mandatory signal, and a biased prediction correlator. The static branch predictor provides a predicted outcome for a branch instruction, and determines if the branch instruction is a biased outcome conditional branch instruction. The mandatory signal is coupled to the static branch predictor and indicates whether or not the branch instruction is the biased outcome conditional branch instruction, thereby indicating whether or not the predicted outcome takes precedence over a dynamic branch prediction for the branch instruction. The biased prediction correlator is coupled to the static branch predictor and the mandatory signal. The biased prediction correlator receives the predicted outcome, the mandatory signal, and the dynamic branch prediction. The biased prediction correlator favors the dynamic branch prediction over the predicted outcome. If the mandatory signal indicates that the branch instruction is a biased outcome conditional branch instruction, however, then the biased prediction correlator favors the predicted outcome over the dynamic branch prediction.

Claims

1. An apparatus in a microprocessor for performing branch prediction, comprising:

a static branch predictor, configured to provide a predicted outcome for a branch instruction, and configured to determine if said branch instruction is a biased outcome conditional branch instruction;

a mandatory signal, produced by said static branch predictor, configured to indicate whether or not said branch instruction is said biased outcome conditional branch instruction, thereby indicating whether or not said predicted outcome takes precedence over a dynamic branch prediction for said branch instruction; and

a biased prediction correlator, coupled to said static branch predictor and said mandatory signal, configured to receive said predicted outcome, said mandatory signal, and said dynamic branch prediction, and configured to favor said dynamic branch prediction over said predicted outcome, wherein, if said mandatory signal indicates that said branch instruction is said biased outcome conditional branch instruction, then said biased prediction correlator favors said predicted outcome over said dynamic branch prediction.

2. The apparatus as recited in claim 1, wherein said biased outcome conditional branch instruction comprises one of a predefined subset of branch instructions specifying conditional tests for the microprocessor.

3. The apparatus as recited in claim 2, wherein said conditional tests comprise overflow, zero, carry, parity, and sign.

4. The apparatus as recited in claim 3, wherein said static predictor provides said predicted outcome based upon a displacement sign within said branch instruction.

5. The apparatus as recited in claim 1, wherein, if said mandatory signal indicates that said predicted outcome takes precedence over said dynamic branch prediction, then the microprocessor executes a first speculative branch in accordance with said predicted outcome provided by said static branch predictor.

6. The apparatus as recited in claim 5, wherein, if said predicted outcome is predicted taken, then the microprocessor executes said first speculative branch to a branch target address.

7. The apparatus as recited in claim 6, wherein, if said predicted outcome is predicted not taken, then the microprocessor does not execute said first speculative branch to said branch target address, but rather continues sequential instruction execution.

8. The apparatus as recited in claim 7, wherein, if said signal indicates that said predicted outcome does not take precedence over said dynamic branch prediction, then the microprocessor executes a second speculative branch in accordance with said dynamic branch prediction.