Multiple global pattern history tables for branch prediction in a microprocessor

• US 5,935,241 A
• Filed: 12/10/1997
• Issued: 08/10/1999
• Est. Priority Date: 12/10/1996
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Shiell, Jonathan H., Cai, George Z. N.
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): Monestime, Mackly
• Application Number:
  US08/987,951
• Time in Patent Office: 608 Days
• Field of Search: 395/586, 395/580, 395/581, 395/583, 395/585, 395/582, 395/587, 395/584, 712/240, 712/239, 712/238, 712/234, 712/236, 712/237, 712/235, 712/233
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A microprocessor (10) and a system (300) incorporating the same is disclosed, in which branch prediction is effected in response to the type of program in which branching instructions are contained. A fetch unit (26) includes a branch target buffer (56) and a plurality of pattern history tables (53). Select logic (80) receives signals indicating, for each branching instruction, the type of program containing the instruction, and selects one of the pattern history tables (53) for use in generating a prediction code in response to a portion of a branch history field (BH) in an entry (63) of the branch target buffer (56) corresponding to the instruction address. Disclosed examples of the signals used in selecting the pattern history table (53) include an indication (U/S) of the privilege level (e.g., user-level or supervisor-level) of the instruction. A range register unit (75) for determining whether the instruction is contained within an address range is also disclosed as used in the selection of the pattern history table (53).

Claims

1. A microprocessor, comprising:

an execution unit for executing instructions according to a plurality of program types;

a memory for storing instruction codes of instructions; and

a fetch unit, for addressing the memory to retrieve instruction codes for execution by the execution unit, comprising;

a branch history circuit, for storing a sequence of results of branching instructions executed by the execution unit;

a plurality of pattern history tables coupled to the branch history circuit, each having a plurality of indexed prediction code entries, and each having an output for presenting the contents of one of the prediction code entries corresponding to a branch history field from the branch history circuit;

an addressing circuit for selecting an address for an instruction to be fetched; and

select logic, coupled to receive a program type indicator, for selectively forwarding, to the addressing circuit, the output of one of the plurality of pattern history tables corresponding to the program type indicator.

2. The microprocessor of claim 1, wherein the branch history circuit comprises a global branch history buffer.

3. The microprocessor of claim 1, wherein the branch history circuit comprises:

a branch target buffer comprised of a plurality of entries, each entry having a tag field corresponding to the instruction address of an associated branching instruction, having a branch history field for storing a sequence of previous branches of its associated branching instruction.

4. The microprocessor of claim 3, wherein each of the plurality of entries in the branch target buffer further comprises a target field for storing a branch target address;

and wherein the addressing circuit, responsive to the select logic forwarding an output corresponding to a branch-taken prediction, selects an address corresponding to the branch target address of the entry corresponding to the associated branching instruction.

5. The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises a privilege level indicator corresponding to a program containing the branching instruction.

6. The microprocessor of claim 5, wherein the privilege level indicator comprises a bit of a code segment register corresponding to the branching instruction.

7. The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises at least one bit of a page table entry for a portion of memory containing the branching instruction.

8. The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises at least one bit of a segment descriptor for a portion of memory containing the branching instruction.

9. The microprocessor of claim 1, wherein the program type indicator of a branching instruction comprises at least one bit of the instruction address of the branching instruction.

10. The microprocessor of claim 1, wherein the select logic comprises:

a multiplexer having inputs for receiving outputs from each of the plurality of pattern history tables and having an output coupled to the branch history circuit, for selecting the output of one of the plurality of pattern history tables for forwarding to the branch history circuit.

11. The microprocessor of claim 10, wherein the program type indicator for a branching instruction comprises a privilege level indicator corresponding to a program containing the branching instruction;

and wherein the multiplexer of the select logic has a control input coupled to receive the privilege level indicator.

12. The microprocessor of claim 11, wherein the select logic further comprises:

logic for generating control signals to the multiplexer responsive to a logical combination of the privilege level indicator and to a global bit of a page table entry for a portion of memory containing the branching instruction.

13. The microprocessor of claim 1, wherein the select logic comprises:

a first pair of range registers for storing a maximum and a minimum address value, respectively; and

a first comparator for comparing a portion of the instruction address of a branching instruction to the contents of the first pair of range registers;

wherein the program type indicator comprises the result of the comparing performed by the first comparator.

14. The microprocessor of claim 13, wherein the select logic further comprises:

a second pair of range registers for storing a maximum and a minimum address value, respectively;

a second comparator for comparing a portion of the instruction address of the branching instruction to the contents of the second pair of range registers; and

logic for generating an in/out signal corresponding to the result of a selected one of the first and second comparators, selected responsive to the state of a privilege level indicator corresponding to a program containing the branching instruction.

15. The microprocessor of claim 14, wherein the program type indicator comprises a combination of the state of the in/out signal with the privilege level indicator.

16. The microprocessor of claim 15, wherein the select logic comprises:

a multiplexer having inputs for receiving outputs from each of the plurality of pattern history tables, having an output coupled to the branch target buffer, and having control inputs coupled to receive the in/out signal and the privilege level indicator.

17. A method of operating a pipelined microprocessor to speculatively execute branching instructions in a program of microprocessor instructions, comprising the steps of:

detecting a branch instruction at a fetch stage of the pipelined microprocessor;

responsive to the detecting step, retrieving at least a portion of a branch history field;

determining a program type corresponding to the branch instruction; and

generating a branch prediction corresponding to the retrieved portion of the branch history field from one of a plurality of pattern history tables selected according to the program type.

18. The method of claim 17, further comprising:

responsive to the detecting step, applying an instruction address to a branch target buffer, the branch target buffer having a plurality of entries, each having a tag field for storing an instruction identifier, and having a branch history field for storing branch results;

wherein the retrieving step is performed responsive to a portion of the applied instruction address matching the tag field of one of the plurality of entries.

19. The method of claim 17, wherein the determining step comprises:

interrogating the state of a privilege level indicator corresponding to the program containing the detected branching instruction.

20. The method of claim 19, wherein the privilege level indicator comprises a bit of a code segment register corresponding to the detected branching instruction.

21. The method of claim 17, wherein the determining step comprises:

interrogating the state of at least one bit of a page table entry for a portion of memory containing the detected branching instruction.

22. The method of claim 17, wherein the determining step comprises:

interrogating the state of at least one bit of a segment descriptor for a portion of memory containing the detected branching instruction.

23. The method of claim 17, wherein the determining step comprises:

comparing the detected branching instruction address to the contents of a first pair of range registers to determine if the detected branching instruction address is within the range specified thereby.

24. The method of claim 23, wherein the determining step further comprises:

comparing the detected branching instruction address to the contents of a plurality of pairs of range registers to determine if the detected branching instruction address is within the ranges specified thereby; and

interrogating the state of a privilege level indicator corresponding to the program containing the detected branching instruction;

and further comprising;

selecting one of the plurality of pattern history tables responsive to the state of the privilege level indicator and to the result of the comparing step performed by one of the plurality of pairs of range registers selected responsive to the state of the privilege level indicator.