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

• 1: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• 2: F. Allen, J. Carter, J. Fabri, J. Ferrante, W. Harrison, P. Loewner, and L. Trevillyan. The experimental compiling system. IBM Journal of Research and Development, 24(6):695--715, Nov. 1980.
• 3: J. Allen and K. Kennedy. PFC: a program to convert FORTRAN to parallel form. In K. Hwang, editor, Supercomputers: Design and Applications. IEEE Computer Society Press, 1984.
• 4: J. Eugene Ball, Predicting the effects of optimization on a procedure body, ACM SIGPLAN Notices, v.14 n.8, p.214-220, August 1979
• 5: David Binkley, Interprocedural Constant Propagation using Dependence Graphs and a Data-Flow Model, Proceedings of the 5th International Conference on Compiler Construction, p.374-388, April 07-09, 1994
• 6: W. Blume and R. Eigenmann. An overview of symbolic analysis techniques needed for the effective parallelization of the Perfect benchmarks. In Proceedings of the 23rd International Conference on Parallel Processing, Volume 2: Software, pages 233--238. CRC Press, Aug. 1994.
• 7: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• 8: Michael Burke , Linda Torczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.367-399, July 1993 [doi>10.1145/169683.169678]
• 9: Paul R. Carini , Michael Hind, Flow-sensitive interprocedural constant propagation, ACM SIGPLAN Notices, v.30 n.6, p.23-31, June 1995
• 10: Mary W. Hall , John M. Mellor-Crummey , Alan Carle , René G. Rodríguez, FIAT: A Framework for Interprocedural Analysis and Transfomation, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.522-545, August 12-14, 1993
• 11: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.23 n.7, p.57-66, July 1988
• 12: Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM SIGPLAN Notices, v.21 n.7, p.58-67, July 1986
• 13: J. Dongarra. LINPACK working note #3: FORTRAN BLAS timing. Technical Report ANL-80-24, Argonne National Laboratory, Feb. 1980.
• 14: Robert W. Floyd, An algorithm for coding efficient arithmetic operations, Communications of the ACM, v.4 n.1, p.42-51, Jan. 1961 [doi>10.1145/366062.366082]
• 15: Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, ACM SIGPLAN Notices, v.28 n.6, p.90-99, June 1993
• 16: J. B. Kam and J. D. Ullman. Monotone data flow analysis frameworks. Acta Inf., 7:305--317, 1977.
• 17: 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]
• 18: R. Metzger and P. Smith. The CONVEX application compiler. Fortran Journal, 3(1):8--10, 1991.
• 19: Brian Richard Murphy , Monica Lam, Frameworks for precise program analysis, 2002
• 20: John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
• 21: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 22: Shmuel Sagiv , Thomas W. Reps , Susan Horwitz, Precise Interprocedural Dataflow Analysis with Applications to Constant Propagation, Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.651-665, May 22-26, 1995
• 23: 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]
• 24: Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985
• 25: B. Wegbreit. Property extraction in well-founded sets. IEEE Transactions on Software Engineering, 1(3), Sept. 1975.
• 26: 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]
• 27: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 28: 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
• 29: {Alle 74} F. E. Allen. Interprocedural data flow analysis. Proceedings IFIP Congress 74, North-Holland Publishing Co.: Amsterdam. 1974.
• 30: {AlKe 84} J. R. Allen and K. Kennedy. PFC: a program to convert Fortran to parallel form. Supercomputers: Design and Applications (K. Hwang, ed.). IEEE Computer Society Press, 1984.
• 31: J. Eugene Ball, Predicting the effects of optimization on a procedure body, ACM SIGPLAN Notices, v.14 n.8, p.214-220, August 1979
• 32: Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, 1983
• 33: 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]
• 34: Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, ACM SIGPLAN Notices, v.19 n.6, p.247-258, June 1984
• 35: 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
• 36: {CoKT 86} K. D. Cooper, K. Kennedy and L. Torczon. Optimization of compiled code in the IRn programming environment. Proceedings of the Nineteenth Annual Hawaii International Conference on Systems Sciences. January, 1986.
• 37: {Dong 80} J. Dongarra. LINPACK working note #3: FORTRAN BLAS timing. Technical Report ANL-80-24, Argonne National Laboratory, February 1980.
• 38: {DBMS 79} J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart. LINPACK Users' Guide. SIAM, Philadelphia. 1979.
• 39: {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.
• 40: {KaUl 77} J. Kam and J. Ullman. Monotone data flow analysis frameworks. Acta Informatica, 7. 1977.
• 41: {Kenn 78} K. Kennedy. Use-definition chains with applications. J. Computer Languages, 3(3). 1978.
• 42: {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.
• 43: 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]
• 44: 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]
• 45: {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.
• 46: 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]
• 47: Linda Marie Torczon, Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation), 1985
• 48: 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]