[LLVMdev] alias set collapse and LICM

[Daniel Berlin]

On Fri, Jun 12, 2015 at 2:03 PM, Andrew Trick <atrick at apple.com> wrote:
>
> On Jun 12, 2015, at 1:51 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>
> So, you can't have disjoint sets, and have one of set that says "i
> access everything". Because it would contain everything :)
>
> Thus, I assume by your description you meant "we want to maintain
> multiple disjoint partitions of the same set of accesses" (which is
> not quite the same as just having one special partition).
>
> When one partition is a refinement of the other (as should be the case
> here), this is known as the nested set union problem, and in fact,
> some very recent research was done into it:
>
> http://www.cs.princeton.edu/~dhlarkin/papers/esa14-nested-set-union.pdf
>
>
> I’m suggesting that the tracker have a special set that is not included in
> the partition and assumed to alias with everything in the partition. So we
> would have a partition over the subset of memory accesses that are actually
> interesting. All the sets in that partition are disjoint. The set outside of
> the partition is not. Every time you query for aliasing, you need to check
> if one of the accesses is in the special set.

Ah, so this seems identical to what Sanjoy suggested initially :)