Next: Applying a PTF Up: Interprocedural Algorithm Previous: Calls Through Pointers

Testing if a PTF Applies

The input domain of a PTF is specified by its initial points-to function and by the values of the parameters used as call targets. To test if a PTF applies, we check if these things are the same in the current context as they were when the PTF was created. We check the initial points-to function entries one at a time, in the order in which they were created. We then compare the values of the parameters that were used as call targets. If at any point they do not match, we give up and go on to the next PTF. The basic steps of this process are shown in Figure 13.

In the process of comparing the initial points-to function, we also build up a parameter mapping. If the PTF matches, we can then use this mapping to apply the PTF in the current context. For each entry in the initial points-to function, we find the actual values of the corresponding pointer in the current context and add the results to the parameter mapping. Just as when the PTF was created, this operation may create new initial points-to entries for the other PTFs on the call stack.

Sometimes the aliases and function pointer values for a PTF match, but we need to extend the PTF because new locations contain pointers. As described in Section 3.3, we record the location sets in each block of memory that may contain pointers. By allowing us to ignore operations that do not involve pointers, this makes the analysis more efficient. However, if an input location contains a pointer in the current calling context, whereas it did not when the PTF was created, the results in the PTF may not be complete. When that happens, we reanalyze the procedure to extend the PTF. Note that the resulting PTF will still be applicable to all the calling contexts in the original input domain, since assuming that more locations may contain pointers is only a matter of efficiency.

If none of the existing PTFs are applicable, we need to reanalyze the procedure. In general, we create an empty PTF and then revisit the procedure to compute its summary. However, this simple approach may waste a lot of storage. During the iterative analysis of a procedure, we may evaluate a call node several times with different input values on each iteration. If we create a new PTF for each set of inputs, we will likely end up with a lot of PTFs that only apply to intermediate results of the iteration. Our solution is to record the calling context where each PTF is created. If none of the existing PTFs match, but one of them was created in the current context during an earlier iteration, we update that PTF instead of creating a new one.

Next: Applying a PTF Up: Interprocedural Algorithm Previous: Calls Through Pointers

Bob Wilson