Keith D. Cooper
Ken Kennedy
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.
- 1 AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 4 ALLEN, J. R., AND KENNEDY, K. A parallel programming environment. IEEE Softw. 2, 4 (Jul. 1985), 22-29.Google Scholar
- 5 AMERICAN NATIONAL STANDARDS INSTITUTE. American National Standard Programming Language Fortran, X3.9-1978, 1978.Google Scholar
- 6 AMERICAN NATIONAL STANDARDS INSTITUTE. Proposals approved for Fortran 8x. X3J3/S6.80 (1981).Google Scholar
- 7 BALL, J.E. Predicting the effects of optimization on a procedure body. In Proceedings o{ the SIG-PLAN 79 Symposium on Compiler Construction; SIGPLAN Not. 14, 8 (Aug. 1979), 214-220. Google Scholar
- 8 BANNING, J.P. An efficient way to find the side effects of procedure calls and the aliases of variables. In Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages (Jan. 1979), ACM, New York, 29-41. Google Scholar
- 9 BARTH, J.M. A practical interprocedural data-flow analysis algorithm. Commun. ACM 21, 9 (Oct. 1972), 613-640. Google Scholar
- 10 BURKE, M. Private communication, Nov. 1983.Google Scholar
- 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.Google Scholar
- 12 CALLAHAN, D., COOPER, K. D., KENNEDY, g., AND TORCZON, L.M. Interprocedural constant propagation. In Proceedings of the SIGPLAN 86 Symposium on Compiler Construction (June 1986), ACM, New York. Google Scholar
- 13 CONRADI, R. Inter-procedural optimization of object code. Tech Rep. 25/83, Univ. of Trondheim, Div. of Computer Science, Trondheim-NTH, Norway, 1983.Google Scholar
- 14 COOPER, K. D. Interprocedural data flow analysis in a programming environment. Ph.D. dissertation, Rice Univ., Dept. of Mathematical Sciences, Houston, Tex., May 1983. Google Scholar
- 15 COOPER, g.D. Analyzing aliases of reference formal parameters. In Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages (Jan. 1985), ACM, New York, 281-290. Google Scholar
- 16 COOPER, K. D., AND KENNEDY, K. Efficient computation of flow-insensitive interprocedural summary information. In Proceedings of the SIGPLAN 84 Symposium on Compiler Construction; SIGPLAN Not. 19, 6 (June 1984), 247-258. Google Scholar
- 17 COOPER, K. D., KENNEDY, K., AND TORCZON, L. Interprocedural optimization: Eliminating unnecessary recompilation. In Proceedings of the SIGPLAN 86 Symposium on Compiler Construction (June 1986), ACM, New York. Google Scholar
- 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.Google Scholar
- 19 DONGARRA, J. LINPACK working note 3: FORTRAN BLAS timing. Tech. Rep. ANL-80-24, Argonne National Laboratory, Feb. 1980.Google Scholar
- 20 DONGARRA, J. J., BUNCH, J. R., MOLER, C. B., AND STEWART, G.W. LINPACK Users' Guide. SIAM, Philadelphia, Pa., 1979.Google Scholar
- 21 ERSHOV, A. ALPHA--an automatic programming system of high efficiency. J. ACM 13, 1 (Jan. 1966), 17-24. Google Scholar
- 22 FARm, J. Automatic storage optimization. In Proceedings of the S1GPLAN 79 Symposium on Compiler Construction; SIGPLAN Not. 14, 8 (Aug. 1979), 83-91. Google Scholar
- 23 FELDMAN, S. Make--a computer program for maintaining computer programs. Softw. Pract. Exper. 9 (1979), 255-265.Google Scholar
- 24 GRAHAM, S. L., AND WEOMAN, M. A fast and usually linear algorithm for global-flow analysis. J. ACM 23, 1 (Jan. 1976), 172-202. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 28 KAM, J., AND ULLMAN, g. Global data-flow analysis and iterative algorithms. J. ACM 23, 1(1976), 158-171. Google Scholar
- 29 KAM, J., AND ULLMAN, J. Monotone data-flow analysis frameworks. Acta Inf. 7 (1977), 305-317.Google Scholar
- 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.Google Scholar
- 31 LAMPSON, B. W., AND SCHMIDT, E.E. Organizing software in a distributed environment. In SIGPLAN 83 Symposium on Programming Language Issues in Software Systems (June 1983), ACM, New York, 1-13. Google Scholar
- 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).Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 36 MYEI~S, E.W. A precise interprocedural data-flow algorithm. In Proceedings o{ the 8th Annual ACM Symposium on Principles of Programming Languages (Jan. 1981), ACM, New York, 219-230. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 39 ROCHKINO, M. J. The source code control system. IEEE Trans. So{tw. Eng. SE-1, 4 (Dec. 1975), 364-370.Google Scholar
- 40 ROSEN, B.K. Data-flow analysis for procedural languages. J. ACM 26, 2 (Apr. 1979), 322-344. Google Scholar
- 41 TARJAN, R.E. A unified approach to path problems. J. ACM 28, 3 (1981), 577-593. Google Scholar
- 42 TA~AN, R.E. Fast algorithms for solving path problems. J. ACM 28, 3 (1981), 594-614. Google Scholar
- 43 TICHY, W.F. A data model for programming support environments and its applications. In Automated Tools {or Information Systems Design, H.-J. Schneider and A. L. Wasserman, Eds., North-Holland, Amsterdam, 1982. Google Scholar
- 44 TICHY, W. F., AND BAKER, M.C. Smart recompilation. In Proceedings o{ the 12th Annual ACM Symposium on Principles o{ Programming Languages (Jan. 1985), ACM, New York, 236-244. Google Scholar
- 45 TORCZON, L.M. Compilation dependences in an ambitious optimizing compiler. Ph.D. dissertation, Rice Univ., Dept. of Computer Science, Houston, Tex., May 1985. Google Scholar
- 46 WEGMAN, M., AND ZADECK, F.K. Constant propagation with conditional branches. In Proceedings o{ the 12th Annual ACM Symposium on Principles o{ Programming Languages (Jan. 1985), ACM, New York, 291-299. Google Scholar
- 47 ZADECK, F.K. Incremental data-flow analysis in a structured program editor. Ph.D. dissertation, Rice Univ., Dept. of Mathematical Sciences, Houston, Tex., Oct. 1983. Google Scholar
Index Terms
- The impact of interprocedural analysis and optimization in the Rn programming environment
Recommendations
SVF: interprocedural static value-flow analysis in LLVM
CC 2016: Proceedings of the 25th International Conference on Compiler ConstructionThis paper presents SVF, a tool that enables scalable and precise interprocedural Static Value-Flow analysis for C programs by leveraging recent advances in sparse analysis. SVF, which is fully implemented in LLVM, allows value-flow construction and ...
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 ...
Interprocedural Pointer Analysis in Goanna
Goanna is an industrial-strength static analysis tool used in academia and industry alike to find bugs in C/C++ programs. Unlike existing approaches, Goanna uses the off-the-shelf model checker NuSMV as its core analysis engine on a syntactic flow-...
Reviews
This is a long-winded, but interesting, paper describing an integrated programming environment that supports interprocedural optimizations of FORTRAN programs. The best sections show how to split the responsibility for gathering information among the editor, the compiler of individual modules, and the global program compiler, as well as how supporting optimization impacts their environment's organization. Other sections discuss things the authors haven't implemented yet: actually performing optimizations, and reducing the need for recompilations due to editing changes that invalidate some of the stored information. The paper combines old techniques with some new ones. A minor flaw is that the authors spend too long discussing basic techniques and repeating minor points in the early sections.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments