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

[Hal Finkel]

----- Original Message -----
> From: "Raul Silvera" <rsilvera at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Chandler Carruth" <chandlerc at google.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Monday, December 1, 2014 11:36:59 AM
> Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
> 
> 
> Thanks for the answers, Hal. I kept forgetting that you annotate the
> references in the scope.
> 
> 
> I agree with your previous points. The main advantage of preserving
> the scope end is that it would apply the restrict against references
> introduced by further inlining. IIUC on your scheme that doesn't
> happen as the newly inlined references will be missing the scope
> metadata.

I was planning on keeping the current logic within the inliner that will adjust for that... if you inline a callsite with scope metadata attached, it will add it to all of the memory accessing instructions that result from the inlining.

> 
> 
> About N4150, I agree your scheme is needed to implement it.

Okay, thanks!

> Another
> idea for extending C99 restrict to C++ might be to annotate pointer
> class members as "owned" or "unique", to allow the restrict property
> to propagate through.
> 

Agreed. I like the simple expressive power of the current proposal -- we'll see if I still feel that way once I've completed the implementation ;)

 -Hal

> 
> Raúl E Silvera | SWE | rsilvera at google.com | 408-789-2846
> 
> 
> On Tue, Nov 25, 2014 at 10:43 AM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> ----- Original Message -----
> > From: "Raul Silvera" < rsilvera at google.com >
> > To: "Hal Finkel" < hfinkel at anl.gov >
> > Cc: "Chandler Carruth" < chandlerc at google.com >, "LLVM Developers
> > Mailing List" < llvmdev at cs.uiuc.edu >
> > Sent: Monday, November 24, 2014 7:20:04 PM
> > Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias
> > metadata
> > 
> > 
> > I'm going to have to read N4150 before commenting on your second
> > point, but in the meantime, a few questions. In the original
> > proposal, if you have:
> > 
> > 
> > T A,B;
> > void foo(T *restrict a, T* restrict b) {
> > A = *b;
> > *a = A;
> > }
> > 
> > 
> > How is this going to be modeled so that B is aliased to *a and *b,
> > but A isn't? What if the references to A are in a call made from
> > foo, which will be inlined later on?
> 
> Within the current AA framework, this question has no well-defined
> meaning. AA only answers queries sensibly regarding values that are
> simultaneously live and referenced at some point in the function's
> control flow. Metadata aside, even with the current function
> argument attributes, querying alias('B', '*b') will respond with
> NoAlias (for both values, llvm::isIdentifiedObject will return true
> -- it will return true for both GlobalVariables and for noalias
> arguments).
> 
> This is another example of why you cannot use our current AA
> framework for IPA, doing so simply does not make sense. The
> metadata/intrinsics scheme I've proposed does not change this.
> 
> > 
> > 
> > Also, what if the reference is in a side path, like this:
> > 
> > 
> > T A, B;
> > void foo(T *restrict a, T *restrict b, bool c) {
> > T tmp = *b;
> > if (c) {
> > A = tmp;
> > }
> > *a = *b;
> > }
> > 
> > 
> > Will you alias A to *a and *b? Seems to me you have to, as foo(&A,
> > &B, false) has well-defined semantics.
> 
> No, and it does not do so now. Querying A or B (global variables) vs.
> *a or *b will return NoAlias. There is no point in the CFG of this
> function where an object accessed through *a or *b can legally be A
> or B.
> 
> Now to the proposed metadata/intrinsics, let's assume that A and B
> are local variables in the caller. It is true that *a and *b will be
> based on a @llvm.noalias result, but that noalias result will only
> be used if the access is tagged with the associated metadata scope
> (which will be true for *a, *b and the A within the inlined
> function, but not true otherwise, thus the semantics will be
> identical after inlining.
> 
> > On the scheme I proposed
> > there is no need, as the exit barrier would separate *a from
> > references to A after the call. Not aliasing A *b will save the
> > reload of *b after the conditional.
> 
> I agree your scheme will also capture this.
> 
> Thanks again,
> Hal
> 
> 
> 
> > 
> > 
> > Thanks
> > 
> > 
> > 
> > 
> > 
> > 
> > Raúl E Silvera | SWE | rsilvera at google.com | 408-789-2846
> > 
> > 
> > On Fri, Nov 21, 2014 at 8:35 PM, Hal Finkel < hfinkel at anl.gov >
> > wrote:
> > 
> > 
> > ----- Original Message -----
> > > From: "Raul Silvera" < rsilvera at google.com >
> > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > Cc: "Chandler Carruth" < chandlerc at google.com >, "LLVM Developers
> > > Mailing List" < llvmdev at cs.uiuc.edu >
> > > Sent: Tuesday, November 18, 2014 9:09:40 PM
> > > Subject: Re: [LLVMdev] Upcoming Changes/Additions to
> > > Scoped-NoAlias
> > > metadata
> > > 
> > 
> > 
> > > I preserve them only weakly... I don't want full barriers; in
> > > fact,
> > > I
> > > plan to add InstCombine code to combine calls to @llvm.noalias
> > > (it
> > > will also take a list of scopes, not just one, so this is
> > > possible).
> > > The goal is to have as few barriers as possible.
> > > 
> > > 
> > > Good.
> > > 
> > > > > Going further, logically the intrinsic should return a
> > > > > pointer
> > > > > to
> > > > > a
> > > > > new object, disjoint from all other live objects. It is not
> > > > > aliased
> > > > > to A, and is well defined even if it contains &A because A is
> > > > > not
> > > > > referenced in the scope.
> > > > 
> > > > This is essentially what is done, but only for accesses in the
> > > > scope
> > > > (or some sub-scope). I don't think the semantics allow for what
> > > > you're suggesting. The specific language from 6.7.3.1p4 says:
> > > > 
> > > > [from C]
> > > > During each execution of B, let L be any lvalue that has &L
> > > > based
> > > > on
> > > > P. If L is used to
> > > > access the value of the object X that it designates, ...,
> > > > then the following requirements apply: ... Every other lvalue
> > > > used to access the value of X shall also have its address based
> > > > on
> > > > P.
> > > > [end from C]
> > > > 
> > > > Where B is defined in 6.7.3.1p2 to be, essentially, the block
> > > > in
> > > > which the relevant declaration appears. And we can really only
> > > > extrapolate from that to the other access in that block, and
> > > > not
> > > > to
> > > > the containing block.
> > > > 
> > > > 
> > > > Inside that block
> > > > (the lifetime of P) , it is safe to assume that X is
> > > > disjoint from an arbitrary live object
> > > > A. It if was
> > > > 
> > > > n't
> > > > , either:
> > > > - A is independently referenced inside the block, so there is
> > > > UB
> > > > and
> > > > all bets are off.
> > > > - A is not independently referenced inside the blo ck,
> > > > so t here are no pairs of accesses to incorrectly reorder as
> > > > all
> > > > accesses to A in
> > > > the block are done through P. You just need to delimit the
> > > > block
> > > > with dataflow barriers
> > > > , summar iz
> > > > ing the effect of the block at entry/exit.
> > > 
> > > Okay, I think I agree with you assuming that we put in entry/exit
> > > barriers to preserve the block boundaries. I'd specifically like
> > > to
> > > avoid that, however.
> > > 
> > > I'm not proposing full code motion barriers, only punctual
> > > dataflow
> > > use/defs to signal entry/exit to the scope.
> > > 
> > > 
> > > 
> > > Logically, entering the scope transfers the pointed data into a
> > > new
> > > unique block of memory, and puts its address on the restrict
> > > pointer. Exiting the scope transfers it back. Of course you do
> > > not
> > > want to actually allocate a new object and move the data, but you
> > > can use these semantics to define the scope entry/exit
> > > intrinsics.
> > > Their contribution to dataflow is only limited to the content of
> > > the
> > > address used to initialize the restricted pointer. These would be
> > > lighter than the proposed intrinsic as they would not have
> > > specialized control-flow ​restrictions.
> > 
> > Thanks for explaining, I now understand what you're proposing.
> > 
> > > 
> > > This approach makes the restrict attribute effective against all
> > > live
> > > variables without having to examine the extent of the scope to
> > > collect all references, which is in general impractical.
> > 
> > I think you've misunderstood this. For restrict-qualified local
> > variables, every memory access within the containing block (which
> > is
> > everything in the function for function argument restrict-qualified
> > pointers) get tagged with the scope. This is trivial to determine.
> > 
> > > It also
> > > removes the need for scope metadata, as there would be no need to
> > > name the scopes.
> > 
> > Indeed.
> > 
> > > 
> > > 
> > > Anyway, this is just a general alternate design, since you were
> > > asking for one.
> > 
> > Yes, and thank you for doing so.
> > 
> > > I'm sure still would take some time/effort to map it
> > > onto the LLVM framework.
> > 
> > That does not seem too difficult, the question is really just
> > whether
> > or not it gives us what we need...
> > 
> > > 
> > 
> > So in this scheme, we'd have the following:
> > 
> > void foo(T * restrict a, T * restrict b) {
> > *a = *b;
> > }
> > 
> > T * x = ..., *y = ..., *z = ..., *w = ...;
> > foo(x, y);
> > foo(z, w);
> > 
> > become:
> > 
> > T * x = ..., *y = ..., *z = ..., *w = ...;
> > 
> > T * a1 = @llvm.noalias.start(x); // model: reads from x (with a
> > general write control dep).
> > T * b1 = @llvm.noalias.start(y);
> > *a1 = *b1;
> > @llvm.noalias.end(a1, x); // model: reads from a1, writes to x.
> > @llvm.noalias.end(b1, y);
> > 
> > T * a2 = @llvm.noalias.start(z);
> > T * b2 = @llvm.noalias.start(w);
> > *a2 = *b2;
> > @llvm.noalias.end(a2, z);
> > @llvm.noalias.end(b2, w);
> > 
> > This does indeed seem generally equivalent to the original proposal
> > in the sense that the original proposal has an implicit ending
> > barrier at the last relevant derived access, and here we have
> > explicit ending barriers. The advantage is the lack of metadata
> > (and
> > associated implementation complexity). The disadvantage is that we
> > have additional barriers to manage, and these are write barriers on
> > the underlying pointers. It is not clear to me this would make too
> > much difference, so long as we aggressively hoisted the ending
> > barriers to just after the last use based on their 'noalias'
> > operands.
> > 
> > So this is relatively appealing, and I think would not be a bad way
> > to model C99 restrict (extending the scheme to handle
> > mutually-ambiguous restrict-qualified pointers from aggregates
> > seems
> > straightforward). It does not, however, cover cases where the
> > region
> > of guaranteed disjointness (for lack of a better term) is not
> > continuous. This will come up when implementing a scheme such as
> > that in the current C++ alias-set proposal (N4150). To construct a
> > quick example, imagine that our implementation of std::vector is
> > annotated such that (assuming the standard allocator) each
> > std::vector object's internal storage has a distinct alias set, and
> > we have:
> > 
> > std::vector<T> x, y;
> > ...
> > T * q = &x[0];
> > for (int i = 0; i < 1600; ++i) {
> > x[i] = y[i];
> > *q += x[i];
> > }
> > 
> > so here we know that the memory accesses inside the operator[] from
> > x
> > and y don't alias, but the alias-set attribute does not tell us
> > about the relationship between those accesses and the *q. The point
> > of dominance, however, needs to associated with the declaration of
> > x
> > and y (specifically, we want to preserve the dominance over the
> > loop). A start/end barrier scheme localized around the inlined
> > operator[] functions would not do that, and placing start/end
> > barriers around the entire live region of x and y would not be
> > correct. I can, however, represent this using the metadata scheme.
> > 
> > Thanks again,
> > Hal
> > 
> > > 
> > > 
> > > 
> > > Regards,
> > 
> > 
> > > 
> > > 
> > > 
> > > 
> > 
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> > 
> > 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory