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] を参照）が、この問題の妥当なインスタンスの多くは決定可能であり、計算効率のよいアルゴリズムが存在する。本論文では、そのような4つのアルゴリズムを提示する。ここで提示する各アルゴリズムは、すべての定数が発見されるとは限らないという意味で保守的であるが、発見された各定数はプログラムのすべての可能な実行にわたって定数である。

いくつかの予備事項の後、アルゴリズムは能力が増加する順にSection 3で提示される。後続する各アルゴリズムは、少なくとも直前のアルゴリズムで発見された定数を発見する。最初の3つのアルゴリズムは他者の研究の再定式化であり、4つ目は新規で、先行する3つのそれぞれの最良の特徴を含んでいる。これらのアルゴリズムは、既知のグローバル定数伝播アルゴリズムの中でも最も単純で高速かつ強力なものの一つである。Section 4では、本アルゴリズムが正しく、かつ多項式時間の上界を持つ従来の最良のアルゴリズムと少なくとも同等の能力を持つことが証明される。Section 5では、一般的な実装上の問題について議論する。

Section 6では、単一の手続きよりも広い領域にわたって定数伝播を実行するためのいくつかの技法を検討する。Section 6.2では、定数伝播と手続き統合の関係について議論する。Section 6.3では、定数伝播と併せてエイリアシング情報を収集する、インタープロシージャ間データフロー解析の一形態を実行する新しいアルゴリズムを示す。

Section 7ではいくつかの未解決問題を概説し、Section 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.