
Solving Demand Versions of Interprocedural Analysis Problems
Thomas Reps1
Datalogisk Institut, University of Copenhagen
Universitetsparken 1
DK2100 Copenhagen East
Denmark
Abstract
This paper concerns the solution of demand versions of interprocedural analysis problems. In a demand version of a programanalysis problem, some piece of summary information (e.g.,the data?owfacts holding at a givenpoint) 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 howalgorithms for demand versions of programanalysis problems can be obtained from their exhaustive counterparts essentially for free, by applying the socalled ?magicsets? transformation that was developed in the logicprogramming and deductivedatabase communities.
1. Introduction
Interprocedural analysis concerns the static examination of a program that consists of
multiple procedures. Its purpose is to determine certain kinds of summary information
associated with the elements of a program (such as reaching de?nitions, available expressions,
live variables, etc.). Most treatments of interprocedural analysis address the
exhaustive version of the problem: summary information is to be reported for all elements
of the program. This paper concerns the solution of demand versions of interprocedural
analysis problems: summary information 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.
One of the novelaspects of our work is that establishes a connection between the ideas
and concerns from twodifferent research areas. This connection can be summarized as
follows:
Methods for solving demand versions of interprocedural analysis problems?and in particular interprocedural analysis problems of interest to the community that studies imperative programs?can be obtained from their exhaustive counterparts essentially for free, by applying a transformation that was developed in the logicprogramming and deductivedatabase communities for optimizing the evaluation of recursive queries in deductive databases (the socalled magicsets transformation [22,3,7]).
1On sabbatical leave from the University of WisconsinMadison.
This work was supported in part by a David and Lucile Packard Fellowship for Science and Engineering, by
the National Science Foundation under grant CCR9100424, and by the Defense Advanced Research Projects
Agencyunder ARPAOrder No. 8856 (monitored by the Of?ce of NavalResearch under contract
N0001492J1937).