Re: Alias Analysis

>>From bwilson@shasta.Stanford.EDU Wed Nov 29 09:10:37 CST 1995


>> For Fortran-style programs written in C, interprocedural pointer analysis
>> provides very accurate information and only requires a small amount of extra
>> compile time. (The situation is less clear for non-numeric programs with
>> lots of recursive data structures, but even there it appears that pointer
>> analysis can be made to work quite well.)


>metzger@bach.convex.com
>I agree about numerical programs that use blocks of contiguous, homogeneous
>storage (Simulating arrays with pointers).
>I am not convinced about recursive data structures. There are many
>interesting papers, but I don't know of an implementation that can handle
>large programs (say GCC) efficiently.


Ok, just an attempt to further clarify the issues:


I've recently analyzed some large C codes using a combination
of fast flow-insensitive and accurate context-sensitive
interprocedural pointer analysis techniques.
The analysis results indicate that targets for pointers to
stack locations (obtained using the address-of (&) operator),
can be very accurately estimated, even with conservative
flow-insensitive approaches (which are quite fast). The
main reason is that stack-directed pointers don't show
very complex aliasing patterns in real C codes: they typically
tend to have one or two targets over the entire program!


As already noted above by others, the heap-directed pointer
problem is more complex (why? : because targets in heap don't
have names, and a heap-directed pointer can potentially have
many targets over the program e.g. a pointer used to traverse a list).
However, important subsets of the problem can be still
effectively solved. In our McCAT C compiler at McGill, we
have implemented two simple heap analyses, which respectively
attempt to identify if two heap accesses lead to disjoint
linked structures in heap, or to disjoint subpieces of
the same (recursive) heap structure: the second problem being
more difficult. Empirical results for medium-size C programs
indicate that effective results can be obtained: however
for larger C codes more engineering is required to make the
analyses efficient. The more interested can look at the following
refs:




@InProceedings{GhiyaHen95,
    Author = "Rakesh Ghiya and Laurie J. Hendren",
    Title = "Connection Analysis: A Practical Interprocedural Heap
                      Analysis for {C}",
    Booktitle = "Proceedings of the Eighth Workshop on Languages and
      Compilers for Parallel Computing",
    Place = "Columbus, Ohio",
    Month = "August",
    Year = 1995,
    Note = "(To appear as LNCS)"
}


ftp from: ftp-acaps.cs.mcgill.ca:pub/doc/papers/lcpc95.ps.gz


@InProceedings{GhiyaHen96,
    Author = "Rakesh Ghiya and Laurie J. Hendren",
    Title = "Is it a Tree, a DAG or a Cyclic Graph? A Shape Analysis
                      for Heap-Directed Pointers in {C}",
    Booktitle = "Conference Record of the 23rd ACM SIGPLAN-SIGACT
                              Symposium on Principles of Programming Languages",
    Month = "Jan",
    Year = 1996,
    Note = "(To appear)"
}


ftp from: ftp-acaps.cs.mcgill.ca:pub/doc/papers/popl96.ps.gz




---


Rakesh.


(ghiya@acaps.cs.mcgill.ca)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.