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 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

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

Thuật ngữ chung: Thuật toán, Ngôn ngữ Các từ khóa và cụm từ bổ sung: Phụ thuộc điều khiển, đồ thị luồng điều khiển, chuỗi def-use, nút chi phối, các trình biên dịch tối ưu hóa

Trong các trình biên dịch tối ưu hóa, lựa chọn cấu trúc dữ liệu ảnh hưởng trực tiếp đến sức mạnh và hiệu quả của tối ưu hóa chương trình thực tế. Một lựa chọn cấu trúc dữ liệu kém có thể cản trở tối ưu hóa hoặc làm chậm quá trình biên dịch đến mức các tính năng tối ưu hóa nâng cao trở nên không mong muốn. Gần đây, dạng gán đơn tĩnh (static single assignment) (SSA) [5, 43] và đồ thị phụ thuộc điều khiển (control dependence graph) [24] đã được đề xuất để biểu diễn các thuộc tính luồng dữ liệu và luồng điều khiển của các chương trình. Mỗi kỹ thuật trước đây không liên quan này đều mang lại hiệu quả và sức mạnh cho một lớp hữu ích các tối ưu hóa chương trình. Mặc dù cả hai cấu trúc này đều hấp dẫn, khó khăn trong việc xây dựng chúng và kích thước tiềm năng của chúng đã cản trở việc sử dụng chúng [4]. Chúng tôi trình bày các thuật toán mới có thể tính toán hiệu quả các cấu trúc dữ liệu này cho các đồ thị luồng điều khiển tùy ý. Các thuật toán sử dụng các biên chi phối (dominance frontiers), một khái niệm mới có thể có các ứng dụng khác. Chúng tôi cũng đưa ra bằng chứng phân tích và thực nghiệm rằng tổng kích thước của tất cả các biên chi phối thường là tuyến tính theo kích thước của chương trình ban đầu. Do đó, bài báo này đưa ra bằng chứng mạnh mẽ rằng dạng SSA và các phụ thuộc điều khiển có thể có ích trong thực tế cho tối ưu hóa.

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