Accurate Static Branch Prediction
by Value Range Propagation

Abstract

The ability to predict at compile time the likelihood of a particular branch being taken provides valuable information for several optimizations, including global instruction scheduling, code layout, function inlining, interprocedural register allocation and many high level optimizations. Previous attempts at static branch prediction have either used simple heuristics, which can be quite inaccurate, or put the burden onto the programmer by using execution profiling data or source code hints.

This paper presents a new approach to static branch prediction called value range propagation. This method tracks the weighted value ranges of variables through a program, much like constant propagation. These value ranges may be either numeric or symbolic in nature. Branch prediction is then performed by simply consulting the value range of the appropriate variable. Heuristics are used as a fallback for cases where the value range of the variable cannot be determined statically. In the process, value range propagation subsumes both constant propagation and copy propagation.

Experimental results indicate that this approach produces significantly more accurate predictions than the best existing heuristic techniques. The value range propagation method can be implemented over any "factored" dataflow representation with a static single assignment property (such as SSA form or a dependence flow graph where the variables have been renamed to achieve single assignment). Experimental results indicate that the technique maintains the linear runtime behavior of constant propagation experienced in practice.

Slides

Key Citations (Selected)

[Muchnick1997]

Steven S. Muchnick. Advanced Compiler Design & Implementation. Morgan Kaufmann, 1997.

[BodikGuptaSarkar2000]

Rastislav Bodik, Rajiv Gupta and Vivek Sarkar. ABCD: Eliminating Array Bounds Checks on Demand. Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI), May 2000, pages 321-333.

[WagnerFosterBrewerAiken2000]

David Wagner, Jeffrey S. Foster, Eric A. Brewer and Alexander Aiken. A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. Proceedings of the Network and Distributed System Security Symposium, 2000, pages 3-17.

[RuginaRinard2005]

Radu Rugina and Martin C. Rinard. Symbolic Bounds Analysis of Pointers, Array Indices, and Accessed Memory Regions. ACM Transactions on Programming Languages and Systems (TOPLAS) 27(2), Mar 2005, pages 185-235.

For a more complete list of citations, see the paper's entries in Google Scholar, CiteSeer and the ACM Digital Library. At last check, a total of about 150 papers cited this paper, plus several textbooks.

Notes

The value range propagation (VRP) algorithm is in widespread use today and has been implemented in many production and research compilers, both for static branch prediction and for other value/type propagation optimizations and analyses, often collectively called "static analysis" today. Therefore, it's safe to say the paper's description of the VRP algorithm is clearly sufficient for most purposes. However, if you do have any questions regarding implementation, please feel free to email jason@lighterra.com.