DDP at PLDI (June 17, 2006)

I read with interest this PLDI paper by Manu Sridharan and Ras Bodik. They have a very interesting analysis that, from a general perspective, uses the overall approach of DDP: choose carefully where in the program you focus analysis efforts, so that your analyzer can scale to large programs but still can use context-sensitivity to unravel different parts of the program.

The authors’ formulation, however, is quite different from DDP. DDP uses a very general formulation: goals, their answers, and dependencies among goals. This is so general that it is not even specific to program-analysis. This generality is a strength and a weakness: it means you can often improve an analysis simply by using DDP as the base layer of the algorithm instead of the normal demand-driven worklist algorithm. However, because DDP is so general at this level, it does not exploit any properties of the rules themselves. It is the classic trade off of generality.

One really nice property of Sridharan’s graph formulation is that you can easily remove the “match” edges and thus cause the algorithm to improve its existing results. There is no analog in DDP as described so far (although I am not ready to say there cannot be such an analog).

Overall, it is great work that is very interesting to me. It is a pity the authors overlooked initially my work in the area, although we have since had a pleasant exchange in private email. More the pity is that the PLDI reviewers of this paper also overlooked the prior work. It was published in ECOOP ‘04, which is not obscure for program-analysis buffs.