Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
John Whaley, Monica S. Lam · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 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 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...
Cited by 582 works. doi:10.1145/996841.996859
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Principles of database and knowledge-base systems
- Principles of database and knowledge-base systems, Vol. I
- Java Virtual Machine Specification
- Precise interprocedural dataflow analysis via graph reachability
- Points-to analysis in almost linear time
- Efficient context-sensitive pointer analysis for C programs
- Context-sensitive interprocedural points-to analysis in the presence of function pointers
- Efficient context-sensitive pointer analysis for C programs
- Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis