[SimplifyCFG] Don't widen cond br to cond br if false branch has successors

[dmakogon]

Summary

This fixes an infinite loop of transformations in SimplifyCFG (GItHub issue - https://github.com/llvm/llvm-project/issues/57221).
The problem is that there are two transforms in SimplifyCFG that do absolutely opposite things.
First, there is tryWidenCondBranchToCondBranch which does the following.
When it sees a branch on widenable condition followed by another conditional branch like here:

bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb4

it thinks that it's profitable for bb2 to branch to bb1 instead of bb7 on true condition.
The IR after the transform:

bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  br i1 undef, label %bb1, label %bb4

Then, there is another transformation SimplifyCondBranchToCondBranch. It sees that bb2 branches to bb1 if the condition is true and that bb1 has the same condition. So instead of bb2->bb1->bb7 branches, it makes it just bb2->bb7 - the exact same IR before the first transform.

This patch limits the tryWidenCondBranchToCondBranch transform making it work only if the false block of widenable condition branch has no successors.
If that block has successors, then the possible impact of the transform is complicated. SimplifyCFG may apply other transforms after this one and produce unexpected results.
As far as I can see this transform only has impact when the no succesors condition stands.

[apilipenko]

So, you are crippling this transformation to avoid an infinite loop with another transform in SimplifyCFG. This is probably OK as we still handle the common case of a widenable condition going to a deoptimization block.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

4010

No need to check it twice. Just check if after line 4001 once.

Also, please add a comment on why you are restricting this transformation with a TODO to find a more fine-grained solution.

llvm/test/Transforms/SimplifyCFG/pr52290.ll

32

Before you make this change, please, update the tests and remove branching on undef. This is UB and the optimizer can do whatever for this test. This can be done in a separate patch without additional review.

[dmakogon]

Hoisted the condition, added comments & updated test to not branch on undef but on a normal value

[mkazantsev]

Is it true that every block which has successors will necessarily fall into this infinite loop? If so, it's not crippling.

[apilipenko]

Is it true that every block which has successors will necessarily fall into this infinite loop?

No. What is special about this test is the fact that bb1 and bb2 have a branch on the same condition (undef).

[apilipenko]

LGTM with a small comment to address.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

4002–4004

Unless you know of any other transformation cycles, just say that we prevent a cyclic transformation with SimplifyCondBranchToCondBranch.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
   //    BI's condition.
   Value *CondWB, *WC;
   BasicBlock *IfTrueBB, *IfFalseBB;
   if (!parseWidenableBranch(PBI, CondWB, WC, IfTrueBB, IfFalseBB) ||
       IfTrueBB != BI->getParent() || !BI->getParent()->getSinglePredecessor())
     return false;
   if (!IfFalseBB->phis().empty())
     return false; // TODO
   // Use lambda to lazily compute expensive condition after cheap ones.
   auto NoSideEffects = [](BasicBlock &BB) {
     return llvm::none_of(BB, [](const Instruction &I) {
         return I.mayWriteToMemory() || I.mayHaveSideEffects();
       });
   };
   if (BI->getSuccessor(1) != IfFalseBB && // no inf looping
       BI->getSuccessor(1)->getTerminatingDeoptimizeCall() && // profitability
+      llvm::succ_empty(IfFalseBB) &&
       NoSideEffects(*BI->getParent())) {
     auto *OldSuccessor = BI->getSuccessor(1);
     OldSuccessor->removePredecessor(BI->getParent());
     BI->setSuccessor(1, IfFalseBB);
     if (DTU)
       DTU->applyUpdates(
           {{DominatorTree::Insert, BI->getParent(), IfFalseBB},
            {DominatorTree::Delete, BI->getParent(), OldSuccessor}});
     return true;
   }
   if (BI->getSuccessor(0) != IfFalseBB && // no inf looping
       BI->getSuccessor(0)->getTerminatingDeoptimizeCall() && // profitability
+      llvm::succ_empty(IfFalseBB) &&
       NoSideEffects(*BI->getParent())) {
     auto *OldSuccessor = BI->getSuccessor(0);
     OldSuccessor->removePredecessor(BI->getParent());
     BI->setSuccessor(0, IfFalseBB);
     if (DTU)
       DTU->applyUpdates(
           {{DominatorTree::Insert, BI->getParent(), IfFalseBB},
            {DominatorTree::Delete, BI->getParent(), OldSuccessor}});

llvm/test/Transforms/SimplifyCFG/pr52290.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 ; RUN: opt < %s -passes=simplifycfg -S | FileCheck %s
 
-; XFAIL: *
-; REQUIRES: asserts
-; FIXME: Fails due to infinite loop in iterativelySimplifyCFG.
-
 ; ModuleID = 'test/Transforms/SimplifyCFG/pr-new.ll'
 source_filename = "test/Transforms/SimplifyCFG/pr-new.ll"
 
 define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
-; CHECK-LABEL: @test
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    br i1 [[TMP]], label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 undef, label [[BB7:%.*]], label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
+; CHECK-NEXT:    br i1 undef, label [[BB7]], label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    call void @snork() [ "deopt"() ]
+; CHECK-NEXT:    unreachable
+; CHECK:       bb5:
+; CHECK-NEXT:    ret i32 0
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP8:%.*]] = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
+; CHECK-NEXT:    ret i32 [[TMP8]]
+;
 bb:
   %tmp = call i1 @llvm.experimental.widenable.condition()
   br i1 %tmp, label %bb2, label %bb1
 
 bb1:                                              ; preds = %bb
   br i1 undef, label %bb7, label %bb5
 
 bb2:                                              ; preds = %bb
   %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
   br i1 undef, label %bb6, label %bb4
 
 bb4:                                              ; preds = %bb2
   call void @snork() [ "deopt"() ]
   unreachable