> 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. -- Sanjoy
----- Original Message -----> From: "Sanjoy Das" <sanjoy at playingwithpointers.com> > To: "Charles R Caldarale" <Chuck.Caldarale at unisys.com> > Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Monday, April 27, 2015 5:44:18 PM > Subject: Re: [LLVMdev] alias set collapse and LICM > > > 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.That's correct. OTOH, I think we can loosen this somewhat (having separate Mod and Ref alias sets, for example). We'd need to change the interface, however, and update the clients. Luckily, there are very few clients. -Hal> > > 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. > > -- Sanjoy > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
You can't win here (believe me, i've tried, and better people than me have tried, for years :P). No matter what you do, the partitioning will never be 100% precise. The only way to solve that in general is to pairwise query over the partitioning. Your basic problem is that all of the alias analyses do not come up with the same partitioning of the heap. Worse, some are not even transitive, or even symmetric. This means one single variable may be in multiple disjoint alias sets in reality. (For example, GEP, PHI will give you different AA results than PHI, GEP in some cases. That is mostly a FIXME, but there are plenty of cases you can come up with where info tells you something about one variable and it's relationship to another, but not to a third. The non-symmetric case is rarer, but again, possible.) Let's say you modify AliasSetTracker to not collapse, and handle multiple disjoint partitions at once. (Here is here i will draw the equivalence between this and what we've done before in GCC :) ) The only way to maintain correctness (in general) and not collapse is to maintain multiple alias sets, and say which are affected by which instructions. (IE you have 1 instruction, and it may MOD 5 different alias sets, each of which represents a different partitioning of the heap). You will discover very quickly, that for most partitioning you can think of, the cost of maintaining the alias sets over a set of instructions with is greater than the cost of additional queries you may come up with in the first place In other words, depending on how precise your partitioning you may have variables that clobber 10 or 20 or 30 of the disjoint alias sets. Handling this is a lot more expensive than saying "hey, i want to move this one load up another instruction. Does it really conflict?". This is because you really only care about individual aliases in the alias set at any given time, but unless you go through all the addresses ahead of time, and had a way to say "okay alias set tracker, i only care about variable x, y, z, and even then, only x in block a, y in block b, etc", you are paying the cost of doing whatever queries are necessary to prove something about *all* variables in an alias set. MemorySSA was essentially built with this problem in mind (and thus, tries to provide chains that let you do querying on. You ask it about a load, it can O(1) tell you the nearest dominating thing that MOD's it (IE to which getModRefInfo(Instruction, Location) says Mod). This means algorithms that use it to hoist, if they are looking to place things in positions that dominate the original load, can be done in O(N) overall. It can O(N) tell you the nearest thing (not dominating) that MOD's it, where N is the number of MOD'ing accesses in between the dominating access and the actual MOD'ing access. We could make this O(1) for a space cost (we compute it but throw it away) It can O(N) tell you the farthest *down* you can move something (and give you O(N) the nearest post-dominated thing, or the nearest thing). It can O(1) tell you the nearest set of uses, and the next "MOD'ing access" (IE the next thing to which getModRefInfo(instruction) says Mod). The nearest common postdominator of all of these is a valid placement point for the store, but may not be the farthest down you can move it. But if it's outside the loop, you may not care to try to move it further. This means store sinking algorithms are N^2 to sink as far down as you can (though you can get a cheap place, of course, for O(N)). O(N) is the worst case, you can do some pretty good caching to get better. It's also N=Number of MOD'ing accesses, not N = Number of instructions. They may or may not be the same thing, most of the time they are not. It's possible to get the same time bounds for store sinking as load sinking by building MemorySSI instead of MemorySSA :) On Mon, Apr 27, 2015 at 3:50 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. > > -- Sanjoy > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150427/f5590111/attachment.html>
On Mon, Apr 27, 2015 at 4:21 PM Daniel Berlin <dberlin at dberlin.org> wrote:> You can't win here (believe me, i've tried, and better people than me have > tried, for years :P). > No matter what you do, the partitioning will never be 100% precise. The > only way to solve that in general is to pairwise query over the > partitioning. > > Your basic problem is that all of the alias analyses do not come up with > the same partitioning of the heap. > > Worse, some are not even transitive, or even symmetric. > > This means one single variable may be in multiple disjoint alias sets in > reality. > > (For example, GEP, PHI will give you different AA results than PHI, GEP in > some cases. That is mostly a FIXME, but there are plenty of cases you can > come up with where info tells you something about one variable and it's > relationship to another, but not to a third. The non-symmetric case is > rarer, but again, possible.) > > Let's say you modify AliasSetTracker to not collapse, and handle multiple > disjoint partitions at once. > > (Here is here i will draw the equivalence between this and what we've done > before in GCC :) ) > > The only way to maintain correctness (in general) and not collapse is to > maintain multiple alias sets, and say which are affected by which > instructions. > > (IE you have 1 instruction, and it may MOD 5 different alias sets, each of > which represents a different partitioning of the heap). > > You will discover very quickly, that for most partitioning you can think > of, the cost of maintaining the alias sets over a set of instructions with > is greater than the cost of additional queries you may come up with in the > first place > > In other words, depending on how precise your partitioning you may have > variables that clobber 10 or 20 or 30 of the disjoint alias sets. >This should be "instructions", not variables.> >>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150427/77f1d1d9/attachment.html>
On Mon, Apr 27, 2015 at 4:21 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> You can't win here (believe me, i've tried, and better people than me have > tried, for years :P). > No matter what you do, the partitioning will never be 100% precise. The > only way to solve that in general is to pairwise query over the > partitioning. > > Your basic problem is that all of the alias analyses do not come up with the > same partitioning of the heap. > > Worse, some are not even transitive, or even symmetric.Am I correct in saying that the lack of transitivity fundamentally cannot be helped -- a MayAlias composed with a MayAlias is not a MayAlias. The simplest example of this I can come up with is {A , C?A:B , B} where A `NoAlias` B and C is a runtime value that cannot be computed at compile-time. Then A `MayAlias` C?A:B and C?A:B `MayAlias` B but A `NoAlias` B.> This means one single variable may be in multiple disjoint alias sets in > reality.Agreed. I did not propose solving the problem within ASTracker for this very reason.> (For example, GEP, PHI will give you different AA results than PHI, GEP in > some cases. That is mostly a FIXME, but there are plenty of cases you can > come up with where info tells you something about one variable and it's > relationship to another, but not to a third. The non-symmetric case is > rarer, but again, possible.) > > Let's say you modify AliasSetTracker to not collapse, and handle multiple > disjoint partitions at once. > > (Here is here i will draw the equivalence between this and what we've done > before in GCC :) ) > > The only way to maintain correctness (in general) and not collapse is to > maintain multiple alias sets, and say which are affected by which > instructions. > > (IE you have 1 instruction, and it may MOD 5 different alias sets, each of > which represents a different partitioning of the heap). > > You will discover very quickly, that for most partitioning you can think of, > the cost of maintaining the alias sets over a set of instructions with is > greater than the cost of additional queries you may come up with in the > first place > > In other words, depending on how precise your partitioning you may have > variables that clobber 10 or 20 or 30 of the disjoint alias sets. Handling > this is a lot more expensive than saying "hey, i want to move this one load > up another instruction. Does it really conflict?". This is because you > really only care about individual aliases in the alias set at any given > time, but unless you go through all the addresses ahead of time, and had a > way to say "okay alias set tracker, i only care about variable x, y, z, and > even then, only x in block a, y in block b, etc", you are paying the cost of > doing whatever queries are necessary to prove something about *all* > variables in an alias set. > > MemorySSA was essentially built with this problem in mind (and thus, tries > to provide chains that let you do querying on. You ask it about a load, it > can O(1) tell you the nearest dominating thing that MOD's it (IE to which > getModRefInfo(Instruction, Location) says Mod).So my proposal is somewhat related to what you're suggesting -- tracking the stores through a separate ASTracker lets me basically ask a conservative version of getModRefInfo over the entire loop body. And given that the loop body will be strongly connected, I think the list of clobbering stores reported by MemorySSA will be exactly equal to the list of stores reported by AST, control flow should not matter since everything in the loop body reaches everything else. -- Sanjoy
> 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
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