Accurate static branch prediction by value range propagation
JRC Patterson - Proceedings of the ACM SIGPLAN 1995 conference on …, 1995 - dl.acm.org
JRC Patterson
Proceedings of the ACM SIGPLAN 1995 conference on Programming language …, 1995•dl.acm.orgThe 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 …
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 …
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 of 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 propagationsubsumes 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.