Limits of Indirect Branch Prediction

Indirect branch prediction is likely to become more important in the futurebecause indi rect branches tend to be more frequent in object-orientedprograms. With indirect branch prediction misprediction rates of around 25% oncurrent processors, such branches can incur a significant fraction of branchmisses even though indirect branches are less frequent than the morepredictable conditional branches. We investigate the predictability ofindirect branches to determine whether the inferior accuracy of the currentindirect branch prediction mechanism (branch target buffers) results from anintrinsic unpredictability of indirect branches or is caused by suboptimalbranch prediction hardware. Using programs from the SPECint95 suite as well asa suite of C++ applications, we show that prediction accuracy can exceed 95% onaverage for these benchmarks, assuming an unlimited hardware budget. Thisresult suggests that better indirect branch prediction hard ware cansignificantly outperform current branch target buffers.