Re: static estimation of conditional branches?

Scott Mahlke <mahlke@crhc.uiuc.edu> writes:
>I was wondering if anyone is aware of any studies performed to staticly
>estimate the direction of non-loop back conditional branches in C programs.


James Larus and I have nearly completed a paper on statically predicting
branches. We have developed a variety of heuristics for predicting
non-loop branches and measured their effectiveness on a wide variety of
programs. For many programs, most of the dynamic branches are non-loop
branches and it is important to predict these branches accurately to
obtain good overall branch prediction.


Our heuristics are simple, but have quite good performance. As one
example, consider a branch that guards a return. The common case for such
branches is to avoid the return (think of recursion and also error
conditions). In the SPEC benchmark gcc, this heuristic applied to 10% of
the dynamic non-loop branches and correctly predicted 70% of these
branches. In the benchmark xlisp, the heuristic covered 35% of the
branches with 80% correctness. Over the 23 programs we measured this
heuristic had an average of 75% correctness +- 15%.


While it is always possible to defeat a heuristic, programs are usually
written to solve problems rather than to defeat branch prediction
heuristics. Our study shows that programs are often written in such a way
that a set of simple heuristics can be used to effectively predict
non-loop branches. We also use loop analysis to accurately predict
branches that control the iteration of loops. While the accuracy of
program-based prediction cannot approach that of profile-based prediction,
we believe program-based prediction reaches a sufficiently good level to
be of practical use.


We expect to be finished with a full version of the paper in a few weeks,
at which time we will make it available via ftp and post an announcement
here.


-- Tom


Thomas Ball Computer Sciences Dept.
tom@cs.wisc.edu University of Wisconsin-Madison
--

Return to the comp.compilers page.
Search the comp.compilers archives again.