Constant Propagation with Conditional Branches

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

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

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.

虽然通常很容易证明常量传播问题是不可判定的（例如参见 Kam 和 Ullman [25]），但该问题存在许多合理的实例，它们是可判定的，并且存在计算效率较高的算法。我们在本文中给出了四种这样的算法。这里给出的每个算法都是保守的，即可能无法找到所有常量，但找到的每个常量在程序的所有可能执行中都是常量。

在介绍了一些预备知识之后，我们在第 3 节中按照能力递增的顺序介绍这些算法；每个后续算法至少能找到前一个算法所找到的常量。前三种算法是对他人工作的重新表述；第四种算法是新的，并包含前三种算法各自的最佳特性。这些算法属于已知的最简单、最快且功能最强大的全局常量传播算法之列。在第 4 节中，我们证明了我们的算法是正确的，并且至少与具有多项式时间界的最佳已有算法一样强大。在第 5 节中，我们讨论了一些常见的实现问题。

在第 6 节中，我们探索了若干种在大于单个过程的范围内执行常量传播的技术。在第 6.2 节中，我们讨论了常量传播与过程集成之间的关系。第 6.3 节给出了一种新的算法，该算法执行一种形式的过程间数据流分析，其中别名信息与常量传播结合收集。

第 7 节概述了一些开放问题，第 8 节总结了本文。

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 中文 by gpt-5, against glossary version 6. Translated from the English.