Susan Horwitz
Abstract
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. Previous work has investigated the complexity of flow-sensitive alias analysis. In this article we show that precise flow-insensitive may-alias analysis is NP-hard given arbitrary levels of pointers and arbitrary pointer dereferencing.
- ANDERSEN, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis, DIKU Rep. 94/19, DIKU, Univ. of Copenhagen, Denmark.Google Scholar
- BURKE, M., CARINI, P., CHOI, J., AND HIND, M. 1994. Flow-insensitive interprocedural alias analysis in the presence of pointers. In Languages and Compilers for Parallel Computing: Proceedings of the 7th International Workshop, K. Pingali, U. Banerjee, D. Galernter, A. Nicolau, and D. Padua, Eds. Lecture Notes in Computer Science, vol. 892. Springer-Verlag, Berlin, 234-250. Google Scholar
- GAREY, M. AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Google Scholar
- LANDI, W. 1992. Undecidability of static analysis. ACM Lett. Program. Lang. Syst. 1, 4, 323-337. Google Scholar
- LANDI, W. AND RYDER, B. 1991. Pointer induced aliasing: A problem classification. In the ACM Symposium on Principles of Programming Languages. ACM, New York, 93-103. Google Scholar
- RAMALINGAM, G. 1994. The undecidability of aliasing. ACM Trans. Program. Lang. Syst. 16, 5, 1467-1471. Google Scholar
- STEENSGAARD, B. 1996. Points-to analysis in almost linear time. In the ACM Symposium on Principles of Programming Languages. ACM, New York, 32-41. Google Scholar
Index Terms
- Precise flow-insensitive may-alias analysis is NP-hard
Recommendations
Demand-driven alias analysis for C
POPL '08This paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. ...
Demand-driven alias analysis for C
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThis paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. ...
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
Max Hailperin
Horwitz show a problem to be NP-hard that several researchers have recently attacked with polynomial-time algorithms for generating imprecise solutions . Imprecise solutions here mean those that may err, but only in a conservative direction. For the may-alias problem, the conservative direction of error is to report that a pair of expressions may be aliased that in fact cannot be. Horwitz thereby provides a rational explanation for this existing research focus. The flow-insensitive may-alias problem is to determine, given a set of programming language statements and a pair of expressions, whether there is any sequence of statements from the set that results in the expressions being aliases, that is, references to the same memory location. Horwitz addresses this problem for a simple language of assignment statements with arbitrarily nested pointer dereferencing. The only kind of statement in this language assigns an expression's value to an identifier. There are two kinds of expressions: either the address-of operator applied to an identifier, or zero or more pointer dereference operators applied to an identifier. Horwitz's proof is straightforward, consisting of a simple reduction from the Hamiltonian path problem. The paper concludes with a list of interesting open problems.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments