Keith D. Cooper
Ken Kennedy
Abstract
One of the primary goals of the IRn programming environment project is to mount a concerted attack on the problems of performing interprocedural analysis and optimization in a compiler. Few commercial optimizing compilers employ interprocedural techniques because the cost of gathering the requisite information in a traditional compiler is too great. Computing the side effects of a procedure call requires detailed knowledge of the internals of both the called procedure and any procedures invoked either directly or indirectly from it. Thus, the compiler potentially needs information about the internals of every procedure to determine the side effects of procedure calls, even separately compiled procedures. Gathering this information would require examining the source of every procedure in the program - an expensive process, particularly unfortunate since the primary goal of separate compilation is to reduce the amount of recompilation required in response to changes in an individual procedure.
The existence of a software development environment like the IRn programming environment [HoKe 84] changes the compilation process enough to make computing such information palatable. Since all modules are developed and all programs are defined using tools of the environment, these tools can cooperate to record the information necessary to do a good job of interprocedural analysis and optimization. Whenever the compiler needs information about possible side effects of a particular procedure, it can simply extract this information from the environment's central database. Because the only mechanism for changing modules or programs is through the tools provided by the environment, the compiler is assured that it will be notified of any changes. Thus, it can use information derived from previous analysis with certain knowledge that the information reflects the current state of the program and its procedures.
- 1 Allen, J.R. and Kennedy, K., "PFC: a Program to Convert Fortran to Parallel Form", Report MASC TR 82-6, Dept. of Mathematical Sciences, Rice University, Houston, TX, March 1982.Google Scholar
- 2 Ball, J.E., "Predicting the Effects of Optimization on a Procedure Body", Proceedings of the Sigplan Symposium on Compiler Construction, SIGPLAN Notices, 14(8), 1979. Google ScholarDigital Library
- 3 Caplinger, M.A., "A Simple Intermediate Language for Programming Environments", Ph.D. Dissertation, Department of Computer Science, Rice University, Houston TX, May 1985. Google ScholarDigital Library
- 4 Comer, R.S., "Data Breakpoints", Ph.D. Dissertation, Department of Computer Science, Rice University, Houston, TX, expected Fall 1985.Google Scholar
- 5 Cooper, K.D., "Interprocedural Data Flow Analysis in a Programming Environment", Ph.D. Dissertation, Department of Mathematical Sciences, Rice University, Houston TX, May 1983. Google ScholarDigital Library
- 6 Cooper, K.D., "Analyzing Aliases of Reference Formal Parameters", Proceedings of the Twelfth Annual ACM Symposium on Principles of Programming Languages, 1985. Google ScholarDigital Library
- 7 Cooper, K.D. and K.W. Kennedy, "Efficient Computation of Flow Insensitive Interprocedural Summary Information", Proceedings of the Sigplan Symposium on Compiler Construction, SIGPLAN Notices, 19(6), 1984. Google ScholarDigital Library
- 8 Dongarra, J., "LINPACK Working Note 3: FORTRAN BLAS Timing",# Technical Report ANL-80-24, Argonne National Laboratory, February 1980.Google Scholar
- 9 Fabri, J., "Automatic Storage Optimization", Proceedings of the SIGPLAN Symposium on Compiler Construction, SIGPLAN Notices, 14(8), 1979. Google ScholarDigital Library
- 10 Feldman, S., "Make - A Computer Program for Maintaining Computer Programs", Software Practice and Experience, Vol. 9, 1979.Google Scholar
- 11 Goldberg, A. and D. Robson, Smalltalk-80: The Language and its Implementation, Reading MA: Addison-Wesley, 1983. Google ScholarDigital Library
- 12 Habermann, A.N. and D.S. Notkin, "The Gandalf Software Development Environment", Research Report, Computer Science Department, Carnegie-Mellon University, Pittsburg PA, January 1982.Google Scholar
- 13 Hood, R. and K. Kennedy, "A Programming Environment for Fortran", Proceedings of the Eighteenth Annual Hawaii International Conference on Systems Sciences, 1985.Google Scholar
- 14 Masinter, L., "Global Program Analysis in an Interactive Environment", Xerox Palo Alto Research Center Technical Report SSL-80-1, January 1980.Google Scholar
- 15 Mitchell, J., W. Maybury and R. Sweet, |"Mesa Language Manual", Technical Report CSL-79-3, Xerox Palo Alto Research Center, Palo Alto CA, April 1979.Google Scholar
- 16 Muller, H., "A Conceptual Framework for Configuration Management Systems", Rice University, Houston TX, September 1983.Google Scholar
- 17 Osterweil, L.J. and L.D. Fosdick, "Dave - A Validation, Error Detection and Documentation System for FORTRAN Programs", Technical Report CU-CS-071-75, Computer Science Department, University of Colorado, Boulder CO, June 1975.Google Scholar
- 18 Rochkind, M.J., "The Source Code Control System", IEEE Transactions on Software Engineering, SE-1, Vol. 4, December 1975.Google Scholar
- 19 Spillman, T., "Exposing Side-Effects in a PL/I Optimizing Compiler", IFIPS Proceedings 1971, North-Holland Publishing Co., 1971.Google Scholar
- 20 Teitelman, W., "A Display-Oriented Programmer's Assistant", Proceedings of the Fifth International Joint Conference on Artificial Intelligence, 1977.Google Scholar
- 21 Teitelbaum, R.T. and T. Reps, "The Cornell Program Synthesizer: A Syntax Directed Programming Environment", Communications of the ACM, 24(9), 1981. Google ScholarDigital Library
- 22 Tichy W. F. and M. C. Baker, "Smart Recompilation", Proceedings of the Twelfth Annual Symposium on Principles of Programming Languages, 1985. Google ScholarDigital Library
- 23 Torczon, L.M., "Compilation Dependences in an Ambitious Optimizing Compiler", Ph.D. Dissertation, Department of Computer Science, Rice University, Houston, TX, May 1985. Google ScholarDigital Library
- 24 Zadeck, F.K., "Incremental Data Flow Analysis in a Structured Program Editor", Ph.D. Dissertation, Department of Mathematical Sciences, Rice University, Houston TX, October 1983. Google ScholarDigital Library
Index Terms
- The impact of interprocedural analysis and optimization on the design of a software development environment
Recommendations
The impact of interprocedural analysis and optimization on the design of a software development environment
SLIPE '85: Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environmentsOne of the primary goals of the IRn programming environment project is to mount a concerted attack on the problems of performing interprocedural analysis and optimization in a compiler. Few commercial optimizing compilers employ interprocedural ...
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
The impact of interprocedural analysis and optimization in the Rn programming environment
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 ...
Comments