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

By: Michael Burke, Jong-Deok Choi, Paul Carini, and Michael Hind

Published in: RC21055 in 1997


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Questions about this service can be mailed to .