[LICM] Add a diagnostic analysis for identifying alias information

Summary:
Currently, in LICM, we use the alias set tracker to identify if the
instruction (we're interested in hoisting) aliases with instruction that
modifies that memory location.

This patch adds an LICM alias analysis diagnostic tool that checks the
mod ref info of the instruction we are interested in hoisting/sinking,
with every instruction in the loop.  Because of O(N^2) complexity this
is now only a diagnostic tool to show the limitation we have with the
alias set tracker and is OFF by default.

Test cases show the difference with the diagnostic analysis tool, where
we're able to hoist out loads and readonly + argmemonly calls from the
loop, where the alias set tracker analysis is not able to hoist these
instructions out.

Reviewers: reames, mkazantsev, fedor.sergeev, hfinkel

Subscribers: llvm-commits

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

llvm-svn: 340026

3 files changed, 150 insertions, 8 deletions

diff --git a/llvm/test/Transforms/LICM/argmemonly-call.ll b/llvm/test/Transforms/LICM/argmemonly-call.ll
index fe7c6af6d6d..b7d7d6a3953 100644
--- a/llvm/test/Transforms/LICM/argmemonly-call.ll
+++ b/llvm/test/Transforms/LICM/argmemonly-call.ll
@@ -1,5 +1,8 @@
-; RUN: opt -S -basicaa -licm %s | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+
 declare i32 @foo() readonly argmemonly nounwind
 declare i32 @foo2() readonly nounwind
 declare i32 @bar(i32* %loc2) readonly argmemonly nounwind
@@ -68,3 +71,27 @@ loop:
   store i32 %res, i32* %loc
   br label %loop
 }
+
+declare i32 @foo_new(i32*) readonly
+; With the default AST mechanism used by LICM for alias analysis,
+; we clump foo_new with bar.
+; With the N2 Alias analysis diagnostic tool, we are able to hoist the
+; argmemonly bar call out of the loop.
+
+define void @test5(i32* %loc2, i32* noalias %loc) {
+; ALIAS-N2-LABEL: @test5
+; ALIAS-N2: @bar
+; ALIAS-N2-LABEL: loop:
+
+; CHECK-LABEL: @test5
+; CHECK-LABEL: loop:
+; CHECK:  @bar
+  br label %loop
+
+loop:
+  %res1 = call i32 @bar(i32* %loc2)
+  %res = call i32 @foo_new(i32* %loc2)
+  store volatile i32 %res1, i32* %loc
+  br label %loop
+}
+
diff --git a/llvm/test/Transforms/LICM/invariant.start.ll b/llvm/test/Transforms/LICM/invariant.start.ll
index ff17bd096ce..3ac6793d185 100644
--- a/llvm/test/Transforms/LICM/invariant.start.ll
+++ b/llvm/test/Transforms/LICM/invariant.start.ll
@@ -1,7 +1,9 @@
-; RUN: opt -licm -basicaa < %s -S | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=0 < %s -S | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
 
-; TODO: should be able to hoist both load and invariant.start
+; TODO: By default (without the -licm-n2-threshold value), we should be able to hoist both load and invariant.start
 define void @test1(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test1(
 ; CHECK-LABEL: entry:
@@ -9,6 +11,12 @@ define void @test1(i1 %cond, i32* %ptr) {
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test1(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+
 entry:
   br label %loop
 
@@ -20,7 +28,7 @@ loop:
   br label %loop
 }
 
-;; TODO: despite the loop varying invariant.start, we should be
+;; TODO: By default, despite the loop varying invariant.start, we should be
 ;; able to hoist the load
 define void @test2(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test2(
@@ -28,7 +36,12 @@ define void @test2(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: loop:
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv)
 ; CHECK: %val = load i32, i32* %ptr
-  
+
+; ALIAS-N2-LABEL: @test2(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:         call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv)
 entry:
   br label %loop
 
@@ -41,7 +54,7 @@ loop:
   br label %loop
 }
 
-; Should be able to hoist since store doesn't alias
+; By default, should be able to hoist since store doesn't alias
 define void @test3(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test3(
 ; CHECK-LABEL: entry:
@@ -49,6 +62,11 @@ define void @test3(i1 %cond, i32* %ptr) {
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test3(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:         call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 entry:
   br label %loop
 
@@ -72,6 +90,12 @@ define void @test4(i1 %cond, i32* %ptr) {
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test4(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:   store i32 0, i32* %ptr
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+; ALIAS-N2: %val = load i32, i32* %ptr
 entry:
   br label %loop
 
@@ -93,6 +117,12 @@ define void @test5(i1 %cond, i32* %ptr) {
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test5(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:   store i32 0, i32* %ptr
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+; ALIAS-N2: %val = load i32, i32* %ptr
 entry:
   br label %loop
 
diff --git a/llvm/test/Transforms/LICM/read-only-calls.ll b/llvm/test/Transforms/LICM/read-only-calls.ll
new file mode 100644
index 00000000000..0a378144fb7
--- /dev/null
+++ b/llvm/test/Transforms/LICM/read-only-calls.ll
@@ -0,0 +1,85 @@
+; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+
+; We should be able to hoist loads in presence of read only calls and stores
+; that do not alias.
+
+; Since LICM uses the AST mechanism for alias analysis, we will clump
+; together all loads and stores in one set along with the read-only call.
+; This prevents hoisting load that doesn't alias with any other memory
+; operations.
+
+declare void @foo(i64, i32*) readonly
+
+; hoist the load out with the n2-threshold
+; since it doesn't alias with the store.
+; default AST mechanism clumps all memory locations in one set because of the
+; readonly call
+define void @test1(i32* %ptr) {
+; CHECK-LABEL: @test1(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: loop:
+; CHECK: %val = load i32, i32* %ptr
+
+; ALIAS-N2-LABEL: @test1(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+entry:
+  br label %loop
+
+loop:
+  %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
+  %val = load i32, i32* %ptr
+  call void @foo(i64 4, i32* %ptr)
+  %p2 = getelementptr i32, i32* %ptr, i32 1
+  store volatile i32 0, i32* %p2
+  %x.inc = add i32 %x, %val
+  br label %loop
+}
+
+; can hoist out load with the default AST and the alias analysis mechanism.
+define void @test2(i32* %ptr) {
+; CHECK-LABEL: @test2(
+; CHECK-LABEL: entry:
+; CHECK: %val = load i32, i32* %ptr
+; CHECK-LABEL: loop:
+
+; ALIAS-N2-LABEL: @test2(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+entry:
+  br label %loop
+
+loop:
+  %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
+  %val = load i32, i32* %ptr
+  call void @foo(i64 4, i32* %ptr)
+  %x.inc = add i32 %x, %val
+  br label %loop
+}
+
+; cannot hoist load since not guaranteed to execute
+define void @test3(i32* %ptr) {
+; CHECK-LABEL: @test3(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: loop:
+; CHECK: %val = load i32, i32* %ptr
+
+; ALIAS-N2-LABEL: @test3(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+entry:
+  br label %loop
+
+loop:
+  %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
+  call void @foo(i64 4, i32* %ptr)
+  %val = load i32, i32* %ptr
+  %x.inc = add i32 %x, %val
+  br label %loop
+}