WIP! [CFG] Create a new removeUnreachable utility that updates the dom in place

[davide]

Summary

This implements the algorithm suggested in https://reviews.llvm.org/D35028#800177 with a slight variation/implementation detail. We could have BBs which don't have corresponding nodes in the dominator, so we need to handle that case as well. We also need an additional worklist for the dead block to avoid iterator invalidation issues (or at least, this was the easiest way I could think how to solve this problem).
This is WIP for two reasons:

1. I want the utility to have a better name for the utility [but I need to think about it, suggestions welcome]
2. I want to test it a little more. It passes the testsuite & bootstrap, but I'll try on something else I have available internally.

[• dberlin]

lib/Transforms/Utils/Local.cpp

1711

Note that if the dom tree is up to date, it would suffice to do:

for (auto *BB : nodes(DT))

Live.insert(BB->getBlock())

or whatever

But IIRC, in your case, the dominator tree is *not* up to date, right?

[davide]

lib/Transforms/Utils/Local.cpp

1711

I guess we could introduce this invariant, if the caller passes a Dom that's always up-to-date? (otherwise, realistically, there's little point in trying to update an already stale dominator).

[kuhar]

lib/Transforms/Utils/Local.cpp

1716

Isn't the size known to be F.size() - Live.size() at this point? Worklist could start with this capacity.

[efriedma]

lib/Transforms/Utils/Local.cpp

1727

I'm pretty sure N is always null here if the domtree is up-to-date.

1730

The dropAllReferences call is redundant; the destructor for BasicBlock calls it for you.

An unreachable block can have reachable successors; you need to use removePredecessor to fix them up properly.

[davide]

Cleaning up my queue.

include/llvm/Transforms/Utils/Local.h

 /// Returns true if any basic block was removed.
 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr);
 
+bool removeUnreachable(Function &F, DominatorTree &DT,
+                       LazyValueInfo *LVI = nullptr);
+
 /// Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed

lib/Transforms/IPO/GlobalOpt.cpp

     // So, remove unreachable blocks from the function, because a) there's
     // no point in analyzing them and b) GlobalOpt should otherwise grow
     // some more complicated logic to break these cycles.
-    // Removing unreachable blocks might invalidate the dominator so we
-    // recalculate it.
     if (!F->isDeclaration()) {
-      if (removeUnreachableBlocks(*F)) {
-        auto &DT = LookupDomTree(*F);
-        DT.recalculate(*F);
+      auto &DT = LookupDomTree(*F);
+      if (removeUnreachable(*F, DT))
         Changed = true;
-      }
     }
 
     Changed |= processGlobal(*F, TLI, LookupDomTree);

lib/Transforms/Utils/Local.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"

   return true;
 }
 
+bool llvm::removeUnreachable(Function &F, DominatorTree &DT,
+                             LazyValueInfo *LVI) {
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  SmallPtrSet<BasicBlock *, 8> Live;
+  SmallPtrSet<BasicBlock *, 8> Processed;
+
+  for (BasicBlock *BB : RPOT)
+    Live.insert(BB);
+
+  if (Live.size() == F.size())
+    return false;
+
+  SmallVector<BasicBlock *, 8> Worklist;
+  for (BasicBlock &BB : F) {
+    if (!Live.count(&BB))
+      Worklist.push_back(&BB);
+  }
+
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.pop_back_val();
+    if (Processed.count(BB))
+      continue;
+    auto *N = DT.getNode(BB);
+    if (!N) {
+      if (LVI)
+        LVI->eraseBlock(BB);
+      BB->dropAllReferences();
+      BB->eraseFromParent();
+      continue;
+    }
+    for (auto *DTN : post_order(N)) {
+      BasicBlock *DTBlock = DTN->getBlock();
+      Processed.insert(DTBlock);
+      for (BasicBlock *Succ : successors(DTBlock))
+        Succ->removePredecessor(DTBlock);
+      if (LVI)
+        LVI->eraseBlock(DTBlock);
+      DT.eraseNode(DTBlock);
+      DTBlock->dropAllReferences();
+      DTBlock->eraseFromParent();
+    }
+  }
+  return true;
+}
+
 void llvm::combineMetadata(Instruction *K, const Instruction *J,
                            ArrayRef<unsigned> KnownIDs) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;

test/Other/new-pm-lto-defaults.ll

 ; CHECK-O-NEXT: Running pass: GlobalSplitPass
 ; CHECK-O-NEXT: Running pass: WholeProgramDevirtPass
 ; CHECK-O2-NEXT: Running pass: GlobalOptPass
-; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O2-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O2-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O2-NEXT: Running pass: ConstantMergePass
 ; CHECK-O2-NEXT: Running pass: DeadArgumentEliminationPass