Complete inlining of recursive calls: beyond tail-recursion elimination

ABSTRACT

A compiler optimizing transformation called complete inlining to inline and eliminate recursive calls is presented. The complete inlining can eliminate the recursive calls that cannot be eliminated by tail-recursion elimination. It can inline the recursive calls completely which the existing procedure inlining can only inline partially.

REFERENCES

• 1: F. E. Allen and J. Cocke. A catalogue of optimizing transformations. In R. Ruskin, editor, Design and Implementation of Compilers. Prentice-Hall, 1971.
• 2: Andrew Ayers , Richard Schooler , Robert Gottlieb, Aggressive inlining, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.134-145, June 16-18, 1997, Las Vegas, Nevada, United States
• 3: Jan Hubicka. The gcc call graph module: A framework for inter-procedural optimization. In Proceedings of the GCC Developers' Summit, pages 65--78, June 2004.
• 4: Xavier Vera , Jingling Xue, Let's Study Whole-Program Cache Behaviour Analytically, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.175, February 02-06, 2002
• 5: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 6: Andreas Bauer. Compilation of Functional Programming Languages using GCC - Tail Calls. Master's thesis, Department of Informatics, Munich University of Technology, Munich, Germany, 2003.
• 7: Shin-Ming Liu , Raymond Lo , Fred Chow, Loop Induction Variable Canonicalization in Parallelizing Compilers, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.228, October 20-23, 1996
• 8: S. Pop, P. Claus, V. Loechner, and G.-A. Silber. Fast recognition of scalar evolutions on three-address SSA code. Technical Report A/354/CRI, Centre de Recherche en Informatique (CRI), 2004.
• 9: Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , Kyle A. Gallivan, A unified framework for nonlinear dependence testing and symbolic analysis, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006226]
• 10: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 11: Peiyi Tang. Complete inlining of recursive calls: Beyond tail-recursion elimination. Technical Report titus.compsci.ualr.edu/~ptang/papers/btr.pdf, Department of Computer Science, University of Arkansas at Little Rock, 2005.
• 12: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 13: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 14: Peiyi Tang and Pen-Chung Yew. Interprocedural induction variable analysis. International Journal of Foundations of Computer Science, 14(3):405--423, June 2003.
• 15: Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.258-269, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Recursion

Keywords:
call graph, complete inlining, full control flow graph, procedure inlining, tail-recursion elimination