Re: [tree-ssa] New type-based aliasing (was: More CFG improvements)

[law at redhat dot com]

In message <20030206134524.GA1735@tornado.toronto.redhat.com>, Diego Novillo wr
ites:
 >Precisely.  It's because variables tend to cluster in the same
 >alias set that we can do this so quickly.
Clearly I'm missing something.  Which is fine.  I can be rather dense
at times.


 >Instead of comparing every variable against every variable, we
 >compare their alias sets.  The new algorithm builds an array of
 >alias sets where each entry represents a group of variables that
 >have conflicting types.  It works in two phases:
 >
 >(1) Register alias sets for every INDIRECT_REF.  If an
 >    INDIRECT_REF is found to conflict with more than one alias
 >    set (I and J), the entries for I and J are merged into one.
 >
 >    This pass is O(I x S).  Where I is the number of INDIRECT_REF
 >    variables in the program and S the number of non-conflicting
 >    types.  In the GCC sources, S is a very small number (1-3).
 >
 >(2) Associate addressables and INDIRECT_REFs to one of the sets
 >    built in (1).  Variables are added to the first entry in the
 >    alias sets array that conflicts with it.
 >
 >    This pass is O((A + I) x S) where A is the number of
 >    addressable variables.  I and S are as above.
So, conceptually if we're going to use the same scheme, but get better
information out of it we could do the following:

  1. Register alias sets for every memory write (via INDIRECT_REFs,
     LHS of a MODIFY_EXPR is addressable, calls and asms).

  2. Associate reads (via INDIRECT_REF, reads of an addressable, calls
     and asms) with one of the sets built in 1.  These reads would be
     added to the first entry in the alias sets array that it conflicts
     with.


This would allow us to get much more accurate information (like who 
really cares about a may alias created by a pair of loads? :-)  For
20001226-1.c that should allow us to disambiguate every INDIRECT
from every other INDIRECT.

The downside of that is we expose a hell of a lot more objects to the
PHI insertion routines, which in turn causes 20001226-1.c to blow back
up  :(  Luckily, I've got changes here to fix that with better PHI
insertion.


My plan is to get the updated PHI insertion stuff flushed out today, then
flush out my improvements to the aliasing code, then pop back to the 
bitmap vs varray discussion :-)

Jeff