Using static single assignment form in a code optimizer

ABSTRACT

Static single assignment form represents data dependences elegantly and provides a basis for powerful optimizations. Table-driven techniques for peephole optimization and code generation are straightforward and effective. it is natural to want to use both together in a code optimizer. However, doing so reveals that static single assignment form does not remove all antidependences, and that it conflicts with table-driven code generation for 2-address machines. This paper describes these problems and how to solve them.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 2: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 3: CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, P.W. Register allocation via coloring. Comput. Lang. 6, 1 (1981), 47-57.
• 4: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 5: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 6: Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512651]
• 7: Jack Winfred Davidson, Simplifying code generation through peephole optimization, 1981
• 8: Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
• 9: Jack W. Davidson , Christopher W. Fraser, The Design and Application of a Retargetable Peephole Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.191-202, April 1980 [doi>10.1145/357094.357098]
• 10: M. Ganapathi , C. N. Fischer, Integrating code generation and peephole optimization, Acta Informatica, v.25 n.1, p.85-109, January 1988 [doi>10.1007/BF00268846]
• 11: Mahadevan Ganapathi , Charles N. Fischer , John L. Hennessy, Retargetable Compiler Code Generation, ACM Computing Surveys (CSUR), v.14 n.4, p.573-592, Dec. 1982 [doi>10.1145/356893.356897]
• 12: R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
• 13: GRAHAM, S.L. Table-driven code generation. IEEE Comput. 13, 8 (1980), 25-34.
• 14: Susan L. Graham , Robert R. Henry , Robert A. Schulman, An experiment in table driven code generation, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.32-43, June 23-25, 1982, Boston, Massachusetts, United States
• 15: Kurt Joseph Hebel, An environment for the development of digital signal processing software, 1989
• 16: Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, ACM SIGPLAN Notices, v.23 n.11, p.18-26, Nov. 1988
• 17: JOHNSON, R. E., MCCONNELL, C., AND LAKE, J.M. The RTL system: A framework for code optimization. Tech. Rep. UIUCDCS-R-9-1698, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, 1991.
• 18: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 19: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 20: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 21: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation

General Terms:
Algorithms, Design

Keywords:
data dependence, peephole optimization, register allocation, static single assignment form