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 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.
- BallLarus92.Thomas Ball and James R. Lares. Optimally Profiling and Tracing Programs. Proceedings of the 19th Annual Symposium on Princlples of Programrmng Languages, January 1992, pages 59-70. Google ScholarDigital Library
- BallLarus93.Thomas Ball and James R. Larus. Branch Prediction For Free. Proceedings of the SIGPLAN '93 Conference on Programrmng Language Design and Implementatson, June 1993, pages 300-313. Google ScholarDigital Library
- Banerjee88.Utpal Banerjee. Dependence Analysis for Supercomputing. Kluwer Academic Publishers, 1988. Google ScholarDigital Library
- BernsteinRodeh91.David Bernstein and Michael Rodeh. Global Instruction Scheduling for Superscalar Machines. Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, June 1991, pages 241-255. Google ScholarDigital Library
- Callahan+86.David Callahan, Keith D. Cooper, Ken Kennedy and Linda Torczon. lnterprocedural Constant Propagation. Proceedings of the SIGPLAN '86 Conference on Compiler Construction, June 1986, pages 152-161. Google ScholarDigital Library
- ChangMahlkeHwu91.Pohua P. Chang, Scott A. Mahlke and Wen-Mei W. Hwu. Using Profile Information to Assist Classic Code Optimizations. Software Practice and Experience 21(12), December 1991, pages 1301-1321. Google ScholarDigital Library
- CooperHallKennedy92.Keith D. Cooper, Mary W. Hall and Ken Kennedy. Procedure Cloning. IEEE 1992 International Conference on Computer Languages, April 1992, pages 96-105.Google ScholarCross Ref
- Cytron+91.Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman and F. Kenneth Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM Transactions on Programming Languages and Systems 13(4), October 1991, pages 451-490. Google ScholarDigital Library
- Ellis85.John R. Ellis. Bulldog: A Compiler for VL1W Architectures. PhD Thesis, Yale University, February 1985. Also available from MIT Press, 1986.Google Scholar
- Fisher81.Joseph A. Fisher. Trace Scheduhng: A Technique for Global Mtcrocode Compaction. IEEE Transactions on Computers 30(7), July 1981, pages 478-490.Google ScholarDigital Library
- FisherFreudenberger92.Joseph A. Fisher and Stefan M. Freudenberger. Predicting Conditional Branch Dtrecttons From Previous Runs of a Program. Proceedings of the 5th International Conference on Architectural Support for Programnung Languages and Operating Systems, October 1992, pages 85-95. Google ScholarDigital Library
- GroveTorczon93.Dan Grove and Llnda Torczon. Interprocedural Constant Propagation: A Study of Jump Function Implementations. Proceedings of the SiGPLAN '93 Conference on Programming Language Design and Implementation, June 1993, pages 90-99. Google ScholarDigital Library
- Gupta93.Rajlv Gupta. Optimizing Array Bound Checks Usmg Flow Analysis. ACM Letters on Programming Languages and Systems 2(1-4), March-December 1993, pages 135- I50. Google ScholarDigital Library
- Harrison77.Wfiham H. Hamson. Compiler Analysts of the Value Ranges for Variables. IEEE Transactions on Software Engineering 3(3), May 1977, pages 243-250.Google Scholar
- JohnsonPingali93.Richard Johnson and Kershav Pingali. Dependence-Based Program Analysis. Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, June 1993, pages 78-89. Google ScholarDigital Library
- Karr84.Michael Karr. Code Generation by Coagulation. Proceedings of the SIGPLAN '84 Symposium on Compiler Constructaon, June 1984, pages 1-12. Google ScholarDigital Library
- Kildall73.G. A. Kildall. A Unified Approach to Global Program Optimization. Proceedings of the First Annum Symposium on Principles of Programnung Languages, October 1973, pages 194-206. Google ScholarDigital Library
- Krall94.Andreas Krall. Improving Semi-Static Branch Predtctton by Code Replication. Proceedings of the SIGPLAN '94 Conference on Programnung Language Design and Implementation, June 1994, pages 97-106. Google ScholarDigital Library
- McFarling89.Scott McFarling. Program Optimization for Instruction Caches. Proceedings of the 3rd International Symposium on ArchltecturaI Support for Programming Languages and Operating Systems, April 1989, pages 183-191. Google ScholarDigital Library
- McFarlingHennessy86.Scott McFarling and John L. Hennessy. Reducing the Cost of Branches. Proceedings of the 13th Annual Symposium on Computer Architecture, June 1986, pages 396-403. Google ScholarDigital Library
- MetzgerStroud93.Robert Metzger and Scan Stroud. Interprocedural Constant Propagation: An Empirical Study. ACM Letters on Programming Languages and Systems 2(1-4), March-December 1993, pages 213- 232. Google ScholarDigital Library
- Morris91.W. G. Morris. CCG: A Prototype Coagulating Code Generator. Proceedings of the SIGPLAN '91 Conference on Programming Language Design and implementation, June 1991, pages 45-58. Google ScholarDigital Library
- PettisHansen90.Karl Pettis and Robert C. Hansen. Profile Guided Code Positioning. Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, June 1990, pages 16-27. Google ScholarDigital Library
- ReifLewis77.John H. Reif and Harry R. Lewis. Symbolic Evaluation and the Global Value Graph. Proceedings of the 4th Annual Symposium on Pnnciples of Programrmng Languages, January 1977, pages 104-I 18. Google ScholarDigital Library
- Smith81.James E. Srmth. A Study of Branch Prediction Strategies. Proceethngs of the 8th Annual Symposmm on Computer Architecture, May 1981, pages 135-148. Google ScholarDigital Library
- SteenkisteHennessy89.Peter A. Steenkiste and John L. Hennessy. A Simple Interprocedural Register Allocation Algorithm and Its Effectiveness for LISP. ACM Transacuons on Programming Languages and Systems 11 (1), January 1989, pages 1-32. Google ScholarDigital Library
- Wagner+94.Tim A. Wagner, Vance Maverick, Susan L. Graham and Michael A. Harrison. Accurate Static Esttmators for Program Optimtzatton. Proceedings of the SiGPLAN '94 Conference on Programming Language Design and Implementation, June 1994, pages 85-96. Google ScholarDigital Library
- Wall86.David W. Wall. Global Register Allocation at Link Time. Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, June 1986, pages 264-275. Google ScholarDigital Library
- Wall88.David W. Wall. Regtster Windows vs Register Allocatton. Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementatton, June 1988, pages 67-78. Google ScholarDigital Library
- Wall91.David W, Wall. Predicting Program Behavior Using Real or Estimated Profiles. Proceedings of the SIGPLAN '91 Conference on Progranumng Language Design and Implementation, June 1991, pages 59-70. Google ScholarDigital Library
- WegmanZadeck91.Mark N. Wegman and F. Kenneth Zadeck. Constant Propagatwn with Conditional Branches. ACM Transactions on Programming Languages and Systems 13(2), April 1991, pages 181-210. Google ScholarDigital Library
- WuLarus94.Youfeng Wu and James R. Larus. Static Branch Frequency and Program Profile Analysis. Proceedings of the 27th International Symposium on Microarchitecture, November 1994, pages i-11. Google ScholarDigital Library
Index Terms
- Accurate static branch prediction by value range propagation
Recommendations
Accurate static branch prediction by value range propagation
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 ...
Static correlated branch prediction
Recent work in history-based branch prediction uses novel hardware structures to capture branch correlation and increase branch prediction accuracy. Branch correlation occurs when the outcome of a conditional branch can be accurately predicted by ...
Comments