Mark N. Wegman
Abstract
Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far foward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. Using the algorithms presented in this paper can produce smaller and faster compiled programs. The same algorithms can be used for other kinds of analyses (e.g., type of determination). We present four algorithms in this paper, all conservitive in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known. We also present a new algorithm that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant progagation. Several variants of this algorithm are considered.
- 1 ARo, A. V., SETm, R, AND ULLMAEN, J. D. Comp~lers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass., 1986. Google Scholar
- 2 ALLEN, F. E. A catalogue of optimizing transformations. In Design and Optimizat~on of Compilers. R. Rustin, Ed., Prentice Hall, Englewood Cliffs, N.J, 1972, pp. 1-30.Google Scholar
- 3 ALLEN, F.E. Interprocedural data fiow analysis. Inf. Proc. 74 (1974), 398-402.Google Scholar
- 4 ALLEN, F. E., CARTER, J. L., FABRI, J., FERRANTE, J., HARRISON, W. H., LOEWNER, P. G., AND TREVmLYAN, L. H. The experimental compiling system. IBM J. Res. Dev. 24, 6 (Nov. 1980), 695-715.Google Scholar
- 5 ALPERN, B., WEGMAN, M. N., AND ZADECK, F.K. Detecting equality of values in programs. In Conference Recordings of the Fifteenth ACM Symposium on Principles of Programming Languages. (Jan. 1988), pp. 1-11. Google Scholar
- 6 ArrEL, A. W., AND &M, T. Continuation-passing, closure-passing style. In Conference Recordings of the Sixteenth ACM Symposium on Principles of Programming Languages. (Jan. 1989), pp. 293-302. Google Scholar
- 7 BALL, J.E. Predicting the effects of optimization on a procedure body. In Proceedings of the SIGPLAN'79 Symposium on Compiler Construction. (Aug. 1979), pp. 214-220. Published as SIGPLAN Not. 14, 8. Google Scholar
- 8 BANNING, J.B. An efficient way to find the side effects of procedure calls and the aliases of variables. In Conference Recordings of the Sixth ACM Symposium on Principles of Programming Languages. (Jan. 1979), pp. 29-41. Google Scholar
- 9 BARTH, J.M. An interprocedural data fiow analysis algorithm. In Conference Recordings of the Fourth ACM Symposium on Principles of Programming Languages. (Jan. 1977), pp. 119-131. Google Scholar
- 10 BURKE, M. An interval approach toward interprocedural analysis. Tech. Rep. RC 10640 47724, IBM, July 1984.Google Scholar
- 11 BURKE, M., AND CYTRON, R. Interprocedural dependence analysis and parallelization. In Proceedings of the SIGPLAN'86 Symposium on Compiler Construction. (June 1986), pp. 162-175. Published as SIGPLAN Not. 21, 7. Google Scholar
- 12 CALLAHAN, D., COOPER, K. D., KENNEDY, K. W., AND TORCZON, L. M. Interprocedural constant propagation. In Proceedings of the SIGPLAN'86 Symposium on Compiler Construction. (June 1986), pp. 152-161. Published as SIGPLAN Not. 21, 7. Google Scholar
- 13 CHOW, F. C. A portable machine-independent global optimizer--Design and measurements. Tech. Rep. 83-254 (Ph.D. thesis), Computer Systems Laboratory, Stanford Univ., Palo Alto, Calif., Dec. 1983. Google Scholar
- 14 COCKE, J. AND SCHWARTZ, T. Programming Languages and The~r Compilers: Prelimmary Notes. Courant Institute of Mathematical Sciences, New York Univ., April 1970. Google Scholar
- 15 CoorER, K. D. Interprocedural data fiow analysis in a programming environment. Ph.D. thesis, Dept. of Mathematical Sciences, Rice Univ., 1983. Google Scholar
- 16 CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F.K. Efficiently computing statie single assignment form and the control dependence graph. Tech. Rep. RC 14756, IBM, revised Mar. 1991.Google Scholar
- 17 ELLIS, J.R. Bulldog: A compiler for VLIW architectures. Ph.D. thesis, Dept. of Computer Science, Yale Unir., New Haven, Conn., Feb. 1985. Google Scholar
- 18 ERSHOV, A. P. On the essence of compilation. In IFIP Working Conference on Formal Description of Programming Concepts. (Aug. 1977).Google Scholar
- 19 FERRANTE, J. AND OTTENSTEIN, K. J. A program form based on data dependency in predicate regions. In Conference Recordings of the Tenth ACM Symposium on Principles of Programming Languages. (Jan. 1983). Google Scholar
- 20 FURTNEY, M. AND PRATT, T.W. Kernel-control tailoring of sequential programs for parallel execution. In Proceedings of the 1982 International Conference on Parallel Processing. (Aug. 1982), pp. 245-247.Google Scholar
- 21 GRAHAM, S. L. AND WEGMAN, M. N. A fast and usually linear algorithm for global fiow analysis. J. ACM23, i (Jan. 1976), 172-202. Google Scholar
- 22 HARRISON, W.H. Compiler analysis of the value ranges for variables. IEEE Trans. Softw. Eng. SE-3, 3 (May 1977), 243-250.Google Scholar
- 23 HOLLEY, L. H. AND ROSEN, B.K. Qualified data fiow problems. IEEE Trans. Softw. Eng. SE-7, I (Jan. 1981), 60-78.Google Scholar
- 24 JOHNgON, I4. Dataflow analygis for intraetable systems software. In Proeeedings of the SIGPLAN'86 Symposium on Compiler Construction. (June 1986), pp. 109-117. Published as SIGPLAN Not. 21, 7. Google Scholar
- 25 KAM, J. B. AND ULLMAN, J. D. Monotone data fiow analysis frameworks. Acta Inf. 7 (1977), 305-317.Google Scholar
- 26 KmnALL, G.A. A unified approach to global program optimization. In Conference Recordings of the First ACM Symposium on Princ~ples of Programming Languages. (Oct. 1973), pp. 194-206. Google Scholar
- 27 MOREL, E. AND RENVOISE, C. Global optimization by suppression of partial redundancies. Commun. ACM 22, 2 (Feb. 1979), 96-103~ Google Scholar
- 28 MUCSMCK, S. S. AND JONES, N. D, Eds. Program Flow Analysis. Prentice~Hall, Englewood Cliffs, N.J., 1981.Google Scholar
- 29 MYERS, E.W. A precise interprocedural data fiow algorithm. In Conference Recordings of the Eighth ACM Symposium on Principles of Programming Languages. (Jan. 1981), pp. 219-230. Google Scholar
- 30 O~rENSTE~N, K. J. Data-fiow graphs as an intermediate form. Ph.D. thesis, Dept. of Computer Science, Purdue Univ., Aug. 1978.Google Scholar
- 31 PRATT, T. W. Program analysis and optimization through kernel-control decomposition. Acta Inf. 9 (1978), 195-216.Google Scholar
- 32 REIF, J. H. AND LEWm, H R Symbolic evaluation and the global value graph. In Conference Recordmgs of the Fourth ACM Symposium on Principles of Programming Languages. (Jan. 1977), pp. 104-118. Google Scholar
- 33 REIF, J. H. AND LEW~S, H. R. Efficient symbolic analysis of programs J. Comput. Syst. Sci. 32, 3 (June 1986), 280-313. Google Scholar
- 34 REIF, J. H. AND T~JAN, R.E. Symbolic program analysis in almost linear time. SIAM J. Comput. 11, I (Feb. 1982), 81-93.Google Scholar
- 35 RICSARDSON, S. AND GANAPATm, M. Interprocedural analysis vs. procedure integration. Inf. Process. Lett. 32, 3 (Aug. 1989), 137-142. Google Scholar
- 36 R~CHARDSON, S. AND GANAPATm, M. Code optimization across procedures. IEEE Comput. 22, 2 (Feb. 1989), 42-51. Google Scholar
- 37 ROSEN, B. K. Data fiow analysis for procedural languages. J. ACM 26, 2 (April 1979), 322-344. Google Scholar
- 38 ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F. K. Global value numbers and redundant computations. In Conference Recordings of the Fifteenth ACM Symposium on Prmc~ples of Programming Languages. (Jan. 1988), pp. 12-27. Google Scholar
- 39 SCREIFLER, R. W. An analysis of inline substitution for a structured programming language. Commun. ACM 20, 9 (Sept. 1977), 647-654. Google Scholar
- 40 SsAPmo, R. M. AND SAI~T, H. The representat~on of algorithms. Tech. Rep. CA-7002-1432, Massachusetts Computer Associates, Feb. 1970.Google Scholar
- 41 TENENBAUM, A.M. Type determination for very high level languages. Ph.D. thesis, Courant Institute of Mathematical Sciences, New York Univ., Oct. 1974. Google Scholar
- 42 WEaSREIT, B. Property extraction in well-founded property sers IEEE Trans. Softw. Eng SE-l, 3 (Sept 1975), 270-285.Google Scholar
- 43 WEGMAN, M.N. General and efficient methods for global code improvement. Ph.D. thesis, Computer Science Dept., Univ. of California at Berkeley, Berkeley, 1981. Google Scholar
- 44 W~GMAN, M. N. AND ZADECK, F. K. Constant propagation with conditional branches. In Conference Record~ngs of the Twelfth ACM Symposium on Princ~ples of Programm~ng Languages. (Jan. 1985), pp. 291-299. Google Scholar
Index Terms
- Constant propagation with conditional branches
Recommendations
Interprocedural constant propagation: an empirical study
Constant propagation is an optimization that substitutes values for names. Interprocedural constant propagation performs this substitution throughout an entire program, propagating constant values across procedure boundaries. CONVEX Computer Corporation ...
A Constant Propagation Algorithm for Explicitly Parallel Programs
In this paper, we present a constant propagation algorithm for explicitly parallel programs, which we call the Concurrent Sparse Conditional Constant propagation algorithm. This algorithm is an extension of the Sparse Conditional Constant propagation ...
Reviews
Anne De Niel
Constant propagation is a way to discover which values in a program remain constant over all possible program executions. The purpose of constant propagation is optimization. The authors discuss several existing algorithms by relating them to each other within a single framework, and deal with implementational aspects . The authors present a new algorithm for constant propagation that takes conditional branches into consideration and detects unreachable code. The algorithm can be combined with both procedure integration and interprocedural analysis requiring aliasing information. The paper is self-contained and written in a clear, informal, somewhat verbose style. Research results are presented, but a large part of the text is devoted to identifying their relationship with other work. Alternative algorithms for constant propagation are pointed out. The work mentioned is mainly oriented toward classical imperative languages. The imperative language features covered are quite basic. The paper contains few references to research concerning functional, object-oriented, or logic programming languages. The authors succeed in their effort to present their work on constant propagation to a large readership. The application domain of their algorithms seems to be fairly limited, however.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments