An analysis of hard to predict branches

Branch prediction accuracy remains to be critical for high performance and low power. Prior work has studied causes of branch mispredictions in order to provide insights into how better branch predictors can be designed. However, most of the previous works have only considered run-time classification of branch mispredictions, leaving a large number of mispredictions in an unknown category. For more comprehensive analysis, in this paper, we present a detailed source code analysis of branch mispredictions for SPEC CPU 2000 and Mibench benchmarks. Our analysis show that constant loop exits, insufficient history lengths, wrong-type history, array access/pointer references, complex linked list data structures, changing function inputs, and varying loop counts are the major causes for most of the branch mispredictions. We further show that most mispredictions have repetitive patterns that suggest different design strategies for future branch predictors.