Next: Pointer Representations Up: Major Concepts Previous: Design of PTFs

Algorithm Outline

Just as we create extended parameters lazily, we only create PTFs as they are needed. In this way, we do not compute unnecessary summaries. We begin by using an iterative data-flow approach to find the potential pointer values in the main procedure. When this iterative analysis encounters a call to a procedure with new input aliases, it recursively analyzes that procedure for the current context to produce a new PTF. We use a stack to keep track of the current calling contexts.

We update the initial points-to functions and parameter mappings lazily during the iterative analysis. When we begin analyzing a procedure, the initial points-to function is empty and the parameter mapping only records the actual values for the formal parameters. When we need to know the initial value of an input pointer and it is not already recorded, we add an entry to the initial points-to function. To check for aliases, we need to look up the initial values in the calling context. If the pointer has not yet been referenced in the calling context either, we will add an entry to the caller's initial points-to function. The process continues recursively up the call graph until the pointer values are known. If the initial values are not aliased with any existing parameters, we create a new extended parameter to represent those values and record that in the parameter mapping. Section 3.2 describes the situations where the initial values are aliased with one or more existing parameters.

When the iterative analysis encounters a procedure call, it needs to find the effects of the call on the points-to function. If the call is through a pointer passed as an input to one or more of the PTFs on the call stack, we add the potential values of that pointer to the specifications of the input domains for those PTFs. For each potential callee procedure, we first check if any of its PTFs apply. This involves building up a parameter mapping and comparing the input aliases to those recorded for the PTF. If the input aliases and function pointer values match, we use the parameter mapping to translate the final pointer values recorded in the PTF back to the current context. Otherwise, if the inputs do not match any of the existing PTFs, we reanalyze the procedure to produce a new PTF.

Next: Pointer Representations Up: Major Concepts Previous: Design of PTFs

Bob Wilson