Next: Evaluating Dereferences Up: Analyzing a Procedure Previous: Strong Updates

Sparse Representation

Because our analysis is interprocedural and needs to keep the entire input program in memory at once, we have gone to considerable effort to use storage space efficiently. Since we analyze heap data as well as global and stack variables, many possible memory locations could be included in the points-to functions. Fortunately, the information stored in the points-to functions is very sparse. Pointers typically have only a few possible values, so we record the possibilities using linked lists rather than bit vectors. Since the points-to functions usually do not change very much between two adjacent program points, we also incorporate the sparse representation described by Chase et al. [1]. This scheme only records the points-to values that change at each node.

Because of the sparse points-to function representation, looking up the values of a pointer requires searching back for the most recent assignment to that location. Beginning at the current node, we search back through the dominating flow graph nodes. If we reach the procedure entry when searching for an assignment to a formal or extended parameter, we compute the value of the initial points-to function for that parameter, if it has not already been recorded, as described in Section 3.2. This may add new extended parameters in the PTFs on the call stack.

Since we only search for assignments in the dominating nodes, each meet node must contain SSA -functions [3] to identify the values to be assigned in it. We insert these -functions dynamically as new locations are assigned [1]. The pseudo-code for handling a meet node is shown in Figure 9. For each -function, we look up the points-to values at each predecessor node and combine the results to get the new points-to values.



Next: Evaluating Dereferences Up: Analyzing a Procedure Previous: Strong Updates


Bob Wilson