Next: Sparse Representation Up: Analyzing a Procedure Previous: Analyzing a Procedure

Strong Updates

Strong updates, where assignments overwrite the previous contents of their destinations, are an important factor in the precision of pointer analysis. Unless we know that an assignment will definitely occur and that it assigns to a unique location, we must conservatively assume that that location potentially retains its old values.

Because strong updates make the node transfer functions non-monotonic, we introduce some constraints on the order in which the flow graph nodes are evaluated in order to guarantee that the algorithm terminates. Specifically, we never evaluate a node until one of its immediate predecessors has been evaluated, and we never evaluate an assignment until its destination locations are known [1].

We take advantage of the extended parameters to increase the opportunities for strong updates. A strong update is only possible if the destination of an assignment is a single location set representing a unique location. A location set is unique if it has no stride and the base represents a unique block of memory. The key is to recognize that an extended parameter representing the initial value of a unique pointer can be a unique block even if that pointer has many possible values in the calling context. Since the pointer can only contain one of those possibilities at any one time, the extended parameter is a unique block within the scope of the procedure. Only when more than one location points to an extended parameter and the actual values for that parameter are not a single unique location must we mark the parameter as not unique. This greatly improves our ability to perform strong updates. Since a heap block represents all the storage allocated in a particular context, we assume that locally allocated heap blocks are never unique. On the other hand, local variables correspond directly to real memory locations so they are always unique blocks.

Next: Sparse Representation Up: Analyzing a Procedure Previous: Analyzing a Procedure

Bob Wilson