Method and apparatus for performing predicate prediction

Abstract

A method and apparatus for performing predicate prediction. In one method, both a predicted predicate value for a predicate and a confidence value for the predicted predicate value are determined.

What is claimed is:  
     
         1 . A method of performing predicate prediction in a processor, the method comprising: 
 determining a predicted predicate value for a predicate; and    determining a confidence value for the predicted predicate value.    
     
     
         2 . The method of    claim 1   , further comprising stalling a portion of the processor if the confidence value has a predetermined logical relationship to a predetermined value.  
     
     
         3 . The method of    claim 2   , wherein stalling continues until an actual predicate value is determined for the predicate.  
     
     
         4 . The method of    claim 2   , wherein stalling continues for a predetermined period of time.  
     
     
         5 . The method of    claim 4   , wherein the predetermined period of time is less than the recovery time for a mispredicted predicate.  
     
     
         6 . The method of    claim 2   , further comprising predicting the predicate to be the predicted predicate value if the confidence value is greater than or equal to the predetermined value.  
     
     
         7 . The method of    claim 1   , further comprising predicting the predicate to be the predicted predicate value if the confidence value has a predetermined logical relationship to a predetermined value.  
     
     
         8 . The method of    claim 1   , wherein determining the confidence value comprises tracking correct and incorrect predictions for the predicate.  
     
     
         9 . The method of    claim 2   , wherein determining the confidence value comprises tracking correct and incorrect predictions for the predicate.  
     
     
         10 . A method of performing predicate prediction in a computer system, the method comprising the steps of: 
 accessing a first entry corresponding to a first predicate in a table;    predicting the first predicate to be a first predicted predicate value in response to accessing the first entry;    creating a modified first entry in the table if it is determined that the first predicted predicate value is incorrect;    accessing the modified first entry corresponding to the first predicate in the table; and    stalling execution of a first instruction that is predicated on the first predicate in response to accessing the modified first entry.    
     
     
         11 . The method of    claim 10   , further comprising the steps of: 
 accessing a second entry corresponding to a second predicate in the table;    predicting the second predicate to be a second predicted predicate value in response to accessing the second entry;    creating a modified second entry in the table if it is determined that the second predicted predicate value is incorrect;    accessing the modified second entry corresponding to the second predicate in the table; and    stalling execution of a second instruction that is predicated on the second predicate in response to accessing the modified second entry.    
     
     
         12 . The method of    claim 10   , wherein the step of accessing the first entry comprises the sub-steps of: 
 searching for the first predicate in the table; and    reading a first confidence value corresponding to the first predicted predicate value.    
     
     
         13 . The method of    claim 12   , wherein the step of creating the first entry comprises the step of changing the first confidence value.  
     
     
         14 . The method of    claim 10   , wherein the step of predicting comprises the sub-steps of: 
 searching for the first predicate in the table;    reading a first predicted predicate value corresponding to the first predicate in the table; and    conditionally executing the first instruction depending on the first predicted predicate value.    
     
     
         15 . The method of    claim 10   , further comprising the steps of fetching the first instruction before the step of accessing the first entry, and re-fetching the first instruction after the step of creating the first entry and before the step of accessing the modified first entry.  
     
     
         16 . The method of    claim 10   , wherein the step of stalling continues until an actual predicate value is determined for the first predicate.  
     
     
         17 . A predicate predictor in a processor, the predicate predictor comprising: 
 a predicate table including a first initial entry corresponding to a first predicate; and    an output circuit coupled to the table to either predict the first predicate or to cause a portion of the processor to stall based on the first initial entry.    
     
     
         18 . The predicate predictor of    claim 17   , further comprising an input circuit coupled to the table to insert a first modified entry in the table corresponding to the first predicate, the first modified entry being based on the first initial entry and a first actual predicate value.  
     
     
         19 . The predicate predictor of    claim 17   , wherein the predicate table further includes a second initial entry corresponding to a second predicate, and the output circuit either predicts the second predicate or causes the portion of the processor to stall based on the second initial entry.  
     
     
         20 . The predicate predictor of    claim 19   , further comprising an input circuit coupled to the table to insert a first modified entry and a second modified entry in the table corresponding to the first predicate and the second predicate, respectively, the first modified entry being based on the first initial entry and a first actual predicate value, and the second modified entry being based on the second initial entry and a second actual predicate value.  
     
     
         21 . The predicate predictor of    claim 17   , wherein the output circuit predicts the first predicate if the first initial entry indicates that a first confidence value corresponding to a first predicted predicate value is greater than a predetermined value, and the output circuit otherwise causes a portion of the processor to stall.  
     
     
         22 . The predicate predictor of    claim 17   , wherein the output circuit predicts the first predicate if the first initial entry indicates that a first confidence value corresponding to a first predicted predicate value is less than a predetermined value, and the output circuit otherwise causes a portion of the processor to stall.