CPA beats oo-CFA - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

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.
Fichier principal
Vignette du fichier
CPA_beats_CFA.pdf (218.37 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00780389 , version 1 (24-11-2014)

Identifiers

Cite

Frédéric Besson. CPA beats oo-CFA. FTfJP '09 - Proceedings of the 11th International Workshop on Formal Techniques for Java-like Programs, 2009, Genova, Italy. ⟨10.1145/1557898.1557905⟩. ⟨hal-00780389⟩
317 View
89 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More