[BasicBlock] add new function removeEdge()

[brzycki]

Summary

First let me comment by saying I'm not sure if the community desires to go in this direction. The primary reason for uploading this patch was twofold:

1. To start a discussion about how we work with edges between blocks in an IR vs CFG manner.
2. To archive the patch should others find the idea useful in the future.

This patch adds a new function removeEdge() as a BasicBlock primitive. It does exactly what the name implies: removes an outgoing edge from BB1 into BB2. The routine asserts if no such edge exists.

This routine started as a reaction to removePredecessor(); a call that only adjust PHIs in the successor BB. Calls to removePredecessor() quietly do nothing in cases such as the following:

BB1:

br BB2

BB2:

br BB3

BB2->removePredecessor(BB1)

This is a bit surprising until one reads the documentation/source for removePredecessor().

The removeEdge() routine alters the terminator instruction of BB1. Should we call BB1->removeEdge(BB2) the resulting IR would now look like

BB1:

unreachable

BB2:

br BB3

Dominance is preserved if a DT handle is passed in: BB1->removeEdge(BB2, DT).

This new interface gives the caller the option to think more about the CFG than the underlying IR details. This has a few complications related to it:

1. The successors of BB1 will be altered by the call, making looping over successors different than of call sites using removePredecessor()
2. removeEdge() does not alter uses.

Even with these drawbacks I think this alternative interface has merit: in too many locations throughout the middle end do we see special-cased code that deals with the details of the IRs many terminator instruction types. At the very least I hope this code spurs a fruitful discussion.

[kuhar]

This actually seems a bit orthogonal to what we wanted to do with @dberlin. The idea was to see if it is possible to always preserve dominators, and to do it completely automatically. With this high-level goal in mind, I tried to hack removePredecessor (and others) to grab DominatorTree (if available) and update it internally. That would probably also deprecate the batch updater, as every update DominatorTree update would happen in lockstep with CFG update calls. The problem was however that the existing BasicBlock API doesn't really care about CFG edges and it wasn't really possible to place the DT update calls anywhere.

It looks like this patch could be the one of the first steps towards completely automatic DominatorTree updates. Another interesting thing would be to see if it would be possible to do something equivalent for addEdge -- with these 2 pieces of API in place, it would be much easier to fuzz and benchmarks the incremental DominatorTree updater.

llvm/lib/IR/BasicBlock.cpp

324

s/removedDest/RemovedDest

348

s/removedCase/RemovedCase

351

Consider using auto here

387

s/removedHandler/RemovedHandler

390

Consider using auto here as well

[brzycki]

Fixed formatting comments recommended by @kuhar .

Fixed a corner-case bug when Invoke instructions have the same Normal and Unwind destination and DT is updated.

[brzycki]

In D37575#864676, @kuhar wrote:

This actually seems a bit orthogonal to what we wanted to do with @dberlin. The idea was to see if it is possible to always preserve dominators, and to do it completely automatically. With this high-level goal in mind, I tried to hack removePredecessor (and others) to grab DominatorTree (if available) and update it internally. That would probably also deprecate the batch updater, as every update DominatorTree update would happen in lockstep with CFG update calls. The problem was however that the existing BasicBlock API doesn't really care about CFG edges and it wasn't really possible to place the DT update calls anywhere.

@sebpop and I tried the exact same thing early on in the D37528 JumpThreading work. We ran into the exact same problem: too many places deal with the minutiae of the IR and we found several CFG cases where dominance couldn't be easily updated. This removeEdge() patch actually came out of that work as yet another attempt to fix the problem. Unfortunately the call sites for removePredecessor() almost always use for (auto Successor: Successors(BB))... and needed more fixup to work with removeEdge().

It looks like this patch could be the one of the first steps towards completely automatic DominatorTree updates. Another interesting thing would be to see if it would be possible to do something equivalent for addEdge -- with these 2 pieces of API in place, it would be much easier to fuzz and benchmarks the incremental DominatorTree updater.

I'd be happy to help move in this direction: it would greatly simplify middle-end work for everyone if we could think about BB chains in the context of CFG nodes and edges instead of constantly programming terminator instruction edge-case logic.

llvm/lib/IR/BasicBlock.cpp

302

Fixed in rev 2, needed to check NormalDestBB != UnwindDestBB in the corner-case where Normal and Unwind are the same basic block.

[brzycki]

ping.

[kuhar]

I'm fine with the patch, I think it goes into right direction with CFG-level IR manipulation.
Please wait for someone else to give you a green light on this. Maybe it would be worth to mention this as an RFC on llvm-dev?

[brzycki]

In D37575#880401, @kuhar wrote:

I'm fine with the patch, I think it goes into right direction with CFG-level IR manipulation.
Please wait for someone else to give you a green light on this. Maybe it would be worth to mention this as an RFC on llvm-dev?

Thanks for the review and you bring up a good point about RFC on llvm-dev. I'll make a post tomorrow morning and see where the conversation goes.

[• dberlin]

(repeating comments i forgot to add to review)
This definitely needs an RFC.

I'll note your approach is badly O(N) in some cases.
You could try using the uses instead (they know what operand number and their uses).
I suspect that's hard to pass down everywhere in each pass.

In general If we are going to go this route, either we should: have a real CFG structure that isn't going to be O(N) to remove an edge.
or incrementally, cache data in basic blocks (successor, predecessor lists and uses) that gets invalidated, so you can find the removal points in constant time.

The latter is likely to require a lot of verification to not generate hard to track down bugs in the compiler.

[brzycki]

In D37575#882225, @dberlin wrote:

(repeating comments i forgot to add to review)
This definitely needs an RFC.

Thanks for the feedback Daniel. I sent the RFC email to llvm-dev this morning.

I'll note your approach is badly O(N) in some cases.
You could try using the uses instead (they know what operand number and their uses).
I suspect that's hard to pass down everywhere in each pass.

I agree several cases are O(N) (switch, catchswitch, indirect branch). I was not aware uses contained the operand number and I do agree that would save time (and probably simplify some of the logic). One of the reasons I wrote the code this way was investigating actual pass code that changed terminator instructions. A good deal of the original idea came from the huge if()..else blocks inside Local.cpp routines. I also haven't examined the code enough to determine if requiring uses would act as a barrier to use.

In general If we are going to go this route, either we should: have a real CFG structure that isn't going to be O(N) to remove an edge.

I definitely agree that a real CFG structure is needed. Thinking about a higher-level change to the shape of the IR and then switching to the intricacies of the IR to implement it can be quite frustrating.

or incrementally, cache data in basic blocks (successor, predecessor lists and uses) that gets invalidated, so you can find the removal points in constant time.
The latter is likely to require a lot of verification to not generate hard to track down bugs in the compiler.

It would be nice to simply query a method of a BB without having to to write for (Successor: Successors())....Validating the cache would be non-trivial and I would consider it a failure if the user had to worry about the internal state (and call routines to verify/fix it at the call site).

My hope is we can start moving in a meaningful direction to reduce this problem without getting overwhelmed with the changes needed to be added. I greatly prefer incremental changes to an existing design as a method to evolve the code.

[brzycki]

This method is too expensive as it is designed today.

llvm/include/llvm/IR/BasicBlock.h

 #include "llvm/Support/Compiler.h"
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 
 namespace llvm {
 
 class CallInst;
+class DominatorTree;
 class Function;
 class LandingPadInst;
 class LLVMContext;
 class Module;
 class PHINode;
 class TerminatorInst;
 class ValueSymbolTable;
 
public:
   ///
   /// This allows one to 'delete' a whole class at a time, even though there may
   /// be circular references... first all references are dropped, and all use
   /// counts go to zero.  Then everything is delete'd for real.  Note that no
   /// operations are valid on an object that has "dropped all references",
   /// except operator delete.
   void dropAllReferences();
 
+  /// \brief Remove the edge between this and To. It does not alter the contents
+  /// of To, only the terminating instruction of this. To must be a successor of
+  /// this or an assert will be raised.
+  ///
+  /// If DT is valid the routine will preserve dominance.
+  ///
+  /// Invoke terminator instructions will raise an assert unless removeInvoke is
+  /// set to true. Invoke instructions cannot be reduced from two successors to
+  /// one: the entire instruction (and two edges) must be removed at the same
+  /// time.
+  ///
+  /// Note: it is not safe to assume one call to removeEdge decrements
+  /// this->getTerminator()->getNumSuccessors() by one. Several terminator
+  /// instructions permit branches to the same basic block and count each jump
+  /// as a unique successor. The removeEdge routine removes *all* instances of
+  /// To from the terminating instruction in this.
+  ///
+  /// Note: the routine may change the terminator instruction type and may also
+  /// create a new basic block. These changes are dependant upon on the type of
+  /// the terminator instruction and the requested edge to remove.
+  void removeEdge(BasicBlock *To, DominatorTree *DT = nullptr,
+                  bool removeInvoke = false);
+
   /// \brief Notify the BasicBlock that the predecessor \p Pred is no longer
   /// able to reach it.
   ///
   /// This is actually not used to update the Predecessor list, but is actually
   /// used to update the PHI nodes that reside in the block.  Note that this
   /// should be called while the predecessor still refers to this block.
   void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs = false);
 

llvm/lib/IR/BasicBlock.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/BasicBlock.h"
 #include "SymbolTableListTraitsImpl.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Type.h"
 #include <algorithm>
 
 using namespace llvm;
 
const BasicBlock *BasicBlock::getUniqueSuccessor() const {
   }
   return SuccBB;
 }
 
 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
   return make_range<phi_iterator>(dyn_cast<PHINode>(&front()), nullptr);
 }
 
+void BasicBlock::removeEdge(BasicBlock *To, DominatorTree *DT,
+                            bool removeInvoke) {
+  // Terminator instruction types: BranchInst(1/2),
+  // SwitchInst(getNumOperands()/2), IndirectBrInst(getNumOperands()-1),
+  // InvokeInst(2), CleanupReturnInst(1/0), CatchReturnInst(1),
+  // CatchSwitchInst(getNumOperands()-1)
+  //
+  // ResumeInst(0), UnreachableInst(0) are not checked because they never
+  // have successors.
+  assert(To && "To cannot be nullptr.");
+  assert(find(succ_begin(this), succ_end(this), To) != succ_end(this) &&
+         "There exists no edge between this and To.");
+
+  SmallVector<DominatorTree::UpdateType, 2> Updates;
+  TerminatorInst *TI = getTerminator();
+
+  if (CleanupReturnInst *CI = dyn_cast<CleanupReturnInst>(TI)) {
+    // To is the only successor.
+    new UnreachableInst(getContext(), this);
+    CI->eraseFromParent();
+  } else if (CatchReturnInst *CI = dyn_cast<CatchReturnInst>(TI)) {
+    // To is the only successor.
+    new UnreachableInst(getContext(), this);
+    CI->eraseFromParent();
+  } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
+    assert(removeInvoke && "Invokes must have two edges removed at once.");
+    if (DT) {
+      BasicBlock *NormalDestBB = II->getNormalDest();
+      BasicBlock *UnwindDestBB = II->getUnwindDest();
+      if (this != NormalDestBB)
+        Updates.push_back({DominatorTree::Delete, this, NormalDestBB});
+      if (this != UnwindDestBB && NormalDestBB != UnwindDestBB)
+        Updates.push_back({DominatorTree::Delete, this, UnwindDestBB});
+    }
+    new UnreachableInst(getContext(), this);
+    II->eraseFromParent();
+  } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+    if (BI->isConditional()) {
+      BasicBlock *L = BI->getSuccessor(0);
+      BasicBlock *R = BI->getSuccessor(1);
+      if (To == L && To == R) {
+        new UnreachableInst(getContext(), this);
+      } else if (To == L) {
+        BranchInst::Create(R, BI);
+      } else {
+        BranchInst::Create(L, BI);
+      }
+    } else {
+      new UnreachableInst(getContext(), this);
+    }
+    BI->eraseFromParent();
+  } else if (IndirectBrInst *II = dyn_cast<IndirectBrInst>(TI)) {
+    // There are 1+ instances of To in the list of destinations.
+    bool RemovedDest;
+    do {
+      unsigned NumDests = II->getNumDestinations();
+      if (NumDests == 1) {
+        if (II->getDestination(0) == To) {
+          // The only remaining destination is To.
+          new UnreachableInst(getContext(), this);
+          II->eraseFromParent();
+        }
+        break;
+      } else {
+        RemovedDest = false;
+        for (unsigned I = 0; I < NumDests; ++I)
+          if (II->getDestination(I) == To) {
+            II->removeDestination(I);
+            RemovedDest = true;
+            break;
+          }
+      }
+    } while (RemovedDest);
+  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+    // To is a successor of one or more case statements (including the
+    // default case). The first task is to remove all non-default case
+    // statements that branch to To.
+    bool RemovedCase;
+    do {
+      RemovedCase = false;
+      for (auto I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
+        if (I == SI->case_default())
+          continue;
+        if (I->getCaseSuccessor() == To) {
+          SI->removeCase(I);
+          RemovedCase = true;
+          break;
+        }
+      }
+    } while (RemovedCase);
+    // Now check the default case.
+    if (SI->getSuccessor(0) == To) {
+      if (SI->getNumSuccessors() == 1) {
+        // The only remaining successor is the default case.
+        new UnreachableInst(getContext(), this);
+        SI->eraseFromParent();
+      } else {
+        // The SwitchInst has non-default cases remaining. Create a new
+        // BasicBlock, set it as the new default destination, and denote
+        // the new BasicBlock as unreachable.
+        BasicBlock *UnreachBB = BasicBlock::Create(
+            getContext(), Twine(getName()) + ".unreachable_switch_default",
+            getParent());
+        SI->setDefaultDest(UnreachBB);
+        new UnreachableInst(UnreachBB->getContext(), UnreachBB);
+        if (DT)
+          Updates.push_back({DominatorTree::Insert, this, UnreachBB});
+      }
+    }
+    if (DT && this != To)
+      Updates.push_back({DominatorTree::Delete, this, To});
+  } else if (CatchSwitchInst *CI = dyn_cast<CatchSwitchInst>(TI)) {
+    // To is a successor of one or more handlers and may also be the unwind
+    // destination. The first task is to remove all the handlers that branch
+    // to To.
+    bool RemovedHandler;
+    do {
+      RemovedHandler = false;
+      for (auto I = CI->handler_begin(), E = CI->handler_end(); I != E; ++I)
+        if (*I == To) {
+          CI->removeHandler(I);
+          RemovedHandler = true;
+          break;
+        }
+    } while (RemovedHandler);
+    // Now check the unwind destination.
+    if (CI->getUnwindDest() == To) {
+      if (CI->getNumHandlers() == 0) {
+        // The only remaining successor is the unwind destination.
+        new UnreachableInst(getContext(), this);
+        CI->eraseFromParent();
+      } else {
+        // The CatchSwitchInst has one or more handlers. Create a new
+        // BasicBlock, set it as the new unwind destination, and denote
+        // the new BasicBlock as unreachable.
+        BasicBlock *UnreachBB = BasicBlock::Create(
+            getContext(), Twine(getName()) + ".unreachable_unwind_default",
+            getParent());
+        CI->setUnwindDest(UnreachBB);
+        new UnreachableInst(UnreachBB->getContext(), UnreachBB);
+        if (DT)
+          Updates.push_back({DominatorTree::Insert, this, UnreachBB});
+      }
+    }
+    if (DT && this != To)
+      Updates.push_back({DominatorTree::Delete, this, To});
+  } else {
+    llvm_unreachable("Unexpected TerminatorInst");
+  }
+  // Remove our edge from the dominator tree. If we used Updates above just
+  // apply them. Otherwise remove the edge between this and To provided it's not
+  // a loop back to itself.
+  if (DT) {
+    if (!Updates.empty())
+      DT->applyUpdates(Updates);
+    else if (this != To)
+      DT->deleteEdge(this, To);
+  }
+}
+
 /// This method is used to notify a BasicBlock that the
 /// specified Predecessor of the block is no longer able to reach it.  This is
 /// actually not used to update the Predecessor list, but is actually used to
 /// update the PHI nodes that reside in the block.  Note that this should be
 /// called while the predecessor still refers to this block.
 ///
 void BasicBlock::removePredecessor(BasicBlock *Pred,
                                    bool DontDeleteUselessPHIs) {

llvm/unittests/IR/BasicBlockRemoveEdgeTest.cpp

+//===- llvm/unittest/IR/BasicBlockRemoveEdgeTest.cpp - BBremoveEdge tests -===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/NoFolder.h"
+#include "llvm/IR/Verifier.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+class BBremoveEdgeTest : public testing::Test {
+protected:
+  void SetUp() override {
+    M.reset(new Module("MyModule", Ctx));
+    FunctionType *FTy = FunctionType::get(Type::getVoidTy(Ctx),
+                                          /*isVarArg=*/false);
+    F = Function::Create(FTy, Function::ExternalLinkage, "MyFunc", M.get());
+    for (int i = 0; i < 5; ++i) {
+      BasicBlock *B;
+      if (i == 0) {
+        B = BasicBlock::Create(Ctx, "entry", F);
+      } else {
+        B = BasicBlock::Create(Ctx, "bb" + std::to_string(i), F);
+        IRBuilder<> Builder(B);
+        Builder.CreateRetVoid();
+      }
+      BB.push_back(B);
+    }
+    GV = new GlobalVariable(*M, Type::getFloatTy(Ctx), true,
+                            GlobalValue::ExternalLinkage, nullptr);
+    DT = new DominatorTree(*F);
+    ParentPad = llvm::ConstantTokenNone::get(Ctx);
+  }
+
+  void TearDown() override {
+    BB.clear();
+    F = nullptr;
+    GV = nullptr;
+    DT = nullptr;
+    ParentPad = nullptr;
+    M.reset();
+  }
+
+  std::unique_ptr<Module> M;
+  std::vector<BasicBlock *> BB;
+  LLVMContext Ctx;
+  Function *F;
+  DominatorTree *DT;
+  GlobalVariable *GV;
+  ConstantTokenNone *ParentPad;
+};
+
+TEST_F(BBremoveEdgeTest, CleanupReturn) {
+  IRBuilder<> Builder(BB[0]);
+  CleanupPadInst *CleanPI = Builder.CreateCleanupPad(ParentPad);
+  Builder.CreateCleanupRet(CleanPI, BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchReturn) {
+  IRBuilder<> Builder(BB[0]);
+  CatchPadInst *CatchPI = Builder.CreateCatchPad(ParentPad, nullptr);
+  Builder.CreateCatchRet(CatchPI, BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Invoke) {
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateInvoke(F, BB[1], BB[2]);
+  DT->recalculate(*F); // cannot insert two edges at once with insertEdge()
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[1], DT, /* removeInvoke */ true);
+  EXPECT_TRUE(DT->verify());
+  // Both invoke successors are removed with the same call due to the atomicity
+  // of the instruction. We no longer have any successors after a single
+  // removeEdge() call.
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, ConditionalBranch1) {
+  // Both conditions connect to the same successor.
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateCondBr(
+      ConstantInt::get(IntegerType::get(M->getContext(), 1), 0), BB[1], BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, ConditionalBranch2) {
+  // Remove the first successor then the second.
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateCondBr(
+      ConstantInt::get(IntegerType::get(M->getContext(), 1), 0), BB[1], BB[2]);
+  DT->recalculate(*F); // cannot insert two edges at once with insertEdge()
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BranchInst *BI = dyn_cast<BranchInst>(BB[0]->getTerminator());
+  EXPECT_NE(BI, nullptr);
+  if (BI)
+    EXPECT_FALSE(BI->isConditional());
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, ConditionalBranch3) {
+  // Remove the second successor then the first.
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateCondBr(
+      ConstantInt::get(IntegerType::get(M->getContext(), 1), 0), BB[1], BB[2]);
+  DT->recalculate(*F); // cannot insert two edges at once with insertEdge()
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BranchInst *BI = dyn_cast<BranchInst>(BB[0]->getTerminator());
+  EXPECT_NE(BI, nullptr);
+  if (BI)
+    EXPECT_FALSE(BI->isConditional());
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, UnconditionalBranch) {
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateBr(BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, IndirectBranch1) {
+  // There is exactly one branch to remove.
+  IRBuilder<> Builder(BB[0]);
+  IndirectBrInst *IBI = Builder.CreateIndirectBr(F, 1);
+  IBI->addDestination(BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, IndirectBranch2) {
+  // Remove only one successor (single instance).
+  IRBuilder<> Builder(BB[0]);
+  IndirectBrInst *IBI = Builder.CreateIndirectBr(F, 3);
+  IBI->addDestination(BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  IBI->addDestination(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  IBI->addDestination(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  IBI = dyn_cast<IndirectBrInst>(BB[0]->getTerminator());
+  EXPECT_NE(IBI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, IndirectBranch3) {
+  // Remove only one successor (multiple instances).
+  IRBuilder<> Builder(BB[0]);
+  IndirectBrInst *IBI = Builder.CreateIndirectBr(F, 5);
+  IBI->addDestination(BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  IBI->addDestination(BB[2]);
+  IBI->addDestination(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  IBI->addDestination(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  IBI->addDestination(BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 5u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  IBI = dyn_cast<IndirectBrInst>(BB[0]->getTerminator());
+  EXPECT_NE(IBI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, IndirectBranch4) {
+  // Remove all successors.
+  IRBuilder<> Builder(BB[0]);
+  IndirectBrInst *IBI = Builder.CreateIndirectBr(F, 5);
+  IBI->addDestination(BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  IBI->addDestination(BB[2]);
+  IBI->addDestination(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  IBI->addDestination(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  IBI->addDestination(BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 5u);
+  BB[0]->removeEdge(BB[3], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch1) {
+  // Switch only has a default case.
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch2) {
+  // Remove default case with non-default cases remaining.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  // We still have 3 successors: removeEdge() added a replacement block as the
+  // default destination to preserve the integrity of the instruction.
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch3) {
+  // Remove one non-default case, no non-defaults remaining.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch4) {
+  // Remove multiple non-default cases, no non-defaults remaining.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch5) {
+  // Remove one non-default case with non-defaults remaining.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+
+TEST_F(BBremoveEdgeTest, Switch6) {
+  // Remove multiple non-default cases with non-defaults remaining.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 4), BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 5), BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch7) {
+  // Remove default case and one non-default case (non-default cases remain).
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  // We have 3 successors: removeEdge() added a replacement block as the
+  // default destination to preserve the integrity of the instruction. We also
+  // removed a single non-default case (4 - (1 + 1) + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch8) {
+  // Remove default case and multiple non-default cases (non-default cases
+  // remain).
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 4), BB[3]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 5), BB[1]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  // We have 3 successors: removeEdge() added a replacement block as the
+  // default destination to preserve the integrity of the instruction. We also
+  // removed 3 non-default cases (6 - (1 + 3) + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch9) {
+  // Remove all cases, don't delete default case last.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 4), BB[3]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 5), BB[1]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  // We have 3 successors: removeEdge() added a replacement block as the
+  // default destination to preserve the integrity of the instruction. We also
+  // removed 3 non-default cases (6 - (1 + 3) + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[3], DT);
+  EXPECT_TRUE(DT->verify());
+  // The previously-inserted default basic block is the only remaining
+  // successor.
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  SI = dyn_cast<SwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(SI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, Switch10) {
+  // Remove all cases and delete default case last.
+  IRBuilder<> Builder(BB[0]);
+  SwitchInst *SI = Builder.CreateSwitch(
+      ConstantInt::get(IntegerType::get(M->getContext(), 8), 0), BB[1]);
+  DT->insertEdge(BB[0], BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 1), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 2), BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 3), BB[1]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 4), BB[3]);
+  SI->addCase(ConstantInt::get(IntegerType::get(M->getContext(), 8), 5), BB[1]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[3], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 5u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  // All remaining cases (default and non-default) were to BB[1]. We can safely
+  // remove the entire instruction without replacing the default case to a new
+  // BasicBlock.
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch1) {
+  // CatchSwitch only has unwind case.
+  IRBuilder<> Builder(BB[0]);
+  Builder.CreateCatchSwitch(ParentPad, BB[1], 0);
+  DT->insertEdge(BB[0], BB[1]);
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch2) {
+  // Remove the unwind case with handlers remaining.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 2);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  // We have 3 successors: removeEdge() added a replacement block as the
+  // Unwind destination to preserve the integrity of the instruction
+  // (3 - 1 + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch3) {
+  // Remove one handler, no handlers remaining.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 1);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch4) {
+  // Remove multiple handlers, no handlers remaining.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 3);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[2]);
+  CI->addHandler(BB[2]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch5) {
+  // Remove one handler with handlers remaining.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 2);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch6) {
+  // Remove multiple handlers with handlers remaining.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 4);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  CI->addHandler(BB[2]);
+  CI->addHandler(BB[4]);
+  DT->insertEdge(BB[0], BB[4]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 5u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch7) {
+  // Remove unwind and one handler (some handlers remain).
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 3);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[1]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  // We have 3 successors: removeEdge() added a replacement block as the
+  // Unwind destination to preserve the integrity of the instruction. We also
+  // removed one handler (4 - (1 + 1) + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch8) {
+  // Remove multiple handlers and unwind (some handlers remain).
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 5);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  CI->addHandler(BB[1]);
+  CI->addHandler(BB[4]);
+  DT->insertEdge(BB[0], BB[4]);
+  CI->addHandler(BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  // We have 4 successors: removeEdge() added a replacement block as the
+  // Unwind destination to preserve the integrity of the instruction. We also
+  // removed two handlers (6 - (1 + 2) + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch9) {
+  // Remove all successors, don't delete unwind last.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 5);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  CI->addHandler(BB[1]);
+  CI->addHandler(BB[4]);
+  DT->insertEdge(BB[0], BB[4]);
+  CI->addHandler(BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  // We have 4 successors: removeEdge() added a replacement block as the
+  // Unwind destination to preserve the integrity of the instruction. We also
+  // removed two handlers (6 - (1 + 2) + 1).
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[3], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 2u);
+  BB[0]->removeEdge(BB[4], DT);
+  EXPECT_TRUE(DT->verify());
+  // The previously-inserted unwind basic block is the only remaining
+  // successor.
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 1u);
+  CI = dyn_cast<CatchSwitchInst>(BB[0]->getTerminator());
+  EXPECT_NE(CI, nullptr);
+}
+
+TEST_F(BBremoveEdgeTest, CatchSwitch10) {
+  // Remove all successors and delete unwind last.
+  IRBuilder<> Builder(BB[0]);
+  CatchSwitchInst *CI = Builder.CreateCatchSwitch(ParentPad, BB[1], 5);
+  DT->insertEdge(BB[0], BB[1]);
+  CI->addHandler(BB[2]);
+  DT->insertEdge(BB[0], BB[2]);
+  CI->addHandler(BB[3]);
+  DT->insertEdge(BB[0], BB[3]);
+  CI->addHandler(BB[1]);
+  CI->addHandler(BB[4]);
+  DT->insertEdge(BB[0], BB[4]);
+  CI->addHandler(BB[1]);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[4]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 6u);
+  BB[0]->removeEdge(BB[4], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[3]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 5u);
+  BB[0]->removeEdge(BB[3], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[2]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 4u);
+  BB[0]->removeEdge(BB[2], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_TRUE(DT->properlyDominates(BB[0], BB[1]));
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 3u);
+  BB[0]->removeEdge(BB[1], DT);
+  EXPECT_TRUE(DT->verify());
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  // All remaining cases (unwind and handler) were to BB[1]. We can safely
+  // remove the entire instruction without replacing the unwind case to a new
+  // BasicBlock.
+  EXPECT_EQ(BB[0]->getTerminator()->getNumSuccessors(), 0u);
+  UnreachableInst *UI = dyn_cast<UnreachableInst>(BB[0]->getTerminator());
+  EXPECT_NE(UI, nullptr);
+}
+
+} // namespace

llvm/unittests/IR/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   Passes
   )
 
 set(IRSources
   AsmWriterTest.cpp
   AttributesTest.cpp
+  BasicBlockRemoveEdgeTest.cpp
   BasicBlockTest.cpp
   CFGBuilder.cpp
   ConstantRangeTest.cpp
   ConstantsTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
   DominatorTreeTest.cpp
   DominatorTreeBatchUpdatesTest.cpp