Next: Points-to Functions Up: Pointer Representations Previous: Location Sets

Extended Parameters

As discussed in Section 2.2, every object is represented by at most one extended parameter. When adding an entry to the initial points-to function, we first find the values of the pointer in the calling context. If the parameter mapping shows that an existing parameter already includes the same values, we reuse the old parameter instead of creating a new one.

For simplicity and efficiency, each initial points-to entry points to a single extended parameter. In cases where the initial values are aliased with more than one parameter, we create a new extended parameter that subsumes all the aliased parameters, and we replace all references to the subsumed parameters. Likewise, when the initial values are aliased with an existing parameter but also include new values, we subsume the aliased parameter with a new one. Figure 6 illustrates this. Parameter 1_a is created first to represent the targets of a. When b is dereferenced later, we discover that its targets include the value represented by 1_a but also another value. Thus, we create a new parameter 1_b that replaces the old parameter 1_a. This scheme reduces the number of extended parameters with some loss of precision. That is an acceptable trade-off for our purposes, but subsuming parameters is not essential to our algorithm and could easily be omitted.

Aliases involving fields of structures can be a bit more complicated. When updating the initial points-to function, if we find a pointer to a field of an existing parameter, we can easily record that fact. However, if we encounter a pointer to a field before a pointer to the enclosing structure, we will create an extended parameter to represent the field, and then the other pointer will have to point before the existing parameter. Fortunately, our location sets solve this problem nicely. We simply allow the location set offsets to be negative, as shown in Figure 7. Emami solves this problem by always creating parameters for structures before any other parameters [5], but that cannot work here because we create the parameters as they are referenced.



Next: Points-to Functions Up: Pointer Representations Previous: Location Sets


Bob Wilson