A lifetime optimal algorithm for speculative PRE

ABSTRACT

A lifetime optimal algorithm, called MC-PRE, is presented for the first time that performs speculative PRE based on edge profiles. In addition to being computationally optimal in the sense that the total number of dynamic computations for an expression in the transformed code is minimized, MC-PRE is also lifetime optimal since the lifetimes of introduced temporaries are also minimized. The key in achieving lifetime optimality lies not only in finding a unique minimum cut on a transformed graph of a given CFG, but also in performing a data-flow analysis directly on the CFG to avoid making unnecessary code insertions and deletions. The lifetime optimal results are rigorously proved. We evaluate our algorithm in GCC against three previously published PRE algorithms, namely, MC-PREcopt (Qiong and Xue's computationally optimal version of MC-PRE), LCM (Knoop, Rüthing, and Steffen's lifetime optimal algorithm for performing nonspeculative classic PRE), and CMP-PRE (Bodik, Gupta, and Soffa's PRE algorithm based on code-motion preventing (CMP) regions, which is speculative but not computationally optimal). We report and analyze our experimental results, obtained from both actual program execution and instrumentation, for all 22 C, C++ and FORTRAN 77 benchmarks from SPECcpu2000 on an Itanium 2 computer system. Our results show that MC-PRE (or MC-PREcopt) is capable of eliminating more partial redundancies than both LCM and CMP-PRE (especially in functions with complex control flow), and, in addition, MC-PRE inserts temporaries with shorter lifetimes than MC-PREcopt. Each of both benefits has contributed to the performance improvements in benchmark programs at the costs of only small compile-time and code-size increases in some benchmarks.

REFERENCES

• 1: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 2: Beszedes, A. 2003. Optimizing for space: Measurements and possibilities for improvement. In GCC Summit 2003.
• 3: Rastislav Bodik , Rajiv Gupta , Mary Lou Soffa, Path-sensitive, value-flow optimizations of programs (program analysis), 1999
• 4: 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
• 5: 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
• 6: Qiong Cai , Jingling Xue, Optimal and efficient speculation-based partial redundancy elimination, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 7: 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
• 8: Chandra S. Chekuri , Andrew V. Goldberg , David R. Karger , Matthew S. Levine , Cliff Stein, Experimental study of minimum cut algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.324-333, January 05-07, 1997, New Orleans, Louisiana, United States
• 9: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 10: Cliff Click, Global code motion/global value numbering, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.246-257, June 18-21, 1995, La Jolla, California, United States
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: 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]
• 13: D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
• 14: Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.212-223, June 15-19, 1992, San Francisco, California, United States
• 15: Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
• 16: Manel Fernandez , Roger Espasa, Link-Time Path-Sensitive Memory Redundancy Elimination, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.300, February 14-18, 2004 [doi>10.1109/HPCA.2004.10009]
• 17: Ford, L. R. and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press, Princeton, NJ.
• 18: Goldberg, A. 2003. Network Optimization Library. http://www.avglab.com/andrew/soft.html.
• 19: 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
• 20: Max Hailperin, Cost-optimal code motion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1297-1322, Nov. 1998 [doi>10.1145/295656.295664]
• 21: R. Nigel Horspool , H. C. Ho, Partial Redundancy Elimination Driven by a Cost-Benefit Analysis, Proceedings of the 8th Israeli Conference on Computer-Based Systems and Software Engineering, p.111, June 18-19, 1997
• 22: Antony L. Hosking , Nathaniel Nystrom , David Whitlock , Quintin Cutts , Amer Diwan, Partial redundancy elimination for access path expressions, Software—Practice & Experience, v.31 n.6, p.577-600, May 2001 [doi>10.1002/spe.371]
• 23: Hu, T. C. 1970. Integer Programming and Network Flows. Addison-Wesley, Reading, MA.
• 24: Troy A. Johnson , Rudolf Eigenmann , T. N. Vijaykumar, Min-cut program decomposition for thread-level speculation, ACM SIGPLAN Notices, v.39 n.6, May 2004
• 25: Kennedy, K. 1972. Safety of code motion. International Journal of Computer Mathematics 3, 2--3, 117--130.
• 26: Robert Kennedy , Fred C. Chow , Peter Dahl , Shin-Ming Liu , Raymond Lo , Mark Streich, Strength Reduction via SSAPRE, Proceedings of the 7th International Conference on Compiler Construction, p.144-158, March 28-April 04, 1998
• 27: Robert Kennedy , Sun Chan , Shin-Ming Liu , Raymond Lo , Peng Tu , Fred Chow, Partial redundancy elimination in SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.627-676, May 1999 [doi>10.1145/319301.319348]
• 28: Jens Knoop , J. Knoop , G. Goos, Optimal Interprocedural Program Optimization: A New Framwork and Its Application, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 29: Jens Knoop , Eduard Mehofer, Distribution Assignment Placement: Effective Optimization of Redistribution Costs, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.628-647, June 2002 [doi>10.1109/TPDS.2002.1011416]
• 30: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
• 31: 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]
• 32: Jens Knoop , Jean-Francois Collard , Roy Dz-Ching Ju, Partial Redundancy Elimination on Predicated Code, Proceedings of the 7th International Symposium on Static Analysis, p.260-279, June 29-July 01, 2000
• 33: Jin Lin , Tong Chen , Wei-Chung Hsu , Pen-Chung Yew , Roy Dz-Ching Ju , Tin-Fook Ngai , Sun Chan, A compiler framework for speculative analysis and optimizations, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 34: Raymond Lo , Fred Chow , Robert Kennedy , Shin-Ming Liu , Peng Tu, Register promotion by sparse partial redundancy elimination of loads and stores, ACM SIGPLAN Notices, v.33 n.5, p.26-37, May 1998
• 35: 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]
• 36: Robert Morgan, Building an optimizing compiler, Digital Press, Newton, MA, 1998
• 37: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 38: 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]
• 39: Oliver Rüthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325715]
• 40: Bernhard Scholz , Nigel Horspool , Jens Knoop, Optimizing for space and time usage with speculative partial redundancy elimination, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 41: Loren Taylor Simpson , Keith D. Cooper, Value-driven redundancy elimination, 1996
• 42: Bernhard Steffen, Property-Oriented Expansion, Proceedings of the Third International Symposium on Static Analysis, p.22-41, September 24-26, 1996
• 43: 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
• 44: Bernhard Steffen , Jens Knoop , Oliver Rüthing, Efficient code motion and an adaption to strength reduction, Proceedings of the international joint conference on theory and practice of software development on Advances in distributed computing (ADC) and colloquium on combining paradigms for software development (CCPSD): Vol. 2, p.394-415, April 1991, Brighton, United Kingdom
• 45: Sverre Jarp. 2002. A methodology for using the Itanium 2 performance counters for bottleneck analysis. http://www.gelato.org/pdf/Performance_counters_final.pdf.
• 46: Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler optimization of scalar value communication between speculative threads, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
Partial redundancy elimination, classic PRE, computational optimality, data-flow analysis, lifetime optimality, speculative PRE