Extended SSA numbering: introducing SSA properties to languages with multi-level pointers

ABSTRACT

Static Single Assignment (SSA) intermediate representations have become quite popular in compiler development. One advantage of the SSA form is that each variable corresponds to exactly one definition, and thus two references of the same SSA variable must denote the same value. To date, most SSA forms concentrate on scalar variables, and it is difficult to extend these intermediate representations to languages with multi-level pointers, such as C.We introduce Extended SSA Numbering analysis, which concentrates on the "same name, same definition" properties of SSA form while compromising on other aspects. What is not provided is well compensated for by new properties introduced for pointer references such as *p. Two references of *p with the same Extended SSA numbers denote the same value.

REFERENCES

• 1: 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]
• 2: Marc M. Brandis , Hanspeter Mössenböck, Single-pass generation of static single-assignment form for structured languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1684-1698, Nov. 1994 [doi>10.1145/197320.197331]
• 3: 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]
• 4: 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]
• 5: Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.36-45, June 21-25, 1993, Albuquerque, New Mexico, United States
• 6: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 7: {7} Ana M. Erosa and Laurie J. Hendren. Taming control flow: A structured approach to eliminating goto statements. In Proc. of the 1994 Intl. Conf. on Computer Languages, pages 229-240, Toulouse, France, May 1994.
• 8: {8} Ana Marie Erosa. A goto-elimination method and its implementation for the McCAT C compiler. Master's thesis, McGill U., Montréal, Qué., May 1995.
• 9: Laurie J. Hendren , C. Donawa , Maryam Emami , Guang R. Gao , Justiani , B. Sridharan, Designing the McCAT Compiler Based on a Family of Structured Intermediate Representations, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.406-420, August 03-05, 1992
• 10: Justiani , Laurie J. Hendren, Supporting Array Dependence Testing for an Optimizing/Parallelizing C Compiler, Proceedings of the 5th International Conference on Compiler Construction, p.309-323, April 07-09, 1994
• 11: {11} Christopher Lapkowski and Laurie J. Hendren. Extended SSA numbering: Introducing SSA properties to languages with multi-level pointers. ACAPS Tech. Memo 102, Sch. of Comp. Sci., McGill U., Montréal, Qué., Apr. 1996. In ftp://ftp-acaps.cs.mcgill.ca/pub/doc/memos.
• 12: 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]
• 13: 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]
• 14: Michael Wolfe, Beyond induction variables, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.162-174, June 15-19, 1992, San Francisco, California, United States

INDEX TERMS

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

General Terms:
Algorithms, Design, Languages, Theory