page 1  (15 pages)
2to next section

Solving Demand Versions of Interprocedural Analysis Problems

Thomas Reps1

Datalogisk Institut, University of Copenhagen
Universitetsparken 1
DK-2100 Copenhagen East
Denmark

Abstract

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 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 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.

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 deductive-database communities for optimizing the evaluation of recursive queries in deductive databases (the so-called magic-sets transformation [22,3,7]).

1On sabbatical leave from the University of Wisconsin-Madison.
This work was supported in part by a David and Lucile Packard Fellowship for Science and Engineering, by the National Science Foundation under grant CCR-9100424, and by the Defense Advanced Research Projects Agencyunder ARPAOrder No. 8856 (monitored by the Of?ce of NavalResearch under contract N00014-92-J-1937).