[LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata

[Hal Finkel]

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