Hal Finkel
2014-Nov-14 00:44 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
Hi everyone, As many of you might know, LLVM now has scoped noalias metadata (http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata) -- it allows us to preserve noalias function argument attributes when inlining, in addition to allowing frontends to add otherwise non-deducible aliasing properties to memory accesses. This currently works well, but needs a change and an intrinsic, as I'll explain below. First, the problem: Currently, ScopedNoAliasAA.cpp is a little bit too much like TypeBasedAliasAnalysis.cpp in that when the metadata is used to return an aliasing result, the Size passed in the AliasAnalysis::Location object is ignored. This is not a problem if the Size is equal to (or less than) the size of the access with which the metadata was originally associated, but if the Size is larger than that associated with the original access, the result might not be correct. Fixing this is not hard for regular accesses (we can also store the size of the original access), although is harder for arbitrary function calls. Now you might think that constructing an AliasAnalysis::Location object with a size larger than the original is uncommon, and in some sense it is, but this is exactly what the loop vectorizer does when partitioning memory accesses in a loop into potential aliasing sets. The loop vectorizer partitions a loop's memory accesses by taking the access's natural Location object, and setting the size to UnknownSize (the largest representable size) and querying using that infinite-size Location. The logic is that if two access don't alias with both sizes set to infinity, then they must always come from disjoint sets of underlying objects, and because the vectorizer only considers access pointers that are linear recurrences, implies that the accesses don't alias both within and across loop iterations. So how does this work now? Consider this function: void foo(float * restrict a, float * restrict b) { for (int i = 0; i < 1600; ++i) a[i] = b[i] + 1; } (note that restrict at the C level becomes a noalias function argument attribute at the IR level) With the scoped noalias metadata, the aliasing information from the 'a' and 'b' function arguments is preserved such that 'a[i]' and 'b[i]' are tagged as not aliasing. There is nothing wrong with this, and in fact, when the loop vectorizer uses its infinite-sized queries on 'a[i]' and 'b[i]', and that returns NoAlias, that result is also not wrong. It is not wrong, however, because the noalias function argument attributes, logically associated with the function entry block, dominate the loop ('a[i]' is based on 'a' for all 'i', and similarly for 'b[i]'). Now here's the problematic case: void inner(float * restrict a, float * restrict b) { *a = *b + 1; } void foo(float * a, float * b) { for (int i = 0; i < 1600; ++i) inner(a+i, b+i); } The problem here is that the noalias function argument attributes on 'inner', when inlined into the loop body, do not dominate the loop; they apply to pointers within each loop iteration, not across loop iterations. But because the generated noalias metadata is essentially the same as in the previous case, and as noted ScopedNoAliasAA.cpp ignores the Location's Size, the loop vectorizer's infinite-sized alias queries return NoAlias as in the previous case. This is a bug. Making ScopedNoAliasAA.cpp check the size of the original access (as it should) would fix this problem, but it will also prevent ScopedNoAliasAA.cpp from returning NoAlias for the first case were we'd like it to do so. So to summarize, scoped-noalias metadata does not preserve enough dominance information to truly capture the full semantics of the noalias function argument attributes. After discussing this with Chandler offline last week, here's the proposed solution: instead of having both !alias.scope and !noalias metadata, we'll have only !alias.scope metadata and an intrinsic: i8* @llvm.noalias(i8* ptr, !metadata !?) where the metadata argument corresponds to a list of !alias.scopes. The idea being that the pointer returned by this intrinsic, and all pointers derived from it, are assumed not to alias with memory accesses tagged with any of the associated !alias.scope metadata entries. This intrinsic needs to carry control dependencies (it cannot be hoisted out of a loop, for example) -- in this sense it is very much like @llvm.assume. And like @llvm.assume, we'll need to add logic to various passes to ignore it as appropriate so that it does not block optimizations unnecessarily. I was hoping this avoid this part of the design space, but I don't see any way around it -- only some non-hoistable instruction can model a control dependence. With this in place, it will be possible to build a loop-aware AA interface capable of answering questions like: Does location A in some loop iteration alias with location B in any iteration (which is really what the vectorizer wants to know). This interface can check whether the @llvm.noalias dominates the loop while answering this query. On the bright side, the metadata will be simpler (or at least less verbose) than the current design. If anyone has suggestions on an alternative design, please share! :-) Regardless, the current design needs to change: Just fixing it to check the size of the location will make it non-useful for the loop vectorizer and otherwise cripple it for mod-ref queries against arbitrary function calls. Thanks again, Hal -- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Chandler Carruth
2014-Nov-14 01:02 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
On Thu, Nov 13, 2014 at 4:44 PM, Hal Finkel <hfinkel at anl.gov> wrote:> After discussing this with Chandler offline last week, here's the proposed > solution: instead of having both !alias.scope and !noalias metadata, we'll > have only !alias.scope metadata and an intrinsic: i8* @llvm.noalias(i8* > ptr, !metadata !?) where the metadata argument corresponds to a list of > !alias.scopes. The idea being that the pointer returned by this intrinsic, > and all pointers derived from it, are assumed not to alias with memory > accesses tagged with any of the associated !alias.scope metadata entries.Could you give examples? I don't quite follow this. I had thought that the analysis would be slightly different. My expectation is that each noalias argument pointer would turn into a @llvm.noalias call, all of them sharing a single metadata "scope". And then any loads or stores through a pointer derived from a @llvm.noalias call would never alias loads and stores derived through a different @llvm.noalias call which had the same scope metadata.> This intrinsic needs to carry control dependencies (it cannot be hoisted > out of a loop, for example) -- in this sense it is very much like > @llvm.assume. And like @llvm.assume, we'll need to add logic to various > passes to ignore it as appropriate so that it does not block optimizations > unnecessarily.We should do something to make this simpler. I think we should have an intrinsic inst base class that assume, lifetime, and other intrinsics which do not represent actual code in the final program derive from so that we don't have to update these lists all over the place. If we need 2 tiers to model assume & noalias as distinct from the lifetime or other intrinsics, fine. We should have high-level categories that can be tested and updated. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141113/a23a0a0e/attachment.html>
Hal Finkel
2014-Nov-14 03:23 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
----- Original Message -----> From: "Chandler Carruth" <chandlerc at google.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Thursday, November 13, 2014 7:02:58 PM > Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata > > > > > > On Thu, Nov 13, 2014 at 4:44 PM, Hal Finkel < hfinkel at anl.gov > > wrote: > > > After discussing this with Chandler offline last week, here's the > proposed solution: instead of having both !alias.scope and !noalias > metadata, we'll have only !alias.scope metadata and an intrinsic: > i8* @llvm.noalias(i8* ptr, !metadata !?) where the metadata argument > corresponds to a list of !alias.scopes. The idea being that the > pointer returned by this intrinsic, and all pointers derived from > it, are assumed not to alias with memory accesses tagged with any of > the associated !alias.scope metadata entries. > > > Could you give examples? I don't quite follow this. I had thought > that the analysis would be slightly different. My expectation is > that each noalias argument pointer would turn into a @llvm.noalias > call, all of them sharing a single metadata "scope". And then any > loads or stores through a pointer derived from a @llvm.noalias call > would never alias loads and stores derived through a different > @llvm.noalias call which had the same scope metadata.Sorry, I did not state this very well. Yes, that's correct, with the exception that "derived through a different> @llvm.noalias call which had the same scope metadata" should also be supplemented with being derived from other identified objects (just like with a noalias argument attribute).> > > This intrinsic needs to carry control dependencies (it cannot be > hoisted out of a loop, for example) -- in this sense it is very much > like @llvm.assume. And like @llvm.assume, we'll need to add logic to > various passes to ignore it as appropriate so that it does not block > optimizations unnecessarily.> We should do something to make this simpler. I think we should have > an intrinsic inst base class that assume, lifetime, and other > intrinsics which do not represent actual code in the final program > derive from so that we don't have to update these lists all over the > place. If we need 2 tiers to model assume & noalias as distinct from > the lifetime or other intrinsics, fine. We should have high-level > categories that can be tested and updated.Agreed. There is come commonality here that can be exploited for at least some of the passes. -Hal -- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Philip Reames
2014-Nov-14 17:57 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
On 11/13/2014 05:02 PM, Chandler Carruth wrote:> > This intrinsic needs to carry control dependencies (it cannot be > hoisted out of a loop, for example) -- in this sense it is very > much like @llvm.assume. And like @llvm.assume, we'll need to add > logic to various passes to ignore it as appropriate so that it > does not block optimizations unnecessarily. > > > We should do something to make this simpler. I think we should have an > intrinsic inst base class that assume, lifetime, and other intrinsics > which do not represent actual code in the final program derive from so > that we don't have to update these lists all over the place. If we > need 2 tiers to model assume & noalias as distinct from the lifetime > or other intrinsics, fine. We should have high-level categories that > can be tested and updated.Agreed. Specific to this point, I've seen a number of cases in discussion recently where a notion of a intrinsic which is control dependent on surrounding control flow, but does not read or write memory would be useful. It really feels like that's what the current implementation of llvm.assume has become and likely what this proposal would require. Maybe it's time to introduce a notion of an arbitrary non-memory control dependence? Cases that come to mind: - invariant.* - lifetime.* - float point state changes (this last one might need a stronger restriction than the others) Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141114/1c4980be/attachment.html>
Philip Reames
2014-Nov-14 18:27 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
+1 The design proposal seems reasonable; I have a couple of comments on implementation. On 11/13/2014 04:44 PM, Hal Finkel wrote:> After discussing this with Chandler offline last week, here's the proposed solution: instead of having both !alias.scope and !noalias metadata, we'll have only !alias.scope metadata and an intrinsic: i8* @llvm.noalias(i8* ptr, !metadata !?) where the metadata argument corresponds to a list of !alias.scopes. The idea being that the pointer returned by this intrinsic, and all pointers derived from it, are assumed not to alias with memory accesses tagged with any of the associated !alias.scope metadata entries. This intrinsic needs to carry control dependencies (it cannot be hoisted out of a loop, for example) -- in this sense it is very much like @llvm.assume. And like @llvm.assume, we'll need to add logic to various passes to ignore it as appropriate so that it does not block optimizations unnecessarily. I was hoping this avoid this part of the design space, but I don't see any way around it -- only some non-hoistable instruction can model a control dependence.There have been several related ideas being talked about recently. If possible, it'd be nice to arrive at something fairly general. Andy Trick and I were talking about the possibility of a more general control dependent metadata holder at the dev meeting. The basic idea is that you'd have an intrinsic something like "void llvm.tag_metadata(any_ty %value, !metadata !?)" The semantics would be that the given metadata applies to the given value at the specific location. By combing this with existing forms of metadata, this converts each from being a property of a value to being a property of a value at a particular location. Implementation wise, it would be extremely similiar to the existing llvm.assume intrinsic. Your current proposal uses the data dependence off the intrinsic, whereas I was thinking using something closer to the assume mechanism. Andy had previously put forth an idea (in the 'Optimization hints for "constant" loads' thread) for a similar intrinsic to create a new value with a data dependence tied to a function with control dependence. (To make scoping !invariant possible.) I can see appeal in both schemes, but it seems like most folks are leaning towards the data dependent model. Do you think it makes sense to roll this all into one family of intrinsics? Or do you see something in your proposed use which wouldn't work for other types of metadata? Other example use cases: - !invariant loads mixed with initialization of the same location - !nonnull and !range facts recorded by a language frontend p.s. For the sake of completeness, Andy and I were also talking about a version of this idea for function attributes as well. This would give us the ability to say things like "if this value is non-null, it is dereferenceable to size X". Philip
Hal Finkel
2014-Nov-14 20:45 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
----- Original Message -----> From: "Philip Reames" <listmail at philipreames.com> > To: "Hal Finkel" <hfinkel at anl.gov>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Friday, November 14, 2014 12:27:58 PM > Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata > > +1 > > The design proposal seems reasonable; I have a couple of comments on > implementation. > > On 11/13/2014 04:44 PM, Hal Finkel wrote: > > After discussing this with Chandler offline last week, here's the > > proposed solution: instead of having both !alias.scope and > > !noalias metadata, we'll have only !alias.scope metadata and an > > intrinsic: i8* @llvm.noalias(i8* ptr, !metadata !?) where the > > metadata argument corresponds to a list of !alias.scopes. The idea > > being that the pointer returned by this intrinsic, and all > > pointers derived from it, are assumed not to alias with memory > > accesses tagged with any of the associated !alias.scope metadata > > entries. This intrinsic needs to carry control dependencies (it > > cannot be hoisted out of a loop, for example) -- in this sense it > > is very much like @llvm.assume. And like @llvm.assume, we'll need > > to add logic to various passes to ignore it as appropriate so that > > it does not block optimizations unnecessarily. I was hoping this > > avoid this part of the design space, but I don't see any way > > around it -- only some non-hoistable instruction can model a > > control dependence. > There have been several related ideas being talked about recently. If > possible, it'd be nice to arrive at something fairly general. > > Andy Trick and I were talking about the possibility of a more general > control dependent metadata holder at the dev meeting.I know ;) -- Andy and I talked about it too.> The basic idea > is > that you'd have an intrinsic something like "void > llvm.tag_metadata(any_ty %value, !metadata !?)" The semantics would > be > that the given metadata applies to the given value at the specific > location. By combing this with existing forms of metadata, this > converts each from being a property of a value to being a property of > a > value at a particular location. Implementation wise, it would be > extremely similiar to the existing llvm.assume intrinsic.I like this idea, I don't think it works for this case (unfortunately). Explained below...> > Your current proposal uses the data dependence off the intrinsic, > whereas I was thinking using something closer to the assume > mechanism. > Andy had previously put forth an idea (in the 'Optimization hints for > "constant" loads' thread) for a similar intrinsic to create a new > value > with a data dependence tied to a function with control dependence. > (To > make scoping !invariant possible.) I can see appeal in both schemes, > but it seems like most folks are leaning towards the data dependent > model.The data dependence is easier to find, but harder on the optimizer (because the intrinsic appears opaque to anything not taught to look through it). For @llvm.assume, using a data dependence really was not possible (the assumption could involve many values, which to return? and if all of them, looking through all of the insert/extractvalue instructions would have been painful). There are two issues here that I see with using a control dependence alone. First, it might be too easy to lose. For example, let's say we have: foo(T * x) { T * restrict y = x - 1; y[0] = 0; y[1] = 1; ... } if we take the control dependence model, and do something like this: foo(T * x) { T * y = x - 1; @llvm.noalias(x - 1, !scope1); y[0] = 0; y[1] = 1; ... } but the optimizer will likely make this into: foo(T * x) { T * y = x - 1; @llvm.noalias(x - 1, !scope1); x[-1] = 0; x = 1; ... } and, effectively, the noalias information will be lost for the second access. That's why I picked a data dependence here. Now you might think that we could get around this by canonicalizing @llvm.noalias(x - 1, !scope1) into @llvm.noalias(x, !scope1), but that's not really legal either. Actually, it's worse than that, it is really important to partition the users of the @llvm.noalias from other uses of the pointer. Here's my canonical example: void foo(T * restrict x, T * restrict y) { for (int i = 0; i < 1600; ++i) x[2*i+1] = y[2*i] + 1; } now imagine inlining a call of foo(q, q). This is allowed because the accesses based on x and those based on y are disjoint, but this cannot be modeled safely with the control-dependence and a single scope alone. [Coincidentally, this is the second time today I've used this example; see http://llvm.org/bugs/show_bug.cgi?id=21556 for the other place, which you might also find interesting].> > Do you think it makes sense to roll this all into one family of > intrinsics? Or do you see something in your proposed use which > wouldn't > work for other types of metadata?I do want this, as a separate matter, but I don't think it necessarily works here.> > Other example use cases: > - !invariant loads mixed with initialization of the same location > - !nonnull and !range facts recorded by a language frontend > > p.s. For the sake of completeness, Andy and I were also talking about > a > version of this idea for function attributes as well. This would > give > us the ability to say things like "if this value is non-null, it is > dereferenceable to size X".Yep. I certainly care about dereferenceability too ;) Thanks again, Hal> > Philip > > >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Hal Finkel
2015-Apr-30 17:19 UTC
[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
Hi everyone, I've posted an initial set of patches to implement this feature (and handle block-level restrict-qualified pointers in Clang). LLVM: http://reviews.llvm.org/D9375 http://reviews.llvm.org/D9376 http://reviews.llvm.org/D9377 http://reviews.llvm.org/D9378 http://reviews.llvm.org/D9379 http://reviews.llvm.org/D9380 http://reviews.llvm.org/D9381 http://reviews.llvm.org/D9382 http://reviews.llvm.org/D9383 http://reviews.llvm.org/D9384 http://reviews.llvm.org/D9385 http://reviews.llvm.org/D9386 http://reviews.llvm.org/D9387 http://reviews.llvm.org/D9388 http://reviews.llvm.org/D9391 http://reviews.llvm.org/D9392 http://reviews.llvm.org/D9393 http://reviews.llvm.org/D9394 http://reviews.llvm.org/D9395 http://reviews.llvm.org/D9396 http://reviews.llvm.org/D9397 http://reviews.llvm.org/D9398 http://reviews.llvm.org/D9400 http://reviews.llvm.org/D9401 Clang: http://reviews.llvm.org/D9403 -Hal ----- Original Message -----> From: "Hal Finkel" <hfinkel at anl.gov> > To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Thursday, November 13, 2014 6:44:54 PM > Subject: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata > > Hi everyone, > > As many of you might know, LLVM now has scoped noalias metadata > (http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata) > -- it allows us to preserve noalias function argument attributes > when inlining, in addition to allowing frontends to add otherwise > non-deducible aliasing properties to memory accesses. This currently > works well, but needs a change and an intrinsic, as I'll explain > below. > > First, the problem: Currently, ScopedNoAliasAA.cpp is a little bit > too much like TypeBasedAliasAnalysis.cpp in that when the metadata > is used to return an aliasing result, the Size passed in the > AliasAnalysis::Location object is ignored. This is not a problem if > the Size is equal to (or less than) the size of the access with > which the metadata was originally associated, but if the Size is > larger than that associated with the original access, the result > might not be correct. Fixing this is not hard for regular accesses > (we can also store the size of the original access), although is > harder for arbitrary function calls. > > Now you might think that constructing an AliasAnalysis::Location > object with a size larger than the original is uncommon, and in some > sense it is, but this is exactly what the loop vectorizer does when > partitioning memory accesses in a loop into potential aliasing sets. > The loop vectorizer partitions a loop's memory accesses by taking > the access's natural Location object, and setting the size to > UnknownSize (the largest representable size) and querying using that > infinite-size Location. The logic is that if two access don't alias > with both sizes set to infinity, then they must always come from > disjoint sets of underlying objects, and because the vectorizer only > considers access pointers that are linear recurrences, implies that > the accesses don't alias both within and across loop iterations. > > So how does this work now? Consider this function: > > void foo(float * restrict a, float * restrict b) { > for (int i = 0; i < 1600; ++i) > a[i] = b[i] + 1; > } > (note that restrict at the C level becomes a noalias function > argument attribute at the IR level) > > With the scoped noalias metadata, the aliasing information from the > 'a' and 'b' function arguments is preserved such that 'a[i]' and > 'b[i]' are tagged as not aliasing. There is nothing wrong with this, > and in fact, when the loop vectorizer uses its infinite-sized > queries on 'a[i]' and 'b[i]', and that returns NoAlias, that result > is also not wrong. It is not wrong, however, because the noalias > function argument attributes, logically associated with the function > entry block, dominate the loop ('a[i]' is based on 'a' for all 'i', > and similarly for 'b[i]'). > > Now here's the problematic case: > > void inner(float * restrict a, float * restrict b) { > *a = *b + 1; > } > void foo(float * a, float * b) { > for (int i = 0; i < 1600; ++i) > inner(a+i, b+i); > } > > The problem here is that the noalias function argument attributes on > 'inner', when inlined into the loop body, do not dominate the loop; > they apply to pointers within each loop iteration, not across loop > iterations. But because the generated noalias metadata is > essentially the same as in the previous case, and as noted > ScopedNoAliasAA.cpp ignores the Location's Size, the loop > vectorizer's infinite-sized alias queries return NoAlias as in the > previous case. This is a bug. Making ScopedNoAliasAA.cpp check the > size of the original access (as it should) would fix this problem, > but it will also prevent ScopedNoAliasAA.cpp from returning NoAlias > for the first case were we'd like it to do so. > > So to summarize, scoped-noalias metadata does not preserve enough > dominance information to truly capture the full semantics of the > noalias function argument attributes. > > After discussing this with Chandler offline last week, here's the > proposed solution: instead of having both !alias.scope and !noalias > metadata, we'll have only !alias.scope metadata and an intrinsic: > i8* @llvm.noalias(i8* ptr, !metadata !?) where the metadata argument > corresponds to a list of !alias.scopes. The idea being that the > pointer returned by this intrinsic, and all pointers derived from > it, are assumed not to alias with memory accesses tagged with any of > the associated !alias.scope metadata entries. This intrinsic needs > to carry control dependencies (it cannot be hoisted out of a loop, > for example) -- in this sense it is very much like @llvm.assume. And > like @llvm.assume, we'll need to add logic to various passes to > ignore it as appropriate so that it does not block optimizations > unnecessarily. I was hoping this avoid this part of the design > space, but I don't see any way around it -- only some non-hoistable > instruction can model a control dependence. > > With this in place, it will be possible to build a loop-aware AA > interface capable of answering questions like: Does location A in > some loop iteration alias with location B in any iteration (which is > really what the vectorizer wants to know). This interface can check > whether the @llvm.noalias dominates the loop while answering this > query. > > On the bright side, the metadata will be simpler (or at least less > verbose) than the current design. > > If anyone has suggestions on an alternative design, please share! :-) > Regardless, the current design needs to change: Just fixing it to > check the size of the location will make it non-useful for the loop > vectorizer and otherwise cripple it for mod-ref queries against > arbitrary function calls. > > Thanks again, > Hal > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > > _______________________________________________ > 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
Possibly Parallel Threads
- [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
- [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
- [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
- [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
- [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata