[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

679

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))) {
+        // Do we already know the actual value of this condition?
+        if (auto *KnownCond = AvailableValues.lookup(CondI)) {
+          // Is the condition known to be true?
+          if (KnownCond == ConstantInt::getTrue(BB->getContext())) {
+            DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
+            removeMSSA(Inst);
+            Inst->eraseFromParent();
+            Changed = true;
+            continue;
+          }
+        }
         // 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;
     }
 
     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
     // its simpler value.
     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {

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) {
+define i32 @test_00(i32* %ptr, i1 %cond) {
 ; We can do store to load forwarding over a guard, since it does not
 ; clobber memory
 
-; CHECK-LABEL: @test0(
+; CHECK-LABEL: @test_00(
 ; CHECK-NEXT:  store i32 40, i32* %ptr
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
 ; CHECK-NEXT:  ret i32 40
 
   store i32 40, i32* %ptr
   call void(i1,...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
   %rval = load i32, i32* %ptr
   ret i32 %rval
 }
 
-define i32 @test1(i32* %val, i1 %cond) {
+define i32 @test_01(i32* %val, i1 %cond) {
 ; We can CSE loads over a guard, since it does not clobber memory
 
-; CHECK-LABEL: @test1(
+; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  %val0 = load i32, i32* %val
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
 ; CHECK-NEXT:  ret i32 0
 
   %val0 = load i32, i32* %val
   call void(i1,...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
   %val1 = load i32, i32* %val
   %rval = sub i32 %val0, %val1
   ret i32 %rval
 }
 
-define i32 @test2() {
+define i32 @test_02() {
 ; Guards on "true" get removed
 
-; CHECK-LABEL: @test2(
+; CHECK-LABEL: @test_02(
 ; CHECK-NEXT: ret i32 0
   call void(i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
   ret i32 0
 }
 
-define i32 @test3(i32 %val) {
+define i32 @test_03(i32 %val) {
 ; After a guard has executed the condition it was guarding is known to
 ; be true.
 
-; CHECK-LABEL: @test3(
+; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  %cond0 = icmp slt i32 %val, 40
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
 ; CHECK-NEXT:  ret i32 -1
 
   %cond0 = icmp slt i32 %val, 40
   call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
   %cond1 = icmp slt i32 %val, 40
   call void(i1,...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
 
   %cond2 = icmp slt i32 %val, 40
   %rval = sext i1 %cond2 to i32
   ret i32 %rval
 }
 
-define i32 @test3.unhandled(i32 %val) {
+define i32 @test_03.unhandled(i32 %val) {
 ; After a guard has executed the condition it was guarding is known to
 ; be true.
 
-; CHECK-LABEL: @test3.unhandled(
+; CHECK-LABEL: @test_03.unhandled(
 ; CHECK-NEXT:  %cond0 = icmp slt i32 %val, 40
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
 ; CHECK-NEXT:  %cond1 = icmp sge i32 %val, 40
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
 ; CHECK-NEXT:  ret i32 0
 
 ; Demonstrates a case we do not yet handle (it is legal to fold %cond2
 ; to false)
   %cond0 = icmp slt i32 %val, 40
   call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
   %cond1 = icmp sge i32 %val, 40
   call void(i1,...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
   ret i32 0
 }
 
-define i32 @test4(i32 %val, i1 %c) {
+define i32 @test_04(i32 %val, i1 %c) {
 ; Same as test3, but with some control flow involved.
 
-; CHECK-LABEL: @test4(
+; CHECK-LABEL: @test_04(
 ; CHECK: entry:
 ; CHECK-NEXT:  %cond0 = icmp slt i32 %val, 40
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond0
 ; CHECK-NEXT:  br label %bb0
 
 ; CHECK:     bb0:
 ; CHECK-NEXT:  %cond2 = icmp ult i32 %val, 200
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond2
left:
   %cond3 = icmp ult i32 %val, 200
   call void(i1,...) @llvm.experimental.guard(i1 %cond3) [ "deopt"() ]
   ret i32 0
 
 right:
  ret i32 20
 }
 
-define i32 @test5(i32 %val, i1 %c) {
+define i32 @test_05(i32 %val, i1 %c) {
 ; Same as test4, but the %left block has mutliple predecessors.
 
-; CHECK-LABEL: @test5(
+; CHECK-LABEL: @test_05(
 
 ; CHECK: entry:
 ; CHECK-NEXT:  %cond0 = icmp slt i32 %val, 40
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond0
 ; CHECK-NEXT:  br label %bb0
 
 ; CHECK: bb0:
 ; CHECK-NEXT:  %cond2 = icmp ult i32 %val, 200
left:
   %cond3 = icmp ult i32 %val, 200
   call void(i1,...) @llvm.experimental.guard(i1 %cond3) [ "deopt"() ]
   br label %right
 
 right:
   br label %left
 }
 
-define void @test6(i1 %c, i32* %ptr) {
+define void @test_06(i1 %c, i32* %ptr) {
 ; Check that we do not DSE over calls to @llvm.experimental.guard.
 ; Guard intrinsics do _read_ memory, so th call to guard below needs
 ; to see the store of 500 to %ptr
 
-; CHECK-LABEL: @test6(
+; CHECK-LABEL: @test_06(
 ; CHECK-NEXT:  store i32 500, i32* %ptr
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
 ; 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 @test_07(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: @test_07(
+; 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 @test_08(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: @test_08(
+; 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 @test_09(i32 %a, i32 %b, i1 %c, i32* %ptr) {
+; Similar to test_08, 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: @test_09(
+; 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 @test_09.unhandled(i32 %a, i32 %b, i32* %ptr) {
+; Demonstrates the case we do not currently cover: branch by guarded condition.
+; We can replace the branching by cmp condition by unconditional branch.
+
+; CHECK-LABEL: @test_09.unhandled(
+; 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 %cmp, 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:    call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; 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 %cmp, 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 @test_10(i32 %a, i32 %b, i1 %c, i32* %ptr) {
+; Make sure that non-dominating guards do not cause other guards removal.
+
+; CHECK-LABEL: @test_10(
+; 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
+}