Branch target prediction for multi-target branches by identifying a repeated pattern

Abstract

An information processing system for branch target prediction includes: a first memory for storing entries for multi-target branch, wherein each entry includes a plurality of target addresses representing a history of target addresses for each single branch in the multi-target branch, and wherein said first memory stores an entry for the branch only if the branch is a multi-target branch; hardware logic for reading the memory and identifying a repeated pattern in each of the plurality of target addresses for the multi-target branch; logic for predicting a next target address for the multi-target branch based on the repeated pattern that was identified, using a pattern matching algorithm; and a second memory for storing information regarding whether a branch is a multi-target branch; wherein the logic for reading and the logic for predicting are executed only if the branch is the multi-target branch.

1 . An information processing system for branch target prediction, the system comprising:
 a first memory for storing entries for each multi-target branch, wherein each entry includes a plurality of target addresses representing a history of target addresses for each single branch in the multi-target branch, and wherein an entry is stored for the branch in the first memory only if the branch is a multi-target branch;   a branch program counter comprising an instruction address for a fetched branch;   a branch target buffer;   hardware logic for reading the memory and identifying a repeated pattern in each of the plurality of target addresses for the multi-target branch;   logic for predicting a next target address for the multi-target branch based on the repeated pattern that was identified, using a pattern matching algorithm; and   a second memory for storing a table comprising information used to distinguish regarding whether a selected branch is a multi-target branch, and wherein the table is indexed with a branch program counter of the selected branch,   wherein the logic for reading and the logic for predicting are executed only if the branch is the multi-target branch.   
   
   
       2 . The information processing system of  claim 1 , wherein the multi-target branch is an indirect multi-target branch. 
   
   
       3 . The information processing system of  claim 1 , wherein each entry includes a first-in-first-out queue for storing the plurality of target addresses. 
   
   
       4 . The information processing system of  claim 1 , wherein the memory comprises a Random Access Memory. 
   
   
       5 . The information processing system of  claim 1 , wherein the logic for reading comprises:
 logic for reading the first memory and identifying the repeated pattern in the plurality of target addresses for the multi-target branch by:   reading a most recent target address from the plurality of target addresses;   searching the plurality of target addresses for a next most recent target address matching the most recent target address; and   identifying the target address that occurred immediately after the next most recent target address matching the most recent target address.   
   
   
       6 . The information processing system of  claim 5 , wherein the logic for predicting comprises:
 logic for predicting the next target address for the multi-target branch by accepting the target address that was identified as the next target address.   
   
   
       7 . The information processing system of  claim 1 , wherein the logic for reading and the logic for predicting comprise computer program logic residing on a microprocessor. 
   
   
       8 . The information processing system of  claim 1 , wherein the second memory comprises: a single bit vector wherein each bit represents whether a separate branch is a multi-target branch. 
   
   
       9 . The information processing system of  claim 1  wherein the second memory comprises multi-bit counters. 
   
   
       10 . The information processing system of  claim 1 , wherein the multi-target branch is an indirect multi-target branch. 
   
   
       11 . The information processing system of  claim 1 , wherein each entry includes a first-in-first-out queue for storing the plurality of target addresses. 
   
   
       12 . A computer readable storage medium comprising program code that, when executed, causes a computer to:
 store a plurality of entries for each multi-target branch in a first memory as part of a branch path prediction, wherein each entry of the plurality of entries includes a plurality of target addresses representing a history of target addresses for each corresponding single branch in the multi-target branch, and wherein only multi-target branch entries are stored in the first memory;   store a table comprising information used to distinguish whether a selected branch is a multi-target branch in a second memory, and wherein said table is indexed with a branch program counter for the selected branch;   read the first memory;   identify a repeated pattern in each of the plurality of target addresses for each of the multi-target branches; and   predict a next target address for the multi-target branch based on the repeated pattern that was identified, using a pattern matching algorithm.   
   
   
       13 . The computer readable storage medium of  claim 12 , wherein the program code further causing the computer to store a first-in-first-out queue for the plurality of target addresses in the first memory. 
   
   
       14 . The computer readable storage medium of  claim 12 , wherein the program code further causes the computer to: store the plurality of entries in a memory comprising a Random Access Memory, wherein each entry includes the plurality of target addresses representing a history of target addresses for the multi-target branch.