[EarlyCSE] Remove guards with conditions known to be true

[mkazantsev]

Summary

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.

[reames]

lib/Transforms/Scalar/EarlyCSE.cpp

661

I think this would be a bit clearer if put under the canHandle branch. i.e.
if (canHandle(CondI)) {

if (auto *KnownCond = ...) {
  ...
}
AV.insert(CondI, True);

}

664

Use isa<ConstantInt>(KnownCond) && cast<ConstantInt>(KnownCond)->isOneValue();

This also might be a case where dyn_cast_or_null would be useful.
auto *KnownCond = ...
auto *KnownCondConst = dyn_cast_or_null...
if (KnownCondConst && KnownCondConst->isOneValue())

Finally, if we've inferred the value to constant false, we should replace the operand with the constant. Don't bother going beyond that for the moment (i.e. exploiting the unreached code), but there's no reason not to put in the constant.

test/Transforms/EarlyCSE/guards.ll

6

minor: submit a separate patch without further review for the test name changes to simplify the diff.

[reames]

test/Transforms/EarlyCSE/guards.ll

270

Not in EarlyCSE (which isn't allowed to modify CFG). We can fold the condition to false at use though. That should be a separate patch.

[mkazantsev]

Addressed the comments.

test/Transforms/EarlyCSE/guards.ll

6

Actually I've looked into other tests for EarlyCSE and decided to keep the naming as is for consistency.

[sanjoy]

lib/Transforms/Scalar/EarlyCSE.cpp

666

You should be able to do if (match(KnownCond, m_One())) to make it a bit more concise, but what you have now is fine too.

[reames]

LGTM

lib/Transforms/Scalar/EarlyCSE.cpp

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     // We can DSE the store to 30, since the store 40 to invariant location p
     // causes undefined behaviour.
     if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
       continue;
 
     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
       if (auto *CondI =
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
+        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.
-        if (SimpleValue::canHandle(CondI))
           AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
         }
+      }
 
       // Guard intrinsics read all memory, but don't write any memory.
       // Accordingly, don't update the generation but consume the last store (to
       // avoid an incorrect DSE).
       LastStore = nullptr;
       continue;
     }
 

test/Transforms/EarlyCSE/guards.ll

 ; RUN: opt -S -early-cse < %s | FileCheck %s
 ; RUN: opt < %s -S -basicaa -early-cse-memssa | FileCheck %s
 
 declare void @llvm.experimental.guard(i1,...)
 
 define i32 @test0(i32* %ptr, i1 %cond) {
 ; We can do store to load forwarding over a guard, since it does not
 ; clobber memory
 
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:  store i32 40, i32* %ptr
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
 ; CHECK-NEXT:  ret i32 40
 

 ; CHECK-NEXT:  store i32 600, i32* %ptr
 
 
   store i32 500, i32* %ptr
   call void(i1,...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
   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
+}