[LoopSimplifyCFG] Fix order of deletion of complex dead subloops

[mkazantsev]

Summary

Function DeleteDeadBlock requires that all predecessors of a block
being deleted have already been deleted, with the exception of a
single-block loop. When we use it for removal of dead subloops that
contain more than one block, we may not fulfull this requirement and
fail an assertion.

This patch replaces invocation of DeleteDeadBlock with a generalized
version DeleteDeadBlocks that is able to deal with multiple dead blocks,
even if they contain some cycles.

[fedor.sergeev]

LGTM.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

for (auto *BB : DeadLoopBlocks) {
              "Header of the current loop cannot be dead!");
       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
                         << "\n");
       if (LI.isLoopHeader(BB)) {
         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
         LI.erase(LI.getLoopFor(BB));
       }
       LI.removeBlock(BB);
-      DeleteDeadBlock(BB, &DTU);
-      ++NumLoopBlocksDeleted;
     }
+
+    DeleteDeadBlocks(DeadLoopBlocks, &DTU);
+    NumLoopBlocksDeleted += DeadLoopBlocks.size();
   }
 
   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
   /// unconditional branches.
   void foldTerminators() {
     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 
     for (BasicBlock *BB : FoldCandidates) {

test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; XFAIL: *
-; Tests complex_dead_subloop_branch and complex_dead_subloop_switch fail an
-; assertion, therefore the CFG simplification is temporarily disabled.
 ; REQUIRES: asserts
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
 ; Make sure that we can eliminate a provably dead backedge.
loop_1_backedge:
   %c_1 = icmp slt i32 %i.next, %N
   br i1 %c_1, label %loop_1, label %exit
 
 exit:
   ret i32 %i
 }
 
 define i32 @complex_dead_subloop_branch(i1 %cond1, i1 %cond2, i1 %cond3) {
+; CHECK-LABEL: @complex_dead_subloop_branch(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RESULT_LCSSA:%.*]] = phi i32 [ 0, [[LOOP]] ]
+; CHECK-NEXT:    ret i32 [[RESULT_LCSSA]]
+;
 entry:
   br label %loop
 
 loop:
   br i1 true, label %latch, label %subloop
 
 subloop:
   br i1 %cond1, label %x, label %y
latch:
   %result = phi i32 [ 0, %loop ], [ %dead_phi, %subloop_latch ]
   br i1 %cond3, label %loop, label %exit
 
 exit:
   ret i32 %result
 }
 
 define i32 @complex_dead_subloop_switch(i1 %cond1, i1 %cond2, i1 %cond3) {
+; CHECK-LABEL: @complex_dead_subloop_switch(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RESULT_LCSSA:%.*]] = phi i32 [ 0, [[LOOP]] ]
+; CHECK-NEXT:    ret i32 [[RESULT_LCSSA]]
+;
 entry:
   br label %loop
 
 loop:
   switch i32 1, label %latch [ i32 0, label %subloop ]
 
 subloop:
   br i1 %cond1, label %x, label %y