Brad Calder et al. in their paper on Evidence Based Static Branch Prediction describe two machine learning systems that use the data collected about the branches in a known set of programs to make decisions on the branches seen in a new set of programs. They experimented with both Neural Networks and Decision Trees.
Branch prediction is the method for determining at compile time whether the branches will be taken or not before they are actually executed. Branch prediction can be very useful in certain compiler optimizations where predicting whether a particular branch is taken or not may lead to considerable differences in the size of code produced.
Compilers usually depend on mainly two kinds of branch prediction - program-based and profile-based branch prediction. The main disadvantage of using profile-based methods is that more work is required on the part of the programmer to provide program profiles. Whereas program-based branch prediction methods are used to make predictions mainly based on the program's structure. Some of the program-based methods use heuristics based on local information which can be encoded in the architecture and some apply heuristics based on less local program structure.
This article describes a new approach to program-based branch prediction which does not use any such heuristics. This general program based prediction method is called ESP. Instead of using a different execution of a program to predict its own behavior (as done in profile-based methods) they use the behavior of a large number of different programs to determine common behavior. This large body of different programs is considered to be the training set and once the common behavior has been identified they try to use this knowledge to predict the behavior of branches in programs that are not part of the training set.
Thus ESP takes place in two stages. The first stage involves profiling the corpus of programs, and is performed only once. Static information about the important static elements (specifically branch instructions and other instructions that precede or follow them) of the corpus is gathered. Then the programs in the corpus are executed and the corresponding dynamic behavior is mapped to each static element. That is the number of times the branch is taken or not taken is recorded for each branch.
The second stage uses the trends gathered in the first to make similar predictions in new programs. The knowledge accumulated about the relationship between the static features of the program and its dynamic behavior can be used to predict the behavior of instructions with similar static features for programs not in the training set. [2]