Make processing @llvm.assume more efficient by using operand bundles

There was an efficiency problem with how we processed @llvm.assume in
ValueTracking (and other places). The AssumptionCache tracked all of the
assumptions in a given function. In order to find assumptions relevant to
computing known bits, etc. we searched every assumption in the function. For
ValueTracking, that means that we did O(#assumes * #values) work in InstCombine
and other passes (with a constant factor that can be quite large because we'd
repeat this search at every level of recursion of the analysis).

Several of us discussed this situation at the last developers' meeting, and
this implements the discussed solution: Make the values that an assume might
affect operands of the assume itself. To avoid exposing this detail to
frontends and passes that need not worry about it, I've used the new
operand-bundle feature to add these extra call "operands" in a way that does
not affect the intrinsic's signature. I think this solution is relatively
clean. InstCombine adds these extra operands based on what ValueTracking, LVI,
etc. will need and then those passes need only search the users of the values
under consideration. This should fix the computational-complexity problem.

At this point, no passes depend on the AssumptionCache, and so I'll remove
that as a follow-up change.

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

llvm-svn: 289755

9 files changed, 38 insertions, 38 deletions

diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/conflict.ll b/llvm/test/Transforms/CorrelatedValuePropagation/conflict.ll
index ef566856ed7..35623ee9c12 100644
--- a/llvm/test/Transforms/CorrelatedValuePropagation/conflict.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/conflict.ll
@@ -26,7 +26,7 @@ declare void @llvm.assume(i1)
 define i8 @test2(i8 %a) {
 ; CHECK-LABEL: @test2
   %cmp1 = icmp eq i8 %a, 5
-  call void @llvm.assume(i1 %cmp1)
+  call void @llvm.assume(i1 %cmp1) [ "affected"(i8 %a) ]
   %cmp2 = icmp eq i8 %a, 3
 ; CHECK: br i1 false, label %dead, label %exit
   br i1 %cmp2, label %dead, label %exit
@@ -43,7 +43,7 @@ define i8 @test3(i8 %a) {
 dead:
   %cmp2 = icmp eq i8 %a, 3
 ; CHECK: call void @llvm.assume(i1 false)
-  call void @llvm.assume(i1 %cmp2)
+  call void @llvm.assume(i1 %cmp2) [ "affected"(i8 %a) ]
   ret i8 %a
 exit:
   ret i8 0
diff --git a/llvm/test/Transforms/InstCombine/assume-redundant.ll b/llvm/test/Transforms/InstCombine/assume-redundant.ll
index 4bdbcc8d086..4e18d0ab90c 100644
--- a/llvm/test/Transforms/InstCombine/assume-redundant.ll
+++ b/llvm/test/Transforms/InstCombine/assume-redundant.ll
@@ -11,7 +11,7 @@ target triple = "x86_64-unknown-linux-gnu"
 define void @_Z3fooR1s(%struct.s* nocapture readonly dereferenceable(8) %x) #0 {
 
 ; CHECK-LABEL: @_Z3fooR1s
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %maskcond) [ "affected"(i64 %maskedptr, i64 %ptrint, double* %{{.*}}) ]
 ; CHECK-NOT: call void @llvm.assume
 
 entry:
diff --git a/llvm/test/Transforms/InstCombine/assume.ll b/llvm/test/Transforms/InstCombine/assume.ll
index 2f9213820f2..da935925197 100644
--- a/llvm/test/Transforms/InstCombine/assume.ll
+++ b/llvm/test/Transforms/InstCombine/assume.ll
@@ -11,7 +11,7 @@ entry:
 ; been removed:
 ; CHECK-LABEL: @foo1
 ; CHECK-DAG: load i32, i32* %a, align 32
-; CHECK-DAG: call void @llvm.assume
+; CHECK-DAG: call void @llvm.assume(i1 %maskcond) [ "affected"(i64 %maskedptr, i64 %ptrint, i32* %a) ]
 ; CHECK: ret i32
 
   %ptrint = ptrtoint i32* %a to i64
@@ -28,7 +28,7 @@ entry:
 ; Same check as in @foo1, but make sure it works if the assume is first too.
 ; CHECK-LABEL: @foo2
 ; CHECK-DAG: load i32, i32* %a, align 32
-; CHECK-DAG: call void @llvm.assume
+; CHECK-DAG: call void @llvm.assume(i1 %maskcond) [ "affected"(i64 %maskedptr, i64 %ptrint, i32* %a) ]
 ; CHECK: ret i32
 
   %ptrint = ptrtoint i32* %a to i64
@@ -51,7 +51,7 @@ entry:
 ; CHECK: ret i32 4
 
   %cmp = icmp eq i32 %a, 4
-  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
   ret i32 %a
 }
 
@@ -93,7 +93,7 @@ entry:
   %and1 = and i32 %a, 3
 
 ; CHECK-LABEL: @bar1
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 1
 
   %and = and i32 %a, 7
@@ -107,7 +107,7 @@ entry:
 define i32 @bar2(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @bar2
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 1
 
   %and = and i32 %a, 7
@@ -125,7 +125,7 @@ entry:
 
 ; Don't be fooled by other assumes around.
 ; CHECK-LABEL: @bar3
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 1
 
   tail call void @llvm.assume(i1 %x)
@@ -145,8 +145,8 @@ entry:
   %and1 = and i32 %b, 3
 
 ; CHECK-LABEL: @bar4
-; CHECK: call void @llvm.assume
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
+; CHECK: call void @llvm.assume(i1 %cmp2) [ "affected"(i32 %a, i32 %b) ]
 ; CHECK: ret i32 1
 
   %and = and i32 %a, 7
@@ -167,7 +167,7 @@ entry:
   ret i32 %conv
 
 ; CHECK-LABEL: @icmp1
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 1
 
 }
@@ -182,7 +182,7 @@ entry:
   ret i32 %lnot.ext
 
 ; CHECK-LABEL: @icmp2
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 0
 }
 
@@ -217,7 +217,7 @@ entry:
 
 ; CHECK-LABEL: @nonnull2
 ; CHECK-NOT: !nonnull
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %load) ]
 }
 
 ; Make sure the above canonicalization does not trigger
@@ -236,7 +236,7 @@ not_taken:
 
 ; CHECK-LABEL: @nonnull3
 ; CHECK-NOT: !nonnull
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32* %load) ]
 }
 
 ; Make sure the above canonicalization does not trigger
@@ -254,7 +254,7 @@ entry:
 
 ; CHECK-LABEL: @nonnull4
 ; CHECK-NOT: !nonnull
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32* %load) ]
 }
 
 
diff --git a/llvm/test/Transforms/InstCombine/assume2.ll b/llvm/test/Transforms/InstCombine/assume2.ll
index c41bbaa04eb..65bc2f962af 100644
--- a/llvm/test/Transforms/InstCombine/assume2.ll
+++ b/llvm/test/Transforms/InstCombine/assume2.ll
@@ -9,7 +9,7 @@ declare void @llvm.assume(i1) #1
 define i32 @test1(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test1
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 5
 
   %and = and i32 %a, 15
@@ -24,7 +24,7 @@ entry:
 define i32 @test2(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test2
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a.not, i32 %a) ]
 ; CHECK: ret i32 2
 
   %and = and i32 %a, 15
@@ -40,7 +40,7 @@ entry:
 define i32 @test3(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test3
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v, i32 %a) ]
 ; CHECK: ret i32 5
 
   %v = or i32 %a, 4294967280
@@ -55,7 +55,7 @@ entry:
 define i32 @test4(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test4
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a.not, i32 %a) ]
 ; CHECK: ret i32 2
 
   %v = or i32 %a, 4294967280
@@ -71,7 +71,7 @@ entry:
 define i32 @test5(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test5
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 4
 
   %v = xor i32 %a, 1
@@ -86,7 +86,7 @@ entry:
 define i32 @test6(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test6
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v.mask, i32 %a) ]
 ; CHECK: ret i32 5
 
   %v = shl i32 %a, 2
@@ -101,7 +101,7 @@ entry:
 define i32 @test7(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test7
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v.mask, i32 %a) ]
 ; CHECK: ret i32 20
 
   %v = lshr i32 %a, 2
@@ -116,7 +116,7 @@ entry:
 define i32 @test8(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test8
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v.mask, i32 %a) ]
 ; CHECK: ret i32 20
 
   %v = lshr i32 %a, 2
@@ -131,7 +131,7 @@ entry:
 define i32 @test9(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test9
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 0
 
   %cmp = icmp sgt i32 %a, 5
@@ -145,7 +145,7 @@ entry:
 define i32 @test10(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test10
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 -2147483648
 
   %cmp = icmp sle i32 %a, -2
@@ -159,7 +159,7 @@ entry:
 define i32 @test11(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test11
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 0
 
   %cmp = icmp ule i32 %a, 256
diff --git a/llvm/test/Transforms/InstSimplify/add-mask.ll b/llvm/test/Transforms/InstSimplify/add-mask.ll
index e30a35f5312..ac2447ac3a6 100644
--- a/llvm/test/Transforms/InstSimplify/add-mask.ll
+++ b/llvm/test/Transforms/InstSimplify/add-mask.ll
@@ -46,7 +46,7 @@ define i1 @test4(i32 %a) {
   %b = load i32, i32* @B
   %b.and = and i32 %b, 1
   %b.cnd = icmp eq i32 %b.and, 1
-  call void @llvm.assume(i1 %b.cnd)
+  call void @llvm.assume(i1 %b.cnd) [ "affected"(i32 %b.and, i32 %b) ]
 
   %rhs = add i32 %a, %b
   %and = and i32 %a, %rhs
diff --git a/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll b/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll
index f1d0f41e250..ff087693ea8 100644
--- a/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll
+++ b/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll
@@ -14,12 +14,12 @@ entry:
 taken:
     %res1 = call i8* @escape()
     %a = icmp eq i8* %res1, null
-    tail call void @llvm.assume(i1 %a)
+    tail call void @llvm.assume(i1 %a) [ "affected"(i8* %res1) ]
     br label %done
 not_taken:
     %res2 = call i8* @escape()
     %b = icmp ne i8* %res2, null
-    tail call void @llvm.assume(i1 %b)
+    tail call void @llvm.assume(i1 %b) [ "affected"(i8* %res2) ]
     br label %done
 
 ; An assume that can be used to simplify this comparison dominates each
diff --git a/llvm/test/Transforms/JumpThreading/assume.ll b/llvm/test/Transforms/JumpThreading/assume.ll
index 53010b71c72..fdaa07ff131 100644
--- a/llvm/test/Transforms/JumpThreading/assume.ll
+++ b/llvm/test/Transforms/JumpThreading/assume.ll
@@ -6,7 +6,7 @@ target triple = "x86_64-unknown-linux-gnu"
 define i32 @test1(i32 %a, i32 %b) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
-  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
   %cmp1 = icmp sgt i32 %b, 1234
   br i1 %cmp1, label %if.then, label %if.else
 
@@ -36,7 +36,7 @@ return:                                           ; preds = %if.else, %if.then,
 define i32 @test2(i32 %a) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
-  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
   %cmp1 = icmp sgt i32 %a, 3
   br i1 %cmp1, label %if.then, label %return
 
diff --git a/llvm/test/Transforms/NaryReassociate/NVPTX/nary-gep.ll b/llvm/test/Transforms/NaryReassociate/NVPTX/nary-gep.ll
index a08e07e9644..827f6445e38 100644
--- a/llvm/test/Transforms/NaryReassociate/NVPTX/nary-gep.ll
+++ b/llvm/test/Transforms/NaryReassociate/NVPTX/nary-gep.ll
@@ -75,10 +75,10 @@ define void @reassociate_gep_assume(float* %a, i32 %i, i32 %j) {
 ; CHECK-LABEL: @reassociate_gep_assume(
   ; assume(j >= 0)
   %cmp = icmp sgt i32 %j, -1
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i32 %j) ]
   %1 = add i32 %i, %j
   %cmp2 = icmp sgt i32 %1, -1
-  call void @llvm.assume(i1 %cmp2)
+  call void @llvm.assume(i1 %cmp2) [ "affected"(i32 %1) ]
 
   %idxprom.j = zext i32 %j to i64
   %2 = getelementptr float, float* %a, i64 %idxprom.j
diff --git a/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll b/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll
index e5c2ef65b31..c77b3e2335e 100644
--- a/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll
+++ b/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll
@@ -91,7 +91,7 @@ define void @test5(i8 %a) {
 ; CHECK-LABEL: @test5
 ; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
   %cmp = icmp ult i8 %a, 2 
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %a) ]
   switch i8 %a, label %default [i8 1, label %true
                                 i8 0, label %false]
 true:
@@ -112,7 +112,7 @@ define void @test6(i8 %a) {
 ; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254 
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %and, i8 %a) ]
   switch i8 %a, label %default [i8 255, label %true
                                 i8 254, label %false]
 true:
@@ -134,7 +134,7 @@ define void @test7(i8 %a) {
 ; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254 
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %and, i8 %a) ]
   switch i8 %a, label %default [i8 255, label %true
                                 i8 254, label %false
                                 i8 0, label %also_dead]
@@ -162,7 +162,7 @@ define void @test8(i8 %a) {
 ; CHECK: switch i8
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, undef
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %and, i8 %a) ]
   switch i8 %a, label %default [i8 255, label %true
                                 i8 254, label %false]
 true: