[tree-ssa] alias analysis

[Daniel Berlin]

On Friday, February 14, 2003, at 07:12  PM, law@redhat.com wrote:

> 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.
>
Yes, but it's likely going to need to be the other way around for speed 
reasons.
PTA, without TBAA, generates orders of magnitudes less aliases that 
need to be pruned, in just as much time as TBAA takes.
Thus, you'd want to use PTA and disambiguate the results using TBAA, as 
it would be faster.
Otherwise, you end up asking PTA about aliases that TBAA can't figure 
out, 206 million times, like we do now, rather than using the results, 
and asking TBAA 100k times about the remaining aliases (or whatever).
Keep that in mind as you are spending time optimizing the type-based 
analyzer.

>
> jeff
>