[LLVMdev] alias set collapse and LICM

[Andrew Trick]

> On Jun 12, 2015, at 2:06 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
> 
> 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 :)

I think he suggested maintaining two partitions, one for Refs and one for Mods. ModRef accesses would be in both partitions. That might also be helpful, but might not be necessary if all the readonly calls are simply removed from the partition.

Andy