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 ofThis 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.ppoints to whatever the target ofqinitially pointed to.

- Case I
- If
randpdo not point to any of the same locations, the target ofqpoints to whatever the target ofrinitially pointed to.- Case II
- If
randpdefinitely point to exactly the same location, then the target ofqretains its original value.- Case III
- If
randpmay point to the same locations but their targets are not definitely the same, then the target ofqmay either retain its original value or point to whatever the target ofrpointed to initially.

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.