Implementing sparse flow-sensitive Andersen analysis

Abstract

Andersen's analysis is the most influential pointer analysis known so far. This paper, which contains parts of the author's upcoming PhD thesis, for the first time presents a flow-sensitive version of that analysis. We prove that the flow-sensitive version still has the same cubic complexity. Thus, the higher precision comes without loss of asymptotic scalability. This contradicts common wisdom of flow-sensitivity being substantially more expensive.

Compared to other flow-sensitive pointer analyses, we have no expensive data-flow problem on the CFG. Instead, we simply propagate pointer targets along data-flow relations which we determine during the analysis. Our analysis in fact combines the computation of the interprocedural SSA data-flow representation and the uncovering of pointer targets. It also integrates the computation of control-flow relations. The analysis thus presents a new, sparse approach for the flow-sensitive solution of the central problems for data-flow based program analyses.

This paper also presents two extensions for higher precision. The first extension shows how the analysis can detect strong updates without increasing the complexity. The second extension describes a context-sensitive version which excludes unrealizable paths. Together this yields the first analysis of that precision which only has a complexity of n^4. This is a substantial improvement over the previous n^6 bound found by Landi.

Thus, in summary this report describes several theoretical advances in the field of flow-sensitive pointer analysis. It also provides details on the algorithms used for incremental SSA construction and context-sensitive pointer propagation.