Interprocedural Pointer Alias Analysis

We present practical approximation methods for computing and
representing interprocedural aliases for a program written in a
language that includes pointers, reference parameters, and recursion.
We present a general framework for interprocedural pointer alias
analysis, and the following:

1) a flow-sensitive interprocedural pointer alias analysis algorithm;

2) a flow-insensitive interprocedural pointer alias analysis algorithm
that can incorporate kill information to improve precision, and use
deferred evaluation to increase efficiency;

3) an algorithm for function pointer analysis that can be incorporated
into the general framework;

4) a compact representation of alias information that is based on
named objects rather than pointer expressions and accommodates cyclic
data structures without resorting to a k-limiting scheme to limit
the level of indirection;

5) techniques that improve the precision of alias analysis with
respect to the unrealizable path problem and the non-distributive
combining problem;

6) a technique for improving the precision of alias informatino for
compact and graph-based representations;

7) an interprocedural naming technique for dynamically allocated
objects that improves the precision of alias analysis for such
objects; and

8) empirical measurements of the efficiency and precision of the three
interprocedural alias analysis algorithms; the flow-sensitive,
flow-insensitive, and flow-insensitive with precompute kill
algorithms.