Re: Pointer alias analysis?

R Seshadri <sesha@chanakya.csa.iisc.ernet.in> wrote:
>I am doing aliasing analysis on language C and Fortran 90 as part of my
>M.E thesis. Most of the aliasing analysis I have seen does not take care
>of pointers to array locations.
>
>For example, Aliasing output doesn't distinguish between the below
>statements.
>
> int *a,b[10];
>
> a = &b[0];
> a = &b[5];
>
> If the range of arrays can be properly incorporated in the
>aliasing analysis then probably this analysis can be done. Has anybody
>done any work in this regard?


      I like to separate the pointer analysis problem into two (not quite)
distinct subproblems:


      1. pointers to stack/static vars (e.g. as shown above)
      2. pointers to dynamically-allocated storage (i.e. p = malloc(...))


Arrays fall into both categories, so you have to decide which you want to
solve because I view category #2 as being harder (principally because you
have no easy way of uniquely naming malloced storage). I should mention
(if it's not already obvious :-) that this type of analysis is very hard
to do in C, given for example C's pointer arithmetic (a++) and C's
less-restrictive style of parameter passing as compared to Fortran (it is
true that in Fortran you can assume that parameters are distinct, isn't
it?).


      I have lots of references on pointer analysis, but I'll try to shorten
them down to what I think is particularly relevant to pointers and arrays.
This list is by no means complete. Happy reading :-)


    - joe


####################### refs ############################


@INPROCEEDINGS{Guarna,
    AUTHOR = "Vincent A. {Guarna Jr.}",
    TITLE = "A Technique for Analyzing Pointer and Structure References
                      in Parallel Restructuring Compilers",
    BOOKTITLE =
        "Proceedings of the International Conference on Parallel Processing",
    VOLUME = "2",
    YEAR = "1988",
    PAGES = "212-220"
    }


[ See V's TR from U. of Illinois for longer version of this paper. ]


@Conference{Smith91,
        AUTHOR = "L. Smith",
        TITLE = "Vectorizing {C} Compilers: How Good Are They?",
        Booktitle = "Proceedings of Supercomputing '91",
        PAGES = "544--553",
        YEAR = "November 1991"
}


[ Smith discusses how far we still have to go. ]


@Conference{LMSS91,
        AUTHOR = "J. Loeliger and R. Metzger and M. Seligman and S. Stroud",
        TITLE = "Pointer Target Tracking - An Empirical Study",
        Booktitle = "Proceedings of Supercomputing '91",
        PAGES = "14-23",
        YEAR = "November 1991"
}


[ Loeliger et al. discuss impl for Convex's interprocedural C compiler,
    mostly an overview of approach. ]


@InProceedings{Miprac92,
    author = "W. Ludwell {Harrison III} and Z. Ammarguellat",
    title = "A Program's Eye View of {Miprac}",
    editor = "D. Gelernter and A. Nicolau and D. Padua",
    booktitle = "Proceedings of the 5th Workshop on Languages and Compilers
                              for Parallel Computing",
    year = 1992,
    month = "August",
    pages = "339--353",
    note = "Available as Yale Tech Report {YALEU/DCS/RR-915}"
}


[ Uses abstract interpretation to "do it all" in terms of pointer analysis;
    very expensive but complete. ]


@Conference{Landi92,
        AUTHOR = "W. Landi and B. Ryder",
        TITLE = "A Safe Approximation Algorithm for Interprocedural
                          Pointer Aliasing",
        Booktitle = "Proceedings of the {SIGPLAN} '92 Conference on
                                  Programming Language Design and Implementation",
        Pages = "235--248",
        YEAR = "June 1992"
}


[ Can't remember if they discuss arrays in particular or not, but a good
    one to read. ]


@TechReport{Maryam93,
AUTHOR = "M. Emami",
TITLE = "A Practical Interprocedural Alias Analysis for an
                                                Optimizing/Parallelizing Compiler",
INSTITUTION = "School of Computer Science, {McGill} University",
YEAR = "September 1993",
                NUMBER = "Masters Thesis"
}


[ Has been implemented as part of McGill's McCat C compiler, a TR is
    available for FTp but I don't know the details -- Chris, Rakesh? ]


@Conference{CBC93,
        AUTHOR = "J. Choi and M. Burke and P. Carini",
        TITLE = "Efficient Flow-Sensitive Interprocedural Computation of
                          Pointer-Induced Aliases and Side-Effects",
        Booktitle = "Proceedings of the {ACM} 20th Symposium on Principles
                                  of Programming Languages",
        PAGES = "232--245",
        YEAR = "January 1993"
}


[ I think they discuss handing arrays... ]


--
Joe Hummel
ICS Graduate Student, UC Irvine
Internet: jhummel@ics.uci.edu
--

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