Static single assignment form for machine code

ABSTRACT

Static Single Assignment (SSA) is an effective intermediate representation in optimizing compilers. However, traditional SSA form and optimizations are not applicable to programs represented as native machine instructions because the use of dedicated registers imposed by calling conventions, the runtime system, and target architecture must be made explicit. We present a simple scheme for converting between programs in machine code and in SSA, such that references to dedicated physical registers in machine code are preserved. Our scheme ignores all output- and anti-dependences imposed by physical registers while a program is in SSA form, but inserts compensation code during machine code reconstruction if any naming requirements have been violated. By resolving all mismatches between the two representations in separate phases, we are able to utilize existing SSA algorithms unaltered to perform machine code optimizations.

REFERENCES

• AM91a: A. Appel and D. MacQueen. Standard ML of New Jersey. Third Int'l Syrup. on Prog. Lang. Implementation and Logic Programming, 1991.
• AM91b: Andrew W. Appel and David B. MacQueen. Standard ML of NewJersey. In Martin Wirsing, editor, Third Int'l Syrup. on Prog. Lang. Implementation and Logic Programming, New York, August 1991. Springer-Verlag.
• App92: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• BCHS88: Preston Briggs , Keith D. Cooper , Timothy J. Harvey , L. Taylor Simpson, Practical improvements to the construction and destruction of static single assignment form, Software—Practice & Experience, v.28 n.8, p.859-881, July 10, 1998 [doi>10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8]
• BL93: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• CCF91: 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]
• CCK+97: Fred Chow , Sun Chan , Robert Kennedy , Shin-Ming Liu , Raymond Lo , Peng Tu, A new algorithm for partial redundancy elimination based on SSA form, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.273-286, June 16-18, 1997, Las Vegas, Nevada, United States
• CCL+96: Fred C. Chow , Sun Chan , Shin-Ming Liu , Raymond Lo , Mark Streich, Effective Representation of Aliases and Indirect Memory Operations in SSA Form, Proceedings of the 6th International Conference on Compiler Construction, p.253-267, April 24-26, 1996
• CFR+89: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• CKB93: Philip L. Campbell, Ksheerabdhi Krishna, and Robert A. Ballance. Refining and defming the program dependence web. Technical Report CS93-6, University of New Mexico, Albuquerque, March 1993.
• Cli95: Cliff Click, Global code motion/global value numbering, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.246-257, June 18-21, 1995, La Jolla, California, United States
• CS95: Keith Cooper and Taylor Simpson. SCC-based value numbering. Technical Report CRPC- TR95636-S, Center for Research on Parallel Computation, Rice University, October 1995.
• CSV95: Keith Cooper, Taylor Simpson, and Christopher A. Vick. Operator strength reduction. Technical Report CRPC-TR95635-S, Center for Research on Parallel Computation, Rice University, October 1995.
• GA96: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• Geo97: Lal George. Mlrisc: Customizable and reusable code generators (http://cm. bell-labs, com/cm/c s/ what/smlnj/doc/mlrisc/index, html). Technical report, Bell Laboratories, Murray Hill, 1997.
• Hew94: Hewlett Packard. PA-RISC 1.1 Architecture and Instruction Set, 3rd Edition, 1994.
• HMM86: Robert Harper, David MacQueen, and Robin Milner. Standard ML. Report ECS-LFCS-86- 2, Laboratory for Foundations of Computer Science, Computer Science Department, Edinburgh University, 1986.
• KRS94: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• MJ92: Carl McConnell , Ralph E. Johnson, Using static single assignment form in a code optimizer, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.152-160, June 1992 [doi>10.1145/151333.151368]
• RWZ88: 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]
• SG95: Vugranam C. Sreedhar , Guang R. Gao, A linear time algorithm for placing &phgr;-nodes, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.62-73, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199464]
• WCES94: Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177907]
• Wol96: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• WZ91: 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: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General
          Subjects: Standards
      D.3.4 Processors
          Subjects: Optimization; Code generation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Standardization, Theory