Improving data-flow analysis with path profiles

ABSTRACT

Data-flow analysis computes its solutions over the paths in a control-flow graph. These paths---whether feasible or infeasible, heavily or rarely executed---contribute equally to a solution. However, programs execute only a small fraction of their potential paths and, moreover, programs' execution time and cost is concentrated in a far smaller subset of hot paths.This paper describes a new approach to analyzing and optimizing programs, which improves the precision of data flow analysis along hot paths. Our technique identifies and duplicates hot paths, creating a hot path graph in which these paths are isolated. After flow analysis, the graph is reduced to eliminate unnecessary duplicates of unprofitable paths. In experiments on SPEC95 benchmarks, path qualification identified 2--112 times more non-local constants (weighted dynamically) than the Wegman-Zadek conditional constant algorithm, which translated into 1--7% more dynamic instructions with constant results.

REFERENCES

• ABL97: 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
• Aho94: Alfred V. Aho, Algorithms for finding patterns in strings, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• BA98: Rastisalv Bodík , Sadun Anik, Path-sensitive value-flow analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.237-251, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268966]
• BGS97a: 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
• BGS97b: 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
• BGS98: 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
• BL96: 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
• Fis81: Joseph A. Fisher. Trace scheduIing: A technique for global mlcrocode compaction. IEEE Transactions on Computers, C-30(7):478-490, July 1981.
• Gri73: David Gries. Describing an algorithm by hopcroft. Acts Informatica, 2:97-109, 1973.
• GWZ94: Allen Goldberg , T. C. Wang , David Zimmerman, Applications of feasible path analysis to program testing, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.80-94, August 17-19, 1994, Seattle, Washington, United States [doi>10.1145/186258.186523]
• HR81: L. Howard Holley and Barry K. Rosen. Qualified data flow probIems. IEEE 7~ansactions on Software Engineering, SE-7(1):60-78, January 1981.
• MW95: Frank Mueller , David B. Whalley, Avoiding conditional branches by code replication, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.56-66, June 18-21, 1995, La Jolla, California, United States
• mWHMC+93: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• Ram96: 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
• WFW+: Robert P. Wilson, Robert S. French, Christopher S. Wilson, Saman P. Amarasinghe, Jennifer M. Anderson, Steve W. K. Tjiang, Shih-Wei Liao, Chau- Wen Tseng, Mary W. Hall, Monica S. Lain, and John L. Hennessy. An overview of the SUIF compiler system. Published on the World Wide Web at http://sulf, stanford.edu/suif/suifl/suif-overview/sulf, html.
• WZ91: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Experimentation, Performance