Re: Fw: [PATCH] ipa aliasing analysis

[Olga Golovanevsky <OLGA at il dot ibm dot com>]

Steven Bosscher <stevenb@suse.de> wrote on 02/05/2005 02:29:22:

> Did you also use this paper by Mayer and Wolfe,
> "InterProcedural Alias Analysis: Implementation and Empirical Results"?
>
> It mentions a mistake in Cooper's paper.  They also use a worklist
> instead of the pair-binding graph (Pi-graph, whatever).  What does your
> implementation use?
>
> Mayer&Wolfe can be downloaded from Citeseer here:
> http://www.cs.ubc.
> ca/local/reading/proceedings/spe91-95/spe/vol23/issue11/spe859.pdf

The algorithm by Cooper and Kennedy (C&K) consists of two phases.
The first phase calculates an alias set for each formal of each
function in the program. To do so the binding graph between
formals is build. The second part uses aliasing info of formals
(collected at first phase) and other considerations (like the same
variable is used as actual parameter for different formals at call site)
to decide about aliasing of pairs of actual parameters at callsite.
This "aliasing-at-callsites" info is used to initialize pair binding
graph built from pair of formals, over which this info is propagated.

The paper by Mayer and Wolfe (M&W) improves the first phase of C&K by
finding strongly connected components. The mistake
you mentioned is also in this part. It also suggest a worklist for
the second phase, that is very similar to what I have been
implemented (although the worklist from M&W is built from triples
(formal1, formal2, function) and mine is built only from functions,
the procedure on an element of worklist passes through all
callsites of the function).

Both papers by M&W and by C&K are fortran oriented.
They do not consider cases were aliasing can be produced from
address taken and derefencing operations. The only aliasing in
their scope is through globals, i.e. alias sets built in first
phase contains only globals.

It was essential for us to be C oriented. Therefore from the first
phase we took only the idea - to figure out the aliasing of
pairs of actual parameters at callsite. For now this is done by very
primitive interprocedural analysis (also part of this patch), but it
can be easily improve. Any kind of interprocedural aliasing
analysis can suit here with some level of precision.

The implementation of second phase is with worklist. We are not
building pair binding graph explicitly, but use the
propagation method similar to ipcp (the algorithm is in
ipaa_propagate_stage function).

> Gr.
> Steven
>