llvm dev - Nov 2014 - [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

Hal, a couple of questions:

1. Do you preserve alias to stores+loads derived through a different
@llvm.noalias call which has *different* scope metadata? Couldn't that be
treated similarly to S+Ls derived from other identified objects?

2. Can you describe the case for explicitly preventing the intrinsic being
hoisted out of a loop? Since the intrinsic generates a new pointer,
wouldn't the interesting cases be handled by avoiding commoning of the
intrinsic?


Raúl E Silvera | SWE | rsilvera at google.com | *408-789-2846*


On Thu, Nov 13, 2014 at 7:23 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141114/13cdbccb/attachment.html>

----- 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: Friday, November 14, 2014 10:34:39 AM
> Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias
metadata
> 
> 
> 
> Hal, a couple of questions:
> 
> 
> 1. Do you preserve alias to stores+loads derived through a different
> @llvm.noalias call which has different scope metadata? Couldn't that
> be treated similarly to S+Ls derived from other identified objects?
>From a different scope? No. Here's why:
  int i = ...;
  T a, b;
  T * y1 = ..., y2 = ...
  {
    T * restrict x = y1;
    a = x[i];
  }
  {
    T * restrict x = y2;
    b = x[i];
  }

which becomes:

  int i = ...;
  T a, b;
  T * y1 = ..., y2 = ...
  T * x1 = @llvm.noalias(y1, !scope1);
  a = x1[i]; // alias.scope !scope1
  T * x2 = @llvm.noalias(y2, !scope2);
  b = x2[i]; // alias.scope !scope2

but can we assume that 'x1[i]' does not alias with 'x2[i]'? No.

Now one possible design here is to solve this problem by mutual dominance, but
to do that, we'd need to make code motion around the @llvm.noalias calls
highly restricted. I'd like to allow for as much data motion as possible.
> 
> 
> 2. Can you describe the case for explicitly preventing the intrinsic
> being hoisted out of a loop? Since the intrinsic generates a new
> pointer, wouldn't the interesting cases be handled by avoiding
> commoning of the intrinsic?
>  
No, here's why. Take the following example:
  T * y = ...;
  for (int i = 0; i < 1600; ++i) {
    T * restrict x = y;
    T t = x[i];
    t += 1;
    x[i] = t;
  }

which becomes something like:

  T * y = ...;
  for (int i = 0; i < 1600; ++i) {
    T * x = @llvm.noalias(y, !scope1)
    T t = x[i]; // alias.scope !scope1
    t += 1;
    x[i] = t; // alias.scope !scope1
  }

now we need to make sure that the call to @llvm.noalias is not hoisted out of
the loop. In order to do that, we tag it as writing (at least to y). The problem
is that, as noted in the original e-mail, when looking across loop iterations
(as the loop vectorizer must do), it is important to be able to test whether or
not the call to @llvm.noalias dominates the loop in question. This example is
over-simplified (because there is only one pointer used in the loop), but
imagine there are several such pointers used. Does that make sense?

Thanks again,
Hal
> 
> 
> 
> 
> 
> 
> Raúl E Silvera | SWE | rsilvera at google.com | 408-789-2846
> 
> 
> On Thu, Nov 13, 2014 at 7:23 PM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> ----- 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
> _______________________________________________
> 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