Accurate static estimators for program optimization

Abstract

Determining the relative execution frequency of program regions is essential for many important optimization techniques, including register allocation, function inlining, and instruction scheduling. Estimates derived from profiling with sample inputs are generally regarded as the most accurate source of this information; static (compile-time) estimates are considered to be distinctly inferior. If static estimates were shown to be competitive, however, their convenience would outweigh minor gains from profiling, and they would provide a sound basis for optimization when profiling is impossible.

We use quantitative metrics to compare estimates from static analysis to those derived from profiles. For C programs, simple techniques for predicting branches and loop counts suffice to estimate intraprocedural frequency patterns with high accuracy. To determine inter-procedural estimates successfully, we combine function-level information with a Markov model of control flow over the call graph to produce arc and basic block frequency estimates for the entire program.

For a suite of 14 programs, including the C programs from the SPEC92 benchmark suite, we demonstrate that static estimates are competitive with those derived from profiles. Using simple heuristics, we can determine the most frequently executed blocks in each function with 81% accuracy. With the Markov model, we identify 80% of the frequently called functions. Combining the two techniques, we identify 76% of the most frequently executed call sites.

References

1. 1 Thomas Ball and James R. Larus. Branch prediction for free. Proceedings of the A CM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 300-313, 1993.
2. 2 David A. Barrett and Benjamin G. Zorn. Using lifetime predictors to improve memory allocation performance. In Proceedings of the A CM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 187-196, Albuquerque, New Mexico, 1993.
3. 3 Preston Briggs and Keith D. Cooper. Effective partial redundancy elimination. Proceedings of the A CM SIGPLAN '96 Conference on Programming Language Design and Implementation, 1994.
4. 4 David Callahan and Brian Koblenz. l~egister allocation via hierarchical graph coloring. Proceedings of the A CM SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 192-202, 1991.
5. 5 Pohua P. Chang, Scott A. Mahlke, William Y. Chen, and Wen-mei W. Itwu. Profile-guided automatic inline expansion for C programs. Software--Practice and Experience, 22(5):349-369, May 1992.
6. 6 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):1301-1321, December 1991.
7. 7 Joseph A. Fisher and Stefan M. Freudenberger. Predicting conditional branch directions from previous runs of a program. Fifth International Conference on Architectural Support for Programming Languages and Operatzng Systems, pages 85-95, 1992.
8. 8 Scott McFarling. Program optimization for instruction caches. Second International Conference on Architectural Support for Programming Languages and Operating Systems, pages 183-191, 1989.
9. 9 C. V. Ramamoorthy. Discrete Markov analysis of computer programs. In A CM 20th National Conference, pages 386-391, Cleveland, Ohio, 1965.
10. 10 Vasta Santhanam and Daryl Odnert. Register allocation across procedure and module boundaries. Proceedings of the A CM SfGPLAN '91 Conference on Programming Language Design and Implementation, pages 28-39, 1991
11. 11 Vivek Sarkar. Determining average program execution times and their variance. In Proceedings of the ACM $IGPLAN '89 Conference on Programming Language Design and Implementation, pages 298-312, Portland, Oregon, 1989.
12. 12 David W. Wall. Predicting program behavior using real or estimated profiles. Proceedings o/ the A CM SIG- PLAN '91 Conference on Programming Language Design and Implementation, pages 59-70, 1991.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

        • Control structures

      • Language types

• Theory of computation

  • Randomness, geometry and discrete structures