bddbddb - A BDD-Based Deductive DataBase


John Whaley, Christopher Unkel, and Monica S. Lam


Stanford University


{jwhaley,cunkel,lam} @ stanford.edu

Abstract

bddbddb is a tool for easily and efficiently specifying and querying program analyses. We represent the program and analysis results in a deductive database implemented with binary decision diagrams. Binary decision diagrams (BDDs) are a data structure that can efficiently represent large relations and provide efficient set operations. They have recently been shown to be effective for whole-program pointer analysis; we demonstrate that they are applicable to other program analyses.

Queries are specified as a program in Datalog, a standard declarative language for reasoning about relations. Our deductive engine automatically translates the Datalog program into an optimized series of BDD operations. We show that a logic database implemented with BDDs is an efficient platform for program analysis. Indeed, experimental results run on a variety of programs show that points-to analysis implemented with our tool is typically faster than a handcoded version.

The latest version of bddbddb is currently available in the CVS repository, accessible from the project page on Sourceforge. To generate the initial relations, we use the Joeq compiler infrastructure. The joeq.Main.GenRelations class generates the initial relations for pointer analysis. We are also working on an Eclipse plugin so you can generate the initial relations directly from the Eclipse AST.

If you are using or are interested in using bddbddb, it would be great if you could drop me a line and let me know about it. I am interested in knowing how people are using the system, and I might actually have some insights that are useful. Thanks!


Last modified: August 2, 2004 by jwhaley