Analyzing aliases of reference formal parameters

ABSTRACT

Compilers for languages with call-by-reference formal parameters must deal with aliases arising from the renaming effects at call sites. This paper presents a set of techniques for analyzing aliasing patterns. The analysis is divided into detecting the introduction of aliases and tracking their propagation. The algorithm for introduction analysis is simple enough to be performed in a structured editor or parser. A data flow analysis framework is given for the propagation problem, making it possible to solve using standard algorithms from global data flow analysis. Several optimizations are shown which can shrink the size of the problem, and extensions are given to handle ALGOL-style name scoping. Finally, this technique is compared to an alternative implementation strategy and an approximate technique.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: [Alle] F. Allen, J. Carter, J. Fabri, J. Ferrante, W. Harrison, P. Loewner. L. Trevillyan, "The Experimental Compiling System", IBM Journal of Research and Development, Vol. 24, No. 6, Nov. 1980.
• 3: [ANSI] ANSI, American National Standard FORTRAN-66 X3.9-1966.
• 4: John Phineas Banning, A method for determining the side effects of procedure calls., Stanford University, Stanford, CA, 1978
• 5: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 6: Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.247-258, June 17-22, 1984, Montreal, Canada
• 7: Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, Rice University, Houston, TX, 1983
• 8: [HoKe] R. Hood, and K. Kennedy, "A Programming Environment for Fortran". Rice University, Department of Mathematical Sciences TR84-1, Rice University, 1984. (to appear in the proceedings of the Eighteenth Annual Hawaii International Conference on Systems Sciences, January, 1985).
• 9: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 10: [Myer] E. Myers, "A Precise and Efficient Algorithm for Determining Existential Summary Data Flow Information", University of Colorado at Boulder, Department of Computer Science Technical Report #CU-CS-175-80.
• 11: George Paul, Directions and Trends in FORTRAN, Programmiersprachen und Programmentwicklung, 7. Fachtagung, veranstaltet vom Fachausschuß 2 der GI, p.32, March 09-10, 1982
• 12: [Spil] T. Spillman, "Exposing Side-Effects in a PL/I Optimizing Compiler", IFIPS Proceedings, 1971, pp 376-381.
• 13: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Algorithms, Design, Languages, Performance, Theory