Solving demand versions of interprocedural analysis problems

This paper concerns the solution of demand versions of interprocedural analysis problems. In a demand version of a program-analysis problem, some piece of summary information (e.g., the dataflow facts holding at a given point) is to be reported only for a single program element of interest (or a small number of elements of interest). Because the summary information at one pro-gram point typically depends on summary information from other points, an important issue is to minimize the number of other points for which (transient) summary information is computed and/or the amount of information computed at those points. The paper describes how algorithms for demand versions of program-analysis problems can be obtained from their exhaustive counter-parts essentially for free, by applying the so-called “magic-sets ” transformation that was devel-oped in the logic-programming and deductive-database communities. 1