On the Complexity of Partially-Flow-Sensitive Alias Analysis

The authors introduce the notion of a partially-flow-sensitive analysis based on the number of read and write operations that are guaranteed to be analyzed in a sequential manner. They 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. Most static analyses for modern programming languages depend significantly on various forms of pointer analysis, such as alias analysis, to deal with indirect data references and modifications.