Predicting the effects of optimization on a procedure body

ABSTRACT

Practical application of procedure integration (inline expansion) as a program optimization requires some method for estimating the effects of subsequent optimization on the integrated procedure. A technique is described for predicting the code improvement that can be expected due to constant folding and test elision when a procedure call involving constant actual parameters is integrated. The technique is based on information collected during a single data flow analysis of each procedure body, and on execution frequency statistics for the procedure. This information can then be used to estimate the cost in code size and the benefit in execution speed of integrating each call to the procedure. The algorithm uses a syntax directed analysis technique suitable for structured programming languages without gotos.

REFERENCES

• 1: Allen, Frances E. and Cocke, John. A catalogue of optimizing transformations. RC 3548, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., September 1971.
• 2: Allen, Frances E. Interprocedural data flow analysis. Proc. IFIP Congress 74, North Holland Publishing Co., Amsterdam, 1974, 398-402.
• 3: Allen, F. E., Carter, J. L., Harrison, W. H., Loewner, P. G., Tapscott, R. P., Trevillyan, L. H., and Wegman, M.N. The Experimental Compiling Systems Project. IBM T. J. Watson Research Center, Yorktown Heights, N.Y., August 1977.
• 4: Ball, Eugene; Williams, Graeme; and Low, James. Zeno Preliminary Language Description. TR41, University of Rochester Computer Science Department, Rochester, NY, December 1978.
• 5: Alan Demers , James Donahue , Glenn Skinner, Data types as values: polymorphism, type-checking, encapsulation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.23-30, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512764]
• 6: Harrison, William. Compiler analysis of the value ranges for variables. RC 5544, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., July 1975.
• 7: William Harrison, A new strategy for code generation: the general purpose optimizing compiler, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-37, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512954]
• 8: Hilfinger, Paul; Feldman, Gary; Fitzgerald, Robert; Kimura, Izumi; London, Ralph L.; Prasad, K. V. S.; Prasad, V. R.; Rosenberg, Jonathan; Shaw, Mary; and Wulf, William A. An Informal Definition of Alphard (Preliminary). Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pa, February 1978.
• 9: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 10: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 11: B. W. Lampson , J. J. Horning , R. L. London , J. G. Mitchell , G. J. Popek, Report on the programming language Euclid, ACM SIGPLAN Notices, v.12 n.2, p.1-79, February 1977 [doi>10.1145/954666.971189]
• 12: Liskov, Barbara; Moss, Eliot; Schaffert, Craig; Scheifler, Bob; and Snyder, Alan. CLU Reference Manual. Computation Structures Group Memo 161, Massachusetts Institute of Technology, Laboratory for Computer Science, July 1978.
• 13: Mitchell, James G. and Wegbreit, Ben. Schemes: A High Level Data Structuring Concept. CSL-77-1, Xerox Palo Alto Research Center, Palo Alto, Ca., January 1977.
• 14: Zelkowitz, M.V. and Bail, W.G. Optimization of structured programs. Software Practice and Experience, 4 (1974), 51-57.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Performance