Interprocedural Pointer Tracking

>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.)


> An exact solution to the aliasing problem is indeed intractable, but very
> accurate approximate solutions can be computed efficiently in practice.
> If you could even come close to translating a C program to Fortran, it would
> be an ideal candidate for pointer analysis. Within the next few years, I
> expect commercial compilers will start including interprocedural pointer
> analysis.


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.


Your predictive powers are less able than your compiler skills. :-)
Commercial compilers HAVE HAD interprocedural pointer analysis since
the production release of the Convex Application Compiler back in May 1991.
You can find a discussion of it in:


Pointer Target Tracking: An Empirical Study
J. Loeliger, R. Metzger, M. Seligman and S. Stroud
Proceedings of Supercomputing '91, IEEE
pages 14-23


As for speed, by the time I had done the third(!) implementation, I
had gotten the cost down to a few minutes for a 30,000 line numerical
C application. That was on a Convex C-220 in 1991, which is at least
an order of magnitude slower for this type of code than the best
workstation you can buy today.


/Bob


--

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