bddbddb

bddbddb stands for BDD-Based Deductive DataBase. It is an implementation of Datalog, a declarative programming language similar to Prolog for talking about relations. What makes bddbddb unique is that it represents the relations using binary decision diagrams (BDDs). BDDs are a data structure that can efficiently represent large relations and provide efficient set operations. This allows bddbddb to efficient represent and operate on extremely large relations - relations that are too large to represent explicitly.

We use bddbddb primarily as a tool for easily and efficiently specifying program analyses. We represent the entire program as database relations. Developing a program analysis becomes as simple as writing the specification for the analysis in a declarative style and then feeding that specification to bddbddb, which automatically transforms your specification into efficient BDD operations.

Using bddbddb for program analysis has a number of advantages:

• First, it closes the gap between the algorithm specification and its implementation. In bddbddb, the algorithm specification is automatically translated into an implementation, so as long as your algorithm specification is correct you can be reasonably sure that your implementation will also be correct.
• Second, because BDDs can efficiently handle exponential relations, it allows us to solve heretofore unsolved problems in program analysis, such as context-sensitive pointer analysis for large programs.
• Third, it makes program analysis accessible, and dare I say it, actually fun. Trying out a new idea in program analysis used to be confined to the realm of experts and compiler writers, and would take weeks to months of tedious effort to implement and debug. With bddbddb, writing a new analysis is simply a matter of writing a few straightforward inference rules. The tool takes care of most of the tedious part and helps you develop powerful program analyses easily.

bddbddb was written by John Whaley, a Ph.D. student working in the Stanford SUIF Compiler group, as part of his research with Professor Monica Lam. He releases this software as open source with the hope that it will take program analysis to a new level by accelerating the development of new advanced analyses, enabling non-specialists to easily develop their own program analyses, and facilitating collaboration between programming language researchers.