Interprocedural constant propagation

ABSTRACT

In a compiling system that attempts to improve code for a whole program by optimizing across procedures, the compiler can generate better code for a specific procedure if it knows which variables will have constant values, and what those values will be, when the procedure is invoked. This paper presents a general algorithm for determining for each procedure in a given program the set of inputs that will have known constant values at run time. The precision of the answers provided by this method are dependent on the precision of the local analysis of individual procedures in the program. Since the algorithm is intended for use in a sophisticated software development environment in which local analysis would be provided by the source editor, the quality of the answers will depend on the amount of work the editor performs. Several reasonable strategies for local analysis with different levels of complexity and precision are suggested and the results of a prototype implementation in a vectorizing Fortran compiler are presented.

REFERENCES

• AhUl 77: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• Alle 74: F. E. Allen. Interprocedural data flow analysis. Proceeding8 IFIP Congre88 7g, North-Holland Publishing Co.: Amsterdam. 1974.
• AlKe 84: J.R. Allen and K. Keanedy. PFC: a program to convert Fortran to parallel form. Supercomputer6: Denigu and Application8 (K. Hwang, ed.). IEEE Computer Society Press, ~984.
• Ball 79: J. Eugene Ball, Predicting the effects of optimization on a procedure body, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.214-220, August 06-10, 1979, Denver, Colorado, United States
• Coop 83: Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, 1983
• Coop 85: Keith D. Cooper, Analyzing aliases of reference formal parameters, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.281-290, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318658]
• CoKe 84: Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.247-258, June 17-22, 1984, Montreal, Canada
• CoKT 85: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization on the design of a software development environment, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.107-116, June 25-28, 1985, Seattle, Washington, United States
• CoKT 86: K.D. Cooper, K. Kennedy and L. Torczon. Optimization of compiled code in the IRa programming environment. Proceeding8 of the Nineteenth Annual Hawaii International Conference on Systems Sciences. January, 1986.
• Dong 80: J. Dongarra. LINPACK working note ~3: FORTRAN BLAS timing. Technical Report ANI~80-24, Argonne National Laboratory, February 1980.
• DBMS 79: J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart. LINPACK U~ers' Guide. SIAM, Philadelphia. 1979.
• HoKe 85: R. T. Hood and K. Kennedy. A programming environment for Fortran. Proceedings of the Eighteenth Annual Hawaii International Conference on Systems Sciences, 1985.
• KaUl 77: J. Kam and J. Ullman. Monotone data flow analysis frameworks. Acta lnformatica, 7. 1977.
• Kenn 78: K. Kennedy. Use-definition chains with applications. Jr. Computer Languages, 3(3). 1978.
• Kenn 81: K. Kennedy. A survey of data flow analysis techniques. Program Flow Analysis: Theory and Applications (S.S. Muchnick and N.D. Jones, eds.). Prentice-Hall. 1981. pp. 5-54.
• Kild 73: 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]
• Myer 81: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• ReLe 82: J. H. Reif and H. R. Lewis. Symbolic evaluation and the global value graph. TR 37-82, Aiken Computation Laboratory, Harvard University. 1982.
• Sche 77: Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
• Torc 85: Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985
• WeZa 85: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation

General Terms:
Algorithms, Performance, Theory