Load-reuse analysis: design and evaluation

ABSTRACT

Load-reuse analysis finds instructions that repeatedly access the same memory location. This location can be promoted to a register, eliminating redundant loads by reusing the results of prior memory accesses. This paper develops a load-reuse analysis and designs a method for evaluating its precision.In designing the analysis, we aspire for completeness---the goal of exposing all reuse that can be harvested by a subsequent program transformation. For register promotion, a suitable transformation is partial redundancy elimination (PRE). To approach the ideal goal of PRE-completeness, the load-reuse analysis is phrased as a data-flow problem on a program representation that is path-sensitive, as it detects reuse even when it originates in a different instruction along each control flow path. Furthermore, the analysis is comprehensive, as it treats scalar, array and pointer-based loads uniformly.In evaluating the analysis, we compare it with an ideal analysis. By observing the run-time stream of memory references, we collect all PRE-exploitable reuse and treat it as the ideal analysis performance. To compare the (static) load-reuse analysis with the (dynamic) ideal reuse, we use an estimator algorithm that computes, given a data-flow solution and a program profile, the dynamic amount of reuse detected by the analysis. We developed a family of estimators that differ in how well they bound the profiling error inherent in the edge profile. By bounding the error, the estimators offer a precise and practical method for determining the run-time optimization benefit.Our experiments show that about 55% of loads executed in Spec95 exhibit reuse. Of those, our analysis exposes about 80%.

REFERENCES

• 1: Ole Agesen , Urs Hölzle, Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.91-107, October 15-19, 1995, Austin, Texas, United States
• 2: 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
• 3: 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]
• 4: Rastislav Bodik , Rajiv Gupta , Mary Lou Soffa, Path-sensitive, value-flow optimizations of programs (program analysis), 1999
• 5: 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]
• 6: Rastislav Bodík , Rajiv Gupta, Array data flow analysis for load-store optimizations in fine-grain architectures, International Journal of Parallel Programming, v.24 n.6, p.481-512, Dec. 1996
• 7: 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
• 8: 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
• 9: 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
• 10: 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
• 11: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.159-170, June 20-24, 1994, Orlando, Florida, United States
• 12: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 13: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 14: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 15: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 16: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, Proceedings of the 18th annual international symposium on Computer architecture, p.266-275, May 27-30, 1991, Toronto, Ontario, Canada
• 17: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 18: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, ACM SIGPLAN Notices, v.33 n.5, p.106-117, May 1998
• 19: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical data flow framework for array reference analysis and its use in optimizations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.68-77, June 21-25, 1993, Albuquerque, New Mexico, United States
• 20: Benjamin Goldberg, Hansoo Kim, Vinod Kathail, and John Gyllenhaal. The trimaran compiler infrastructure for instruction level parallelism research. Technical Report he tp: / / www. trimaran, o rg, Hewlett-Packard Laboratories, University of Illinois, NYU, 1998.
• 21: 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
• 22: 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]
• 23: Vinod Kathail, Michael S. Schlansker, and B. Ramakrishna Rau. Hpl playdoh architecture specification: Version 1.0. Technical Report HPL-93-80, Hewlett-Packard Laboratories, 1994.
• 24: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 25: James Larus and Satish Chandra. Using tracing and dynamic slicing to tune compilers. Technical Report TR-1174, University of Wisconsin, 1993.
• 26: Raymond Lo , Fred Chow , Robert Kennedy , Shin-Ming Liu , Peng Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.26-37, June 17-19, 1998, Montreal, Quebec, Canada
• 27: John Lu , Keith D. Cooper, Register promotion in C programs, ACM SIGPLAN Notices, v.32 n.5, p.308-319, May 1997
• 28: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 29: Frank Mueller , David B. Whalley, Avoiding conditional branches by code replication, ACM SIGPLAN Notices, v.30 n.6, p.56-66, June 1995
• 30: John Plevyak , Andrew A. Chien, Type Directed Cloning for Object-Oriented Programs, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.566-580, August 10-12, 1995
• 31: G. Ramalingam, The undecidability of aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1467-1471, Sept. 1994 [doi>10.1145/186025.186041]
• 32: 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
• 33: Glenn Reinman, Brad Calder, Dean Tullsen, Gary Tyson, and Todd Austin. Profile guided load marking for memory renaming. Technical Report UCSD-CS98-593, University of California, San Diego, 1998.
• 34: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 35: A. V. S. Sastry , Roy D. C. Ju, A new algorithm for scalar register promotion based on SSA form, ACM SIGPLAN Notices, v.33 n.5, p.15-25, May 1998
• 36: Bernhard Steffen, Property-Oriented Expansion, Proceedings of the Third International Symposium on Static Analysis, p.22-41, September 24-26, 1996
• 37: B. Steffen , J. Knoop , O. Rüthing, The value flow graph: a program representation for optimal program transformations, Proceedings of the third European symposium on programming on ESOP '90, p.389-405, May 1990, Copenhagen, Denmark
• 38: Youfeng Wu. Conflict Ratio Profiling for Memory References. Technical Report MRL Compiler Technical Report 96012, Intel Corp., 1996.
• 39: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Algorithms, Experimentation, Languages, Measurement

Keywords:
data-flow analysis, profile-guided optimizations, program representations, register promotion