Multi-level PHT entry swaps based on first level miss and second level hit

Abstract

A branch prediction logic system includes a branch history table (BHT), a multi-level history table, and a prediction update queue. The BHT includes a plurality of lines, each line corresponding to at least one branch instruction and containing history information specific to the at least one branch instruction. A first pattern history table (PHT-1) stores first branch data corresponding to the at least one branch instruction included in a given line of the BHT and a second pattern history table (PHT-2) stores second branch data corresponding to the at least one branch instruction included in a given line. The prediction update queue stores a line presence bit having one of a “1” logic state or a “0” logic state. The branch prediction logic system performs a data swap between the PHT-2 and the PHT-1 based on the logic state of the line presence bit.

What is claimed is: 
     
         1 . A computing system including a branch prediction logic system comprising:
 a branch history table (BHT) including a plurality of lines, each line corresponding to at least one branch instruction and containing history information specific to the at least one branch instruction;   a multi-level pattern history table configured to store branch data indexed to the at least one branch instruction, the multi-level pattern history table including a first pattern history table (PHT-1) configured to store first branch data corresponding to the at least one branch instruction included in a given line of the BHT and a second pattern history table (PHT-2) configured to store second branch data corresponding to the at least one branch instruction included in a given line; and   a prediction update queue (PUQ) configured to store at least one PUQ entry corresponding to the at least one branch instruction, the PUQ entry including a line presence bit having one of a “1” logic state or a “0” logic state,   wherein the branch prediction logic system is configured to perform a data swap between the PHT-2 and the PHT-1 based on the logic state of the line presence bit, the data swap including replacing, at the same index, the first branch data stored in the PHT-1 with the second branch data, and replacing, at the same index, the second branch data stored in the PHT-2 with the first branch data.   
     
     
         2 . The computing system of  claim 1 , wherein a combination of the first branch data and the history information provides first result data when the at least one branch instruction corresponding to the first branch data completes, and wherein a combination of the second branch data and the history information provides second result data when the at least one branch instruction corresponding to the second branch data completes. 
     
     
         3 . The computing system of  claim 2 , wherein the branch prediction logic system updates the PHT-1 and the BHT based on the first result data, and updates the PHT-2 and the BHT based on the second result data. 
     
     
         4 . The computing system of  claim 3 , wherein the branch prediction logic system performs the data swap when a completed branch from the line matches a PUQ entry indicating a need to update, the matching PUQ entry includes the line presence bit set to the “1” logic state, and the completed branch indexes to the second branch data in the PHT-2. 
     
     
         5 . The computing system of  claim 4 , wherein the branch prediction logic system maintains the first branch data in the PHT-1 and the second branch data in the PHT-2 when the matching PUQ entry includes the line presence bit set to the “0” logic state. 
     
     
         6 . A computer implemented method comprising:
 storing a plurality of lines in a branch history table (BHT), each line corresponding to at least one branch instruction and containing history information specific to the at least one branch instruction;   storing, in a first pattern history table (PHT-1) of a multi-level pattern history table, first branch data corresponding to the at least one branch instruction included in a given line of the BHT;   storing, in a second pattern history table (PHT-2) of the multi-level pattern history table, second branch data corresponding to the at least one branch instruction included in a given line;   storing, in a prediction update queue, at least one PUQ entry corresponding to the at least one branch instruction, the PUQ entry including a line presence bit having one of a “1” logic state or a “0” logic state; and   performing a data swap between the PHT-2 and the PHT-1 based on the logic state of the line presence bit, the data swap including replacing, at the same index, the first branch data stored in the PHT-1 with the second branch data, and replacing, at the same index, the second branch data stored in the PHT-2 with the first branch data.   
     
     
         7 . The computer implemented method of  claim 6 , further comprising:
 providing first result data based on a combination of the first branch data and the history information in response to completion of the at least one branch instruction corresponding to the first branch data; and   providing second result data based on a combination of the second branch data and the history information in response to completion of the at least one branch instruction corresponding to the second branch data.   
     
     
         8 . The computer implemented method of  claim 7 , further comprising:
 updating the PHT-1 and the BHT based on the first result data; and   updating the PHT-2 and the BHT based on the second result data.   
     
     
         9 . The computer implemented method of  claim 8 , further comprising:
 performing the data swap in response to:
 a completed branch from the line corresponds to a matching PUQ entry indicating a need to update; 
 the matching PUQ entry including the line presence bit set to the “1” logic state; and 
 the completed branch indexes to the second branch data in the PHT-2. 
   
     
     
         10 . The computer implemented method of  claim 9 , further comprising:
 maintaining the first branch data in the PHT-1 and the second branch data in the PHT-2 when the matching PUQ entry includes the line presence bit set to the “0” logic state.   
     
     
         11 . A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform operations comprising:
 storing a plurality of lines in a branch history table (BHT), each line corresponding to at least one branch instruction and containing history information specific to the at least one branch instruction;   storing, in a first pattern history table (PHT-1) of a multi-level pattern history table, first branch data corresponding to the at least one branch instruction included in a given line of the BHT;   storing, in a second pattern history table (PHT-2) of the multi-level pattern history table, second branch data corresponding to the at least one branch instruction included in a given line;   storing, in a prediction update queue, at least one PUQ entry corresponding to the at least one branch instruction, the PUQ entry including a line presence bit having one of a “1” logic state or a “0” logic state; and   performing a data swap between the PHT-2 and the PHT-1 based on the logic state of the line presence bit, the data swap including replacing, at the same index, the first branch data stored in the PHT-1 with the second branch data, and replacing, at the same index, the second branch data stored in the PHT-2 with the first branch data.   
     
     
         12 . The computer program product of  claim 11 , further comprising:
 providing first result data based on a combination of the first branch data and the history information in response to completion of the at least one branch instruction corresponding to the first branch data; and   providing second result data based on a combination of the second branch data and the history information in response to completion of the at least one branch instruction corresponding to the second branch data.   
     
     
         13 . The computer program product of  claim 12 , further comprising:
 updating the PHT-1 and the BHT based on the first result data; and   updating the PHT-2 and the BHT based on the second result data.   
     
     
         14 . The computer program product of  claim 13 , further comprising:
 performing the data swap in response to:
 a completed branch from the line corresponds to a matching PUQ entry indicating a need to update; 
 the matching PUQ entry including the line presence bit set to the “1” logic state; 
 the completed branch indexes to the second branch data in the PHT-2. 
   
     
     
         15 . The computer program product of  claim 14 , further comprising:
 maintaining the first branch data in the PHT-1 and the second branch data in the PHT-2 when the matching PUQ entry includes the line presence bit set to the “0” logic state.