Next: Design of PTFs Up: Major Concepts Previous: Major Concepts

Partial Transfer Functions

To provide some insight on how one might define transfer functions for pointer analysis, consider an informal summary for the very simple procedure f in Figure 1:

The target of p points to whatever the target of q initially pointed to.
Case I
If r and p do not point to any of the same locations, the target of q points to whatever the target of r initially pointed to.
Case II
If r and p definitely point to exactly the same location, then the target of q retains its original value.
Case III
If r and p may point to the same locations but their targets are not definitely the same, then the target of q may either retain its original value or point to whatever the target of r pointed to initially.

This example illustrates two important points. First, the aliases among the inputs to a procedure determine its behavior. Given a particular set of aliases, summarizing a procedure is relatively easy. Second, even for this simple two-statement procedure the complete summary is fairly complex. Computing a full summary for a procedure with cycles and recursive data structures is prohibitively expensive.

The main idea behind our algorithm is that we need not summarize a procedure for all possible aliases among its inputs. Instead, we only need to find summaries that apply to the specific alias patterns that occur in the program. For our simple example, Case I applies to the calls at S1 and S2 because they have the same alias pattern, even though they have totally different parameters. Case II applies to the call at S3. Thus it is not necessary to consider Case III for this particular program.

Our basic approach and its comparison with traditional interval analysis are illustrated in Figure 2. The traditional approach is to define a complete transfer function that maps the entire input domain for a procedure to the corresponding outputs (Figure 2(a)). Instead, we develop a set of partial transfer functions (PTFs), each of which is applicable to only a subset of the input domain. As shown in Figure 2(b), the domains of these partial functions are disjoint and the union of their domains does not necessarily cover all the possible inputs. Many potential inputs never occur in practice, and we only need PTFs for the inputs that actually occur. That means the complexity of all the PTFs taken together is much lower than that of the full transfer function.

Next: Design of PTFs Up: Major Concepts Previous: Major Concepts

Bob Wilson