Branch Predictor for Wide Issue, Arbitrarily Aligned Fetch

Abstract

In an embodiment, a processor may be configured to fetch N instruction bytes from an instruction cache (a “fetch group”), even if the fetch group crosses a cache line boundary. A branch predictor may be configured to produce branch predictions for up to M branches in the fetch group, where M is a maximum number of branches that may be included in the fetch group. In an embodiment, a branch direction predictor may be updated responsive to a misprediction and also responsive to the branch prediction being within a threshold of transitioning between predictions. To avoid a lookup to determine if the threshold update is to be performed, the branch predictor may detect the threshold update during prediction, and may transmit an indication with the branch.

What is claimed is: 
     
         1 . A processor comprising:
 a branch direction predictor configured to generate a branch direction prediction corresponding to a branch instruction, wherein the branch direction predictor is configured to detect whether or not a branch prediction value associated with the branch direction prediction is within a changing threshold and is configured to transmit an indication with each branch direction prediction indicating whether or not the branch prediction value is within the threshold; and   a branch execution unit coupled to the branch direction predictor, wherein the branch execution unit is configured to execute a branch instruction, and wherein the branch execution unit is configured to generate an update request for the branch direction predictor responsive to the indication indicating update, even in a case that the branch execution unit would not generate an update due to a result of executing the branch instruction.   
     
     
         2 . The processor as recited in  claim 1  wherein the branch execution unit is configured to detect a misprediction of the branch direction of the branch instruction, and wherein the branch execution unit is configured to generate the update request in response to the misprediction. 
     
     
         3 . The processor as recited in  claim 2  wherein the branch execution unit is configured to generate a branch direction of the branch instruction, and wherein the branch execution unit is configured to generate the update request responsive to the branch direction and the indication indicating update. 
     
     
         4 . The processor as recited in  claim 1  wherein the branch execution unit is configured to generate the update in response to the indication even in the case that the branch direction prediction is correct. 
     
     
         5 . The processor as recited in  claim 1  wherein the branch predictor is configured to generate a branch direction prediction for potential branch instructions in a fetch group according to a first instruction set implemented by the processor and a size of the fetch group. 
     
     
         6 . The processor as recited in  claim 5  wherein the size of the fetch group is fixed and crosses a cache line boundary for at least some values of the fetch address. 
     
     
         7 . The processor as recited in  claim 5  wherein the processor also implements a second instruction set, and wherein a number of the branch direction predictions is less than a number of the potential branch instructions in the fetch group for the second instruction set. 
     
     
         8 . A method comprising:
 reading a plurality of branch prediction tables in response to a fetch address, wherein the tables are configured to output at least one value from an entry of the table, and wherein an index to each table of the plurality of branch prediction tables is generated differently;   summing the values output from the tables, wherein a sign of the sum indicates a direction prediction for a branch instruction;   predicting the direction of the branch instruction responsive to the sign;   detecting that the sum is within a threshold value of zero responsive to the summing, wherein the tables are trained responsive to the sum being within the threshold value of zero; and   transmitting an indication that the tables are to be trained responsive to the detecting that the sum is within a threshold value of zero.   
     
     
         9 . The method as recited in  claim 8  further comprising:
 executing the branch instruction; and 
 updating the plurality of branch prediction tables responsive to the indication even in a case that the direction prediction is correct. 
 
     
     
         10 . The method as recited in  claim 8  further comprising:
 executing a second branch instruction, wherein the sum corresponding to the second branch instruction is not within the threshold; 
 detecting that a second direction prediction corresponding to the second branch instruction is correct; and 
 not updating the plurality of branch prediction tables responsive to the detecting and the sum being not within the threshold. 
 
     
     
         11 . The method as recited in  claim 8  further comprising:
 executing a second branch instruction; 
 detecting that a second direction prediction corresponding to the second branch instruction is incorrect; and 
 updating the plurality of branch prediction tables responsive to the detecting and independent of whether or not the sum corresponding to the second branch instruction is within the threshold. 
 
     
     
         12 . A processor comprising a branch direction predictor, the branch prediction predictor including:
 an index generator configured to generate a plurality of indexes responsive to a fetch address and branch history data;   a plurality of branch prediction tables coupled to the index generator, wherein the tables are addressed using respective indexes generated by the index generator, and the tables configured to output at least one value in response to the respective index; and   at least one adder configured to:
 sum the at least one value from the tables to generate a branch direction prediction; 
 generate an indication that the sum is within a threshold of changing the branch direction prediction; and 
 transmit an indication with the branch direction prediction indicating whether or not the sum is within the threshold. 
   
     
     
         13 . The processor as recited in  claim 12  further comprising a branch execution unit coupled to the branch direction predictor, wherein the branch execution unit is configured to execute the branch instruction corresponding to the branch direction prediction, and wherein the branch execution unit is configured to generate an update request for the branch direction predictor responsive to the indication indicating that the sum is within a threshold of changing direction, even in a case that the branch execution unit would not generate an update due to a result of executing the branch instruction. 
     
     
         14 . The processor as recited in  claim 13  wherein the branch execution unit is configured to detect a misprediction of the branch direction of the branch instruction, and wherein the branch execution unit is configured to generate the update request in response to the misprediction. 
     
     
         15 . The processor as recited in  claim 13  wherein the branch execution unit is configured to generate a branch direction of the branch instruction, and wherein the branch execution unit is configured to generate the update request responsive to the branch direction and the indication indicating update. 
     
     
         16 . The processor as recited in  claim 13  wherein the branch execution unit is configured to generate the update in response to the indication even in the case that the branch direction prediction is correct. 
     
     
         17 . The processor as recited in  claim 13  wherein the branch predictor is configured to generate a branch direction prediction for each potential branch instruction in a fetch group according to a first instruction set implemented by the processor and a size of the fetch group. 
     
     
         18 . The processor as recited in  claim 17  wherein the size of the fetch group is fixed and crosses a cache line boundary for at least some values of the fetch address. 
     
     
         19 . The processor as recited in  claim 17  wherein the processor also implements a second instruction set, and wherein a number of the branch direction predictions is less than a number of the potential branch instructions in the fetch group for the second instruction set. 
     
     
         20 . The processor as recited in  claim 12  wherein the update includes an update for the branch prediction value corresponding to the branch instruction in each of the plurality of branch prediction tables.