CPA beats oo-CFA
Abstract
Context-sensitive points-to analysis is the current most scalable technology for constructing a precise control-flow graph for large object-oriented programs. One appealing feature of this framework is that it is parametric thus allowing to trade time for precision. Typical instances of this framework are k-CFAs and Agesen's Cartesian Product Algorithm (CPA). It is common sense that k-CFAs (for increasing ks) form a hierarchy. Yet, what is the relative precision of k-CFA and CPA? Grove and Chambers [2] conjecture that CPA is more precise than oo-CFA. For a core object-oriented language, we formally compare the precision of oo-CFA and CPA. We prove that CPA is indeed strictly more precise than oo-CFA. On a theoretical level, this result confirms the findings of empiric studies concluding the superiority of object-sensitivity with respect to call-string sensitivity.
Origin : Files produced by the author(s)
Loading...