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.