Simplify and improve scoped-noalias metadata semantics

In the process of fixing the noalias parameter -> metadata conversion process
that will take place during inlining (which will be committed soon, but not
turned on by default), I have come to realize that the semantics provided by
yesterday's commit are not really what we want. Here's why:

void foo(noalias a, noalias b, noalias c, bool x) {
  *q = x ? a : b;
  *c = *q;
}

Generically, we know that *c does not alias with *a and with *b (so there is an
'and' in what we know we're not), and we know that *q might be derived from *a
or from *b (so there is an 'or' in what we know that we are). So we do not want
the semantics currently, where any noalias scope matching any alias.scope
causes a NoAlias return. What we want to know is that the noalias scopes form a
superset of the alias.scope list (meaning that all the things we know we're not
is a superset of all of things the other instruction might be).

Making that change, however, introduces a composibility problem. If we inline
once, adding the noalias metadata, and then inline again adding more, and we
append new scopes onto the noalias and alias.scope lists each time. But, this
means that we could change what was a NoAlias result previously into a MayAlias
result because we appended an additional scope onto one of the alias.scope
lists. So, instead of giving scopes the ability to have parents (which I had
borrowed from the TBAA implementation, but seems increasingly unlikely to be
useful in practice), I've given them domains. The subset/superset condition now
applies within each domain independently, and we only need it to hold in one
domain. Each time we inline, we add the new scopes in a new scope domain, and
everything now composes nicely. In addition, this simplifies the
implementation.

llvm-svn: 213948

2 files changed, 58 insertions, 52 deletions

diff --git a/llvm/lib/Analysis/ScopedNoAliasAA.cpp b/llvm/lib/Analysis/ScopedNoAliasAA.cpp
index f197f1c48a6..d090227d318 100644
--- a/llvm/lib/Analysis/ScopedNoAliasAA.cpp
+++ b/llvm/lib/Analysis/ScopedNoAliasAA.cpp
@@ -10,13 +10,14 @@
 // This file defines the ScopedNoAlias alias-analysis pass, which implements
 // metadata-based scoped no-alias support.
 //
-// Alias-analysis scopes are defined similar to TBAA nodes:
+// Alias-analysis scopes are defined by an id (which can be a string or some
+// other metadata node), a domain node, and an optional descriptive string.
+// A domain is defined by an id (which can be a string or some other metadata
+// node), and an optional descriptive string.
 //
-// !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 }
+// !dom0 =   metadata !{ metadata !"domain of foo()" }
+// !scope1 = metadata !{ metadata !scope1, metadata !dom0, metadata !"scope 1" }
+// !scope2 = metadata !{ metadata !scope2, metadata !dom0, metadata !"scope 2" }
 //
 // Loads and stores can be tagged with an alias-analysis scope, and also, with
 // a noalias tag for a specific scope:
@@ -25,17 +26,13 @@
 // ... = 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
+// has a set of noalias scopes in some domain that is superset of the alias
+// scopes in that domain of some other instruction, then the two memory
 // accesses are assumed not to alias.
 //
-// Note that if 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.
-//
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/Constants.h"
@@ -66,15 +63,11 @@ public:
   /// getNode - Get the MDNode for this AliasScopeNode.
   const MDNode *getNode() const { return Node; }
 
-  /// getParent - Get this AliasScopeNode's Alias tree parent.
-  AliasScopeNode getParent() const {
+  /// getDomain - Get the MDNode for this AliasScopeNode's domain.
+  const MDNode *getDomain() const {
     if (Node->getNumOperands() < 2)
-      return AliasScopeNode();
-    MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
-    if (!P)
-      return AliasScopeNode();
-    // Ok, this node has a valid parent. Return it.
-    return AliasScopeNode(P);
+      return nullptr;
+    return dyn_cast_or_null<MDNode>(Node->getOperand(1));
   }
 };
 
@@ -102,8 +95,9 @@ public:
   }
 
 protected:
-  bool mayAlias(const MDNode *A, const MDNode *B) const;
   bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) const;
+  void collectMDInDomain(const MDNode *List, const MDNode *Domain,
+                         SmallPtrSetImpl<const MDNode *> &Nodes) const;
 
 private:
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
@@ -133,24 +127,13 @@ ScopedNoAliasAA::getAnalysisUsage(AnalysisUsage &AU) const {
   AliasAnalysis::getAnalysisUsage(AU);
 }
 
-/// mayAlias - 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::mayAlias(const MDNode *A,
-                          const MDNode *B) const {
-  // Climb the tree from A to see if we reach B.
-  for (AliasScopeNode T(A); ; ) {
-    if (T.getNode() == B)
-      // B is an ancestor of A.
-      return false;
-
-    T = T.getParent();
-    if (!T.getNode())
-      break;
-  }
-
-  return true;
+void
+ScopedNoAliasAA::collectMDInDomain(const MDNode *List, const MDNode *Domain,
+                   SmallPtrSetImpl<const MDNode *> &Nodes) const {
+  for (unsigned i = 0, ie = List->getNumOperands(); i != ie; ++i)
+    if (const MDNode *MD = dyn_cast<MDNode>(List->getOperand(i)))
+      if (AliasScopeNode(MD).getDomain() == Domain)
+        Nodes.insert(MD);
 }
 
 bool
@@ -159,14 +142,35 @@ ScopedNoAliasAA::mayAliasInScopes(const MDNode *Scopes,
   if (!Scopes || !NoAlias)
     return true;
 
-  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;
+  // Collect the set of scope domains relevant to the noalias scopes.
+  SmallPtrSet<const MDNode *, 16> Domains;
+  for (unsigned i = 0, ie = NoAlias->getNumOperands(); i != ie; ++i)
+    if (const MDNode *NAMD = dyn_cast<MDNode>(NoAlias->getOperand(i)))
+      if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
+        Domains.insert(Domain);
+
+  // We alias unless, for some domain, the set of noalias scopes in that domain
+  // is a superset of the set of alias scopes in that domain.
+  for (const MDNode *Domain : Domains) {
+    SmallPtrSet<const MDNode *, 16> NANodes, ScopeNodes;
+    collectMDInDomain(NoAlias, Domain, NANodes);
+    collectMDInDomain(Scopes, Domain, ScopeNodes);
+    if (!ScopeNodes.size())
+      continue;
+
+    // To not alias, all of the nodes in ScopeNodes must be in NANodes.
+    bool FoundAll = true;
+    for (const MDNode *SMD : ScopeNodes)
+      if (!NANodes.count(SMD)) {
+        FoundAll = false;
+        break;
+      }
+
+    if (FoundAll)
+      return false;
+  }
 
-  return true; 
+  return true;
 }
 
 AliasAnalysis::AliasResult
diff --git a/llvm/lib/IR/MDBuilder.cpp b/llvm/lib/IR/MDBuilder.cpp
index 103915f5ae5..39307a26f24 100644
--- a/llvm/lib/IR/MDBuilder.cpp
+++ b/llvm/lib/IR/MDBuilder.cpp
@@ -60,11 +60,13 @@ MDNode *MDBuilder::createRange(const APInt &Lo, const APInt &Hi) {
   return MDNode::get(Context, Range);
 }
 
-MDNode *MDBuilder::createAnonymousAARoot(StringRef Name) {
+MDNode *MDBuilder::createAnonymousAARoot(StringRef Name, MDNode *Extra) {
   // To ensure uniqueness the root node is self-referential.
   MDNode *Dummy = MDNode::getTemporary(Context, ArrayRef<Value*>());
 
-  SmallVector<Value *, 2> Args(1, Dummy);
+  SmallVector<Value *, 3> Args(1, Dummy);
+  if (Extra)
+    Args.push_back(Extra);
   if (!Name.empty())
     Args.push_back(createString(Name));
   MDNode *Root = MDNode::get(Context, Args);
@@ -98,12 +100,12 @@ MDNode *MDBuilder::createTBAANode(StringRef Name, MDNode *Parent,
   }
 }
 
-MDNode *MDBuilder::createAliasScopeRoot(StringRef Name) {
+MDNode *MDBuilder::createAliasScopeDomain(StringRef Name) {
   return MDNode::get(Context, createString(Name));
 }
 
-MDNode *MDBuilder::createAliasScopeNode(StringRef Name, MDNode *Parent) {
-  Value *Ops[2] = { createString(Name), Parent };
+MDNode *MDBuilder::createAliasScope(StringRef Name, MDNode *Domain) {
+  Value *Ops[2] = { createString(Name), Domain };
   return MDNode::get(Context, Ops);
 }