An ILP (Instruction-Level Parallelism) compiler uses aggressive optimizations
to reduce a program's running time. These optimizations have been shown
to be effective when profile information is available. Unfortunately,
users are not always willing or able to profile their programs. A method of
overcoming this issue is for an ILP compiler to statically infer the
information normally obtained from profiling. This paper investigates one
aspect of this inference: the static prediction of conditional-branch
direction. The goals of this work are to utilize the source-level information
available in a compiler when performing static branch prediction,
to identify static-branch-prediction cases in which there is a
high confidence that a branch will go in one direction at run time, to gain an
intuitive understanding into the reasons why the static-branch-prediction
heuristics are effective, and ultimately to improve the accuracy of the
static branch prediction.
The effectiveness of the static-branch-prediction heuristics developed in
this paper is demonstrated on a set of programs from SPEC CINT92, SPEC CINT95,
and the IMPACT compiler.