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

>
> 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.
>
​It should, no? by virtue of x2 being restrict you know that *x2 doesn't
alias A, and *x1 is A.​

This example is flawed anyway ​because it only has loads, so the aliasing
isn't that interesting. Something more realistic:
​
  T
​A, B

  T * x1 ​.... // either &A or &B
  T * y2 ​.... // ​
​maybe &A
​  ​
{
    T * restrict x2 = y2;

​*​
x
​1
​ = ...


​*​
x2
​ = ...

  }

​In this case you'll be able to tell *x1 doesn't alias​ *x2, right? How
about if you add restrict to x1?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141114/2aa558b5/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 5:31:24 PM
> Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias
metadata
> 
> 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.
> 
> 
> 
> 
> It should, no? by virtue of x2 being restrict you know that *x2
> doesn't alias A, and *x1 is A.
No, it doesn't. The fact that x2 is restrict does not mean that it does not
alias with any other potential accesses from variables live in its block. It
only means it does not alias with other accesses with that occur in the block
where x2 is live. There is no access to A or x1 in that block, so we can say
nothing about it.
> 
> 
> This example is flawed anyway ​because it only has loads,
Yes, but I'm ignoring that for the time being.
> so the
> aliasing isn't that interesting. Something more realistic:
>  
> 
> 
  T A, B;
  T * x1 = .... // either &A or &B
  T * y2 =​ .... // ​​maybe &A
  {
    T * restrict x2 = y2;
​    *​x1 = ...
​    *​x2 = ...
  }
> 
> 
> 
> In this case you'll be able to tell *x1 doesn't alias​ *x2, right?
In this case, yes, we can conclude that x1 and x2 don't alias (because *x1
and *x2 cannot both legally refer to the same object).
> How about if you add restrict to x1?
The conclusion is the same, but if you add restrict to x1, you don't need it
on x2. x2 is definitely not based on x1, so if x1 is restrict, then we know that
x1 and x2 don't alias.

Thanks again,
Hal
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory