[EarlyCSE] Make branches unconditional if the condition is known

[mkazantsev]

Summary

If EarlyCSE has proved that branch condition is true/false, it can replace it with unconditional branch to the corresponding block.

[mkazantsev]

Added space in the debug message.

[efriedma]

EarlyCSE is supposed to preserve the CFG (calls setPreservesCFG, depends on DomTree/MemorySSA etc.), so you can't replace a conditional branch with an unconditional branch. Replacing the value of the condition with "true" or "false" is fine, though.

Why do we want to do this specifically for branches, as opposed to doing it for any instruction where we can prove an operand is constant?

[mkazantsev]

Needs rework (or maybe abandoning) since EarlyCSE is not supposed to change the CFG.

[mkazantsev]

Need a more general solution regarding scope, and also need to avoid breaking CFG. I will do it in a separate patch using another approach later.

lib/Transforms/Scalar/EarlyCSE.cpp

if (Inst->mayWriteToMemory()) {
         if (MemInst.isUnordered() && !MemInst.isVolatile())
           LastStore = Inst;
         else
           LastStore = nullptr;
       }
     }
   }
 
+  // Now take care of the block's terminator. If we know the condition being
+  // true or false, we can make it unconditional.
+  if (BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator()))
+    if (Term->isConditional())
+      if (Instruction *CondI = dyn_cast<Instruction>(Term->getCondition()))
+        if (SimpleValue::canHandle(CondI))
+          if (Value *KnownCond = AvailableValues.lookup(CondI)) {
+            BasicBlock *OnlySuccessor = nullptr;
+            if (KnownCond == ConstantInt::getTrue(BB->getContext()))
+              OnlySuccessor = Term->getSuccessor(0);
+            else if (KnownCond == ConstantInt::getFalse(BB->getContext()))
+              OnlySuccessor = Term->getSuccessor(1);
+
+            if (OnlySuccessor) {
+              DEBUG(dbgs() << "EarlyCSE replacing branch in block "
+                           << BB->getName() << " with unconditional to block "
+                           << OnlySuccessor->getName() << "\n");
+              Term->eraseFromParent();
+              BranchInst::Create(OnlySuccessor, BB);
+              Changed = true;
+            }
+          }
+
   return Changed;
 }
 
 bool EarlyCSE::run() {
   // Note, deque is being used here because there is significant performance
   // gains over vector when the container becomes very large due to the
   // specific access patterns. For more information see the mailing list
   // discussion on this:

test/Transforms/EarlyCSE/guards.ll

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:
if.false:
   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 @test_15(i32 %a, i32 %b, i32* %ptr) {
+; Make sure we can remove conditional branches basing on guards.
+
+; CHECK-LABEL: @test_15(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    br label %if.true
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 100, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:                                         ; No predecessors!
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br i1 %cmp, label %if.true, label %if.false
+
+if.true:
+  store i32 100, i32* %ptr
+  br label %merge
+
+if.false:
+  store i32 200, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test_15.unhandled(i32 %a, i32 %b, i32* %ptr) {
+; Demonstrate that we cannot chose branch basing on known guard by negative
+; condition. Once we handle it, if.false should be unconditionally taken.
+
+; CHECK-LABEL: @test_15.unhandled(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    %neg.cmp = icmp ne i32 %a, %b
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    br i1 %neg.cmp, label %if.true, label %if.false
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  %neg.cmp = icmp ne i32 %a, %b
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br i1 %neg.cmp, label %if.true, label %if.false
+
+if.true:
+  store i32 100, i32* %ptr
+  br label %merge
+
+if.false:
+  store i32 200, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test_16(i32 %a, i32 %b, i32* %ptr) {
+; Make sure we can remove conditional branches basing on assumes.
+
+; CHECK-LABEL: @test_16(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    call void @llvm.assume(i1 %cmp)
+; CHECK-NEXT:    br label %if.true
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 100, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:                                         ; No predecessors!
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  call void @llvm.assume(i1 %cmp)
+  br i1 %cmp, label %if.true, label %if.false
+
+if.true:
+  store i32 100, i32* %ptr
+  br label %merge
+
+if.false:
+  store i32 200, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test_16.unhandled(i32 %a, i32 %b, i32* %ptr) {
+; Demonstrate that we cannot chose branch basing on known assume by negative
+; condition. Once we handle it, if.false should be unconditionally taken.
+
+; CHECK-LABEL: @test_16.unhandled(
+; CHECK:       entry:
+; CHECK-NEXT:    %cmp = icmp eq i32 %a, %b
+; CHECK-NEXT:    %neg.cmp = icmp ne i32 %a, %b
+; CHECK-NEXT:    call void @llvm.assume(i1 %cmp)
+; CHECK-NEXT:    br i1 %neg.cmp, label %if.true, label %if.false
+
+entry:
+  %cmp = icmp eq i32 %a, %b
+  %neg.cmp = icmp ne i32 %a, %b
+  call void @llvm.assume(i1 %cmp)
+  br i1 %neg.cmp, label %if.true, label %if.false
+
+if.true:
+  store i32 100, i32* %ptr
+  br label %merge
+
+if.false:
+  store i32 200, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test_17(i32 %a, i32 %b, i32* %ptr) {
+; Similar to test_15, but with more complex control flow.
+
+; CHECK-LABEL: @test_17(
+; 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 label %if.true
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 500, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:                                         ; No predecessors!
+; 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
+}