[tree-ssa] alias analysis

[law@redhat.com]

In message <20030211203337.GA6202@tornado.toronto.redhat.com>, Diego Novillo wr
ites:
 >On Tue, 11 Feb 2003, Jeff Law wrote:
 >
 >>  >>   int x = 5;
 >>  >>   int y = 10;
 >>  >> 
 >>  >>   foo (&x, &y);
 >>  >> 
 >>  >> 
 >>  >> We'd have distinct tags for x & y, even though they have the same alias
 >>  >> set.
 >>  >> 
 >>  >Now you lost me.  I thought you were separating load from store
 >>  >aliases?  Aren't x and y store aliases here?  Or is it load
 >>  >aliases?  I think I need a step-by-step description again :)
 >> They are stores, but they are stores to distinct VAR_DECLs.  There's no
 >> way they can actually alias each other as the underlying objects will
 >> always be distinct.  Ie, there is no way that x = foo will every modify y.

So, just to provide a little more color on the two ways I think we can
improve on the initial generation of may alias code.

As I stated before, both are based on the notion that separating loads
from stores can both speed up the alias analysis phase and provide
more accurate information.    I've already shown data which supports
the belief that we can speed up the compiler.

In the first scheme we keep separate tags for addressable VAR_DECLs
even if they have the same alias set number.  This requires us to
walk all the store tags when checking to see if a load is aliased by
any of the stores.  Note that if we encounter a store via an 
INDIRECT_REF we glob all the stores via addressable VAR_DECLs with
the same alias set number to use the tag for the INDIRECT_REF.

The second scheme is simpler in that we always glob addressable VAR_DECLs
with the same alias set into a single tag.  This can lead to slightly
worse alias information than the first scheme.  Interestingly enough it
also had slightly worse overall performance than the first scheme
(but was still better than the code on the branch).

First I instrumented find_alias_for.  For the current branch sources
it records how often an alias was found or not found when walking the
indirect_refs and how often an alias was found or not found when
walking the addresssables.

Calls for indirect_refs which found an alias          : 79896
Calls for indirect_refs which did not find an alias   :     8
Totals calls for indirect_refs:                       : 79904

Calls for addressable_vars which found an alias       : 16382
Calls for addressable_vars which did not find an alias:   469
Total calls for addressable_vars:                     : 16851

Total calls:                                          : 96755


As you can see the vast majority of calls resulted in finding an
alias.

Then I instrumented the compiler using the two schemes noted
above.  Because the arrays are tracking totally different concepts
than the current branch the numbers below aren't a direct comparison,
but they do give you something to think about:


Calls for stores which found a store alias            : 31665  (31659)
Calls for stores which did not find a store alias     :     0
Total calls for stores                                : 31665


Calls for loads which found a store alias             : 69780  (69932)
Calls for loads which did not find a store alias      :  4801
Total calls for loads                                 : 74581

Total calls                                           : 106246

The number in parenthesis is how many aliases were found -- remember
we can't stop when we find the first alias.    As you can see it
was pretty rare to find a second alias.


For the scheme which separates loads from stores, but always globs
addressable VAR_DECLs we get:

Calls for stores which found an alias                 : 31659
Calls for stores which did not find an alias:         :     0
Total calls for stores                                : 31659

Calls for loads which found an alias                  : 69808
Calls for loads which did not find an alias           :  4773
Total calls for loads                                 : 74581

Total calls                                           : 106240

Note that since this scheme globs, we can stop when we find the
first alias.


So what does all this mean?

First, my scheme surprisingly does 10.5% more calls into find_alias_for.
I say surprising because the compilers with my scheme are both around
1% faster than the current branch.  I suspect, but have not confirmed
that the increase in calls can be accounted for by the fact that
my schemes generate a call for both a load and a store through the same
INDIRECT_REF, but the current sources would generate a single call.

The other difference is the number of calls which resulted in finding
no may aliases.  On the current branch only 0.5% of the calls resulted
in finding no aliases.  Contrast this to my code in which 4.4% of the
calls resulted in not finding an alias (this is a good thing).
Presumably this results in fewer vdef/vuses that need to be created,
rewritten, etc etc.  But I haven't verified this.
[ In a worst case scenario the 4000 disambiguated references could
  come from the 10k extra calls.  I really doubt that's the case, but
  it's definitely possible. ]

Anyway, we could use some flag bits to reduce the redundant calls, which
might give us results more comparable to the current branch sources.

Anyway, I'm going to table this until Diego gets back.  While I don't
think there's an affect on the SSA builder and I think that doing something
in this space is wise, it's clear that there's stuff to hash through.

Jeff