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

[Raul Silvera]

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?

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. 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.

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141124/2bddb304/attachment.html>