Update aosp/master LLVM for rebase to r222494.

Change-Id: Ic787f5e0124df789bd26f3f24680f45e678eef2d

15 files changed, 385 insertions, 0 deletions

diff --git a/test/Analysis/CFLAliasAnalysis/arguments-globals.ll b/test/Analysis/CFLAliasAnalysis/arguments-globals.ll
new file mode 100644
index 0000000..18bbe8b
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/arguments-globals.ll
@@ -0,0 +1,20 @@
+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+; (Everything should alias everything, because args can alias globals, so the
+; aliasing sets should of args+alloca+global should be combined)
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+
+@g = external global i32
+
+define void @test(i1 %c, i32* %arg1, i32* %arg2) {
+  ; CHECK: 15 Total Alias Queries Performed
+  ; CHECK: 0 no alias responses
+  %A = alloca i32, align 4
+  %B = select i1 %c, i32* %arg1, i32* %arg2
+  %C = select i1 %c, i32* @g, i32* %A
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/arguments.ll b/test/Analysis/CFLAliasAnalysis/arguments.ll
new file mode 100644
index 0000000..f3e6679
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/arguments.ll
@@ -0,0 +1,15 @@
+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+
+define void @test(i1 %c, i32* %arg1, i32* %arg2) {
+  ; CHECK: 6 Total Alias Queries Performed
+  ; CHECK: 3 no alias responses
+  %a = alloca i32, align 4
+  %b = select i1 %c, i32* %arg1, i32* %arg2
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/basic-interproc-ret.ll b/test/Analysis/CFLAliasAnalysis/basic-interproc-ret.ll
new file mode 100644
index 0000000..d56a455
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/basic-interproc-ret.ll
@@ -0,0 +1,26 @@
+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+; CHECK: 4 Total Alias Queries Performed
+; CHECK: 3 no alias responses
+; ^ The 1 MayAlias is due to %arg1. Sadly, we don't currently have machinery
+; in place to check whether %arg1 aliases %a, because BasicAA takes care of 
+; that for us.
+
+define i32* @test2(i32* %arg1) {
+  store i32 0, i32* %arg1
+
+  %a = alloca i32, align 4
+  ret i32* %a
+}
+
+define void @test() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %c = call i32* @test2(i32* %a)
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/basic-interproc.ll b/test/Analysis/CFLAliasAnalysis/basic-interproc.ll
new file mode 100644
index 0000000..c0a5404
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/basic-interproc.ll
@@ -0,0 +1,24 @@
+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+; CHECK: 2 Total Alias Queries Performed
+; CHECK: 1 no alias responses
+; ^^ In @test2, %arg1 and %arg2 may alias
+
+define void @test2(i32* %arg1, i32* %arg2) {
+  store i32 0, i32* %arg1
+  store i32 0, i32* %arg2
+
+  ret void
+}
+
+define void @test() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  call void @test2(i32* %a, i32* %b)
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll b/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll
new file mode 100644
index 0000000..9ae200b
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll
@@ -0,0 +1,21 @@
+; This testcase consists of alias relations which should be completely
+; resolvable by cfl-aa, but require analysis of getelementptr constant exprs.
+; Derived from BasicAA/2003-12-11-ConstExprGEP.ll
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+@G = external global %T
+
+; CHECK:     Function: test
+; CHECK-NOT:   May:
+
+define void @test() {
+  %D = getelementptr %T* @G, i64 0, i32 0
+  %E = getelementptr %T* @G, i64 0, i32 1, i64 5
+  %F = getelementptr i32* getelementptr (%T* @G, i64 0, i32 0), i64 0
+  %X = getelementptr [10 x i8]* getelementptr (%T* @G, i64 0, i32 1), i64 0, i64 5
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/constant-over-index.ll b/test/Analysis/CFLAliasAnalysis/constant-over-index.ll
new file mode 100644
index 0000000..fb44b95
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/constant-over-index.ll
@@ -0,0 +1,30 @@
+; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
+
+; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem
+; acceptable (although we might decide that we don't want PartialAlias, and if
+; so, we should update this test case accordingly).
+; CHECK: {{PartialAlias|MayAlias}}: double* %p.0.i.0, double* %p3
+
+; %p3 is equal to %p.0.i.0 on the second iteration of the loop,
+; so MayAlias is needed.
+
+define void @foo([3 x [3 x double]]* noalias %p) {
+entry:
+  %p3 = getelementptr [3 x [3 x double]]* %p, i64 0, i64 0, i64 3
+  br label %loop
+
+loop:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+
+  %p.0.i.0 = getelementptr [3 x [3 x double]]* %p, i64 0, i64 %i, i64 0
+
+  store volatile double 0.0, double* %p3
+  store volatile double 0.1, double* %p.0.i.0
+
+  %i.next = add i64 %i, 1
+  %cmp = icmp slt i64 %i.next, 3
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/empty.ll b/test/Analysis/CFLAliasAnalysis/empty.ll
new file mode 100644
index 0000000..907fa48
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/empty.ll
@@ -0,0 +1,12 @@
+; RUN: opt < %s -cfl-aa -aa-eval -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"
+
+; CHECK:      Function: foo:
+; CHECK-NEXT:   NoAlias: {}* %p, {}* %q
+
+define void @foo({}* %p, {}* %q) {
+  store {} {}, {}* %p
+  store {} {}, {}* %q
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll b/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll
new file mode 100644
index 0000000..155fe13
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll
@@ -0,0 +1,37 @@
+; RUN: opt -S -tbaa -cfl-aa -gvn < %s | FileCheck -check-prefix=CFLAA %s
+; RUN: opt -S -tbaa -gvn < %s | FileCheck %s
+; Adapted from the BasicAA full-store-partial-alias.ll test.
+
+; CFL AA should notice that the store stores to the entire %u object,
+; so the %tmp5 load is PartialAlias with the store and suppress TBAA.
+; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store.
+
+target datalayout = "e-p:64:64:64"
+
+%union.anon = type { double }
+
+@u = global %union.anon { double -2.500000e-01 }, align 8
+@endianness_test = global i64 1, align 8
+
+define i32 @signbit(double %x) nounwind {
+; CFLAA: ret i32 %tmp5.lobit
+; CHECK:   ret i32 0
+entry:
+  %u = alloca %union.anon, align 8
+  %tmp9 = getelementptr inbounds %union.anon* %u, i64 0, i32 0
+  store double %x, double* %tmp9, align 8, !tbaa !0
+  %tmp2 = load i32* bitcast (i64* @endianness_test to i32*), align 8, !tbaa !3
+  %idxprom = sext i32 %tmp2 to i64
+  %tmp4 = bitcast %union.anon* %u to [2 x i32]*
+  %arrayidx = getelementptr inbounds [2 x i32]* %tmp4, i64 0, i64 %idxprom
+  %tmp5 = load i32* %arrayidx, align 4, !tbaa !3
+  %tmp5.lobit = lshr i32 %tmp5, 31
+  ret i32 %tmp5.lobit
+}
+
+!0 = metadata !{metadata !4, metadata !4, i64 0}
+!1 = metadata !{metadata !"omnipotent char", metadata !2}
+!2 = metadata !{metadata !"Simple C/C++ TBAA", null}
+!3 = metadata !{metadata !5, metadata !5, i64 0}
+!4 = metadata !{metadata !"double", metadata !1}
+!5 = metadata !{metadata !"int", metadata !1}
diff --git a/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll b/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
new file mode 100644
index 0000000..a0195d7
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
@@ -0,0 +1,17 @@
+; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll
+
+target datalayout = "e-p:32:32:32"
+
+; CHECK: 1 partial alias response
+
+define i32 @test(i32* %tab, i32 %indvar) nounwind {
+  %tmp31 = mul i32 %indvar, -2
+  %tmp32 = add i32 %tmp31, 30
+  %t.5 = getelementptr i32* %tab, i32 %tmp32
+  %loada = load i32* %tab
+  store i32 0, i32* %t.5
+  %loadb = load i32* %tab
+  %rval = add i32 %loada, %loadb
+  ret i32 %rval
+}
diff --git a/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll b/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll
new file mode 100644
index 0000000..9bbc721
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll
@@ -0,0 +1,31 @@
+; This testcase ensures that CFL AA responds conservatively when we union 
+; groups of pointers together through ternary/conditional operations
+; Derived from:
+; void foo(bool c) {
+;   char a, b;
+;   char *m = c ? &a : &b;
+;   *m;
+; }
+;
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+
+define void @test(i1 %C) {
+; CHECK: 10 Total Alias Queries Performed
+; CHECK: 4 no alias responses
+  %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP
+  %A = alloca %T, align 8
+  %B = alloca %T, align 8
+
+  %MS = select i1 %C, %T* %B, %T* %A
+
+  store %T* %MS, %T** %M
+
+  %AP = load %T** %M ; PartialAlias with %A, %B
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/multilevel.ll b/test/Analysis/CFLAliasAnalysis/multilevel.ll
new file mode 100644
index 0000000..9c9eb9a
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/multilevel.ll
@@ -0,0 +1,30 @@
+; This testcase ensures that CFL AA handles trivial cases with storing 
+; pointers in pointers appropriately.
+; Derived from:
+; char a, b;
+; char *m = &a, *n = &b;
+; *m;
+; *n;
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+
+define void @test() {
+; CHECK: 15 Total Alias Queries Performed
+; CHECK: 13 no alias responses
+  %M = alloca %T*, align 8
+  %N = alloca %T*, align 8
+  %A = alloca %T, align 8
+  %B = alloca %T, align 8
+
+  store %T* %A, %T** %M
+  store %T* %B, %T** %N
+
+  %AP = load %T** %M ; PartialAlias with %A
+  %BP = load %T** %N ; PartialAlias with %B
+
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/must-and-partial.ll b/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
new file mode 100644
index 0000000..df7de38
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
@@ -0,0 +1,39 @@
+; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
+
+; When merging MustAlias and PartialAlias, merge to PartialAlias
+; instead of MayAlias.
+
+
+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"
+
+; CHECK: PartialAlias:  i16* %bigbase0, i8* %phi
+define i8 @test0(i8* %base, i1 %x) {
+entry:
+  %baseplusone = getelementptr i8* %base, i64 1
+  br i1 %x, label %red, label %green
+red:
+  br label %green
+green:
+  %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
+  store i8 0, i8* %phi
+
+  %bigbase0 = bitcast i8* %base to i16*
+  store i16 -1, i16* %bigbase0
+
+  %loaded = load i8* %phi
+  ret i8 %loaded
+}
+
+; CHECK: PartialAlias:  i16* %bigbase1, i8* %sel
+define i8 @test1(i8* %base, i1 %x) {
+entry:
+  %baseplusone = getelementptr i8* %base, i64 1
+  %sel = select i1 %x, i8* %baseplusone, i8* %base
+  store i8 0, i8* %sel
+
+  %bigbase1 = bitcast i8* %base to i16*
+  store i16 -1, i16* %bigbase1
+
+  %loaded = load i8* %sel
+  ret i8 %loaded
+}
diff --git a/test/Analysis/CFLAliasAnalysis/phi-and-select.ll b/test/Analysis/CFLAliasAnalysis/phi-and-select.ll
new file mode 100644
index 0000000..a0e71a7
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/phi-and-select.ll
@@ -0,0 +1,36 @@
+; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; Derived from (a subset of) BasicAA/phi-and-select.ll 
+
+; CHECK: Function: qux
+; CHECK:  NoAlias: double* %a, double* %b
+; CHECK: ===== Alias Analysis Evaluator Report =====
+
+; Two PHIs with disjoint sets of inputs.
+define void @qux(i1 %m, double* noalias %x, double* noalias %y,
+                 i1 %n, double* noalias %v, double* noalias %w) {
+entry:
+  br i1 %m, label %true, label %false
+
+true:
+  br label %exit
+
+false:
+  br label %exit
+
+exit:
+  %a = phi double* [ %x, %true ], [ %y, %false ]
+  br i1 %n, label %ntrue, label %nfalse
+
+ntrue:
+  br label %nexit
+
+nfalse:
+  br label %nexit
+
+nexit:
+  %b = phi double* [ %v, %ntrue ], [ %w, %nfalse ]
+  store volatile double 0.0, double* %a
+  store volatile double 1.0, double* %b
+  ret void
+}
+
diff --git a/test/Analysis/CFLAliasAnalysis/simple.ll b/test/Analysis/CFLAliasAnalysis/simple.ll
new file mode 100644
index 0000000..7bc455a
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/simple.ll
@@ -0,0 +1,18 @@
+; This testcase consists of alias relations which should be completely
+; resolvable by cfl-aa (derived from BasicAA/2003-11-04-SimpleCases.ll).
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+; CHECK-NOT:   May:
+
+define void @test(%T* %P) {
+  %A = getelementptr %T* %P, i64 0
+  %B = getelementptr %T* %P, i64 0, i32 0
+  %C = getelementptr %T* %P, i64 0, i32 1
+  %D = getelementptr %T* %P, i64 0, i32 1, i64 0
+  %E = getelementptr %T* %P, i64 0, i32 1, i64 5
+  ret void
+}
diff --git a/test/Analysis/CFLAliasAnalysis/va.ll b/test/Analysis/CFLAliasAnalysis/va.ll
new file mode 100644
index 0000000..3094cb0
--- /dev/null
+++ b/test/Analysis/CFLAliasAnalysis/va.ll
@@ -0,0 +1,29 @@
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test1
+; CHECK: 0 no alias responses
+
+define i32 @test1(i32 %X, ...) {
+  ; Initialize variable argument processing
+  %ap = alloca i8*
+  %ap2 = bitcast i8** %ap to i8*
+  call void @llvm.va_start(i8* %ap2)
+
+  ; Read a single integer argument
+  %tmp = va_arg i8** %ap, i32
+
+  ; Demonstrate usage of llvm.va_copy and llvm.va_end
+  %aq = alloca i8*
+  %aq2 = bitcast i8** %aq to i8*
+  call void @llvm.va_copy(i8* %aq2, i8* %ap2)
+  call void @llvm.va_end(i8* %aq2)
+
+  ; Stop processing of arguments.
+  call void @llvm.va_end(i8* %ap2)
+  ret i32 %tmp
+}
+
+declare void @llvm.va_start(i8*)
+declare void @llvm.va_copy(i8*, i8*)
+declare void @llvm.va_end(i8*)
+