Whole program paths

ABSTRACT

Whole program paths (WPP) are a new approach to capturing and representing a program's dynamic---actually executed---control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact description of a program's entire control flow, including loop iteration and interprocedural paths.This paper explains how to collect and represent WPPs. It also shows how to use WPPs to find hot subpaths, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization.

REFERENCES

• 1: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 2: 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
• 3: Sten Andler, Predicate path expressions, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.226-236, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567774]
• 4: Brenda S. Baker, Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance, SIAM Journal on Computing, v.26 n.5, p.1343-1362, Oct. 1997 [doi>10.1137/S0097539793246707]
• 5: V. Bala, "Low Overhead Path Profiling," Hewlett Packard Labs 1996.
• 6: 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
• 7: 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]
• 8: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Refining data flow information using infeasible paths, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.361-377, September 22-25, 1997, Zurich, Switzerland
• 9: I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.128-137, October 01-04, 1996, Cambridge, Massachusetts, United States
• 10: E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.2, p.244-263, April 1986 [doi>10.1145/5397.5399]
• 11: J. A. Fisher, "Trace Scheduling: A Technique for Global Microeode Compaction," IEEE Transactions on Computers, vol. C-30, pp. 478-490, 1981.
• 12: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 13: J. Gray, "The Benchmark Handbook for Database and Transaction Processing Systems," in The Morgan Kaufmann Series in Data Management Systems, J. Gray, Ed., second ed. San Francisco: Morgan Kaufmann, 1993.
• 14: 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
• 15: Quinn Jacobson , Eric Rotenberg , James E. Smith, Path-based next trace prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: J. R. Larus, Abstract execution: a technique for efficiently tracing programs, Software—Practice & Experience, v.20 n.12, p.1241-1258, Dec. 1990 [doi>10.1002/spe.4380201205]
• 17: James R. Larus , Eric Schnarr, EEL: machine-independent executable editing, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.291-300, June 18-21, 1995, La Jolla, California, United States
• 18: D. Melski and T. Reps, "Interprocedural Path Profiling," Computer Sciences Department, University of Wisconsin- Madison, Technical Report TR- 1382, September 1998.
• 19: 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
• 20: David Mosberger , Larry L. Peterson, Making paths explicit in the Scout operating system, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.153-167, October 29-November 01, 1996, Seattle, Washington, United States
• 21: C. G. Nevill-Manning and I. H. Witten, "Compression and explanation using hierarchical grammars," The Computer Journal, vol. 40, pp. 103-116, 1997.
• 22: Craig G. Nevill-Manning , Ian H. Witten, Linear-Time, Incremental Hierarchy Inference for Compression, Proceedings of the Conference on Data Compression, p.3, March 25-27, 1997
• 23: Andrew R. Pleszkun, Techniques for compressing program address traces, Proceedings of the 27th annual international symposium on Microarchitecture, p.32-39, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192728]
• 24: C. Pu , T. Autrey , A. Black , C. Consel , C. Cowan , J. Inouye , L. Kethana , J. Walpole , K. Zhang, Optimistic incremental specialization: streamlining a commercial operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.314-321, December 03-06, 1995, Copper Mountain, Colorado, United States
• 25: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• 26: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 27: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 28: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory

Keywords:
data compression, dynamic program measurement, path profiling, program control flow, program tracing