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
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
On Fri, Jun 12, 2015 at 2:58 PM, Philip Reames <listmail at philipreames.com> wrote:> > > 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.Interesting, i knew it was bad from work on GVN, i didn't realize it was that bad.> Where does MemorySSA stand at this point? I don't > believe it's landed yet has it? >I lost a bunch of weeks due to vacation and other fires, but it should go in in the next week or two.> 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.I agree. I was just wondering if we couldn't solve the problem without trying to redesign alias-set tracker, since, as i'm sure you realize, the AST problem is inherently #loads * #stores if you want fully-precise answers. For anything less, my experience is that you can never come up with enough special cases. Someone always finds reasonable cases that you are still collapsing if you don't do the queries, and they either then want a new optimization pass that uses the info in a different way to do the same thing, or to just add "that one more special case" to AST (Let's call this "the basicaa problem" :P) Interestingly, at worse, memoryssa's data structures can give you all the ref/mod/modref'ing instructions in a block anyway (which saves you some amount of useless walking), even if you don't rely on memoryssa for dependence info.