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

>
> > 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];
> > }
> >
> > 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.
>
It does. You can assume x2 is not aliased to A and still get well-defined
semantics, precisely because A is not referenced in the scope of x2. That
refinement would only get you into trouble if A is referenced in the scope
of x2, which would trigger UB.

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 does require dataflow barriers on entrance/exits to the scope,
but those can be made no worse than the original code.

Aliasing x2 to A is not only unnecessary, but also pessimistic because in
general you do not have access to the dynamic scope of the restricted
pointer.

>   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.
>
Agreed. So will your approach be able to catch both cases? It seemed to me
it wouldn't be able to catch the second one because it would have a
different scope, but probably I'm missing something.

Thanks for your patience,

> >
>
> --
> 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/20141117/9bfe9d46/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: Monday, November 17, 2014 11:26:57 AM
> 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];
> > }
> > 
> > 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.
> 
> 
> 
> It does. You can assume x2 is not aliased to A and still get
> well-defined semantics, precisely because A is not referenced in the
> scope of x2. That refinement would only get you into trouble if A is
> referenced in the scope of x2, which would trigger UB.
I don't understand exactly what you're saying here. You can do that at
the source level where you still have the original blocks. The problem is that,
at the IR level, these blocks don't remain separate basic blocks, and the
distinction then matters.
> 
> 
> 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.

This does require dataflow barriers on
> entrance/exits to the scope, but those can be made no worse than the
> original code.
These don't turn into general scheduling barriers anyway. They'll be
tagged as writing to memory, yes, but like with @llvm.assume, they'll get
special treatment in BasicAA and a few other places so they don't hurt code
motion too badly.
> 
> 
> 
> Aliasing x2 to A is not only unnecessary, but also pessimistic
It is pessimistic, but only in the sense that the restrict qualifier does not
say anything about it.
> because in general you do not have access to the dynamic scope of
> the restricted pointer.
> 
> 
> 
> 
> 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.
> 
> Agreed. So will your approach be able to catch both cases? It seemed
> to me it wouldn't be able to catch the second one because it would
> have a different scope, but probably I'm missing something.
Yes, it will catch it. Just as in the current metadata design, the scope of each
access is really a list of scopes. The accesses in the inner blocks get tagged
with both the inner and the outer scopes, so they pick up the restrict from the
outer scope.
> 
> 
> Thanks for your patience,
> 
Not a problem; I appreciate the feedback!

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