Constant Propagation with Conditional Branches

Mark N. Wegman, F. Kenneth Zadeck, 1991, ACM TOPLAS

About this paper中文日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

English
Tiếng Việt

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 forward 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 determination). We present four algorithms in this paper, all conservative 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 propagation. Several variants of this algorithm are considered.

Categories and Subject Descriptors: D.3.3 [Programming Languages]: Language Constructs and Features—data types and structures; procedures, functions and subroutines; D.3.4 [Programming Languages]: Processors—code generation; compilers; optimization; preprocessors; I.2.2 [Artificial Intelligence]: Automatic Programming—program transformation General Terms: Algorithms, Design, Languages, Theory Additional Key Words and Phrases: Abstract interpretation, code optimization, constant propagation, control flow graph, interprocedural analysis, procedure integration, static single assignment form, type determination

Mặc dù bài toán lan truyền hằng có thể dễ dàng được chứng minh là không quyết định được nói chung (xem Kam và Ullman [25], chẳng hạn), có nhiều trường hợp hợp lý của bài toán này là quyết định được và có các thuật toán hiệu quả về mặt tính toán tồn tại. Chúng tôi trình bày bốn thuật toán như vậy trong bài báo này. Mỗi thuật toán được trình bày ở đây có tính bảo thủ theo nghĩa là có thể không tìm được tất cả các hằng số, nhưng mỗi hằng số được tìm thấy là hằng số trong mọi thực thi có thể có của chương trình.

Sau một số kiến thức sơ bộ, các thuật toán được trình bày trong Mục 3 theo thứ tự tăng dần về sức mạnh; mỗi thuật toán kế tiếp tìm được ít nhất các hằng số mà thuật toán trước đó tìm được. Ba thuật toán đầu tiên là các cách xây dựng lại từ công trình của những người khác; thuật toán thứ tư là mới và chứa các đặc điểm tốt nhất của mỗi thuật toán trong ba thuật toán trước. Các thuật toán này nằm trong số những thuật toán lan truyền hằng toàn cục đơn giản nhất, nhanh nhất và mạnh nhất đã biết. Trong Mục 4, thuật toán của chúng tôi được chứng minh là đúng và mạnh ít nhất bằng các thuật toán trước tốt nhất với các cận thời gian đa thức. Trong Mục 5, một số vấn đề triển khai phổ biến được thảo luận.

Trong Mục 6, một số kỹ thuật được khảo sát để thực hiện lan truyền hằng trên một vùng lớn hơn các thủ tục đơn lẻ. Trong Mục 6.2, mối quan hệ giữa lan truyền hằng và tích hợp thủ tục được thảo luận. Mục 6.3 đưa ra một thuật toán mới thực hiện một dạng phân tích luồng dữ liệu liên thủ tục trong đó thông tin bí danh được thu thập kết hợp với lan truyền hằng.

Mục 7 phác thảo một số vấn đề mở và Mục 8 kết luận bài báo.

1.

1 INTRODUCTION

This section is missing here.

2 PRELIMINARIES

This section is missing here.

3 CONSTANT PROPAGATION ALGORITHMS

This section is missing here.

4 THEOREMS AND PROPOSITIONS

This section is missing here.

5 OBSERVATIONS ON THE CONSTANT PROPAGATION ALGORITHMS

This section is missing here.

6 PROCEDURE INTEGRATION AND INTERPROCEDURAL CONSTANT PROPAGATION

This section is missing here.

7 AREAS FOR FUTURE RESEARCH

This section is missing here.

8 CONCLUSIONS

This section is missing here.

Acknowledgments

This section is missing here.

References

  1. Aho, A. V., Sethi, R., and Ullman, J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass., 1986.
  2. Allen, F. E. A catalogue of optimizing transformations. In Design and Optimization of Compilers. R. Rustin, Ed., Prentice Hall, Englewood Cliffs, N.J., 1972, pp. 1–30. ACM Transactions on Programming Languages and Systems, Vol. 13, No 2, April 1991.
  3. Allen, F. E. Interprocedural data flow analysis. Inf. Proc. 74 (1974), 398–402.
  4. Allen, F. E., Carter, J. L., Fabri, J., Ferrante, J., Harrison, W. H., Loewner, P. G., and Trevillyan, L. H. The experimental compiling system. IBM J. Res. Dev. 24, 6 (Nov. 1980), 695–715.
  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.
  6. Appel, A. W., and Jim, T. Continuation-passing, closure-passing style. In Conference Recordings of the Sixteenth ACM Symposium on Principles of Programming Languages. (Jan. 1989), pp. 293–302.
  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. 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.
  9. Barth, J. M. An interprocedural data flow analysis algorithm. In Conference Recordings of the Fourth ACM Symposium on Principles of Programming Languages. (Jan. 1977), pp. 119–131.
  10. Burke, M. An interval approach toward interprocedural analysis. Tech. Rep. RC 10640 47724, IBM, July 1984.
  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.
  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.
  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.
  14. Cocke, J. and Schwartz, T. Programming Languages and Their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York Univ., April 1970.
  15. Cooper, K. D. Interprocedural data flow analysis in a programming environment. Ph.D. thesis, Dept. of Mathematical Sciences, Rice Univ., 1983.
  16. Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., and Zadeck, F. K. Efficiently computing static single assignment form and the control dependence graph. Tech. Rep. RC 14756, IBM, revised Mar. 1991. Read it here
  17. Ellis, J. R. Bulldog: A compiler for VLIW architectures. Ph.D. thesis, Dept. of Computer Science, Yale Univ., New Haven, Conn., Feb. 1985.
  18. Ershov, A. P. On the essence of compilation. In IFIP Working Conference on Formal Description of Programming Concepts. (Aug. 1977).
  19. Ferrante, J. and Ottensstein, 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).
  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.
  21. Graham, S. L. and Wegman, M. N. A fast and usually linear algorithm for global flow analysis. J. ACM 23, 1 (Jan. 1976), 172–202.
  22. Harrison, W. H. Compiler analysis of the value ranges for variables. IEEE Trans. Softw. Eng. SE-3, 3 (May 1977), 243–250.
  23. Holley, L. H. and Rosen, B. K. Qualified data flow problems. IEEE Trans. Softw. Eng. SE-7, 1 (Jan. 1981), 60–78.
  24. Johnson, H. Dataflow analysis for intractable systems software. In Proceedings of the SIGPLAN’86 Symposium on Compiler Construction. (June 1986), pp. 109–117. Published as SIGPLAN Not. 21, 7.
  25. Kam, J. B. and Ullman, J. D. Monotone data flow analysis frameworks. Acta Inf. 7 (1977), 305–317.
  26. Kildall, G. A. A unified approach to global program optimization. In Conference Recordings of the First ACM Symposium on Principles of Programming Languages. (Oct. 1973), pp. 194–206.
  27. Morel, E. and Renvoise, C. Global optimization by suppression of partial redundancies. Commun. ACM 22, 2 (Feb. 1979), 96–103.
  28. Muchnick, S. S. and Jones, N. D, Eds. Program Flow Analysis. Prentice-Hall, Englewood Cliffs, N.J., 1981.
  29. Myers, E. W. A precise interprocedural data flow algorithm. In Conference Recordings of the Eighth ACM Symposium on Principles of Programming Languages. (Jan. 1981), pp. 219–230.
  30. Ottenstein, K. J. Data-flow graphs as an intermediate form. Ph.D. thesis, Dept. of Computer Science, Purdue Univ., Aug. 1978.
  31. Pratt, T. W. Program analysis and optimization through kernel-control decomposition. Acta Inf. 9 (1978), 195–216.
  32. Reif, J. H. and Lewis, H R Symbolic evaluation and the global value graph. In Conference Recordings of the Fourth ACM Symposium on Principles of Programming Languages. (Jan. 1977), pp. 104–118.
  33. Reif, J. H. and Lewis, H. R. Efficient symbolic analysis of programs J. Comput. Syst. Sci. 32, 3 (June 1986), 280–313.
  34. Reif, J. H. and Tarjan, R. E. Symbolic program analysis in almost linear time. SIAM J. Comput. 11, 1 (Feb. 1982), 81–93.
  35. Richardson, S. and Ganapathi, M. Interprocedural analysis vs. procedure integration. Inf. Process. Lett. 32, 3 (Aug. 1989), 137–142.
  36. Richardson, S. and Ganapathi, M. Code optimization across procedures. IEEE Comput. 22, 2 (Feb. 1989), 42–51.
  37. Rosen, B. K. Data flow analysis for procedural languages. J. ACM 26, 2 (April 1979), 322–344.
  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 Principles of Programming Languages. (Jan. 1988), pp. 12–27.
  39. Scheifler, R. W. An analysis of inline substitution for a structured programming language. Commun. ACM 20, 9 (Sept. 1977), 647–654.
  40. Shapiro, R. M. and Saint, H. The representation of algorithms. Tech. Rep. CA-7002-1432, Massachusetts Computer Associates, Feb. 1970.
  41. Tenenbaum, A. M. Type determination for very high level languages. Ph.D. thesis, Courant Institute of Mathematical Sciences, New York Univ., Oct. 1974.
  42. Wegbreit, B. Property extraction in well-founded property sets IEEE Trans. Softw. Eng SE-1, 3 (Sept 1975), 270–285.
  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.
  44. Wegman, M. N. and Zadeck, F. K. Constant propagation with conditional branches. In Conference Recordings of the Twelfth ACM Symposium on Principles of Programming Languages. (Jan. 1985), pp. 291–299. Received February 1988; revised June 1989; accepted October 1990

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.