[LLVMdev] alias set collapse and LICM

[Sanjoy Das]

On Mon, Apr 27, 2015 at 4:21 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
> You can't win here (believe me, i've tried, and better people than me have
> tried, for years :P).
> No matter what you do, the partitioning will never be 100% precise.  The
> only way to solve that in general is to pairwise query over the
> partitioning.
>
> Your basic problem is that all of the alias analyses do not come up with the
> same partitioning of the heap.
>
> Worse, some are not even transitive, or even symmetric.

Am I correct in saying that the lack of transitivity fundamentally
cannot be helped -- a MayAlias composed with a MayAlias is not a
MayAlias.  The simplest example of this I can come up with is {A ,
C?A:B , B} where A `NoAlias` B and C is a runtime value that cannot be
computed at compile-time.  Then A `MayAlias` C?A:B and C?A:B
`MayAlias` B but A `NoAlias` B.

> This means one single variable may be in multiple disjoint alias sets in
> reality.

Agreed.  I did not propose solving the problem within ASTracker for
this very reason.

> (For example, GEP, PHI will give you different AA results than PHI, GEP in
> some cases. That is mostly a FIXME, but there are plenty of cases you can
> come up with where info tells you something about one variable and it's
> relationship to another, but not to a third. The non-symmetric case is
> rarer, but again, possible.)
>
> Let's say you modify AliasSetTracker to not collapse, and handle multiple
> disjoint partitions at once.
>
> (Here is here i will draw the equivalence between this and what we've done
> before in GCC :) )
>
> The only way to maintain correctness (in general) and not collapse is to
> maintain multiple alias sets, and say which are affected by which
> instructions.
>
> (IE you have 1 instruction, and it may MOD 5 different alias sets, each of
> which represents a different partitioning of the heap).
>
> You will discover very quickly, that for most partitioning you can think of,
> the cost of maintaining the alias sets over a set of instructions with is
> greater than the cost of additional queries you may come up with in the
> first place
>
> In other words, depending on how precise your partitioning you may have
> variables that clobber 10 or 20 or 30 of the disjoint alias sets.  Handling
> this is a lot more expensive than saying "hey, i want to move this one load
> up another instruction. Does it really conflict?".  This is because you
> really only care about individual aliases in the alias set at any given
> time, but unless you go through all the addresses ahead of time, and had a
> way to say "okay alias set tracker, i only care about variable x, y, z, and
> even then, only x in block a, y in block b, etc", you are paying the cost of
> doing whatever queries are necessary to prove something about *all*
> variables in an alias set.
>
> MemorySSA was essentially built with this problem in mind (and thus, tries
> to provide chains that let you do querying on.  You ask it about a load, it
> can O(1) tell you the nearest dominating thing that MOD's it (IE to which
> getModRefInfo(Instruction, Location) says Mod).

So my proposal is somewhat related to what you're suggesting --
tracking the stores through a separate ASTracker lets me basically ask
a conservative version of getModRefInfo over the entire loop body.
And given that the loop body will be strongly connected, I think the
list of clobbering stores reported by MemorySSA will be exactly equal
to the list of stores reported by AST, control flow should not matter
since everything in the loop body reaches everything else.

-- Sanjoy