Retargetable high-level alias analysis

ABSTRACT

All optimizing compilers must deal with the problem of aliases arising due to the presence of multiple names that reference the same memory areas. Presented in this paper is a staged, high-level alias analysis methodology that provides detailed alias information to a global optimizer implemented at any level in the compilation process. The framework provides easy portability of optimizing compilers to new architectures, as well as the easy addition, of new compilers to an already existing family of optimizing compilers. The method involves the application of a set of language-specific alias rules to the source code in order to gather alias information. A language-independent component then performs a transitive closure of this information and transforms it into a presentation more suitable for use by a global optimizer. Each stage of the methodology is detailed. Results are given for an implemented family of compilers targeted for a reduced instruction set computer.

REFERENCES

• 1: A. V. Aho and J. D. Ullman, <i>Principles of Compiler Design,</i> Addison Wesley, Reading, MA, 1977.
• 2: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 3: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 4: J. S. Birnbaum and W. S. Worley, Jr., "Beyond RISC: High Precision Architecture," <i>Hewlett-Packard Journal</i> <b>36</b>, 8 (August 1985), 4--10.
• 5: Jeffrey M. Barth, An interprocedural data flow analysis algorithm, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-131, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512962]
• 6: W. Bright, <i>Official Correspondence X3J11/84-210,</i> American National Standards Committee, Dec. 1984.
• 7: Anita L. Chow , Andres Rudmik, The design of a data flow analyzer, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.106-113, June 23-25, 1982, Boston, Massachusetts, United States
• 8: Keith D. Cooper, Analyzing aliases of reference formal parameters, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.281-290, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318658]
• 9: P. Gerring, P. Nye, A. Rodriquez and A. Samuel, "A Universal P-Code for the S-1 Project," CSL Technical Note 159, Stanford University, Aug. 1979.
• 10: 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]
• 11: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 12: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 13: David A. Patterson, Reduced instruction set computers, Communications of the ACM, v.28 n.1, p.8-21, Jan. 1985 [doi>10.1145/2465.214917]
• 14: D. R. Perkins and R. L. Sites, "Universal P-Code Definition Version {0.3}," Applied Physics and Information Science Document UCSD/CS-79/037. University of California at San Diego, July 1979.
• 15: T. Plum, <i>Official Correspondence X3J11/85--001.</i> American National Standards Committee, Jan. 1985.
• 16: T. C. Spillman, "Exposing Side-Effects in a PL/1 Optimizing Compiler," <i>Proc. IFIP Conf. 1971,</i> North Holland Publishing Company, Amsterdam, 376--381.
• 17: 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]