Extending Path Profiling across Loop Backedges and Procedure Boundaries

ABSTRACT

Since their introduction, path profiles have been used toguide the application of aggressive code optimizations andperforming instruction scheduling. However, for optimizationand scheduling, it is often desirable to obtain frequencycounts of paths that extend across loop iterations and crossprocedure boundaries. These longer paths, referred to asinteresting paths in this paper, account for over 75% of theflow in a subset of SPEC benchmarks. Although the frequencycounts of interesting paths can be estimated frompath profiles, the degree of imprecision of these estimates isvery high. We extend Ball Larus (BL) paths to create slightlylonger overlapping paths and develop an instrumentationalgorithm to collect their frequencies. While these pathsare slightly longer than BL paths, they enable very preciseestimation of frequencies of potentially much longer interestingpaths. Our experiments show that the average cost ofcollecting frequencies of overlapping paths is 86.8% whichis 4.2 times that of BL paths. However, while the averageimprecision in estimated total flow of interesting paths derivedfrom BL path frequencies ranges from -38 % to +138%, the average imprecision in flow estimates derived fromoverlapping path frequencies ranges only from -4% to +8%.

REFERENCES

• 1: Glenn Ammons , James R. Larus, Improving data-flow analysis with path profiles, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.72-84, June 17-19, 1998, Montreal, Quebec, Canada
• 2: Taweesup Apiwattanapong , Mary Jean Harrold, Selective path profiling, Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, November 18-19, 2002, Charleston, South Carolina, USA
• 3: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 4: Thomas Ball , Peter Mataga , Mooly Sagiv, Edge profiling versus path profiling: the showdown, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.134-148, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268958]
• 5: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Interprocedural conditional branch elimination, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.146-158, June 16-18, 1997, Las Vegas, Nevada, United States
• 6: Rastislav Bodík , Rajiv Gupta, Partial dead code elimination using slicing transformations, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.159-170, June 16-18, 1997, Las Vegas, Nevada, United States
• 7: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Complete removal of redundant expressions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.1-14, June 17-19, 1998, Montreal, Quebec, Canada
• 8: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Load-reuse analysis: design and evaluation, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.64-76, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.202-211, November 2000, Cambridge, Massachusetts, United States
• 11: [11] J. A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, C- 30:478-490, 1981.
• 12: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Resource-sensitive profile-directed data flow analysis for code optimization, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.358-368, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 13: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Path Profile Guided Partial Dead Code Elimination Using Predication, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.102, November 11-15, 1997
• 14: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Path Profile Guided Partial Redundancy Elimination Using Speculation, Proceedings of the 1998 International Conference on Computer Languages, p.230, May 14-16, 1998
• 15: Rahul Joshi , Michael D. Bond , Craig Zilles, Targeted Path Profiling: Lower Overhead Path Profiling for Staged Dynamic Optimization Systems, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.239, March 20-24, 2004, Palo Alto, California
• 16: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 17: David Melski , Thomas W. Reps, Interprocedural Path Profiling, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.47-62, March 22-28, 1999
• 18: G. Ramalingam, Data flow frequency analysis, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.267-277, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 19: [19] The Trimaran Compiler Research Infrastructure. Tutorial Notes, November 1997.
• 20: Cliff Young , Michael D. Smith, Better global scheduling using path profiles, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.115-123, November 1998, Dallas, Texas, United States
• 21: Cliff Young , Michael D. Smith, Improving the accuracy of static branch prediction using branch correlation, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.232-241, October 05-07, 1994, San Jose, California, United States
• 22: Youtao Zhang , Rajiv Gupta, Timestamped whole program path representation and its applications, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.180-190, June 2001, Snowbird, Utah, 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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Design, Performance

Keywords:
path profiles, overlapping path profiles, profileguided optimization, and instruction scheduling