The need for accurate conditional-branch prediction is well known; mispredictions waste large numbers of cycles and also waste power on mis-speculated computation. A number of studies have explored ways to improve the prediction accuracy of two-level predictors, but have considered exclusively global or local history. Because most programs benefit from having both global and local history available, other work has proposed hybrid predictors that combine a global-history with a local-history component.

Building on prior work that categorizes the types of branch mispredictions, this paper presents a taxonomy of mispredictions. Using the taxonomy, the paper shows why a two-level predictor that alloys local and global history in the same predictor index provides superior performance. By making both types of history available all the time, an alloyed scheme obtains accuracies competitive with hybrid schemes, even though organized like conventional two-level predictors. Alloying has the advantage that it eliminates the need to make a choice between components, since the history types are merged. For large predictors used in high-performance processors, an alloyed organization provides competitive performance that suffers less variation from program to program than alternatives. For the smaller predictors needed in space- and power-constrained environments, alloying outperforms alternative organizations.