Re: [tree-ssa] alias analysis

[law at redhat dot com]

In message <1045149809 dot 10501 dot 18 dot camel at frodo>, Diego Novillo writes:
 >
 >> 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.
 >
 >Your patch would refine this by separating load-load aliases.  How can
 >that be faster?  You're adding more checks to the aliasing code :)
 >But I agree with you that it can be comparable in complexity.  If so,
 >I'm all for it.
The first (and most important) thing to realize is that most functions
have more loads than stores.  And in fact, many functions have just loads
and no stores.

To show the effect, let's (just for the sake of argument) look at a
naive alias analysis.

foreach indirect I
  {
    foreach indirect J
      check for conflicts between I & J

    foreach addressable K
      check for conflicts between I & K     
  }

Which performs I * J + I * K checks.  Which is just I * (J + K)
We know that I & J are related from which we get I * (I/2 + K) checks


This algorithm is clearly dominated by I -- the number of indirect
references.  I includes indirects created by both stores and loads.


If you split loads & stores you get something like this:

foreach store S
  {
    foreach store T
      check for conflicts between S & T

    foreach load L
      check for conflicts between S & L
  }


Which is S * (S/2 + L).  Which looks the same until you realize that
typically S will be much smaller than I.  Which is good -- when we
can drastically decrease dominating variable, we get much better 
behavior.


The same concepts apply to the scheme currently on the branch.  We
register alias sets for all the stores, then check the stores & loads
for conflicts with the registered alias sets.  We have to register
far far fewer alias sets because we only register those used by store
instructions.

A secondary effect is that our may alias sets get smaller, meaning
that our cost to manage those sets can go down significantly. ie, we
get far fewer calls to add_may_alias.

The proof is in the pudding so they say.  Separating loads from stores
cuts alias time by nearly 70%.  That's nothing to sneeze at.

 >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.
No heuristics needed.  And remember, you're still going to need type
based alias analysis.

jeff