[CFLAA] Add an initial CFLAnders implementation.

This adds an incomplete anders-style implementation for CFLAA. It's
incomplete in that it's missing interprocedural analysis, attrs
handling, etc. and that it needs more tests. More tests and features
will be added in future commits.

Patch by Jia Chen.

Differential Revision: https://reviews.llvm.org/D22291

llvm-svn: 275602

4 files changed, 102 insertions, 0 deletions

diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll
new file mode 100644
index 00000000000..237fe72732e
--- /dev/null
+++ b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll
@@ -0,0 +1,24 @@
+; This testcase ensures that CFL AA handles assignment in an inclusion-based 
+; manner
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_assign
+; CHECK: NoAlias: i64* %a, i64* %b
+; CHECK: NoAlias: i32* %c, i64* %b
+; CHECK: NoAlias: i32* %d, i64* %a
+; CHECK: NoAlias: i32* %c, i32* %d
+; CHECK: MayAlias: i32* %e, i64* %a
+; CHECK: MayAlias: i32* %e, i64* %b
+; CHECK: MayAlias: i32* %c, i32* %e
+; CHECK: MayAlias: i32* %d, i32* %e
+define void @test_assign(i1 %cond) {
+  %a = alloca i64, align 8
+  %b = alloca i64, align 8
+
+  %c = bitcast i64* %a to i32*
+  %d = bitcast i64* %b to i32*
+  %e = select i1 %cond, i32* %c, i32* %d
+  ret void
+}
\ No newline at end of file
diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll
new file mode 100644
index 00000000000..8bd98f388f0
--- /dev/null
+++ b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll
@@ -0,0 +1,23 @@
+; This testcase ensures that CFL AA handles assignment in an inclusion-based 
+; manner
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_assign2
+; CHECK: NoAlias: i32* %b, i64* %a
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %d
+; CHECK: MayAlias: i32* %e, i64* %a
+; CHECK: MayAlias: i32* %b, i32* %e
+; CHECK: MayAlias: i32* %c, i32* %e
+; CHECK: MayAlias: i32* %d, i32* %e
+define void @test_assign2(i1 %cond) {
+	%a = alloca i64, align 8
+	%b = alloca i32, align 4
+
+	%c = bitcast i64* %a to i32*
+	%d = bitcast i64* %a to i32*
+	%e = select i1 %cond, i32* %c, i32* %b
+	ret void
+}
\ No newline at end of file
diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll
new file mode 100644
index 00000000000..4ce9467ddc3
--- /dev/null
+++ b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll
@@ -0,0 +1,34 @@
+; This testcase ensures that CFL AA handles assignment cycles correctly
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_cycle
+; CHECK: NoAlias: i64* %a, i64** %b
+; CHECK: NoAlias: i64* %a, i64*** %c
+; CHECK: NoAlias: i64** %b, i64*** %c
+; CHECK: NoAlias: i64* %a, i64**** %d
+; CHECK: NoAlias: i64** %b, i64**** %d
+; CHECK: NoAlias: i64*** %c, i64**** %d
+; CHECK: NoAlias: i64* %a, i64* %e
+; CHECK: NoAlias: i64* %e, i64** %b
+; CHECK: NoAlias: i64* %e, i64*** %c
+; CHECK: MayAlias: i64* %a, i64* %f
+; CHECK: NoAlias: i64* %f, i64** %b
+; CHECK: NoAlias: i64* %f, i64*** %c
+; CHECK: MayAlias: i64* %f, i64**** %d
+; CHECK: MayAlias: i64* %e, i64* %f
+define void @test_cycle() {
+  %a = alloca i64, align 8
+  %b = alloca i64*, align 8
+  %c = alloca i64**, align 8
+  %d = alloca i64***, align 8
+  store i64* %a, i64** %b
+  store i64** %b, i64*** %c
+  store i64*** %c, i64**** %d
+
+  %e = bitcast i64**** %d to i64*
+  store i64* %e, i64** %b
+  %f = load i64*, i64** %b
+  ret void
+}
diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll
new file mode 100644
index 00000000000..d3fb09091aa
--- /dev/null
+++ b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll
@@ -0,0 +1,21 @@
+; This testcase ensures that CFL AA correctly handles simple memory alias 
+; pattern
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_memalias
+; CHECK: NoAlias: i64* %a, i64** %b
+; CHECK: NoAlias: i32** %c, i64* %a
+; CHECK: MayAlias: i32* %d, i64* %a
+; CHECK: NoAlias: i32* %d, i64** %b
+; CHECK: NoAlias: i32* %d, i32** %c
+define void @test_memalias() {
+  %a = alloca i64, align 8
+  %b = alloca i64*, align 8
+  store i64* %a, i64** %b
+
+  %c = bitcast i64** %b to i32**
+  %d = load i32*, i32** %c
+  ret void
+}
\ No newline at end of file