Predicting conditional branch directions from previous runs of a program

Abstract

There are several important reasons for predicting which way the flow of control of a program is going to go tirst, in instmctionIevel parallel architectures, code motions can produce more dataready candidate instructions at once than there are resources to execute them. Some of these are speculative (executed ahead of a conditional branch that might otherwise have prevented their execution), so one must sensibly pick among them, and one must avoid issuing low probability speculative instructions when the system overhead associated with canceling them most of the time outweighs the gain of their infrequent succes~ second, important classes of compiler optimization depend upon this information, and finally, branch prediction can help optimize pipelined fetch and execute, icache fill, etc. If substantial code motions are desired, it is probably impractical to expect the hardware to make them, and a compiler must instead. Thus, the compiler must have access to branch predictions made before the program runs. In this paper we consider the question of how predictable branches are when previous runs of a program are used to feed back information to the compiler. We propose new measures which we believe more clearly capture the predictability of branches in programs. We fmd that even code with a complex flow of control, including systems utilities and language processors written in C, are dominated by branches which go in one way, and that this direction usually varies little when one changes the data used as the predictor and target.