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

3 files changed, 80 insertions, 15 deletions

diff --git a/llvm/test/Analysis/ScopedNoAliasAA/basic-domains.ll b/llvm/test/Analysis/ScopedNoAliasAA/basic-domains.ll
new file mode 100644
index 00000000000..d88a4966c41
--- /dev/null
+++ b/llvm/test/Analysis/ScopedNoAliasAA/basic-domains.ll
@@ -0,0 +1,57 @@
+; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @foo1(float* nocapture %a, float* nocapture readonly %c) #0 {
+entry:
+; CHECK-LABEL: Function: foo1
+  %0 = load float* %c, align 4, !alias.scope !9
+  %arrayidx.i = getelementptr inbounds float* %a, i64 5
+  store float %0, float* %arrayidx.i, align 4, !noalias !6
+
+  %1 = load float* %c, align 4, !alias.scope !5
+  %arrayidx.i2 = getelementptr inbounds float* %a, i64 15
+  store float %1, float* %arrayidx.i2, align 4, !noalias !6
+
+  %2 = load float* %c, align 4, !alias.scope !6
+  %arrayidx.i3 = getelementptr inbounds float* %a, i64 16
+  store float %2, float* %arrayidx.i3, align 4, !noalias !5
+
+  ret void
+}
+
+attributes #0 = { nounwind uwtable }
+
+!0 = metadata !{metadata !0, metadata !"some domain"}
+!1 = metadata !{metadata !1, metadata !"some other domain"}
+
+; Two scopes (which must be self-referential to avoid being "uniqued"):
+!2 = metadata !{metadata !2, metadata !0, metadata !"a scope in dom0"}
+!3 = metadata !{metadata !2}
+
+!4 = metadata !{metadata !4, metadata !0, metadata !"another scope in dom0"}
+!5 = metadata !{metadata !4}
+
+; A list of the two scopes.
+!6 = metadata !{metadata !2, metadata !4}
+
+; Another scope in the second domain
+!7 = metadata !{metadata !7, metadata !1, metadata !"another scope in dom1"}
+!8 = metadata !{metadata !7}
+
+; A list of scopes from both domains.
+!9 = metadata !{metadata !2, metadata !4, metadata !7}
+
+; CHECK: NoAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %0, float* %arrayidx.i, align 4, !noalias !6
+; CHECK: NoAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %1, float* %arrayidx.i2, align 4, !noalias !6
+; CHECK: MayAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %2, float* %arrayidx.i3, align 4, !noalias !7
+; CHECK: NoAlias:   %1 = load float* %c, align 4, !alias.scope !7 <->   store float %0, float* %arrayidx.i, align 4, !noalias !6
+; CHECK: NoAlias:   %1 = load float* %c, align 4, !alias.scope !7 <->   store float %1, float* %arrayidx.i2, align 4, !noalias !6
+; CHECK: NoAlias:   %1 = load float* %c, align 4, !alias.scope !7 <->   store float %2, float* %arrayidx.i3, align 4, !noalias !7
+; CHECK: NoAlias:   %2 = load float* %c, align 4, !alias.scope !6 <->   store float %0, float* %arrayidx.i, align 4, !noalias !6
+; CHECK: NoAlias:   %2 = load float* %c, align 4, !alias.scope !6 <->   store float %1, float* %arrayidx.i2, align 4, !noalias !6
+; CHECK: MayAlias:   %2 = load float* %c, align 4, !alias.scope !6 <->   store float %2, float* %arrayidx.i3, align 4, !noalias !7
+; CHECK: NoAlias:   store float %1, float* %arrayidx.i2, align 4, !noalias !6 <->   store float %0, float* %arrayidx.i, align 4, !noalias !6
+; CHECK: NoAlias:   store float %2, float* %arrayidx.i3, align 4, !noalias !7 <->   store float %0, float* %arrayidx.i, align 4, !noalias !6
+; CHECK: NoAlias:   store float %2, float* %arrayidx.i3, align 4, !noalias !7 <->   store float %1, float* %arrayidx.i2, align 4, !noalias !6
+
diff --git a/llvm/test/Analysis/ScopedNoAliasAA/basic.ll b/llvm/test/Analysis/ScopedNoAliasAA/basic.ll
index bae977f28ee..73fe3339038 100644
--- a/llvm/test/Analysis/ScopedNoAliasAA/basic.ll
+++ b/llvm/test/Analysis/ScopedNoAliasAA/basic.ll
@@ -5,9 +5,9 @@ target triple = "x86_64-unknown-linux-gnu"
 define void @foo1(float* nocapture %a, float* nocapture readonly %c) #0 {
 entry:
 ; CHECK-LABEL: Function: foo1
-  %0 = load float* %c, align 4, !alias.scope !0
+  %0 = load float* %c, align 4, !alias.scope !1
   %arrayidx.i = getelementptr inbounds float* %a, i64 5
-  store float %0, float* %arrayidx.i, align 4, !noalias !0
+  store float %0, float* %arrayidx.i, align 4, !noalias !1
   %1 = load float* %c, align 4
   %arrayidx = getelementptr inbounds float* %a, i64 7
   store float %1, float* %arrayidx, align 4
@@ -22,5 +22,6 @@ entry:
 
 attributes #0 = { nounwind uwtable }
 
-!0 = metadata !{metadata !0}
+!0 = metadata !{metadata !0, metadata !"some domain"}
+!1 = metadata !{metadata !1, metadata !0, metadata !"some scope"}
 
diff --git a/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll b/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll
index 44393bbdaab..37b0add68bd 100644
--- a/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll
+++ b/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll
@@ -7,28 +7,35 @@ entry:
 ; CHECK-LABEL: Function: foo2
   %0 = load float* %c, align 4, !alias.scope !0
   %arrayidx.i = getelementptr inbounds float* %a, i64 5
-  store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1
+  store float %0, float* %arrayidx.i, align 4, !alias.scope !5, !noalias !4
   %arrayidx1.i = getelementptr inbounds float* %b, i64 8
-  store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2
+  store float %0, float* %arrayidx1.i, align 4, !alias.scope !0, !noalias !5
   %1 = load float* %c, align 4
   %arrayidx = getelementptr inbounds float* %a, i64 7
   store float %1, float* %arrayidx, align 4
   ret void
 
-; CHECK: NoAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1
-; CHECK: NoAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2
+; CHECK: MayAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !4, !noalia
+; CHECK: s !5
+; CHECK: MayAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %0, float* %arrayidx1.i, align 4, !alias.scope !0, !noali
+; CHECK: as !4
 ; CHECK: MayAlias:   %0 = load float* %c, align 4, !alias.scope !0 <->   store float %1, float* %arrayidx, align 4
-; CHECK: MayAlias:   %1 = load float* %c, align 4 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1
-; CHECK: MayAlias:   %1 = load float* %c, align 4 <->   store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2
+; CHECK: MayAlias:   %1 = load float* %c, align 4 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !4, !noalias !5
+; CHECK: MayAlias:   %1 = load float* %c, align 4 <->   store float %0, float* %arrayidx1.i, align 4, !alias.scope !0, !noalias !4
 ; CHECK: MayAlias:   %1 = load float* %c, align 4 <->   store float %1, float* %arrayidx, align 4
-; CHECK: NoAlias:   store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1
-; CHECK: NoAlias:   store float %1, float* %arrayidx, align 4 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1
-; CHECK: MayAlias:   store float %1, float* %arrayidx, align 4 <->   store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2
+; CHECK: NoAlias:   store float %0, float* %arrayidx1.i, align 4, !alias.scope !0, !noalias !4 <->   store float %0, float* %arrayidx.i, align
+; CHECK: 4, !alias.scope !4, !noalias !5
+; CHECK: NoAlias:   store float %1, float* %arrayidx, align 4 <->   store float %0, float* %arrayidx.i, align 4, !alias.scope !4, !noalias !5
+; CHECK: MayAlias:   store float %1, float* %arrayidx, align 4 <->   store float %0, float* %arrayidx1.i, align 4, !alias.scope !0, !noalias !
+; CHECK: 4
 }
 
 attributes #0 = { nounwind uwtable }
 
-!0 = metadata !{metadata !1, metadata !2}
-!1 = metadata !{metadata !1}
-!2 = metadata !{metadata !2}
+!0 = metadata !{metadata !1, metadata !3}
+!1 = metadata !{metadata !1, metadata !2, metadata !"some scope"}
+!2 = metadata !{metadata !2, metadata !"some domain"}
+!3 = metadata !{metadata !3, metadata !2, metadata !"some other scope"}
+!4 = metadata !{metadata !1}
+!5 = metadata !{metadata !3}