On the complexity of partially-flow-sensitive alias analysis
Noam Rinetzky, Ganesan Ramalingam, Mooly Sagiv, Eran Yahav · ACM Transactions on Programming Languages and Systems · 2008
We introduce the notion of apartially-flow-sensitive analysis based on the number of read and write operations that are guaranteed to be analyzed in a sequential manner. We study the complexity of partially-flow-sensitive alias analysis and show that precise alias analysis with a very limited flow-sensitivity is as hard as precise flow-sensitive alias analysis, both when dynamic memory allocation is allowed, as well as in the absence of dynamic memory allocation.