Branch prediction for free

Many compilers rely on branch prediction to improve program performance by identifying frequently executed regions and by aiding in scheduling instructions. Profle-based predictors require a time-consuming and inconvenient compile-profile-compile cycle in order to make prdlctions. We present a program-based branch predictor that performs welt for a large and diverse set of programs written in C and Fortran. In addition to using natural loop analysis to predict branches that control the iteration of loops, we focus on heuristics for predicting non-loop Lmstches, which dominate the dynamic branch count of many programs. The heuristics are sim-ple and require little program analysis, yet they are effective in terms of coverage and miss rate. Although program-based predic-tion does not equal the accuracy of profile-based Prdlction, we believe it reaches a sufficiently high level to be useful. Additional type and semantic information available to a compiler would enhance our heuristics. 1