[Utils] Extract EliminateUnreachableBlocks (NFC)

[modocache]

Summary

Extract the functionality of eliminating unreachable basic blocks
within a function, previously encapsulated within the
-unreachableblockelim pass, and make it available as a function within
BlockUtils.h. No functional change intended other than making the logic
reusable.

Exposing this logic makes it easier to implement
https://reviews.llvm.org/D59068, which fixes coroutines bug
https://bugs.llvm.org/show_bug.cgi?id=40979.

[modocache]

Friendly ping! I thought this might be easier to review if I split it up from https://reviews.llvm.org/D59068, which fixes a bug in coroutines and has already been accepted. This diff is an NFC but is necessary to land the bug fix.

[davide]

lib/Transforms/Utils/BasicBlockUtils.cpp

113–114 ↗

(On Diff #189639)

Do you need KeepOneInputPHIs ?

[modocache]

Oops! Thanks for pointing that out @davide -- I had meant to pass them through to the DeleteDeadBlocks but forgot. Should be good now!

[davide]

LGTM.

llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h

 /// duplicating blocks. If there are loops among this set of blocks, all
 /// relevant loop info updates should be done before this function is called.
 /// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks
 /// being deleted will be preserved.
 void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs,
                       DomTreeUpdater *DTU = nullptr,
                       bool KeepOneInputPHIs = false);
 
+/// Delete all basic blocks from \p F that are not reachable from its entry
+/// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of
+/// blocks being deleted will be preserved.
+bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr,
+                                bool KeepOneInputPHIs = false);
+
 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
 /// in it, fold them away. This handles the case when all entries to the PHI
 /// nodes in a block are guaranteed equal, such as when the block has exactly
 /// one predecessor.
 void FoldSingleEntryPHINodes(BasicBlock *BB,
                              MemoryDependenceResults *MemDep = nullptr);
 
 /// Examine each PHI in the given block and delete it if it is dead. Also

llvm/trunk/lib/CodeGen/UnreachableBlockElim.cpp

 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 using namespace llvm;
 
-static bool eliminateUnreachableBlock(Function &F) {
-  df_iterator_default_set<BasicBlock*> Reachable;
-
-  // Mark all reachable blocks.
-  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
-    (void)BB/* Mark all reachable blocks */;
-
-  // Collect all dead blocks.
-  std::vector<BasicBlock*> DeadBlocks;
-  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-    if (!Reachable.count(&*I)) {
-      BasicBlock *BB = &*I;
-      DeadBlocks.push_back(BB);
-    }
-
-  // Delete the dead blocks.
-  DeleteDeadBlocks(DeadBlocks);
-
-  return !DeadBlocks.empty();
-}
-
 namespace {
 class UnreachableBlockElimLegacyPass : public FunctionPass {
   bool runOnFunction(Function &F) override {
-    return eliminateUnreachableBlock(F);
+    return llvm::EliminateUnreachableBlocks(F);
   }
 
 public:
   static char ID; // Pass identification, replacement for typeid
   UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
     initializeUnreachableBlockElimLegacyPassPass(
         *PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<DominatorTreeWrapperPass>();
   }
 };
 }
 char UnreachableBlockElimLegacyPass::ID = 0;
 INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
                 "Remove unreachable blocks from the CFG", false, false)
 
 FunctionPass *llvm::createUnreachableBlockEliminationPass() {
   return new UnreachableBlockElimLegacyPass();
 }
 
 PreservedAnalyses UnreachableBlockElimPass::run(Function &F,
                                                 FunctionAnalysisManager &AM) {
-  bool Changed = eliminateUnreachableBlock(F);
+  bool Changed = llvm::EliminateUnreachableBlocks(F);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }
 
 namespace {

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

#endif
 
   for (BasicBlock *BB : BBs)
     if (DTU)
       DTU->deleteBB(BB);
     else
       BB->eraseFromParent();
 }
 
+bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
+                                      bool KeepOneInputPHIs) {
+  df_iterator_default_set<BasicBlock*> Reachable;
+
+  // Mark all reachable blocks.
+  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
+    (void)BB/* Mark all reachable blocks */;
+
+  // Collect all dead blocks.
+  std::vector<BasicBlock*> DeadBlocks;
+  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+    if (!Reachable.count(&*I)) {
+      BasicBlock *BB = &*I;
+      DeadBlocks.push_back(BB);
+    }
+
+  // Delete the dead blocks.
+  DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
+
+  return !DeadBlocks.empty();
+}
+
 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
                                    MemoryDependenceResults *MemDep) {
   if (!isa<PHINode>(BB->begin())) return;
 
   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
     if (PN->getIncomingValue(0) != PN)
       PN->replaceAllUsesWith(PN->getIncomingValue(0));
     else

llvm/trunk/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp

 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
   SMDiagnostic Err;
   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
   if (!Mod)
     Err.print("BasicBlockUtilsTests", errs());
   return Mod;
 }
 
+TEST(BasicBlockUtils, EliminateUnreachableBlocks) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(
+    C,
+    "define i32 @has_unreachable(i1 %cond) {\n"
+    "entry:\n"
+    "  br i1 %cond, label %bb0, label %bb1\n"
+    "bb0:\n"
+    "  br label %bb1\n"
+    "bb1:\n"
+    "  %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
+    "  ret i32 %phi\n"
+    "bb2:\n"
+    "  ret i32 42\n"
+    "}\n"
+    "\n"
+    );
+
+  auto *F = M->getFunction("has_unreachable");
+  DominatorTree DT(*F);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+
+  EXPECT_EQ(F->size(), (size_t)4);
+  bool Result = EliminateUnreachableBlocks(*F, &DTU);
+  EXPECT_TRUE(Result);
+  EXPECT_EQ(F->size(), (size_t)3);
+  EXPECT_TRUE(DT.verify());
+}
+
+TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(
+    C,
+    "define i32 @no_unreachable(i1 %cond) {\n"
+    "entry:\n"
+    "  br i1 %cond, label %bb0, label %bb1\n"
+    "bb0:\n"
+    "  br label %bb1\n"
+    "bb1:\n"
+    "  %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
+    "  ret i32 %phi\n"
+    "}\n"
+    "\n"
+    );
+
+  auto *F = M->getFunction("no_unreachable");
+  DominatorTree DT(*F);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+
+  EXPECT_EQ(F->size(), (size_t)3);
+  bool Result = EliminateUnreachableBlocks(*F, &DTU);
+  EXPECT_FALSE(Result);
+  EXPECT_EQ(F->size(), (size_t)3);
+  EXPECT_TRUE(DT.verify());
+}
+
 TEST(BasicBlockUtils, SplitBlockPredecessors) {
   LLVMContext C;
 
   std::unique_ptr<Module> M = parseIR(
     C,
     "define i32 @basic_func(i1 %cond) {\n"
     "entry:\n"
     "  br i1 %cond, label %bb0, label %bb1\n"