Add dominator tree node downward splitting support

[hliao]

Summary

Tell downward splitting from the previous upward splitting.

• By upward splitting, a new basic block (NewBB) is split and inherits part or all predecessors of the original basic block (OrigBB) and has OrigBB as its only successor.
• By downward splitting, NewBB is split and inherits part of all successors of OrigBB and has OrigBB as its only predecessor.

So far, we only support upward splitting for (forward) dominator tree. For post-dominator tree, a upward splitting in the forward graph is in fact a downward splitting in the backward graph. This renders the current splitting support invalid if we want to incrementally update post-dominator tree.

Minor name change on the interface checking whether a dominator tree node is reachable from entry to use it for both dominator and post-dominator trees.

[hliao]

Add one check when update dominator tree for node splitting downward. Need to check whether the code is reachable from entry(s) or dominated by the root.

[hliao]

kindly ping

[jmolloy]

I don't think I'm an appropriate reviewer for this; resigning.

[gottesmm]

I also am not appropriate for reviewing this. Resigning as well.

[chandlerc]

It isn't clear in the description as stated what the end goal is, and the description of the patch isn't terribly clear. If this is still interesting, please update to make it clear where you're going with this and why.

include/llvm/CodeGen/MachineDominators.h

public:
   /// eraseNode - Removes a node from  the dominator tree. Block must not
   /// dominate any other blocks. Removes node from its immediate dominator's
   /// children list. Deletes dominator node associated with basic block BB.
   inline void eraseNode(MachineBasicBlock *BB) {
     applySplitCriticalEdges();
     DT->eraseNode(BB);
   }
 
-  /// splitBlock - BB is split and now it has one successor. Update dominator
-  /// tree to reflect this change.
-  inline void splitBlock(MachineBasicBlock* NewBB) {
+  /// splitBlockUpward - BB is split and now it has one successor. Update
+  /// dominator tree to reflect this change.
+  inline void splitBlockUpward(MachineBasicBlock* NewBB) {
     applySplitCriticalEdges();
-    DT->splitBlock(NewBB);
+    DT->splitBlockUpward(NewBB);
   }
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   bool isReachableFromEntry(const MachineBasicBlock *A) {
     applySplitCriticalEdges();
     return DT->isReachableFromEntry(A);
   }

include/llvm/Support/GenericDomTree.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 namespace llvm {
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
     PrintDomTree<NodeT>(*I, o, Lev + 1);
 }
 
 // The calculate routine is provided in a separate header but referenced here.
 template <class FuncT, class N>
 void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT,
                FuncT &F);
 
+template <class GraphT> class DominatedAndPrunedTraversal {
+  typedef typename GraphT::NodeType NodeTy;
+
+  DominatorTreeBase<NodeTy> &DT;
+  DomTreeNodeBase<NodeTy> *Parent;
+  NodeTy *PrunedBlock;
+  SmallPtrSet<const NodeTy *, 8> Visited;
+
+public:
+  DominatedAndPrunedTraversal(DominatorTreeBase<NodeTy> &D,
+                              DomTreeNodeBase<NodeTy> *N, NodeTy *PrunedBlock)
+      : DT(D), Parent(N), PrunedBlock(PrunedBlock) {}
+
+  bool preVisit(const NodeTy *From, const NodeTy *To) {
+    if (To == PrunedBlock)
+      return false;
+    DomTreeNodeBase<NodeTy> *N = DT.getNode(const_cast<NodeTy *>(To));
+    if (!DT.dominates(Parent, N))
+      return false;
+    return Visited.insert(To).second;
+  }
+  void postVisit(const NodeTy *) {}
+};
+
+/// Specialize po_iterator_storage.
+template <class GraphT>
+class po_iterator_storage<DominatedAndPrunedTraversal<GraphT>, true> {
+  typedef typename GraphT::NodeType NodeTy;
+
+  DominatedAndPrunedTraversal<GraphT> &DAPT;
+
+public:
+  po_iterator_storage(DominatedAndPrunedTraversal<GraphT> &T) : DAPT(T) {}
+
+  bool insertEdge(const NodeTy *From, const NodeTy *To) {
+    return DAPT.preVisit(From, To);
+  }
+  void finishPostorder(const NodeTy *N) { DAPT.postVisit(N); }
+};
+
 /// \brief Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
 /// various graphs in the LLVM IR or in the code generator.
 template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
   DominatorTreeBase(const DominatorTreeBase &) = delete;
   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
 
   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
                                const DomTreeNodeBase<NodeT> *B) const {
     assert(A != B);
-    assert(isReachableFromEntry(B));
-    assert(isReachableFromEntry(A));
+    assert(isDominatedByRoot(B));
+    assert(isDominatedByRoot(A));
 
     const DomTreeNodeBase<NodeT> *IDom;
     while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
       B = IDom; // Walk up the tree
     return IDom != nullptr;
   }
 
   /// \brief Wipe this tree's state without releasing any resources.
void reset() {
     IDoms.clear();
     this->Roots.clear();
     Vertex.clear();
     RootNode = nullptr;
     DFSInfoValid = false;
     SlowQueries = 0;
   }
 
-  // NewBB is split and now it has one successor. Update dominator tree to
-  // reflect this change.
+  // NewBB is split upward and now it has the original BB as its single
+  // successor. Update dominator tree to reflect this change.
+  //
+  // By `upward`, the original block
+  //
+  //     |   |   |   |
+  //     |   |   |   |
+  // +---v---v---v---v---+
+  // |                   |
+  // |      OrigBB       |
+  // |                   |
+  // +---+---+---+---+---+
+  //     |   |   |   |
+  //     v   v   v   v
+  //
+  //
+  // is split into
+  //
+  //
+  //     |    |         |      |
+  //     |    |         |      |
+  //     |    |   +-----v------v------+
+  //     |    |   |                   |
+  //     |    |   |       NewBB       |
+  //     |    |   |                   |
+  //     |    |   +---------+---------+
+  //     |    |             |
+  //     |    |             |
+  //     |    |    /--------/
+  //     |    |    |
+  //     |    |    |
+  // +---v----v----v-----+
+  // |                   |
+  // |      OrigBB       |
+  // |                   |
+  // +---+---+---+---+---+
+  //     |   |   |   |
+  //     v   v   v   v
+  //
   template <class N, class GraphT>
-  void Split(DominatorTreeBase<typename GraphT::NodeType> &DT,
+  void splitUpward(DominatorTreeBase<typename GraphT::NodeType> &DT,
                    typename GraphT::NodeType *NewBB) {
     assert(std::distance(GraphT::child_begin(NewBB),
                          GraphT::child_end(NewBB)) == 1 &&
            "NewBB should have a single successor!");
-    typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB);
+    typename GraphT::NodeType *OrigBB = *GraphT::child_begin(NewBB);
 
     std::vector<typename GraphT::NodeType *> PredBlocks;
     typedef GraphTraits<Inverse<N>> InvTraits;
     for (typename InvTraits::ChildIteratorType
              PI = InvTraits::child_begin(NewBB),
              PE = InvTraits::child_end(NewBB);
          PI != PE; ++PI)
       PredBlocks.push_back(*PI);
 
     assert(!PredBlocks.empty() && "No predblocks?");
 
-    bool NewBBDominatesNewBBSucc = true;
+    bool NewBBDominatesOrigBB = true;
     for (typename InvTraits::ChildIteratorType
-             PI = InvTraits::child_begin(NewBBSucc),
-             E = InvTraits::child_end(NewBBSucc);
+             PI = InvTraits::child_begin(OrigBB),
+             E = InvTraits::child_end(OrigBB);
          PI != E; ++PI) {
       typename InvTraits::NodeType *ND = *PI;
-      if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
-          DT.isReachableFromEntry(ND)) {
-        NewBBDominatesNewBBSucc = false;
+      if (ND != NewBB && !DT.dominates(OrigBB, ND) &&
+          DT.isDominatedByRoot(DT.getNode(ND))) {
+        NewBBDominatesOrigBB = false;
         break;
       }
     }
 
     // Find NewBB's immediate dominator and create new dominator tree node for
     // NewBB.
     NodeT *NewBBIDom = nullptr;
     unsigned i = 0;
     for (i = 0; i < PredBlocks.size(); ++i)
-      if (DT.isReachableFromEntry(PredBlocks[i])) {
+      if (DT.isDominatedByRoot(DT.getNode(PredBlocks[i]))) {
         NewBBIDom = PredBlocks[i];
         break;
       }
 
     // It's possible that none of the predecessors of NewBB are reachable;
     // in that case, NewBB itself is unreachable, so nothing needs to be
     // changed.
     if (!NewBBIDom)
       return;
 
     for (i = i + 1; i < PredBlocks.size(); ++i) {
-      if (DT.isReachableFromEntry(PredBlocks[i]))
+      if (DT.isDominatedByRoot(DT.getNode(PredBlocks[i])))
         NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
     }
 
     // Create the new dominator tree node... and set the idom of NewBB.
     DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
 
     // If NewBB strictly dominates other blocks, then it is now the immediate
-    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
-    if (NewBBDominatesNewBBSucc) {
-      DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
-      DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
-    }
+    // dominator of OrigBB. Update the dominator tree as appropriate.
+    if (NewBBDominatesOrigBB) {
+      DomTreeNodeBase<NodeT> *OrigBBNode = DT.getNode(OrigBB);
+      DT.changeImmediateDominator(OrigBBNode, NewBBNode);
+    }
+
+  // NewBB is split downward and now it has the original BB as its single
+  // predecessor. Update dominator tree to reflect this change.
+  //
+  // By `downward`, the original block
+  //
+  //     |   |   |   |
+  //     |   |   |   |
+  // +---v---v---v---v---+
+  // |                   |
+  // |      OrigBB       |
+  // |                   |
+  // +---+---+---+---+---+
+  //     |   |   |   |
+  //     v   v   v   v
+  //
+  //
+  // is split into
+  //
+  //
+  //     |   |   |   |
+  //     |   |   |   |
+  // +---v---v---v---v---+
+  // |                   |
+  // |      OrigBB       |
+  // |                   |
+  // +---+----+----+-----+
+  //     |    |    |
+  //     |    |    |
+  //     |    |    \--------\
+  //     |    |             |
+  //     |    |             |
+  //     |    |   +---------v---------+
+  //     |    |   |                   |
+  //     |    |   |       NewBB       |
+  //     |    |   |                   |
+  //     |    |   +-----+------+------+
+  //     |    |         |      |
+  //     v    v         v      v
+  //
+  template <class N, class GraphT>
+  void splitDownward(DominatorTreeBase<typename GraphT::NodeType> &DT,
+                     typename GraphT::NodeType *NewBB) {
+    typedef GraphTraits<Inverse<N>> InvGraphT;
+    assert(std::distance(InvGraphT::child_begin(NewBB),
+                         InvGraphT::child_end(NewBB)) == 1 &&
+           "NewBB should have a single predecessor!");
+    typename InvGraphT::NodeType *OrigBB = *InvGraphT::child_begin(NewBB);
+
+    auto OrigNode = DT.getNode(OrigBB);
+    // Skip node not reachable.
+    if (!OrigNode) return;
+
+    // Collect original child blocks of OrigBB.
+    SmallPtrSet<typename GraphT::NodeType *, 8> OrigChildBBs;
+    for (auto I = OrigNode->begin(), E = OrigNode->end(); I != E; ++I)
+      OrigChildBBs.insert((*I)->getBlock());
+
+    // Add NewBB with OrigBB as its immediate dominator since NewBB has a
+    // single predecessor.
+    DT.addNewBlock(NewBB, OrigBB);
+
+    // Prune original child blocks.
+    DominatedAndPrunedTraversal<GraphT> DAPT(DT, OrigNode, NewBB);
+    for (auto I : post_order_ext<N>(OrigBB, DAPT))
+      OrigChildBBs.erase(I);
+    // Re-parent the remaining blocks, which are only reachable from the split
+    // NewBB.
+    for (auto I : OrigChildBBs)
+      DT.changeImmediateDominator(I, NewBB);
   }
 
 public:
   explicit DominatorTreeBase(bool isPostDom)
       : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
 
   DominatorTreeBase(DominatorTreeBase &&Arg)
       : DominatorBase<NodeT>(
public:
 
   bool properlyDominates(const NodeT *A, const NodeT *B) const;
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   bool isReachableFromEntry(const NodeT *A) const {
     assert(!this->isPostDominator() &&
            "This is not implemented for post dominators");
-    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
+    return isDominatedByRoot(getNode(const_cast<NodeT *>(A)));
   }
 
-  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
+  bool isDominatedByRoot(const DomTreeNodeBase<NodeT> *A) const { return A; }
 
   /// dominates - Returns true iff A dominates B.  Note that this is not a
   /// constant time operation!
   ///
   bool dominates(const DomTreeNodeBase<NodeT> *A,
                  const DomTreeNodeBase<NodeT> *B) const {
     // A node trivially dominates itself.
     if (B == A)
       return true;
 
     // An unreachable node is dominated by anything.
-    if (!isReachableFromEntry(B))
+    if (!isDominatedByRoot(B))
       return true;
 
     // And dominates nothing.
-    if (!isReachableFromEntry(A))
+    if (!isDominatedByRoot(A))
       return false;
 
     // Compare the result of the tree walk and the dfs numbers, if expensive
     // checks are enabled.
 #ifdef XDEBUG
     assert((!DFSInfoValid ||
             (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
            "Tree walk disagrees with dfs numbers!");
if (IDom) {
              "Not in immediate dominator children set!");
       // I am no longer your child...
       IDom->Children.erase(I);
     }
 
     DomTreeNodes.erase(BB);
   }
 
-  /// splitBlock - BB is split and now it has one successor. Update dominator
-  /// tree to reflect this change.
-  void splitBlock(NodeT *NewBB) {
+  /// splitBlockUpward - BB is split upward and now it has one successor.
+  /// Update dominator tree to reflect this change.
+  void splitBlockUpward(NodeT *NewBB) {
+    if (this->IsPostDominators)
+      this->splitDownward<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(
+          *this, NewBB);
+    else
+      this->splitUpward<NodeT *, GraphTraits<NodeT *>>(*this, NewBB);
+  }
+
+  /// splitBlockDownward - BB is split downward and now it has one successor.
+  /// Update dominator tree to reflect this change.
+  void splitBlockDownward(NodeT *NewBB) {
     if (this->IsPostDominators)
-      this->Split<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this,
+      this->splitUpward<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this,
                                                                          NewBB);
     else
-      this->Split<NodeT *, GraphTraits<NodeT *>>(*this, NewBB);
+      this->splitDownward<NodeT *, GraphTraits<NodeT *>>(*this, NewBB);
   }
 
   /// print - Convert to human readable form
   ///
   void print(raw_ostream &o) const {
     o << "=============================--------------------------------\n";
     if (this->isPostDominator())
       o << "Inorder PostDominator Tree: ";

lib/Transforms/Utils/BasicBlockUtils.cpp

 /// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA
 /// analysis information.
 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
                                       ArrayRef<BasicBlock *> Preds,
                                       DominatorTree *DT, LoopInfo *LI,
                                       bool PreserveLCSSA, bool &HasLoopExit) {
   // Update dominator tree if available.
   if (DT)
-    DT->splitBlock(NewBB);
+    DT->splitBlockUpward(NewBB);
 
   // The rest of the logic is only relevant for updating the loop structures.
   if (!LI)
     return;
 
   Loop *L = LI->getLoopFor(OldBB);
 
   // If we need to preserve loop analyses, collect some information about how

lib/Transforms/Utils/CodeExtractor.cpp

void CodeExtractor::severSplitPHINodes(BasicBlock *&Header) {
   BasicBlock *OldPred = Header;
   Blocks.remove(OldPred);
   Blocks.insert(NewBB);
   Header = NewBB;
 
   // Okay, update dominator sets. The blocks that dominate the new one are the
   // blocks that dominate TIBB plus the new block itself.
   if (DT)
-    DT->splitBlock(NewBB);
+    DT->splitBlockUpward(NewBB);
 
   // Okay, now we need to adjust the PHI nodes and any branches from within the
   // region to go to the new header block instead of the old header block.
   if (NumPredsFromRegion) {
     PHINode *PN = cast<PHINode>(OldPred->begin());
     // Loop over all of the predecessors of OldPred that are in the region,
     // changing them to branch to NewBB instead.
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)

lib/Transforms/Utils/LoopSimplify.cpp

static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
 
   //===--- Update all analyses which we must preserve now -----------------===//
 
   // Update Loop Information - we know that this block is now in the current
   // loop and all parent loops.
   L->addBasicBlockToLoop(BEBlock, *LI);
 
   // Update dominator information
-  DT->splitBlock(BEBlock);
+  DT->splitBlockUpward(BEBlock);
 
   return BEBlock;
 }
 
 /// \brief Simplify one loop and queue further loops for simplification.
 ///
 /// FIXME: Currently this accepts both lots of analyses that it uses and a raw
 /// Pass pointer. The Pass pointer is used by numerous utilities to update

lib/Transforms/Vectorize/SLPVectorizer.cpp

for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
     Insert->moveBefore(PreHeader->getTerminator());
   }
 
   // Make a list of all reachable blocks in our CSE queue.
   SmallVector<const DomTreeNode *, 8> CSEWorkList;
   CSEWorkList.reserve(CSEBlocks.size());
   for (BasicBlock *BB : CSEBlocks)
     if (DomTreeNode *N = DT->getNode(BB)) {
-      assert(DT->isReachableFromEntry(N));
+      assert(DT->isDominatedByRoot(N));
       CSEWorkList.push_back(N);
     }
 
   // Sort blocks by domination. This ensures we visit a block after all blocks
   // dominating it are visited.
   std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(),
                    [this](const DomTreeNode *A, const DomTreeNode *B) {
     return DT->properlyDominates(A, B);

unittests/IR/DominatorTreeTest.cpp

 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace llvm {
   void initializeDPassPass(PassRegistry&);
+  void initializeSplitTestPass(PassRegistry&);
 
   namespace {
     struct DPass : public FunctionPass {
       static char ID;
       bool runOnFunction(Function &F) override {
         DominatorTree *DT =
             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
         PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
namespace {
 
     TEST(DominatorTree, Unreachable) {
       DPass *P = new DPass();
       std::unique_ptr<Module> M = makeLLVMModule(P);
       legacy::PassManager Passes;
       Passes.add(P);
       Passes.run(*M);
     }
+
+    struct SplitTest : public FunctionPass {
+      typedef std::function<bool(Pass *, Function &, bool &, bool &)>
+        CallbackFuncTy;
+
+      CallbackFuncTy Callback;
+
+      explicit SplitTest(CallbackFuncTy Callback = nullptr)
+        : FunctionPass(ID), Callback(Callback) {
+        initializeSplitTestPass(*PassRegistry::getPassRegistry());
+      }
+
+      void getAnalysisUsage(AnalysisUsage &AU) const override {
+        AU.addRequired<DominatorTreeWrapperPass>();
+        AU.addRequired<PostDominatorTree>();
+      }
+
+      bool runOnFunction(Function &F) override {
+        DominatorTree *DT =
+          &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+        PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
+
+        bool NeedVerifyDom = false;
+        bool NeedVerifyPostDom = false;
+        bool Changed = Callback(this, F, NeedVerifyDom, NeedVerifyPostDom);
+
+        EXPECT_TRUE(!NeedVerifyDom || !verifyDominatorTree(F, DT));
+        EXPECT_TRUE(!NeedVerifyPostDom || !verifyDominatorTree(F, PDT->DT));
+
+        return Changed;
+      }
+
+      bool verifyDominatorTree(Function &F,
+                               DominatorTreeBase<BasicBlock> *DT) {
+        DominatorTreeBase<BasicBlock> OtherDT(DT->isPostDominator());
+        OtherDT.recalculate(F);
+        return DT->compare(OtherDT);
+      }
+
+      static char ID;
+    };
+
+    char SplitTest::ID = 0;
+
+    std::unique_ptr<Module> loadModule(const char *ModuleString) {
+      LLVMContext &C = getGlobalContext();
+      SMDiagnostic Err;
+      return parseAssemblyString(ModuleString, Err, C);
+    }
   }
 }
 
 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)
+
+INITIALIZE_PASS_BEGIN(SplitTest, "split-test-pass", "split-test-pass", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_END(SplitTest, "split-test-pass", "split-test-pass", false, false)
+
+TEST(DominatorTree, SplitUp) {
+  std::unique_ptr<Module> M = loadModule(
+      "define void @t0() {\n"
+      "entry:\n"
+      "  br i1 undef, label %bb0, label %exit\n"
+      "bb0:\n"
+      "  br i1 undef, label %bb1, label %bb2\n"
+      "bb1:\n"
+      "  br label %exit\n"
+      "bb2:\n"
+      "  br label %exit\n"
+      "exit:\n"
+      "  ret void\n"
+      "}\n");
+  Function *t0 = M->getFunction("t0");
+  SplitTest *P = new SplitTest([t0](Pass *P, Function &F,
+                                    bool &NeedVerifyDom,
+                                    bool &NeedVerifyPostDom) -> bool {
+    if (t0 != &F)
+      return false;
+    Function::iterator FI = F.begin();
+
+    /* Entry */ FI++;
+    /* BB0 */   FI++;
+    BasicBlock *BB1 = &*FI++;
+    BasicBlock *BB2 = &*FI++;
+    BasicBlock *Exit = &*FI++;
+
+    BasicBlock *Joint = BasicBlock::Create(F.getContext(), "joint", &F, Exit);
+    BranchInst::Create(Exit, Joint);
+
+    BB1->getTerminator()->setSuccessor(0, Joint);
+    BB2->getTerminator()->setSuccessor(0, Joint);
+
+    if (auto DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
+      DominatorTree &DT = DTWP->getDomTree();
+      DT.splitBlockUpward(Joint);
+      NeedVerifyDom = true;
+    }
+
+    if (auto PDT = P->getAnalysisIfAvailable<PostDominatorTree>()) {
+      PDT->DT->splitBlockUpward(Joint);
+      NeedVerifyPostDom = true;
+    }
+
+    return true;
+  });
+  legacy::PassManager PM;
+  PM.add(P);
+  PM.run(*M);
+}
+
+TEST(DominatorTree, SplitDown) {
+  std::unique_ptr<Module> M = loadModule(
+      "define void @t0() {\n"
+      "entry:\n"
+      "  indirectbr i8* undef, [label %bb0, label %bb1, label %bb2]\n"
+      "bb0:\n"
+      "  br i1 undef, label %bb3, label %bb4\n"
+      "bb1:\n"
+      "  br label %exit\n"
+      "bb2:\n"
+      "  br label %exit\n"
+      "bb3:\n"
+      "  br label %exit\n"
+      "bb4:\n"
+      "  br i1 undef, label %exit, label %bb1\n"
+      "exit:\n"
+      "  ret void\n"
+      "}\n");
+  Function *t0 = M->getFunction("t0");
+  SplitTest *P = new SplitTest([t0](Pass *P, Function &F,
+                                    bool &NeedVerifyDom,
+                                    bool &NeedVerifyPostDom) -> bool {
+    if (t0 != &F)
+      return false;
+
+    Function::iterator FI = F.begin();
+    BasicBlock *Entry = &*FI++;
+    BasicBlock *BB0 = &*FI++;
+    BasicBlock *BB1 = &*FI++;
+    BasicBlock *BB2 = &*FI++;
+    BasicBlock *Split = BasicBlock::Create(F.getContext(), "split", &F, BB0);
+    BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F.getContext()), Split);
+
+    Entry->getTerminator()->eraseFromParent();
+    BranchInst::Create(BB0, Split, ConstantInt::getTrue(F.getContext()), Entry);
+
+    if (auto DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
+      DominatorTree &DT = DTWP->getDomTree();
+      DT.splitBlockDownward(Split);
+      NeedVerifyDom = true;
+    }
+
+    if (auto PDT = P->getAnalysisIfAvailable<PostDominatorTree>()) {
+      PDT->DT->splitBlockDownward(Split);
+      NeedVerifyPostDom = true;
+    }
+
+    return true;
+  });
+  legacy::PassManager PM;
+  PM.add(P);
+  PM.run(*M);
+}