Constant Propagation with Conditional Branches

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

About this paperEnglish中文日本語beside Englishbeside 中文beside 日本語

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.

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.

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. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.