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

[Diego Novillo <dnovillo at redhat dot com>]

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.

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.

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 can look at the other testcases you mention and find more cases where
> aliasing analysis is very conservative and file the bugs for them.  This
> seems like a better plan than just changing the representation to work
> around the fact the may-alias sets are big.
> 
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.

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.

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.

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.