Static branch frequency and program profile analysis

ABSTRACT

Program profiles identify frequently executed portions of a program, which are the places at which optimizations offer programmers and compilers the greatest benefit. Compilers, however, infrequently exploit program profiles, because profiling a program requires a programmer to instrument and run the program. An attractive alternative is for the compiler to statically estimate program profiles. This paper presents several new techniques for static branch prediction and profiling. The first technique combines multiple predictions of a branch's outcome into a prediction of the probability that the branch is taken. Another technique uses these predictions to estimate the relative execution frequency (i.e., profile) of basic blocks and control-flow edges within a procedure. A third algorithm uses local frequency estimates to predict the global frequency of calls, procedure invocations, and basic block and control-flow edge executions. Experiments on the SPEC92 integer benchmarks and Unix applications show that the frequently executed blocks, edges, and functions identified by our techniques closely match those in a dynamic profile.

REFERENCES

• Ball-92: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• Ball-93: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• Chang-91: Pohua P. Chang , Scott A. Mahlke , Wen-mei W. Hwu, Using profile information to assist classic code optimizations, Software—Practice & Experience, v.21 n.12, p.1301-1321, Dec. 1991 [doi>10.1002/spe.4380211204]
• Chen-92: William Y. Chen , Roger A. Bringmann , Scott A. Mahlke , Sadun Anik , Tokuzo Kiyohara , Nancy J. Warter , Daniel M. Lavery , Wen-mei W. Hwu , Richard E. Hank , John C. Gyllenhaal, Using Profile Information to Assist Advaced Compiler Optimization and Scheduling, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.31-48, August 03-05, 1992
• Fisher-81: Fisher, Joseph A, "Trace Scheduling' A Technique for Global Microcode Compaction." IEEE Trans. Computera, C-30, 7 (July, 1981) pp. 478-490.
• Fisher-92: Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.85-95, October 12-15, 1992, Boston, Massachusetts, United States
• Forman-81: Ira R. Forman, On the time overhead of counters and traversal markers, Proceedings of the 5th international conference on Software engineering, p.164-169, March 09-12, 1981, San Diego, California, United States
• Graham-83: Graham, S.L, P.B. Kessler, and M.K. McKusick, "An Execution Profiler for Modular Programs," Software-Practice and Experience, 13 (1983) pp. 671-685.
• Hall-92: Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992 [doi>10.1145/151640.151643]
• Hank-93: Richard E. Hank , Scott A. Mahlke , Roger A. Bringmann , John C. Gyllenhaal , Wen-mei W. Hwu, Superblock formation using static program analysis, Proceedings of the 26th annual international symposium on Microarchitecture, p.247-255, December 01-03, 1993, Austin, Texas, United States
• Hicky-88: Timothy Hickey , Jacques Cohen, Automating program analysis, Journal of the ACM (JACM), v.35 n.1, p.185-220, Jan. 1988 [doi>10.1145/42267.42275]
• Huelsbergen-94: Lorenz Huelsbergen , James R. Larus , Alexander Aiken, Using the run-time sizes of data structures to guide parallel-thread creation, Proceedings of the 1994 ACM conference on LISP and functional programming, p.79-90, June 27-29, 1994, Orlando, Florida, United States
• Hwu-89: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• McFarling-89: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• Pettis-90: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• Ramamoorthy-65: C. V. Ramamoorthy, Analysis of computational systems: Discrete Markov analysis of computer programs, Proceedings of the 1965 20th national conference, p.386-392, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806061]
• Sarkar-89: V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States
• Shafer-76: Shafer, G., A Mathematwal Theory of Evidence. Princeton University Press, 1976.
• Spec92: SPEC Cint92, Release V 1.1
• Wagner-94: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States
• Wall-91: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada
• Wu-92: Youfeng Wu, Ordering functions for improving memory reference locality in a shared memory multiprocessor system, Proceedings of the 25th annual international symposium on Microarchitecture, p.218-221, December 01-04, 1992, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory