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 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.
Introduction
In static program analysis, researchers and developers typically rely on exhaustive analysis, which computes dataflow facts for every program point across an entire codebase. While thorough, this approach is often computationally expensive and unnecessary for many practical applications. For instance, a developer debugging a specific function or a compiler optimizer focusing on a "hot spot" loop only requires information relevant to those specific locations.
This creates a need for demand versions of analysis problems. However, manually designing demand-driven algorithms for interprocedural analysis—which tracks data across function boundaries—is notoriously difficult. The primary challenge lies in managing calling contexts to ensure the analysis only explores "valid paths" (paths that respect the call-return structure of the program). This paper demonstrates that these complex demand-driven algorithms do not need to be designed from scratch; instead, they can be derived automatically from standard exhaustive algorithms.
Methodology: The Magic-Sets Transformation
The paper proposes a two-phase methodology to bridge the gap between exhaustive and demand-driven analysis by leveraging techniques from the deductive database community.
1. Logic Encoding
The first step involves encoding a standard exhaustive interprocedural analysis as a logic program. Specifically, the author utilizes the "functional approach" to interprocedural analysis defined by Sharir and Pnueli. By representing the analysis using Horn clauses (similar to the Prolog language), the dataflow problem is transformed into a set of recursive logic rules.
To facilitate this encoding, the author introduces the use of nkill (not-killed) sets rather than traditional "kill" sets. This representation allows the logic engine to handle the intersection and union of dataflow facts naturally through its built-in mechanisms for evaluating multiple rules.
2. The Magic-Sets Transformation
Once the analysis is expressed as a logic program, the paper applies the "magic-sets" transformation (also known as the Alexander method). Originally developed to optimize recursive queries in deductive databases, this transformation takes a general set of rules and a specific query (the "demand") and produces a new, specialized set of rules.
These generated rules include "guard" literals that restrict the computation. The resulting system only visits program points and computes dataflow facts that are strictly necessary to answer the specific demand query. This process effectively automates the creation of a targeted analysis.
Key Insights and Technical Advantages
Context Sensitivity "For Free"
One of the most significant hurdles in interprocedural analysis is ensuring that the analysis respects the call-return structure (context sensitivity). The paper demonstrates that if the initial exhaustive logic program is designed to respect valid paths, the magic-sets transformation preserves this property. Consequently, the derived demand-driven algorithm is automatically context-sensitive.
Caching and Memoization
Because the resulting algorithm is evaluated using bottom-up logic evaluation, intermediate results are naturally cached. This provides an inherent efficiency: if a user submits a second demand query later, the system can reuse the memoized results from the first query, further reducing redundant computation.
Algorithmic Equivalence
The paper provides a formal foundation for this approach, proving that the demand-driven algorithm produced by the magic-sets transformation is equivalent to the meet-over-all-valid-paths solution for distributive dataflow problems. This ensures that the automated shortcut does not sacrifice accuracy for speed.
Scope and Limitations
While the methodology is powerful, its current application is primarily tailored to distributive dataflow functions, such as "gen-kill" problems (e.g., reaching definitions or available expressions). Non-distributive problems, which are more complex and less common, are not the primary focus of this framework.
Additionally, the efficiency of the generated demand algorithm is sensitive to the sideways information-passing strategy (SIP)—the order in which logic rules are processed. A poorly ordered rule set may still perform more work than an optimally hand-coded algorithm. Finally, the initial framework assumes a program structure with global variables and no procedure-valued variables (function pointers), though these are noted as areas for extension.
Conclusion
By cross-pollinating ideas from the database and programming language communities, this work provides a method to obtain demand-driven interprocedural analyses "essentially for free." The use of the magic-sets transformation allows researchers to focus on defining correct exhaustive analyses while leaving the optimization of demand-driven variants to automated logic-transformation tools.
Summary updated