Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis
Guoqing Harry Xu, Atanas Rountev · 2008
A context-sensitive points-to analysis maintains separate pointsto relationships for each possible (abstract) calling context of a method. Previous work has shown that a large number of equivalence classes exists in the representation of calling contexts. Such equivalent contexts provide opportunities for context-sensitive analyses based on binary decision diagrams (BDDs), in which BDDs automatically merge equivalent points-to relationships. However, the use of a BDD “black box ” introduces additional overhead for analysis running time. Furthermore, with heap cloning (i.e., using context-sensitive object allocation sites), BDDs are not as effective because the number of equivalence classes increases significantly. A further step must be taken to look inside the BDD black box to investigate where the equivalence comes from, and what tradeoffs can be employed to enable practical large-scale heap cloning. This paper