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

[Hal Finkel]

----- Original Message -----
> From: "Philip Reames" <listmail at philipreames.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Friday, November 14, 2014 12:27:58 PM
> Subject: Re: [LLVMdev] Upcoming Changes/Additions to Scoped-NoAlias metadata
> 
> +1
> 
> The design proposal seems reasonable; I have a couple of comments on
> implementation.
> 
> On 11/13/2014 04:44 PM, Hal Finkel 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. 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. I was hoping this
> > avoid this part of the design space, but I don't see any way
> > around it -- only some non-hoistable instruction can model a
> > control dependence.
> There have been several related ideas being talked about recently. If
> possible, it'd be nice to arrive at something fairly general.
> 
> Andy Trick and I were talking about the possibility of a more general
> control dependent metadata holder at the dev meeting. 

I know ;) -- Andy and I talked about it too.

> The basic idea
> is
> that you'd have an intrinsic something like "void
> llvm.tag_metadata(any_ty %value, !metadata !?)"   The semantics would
> be
> that the given metadata applies to the given value at the specific
> location.  By combing this with existing forms of metadata, this
> converts each from being a property of a value to being a property of
> a
> value at a particular location.  Implementation wise, it would be
> extremely similiar to the existing llvm.assume intrinsic.

I like this idea, I don't think it works for this case (unfortunately). Explained below...

> 
> Your current proposal uses the data dependence off the intrinsic,
> whereas I was thinking using something closer to the assume
> mechanism.
> Andy had previously put forth an idea (in the 'Optimization hints for
> "constant" loads' thread) for a similar intrinsic to create a new
> value
> with a data dependence tied to a function with control dependence.
>  (To
> make scoping !invariant possible.)  I can see appeal in both schemes,
> but it seems like most folks are leaning towards the data dependent
> model.

The data dependence is easier to find, but harder on the optimizer (because the intrinsic appears opaque to anything not taught to look through it). For @llvm.assume, using a data dependence really was not possible (the assumption could involve many values, which to return? and if all of them, looking through all of the insert/extractvalue instructions would have been painful). There are two issues here that I see with using a control dependence alone. First, it might be too easy to lose. For example, let's say we have:

  foo(T * x) {
    T * restrict y = x - 1;
    y[0] = 0;
    y[1] = 1;
    ...
  }

if we take the control dependence model, and do something like this:

  foo(T * x) {
    T * y = x - 1;
    @llvm.noalias(x - 1, !scope1);
    y[0] = 0;
    y[1] = 1;
    ...
  }

but the optimizer will likely make this into:

  foo(T * x) {
    T * y = x - 1;
    @llvm.noalias(x - 1, !scope1);
    x[-1] = 0;
    x = 1;
    ...
  }

and, effectively, the noalias information will be lost for the second access. That's why I picked a data dependence here. Now you might think that we could get around this by canonicalizing @llvm.noalias(x - 1, !scope1) into @llvm.noalias(x, !scope1), but that's not really legal either. Actually, it's worse than that, it is really important to partition the users of the @llvm.noalias from other uses of the pointer. Here's my canonical example:

void foo(T * restrict x, T * restrict y) {
  for (int i = 0; i < 1600; ++i)
    x[2*i+1] = y[2*i] + 1;
}

now imagine inlining a call of foo(q, q). This is allowed because the accesses based on x and those based on y are disjoint, but this cannot be modeled safely with the control-dependence and a single scope alone.

[Coincidentally, this is the second time today I've used this example; see http://llvm.org/bugs/show_bug.cgi?id=21556 for the other place, which you might also find interesting].

> 
> Do you think it makes sense to roll this all into one family of
> intrinsics?  Or do you see something in your proposed use which
> wouldn't
> work for other types of metadata?

I do want this, as a separate matter, but I don't think it necessarily works here.

> 
> Other example use cases:
> - !invariant loads mixed with initialization of the same location
> - !nonnull and !range facts recorded by a language frontend
> 
> p.s. For the sake of completeness, Andy and I were also talking about
> a
> version of this idea for function attributes as well.  This would
> give
> us the ability to say things like "if this value is non-null, it is
> dereferenceable to size X".

Yep. I certainly care about dereferenceability too ;)

Thanks again,
Hal

> 
> Philip
> 
> 
> 

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