[Dominators] Make RemoveUnreachableBlocks return false if the BasicBlock is already awaiting deletion

[NutshellySima]

Summary

Previously, removeUnreachableBlocks still returns true (which indicates the CFG is changed) even when all the unreachable blocks found is awaiting deletion in the DDT class.
This makes code pattern like

// Code modified from lib/Transforms/Scalar/SimplifyCFGPass.cpp 
bool EverChanged = removeUnreachableBlocks(F, nullptr, DDT);
...
do {
    EverChanged = someMightHappenModifications();
    EverChanged |= removeUnreachableBlocks(F, nullptr, DDT);
  } while (EverChanged);

become a dead loop.
Fix this by detecting whether a BasicBlock is already awaiting deletion.

[NutshellySima]

Rebase to use the DomTreeUpdater interface.

[NutshellySima]

rebase

[kuhar]

Looks fine except for the test IR.

unittests/Transforms/Utils/Local.cpp

752

I don't think it's valid to branch to entry (the entry block is supposed to have no predecessors).

[NutshellySima]

Address comments.

[brzycki]

OK by me. Probably won't save much compile time but it is a bit cleaner to read.

lib/Transforms/Utils/Local.cpp

if (DTU) {
       ++I;
     } else {
       I = F.getBasicBlockList().erase(I);
     }
   }
 
   if (DTU) {
     DTU->applyUpdates(Updates, /*ForceDeduplication*/ true);
-    for (auto *BB : ToDeleteBBs)
+    bool Deleted = false;
+    for (auto *BB : ToDeleteBBs) {
+      if (DTU->isBBPendingDeletion(BB))
+        --NumRemoved;
+      else
+        Deleted = true;
       DTU->deleteBB(BB);
     }
+    if (!Deleted)
+      return false;
+  }
   return true;
 }
 
 void llvm::combineMetadata(Instruction *K, const Instruction *J,
                            ArrayRef<unsigned> KnownIDs) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   K->dropUnknownNonDebugMetadata(KnownIDs);
   K->getAllMetadataOtherThanDebugLoc(Metadata);

unittests/Transforms/Utils/Local.cpp

TEST(Local, RemoveUnreachableBlocks) {
   runWithDomTree(*M, "br_constant", runEager);
   runWithDomTree(*M, "br_loop", runEager);
 
   // Test removeUnreachableBlocks under Lazy UpdateStrategy.
   runWithDomTree(*M, "br_simple", runLazy);
   runWithDomTree(*M, "br_self_loop", runLazy);
   runWithDomTree(*M, "br_constant", runLazy);
   runWithDomTree(*M, "br_loop", runLazy);
+
+  M = parseIR(C,
+              R"(
+      define void @f() {
+      entry:
+        br label %entry
+      bb0:
+        ret void
+      }
+        )");
+
+  auto checkRUBlocksRetVal = [&](Function &F, DominatorTree *DT) {
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+    EXPECT_TRUE(removeUnreachableBlocks(F, nullptr, &DTU));
+    EXPECT_FALSE(removeUnreachableBlocks(F, nullptr, &DTU));
+    EXPECT_TRUE(DTU.getDomTree().verify());
+  };
+
+  runWithDomTree(*M, "f", checkRUBlocksRetVal);
 }
 No newline at end of file