[SimpleLoopUnswitch] remove a chain of dead blocks at once

[fedor.sergeev]

Summary

Recent change to deleteDeadBlocksFromLoop was not enough to
fix all the problems related to dead blocks after nontrivial
unswitching of switches.

We need to delete all the dead blocks that were created during
unswitching, otherwise we will keep having problems with phi's
or dead blocks.

This change removes all the dead blocks that are reachable from the loop,
not trying to track whether these blocks are newly created by unswitching
or not. While not completely correct, we are unlikely to get loose but
reachable dead blocks that do not belong to our loop nest.

It does fix all the failures currently known, in particular PR38778.

[fedor.sergeev]

correcting typo

[asbirlea]

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

1396

Do we need to go over all parent loops now? Processing the successors of each block in DeathCandidates may be enough. It at least resolves testcase delete-dead-blocks.ll which motivated processing blocks in parent loops.

1398

Could we pull the while outside the for loop?
And populate the initial DeathCandidates with ExitBlocks and loop blocks?

[fedor.sergeev]

addressing comments:

• populate candidates with current loop blocks + exit blocks
• run candidate loop separately after that

Also removed DeadBlocks vector since it duplicates the set
and is not actively used.

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

deleteDeadClonedBlocks(Loop &L, ArrayRef<BasicBlock *> ExitBlocks,
   for (BasicBlock *BB : DeadBlocks)
     BB->eraseFromParent();
 }
 
 static void
 deleteDeadBlocksFromLoop(Loop &L,
                          SmallVectorImpl<BasicBlock *> &ExitBlocks,
                          DominatorTree &DT, LoopInfo &LI) {
-  // Find all the dead blocks, and remove them from their successors.
-  SmallVector<BasicBlock *, 16> DeadBlocks;
-  for (BasicBlock *BB : ExitBlocks)
-    if (!DT.isReachableFromEntry(BB)) {
-      for (BasicBlock *SuccBB : successors(BB))
+  // Find all the dead blocks tied to this loop, and remove them from their
+  // successors.
+  SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
+
+  // Start with loop/exit blocks and get a transitive closure of reachable dead
+  // blocks.
+  SmallVector<BasicBlock *, 16> DeathCandidates(ExitBlocks.begin(),
+                                                ExitBlocks.end());
+  DeathCandidates.append(L.blocks().begin(), L.blocks().end());
+  while (!DeathCandidates.empty()) {
+    auto *BB = DeathCandidates.pop_back_val();
+    if (!DeadBlockSet.count(BB) && !DT.isReachableFromEntry(BB)) {
+      for (BasicBlock *SuccBB : successors(BB)) {
         SuccBB->removePredecessor(BB);
-      DeadBlocks.push_back(BB);
+        DeathCandidates.push_back(SuccBB);
+      }
+      DeadBlockSet.insert(BB);
     }
-
-  for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop())
-    for (BasicBlock *BB : ParentL->blocks())
-      if (!DT.isReachableFromEntry(BB)) {
-        for (BasicBlock *SuccBB : successors(BB))
-          SuccBB->removePredecessor(BB);
-        DeadBlocks.push_back(BB);
-      }
-
-  SmallPtrSet<BasicBlock *, 16> DeadBlockSet(DeadBlocks.begin(),
-                                             DeadBlocks.end());
 
   // Filter out the dead blocks from the exit blocks list so that it can be
   // used in the caller.
   llvm::erase_if(ExitBlocks,
                  [&](BasicBlock *BB) { return DeadBlockSet.count(BB); });
 
   // Walk from this loop up through its parents removing all of the dead blocks.
   for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) {
-    for (auto *BB : DeadBlocks)
+    for (auto *BB : DeadBlockSet)
       ParentL->getBlocksSet().erase(BB);
     llvm::erase_if(ParentL->getBlocksVector(),
                    [&](BasicBlock *BB) { return DeadBlockSet.count(BB); });
   }
 
   // Now delete the dead child loops. This raw delete will clear them
   // recursively.
   llvm::erase_if(L.getSubLoopsVector(), [&](Loop *ChildL) {
     if (!DeadBlockSet.count(ChildL->getHeader()))
       return false;
 
     assert(llvm::all_of(ChildL->blocks(),
                         [&](BasicBlock *ChildBB) {
                           return DeadBlockSet.count(ChildBB);
                         }) &&
            "If the child loop header is dead all blocks in the child loop must "
            "be dead as well!");
     LI.destroy(ChildL);
     return true;
   });
 
   // Remove the loop mappings for the dead blocks and drop all the references
   // from these blocks to others to handle cyclic references as we start
   // deleting the blocks themselves.
-  for (auto *BB : DeadBlocks) {
+  for (auto *BB : DeadBlockSet) {
     // Check that the dominator tree has already been updated.
     assert(!DT.getNode(BB) && "Should already have cleared domtree!");
     LI.changeLoopFor(BB, nullptr);
     BB->dropAllReferences();
   }
 
   // Actually delete the blocks now that they've been fully unhooked from the
   // IR.

test/Transforms/SimpleLoopUnswitch/delete-dead-blocks.ll

outer_continue:
   %ocmp = icmp eq i32 %oi, 100
   br i1 %ocmp, label %outer, label %get_out
 
 get_out:
   ret void
 get_out2:
   unreachable
 }
+
+;
+; This comes from PR38778
+; CHECK-LABEL: @Test2
+define void @Test2(i32) {
+header:
+  br label %loop
+loop:
+  switch i32 %0, label %continue [
+    i32 -2147483648, label %check
+    i32 98, label %guarded1
+    i32 99, label %guarded2
+  ]
+; CHECK-NOT: {{^}}guarded1:
+guarded1:
+  br i1 undef, label %continue, label %leave
+guarded2:
+  br label %continue
+check:
+  %val = add i32 0, 1
+  br i1 undef, label %continue, label %leave
+continue:
+  br label %loop
+leave:
+  %local = phi i32 [ 0, %guarded1 ], [ %val, %check ]
+  ret void
+}
+
+;
+; Yet another test from PR38778
+;
+; CHECK-LABEL: @Test3
+define void @Test3(i32) {
+header:
+  br label %outer
+outer:
+  %bad_input.i = icmp eq i32 %0, -2147483648
+  br label %inner
+inner:
+  br i1 %bad_input.i, label %overflow, label %switchme
+overflow:
+  br label %continue
+switchme:
+  switch i32 %0, label %continue [
+    i32 88, label %go_out
+    i32 99, label %case2
+  ]
+; CHECK-NOT: {{^}}case2:
+case2:
+  br label %continue
+continue:
+  %local_11_92 = phi i32 [ 0, %switchme ], [ 18, %case2 ], [ 0, %overflow ]
+  br i1 undef, label %outer, label %inner
+go_out:
+  unreachable
+}