Precise flow-insensitive may-alias analysis is NP-hard
- 1 January 1997
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 19 (1) , 1-6
- https://doi.org/10.1145/239912.239913
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.Keywords
This publication has 3 references indexed in Scilit:
- Flow-insensitive interprocedural alias analysis in the presence of pointersPublished by Springer Nature ,1995
- The undecidability of aliasingACM Transactions on Programming Languages and Systems, 1994
- Undecidability of static analysisACM Letters on Programming Languages and Systems, 1992