alias analysis (was Loop Optimizations and Gotos)

cliffc@ami.sps.mot.com (Cliff Click) wrote:
> There's no general way to figure out the Fortran no-alias assertion in
> C code (lots of IPA can get you part of the way there, but not all the
> way). Lack of this assertion can hurt some dependence analysis, with
> the results outlined above.


OK, Cliff, you made a similar remark in a previous post and I let
it slide, but I'm speaking up this time. I think we agree that
the lack of alias information in C is one of the biggest obstacles
to better optimization. You're just being far too pessimistic
about using interprocedural analysis to provide information about
aliases.


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




> Summary:
> 1) Loops from GOTOs will be optimized "properly" on most (not all)
> workstation compilers.
> 2) Array refs as pointer derefs could be optimized properly, 'cept
> they aren't on most (not all) compilers. Cause: software inertia.
> 3) You can't get the "no alias" assertion without writing Fortran
> (modulo pragma's & wild function-unswitching techniques).
> Cause: it's intractable.


The SUIF compiler handles all these problems, although the scalar
optimizer which handles #1 has fallen into disrepair. (Note: the
released version doesn't include all these features, but it will
eventually.)


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. If you can
wait, that might be better than rewriting all your C programs in
Fortran.


Here are some references for anyone out there who wants to
know more:


@inproceedings { RWilson_95,
author = "Robert P. Wilson and Monica S. Lam",
title = "Efficient Context-Sensitive Pointer Analysis for {C}
                                Programs",
booktitle= pldi95,
month = jun,
year = 1995,
pages = "1--12"
}


@inproceedings { MEmami_94,
author = "Maryam Emami and Rakesh Ghiya and Laurie J. Hendren" ,
title = "Context-Sensitive Interprocedural Points-to Analysis
                                in the Presence of Function Pointers" ,
booktitle= pldi94 ,
month = jun ,
year = 1994 ,
pages = "242--256"
}


@inproceedings { WLandi_92,
author = "William Landi and Barbara G. Ryder" ,
title = "A Safe Approximate Algorithm for Interprocedural
                                Pointer Aliasing" ,
booktitle= pldi92 ,
month = jun ,
year = 1992 ,
pages = "235--248"
}


@inproceedings { WLandi_93,
author = "William Landi and Barbara G. Ryder and Sean Zhang" ,
title = "Interprocedural Modification Side Effect Analysis
                                With Pointer Aliasing" ,
booktitle= pldi93 ,
month = jun ,
year = 1993 ,
pages = "56--67"
}


@inproceedings { ERuf_95,
author = "Erik Ruf",
title = "Context-Insensitive Alias Analysis Reconsidered",
booktitle= pldi95,
month = jun,
year = 1995,
pages = "13--22"
}


@inproceedings { JDChoi_93,
author = "Jong-Deok Choi and Michael Burke and Paul Carini" ,
title = "Efficient Flow-Sensitive Interprocedural Computation
                                of Pointer-Induced Aliases and Side Effects" ,
booktitle= popl93 ,
month = jan ,
year = 1993 ,
pages = "232--245"
}
--

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