| This thesis shows that whole-program context-sensitive inclusion-based pointer analysis, a previously intractable problem, can be efficiently solved using binary decision diagrams. In addition, we show that it is possible to automatically translate from a high-level analysis specification written in Datalog into an efficient implementation using binary decision diagrams.; We present the first scalable context-sensitive, inclusion-based pointer 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 1014 acyclic paths or more. We show that these exponential relations can be computed efficiently using BDDs.; We also describe bddbddb, a BDD-Based Deductive DataBase, which implements the declarative language Datalog with stratified negation, totally-ordered finite domains and comparison operators. bddbddb uses binary decision diagrams (BDDs) to efficiently represent large relations. BDD operations take time proportional to the size of the data structure, not the number of tuples in a relation, which leads to fast execution times. bddbddb is an effective tool for implementing a large class of program analyses. We show that a context-insensitive pointer analysis implemented with bddbddb is about twice as fast as a carefully hand-tuned version. |
