Two-level branch prediction cache

• US 5,163,140 A
• Filed: 03/02/1992
• Issued: 11/10/1992
• Est. Priority Date: 02/26/1990
• Status: Expired due to Term

• Current Assignee: Nexgen Incorporated (Advanced Micro Devices, Inc.)
• Original Assignee: Nexgen Microsystems
• Inventors: Van Dyke, Korbin S., Favor, John G., Stiles, David R.
• Primary Examiner(s): Chan, Eddie P.
• Application Number:
  US07/844,995
• Time in Patent Office: 253 Days
• Field of Search: 395/425, 395/375, 364/DIG. 1
• US Class Current: 711/140
• 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

An improved branch prediction cache (BPC) scheme that utilizes a hybrid cache structure. The BPC provides two levels of branch information caching. The fully associative first level BPC is a shallow but wide structure (36 32-byte entries), which caches full prediction information for a limited number of branch instructions. The second direct mapped level BPC is a deep but narrow structure (256 2-byte entries), which caches only partial prediction information, but does so for a much larger number of branch instructions. As each branch instruction is fetched and decoded, its address is used to perform parallel look-ups in the two branch prediction caches.

Claims

1. In a computer system having decode logic responsive to fetched instructions and an instruction cache from which instructions, including branch instructions, are fetched for execution, the improvement comprising:

means for generating an input PC representative of the address of an encountered instruction;

a first level branch prediction cache (BPC), separate from the instruction cache, having a first number N1 of lines for storing prediction information on up to N1 previously encountered branch instructions, each line capable of storing an entry providing prediction information at a first level of detail including the address of the branch instruction for which prediction information is stored, a target address for the branch instruction, target instruction bytes corresponding to the instruction stream starting at the target address, and branch history information representing the direction taken during at least one previous execution of the branch instruction;

means, associated with said first level BPC, for comparing said input PC with the address of the branch instruction in each of the first level BPC entries, and, in the event of a match between the input PC and the address of the branch instruction in the first level BPC entry, for enabling a first level BPC entry to be output and target instruction bytes in the first level BPC entry to be communicated to the decode logic;

a second level BPC, separate from the instruction cache, having a second number N2 of lines, larger than said first number of lines, for storing prediction information on up to N2 previously encountered branch instructions, each line capable of storing an entry providing prediction information at a second level of detail, lower than said first level of detail, including a portion of a target instruction address and branch history information representing the direction taken during at least one previous execution of the branch instruction for which prediction information is stored, said second level BPC being indexed by only a portion of the input PC; and

means, associated with said second level BPC, for enabling a second level BPC entry to be output for use in the event that no match exists in said first level BPC.

2. The improvement of claim 1 wherein said second level BPC contains no tag bits relating to said input PC.

3. In the operation of a computer system wherein instructions, including branch instructions, are fetched for execution and communicated to decode logic, a method of predicting branch outcome, comprising the steps of:

generating an input PC representative of the address of an encountered instruction;

providing a first level BPC having a first number of lines;

storing in each of at least some of the lines of the first level BPC respective entries providing information corresponding to respective previously encountered branch instructions, each entry including the address of the respective branch instruction, a target address for the respective branch instruction, target instruction bytes corresponding to the instruction stream starting at the target address, and branch history information representing the direction taken during at least one previous execution of the respective branch instruction;

comparing the input PC with the address of the branch instruction in each of the first level BPC entries, and, in the event of a match between the PC and the address of the branch instruction for a particular first level BPC entry, enabling the particular first level BPC entry to be output and target bytes in the first level BPC entry to be communicated to the decode logic; and

providing a second level BPC having a second number, larger than said first number, of lines;

storing in each of at least some of the lines of the second level BPC respective entries providing information corresponding to respective previously encountered branch instructions, each entry including a portion of a target instruction address and branch history information representing the direction taken during at least one previous execution of the branch instruction, the second level BPC being indexed by only a portion of the input PC; and

enabling a second level BPC entry to be output for use in the event that no match exists in the first level BPC.