[LLVMdev] alias set collapse and LICM

[Philip Reames]

On 06/12/2015 02:44 PM, Daniel Berlin wrote:
> 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)
Rephrasing LICM's aliasing queries on top of MemorySSA might actually be 
reasonable.  Doing it using the existing MDA would be a non-starter 
performance wise.  Where does MemorySSA stand at this point?  I don't 
believe it's landed yet has it?

Though, the only place LICM tries to place things is the loop 
preheader.  The existing aliasing and guaranteed to execute logic there 
is actually pretty powerful.  It's not clear that MemorySSA is strictly 
better here.
>
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev