Interprocedural Pointer Tracking

metzger@bach.convex.com (Robert Metzger)
Wed, 29 Nov 1995 15:56:20 GMT

          From comp.compilers

Related articles
Re: Loop Optimizations and Gotos cliffc@ami.sps.mot.com (1995-11-22)
alias analysis (was Loop Optimizations and Gotos) bwilson@shasta.Stanford.EDU (Bob Wilson) (1995-11-28)
Interprocedural Pointer Tracking metzger@bach.convex.com (1995-11-29)
Re: Alias Analysis ghiya@acaps.CS.McGill.CA (1995-11-30)
Re: Interprocedural Pointer Tracking bwilson@shasta.Stanford.EDU (Bob Wilson) (1995-11-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: metzger@bach.convex.com (Robert Metzger)
Keywords: analysis, optimize
Organization: Compilers Central
References: 95-11-198 95-11-228
Date: Wed, 29 Nov 1995 15:56:20 GMT

>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


--


Post a followup to this message

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