[LLVMdev] alias set collapse and LICM

[Daniel Berlin]

Maybe it's me :)
I read his suggestion as "create one set that tracks all memory
operations", and one set that tracks "mods" he cared about.
That way, he could remove the readonly call from the set of "things he
cared about".  Which is what i read your suggestion as.

(As an even more meta question, it's not clear to me with LICM is
using alias set tracker instead of memory dependence of some sort,
since it's really trying to discover where the memory dependences for
a given load/store are so it knows where it can place things. Instead,
it hands alias set tracker all the things in the loop and says "hey,
is this modded in the loop", which is, IMHO, the wrong way around :P)

On Fri, Jun 12, 2015 at 2:10 PM, Andrew Trick <atrick at apple.com> wrote:
>
>> 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