Page MenuHomePhabricator

Scoped NoAlias Metadata
ClosedPublic

Authored by hfinkel on Nov 15 2013, 3:08 PM.

Details

Summary

This patch adds support for scoped noalias metadata. The primary motivations for this feature are:

  1. To preserve noalias function attribute information when inlining
  2. To provide the ability to model block-scope C99 restrict pointers

The second point requires frontend enhancement, and only the first capability is added here. In practice, this patch adds the ability to generally specify noalias memory-access sets, and I'm sure that other frontends will find this useful too. These things are important for vectorization, LICM, instruction scheduling, etc.

First, this is a large patchset; however, it is mostly a formulaic generalization of the current TBAA support. The new alias.scope and noalias metadata act very much like TBAA metadata: references to the associated MDNodes need to be included in AA's Location object, handled by the AA infrastructure, and preserved like TBAA in existing passes. This patch introduces a new structure, AAMDNodes, to hold MDNode pointers to all three of the possible AA MDNodes associated with a memory access (tbaa, alias.scope and noalias), and changes almost all code that deals with MDNode* for TBAA to use the AAMDNodes structure instead. As part of this, I tried to also rename the relevant variables (TBAAInfo -> AAInfo, TBAATag -> AATags, etc.) and update any relevant comments.

As for the metadata itself, alias-analysis scopes are defined similar to TBAA nodes:

!scope0 = metadata !{ metadata !"scope of foo()" }
!scope1 = metadata !{ metadata !"scope 1", metadata !scope0 }
!scope2 = metadata !{ metadata !"scope 2", metadata !scope0 }
!scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 }
!scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 }

Loads and stores can be tagged with an alias-analysis scope, and also, with a noalias tag for a specific scope:

... = load %ptr1, !alias.scope !{ !scope1 }
... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 }

When evaluating an aliasing query, if one of the instructions is associated with an alias.scope id that is identical to the noalias scope associated with the other instruction, or is a descendant (in the scope hierarchy) of the noalias scope associated with the other instruction, then the two memory accesses are assumed not to alias.

Note that is the first element of the scope metadata is a string, then it can be combined accross functions and translation units. The string can be replaced by a self-reference to create globally unqiue scope identifiers.

[Note: This overview is slightly stylized, since the metadata nodes really need to just be numbers (!0 instead of !scope0), and the scope lists are also global unnamed metadata.]

When a function is inlined, the noalias metadata is added to the function: A new unique scope is created for each noalias function parameter. noalias indicates that pointer values based on the argument do not alias pointer values which are not based on it. So we add a new "scope" for each noalias function argument. Accesses using pointers based on that argument become part of that alias scope, accesses using pointers not based on that argument are tagged as noalias with that scope.

Also, existing metadata in the inlined callee may be "cloned" for use by the inlined code. This is necessary because the aliasing scopes are unique to each call site (because of possible control dependencies on the aliasing properties). For example, consider a function: foo(noalias a, noalias b) { *a = *b; } that gets inlined into bar() { ... if (...) foo(a1, b1); ... if (...) foo(a2, b2); } -- now just because we know that a1 does not alias with b1 at the first call site, and a2 does not alias with b2 at the second call site, we cannot let inlining these functons have the metadata imply that a1 does not alias with b2.

The significant code additions are in lib/Analysis/ScopedNoAliasAA.cpp and lib/Transforms/Utils/InlineFunction.cpp (and a few things in lib/IR/Metadata.cpp); the overall amount of new code is actually pretty minimal.

Please review.

Thanks again!

P.S. I know that the LangRef documentation changes are not here yet; if we're okay with the design, then I'll write some (based on the text above).

Diff Detail

Event Timeline

hfinkel updated this revision to Unknown Object (????).Nov 18 2013, 12:27 PM

This diff is the same as the last one, but this time with full context (Manuel Klimek fixed the upload size limit for me).

I'm looking at the tests now, but apart from some comments below, the code looks good to me.

Of course, I'd encourage other people to have a look as well, as I'm no expert in AA.

lib/IR/IRBuilder.cpp
75

Update this comment

106

update this comment

133

update this comment

lib/Transforms/Utils/InlineFunction.cpp
413

Couldn't this be an else on the if block below? It's probably going to evaluate isa<> on each one (at least) anyway.

434

found "no" pointers?

Tests look ok, though I don't like the fact that the metadata nodes are unnamed and unidentified. Would be good to do like TBAA nodes where at least there's a text (even if unused) referring as to what is that node.

Thanks for looking at this! I'll update and rebase soon.

lib/IR/IRBuilder.cpp
75

No, this is still specifically TBAA.

Unlike everywhere else, for IRBuilder, I used three separate function parameters for the (now three) different MD types. This gives enough interface stability that Clang need not be updated with this change (and I assume the same is true of other clients).

106

No, also still TBAA.

133

No, also still TBAA.

lib/Transforms/Utils/InlineFunction.cpp
413

Yes, good point.

434

Yes, thanks!

Okay, good point. I'll come up with some scheme for generating names. Thanks!

hfinkel updated this revision to Unknown Object (????).Dec 13 2013, 3:29 PM

Rebased and updated as per review comments.

The metadata for each scope added by the inliner now has a name derived from the function name and the argument name. These also carry a self reference (to make them unique), but this added name should make the metadata easier to understand. Something like this:

!1 = metadata !{metadata !1, metadata !"hello: %a"}

The form of the metadata that defines each scope is, as before, arbitrary.

Hal rebased this and that got it into my inbox again.

I'll look at the code soon, but I had a high-level comment: this is solving an extremely similar problem to lifetime markers. I would be interested to see to what degree the two should or should not share the same design principles, and why. Maybe Nick should comment on this in general?

I think that this is a good point, and we certainly could think of modeling this with some llvm.noalias.start/llvm.noalias.end intrinsics. I don't think this buys us anything, however:

The issue is that that noalias pointers, after inlining, don't not alias with all other pointers in the function, only those which came from the same original function under the same control dependencies. Consequently, we'd still need some way of specifying with which other pointers the noalias pointers don't alias (it is not generally all of them). We could add some additional intrinsics for tagging these other pointers, and some metadata to tie them together. This looks much like the current solution, but:

  • Involves searching for these intrinsics during AA queries (which seems like it could get expensive)
  • Seems as though it will prevent some useful instruction combining, reordering, etc. without either removing the AA information, or some complicated gymnastics (and just getting this right in all of the relevant passes seems like a large auditing problem).

Done this way does involve more metadata, but I think it is much easier to ensure correctness, yields little overhead in AA, and because passes should drop metadata they don't understand, easier to get right by default.

Ping.

-Hal

  • Original Message -----

From: hfinkel@anl.gov
To: atrick@apple.com, sunfish@google.com, chandlerc@gmail.com, hfinkel@anl.gov
Cc: llvm-commits@cs.uiuc.edu, nrotem@apple.com, "renato golin" <renato.golin@linaro.org>, nlewycky@google.com
Sent: Friday, December 13, 2013 6:30:15 PM
Subject: Re: [PATCH] Scoped NoAlias Metadata

I think that this is a good point, and we certainly could think of
modeling this with some llvm.noalias.start/llvm.noalias.end
intrinsics. I don't think this buys us anything, however:
 
The issue is that that noalias pointers, after inlining, don't not
alias with all other pointers in the function, only those which
came from the same original function under the same control
dependencies. Consequently, we'd still need some way of specifying
with which other pointers the noalias pointers don't alias (it is
not generally all of them). We could add some additional
intrinsics for tagging these other pointers, and some metadata to
tie them together. This looks much like the current solution, but:
  - Involves searching for these intrinsics during AA queries
  (which seems like it could get expensive)
  - Seems as though it will prevent some useful instruction
  combining, reordering, etc. without either removing the AA
  information, or some complicated gymnastics (and just getting
  this right in all of the relevant passes seems like a large
  auditing problem).
 
Done this way does involve more metadata, but I think it is much
easier to ensure correctness, yields little overhead in AA, and
because passes should drop metadata they don't understand, easier
to get right by default.

http://llvm-reviews.chandlerc.com/D2194

atrick accepted this revision.Jan 10 2014, 11:12 PM

Hal, this looks pretty good!

On the design, we could do better that a quadratic search on each query over two lists of AA scopes. But it doesn't seem worth the complexity at this time.

lib/Analysis/ScopedNoAliasAA.cpp
83–86

I personally don't like indenting large class definitions within anonymous namespace. It's unnecessary indentation and I find myself wondering if I'm looking at a nested class.

137–142

I know this is consistent with TBAA, but I find it misleading: Aliases() returns true on an unknown relation. Shouldn't it be called MayAlias()?

169–175

Please put this in a helper instead of repeating it four times:

e.g.

+static bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) {
+ if (!Scopes || !NoAlias)
+ return false;
+ for (unsigned i = 0, ie = Scopes->getNumOperands(); i != ie; ++i) {
+ if (const MDNode *SMD = dyn_cast<MDNode>(Scopes->getOperand(i)))
+ for (unsigned j = 0, je = NoAlias->getNumOperands(); j != je; ++j)
+ if (const MDNode *NAMD = dyn_cast<MDNode>(NoAlias->getOperand(j)))
+ if (!MayAlias(SMD, NAMD))
+ return false;
+ }
+ return true;

test/Transforms/Inline/noalias2.ll
44

is inlined

I'd still really like to hear Nick's thoughts about this based on the
experience with lifetime markers...

Anyways, on a totally unrelated topic:

Andy,

Thanks for the review! I apologize for taking so long to get back to this.

I've attached a revised patch, implementing your suggestions, rebasing, and including a LangRef addition. Unfortunately, I've hit a file upload limit again on phab with the full-context diff (which I've e-mailed Manuel about, but as I recall, he said he's on vacation for two weeks).

-Hal

  • Original Message -----

From: "Andrew Trick" <atrick@apple.com>
To: atrick@apple.com, sunfish@google.com, chandlerc@gmail.com, hfinkel@anl.gov
Cc: llvm-commits@cs.uiuc.edu, nrotem@apple.com, "renato golin" <renato.golin@linaro.org>, nlewycky@google.com
Sent: Saturday, January 11, 2014 1:12:32 AM
Subject: Re: [PATCH] Scoped NoAlias Metadata

Hal, this looks pretty good!
 
On the design, we could do better that a quadratic search on each
query over two lists of AA scopes. But it doesn't seem worth the
complexity at this time.

================
Comment at: lib/Analysis/ScopedNoAliasAA.cpp:82-85
@@ +81,6 @@
+
+namespace {
+ / ScopedNoAliasAA - This is a simple alias analysis
+
/ implementation that uses scoped-noalias metadata to answer
queries.
+ class ScopedNoAliasAA : public ImmutablePass, public AliasAnalysis
{
+ public:


I personally don't like indenting large class definitions within
anonymous namespace. It's unnecessary indentation and I find myself
wondering if I'm looking at a nested class.

================
Comment at: lib/Analysis/ScopedNoAliasAA.cpp:136-141
@@ +135,8 @@
+
+/ Aliases - Test whether the scope represented by A may alias the
+
/ scope represented by B. Specifically, A is the target scope, and
B is the
+/ noalias scope.
+bool
+ScopedNoAliasAA::Aliases(const MDNode *A,
+ const MDNode *B) const {
+
Climb the tree from A to see if we reach B.


I know this is consistent with TBAA, but I find it misleading:
Aliases() returns true on an unknown relation. Shouldn't it be
called MayAlias()?

================
Comment at: lib/Analysis/ScopedNoAliasAA.cpp:168-174
@@ +167,9 @@
+
+ if (AScopes && BNoAlias)
+ for (unsigned i = 0, ie = AScopes->getNumOperands(); i != ie;
++i)
+ if (const MDNode *AMD =
dyn_cast<MDNode>(AScopes->getOperand(i)))
+ for (unsigned j = 0, je = BNoAlias->getNumOperands(); j !=
je; ++j)
+ if (const MDNode *BMD =
dyn_cast<MDNode>(BNoAlias->getOperand(j)))
+ if (!Aliases(AMD, BMD))
+ return NoAlias;
+


Please put this in a helper instead of repeating it four times:

e.g.

+static bool mayAliasInScopes(const MDNode *Scopes, const MDNode
*NoAlias) {
+ if (!Scopes || !NoAlias)
+ return false;
+ for (unsigned i = 0, ie = Scopes->getNumOperands(); i != ie; ++i)
{
+ if (const MDNode *SMD = dyn_cast<MDNode>(Scopes->getOperand(i)))
+ for (unsigned j = 0, je = NoAlias->getNumOperands(); j != je;
++j)
+ if (const MDNode *NAMD =
dyn_cast<MDNode>(NoAlias->getOperand(j)))
+ if (!MayAlias(SMD, NAMD))
+ return false;
+ }
+ return true;

================
Comment at: test/Transforms/Inline/noalias2.ll:43
@@ +42,3 @@
+
+; Check that when hello() in inlined into foo(), and then foo() is
inlined into
+; foo2(), the noalias scopes are properly concatenated.


is inlined

http://llvm-reviews.chandlerc.com/D2194

hfinkel updated this revision to Diff 11270.Jul 10 2014, 6:53 AM
hfinkel edited edge metadata.

Addressed all comments, added docs, etc.

(special thanks to Alexander Kornienko for fixing the file upload size so that I could post this).

hfinkel updated this revision to Diff 11683.Jul 18 2014, 9:29 PM
hfinkel edited edge metadata.

Rebased.

hfinkel updated this revision to Diff 11690.Jul 19 2014, 8:47 PM

Updated to also preserve the metadata in the loop vectorizer.

hfinkel updated this revision to Diff 11805.Jul 23 2014, 12:36 AM

Rebased (and fixed the docs typo Tobias found).

I talked with Chandler on IRC last night, and he's satisfied that I've discussed this with Nick (which was his review requirements from long ago). As I've mentioned previously, the outcome of that discussion is that we need a sanitizer for aliasing. On this there is no disagreement, and I've started developing one (see http://reviews.llvm.org/D4446).

Rereading the code, however, there is bad news: The exact scheme proposed in this patch won't do what we want it to do, and will be hard for Clang to use effectively. First, I'll mention that the code here that transforms noalias function parameters into metadata during inlining is wrong, primarily because it omits a capturing analysis. This is fixable during inlining, but explains why Clang could not effectively use the scheme for block-level restrict pointers: Clang would need to do a capturing analysis to emit the metadata too (at least, if it were to do a good job of it).

To explain: If we have some function like:
void foo(noalias a, noalias b) {

c = foo(a, b);
*c = *a + *b;

}

In the scheme in this patch, we first define a 'scope' for this function for each noalias parameter (so here we have 2 scopes, one for a and one for b), so here we'd tag *a with !scope_a and *b with !scope_b (because a and b are their pointer's underlying objects). Then we'd look for the accesses: We tag *a with 'noalias !scope_b' (because its pointer does not derive from b), we'd tag *b with 'noalias !scope_a' similarly, and we'd tag *c with 'noalias !scope_a,!scope_b', which is wrong. Even though the pointer used by *c does not directly derive from a or b, if a or b are captured by foo, then c might be derived from them.

Within the scheme in this patch, there are two possible ways to fix this; perform a capture analysis either:

  1. Be conservative and not place any metadata on *c.
  2. Generate yet-another scope to represent 'derived from a or b', and also tag everything that does not potentially derived from or or b with this scope metadata also.

Neither choice is ideal. In the first case, we discard useful information. In the second, we could have an exponentially-increasing about of metadata (which we'd need to cutoff at some point, leaving us the first choice).

In any case, there is a better scheme, which provides an ideal solution here and also is easily usable from Clang:

  1. Keep the scope metadata, but only generate one scope per function (or block if doing it from Clang).
  2. Do not use noalias metadata, but add a @llvm.noalias(ptr*, !metadata) intrinsic; this intrinsic will use the pointer value and also associate its noalias assumption with the scope metadata to which it applies.
  3. As BasicAA ascends up the value chain, in BasicAA::aliasCheck, it can look for users of the pointer that are @llvm.noalias, and if it finds one, look at the scope metadata node from the Location object, and if it finds a match, it treats that value as if it had found a noalias argument.

This is better because a) There is much less metadata b) it does not require a capturing analysis (BasicAA will do one at query time if necessary just as it does now). Because the metadata explicitly mark the applicable memory accesses, there is no need to derive that information from dominance, and thus no need to maintain control dependencies on the intrinsic itself (it can be marked IntNoMem, just like the debug intrinsics).

The good news is that any scheme we use (that does not involve scheduling barriers) must have some kind scope-tagging metadata, and so the refactoring of Loc.TBAATag -> Loc.AATags will be necessary regardless.

And here's the awkward part: Then C++ noalias attributes I've been working on (with lots of other folks), see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf, aims to have the noalias set inheritance be syntactically derivable, and so probably prefers this current scheme (or some extension of it).

I'll update to the new scheme and re-post.

  • Original Message -----

From: hfinkel@anl.gov
To: hfinkel@anl.gov, dan433584@gmail.com, atrick@apple.com, chandlerc@gmail.com
Cc: "zinovy nis" <zinovy.nis@gmail.com>, mcrosier@codeaurora.org, nlewycky@google.com, "renato golin"
<renato.golin@linaro.org>, nrotem@apple.com, llvm-commits@cs.uiuc.edu
Sent: Wednesday, July 23, 2014 6:04:44 PM
Subject: Re: [PATCH] Scoped NoAlias Metadata

I talked with Chandler on IRC last night, and he's satisfied that
I've discussed this with Nick (which was his review requirements
from long ago). As I've mentioned previously, the outcome of that
discussion is that we need a sanitizer for aliasing. On this there
is no disagreement, and I've started developing one (see
http://reviews.llvm.org/D4446).

Rereading the code, however, there is bad news: The exact scheme
proposed in this patch won't do what we want it to do, and will be
hard for Clang to use effectively. First, I'll mention that the code
here that transforms noalias function parameters into metadata
during inlining is wrong, primarily because it omits a capturing
analysis. This is fixable during inlining, but explains why Clang
could not effectively use the scheme for block-level restrict
pointers: Clang would need to do a capturing analysis to emit the
metadata too (at least, if it were to do a good job of it).

To explain: If we have some function like:
void foo(noalias a, noalias b) {

c = foo(a, b);
*c = *a + *b;

}

In the scheme in this patch, we first define a 'scope' for this
function for each noalias parameter (so here we have 2 scopes, one
for a and one for b), so here we'd tag *a with !scope_a and *b with
!scope_b (because a and b are their pointer's underlying objects).
Then we'd look for the accesses: We tag *a with 'noalias !scope_b'
(because its pointer does not derive from b), we'd tag *b with
'noalias !scope_a' similarly, and we'd tag *c with 'noalias
!scope_a,!scope_b', which is wrong. Even though the pointer used by
*c does not directly derive from a or b, if a or b are captured by
foo, then c might be derived from them.

Within the scheme in this patch, there are two possible ways to fix
this; perform a capture analysis either:

    1. Be conservative and not place any metadata on *c.
    2. Generate yet-another scope to represent 'derived from a or b', and also tag everything that does not potentially derived from or or b with this scope metadata also. Neither choice is ideal. In the first case, we discard useful information. In the second, we could have an exponentially-increasing about of metadata (which we'd need to cutoff at some point, leaving us the first choice).

      In any case, there is a better scheme, which provides an ideal solution here and also is easily usable from Clang:
  1. Keep the scope metadata, but only generate one scope per function (or block if doing it from Clang).
  2. Do not use noalias metadata, but add a @llvm.noalias(ptr*, !metadata) intrinsic; this intrinsic will use the pointer value and also associate its noalias assumption with the scope metadata to which it applies.
  3. As BasicAA ascends up the value chain, in BasicAA::aliasCheck, it can look for users of the pointer that are @llvm.noalias, and if it finds one, look at the scope metadata node from the Location object, and if it finds a match, it treats that value as if it had found a noalias argument.

As it turns out, unfortunately, this does not work (so I'm returning to the original design -- with the necessary added capture analysis during inlining). I'll explain why:

callee:
foo(noalias a) {

a[-4] = *a;

}

caller:
x = w+4;
foo(x, m);

then we inline:
x = w+4
@llvm.noalias(x, !foo);
x[-4] <!foo> = *a <!foo>;

then we simplify:
x = w+4
@llvm.noalias(x, !foo);
*w <!foo> = *a <!foo>;

and now we have a problem, because it will look like *a and *w don't alias because they have the same scope tag but only one of them goes up through a pointer with the @llvm.noalias user.

To reiterate another rejected resign, we could make @llvm.noalias return a pointer, so we force it to be the (indirect) parent of all derived pointers. But we specifically don't want to do that because it will block exactly the kind of combining in the above example, and that is combining that we do want to happen. We also rejected any other design that introduces code-motion barriers around the inlined code.

So that leaves me with the original design (although, as I've mentioned, I need to fix the inlining attribute -> metadata procedure).

Hopefully I've not confused the issue too much; the benefit of having this small detour in writing is that in the future I'll remember why all of the rejected designs were rejected. ;)

So, here's my plan: I'm going to separate this into three patches:

  1. The basic refactoring.
  2. The scoped-noalias metadata
  3. The noalias parameter attribute -> metadata conversion

Since everyone was happy (including me) with (1) and (2), I'll commit those. I'll fix (3) and post it for review.

Thanks again everyone,
Hal

This is better because a) There is much less metadata b) it does not
require a capturing analysis (BasicAA will do one at query time if
necessary just as it does now). Because the metadata explicitly mark
the applicable memory accesses, there is no need to derive that
information from dominance, and thus no need to maintain control
dependencies on the intrinsic itself (it can be marked IntNoMem,
just like the debug intrinsics).

The good news is that any scheme we use (that does not involve
scheduling barriers) must have some kind scope-tagging metadata, and
so the refactoring of Loc.TBAATag -> Loc.AATags will be necessary
regardless.

And here's the awkward part: Then C++ noalias attributes I've been
working on (with lots of other folks), see
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf,
aims to have the noalias set inheritance be syntactically derivable,
and so probably prefers this current scheme (or some extension of
it).

I'll update to the new scheme and re-post.

http://reviews.llvm.org/D2194

Refactoring portions committed in r213859.

hfinkel closed this revision.Jul 24 2014, 7:51 AM

The basic feature (without the noalias parameter attribute -> metadata conversion) was committed in r213864. I'm going to close out this now, and I'll create a new thread for the remaining feature.