Cloning-based context-sensitive pointer alias analysis using binary decision diagrams

• DOI: 10.1145/996841.996859
• Publication Date: 2004-07-20T11:55:38Z
• Authors: John Whaley; Monica S. Lam
• Keywords: Pointer analysis; Datalog; Call graph; Binary decision diagram; Alias

This paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for Java programs. Our approach to context sensitivity is create a clone of method every interest, and run context-insensitive algorithm over expanded call graph get context-sensitive results. For precision, we generate acyclic path through program's graph, treating methods in strongly connected component as single node. Normally, this formulation hopelessly intractable often has 10 14 paths or more. We show that these exponential relations can be computed efficiently using binary decision diagrams (BDDs). Key scalability technique numbering scheme exposes commonalities across contexts. applied our most popular applications available on Sourceforge, found largest programs, with hundreds thousands bytecodes, analyzed under 20 minutes.This shows analysis, many other queries algorithms, described succinctly declaratively Datalog, logic programming language. have developed system called bddbddb automatically translates Datalog programs into highly efficient BDD implementations. used develop variety algorithms including side effect type escape analysis.