Next: Analyzing a Procedure Up: Pointer Representations Previous: Extended Parameters

Points-to Functions

Both the domains and ranges of the points-to functions are expressed in terms of location sets. At each statement in a program, a points-to function maps the location sets containing pointers to the locations that may be reached through those pointers. Thus, a points-to function is a mapping from location sets to sets of location sets.

It is important for the analysis to know which locations may contain pointers. Since we do not use the high-level types and since the points-to functions only contain entries for pointers that have already been referenced, we record separately for each block of memory the location sets that may hold pointers. Without that information, the analysis would have to conservatively evaluate every assignment as a potential pointer assignment. Although that would not affect the precision of the results (eventually the analysis finds which values may be pointers and removes any spurious results), we have found that it makes the analysis very inefficient.

For a variety of optimizations, it is important to know when a location definitely holds a certain pointer value. Within the pointer analysis itself, that information can enable strong updates, where assignments overwrite the previous contents of their destinations. Others have kept track of ``possible'' and ``definite'' points-to values separately [6], but that is unnecessary for our purposes. We only need that information at the point where a pointer is dereferenced. Since we assume that the input is legal, a location being dereferenced must contain a valid pointer. The points-to functions record all the valid pointers possibly contained in each location, and if there is only one possibility, it is safe to assume that is the value being dereferenced. Thus, we get the benefits of definite pointer values without the overhead of tracking them separately.



Next: Analyzing a Procedure Up: Pointer Representations Previous: Extended Parameters


Bob Wilson