Solving Demand Versions of Interprocedural Analysis Problems
Thomas Reps
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 program 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
counterparts essentially for free, by applying the so-called
"magic-sets" transformation that was developed in the
logic-programming and deductive-database communities.
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin