The impact of interprocedural analysis and optimization in the Rn programming environment

ABSTRACT

In spite of substantial progress in the theory of interprocedural data flow analysis, few practical compiling systems can afford to apply it to produce more efficient object programs. To perform interprocedural analysis, a compiler needs not only the source code of the module being compiled, but also information about the side effects of every procedure in the program containing that module, even separately compiled procedures. In a conventional batch compiler system, the increase in compilation time required to gather this information would make the whole process impractical. In an integrated programming environment, however, other tools can cooperate with the compiler to compute the necessary interprocedural information incrementally. as the program is being developed, decreasing both the overall cost of the analysis and the cost of individual compilations. A central goal of the Rn project at Rice University is to construct a prototype software development environment that is designed to build whole programs, rather than just individual modules. It employs interprocedural analysis and optimization to produce high-quality machine code for whole programs. This paper presents an overview of the methods used by the environment to accomplish this task and discusses the impact of these methods on the various environment components. The responsibilities of each component of the environment for the preparation and use of interprocedural information are presented in detail.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: ALLEN, F. E., AND COCKE, J. A catalogue of optimizing transformations. In Design and Optimization of Compilers, R. Rustin, Ed., Prentice Hall, Englewood Cliffs, N.J., 1972, 1-30.
• 3: ALLEN, J. R., AND KENNEDY, K. PFC: A program to convert Fortran to parallel form. In Supercomputers: Design and Applications, K. Hwang, Ed., IEEE Computer Society Press, New York, 1984, 186-205.
• 4: ALLEN, J. R., AND KENNEDY, K. A parallel programming environment. IEEE Softw. 2, 4 (Jul. 1985), 22-29.
• 5: AMERICAN NATIONAL STANDARDS INSTITUTE. American National Standard Programming Language Fortran, X3.9-1978, 1978.
• 6: AMERICAN NATIONAL STANDARDS INSTITUTE. Proposals approved for Fortran 8x. X3J3/S6.80 (1981).
• 7: 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
• 8: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 9: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 10: BURKE, M. Private communication, Nov. 1983.
• 11: BURKE, M. An interval analysis approach toward interprocedural data flow. Rep. RC 10640, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., July 1984.
• 12: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.152-161, June 25-27, 1986, Palo Alto, California, United States
• 13: CONRADI, R. Inter-procedural optimization of object code. Tech Rep. 25/83, Univ. of Trondheim, Div. of Computer Science, Trondheim-NTH, Norway, 1983.
• 14: Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, 1983
• 15: 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]
• 16: 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
• 17: Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.58-67, June 25-27, 1986, Palo Alto, California, United States
• 18: DEREMER, F., AND KRON, ~-{. H. Programming-in-the-large versus programming-in-the-small. IEEE Trans. Softw. Eng. SE-2, 2 (June 1976), 80-86.
• 19: DONGARRA, J. LINPACK working note 3: FORTRAN BLAS timing. Tech. Rep. ANL-80-24, Argonne National Laboratory, Feb. 1980.
• 20: DONGARRA, J. J., BUNCH, J. R., MOLER, C. B., AND STEWART, G.W. LINPACK Users' Guide. SIAM, Philadelphia, Pa., 1979.
• 21: A. P. Yershov, ALPHA—An Automatic Programming System of High Efficiency, Journal of the ACM (JACM), v.13 n.1, p.17-24, Jan. 1966 [doi>10.1145/321312.321314]
• 22: Janet Fabri, Automatic storage optimization, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.83-91, August 06-10, 1979, Denver, Colorado, United States
• 23: FELDMAN, S. Make--a computer program for maintaining computer programs. Softw. Pract. Exper. 9 (1979), 255-265.
• 24: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 25: HECHT, M. S., AND ULLMAN, J.D. A simple algorithm for global data-flow analysis problems. SIAMJ. Comput. 1, 2 (Dec. 1975), 519-532.
• 26: HOOD, R. T., AND KENNEDY, K. A programming environment for Fortran. In Proceedings of the 18th Annual Hawaii International Conference on Systems Sciences (Jan. 1985), 625-637.
• 27: HOOD, R. T., AND KENNEDY, K. Programming language support for supercomputers. In Frontiers of Supercomputing, Metropolis, Sharp, Worlton, and Ames, Eds., Univ. of California Press, Berkeley, 1986, 282-311.
• 28: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 29: KAM, J., AND ULLMAN, J. Monotone data-flow analysis frameworks. Acta Inf. 7 (1977), 305-317.
• 30: KENNEDY, K. A survey of data-flow analysis techniques. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds., Prentice-Hall, Englewood Cliffs, N.J., 1981, 5-54.
• 31: Butler W. Lampson , Eric E. Schmidt, Organizing software in a distributed environment, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.1-13, June 27-29, 1983, San Francisco, California, United States
• 32: LERLANG, D. B., AND McLEAN, G. D. Configuration management for large-scale software development efforts. In Workshop on Software Engineering Environments for Programming-inthe-Large (Harwichport, Ma., June 1985).
• 33: MASINTER, L. Global program analysis in an interactive environment. Tech. Rep. SSL-80-1, Xerox Palo Alto Research Center, Paid Alto, Calif., Jan. 1980.
• 34: MITCHELL, J., MAYRURY, W., AND SWEET, R. Mesa language manual. Tech. Rep. CSL-79-3, Xerox Palo Alto Research Center, Paid Alto, Calif., Apr. 1979.
• 35: MYERS, E.W. A precise and efficient algorithm for determining existential summary data-flow information. Tech. Rep. CU-CS-175-80, Univ. of Colorado, Dept. of Computer Science, Boulder, Mar. 1980.
• 36: 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]
• 37: OSTERWEIL, L. J., AND FOSDICK, L.D. Dave--a validation, error detection and documentation system for FORTRAN programs. Tech. Rep. CU-CS-071-75, Univ. of Colorado, Dept. of Computer Science, Boulder, June 1975.
• 38: REW, J. H., AND LEWIS, H.R. Symbolic evaluation and the global value graph. Tech. Rep. 37-82, Harvard Univ., Aiken Computation Lab., Cambridge, Mass., 1982.
• 39: ROCHKINO, M. J. The source code control system. IEEE Trans. So{tw. Eng. SE-1, 4 (Dec. 1975), 364-370.
• 40: Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979 [doi>10.1145/322123.322135]
• 41: Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
• 42: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 43: W. F. Tichy, A data model for programming support environments and its application, Trends in information systems, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 44: Walter F. Tichy , Mark C. Baker, Smart recompilation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-244, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318648]
• 45: Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985
• 46: 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]
• 47: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, 1984

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Design, Languages, Performance