G. Ramalingam
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.
- CHOI, J.-D., BURKE, M. G. AND CARINI, P. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the 20th ACM Symposium on Principles of Programming Languages (Charleston, S. Carolina). ACM, New York, 232-245. Google Scholar
- HOPCROFT, J. E. AND ULLMAN, J.D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass. Google Scholar
- KAM, J. B. AND ULLMAN, Z. D. 1977. Monotone data flow analysis frameworks. In Acta Informatica 7, 305-317.Google Scholar
- LANDI, W. 1992. Undecidability of static analysis. 1992. Lett. Program. Lang. Syst. 1, 4 (Dec.). Google Scholar
- LANDI, W. 1991. Interprocedural aliasing in the presence of pointers. Ph.D. thesis, Dept. of Computer Science, Rutgers Univ., New Brunswick, N.J. Google Scholar
- LANDI, W. AND RYDER, B.G. 1992. A safe approximate algorithm for pointer-induced aliasing. SIGPLAN Not. 27, 7 (July), 235-248. Google Scholar
- LARUS, J.R. 1989. Restructuring symbolic programs for concurrent execution on multiprocessors. Ph.D. thesis, Univ. of California, Berkeley, Calif. (May). Google Scholar
- LARUS, J. R. AND HILFINGER, P. N.1988. Detecting conflicts between structure accesses. SIGPLAN Not. 23, 7 (July), 21-34. Google Scholar
- MYERS, E. 1981. A precise inter-procedural data flow algorithm. In Conference Record of the 8th ACM Symposium on Principles of Programming Languages (Williamsburg, Va., Jan. 26-28). ACM, New York. Google Scholar
- PFEIFFER, P. 1991. Dependence-based representations for programs with reference variables. Ph.D. dissertation and Tech. Rep. TR-1037, Computer Sciences Dept., Univ. of Wisconsin, Madison, Wis. (Aug.). Google Scholar
Index Terms
- The undecidability of aliasing
Recommendations
Precise flow-insensitive may-alias analysis is NP-hard
Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...
Undecidability of static analysis
Static analysis of programs is indispensable to any software tool, environment, or system that requires compile-time information about the semantics of programs. With the emergence of languages like C and LISP, static analysis of programs with dynamic ...
Semi-sparse flow-sensitive pointer analysis
POPL '09Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...
Reviews
Danny B. Lange
Common static program analyses such as reaching-definition analysis and live-variables analysis require alias information. Two names (L-valued expressions) are said to alias each other at a particular point during program execution if both may, or must, have the same value. Landi [1] recently established that “may” and “must” alias problems are undecidable for languages that permit “if” statements, loops, dynamic storage, and recursive data structures. Ramalingam presents a simpler and very elegant proof of the same result. The approach taken is to reduce Post's Correspondence Problem (PCP), which is undecidable, to the “may” and “must” alias problems. The proof is supported by a program example in C. I f you are working in the field of static program analysis, be sure to take a look at this short and easy-to-read paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments