Static branch prediction determines the most frequent direction of control flow
in programs, e.g. predicting whether if or else will be chosen most of the time.
Improving static branch prediction is an important problem with various interesting applications ranging from compiler optimizations, to improving dynamic branch predictors, to improving performance of embedded microprocessors.
This paper builds on previous work done on evidence-based static branch prediction which uses decision trees to classify branches. We demonstrate how decision trees can be used to improve the Ball and Larus heuristics by optimizing the sequence of applying the heuristics and by adding two new heuristics, namely one based on the postdomination relationship between the current basic block and its successor and one based on the dependency distance between the branch and its operand defining instruction. Experimental results indicate an increase in the number of instructions per mispredicted branch by 18.5% for SPECint95 and SPECint2000.