Re: RFC: Memory SSA. A redesign of the virtual operand scheme.

[Andrew Pinski <pinskia at physics dot uc dot edu>]

> 
> On 03/08/06 15:05, Andrew Pinski wrote:
> 
> > Is there a reason why not tune the aliasing anaysis to return more liberal results
> > instead of changing the representation?
> > 
> Yes, as I tried to explain on IRC, alias analysis is an undecidable
> problem.  It is impossible in general to compute an exact points-to set
> for a given pointer.  Even if you reduce the may-alias sets to a
> minimum, you can still end up with tens or hundreds of elements in the
> may-alias sets.

Yes grouping solves that issue and in fact we do grouping already and
seems to work fine.  As I will mention below grouping in alias1 is just
bad as the may_alias sets are huge.  In alias2, it is a different story
and actually works correctly as far as I can tell.


> Even if your alias sets are small, the current representation does not
> scale well when the code has many pointer dereferences involving the
> alias sets.  Suppose that you have a perfectly small may-alias set with
> 3 elements and 50,000 IL instructions that make a load/store through the
> pointer.  This will generate 150,000 virtual operands.  66% of those are
> not necessary.

Wait are you saying that there are testcases with that large number of
load/stores, that seems crazy in general and seems like not a case which
we should be looking into and fixing.

> Currently, we try to avoid this explosion by a grouping heuristic which
> will flip around the relation between alias tags and aliased symbols
> (that's when you see SMTs being used in virtual operands).
> 
> That reduces the amount of virtual operators significantly, but causes
> even more loss of aliasing precision (distinct members of the alias set
> start affecting each other).
> 
> As an experiment, try disabling the grouping and the .GLOBAL_VAR
> heuristic and see the results.

I noticed while looking through both tramp3d and PR8361, that most of
the functions which did grouping in alias1 did not do grouping in
alias2.  This in itself says that we obvious don't have precise even
may-alias sets for alias1.  One way of fixing this would be have a
"quick and dirty" DCE and CCP which only acts on registers.


> Sure, this is helpful.  But don't confuse an optimization problem with
> the representation problem.  The current representation does not scale
> well when the may-alias sets are large or when there are many pointer
> dereferences in the code.  This problem is essentially non-solvable
> (that's the undecidable part of the problem), so we need to fix the
> representation to avoid the scaling issues.

But the scaling issue has all to do with the may-alias sets being large.
You are saying the scaling issue is not coupled to the may-alias sets being
large but that is not true, look at what normal code does.  95% of the time
the may-alias set is larger than it should be and not that we have too
many loads and stores.
Now if there are a large number of load/stores that is a different issue
and really is not an issue as the code is just crazy at that point.


> The proposal does *nothing* to alleviate our precision problems.  It
> does two main things: (a) Provides a mechanism for plugging in
> precision-enhancing analyses, (b) Provides better scaling for
> pointer-heavy and/or imprecise aliasing results.  There are other goals
> I have in mind to help passes that introduce new pointers like ivopts or
> the vectorizer that I think are easier to implement with this design.

Yes those two cases are problematic but I suspect can be avioded currently
even without many changes.

> Adding more precise analysis is great but they come with a cost.  As we
> make them more sophisticated, we may even reach a point where we turn
> some of them off at lower optimization levels.  This should not
> translate to increased memory usage because of an explosion of may-aliases.

Depends, what I have been finding are mostly agruments comming into the function
cannot alias local variable issues.  The other issue, I found look like they can
be solved by doing CCP/DCE before the first may_alias.  One more issue I found
is really a call clobbering issue which causes us to call clobber stuff because
of the SMT being call clobbered.  A different issue I found a while back is 
flow sensitive call clobber would actually lower down the number of VOPs in general.

> I strongly encourage you to read up on alias analysis.  Since you keep
> coming back to the same confused point, I guess that I have not been
> able to explain sufficiently why the two things are orthogonal.  The
> references I included in the text should be a good starting point.

Now if you were talking about solving the case where there are lots of
loads/store, your proposal would be fine but that is not the common
case in any of the cases you mentioned in your proposal. 

-- Pinski