Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
John Whaley, Monica S. Lam · ACM SIGPLAN Notices · 2004
This paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for Java programs. Our approach to context sensitivity is to create a clone of a method for every context of interest, and run a context-insensitive algorithm over the expanded call graph to get context-sensitive results. For precision, we generate a clone for every acyclic path through a program's call graph, treating methods in a strongly connected component as a single node. Normally, this formulation is hopelessly intractable as a call graph often has 10 14 acyclic paths or more. We show that these exponential relations can be computed efficiently using binary decision diagrams (BDDs). Key to the scalability of the technique is a context numbering scheme that exposes the commonalities across contexts. We applied our algorithm to the most popular applications available on Sourceforge, and found that the largest programs, with hundreds of thousands of Java bytecodes, can be analyzed in under 20 minutes.This paper shows that pointer analysis, and many other queries and algorithms, can be described succinctly and declaratively using Datalog, a logic programming language. We have developed a system called bddbddb that automatically translates Datalog programs into highly efficient BDD implementations. We used this approach to develop a variety of context-sensitive algorithms including side effect analysis, type analysis, and escape analysis.
Cited by 57 works. doi:10.1145/996893.996859
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Principles of database and knowledge-base systems
- Precise interprocedural dataflow analysis via graph reachability
- Points-to analysis in almost linear time
- Context-sensitive interprocedural points-to analysis in the presence of function pointers
- Efficient context-sensitive pointer analysis for C programs
- Horn clause queries and generalizations
- Escape analysis for Java
- Unification-based pointer analysis with directional assignments
- Compositional pointer and escape analysis for Java programs