[EarlyCSE] Remove guards with conditions known to be true

If a condition is calculated only once, and there are multiple guards on this condition, we should be able
to remove all guards dominated by the first of them. This patch allows EarlyCSE to try to find the condition
of a guard among the known values, and if it is true, remove the guard. Otherwise we keep the guard and
mark its condition as 'true' for future consideration.

Reviewers: sanjoy, reames, apilipenko, skatkov, anna, dberlin

Reviewed By: reames, sanjoy

Subscribers: llvm-commits

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

llvm-svn: 301623

2 files changed, 174 insertions, 3 deletions

diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
index 04479b6e49a..da33c7aa836 100644
--- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -658,10 +658,25 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
       if (auto *CondI =
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
-        // The condition we're on guarding here is true for all dominated
-        // locations.
-        if (SimpleValue::canHandle(CondI))
+        if (SimpleValue::canHandle(CondI)) {
+          // Do we already know the actual value of this condition?
+          if (auto *KnownCond = AvailableValues.lookup(CondI)) {
+            // Is the condition known to be true?
+            if (isa<ConstantInt>(KnownCond) &&
+                cast<ConstantInt>(KnownCond)->isOneValue()) {
+              DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
+              removeMSSA(Inst);
+              Inst->eraseFromParent();
+              Changed = true;
+              continue;
+            } else
+              // Use the known value if it wasn't true.
+              cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
+          }
+          // The condition we're on guarding here is true for all dominated
+          // locations.
           AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+        }
       }
 
       // Guard intrinsics read all memory, but don't write any memory.
diff --git a/llvm/test/Transforms/EarlyCSE/guards.ll b/llvm/test/Transforms/EarlyCSE/guards.ll
index 55185f9fe56..5d1e3835c9a 100644
--- a/llvm/test/Transforms/EarlyCSE/guards.ll
+++ b/llvm/test/Transforms/EarlyCSE/guards.ll
@@ -180,3 +180,159 @@ define void @test6(i1 %c, i32* %ptr) {
   store i32 600, i32* %ptr
   ret void
 }
+
+define void @test07(i32 %a, i32 %b) {
+; Check that we are able to remove the guards on the same condition even if the
+; condition is not being recalculated.
+
+; CHECK-LABEL: @test07(
+; CHECK-NEXT:  %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:  ret void
+
+  %cmp = icmp eq i32 %a, %b
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  ret void
+}
+
+define void @test08(i32 %a, i32 %b, i32* %ptr) {
+; Check that we deal correctly with stores when removing guards in the same
+; block in case when the condition is not recalculated.
+
+; CHECK-LABEL: @test08(
+; CHECK-NEXT:  %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:  store i32 100, i32* %ptr
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:  store i32 400, i32* %ptr
+; CHECK-NEXT:  ret void
+
+  %cmp = icmp eq i32 %a, %b
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 200, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  ret void
+}
+
+define void @test09(i32 %a, i32 %b, i1 %c, i32* %ptr) {
+; Similar to test08, but with more control flow.
+; TODO: Can we get rid of the store in the end of entry given that it is
+; post-dominated by other stores?
+
+; CHECK-LABEL: @test09(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    store i32 100, i32* %ptr
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    store i32 400, i32* %ptr
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 500, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    store i32 600, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 200, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 500, i32* %ptr
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 600, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test10(i32 %a, i32 %b, i1 %c, i32* %ptr) {
+; Make sure that non-dominating guards do not cause other guards removal.
+
+; CHECK-LABEL: @test10(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    store i32 100, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    store i32 200, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    store i32 300, i32* %ptr
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    store i32 400, i32* %ptr
+; CHECK-NEXT:    ret void
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br label %merge
+
+if.false:
+  store i32 200, i32* %ptr
+  br label %merge
+
+merge:
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  ret void
+}
+
+define void @test11(i32 %a, i32 %b, i32* %ptr) {
+; Make sure that branching condition is applied to guards.
+
+; CHECK-LABEL: @test11(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    br i1 %cmp, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br label %merge
+
+merge:
+  ret void
+}