[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: Tuesday, November 18, 2014 11:23:25 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.
> 
> 
> Agreed. My point is that if you preserve the
> block boundaries yo u
>  
> can use
> better a
>  liasing for the restricted pointers. You are already preserving the
>  blo ck entry
> by introducing the intrinsic
> ; the block exits could be similarly preserved.

I preserve them only weakly... I don't want full barriers; in fact, I plan to add InstCombine code to combine calls to @llvm.noalias (it will also take a list of scopes, not just one, so this is possible). The goal is to have as few barriers as possible.

> 
> 
> 
> > 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.
> 
> 
> Inside that block
> (the lifetime of P) , it is safe to assume that X is
> disjoint from an arbitrary live object
>  A. It if was
>  
> n't
>  , either:
> - A is independently referenced inside the block, so there is UB and
> all bets are off.
> - A is not independently referenced inside the blo ck,
> so t here are no pairs of accesses to incorrectly reorder as all
> accesses to A in
>  the block are done through P. You just need to delimit the block
>  with dataflow barriers
> , summar iz
> ing the effect of the block at entry/exit.

Okay, I think I agree with you assuming that we put in entry/exit barriers to preserve the block boundaries. I'd specifically like to avoid that, however.

> 
> 
> 
> This is similar to the way dummy args are implemented on Fortran
> compilers, extended to arbitrary scopes.

Interesting.

Thanks again,
Hal

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

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