Branch prediction apparatus and process for restoring replaced branch history for use in future branch predictions for an executing program

• US 6,877,089 B2
• Filed: 12/27/2000
• Issued: 04/05/2005
• Est. Priority Date: 12/27/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sinharoy, Balaram
• Primary Examiner(s): Chan, Eddie
• Assistant Examiner(s): Huisman, David J
• Application Number:
  US09/748,841
• Publication Number:
  US 20020083312A1
• Time in Patent Office: 1,560 Days
• Field of Search: 712/228, 712/233, 712/234, 712/238, 712/239, 712/240
• US Class Current: 712/239
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/3005 to perform operations for flow control
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• 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

Apparatus and methods implemented in a processor semiconductor logic chip for providing novel “hint instructions” that uniquely preserve and reuse branch predictions replaced in a branch history table (BHT). A branch prediction is lost in the BHT after its associated instruction is replaced in an instruction cache. The unique “hint instructions” are generated and stored in a unique instruction cache which associates each hint instruction with a line of instructions. The hint instructions contains the latest branch history for all branch instructions executed in an associated line of instructions, and they are stored in the instruction cache during instruction cache hits in the associated line. During an instruction cache miss in an instruction line, the associated hint instruction is stored in a second level cache with a copy of the associated instruction line being replaced in the instruction cache. In the second level cache, the copy of the line is located through the instruction cache directory entry associated with the line being replaced in the instruction cache. Later, the hint instruction can be retrieved into the instruction cache when its associated instruction line is fetched from the second level cache, and then its associated hint instruction is also retrieved and used to restore the latest branch predictions for that instruction line. In the prior art this branch prediction would have been lost. It is estimated that this invention improves program performance for each replaced branch prediction by about 80%, due to increasing the probability of BHT bits correctly predicting the branch paths in the program from about 50% to over 90%. Each incorrect BHT branch prediction may result in the loss of many execution cycles, resulting in additional instruction re-execution overhead when incorrect branch paths are belatedly discovered.

Claims

1. A branch prediction process for a computer system for improving branch prediction rates when using a branch history table (BHT), comprising:

determining if a program instruction processor has an access hit (hit) or access miss (miss) in an instruction cache (I-cache) when utilizing an instruction address (IFAR address) in attempting to select a program instruction for execution by the program instruction processor,

generating a hint instruction when the program instruction is a branch in response to a hit occurring during the determining operation, storing the hint instruction in association with a copy of a program instruction line containing the program instruction in a storage hierarchy of the computer system, the hint instruction storing BHT prediction fields obtained from a copy of a current BHT entry associated with the program instruction line when the hit occurs, and storing a branch mask in the hint instruction for locating the program instruction in the program instruction line, and

transferring the copy of the program instruction line and associated hint instruction from the storage hierarchy to the I-cache in response to a miss occurring during the determining operation, and executing the hint instruction to restore a BHT prediction field in said current BHT entry to the state of a BHT field in the hint instruction located by the branch mask, and

the generating operation of generating hint instructions being performed by a hint processor operating in parallel with the program instruction processor, and

executing a hint instruction when the hint instruction is received in the I-cache by testing an operation code field in the hint instruction to determine if a completed hint instruction is indicated or if a no-operation state is indicated for the hint instruction, and continuing the executing process only if a completed hint instruction is indicated by performing the following operations;

reading a BHT entry in the BHT located at an index determined by a bht_index field in the hint instruction, and storing the BHT entry in a curr_bht register,

logically ANDing an Nth bit in an inversion of a branch_mask field in the hint instruction with an Nth bit in the curr_bht register, where N is the bit position of current instruction in the program instruction line, and logically ANDing the Nth bit in the branch_mask field with an Nth bit in a bht_bits field in the hint instruction,

logically ORing outputs of the two logical ANDing operations to provide an Nth bit output, and setting an Nth bit in a new_bht register to the Nth bit output, receiving without change in the new_bht register at bit locations other than at the Nth bit location the bits in the curr_bht register at corresponding bit locations other than the Nth bit location, and

setting contents of the new_bht register into the current BHT entry in the BHT to restore the BHT entry to its last prediction state for the current instruction.

2. The branch prediction process for a computer system for improving branch prediction rates when using a branch history table as defined by claim 1, further comprising:

performing all of the hint instruction operations in a hint instruction processor.

3. The branch prediction process for a computer system for improving branch prediction rates when using a branch history table as defined by claim 2, further comprising:

performing all hint instruction operations and all program instruction processor operations in a single semiconductor chip.