Re: [tree-ssa] alias analysis

[law at redhat dot com]

In message <20030211203337.GA6202@tornado.toronto.redhat.com>, Diego Novillo wr
ites:
 >Oh, I see.  Do you want to be able to rewrite X and Y in this
 >case?  The problem is that since X and Y are aliased, regardless
 >of what their alias is, SSA will refuse to rewrite them.  What we
 >will re-write are the VDEFs to their alias tag.
Well, in that example we certainly wouldn't want to rewrite them --
they're addressable *and* they would be aliased by the virtual store
at the call site.  We would want to continue to rewrite their VDEFs 
the same way we do now.

All we're effectively doing is pruning the set of objects that are
considered aliasing each other by noting that an alias created by
a load-load is totally uninteresting.  I don't see how these changes
necessarily have to interact with what variables we rewrite.

>From the SSA builder's standpoint nothing has to change in this case
as far as I can tell.

 >In this case we would want to split alias sets whose members
 >cannot alias each other.  But this could quickly take us back to
 >quadratic behaviour.  Say we have this initial alias set for X
 >and Y:
No more so than the current algorithm.  We can make the current algorithm
blow up by having a different type for every variable and indirection
for each of those types.  Suddenly you're in the "oh god this sucks"
situation again.

If we make the same simplifying assumption you do for the current code,
namely that the number of types is significantly smaller than the number
of variables & indirections and we make the assumption that most variables
are not addressable, then my code will be roughly equivalent in time
complexity.

Of course that also shows precisely when and how my code would blow up --
if you have code where every variable is a different type with lots of
indirections, then it loses.  Similarly it would lose if we had an 
ungodly number of addressable variables and no pointers which aliased
them (if we have a pointer which aliases the addressables, then the
pointer becomes the tag for the set which includes all the addressables
it may alias).

The reason my code tends to produce faster overall alias analysis is 
because we avoid computing any may aliasing information for load-load
situations.

Also note that my code can be twiddled to degenerate more gracefully by
having addressable VAR_DECLs with the same alias set use the same tag.
That was slightly slower than keeping them separate.

Yes, splitting the sets would work too, but that seems to be avoiding 
the real issue -- creating too many useless alias relationships to begin
with.

Jeff