llvm dev - Nov 2014 - [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata

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

Thanks, Hal... Let me stay on the first question for now.

If we take your example and remove the first restrict:
  T A;
  T * y1 = ..., y2 = ...
  {
    T * x = &A;
    a = x[i];
  }
  {
    T * restrict x = y2;
    b = x[i];
  }

Will we assert that *x1 and *x2 do not alias each other? If so, why is it
OK here and not if the first one is restrict? I believe from a language
perspective you just need the bottom restrict to make the guarantee.

On Fri Nov 14 2014 at 9:48:42 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: 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;
>
> 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141114/05f4615c/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 12:15:51 PM
> Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias
metadata
> 
> Thanks, Hal... Let me stay on the first question for now.
> 
> 
> 
> If we take your example and remove the first restrict:
> T A;
> T * y1 = ..., y2 = ...
> {
> T * x = &A;
> a = x[i];
> }
> {
> T * restrict x = y2;
> b = x[i];
> }
> 
> Will we assert that *x1 and *x2 do not alias each other? If so, why
> is it OK here and not if the first one is restrict?
You don't have x1 and x2 in your example, assuming you mean:

  int i = 0;
  T A;
  T * y2 = ...
  {
    T * x1 = &A;
    a = x1[i];
  }
  {
    T * restrict x2 = y2;
    b = x2[i];
  }

then the answer is no, the fact that x2 is restrict qualified does not allow us
to conclude that &x2[i] and &x1[i] don't alias.
> I believe from a
> language perspective you just need the bottom restrict to make the
> guarantee.
Now assuming that the '...' is not &A, the BasicAA will catch this,
but that's another matter.  You'd need to have the restrict in a parent
block here.

 -Hal
> 
> 
> 
> On Fri Nov 14 2014 at 9:48:42 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: 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;
> 
> 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.
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory