Improving Indirect Branch Prediction With Source- and Arity-basedClassification and Cascaded Prediction

Indirect branch prediction is likely to become more critical to programperformance because indirect branches occur more frequently in object-orientedprograms. We study indirect branch behavior in both procedural andobject-oriented programs in order to build more accurate predictorarchitectures. First we use a statically classifying hybrid predictor with ashared history table and separate history buffers tuned for different branchclasses. Opcode-based classification, which classifies branches according totheir source code origin, leads to only minor improvements in predictionperformance. Arity-based classification, which classifies branches accordingto the number of different targets, obtains better performance, competitivewith recently proposed dual- path length hybrid predictors. Finally, wepresent cascaded branch predictors, which dynamically classifies easilypredicted branches using an inexpensive predictor. By preventing insertion ofthese branches into a more powerful second stage predictor, cascaded predictionobtains prediction rates equivalent to that of the previously best knownindirect branch predictors, but at roughly half the cost. Specifically, acascaded predictor with a total of 288 history table entries achieves 89.3%prediction accuracy.