Efficiently Computing Static Single Assignment Form and the Control Dependence Graph

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck, 1991, ACM TOPLAS

About this paperTiếng Việt

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
日本語

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization. A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable. Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow properties of programs. Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimizations. Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use. We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs. The algorithms use dominance frontiers, a new concept that may have other applications. We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program. This paper thus presents strong evidence that these structures can be of practical use in optimization.

Categories and Subject Descriptors: D.3.3 [Programming Languages]: Language Constructs—control structures; data types and structures; procedures, functions and subroutines; D.3.4 [Programming Languages]: Processors—compilers; optimization; I.1.2 [Algebraic Manipulation]: Algorithms—analysis of algorithms; I.2.2 [Artificial Intelligence]: Automatic Programming—program transformation

A preliminary version of this paper, “An Efficient Method of Computing Static Single Assignment Form,” appeared in the Conference Record of the 16th ACM Symposium on Principles of Programming Languages (Jan. 1989). F. K. Zadeck’s work on this paper was partially supported by the IBM Corporation, the Office of Naval Research, and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA order 6320, Amendment 1. Authors’ addresses: R. Cytron, J. Ferrante, and M. N. Wegman, Computer Sciences Department, IBM Research Division, P. O. Box 704, Yorktown Heights, NY 10598; B. K. Rosen, Mathematical Sciences Department, IBM Research Division, P. O. Box 218, Yorktown Heights, NY 10598; F. K. Zadeck, Computer Science Department, P.O. Box 1910, Brown University, Providence, RI 02912. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1991 ACM 0164-0925/91/1000-0451 \$01.50

General Terms: Algorithms, Languages Additional Key Words and Phrases: Control dependence, control flow graph, def-use chain, dominator, optimizing compilers

一般用語：アルゴリズム、言語 追加キーワードおよびフレーズ：制御依存関係、制御フローグラフ、定義使用チェーン、支配者、最適化コンパイラ

最適化コンパイラにおいて、データ構造の選択は、実用的なプログラム最適化の能力と効率に直接影響を与える。データ構造の選択を誤ると、最適化が妨げられたり、コンパイルが遅くなったりして、高度な最適化機能が望ましくないものとなる可能性がある。近年、静的単一代入形式 (SSA) [5, 43] と制御依存グラフ [24] が、プログラムのデータフローおよび制御フローの特性を表現するために提案されている。これらの、従来は互いに関連していなかった技法は、それぞれ有用なプログラム最適化の一群に効率性と能力をもたらす。これら2つの構造はいずれも魅力的であるが、その構築の困難さと潜在的なサイズが、その利用を妨げてきた [4]。本論文では、任意の制御フローグラフに対してこれらのデータ構造を効率的に計算する新しいアルゴリズムを提示する。これらのアルゴリズムは、他の応用にも利用できる可能性のある新しい概念である支配フロンティアを用いる。また、すべての支配フロンティアのサイズの総和が、通常、元のプログラムのサイズに対して線形であることを示す解析的および実験的な証拠も提示する。したがって本論文は、SSA形式と制御依存関係が最適化において実用的に利用できることを示す強力な証拠を提示する。

1 INTRODUCTION

This section is missing here.

2 CONTROL FLOW GRAPHS

This section is missing here.

3 STATIC SINGLE ASSIGNMENT FORM

This section is missing here.

4 DOMINANCE

This section is missing here.

5 CONSTRUCTION OF MINIMAL SSA FORM

This section is missing here.

6 CONSTRUCTION OF CONTROL DEPENDENCIES

This section is missing here.

7 TRANSLATING FROM SSA FORM

This section is missing here.

8 ANALYSIS AND MEASUREMENTS

This section is missing here.

9 DISCUSSION

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., Burke, M., Charles, P., Cytron, R., and Ferrante, J An overview of the PTRAN analysis system for multiprocessing. J. Parallel Distrib. Comput. 5, (Oct. 1988), 617–640.
  3. Allen, J. R Dependence analysis for subscripted variables and its application to program transformations. Ph.D. thesis, Department of Computer Science, Rice Univ., Houston, Tex., Apr. 1983.
  4. Allen, J R , and Johnson, S Compiling C for vectorization, parallelization and inline expansion. In Proceedings of the SIGPLAN '88 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 23, 7 (June 1988), 241–249
  5. Alpern, B , Wegman, M. N., and Zadeck, F. K. Detecting equality of values in programs In Conference Record of the 15th ACM Symposium on Principles of Programming Languages (Jan. 1988), ACM, New York, pp. 1–11.
  6. Ballance, R. A., MacCabe, A. B., and Ottensstein, K. J. The program dependence web: A representation supporting control-, data-, and demand driven interpretation of languages. In Proceedings of the SIGPLAN 90 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 25, 6 (June 1990), 257–271.
  7. Banning, J. B. An efficient way to find the side effects of procedure calls and the aliases of variables. In Conference Record of the 6th ACM Symposium on Principles of Programming Languages (Jan. 1979) ACM, New York, pp. 29–41
  8. Barth, J. M. An interprocedural data flow analysis algorithm. In Conference Record of the 4th ACM Symposium on Principles of Programming Languages (Jan. 1977) ACM, New York: pp. 119–131.
  9. Burke, M. An interval-based approach to exhaustive and incremental interprocedural data flow analysis. ACM Trans. Program Lang. Syst. 12, 3 (July 1990), 341–395.
  10. Burke, M., and Cytron, R. Interprocedural dependence analysis and parallelization. In Proceedings of the SIGPLAN 86 Symposium on Compiler Construction SIGPLAN Not (ACM) 21, 7 (June 1986), 162–175. ACM Transactions on Programming Languages and Systems, Vol. 13, No. 4, October 1991 Static Single Assignment Form and the Control Dependence Graph • 489
  11. Cartwright, R., and Felleisen, M. The semantics of program dependence. In *Proceedings of the SIGPLAN'89 Symposium on Compiler Construction. SIGPLAN Not. (ACM)* 24, 7 (July 1989), 13–27.
  12. Chaitin, G. J. Register allocation and spilling via graph coloring. In *Proceedings of the SIGPLAN '82 Symposium on Compiler Construction. SIGPLAN Not. (ACM)* 17, 6 (June 1982), 98–105.
  13. Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Markstein, P. W. Register allocation via coloring. *Computer Lang.* 6 (1981), 47–57.
  14. Chase, D. R. Safety considerations for storage allocation optimizations. In *Proceedings of the SIGPLAN'88 Symposium on Compiler Construction. SIGPLAN Not. (ACM)* 23, 7 (June 1988), 1–10.
  15. Chase, D. R., Wegman, M. and Zadeck, F. K. Analysis of pointers and structures. In *Proceedings of the SIGPLAN 90 Symposium on Compiler Construction. SIGPLAN Not. (ACM)* 25, 6 (June 1990), 296–310.
  16. Choi, J., Cytron, R., and Ferrante, J. Automatic construction of sparse data flow evaluation graphs. In *Conference Record of the 18th ACM Symposium on Principles of Programming Languages* (Jan. 1991). ACM, New York, pp. 55–66.
  17. Chow, F. C. A portable machine-independent global optimizer—Design and measurements. Ph.D. thesis and Tech. Rep. 83-254, Computer Systems Laboratory, Stanford Univ., Stanford, Calif., Dec. 1983.
  18. Chow, F. C., and Hennessy, J. L. The priority-based coloring approach to register allocation. *ACM Trans. Program. Lang. Syst.* 12, 4 (Oct. 1990), 501–536.
  19. Cooper, K. D. Interprocedural data flow analysis in a programming environment. Ph.D. thesis, Dept. of Mathematical Sciences, Rice Univ., Houston, Tex., 1983.
  20. Cytron, R., and Ferrante, J. An improved control dependence algorithm. Tech. Rep. RC 13291, IBM Corp., Armonk, N.Y., 1987.
  21. Cytron, R., and Ferrante, J. What's in a name? In *Proceedings of the 1987 International Conference on Parallel Processing* (Aug. 1987), pp. 19–27.
  22. Cytron, R., Lowry, A., and Zadeck, F. K. Code motion of control structures in high-level languages. In *Conference Record of the 13th ACM Symposium on Principles of Programming Languages* (Jan. 1986). ACM, New York, pp. 70–85.
  23. Dennis, J. B. First version of a data flow procedure language. Tech. Rep. Comput. Struc. Group Memo 93 (MAC Tech. Memo 61), MIT, Cambridge, Mass., May 1975.
  24. Ferrante, J., Ottenstein, K. J., and Warren, J. D. The program dependence graph and its use in optimization. *ACM Trans. Program. Lang. Syst.* 9, 3 (July 1987), 319–349.
  25. Giegerich, R. A formal framework for the derivation of machine-specific optimizers. *ACM Trans. Program. Lang. Syst.* 5, 3 (July 1983), 478–498.
  26. Harel, D. A linear time algorithm for finding dominators in flow graphs and related problems. In *Proceedings of the 17th ACM Symposium on Theory of Computing* (May 1985). ACM, New York, pp. 185–194.
  27. Horwitz, S., Pfeiffer, P., and Reps, T. Dependence analysis for pointer variables. In *Proceedings of the SIGPLAN 89 Symposium on Compiler Construction. SIGPLAN Not. (ACM)* 24, 7 (June 1989).
  28. Horwitz, S., Prins, J., and Reps, T. Integrating non-interfering versions of programs. *ACM Trans. Program. Lang. Syst.* 11, 3 (July 1989), 345–387.
  29. Jones, N. D., and Muchnick, S. S. Flow analysis and optimization of LISP-like structures. In *Program Flow Analysis*, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, N.J., 1981, chap. 4, pp. 102–131.
  30. Kennedy, K. W. Global dead computation elimination. Tech. Rep. SETL Newsl. 111, Courant Institute of Mathematical Sciences, New York Univ., New York, N.Y., Aug. 1973.
  31. Kennedy, K. W. A survey of data flow analysis techniques. In *Program Flow Analysis*, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, N.J., 1981.
  32. Kuck, D. J. *The Structure of Computers and Computations.* Wiley, New York, 1978.
  33. Larus, J. R. Restructuring symbolic programs for concurrent execution on multiprocessors. Tech. Rep. UCB/CSD 89/502, Computer Science Dept., Univ. of California at Berkeley, Berkeley, Calif., May 1989. ACM Transactions on Programming Languages and Systems, Vol. 13, No. 4, October 1991. 490 • Ron Cytron et al.
  34. Larus, J. R., and Hilfinger, P. N. Detecting conflicts between structure accesses. In *Proceedings of the ACM SIGPLAN 88 Symposium on Compiler Construction*. SIGPLAN Not. 23, 7 (July 1988), 21–34.
  35. Lengauer, T., and Tarjan, R. E. A fast algorithm for finding dominators in a flowgraph. *ACM Trans. Program. Lang. Syst.* 1, 1 (July 1979), 121–141.
  36. Muchnick, S. S., and Jones, N. D., Eds. *Program Flow Analysis*. Prentice-Hall, Englewood Cliffs, N.J., 1981.
  37. Myers, E. W. A precise interprocedural data flow algorithm. In *Conference Record of the 8th ACM Symposium on Principles of Programming Languages* (Jan. 1981). ACM, New York, pp. 219–230.
  38. Ottenstein, K. J. Data-flow graphs as an intermediate form. Ph.D. thesis, Dept. of Computer Science, Purdue Univ., W. Lafayette, Ind., Aug. 1978.
  39. Pointer, L. Perfect report: 1. Tech. Rep CSR D 896, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana-Champaign, Urbana, Ill., July 1989.
  40. Reif, J. H., and Lewis, H. R. Efficient symbolic analysis of programs. *J. Comput. Syst. Sci.* 32, 3 (June 1986), 280–313.
  41. Reif, J. H., and Tarjan, R. E. Symbolic program analysis in almost linear time. *SIAM J. Comput.* 11, 1 (Feb. 1982), 81–93.
  42. Rosen, B. K. Data flow analysis for procedural languages. *J. ACM* 26, 2 (Apr. 1979), 322–344.
  43. Rosen, B. K., Wegman, M. N., and Zadeck, F. K. Global value numbers and redundant computations. In *Conference Record of the 15th ACM Symposium on Principles of Programming Languages* (Jan. 1988). ACM, New York, pp. 12–27.
  44. Ruggieri, C., and Murtagh, T. P. Lifetime analysis of dynamically allocated objects. In *Conference Record of the 15th ACM Symposium on Principles of Programming Languages* (Jan. 1988). ACM, New York, pp. 285–293.
  45. Shapiro, R. M., and Saint, H. The representation of algorithms. Tech. Rep. CA-7002-1432, Massachusetts Computer Associates, Feb. 1970.
  46. Smith, B. T., Boyle, J. M., Dongarra, J. J., Garbow, B. S., Ikebe, Y., Klema, V. C., and Moler, C. B. *Matrix Eigensystem Routines – Eispack Guide*. Springer-Verlag, New York, 1976.
  47. Tarjan, R. E. Finding dominators in directed graphs. *SIAM J. Comput.* 3, 1 (1974), 62–89.
  48. Wegbreit, B. Property extraction in well-founded property sets. *IEEE Trans. Softw. Eng.* SE-1, 3 (Sept. 1975), 270–285.
  49. Wegman, M. N., and Zadeck, F. K. Constant propagation with conditional branches. In *Conference Record of the 12th ACM Symposium on Principles of Programming Languages* (Jan.). ACM, New York, pp. 291–299.
  50. Wegman, M. N., and Zadeck, F. K. Constant propagation with conditional branches. *ACM Trans. Program. Lang. Syst.* To be published.
  51. Wolfe, M. J. Optimizing supercompilers for supercomputers. Ph.D. thesis, Dept of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana Ill., 1982.
  52. Yang, W., Horwitz, S., and Reps, T. Detecting program components with equivalent behaviors. Tech. Rep. 840. Dept. of Computer Science, Univ. of Wisconsin at Madison, Madison, Apr. 1989. Received July 1989; revised March 1991; accepted March 1991 ACM Transactions on Programming Languages and Systems, Vol 13, No 4, October 1991.

Read off the page by a vision model reading the page images using gpt-5.

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.