Decision Trees for Improving Heuristic-Based Static Branch Prediction

Abstract—Static branch prediction determines the most frequent direction of control flow in programs, e.g. predicting whetherif orelse 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 lacking a dynamic branch predictor. This paper builds on previous work done on evidence-based static branch prediction which uses decision trees to classify branches [1]. We demonstrate how decision trees can be used to improve the Ball and Larus heuristics [2] 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 an