[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, 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