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

[Hal Finkel]

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