[tree-ssa] alias analysis

[law@redhat.com]

In message <1045149809.10501.18.camel@frodo>, Diego Novillo writes:
 >On Tue, 2003-02-11 at 23:41, law@redhat.com wrote:
 >> In message <20030211203337.GA6202@tornado.toronto.redhat.com>, Diego Novill
 >o wr
 >> ites:
 >>  >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.
 >> 
 >To get into that situation you would need a program with tens of
 >thousands of *different* types and tens of thousands of different
 >variables of those types.  If you got that kind of program, I bet you
 >you will lose no matter what you do.
Precisely.


 >> The reason my code tends to produce faster overall alias analysis is 
 >> because we avoid computing any may aliasing information for load-load
 >> situations.
 >> 
 >Faster than what we have now?  At this point I will need to see the
 >patch :)  Right now we are so fast mainly because we bag most
 >addressables and dereferences together.
Yup.  My scheme is faster than what we have now.  

FWIW, after my various improvements to CCP, alias analysis has become the
clear CPU hog again as far as the tree optimizers are concerned
(with gimplification running a close second).  And I know how to make
mine even faster and probably use less memory as well :-)


 >What I would like to avoid is getting into the situation where we start
 >to implement various additional heuristics to the type-based analyzer
 >instead of relying on the PTA code.  I think I'd rather have a good PTA
 >implementation.  The type-based analyzer was something to get by in the
 >meantime, really.
Conceptually you should think of PTA as a way to prune the aliases 
found by type analysis.  In all likelihood they're going to have to
work together.


jeff