Re: [tree-ssa] alias analysis

[law at redhat dot com]

In message <1045613408.1867.19.camel@frodo>, Diego Novillo writes:
 >On Fri, 2003-02-14 at 19:12, law@redhat.com wrote:
 >
 >>  >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.  
 >> 
 >Faster to compute aliasing, or faster when combined with the SSA
 >builder?  If you are trying to improve times that are in the fractions
 >of a second for a multi-second compile, I think you're wasting your
 >time.  We have much bigger performance problems in the branch, don't you
 >think?
Faster overall.  ie, any extra time spent in the SSA builder is recovered
by significantly faster alias analysis.

While there are other issues that can and should be addressed, the aliasing
code (once my remaining CPP fixes are installed) is the slowest part of the
tree-ssa path as a whole and is taking a significant amount of CPU time.

To put it in perspective, over 2% of our time building cc1 is spent in the
tree alias analysis code.  That's a hell of a lot better than we used to
be, but 2% frankly is way too much.

IMHO if any part of the SSA path is taking more than 1% of the total 
compilation time, then it needs to be looked at very carefully.  While
it's great to have the ability to do more complex analysis and optimizations
using tree-ssa, we have to be very aware of introducing more slow code
into the compiler.  It's very important to use good algorithms and 
implementations, otherwise we're going to be introducing a lot of crap
that nobody will ever use.

 >> 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 :-)
 >> 
 >Now you lost me again.  Why are you so interested in making alias
 >analysis a CPU hog?  We were trying to do the opposite!
Before my changes to CCP it was the slowest part of the SSA path, taking
on the order of 20 seconds for my components of cc1 test (out of a 
total of around 700 seconds).  Now CCP is down to around 4 seconds for
that same test.

Alias analysis takes 13 seconds for that test and gimplification takes
around 15 seconds.  Neither are affected by my changes.  But both clearly
need to be worked on further as each accounts for about 2% of our total
compilation time and are the biggest cpu hogs in the SSA path.

By no means am I looking to slow things down -- what's happening is
merely a matter of taking the worst offenders, making them fast,
then continuing to iterate.  With my CCP changes, CCP gets under
the radar again.  With CCP off the radar screen, it's time to look
at another hog -- which happens to be our aliasing code.

 >>  >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.
 >> 
 >I always thought that TBA was a way of pruning PTA.  You first do a
 >quick TBA query, if that fails, you do PTA.
Either way, our TBA is too bloody slow, even with your nice changes
from a couple weeks ago.  The amount of useless work we do in TBA needs
to be reduced.

jeff