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 On Fri, Jun 12, 2015 at 1:00 PM, Andrew Trick <atrick at apple.com> wrote:> >> On Apr 27, 2015, at 3:44 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: >> >>> Can you explain why the alias sets are collapsed into one here? >> >> If I'm reading the code correctly, it is because the readonly call >> aliases all of %a, %b and %c. Since two pointers can be in two >> different alias sets only if they do not alias, %a has to be in the >> same alias set as the read only call and so does %b and %c. >> Therefore, all of them have to be in the same alias set. >> >>> Can that collapsing simply be avoided for read-only calls without creating a second alias set? >> >> I have not yet come up with a simple scheme to solve that problem >> within AliasSetTracker. Obviously, that does not mean that there >> isn't one. > > I never saw a good conclusion to this thread. Clearly, collapsing all of the alias sets whenever the loop contains a call with “AnyWhere” ModRef behavior is not an effective design. AliasSet partitions need to remain disjoint, but that doesn’t mean all memory access needs to be partitioned. There should be one special set of accesses that simply alias with everything without causing the partitions to collapse. I haven’t thought through how to make this change with our AliasSetTracker API though. > > Andy
> 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 <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. Andy> On Fri, Jun 12, 2015 at 1:00 PM, Andrew Trick <atrick at apple.com> wrote: >> >>> On Apr 27, 2015, at 3:44 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: >>> >>>> Can you explain why the alias sets are collapsed into one here? >>> >>> If I'm reading the code correctly, it is because the readonly call >>> aliases all of %a, %b and %c. Since two pointers can be in two >>> different alias sets only if they do not alias, %a has to be in the >>> same alias set as the read only call and so does %b and %c. >>> Therefore, all of them have to be in the same alias set. >>> >>>> Can that collapsing simply be avoided for read-only calls without creating a second alias set? >>> >>> I have not yet come up with a simple scheme to solve that problem >>> within AliasSetTracker. Obviously, that does not mean that there >>> isn't one. >> >> I never saw a good conclusion to this thread. Clearly, collapsing all of the alias sets whenever the loop contains a call with “AnyWhere” ModRef behavior is not an effective design. AliasSet partitions need to remain disjoint, but that doesn’t mean all memory access needs to be partitioned. There should be one special set of accesses that simply alias with everything without causing the partitions to collapse. I haven’t thought through how to make this change with our AliasSetTracker API though. >> >> Andy-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150612/f6dba762/attachment.html>
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 :)