Method and system for branch target prediction using path information

Abstract

A system and method for predicting a branch target for a current instruction in a microprocessor, the system comprising a cache storing indirect branch instructions and a path register. The path register is updated on certain branches by an XOR operation on the path register and the branch instruction, followed by the addition of one or more bits to the register. The cache is indexed by performing an operation on a portion of the current instruction address and the path register; the entry returned, if any, may be used to predict the target of the current instruction.

1 . A system comprising: 
 a register to store a current register value, where at least a portion of the current register value is generated from a first computation, the first computation comprising a first operation on a previous register value and a set of bits from a previous branch address; and    a first table to store branch target values, the first table indexed by a result of a second computation on the current register value and the branch address of the current branch instruction.    
   
   
       2 . The system of  claim 1  wherein the first operation is an exclusive OR operation.  
   
   
       3 - 8 . (canceled)  
   
   
       9 . The system of  claim 1  further comprising: 
 a buffer to store branch target values, wherein:    the buffer is to either provide a buffer prediction for the current branch instruction or return a buffer miss;    the first table is to either provide a first table prediction for the current branch instruction or return a first table miss; and    if a buffer prediction is to be provided, the system is to return a prediction.    
   
   
       10 - 11 . (canceled)  
   
   
       12 . A method comprising: 
 placing in a register the result of a first calculation on the register and a set of bits from an address of a completed branch instruction;    creating an index by performing a second calculation on the register and a set of bits from an address of a current branch instruction; and    using the index to find a target address for the second branch address in a first table, where the first table either provides a first table prediction for the current branch instruction or returns a first table miss.    
   
   
       13 . The method of  claim 12  where the first calculation comprises an XOR operation.  
   
   
       14 - 25 . (canceled)  
   
   
       26 . The method of  claim 12  further comprising: 
 adding entries to the first table only for branch instructions which have not been marked as being predictable.    
   
   
       27 . (canceled)  
   
   
       28 . The method of  claim 13  where the first table is a cache.  
   
   
       29 - 31 . (canceled)  
   
   
       32 . A system comprising: 
 a register to store a current register value, wherein at least a portion of the current register value is generated from a first computation, the first computation comprising an exclusive OR (XOR) operation on a previous register value and a set of bits from a previous branch address;    a first table to store branch target values, the first table being indexed by a result of a second computation on the current register value and the branch address of the current branch instruction; and    a second table to store branch target values for indirect branches and branch target values for direct branches, wherein the first table stores branch target values for indirect branches.    
   
   
       33 . The system of  claim 32  wherein: 
 the second table is a branch target buffer; and    the second table is indexed by a portion of the branch address of the current branch instruction.    
   
   
       34 . The system of  claim 32  wherein: 
 the second table is to either provide a second table prediction and a type prediction for the current branch instruction or return a second table miss;    the first table is to either provide a first table prediction for the current branch instruction or return a first table miss; and    if, for the current branch instruction, a second table prediction is to be provided, a first table prediction is to be provided, and the type prediction is to be indirect, the system is to form a branch target prediction from the contents of the first table.    
   
   
       35 . The system of  claim 32  wherein the first computation further comprises logic to shift left by one bit a value and an OR operation, where one operand of the OR operation is 0 if the previous branch address is for a first type of branch and 1 if the previous branch address is for a second type of branch; and an entry from the first table is returned as a prediction only if a second table hit occurs.  
   
   
       36 . An apparatus comprising: 
 first means for storing branch target values, the first means indexed by a result of a first computation on a current register value and a current branch address of a current branch instruction,    wherein at least a portion of the current register value is formed from a second computation, the second computation comprising a first operation on a previous register value and a set of bits from a previous branch address.    
   
   
       37 . The apparatus of  claim 36  wherein the first operation is an exclusive OR operation.  
   
   
       38 . The apparatus of  claim 37  further comprising a second means for storing branch target values for indirect branches and branch target values for direct branches, where the first means stores branch target values for indirect branches.  
   
   
       39 . The apparatus of  claim 38  wherein: 
 the second means is a branch target buffer; and    the second means is indexed by a portion of the current branch address of the current branch instruction.    
   
   
       40 . The apparatus of  claim 38  wherein: 
 the second means either provides a second prediction and a type prediction for the current branch instruction or returns a second miss;    the first means either provides a first prediction for the current branch instruction or returns a first miss; and    if, for the current branch instruction, a second prediction is provided, a first prediction is provided, and the type prediction is indirect, and a branch target prediction is formed from the contents of the first means.    
   
   
       41 . The apparatus of  claim 37  further comprising a second means for storing branch target values for indirect branches and branch target values for direct branches, wherein: 
 the first means stores branch target values for indirect branches;    the second computation further comprises a shift left one bit operation and an OR operation, where one operand of the OR operation is 0 if the previous branch address is for a first type of branch and 1 if the previous branch address is for a second type of branch; and    an entry from the first means is returned as a prediction only if a second means hit occurs.    
   
   
       42 . The apparatus of  claim 36  where the second computation further comprises: 
 a shift left operation; and    an OR operation.    
   
   
       43 . The apparatus of  claim 42  wherein: 
 the first means is a cache;    the shift left operation shifts left one bit; and    one operand of the OR operation is 0 if the previous branch address is for a first type of branch and 1 if the previous branch address is for a second type of branch.    
   
   
       44 . The apparatus of  claim 43  wherein: 
 each branch target value corresponds to an indirect branch.    
   
   
       45 . The apparatus of  claim 36  further comprising: 
 branch target values are to be stored in a buffer, wherein:    the second means either provides a second prediction for the current branch instruction or returns a second miss;    the first means either provides a first prediction for the current branch instruction or returns a first miss; and    if a second prediction is provided, a prediction is returned.    
   
   
       46 . The apparatus of  claim 36  further comprising a second means for having a plurality of entries, each entry storing a branch target value for a branch and a second entry error counter, the second entry error counter being recalculated when the second entry provides a prediction; where: 
 the first means comprises a plurality of entries, each entry storing a branch target value for an indirect branch;    if, for a second entry, the second entry error counter reaches a certain value, a first entry corresponding to the second entry is created; and    an entry from the first means is returned as a prediction only if a second hit occurs.    
   
   
       47 . An apparatus comprising: 
 a first table to store branch target values, the first table indexed by a result of a first computation on a current register value and a current branch address of a current branch instruction,    wherein at least a portion of the current register value is to be formed from a second computation, the second computation comprising a first operation on a previous register value and a set of bits from a previous branch address.    
   
   
       48 . The apparatus of  claim 47  wherein the first operation is to be an exclusive OR operation.  
   
   
       49 . The apparatus of  claim 48  further comprising a second table to store branch target values for indirect branches and branch target values for direct branches, where the first table is to store branch target values for indirect branches.  
   
   
       50 . The apparatus of  claim 49  wherein: 
 the second table is to be a branch target buffer; and    the second table is to be indexed by a portion of the current branch address of the current branch instruction.    
   
   
       51 . The apparatus of  claim 49  wherein: 
 the second table is either to provide a second table prediction and a type prediction for the current branch instruction or to return a second table miss;    the first table is either to provide a first table prediction for the current branch instruction or to return a first table miss; and    if, for the current branch instruction, a second table prediction is provided, a first table prediction is to be provided, and the type prediction is to be indirect, and a branch target prediction is to be formed from the contents of the first table.    
   
   
       52 . The apparatus of  claim 48  further comprising a second table to store branch target values for indirect branches and branch target values for direct branches, wherein: 
 the first table is to store branch target values for indirect branches;    the second computation further comprises a shift left one bit operation and an OR operation, wherein one operand of the OR operation is to be 0 if the previous branch address is to be for a first type of branch and 1 if the previous branch address is to be for a second type of branch; and    an entry from the first table is to be returned as a prediction only if a second table hit occurs.    
   
   
       53 . The apparatus of  claim 47  wherein the second computation further comprises: 
 a shift left operation; and    an OR operation.    
   
   
       54 . The apparatus of  claim 53  wherein: 
 the first table is a cache;    the shift left operation is to shift left one bit; and    one operand of the OR operation is to be 0 if the previous branch address is for a first type of branch and 1 if the previous branch address is for a second type of branch.    
   
   
       55 . The apparatus of  claim 54  wherein: 
 each branch target value is to correspond to an indirect branch.    
   
   
       56 . The apparatus of  claim 47  wherein: 
 branch target values are to be stored in a buffer;    the buffer is either to provide a buffer prediction for the current branch instruction or to return a buffer miss;    the first table is to either provide a first table prediction for the current branch instruction or to return a first table miss; and    if a buffer prediction is to be provided, a prediction is returned.    
   
   
       57 . The apparatus of  claim 47  further comprising a second table to store a plurality of entries, each entry to store a branch target value for a branch and a second table entry error counter, the second table entry error counter to be recalculated when the second table entry provides a prediction; wherein: 
 the first table comprises a plurality of entries, each entry to store a branch target value for an indirect branch;    if, for a second table entry, the second table error counter reaches a certain value, a first table entry corresponding to the second table entry is to be created; and    an entry from the first table is to be returned as a prediction only if a second table hit occurs.