The undecidability of aliasing

ABSTRACT

Alias analysis is a prerequisite for performing most of the common program analyses such as reaching-definitions analysis or live-variables analysis. Landi [1992] recently established that it is impossible to compute statically precise alias information—either may-alias or must-alias—in languages with if statements, loops, dynamic storage, and recursive data structures: more precisely, he showed that the may-alias relation is not recursive, while the must-alias relation is not even recursively enumerable. This article presents simpler proofs of the same results.

REFERENCES

• 1: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 2: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 3: KAM, J. B. AND ULLMAN, Z. D. 1977. Monotone data flow analysis frameworks. In Acta Informatica 7, 305-317.
• 4: William Landi, Undecidability of static analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.323-337, Dec. 1992 [doi>10.1145/161494.161501]
• 5: William Alexander Landi, Interprocedural aliasing in the presence of pointers, Rutgers University, New Brunswick, NJ, 1992
• 6: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
• 7: James Richard Larus , Paul Hifinger, Restructuring symbolic programs for concurrent execution on multiprocessors, 1989
• 8: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, ACM SIGPLAN Notices, v.23 n.7, p.24-31, July 1988
• 9: 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]
• 10: Phillip Edward Pfeiffer, IV, Dependence-based representations for programs with reference variables, University of Wisconsin at Madison, Madison, WI, 1992

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.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory
      F.4.3 Formal Languages
          Subjects: Decision problems

General Terms:
Languages, Theory

Keywords:
alias analysis, pointer analysis