I learned how to describe nearly any (with some constraints) reasonable static code analysis in terms of a simple logic programming language Datalog. The simplest implementation allows immediately for incremental analysis to be performed. But this is not all we can get with it! Static analyses are considered difficult because of enormous resources consumption (exponential blowup is not exotic). The problem is addressed by special data representation technique based on Binary Decision Diagrams (BDDs). The logic program in Datalog is translated in terms of relational algebra operations which act over BDD representation of relations. The idea behind the usage of BDDs is that they allow for compact representation of relations as Boolean functions. Although in worst cases the representation of arbitrary function can not be concise (as there are 22n of them), the regularities found in most functions provide opportunity to effectively store them. The idea has been put into practice just several years ago in bddbddb implementation of Datalog at Stanford. Results presented in the concomitant paper are very impressive: most complex full program analyses of large code bases (hundreds of thousands lines of code) have been performed in minutes, not hours!
There is no need to say that the work of SUIF Compiler Group anticipated and, more importantly, elaborated and put into pracrice the ideas on generalized analysis implementation which I was only incubating. All by the time I entered the NSU. One question I had after reading the paper was, why didn't I know about this technique a year ago? I won't investigate the obvious reasons but will try implementing my type analysis with the framework provided by bddbddb. For a start, my part will be to see if these ideas are immediately applicable to interactive analysis tools, or require improvement.
