Remove LLVM 8.0.1 files.

1 files changed, 0 insertions, 992 deletions

diff --git a/gnu/llvm/unittests/IR/DominatorTreeTest.cpp b/gnu/llvm/unittests/IR/DominatorTreeTest.cpp
deleted file mode 100644
index 7539bbc860b..00000000000
--- a/gnu/llvm/unittests/IR/DominatorTreeTest.cpp
+++ /dev/null
@@ -1,992 +0,0 @@
-//===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include <random>
-#include "llvm/Analysis/PostDominators.h"
-#include "llvm/Analysis/IteratedDominanceFrontier.h"
-#include "llvm/AsmParser/Parser.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Support/SourceMgr.h"
-#include "CFGBuilder.h"
-#include "gtest/gtest.h"
-
-using namespace llvm;
-
-
-/// Build the dominator tree for the function and run the Test.
-static void runWithDomTree(
-    Module &M, StringRef FuncName,
-    function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)>
-        Test) {
-  auto *F = M.getFunction(FuncName);
-  ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
-  // Compute the dominator tree for the function.
-  DominatorTree DT(*F);
-  PostDominatorTree PDT(*F);
-  Test(*F, &DT, &PDT);
-}
-
-static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
-                                              StringRef ModuleStr) {
-  SMDiagnostic Err;
-  std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
-  assert(M && "Bad assembly?");
-  return M;
-}
-
-TEST(DominatorTree, Unreachable) {
-  StringRef ModuleString =
-      "declare i32 @g()\n"
-      "define void @f(i32 %x) personality i32 ()* @g {\n"
-      "bb0:\n"
-      "  %y1 = add i32 %x, 1\n"
-      "  %y2 = add i32 %x, 1\n"
-      "  %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n"
-      "bb1:\n"
-      "  %y4 = add i32 %x, 1\n"
-      "  br label %bb4\n"
-      "bb2:\n"
-      "  %y5 = landingpad i32\n"
-      "          cleanup\n"
-      "  br label %bb4\n"
-      "bb3:\n"
-      "  %y6 = add i32 %x, 1\n"
-      "  %y7 = add i32 %x, 1\n"
-      "  ret void\n"
-      "bb4:\n"
-      "  %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
-      "  %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
-      "  ret void\n"
-      "}\n";
-
-  // Parse the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
-        Function::iterator FI = F.begin();
-
-        BasicBlock *BB0 = &*FI++;
-        BasicBlock::iterator BBI = BB0->begin();
-        Instruction *Y1 = &*BBI++;
-        Instruction *Y2 = &*BBI++;
-        Instruction *Y3 = &*BBI++;
-
-        BasicBlock *BB1 = &*FI++;
-        BBI = BB1->begin();
-        Instruction *Y4 = &*BBI++;
-
-        BasicBlock *BB2 = &*FI++;
-        BBI = BB2->begin();
-        Instruction *Y5 = &*BBI++;
-
-        BasicBlock *BB3 = &*FI++;
-        BBI = BB3->begin();
-        Instruction *Y6 = &*BBI++;
-        Instruction *Y7 = &*BBI++;
-
-        BasicBlock *BB4 = &*FI++;
-        BBI = BB4->begin();
-        Instruction *Y8 = &*BBI++;
-        Instruction *Y9 = &*BBI++;
-
-        // Reachability
-        EXPECT_TRUE(DT->isReachableFromEntry(BB0));
-        EXPECT_TRUE(DT->isReachableFromEntry(BB1));
-        EXPECT_TRUE(DT->isReachableFromEntry(BB2));
-        EXPECT_FALSE(DT->isReachableFromEntry(BB3));
-        EXPECT_TRUE(DT->isReachableFromEntry(BB4));
-
-        // BB dominance
-        EXPECT_TRUE(DT->dominates(BB0, BB0));
-        EXPECT_TRUE(DT->dominates(BB0, BB1));
-        EXPECT_TRUE(DT->dominates(BB0, BB2));
-        EXPECT_TRUE(DT->dominates(BB0, BB3));
-        EXPECT_TRUE(DT->dominates(BB0, BB4));
-
-        EXPECT_FALSE(DT->dominates(BB1, BB0));
-        EXPECT_TRUE(DT->dominates(BB1, BB1));
-        EXPECT_FALSE(DT->dominates(BB1, BB2));
-        EXPECT_TRUE(DT->dominates(BB1, BB3));
-        EXPECT_FALSE(DT->dominates(BB1, BB4));
-
-        EXPECT_FALSE(DT->dominates(BB2, BB0));
-        EXPECT_FALSE(DT->dominates(BB2, BB1));
-        EXPECT_TRUE(DT->dominates(BB2, BB2));
-        EXPECT_TRUE(DT->dominates(BB2, BB3));
-        EXPECT_FALSE(DT->dominates(BB2, BB4));
-
-        EXPECT_FALSE(DT->dominates(BB3, BB0));
-        EXPECT_FALSE(DT->dominates(BB3, BB1));
-        EXPECT_FALSE(DT->dominates(BB3, BB2));
-        EXPECT_TRUE(DT->dominates(BB3, BB3));
-        EXPECT_FALSE(DT->dominates(BB3, BB4));
-
-        // BB proper dominance
-        EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
-        EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
-        EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
-        EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
-
-        EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
-        EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
-        EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
-        EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
-
-        EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
-        EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
-        EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
-        EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
-
-        EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
-        EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
-        EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
-        EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
-
-        // Instruction dominance in the same reachable BB
-        EXPECT_FALSE(DT->dominates(Y1, Y1));
-        EXPECT_TRUE(DT->dominates(Y1, Y2));
-        EXPECT_FALSE(DT->dominates(Y2, Y1));
-        EXPECT_FALSE(DT->dominates(Y2, Y2));
-
-        // Instruction dominance in the same unreachable BB
-        EXPECT_TRUE(DT->dominates(Y6, Y6));
-        EXPECT_TRUE(DT->dominates(Y6, Y7));
-        EXPECT_TRUE(DT->dominates(Y7, Y6));
-        EXPECT_TRUE(DT->dominates(Y7, Y7));
-
-        // Invoke
-        EXPECT_TRUE(DT->dominates(Y3, Y4));
-        EXPECT_FALSE(DT->dominates(Y3, Y5));
-
-        // Phi
-        EXPECT_TRUE(DT->dominates(Y2, Y9));
-        EXPECT_FALSE(DT->dominates(Y3, Y9));
-        EXPECT_FALSE(DT->dominates(Y8, Y9));
-
-        // Anything dominates unreachable
-        EXPECT_TRUE(DT->dominates(Y1, Y6));
-        EXPECT_TRUE(DT->dominates(Y3, Y6));
-
-        // Unreachable doesn't dominate reachable
-        EXPECT_FALSE(DT->dominates(Y6, Y1));
-
-        // Instruction, BB dominance
-        EXPECT_FALSE(DT->dominates(Y1, BB0));
-        EXPECT_TRUE(DT->dominates(Y1, BB1));
-        EXPECT_TRUE(DT->dominates(Y1, BB2));
-        EXPECT_TRUE(DT->dominates(Y1, BB3));
-        EXPECT_TRUE(DT->dominates(Y1, BB4));
-
-        EXPECT_FALSE(DT->dominates(Y3, BB0));
-        EXPECT_TRUE(DT->dominates(Y3, BB1));
-        EXPECT_FALSE(DT->dominates(Y3, BB2));
-        EXPECT_TRUE(DT->dominates(Y3, BB3));
-        EXPECT_FALSE(DT->dominates(Y3, BB4));
-
-        EXPECT_TRUE(DT->dominates(Y6, BB3));
-
-        // Post dominance.
-        EXPECT_TRUE(PDT->dominates(BB0, BB0));
-        EXPECT_FALSE(PDT->dominates(BB1, BB0));
-        EXPECT_FALSE(PDT->dominates(BB2, BB0));
-        EXPECT_FALSE(PDT->dominates(BB3, BB0));
-        EXPECT_TRUE(PDT->dominates(BB4, BB1));
-
-        // Dominance descendants.
-        SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs;
-
-        DT->getDescendants(BB0, DominatedBBs);
-        PDT->getDescendants(BB0, PostDominatedBBs);
-        EXPECT_EQ(DominatedBBs.size(), 4UL);
-        EXPECT_EQ(PostDominatedBBs.size(), 1UL);
-
-        // BB3 is unreachable. It should have no dominators nor postdominators.
-        DominatedBBs.clear();
-        PostDominatedBBs.clear();
-        DT->getDescendants(BB3, DominatedBBs);
-        DT->getDescendants(BB3, PostDominatedBBs);
-        EXPECT_EQ(DominatedBBs.size(), 0UL);
-        EXPECT_EQ(PostDominatedBBs.size(), 0UL);
-
-        // Check DFS Numbers before
-        DT->updateDFSNumbers();
-        EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);
-        EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL);
-        EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);
-        EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL);
-        EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL);
-        EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL);
-        EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL);
-        EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL);
-
-        // Check levels before
-        EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U);
-        EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U);
-        EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U);
-        EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);
-
-        // Reattach block 3 to block 1 and recalculate
-        BB1->getTerminator()->eraseFromParent();
-        BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1);
-        DT->recalculate(F);
-
-        // Check DFS Numbers after
-        DT->updateDFSNumbers();
-        EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);
-        EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL);
-        EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);
-        EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL);
-        EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL);
-        EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL);
-        EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL);
-        EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL);
-        EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL);
-        EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL);
-
-        // Check levels after
-        EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U);
-        EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U);
-        EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U);
-        EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U);
-        EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);
-
-        // Change root node
-        EXPECT_TRUE(DT->verify());
-        BasicBlock *NewEntry =
-            BasicBlock::Create(F.getContext(), "new_entry", &F, BB0);
-        BranchInst::Create(BB0, NewEntry);
-        EXPECT_EQ(F.begin()->getName(), NewEntry->getName());
-        EXPECT_TRUE(&F.getEntryBlock() == NewEntry);
-        DT->setNewRoot(NewEntry);
-        EXPECT_TRUE(DT->verify());
-      });
-}
-
-TEST(DominatorTree, NonUniqueEdges) {
-  StringRef ModuleString =
-      "define i32 @f(i32 %i, i32 *%p) {\n"
-      "bb0:\n"
-      "   store i32 %i, i32 *%p\n"
-      "   switch i32 %i, label %bb2 [\n"
-      "     i32 0, label %bb1\n"
-      "     i32 1, label %bb1\n"
-      "   ]\n"
-      " bb1:\n"
-      "   ret i32 1\n"
-      " bb2:\n"
-      "   ret i32 4\n"
-      "}\n";
-
-  // Parse the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
-        Function::iterator FI = F.begin();
-
-        BasicBlock *BB0 = &*FI++;
-        BasicBlock *BB1 = &*FI++;
-        BasicBlock *BB2 = &*FI++;
-
-        const Instruction *TI = BB0->getTerminator();
-        assert(TI->getNumSuccessors() == 3 && "Switch has three successors");
-
-        BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0));
-        assert(Edge_BB0_BB2.getEnd() == BB2 &&
-               "Default label is the 1st successor");
-
-        BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1));
-        assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor");
-
-        BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2));
-        assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor");
-
-        EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2));
-        EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1));
-
-        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1));
-        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1));
-
-        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2));
-        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2));
-      });
-}
-
-// Verify that the PDT is correctly updated in case an edge removal results
-// in a new unreachable CFG node. Also make sure that the updated PDT is the
-// same as a freshly recalculated one.
-//
-// For the following input code and initial PDT:
-//
-//          CFG                   PDT
-//
-//           A                    Exit
-//           |                     |
-//          _B                     D
-//         / | \                   |
-//        ^  v  \                  B
-//        \ /    D                / \
-//         C      \              C   A
-//                v
-//                Exit
-//
-// we verify that CFG' and PDT-updated is obtained after removal of edge C -> B.
-//
-//          CFG'               PDT-updated
-//
-//           A                    Exit
-//           |                   / | \
-//           B                  C  B  D
-//           | \                   |
-//           v  \                  A
-//          /    D
-//         C      \
-//         |       \
-// unreachable    Exit
-//
-// Both the blocks that end with ret and with unreachable become trivial
-// PostDominatorTree roots, as they have no successors.
-//
-TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {
-  StringRef ModuleString =
-      "define void @f() {\n"
-      "A:\n"
-      "  br label %B\n"
-      "B:\n"
-      "  br i1 undef, label %D, label %C\n"
-      "C:\n"
-      "  br label %B\n"
-      "D:\n"
-      "  ret void\n"
-      "}\n";
-
-  // Parse the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
-        Function::iterator FI = F.begin();
-
-        FI++;
-        BasicBlock *B = &*FI++;
-        BasicBlock *C = &*FI++;
-        BasicBlock *D = &*FI++;
-
-        ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
-        EXPECT_TRUE(DT->verify());
-        EXPECT_TRUE(PDT->verify());
-
-        C->getTerminator()->eraseFromParent();
-        new UnreachableInst(C->getContext(), C);
-
-        DT->deleteEdge(C, B);
-        PDT->deleteEdge(C, B);
-
-        EXPECT_TRUE(DT->verify());
-        EXPECT_TRUE(PDT->verify());
-
-        EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
-        EXPECT_NE(PDT->getNode(C), nullptr);
-
-        DominatorTree NDT(F);
-        EXPECT_EQ(DT->compare(NDT), 0);
-
-        PostDominatorTree NPDT(F);
-        EXPECT_EQ(PDT->compare(NPDT), 0);
-      });
-}
-
-// Verify that the PDT is correctly updated in case an edge removal results
-// in an infinite loop. Also make sure that the updated PDT is the
-// same as a freshly recalculated one.
-//
-// Test case:
-//
-//          CFG                   PDT
-//
-//           A                    Exit
-//           |                     |
-//          _B                     D
-//         / | \                   |
-//        ^  v  \                  B
-//        \ /    D                / \
-//         C      \              C   A
-//        / \      v
-//       ^  v      Exit
-//        \_/
-//
-// After deleting the edge C->B, C is part of an infinite reverse-unreachable
-// loop:
-//
-//          CFG'                  PDT'
-//
-//           A                    Exit
-//           |                   / | \
-//           B                  C  B  D
-//           | \                   |
-//           v  \                  A
-//          /    D
-//         C      \
-//        / \      v
-//       ^  v      Exit
-//        \_/
-//
-// As C now becomes reverse-unreachable, it forms a new non-trivial root and
-// gets connected to the virtual exit.
-// D does not postdominate B anymore, because there are two forward paths from
-// B to the virtual exit:
-//  - B -> C -> VirtualExit
-//  - B -> D -> VirtualExit.
-//
-TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) {
-  StringRef ModuleString =
-      "define void @f() {\n"
-      "A:\n"
-      "  br label %B\n"
-      "B:\n"
-      "  br i1 undef, label %D, label %C\n"
-      "C:\n"
-      "  switch i32 undef, label %C [\n"
-      "    i32 0, label %B\n"
-      "  ]\n"
-      "D:\n"
-      "  ret void\n"
-      "}\n";
-
-  // Parse the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
-        Function::iterator FI = F.begin();
-
-        FI++;
-        BasicBlock *B = &*FI++;
-        BasicBlock *C = &*FI++;
-        BasicBlock *D = &*FI++;
-
-        ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
-        EXPECT_TRUE(DT->verify());
-        EXPECT_TRUE(PDT->verify());
-
-        auto SwitchC = cast<SwitchInst>(C->getTerminator());
-        SwitchC->removeCase(SwitchC->case_begin());
-        DT->deleteEdge(C, B);
-        EXPECT_TRUE(DT->verify());
-        PDT->deleteEdge(C, B);
-        EXPECT_TRUE(PDT->verify());
-
-        EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
-        EXPECT_NE(PDT->getNode(C), nullptr);
-
-        DominatorTree NDT(F);
-        EXPECT_EQ(DT->compare(NDT), 0);
-
-        PostDominatorTree NPDT(F);
-        EXPECT_EQ(PDT->compare(NPDT), 0);
-      });
-}
-
-// Verify that the PDT is correctly updated in case an edge removal results
-// in an infinite loop.
-//
-// Test case:
-//
-//          CFG                   PDT
-//
-//           A                    Exit
-//           |                   / | \
-//           B--               C2  B  D
-//           |  \              /   |
-//           v   \            C    A
-//          /     D
-//         C--C2   \
-//        / \  \    v
-//       ^  v  --Exit
-//        \_/
-//
-// After deleting the edge C->E, C is part of an infinite reverse-unreachable
-// loop:
-//
-//          CFG'                  PDT'
-//
-//           A                    Exit
-//           |                   / | \
-//           B                  C  B  D
-//           | \                   |
-//           v  \                  A
-//          /    D
-//         C      \
-//        / \      v
-//       ^  v      Exit
-//        \_/
-//
-// In PDT, D does not post-dominate B. After the edge C -> C2 is removed,
-// C becomes a new nontrivial PDT root.
-//
-TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) {
-  StringRef ModuleString =
-      "define void @f() {\n"
-      "A:\n"
-      "  br label %B\n"
-      "B:\n"
-      "  br i1 undef, label %D, label %C\n"
-      "C:\n"
-      "  switch i32 undef, label %C [\n"
-      "    i32 0, label %C2\n"
-      "  ]\n"
-      "C2:\n"
-      "  ret void\n"
-      "D:\n"
-      "  ret void\n"
-      "}\n";
-
-  // Parse the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
-        Function::iterator FI = F.begin();
-
-        FI++;
-        BasicBlock *B = &*FI++;
-        BasicBlock *C = &*FI++;
-        BasicBlock *C2 = &*FI++;
-        BasicBlock *D = &*FI++;
-
-        EXPECT_TRUE(DT->verify());
-        EXPECT_TRUE(PDT->verify());
-
-        auto SwitchC = cast<SwitchInst>(C->getTerminator());
-        SwitchC->removeCase(SwitchC->case_begin());
-        DT->deleteEdge(C, C2);
-        PDT->deleteEdge(C, C2);
-        C2->removeFromParent();
-
-        EXPECT_EQ(DT->getNode(C2), nullptr);
-        PDT->eraseNode(C2);
-        delete C2;
-
-        EXPECT_TRUE(DT->verify());
-        EXPECT_TRUE(PDT->verify());
-
-        EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
-        EXPECT_NE(PDT->getNode(C), nullptr);
-
-        DominatorTree NDT(F);
-        EXPECT_EQ(DT->compare(NDT), 0);
-
-        PostDominatorTree NPDT(F);
-        EXPECT_EQ(PDT->compare(NPDT), 0);
-      });
-}
-
-// Verify that the IDF returns blocks in a deterministic way.
-//
-// Test case:
-//
-//          CFG
-//
-//          (A)
-//          / \
-//         /   \
-//       (B)   (C)
-//        |\   /|
-//        |  X  |
-//        |/   \|
-//       (D)   (E)
-//
-// IDF for block B is {D, E}, and the order of blocks in this list is defined by
-// their 1) level in dom-tree and 2) DFSIn number if the level is the same.
-//
-TEST(DominatorTree, IDFDeterminismTest) {
-  StringRef ModuleString =
-      "define void @f() {\n"
-      "A:\n"
-      "  br i1 undef, label %B, label %C\n"
-      "B:\n"
-      "  br i1 undef, label %D, label %E\n"
-      "C:\n"
-      "  br i1 undef, label %D, label %E\n"
-      "D:\n"
-      "  ret void\n"
-      "E:\n"
-      "  ret void\n"
-      "}\n";
-
-  // Parse the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
-        Function::iterator FI = F.begin();
-
-        BasicBlock *A = &*FI++;
-        BasicBlock *B = &*FI++;
-        BasicBlock *C = &*FI++;
-        BasicBlock *D = &*FI++;
-        BasicBlock *E = &*FI++;
-        (void)C;
-
-        DT->updateDFSNumbers();
-        ForwardIDFCalculator IDF(*DT);
-        SmallPtrSet<BasicBlock *, 1> DefBlocks;
-        DefBlocks.insert(B);
-        IDF.setDefiningBlocks(DefBlocks);
-
-        SmallVector<BasicBlock *, 32> IDFBlocks;
-        SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
-        IDF.resetLiveInBlocks();
-        IDF.calculate(IDFBlocks);
-
-
-        EXPECT_EQ(IDFBlocks.size(), 2UL);
-        EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL);
-        EXPECT_EQ(IDFBlocks[0], D);
-        EXPECT_EQ(IDFBlocks[1], E);
-        EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() <
-                    DT->getNode(IDFBlocks[1])->getDFSNumIn());
-      });
-}
-
-namespace {
-const auto Insert = CFGBuilder::ActionKind::Insert;
-const auto Delete = CFGBuilder::ActionKind::Delete;
-
-bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) {
-  return std::tie(A.Action, A.Edge.From, A.Edge.To) <
-         std::tie(B.Action, B.Edge.From, B.Edge.To);
-}
-}  // namespace
-
-TEST(DominatorTree, InsertReachable) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
-      {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
-
-  std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}},
-                                             {Insert, {"10", "9"}},
-                                             {Insert, {"7", "6"}},
-                                             {Insert, {"7", "5"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate;
-  while ((LastUpdate = B.applyUpdate())) {
-    EXPECT_EQ(LastUpdate->Action, Insert);
-    BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-    BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-    DT.insertEdge(From, To);
-    EXPECT_TRUE(DT.verify());
-    PDT.insertEdge(From, To);
-    EXPECT_TRUE(PDT.verify());
-  }
-}
-
-TEST(DominatorTree, InsertReachable2) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
-      {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"},
-      {"10", "9"}, {"9", "10"}};
-
-  std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
-  EXPECT_TRUE(LastUpdate);
-
-  EXPECT_EQ(LastUpdate->Action, Insert);
-  BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-  BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-  DT.insertEdge(From, To);
-  EXPECT_TRUE(DT.verify());
-  PDT.insertEdge(From, To);
-  EXPECT_TRUE(PDT.verify());
-}
-
-TEST(DominatorTree, InsertUnreachable) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"},  {"2", "3"},  {"3", "4"},
-                                       {"5", "6"},  {"5", "7"},  {"3", "8"},
-                                       {"9", "10"}, {"11", "12"}};
-
-  std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},
-                                             {Insert, {"8", "9"}},
-                                             {Insert, {"10", "12"}},
-                                             {Insert, {"10", "11"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate;
-  while ((LastUpdate = B.applyUpdate())) {
-    EXPECT_EQ(LastUpdate->Action, Insert);
-    BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-    BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-    DT.insertEdge(From, To);
-    EXPECT_TRUE(DT.verify());
-    PDT.insertEdge(From, To);
-    EXPECT_TRUE(PDT.verify());
-  }
-}
-
-TEST(DominatorTree, InsertFromUnreachable) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}};
-
-  std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
-  EXPECT_TRUE(LastUpdate);
-
-  EXPECT_EQ(LastUpdate->Action, Insert);
-  BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-  BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-  PDT.insertEdge(From, To);
-  EXPECT_TRUE(PDT.verify());
-  EXPECT_TRUE(PDT.getRoots().size() == 2);
-  // Make sure we can use a const pointer with getNode.
-  const BasicBlock *BB5 = B.getOrAddBlock("5");
-  EXPECT_NE(PDT.getNode(BB5), nullptr);
-}
-
-TEST(DominatorTree, InsertMixed) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"},  {"3", "4"},  {"5", "6"},   {"5", "7"},
-      {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};
-
-  std::vector<CFGBuilder::Update> Updates = {
-      {Insert, {"4", "5"}},   {Insert, {"2", "5"}},   {Insert, {"10", "9"}},
-      {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}},
-      {Insert, {"7", "5"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate;
-  while ((LastUpdate = B.applyUpdate())) {
-    EXPECT_EQ(LastUpdate->Action, Insert);
-    BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-    BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-    DT.insertEdge(From, To);
-    EXPECT_TRUE(DT.verify());
-    PDT.insertEdge(From, To);
-    EXPECT_TRUE(PDT.verify());
-  }
-}
-
-TEST(DominatorTree, InsertPermut) {
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"},  {"3", "4"},  {"5", "6"},   {"5", "7"},
-      {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};
-
-  std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},
-                                             {Insert, {"2", "5"}},
-                                             {Insert, {"10", "9"}},
-                                             {Insert, {"12", "10"}}};
-
-  while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) {
-    CFGHolder Holder;
-    CFGBuilder B(Holder.F, Arcs, Updates);
-    DominatorTree DT(*Holder.F);
-    EXPECT_TRUE(DT.verify());
-    PostDominatorTree PDT(*Holder.F);
-    EXPECT_TRUE(PDT.verify());
-
-    Optional<CFGBuilder::Update> LastUpdate;
-    while ((LastUpdate = B.applyUpdate())) {
-      EXPECT_EQ(LastUpdate->Action, Insert);
-      BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-      BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-      DT.insertEdge(From, To);
-      EXPECT_TRUE(DT.verify());
-      PDT.insertEdge(From, To);
-      EXPECT_TRUE(PDT.verify());
-    }
-  }
-}
-
-TEST(DominatorTree, DeleteReachable) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"},  {"5", "6"},
-      {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
-
-  std::vector<CFGBuilder::Update> Updates = {
-      {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate;
-  while ((LastUpdate = B.applyUpdate())) {
-    EXPECT_EQ(LastUpdate->Action, Delete);
-    BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-    BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-    DT.deleteEdge(From, To);
-    EXPECT_TRUE(DT.verify());
-    PDT.deleteEdge(From, To);
-    EXPECT_TRUE(PDT.verify());
-  }
-}
-
-TEST(DominatorTree, DeleteUnreachable) {
-  CFGHolder Holder;
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"},  {"5", "6"}, {"5", "7"},
-      {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
-
-  std::vector<CFGBuilder::Update> Updates = {
-      {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}};
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate;
-  while ((LastUpdate = B.applyUpdate())) {
-    EXPECT_EQ(LastUpdate->Action, Delete);
-    BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-    BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-    DT.deleteEdge(From, To);
-    EXPECT_TRUE(DT.verify());
-    PDT.deleteEdge(From, To);
-    EXPECT_TRUE(PDT.verify());
-  }
-}
-
-TEST(DominatorTree, InsertDelete) {
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
-      {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
-
-  std::vector<CFGBuilder::Update> Updates = {
-      {Insert, {"2", "4"}},  {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
-      {Insert, {"7", "6"}},  {Insert, {"7", "5"}},   {Delete, {"3", "8"}},
-      {Insert, {"10", "7"}}, {Insert, {"2", "8"}},   {Delete, {"3", "4"}},
-      {Delete, {"8", "9"}},  {Delete, {"11", "12"}}};
-
-  CFGHolder Holder;
-  CFGBuilder B(Holder.F, Arcs, Updates);
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-  PostDominatorTree PDT(*Holder.F);
-  EXPECT_TRUE(PDT.verify());
-
-  Optional<CFGBuilder::Update> LastUpdate;
-  while ((LastUpdate = B.applyUpdate())) {
-    BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-    BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-    if (LastUpdate->Action == Insert) {
-      DT.insertEdge(From, To);
-      PDT.insertEdge(From, To);
-    } else {
-      DT.deleteEdge(From, To);
-      PDT.deleteEdge(From, To);
-    }
-
-    EXPECT_TRUE(DT.verify());
-    EXPECT_TRUE(PDT.verify());
-  }
-}
-
-TEST(DominatorTree, InsertDeleteExhaustive) {
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
-      {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
-
-  std::vector<CFGBuilder::Update> Updates = {
-      {Insert, {"2", "4"}},  {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
-      {Insert, {"7", "6"}},  {Insert, {"7", "5"}},   {Delete, {"3", "8"}},
-      {Insert, {"10", "7"}}, {Insert, {"2", "8"}},   {Delete, {"3", "4"}},
-      {Delete, {"8", "9"}},  {Delete, {"11", "12"}}};
-
-  std::mt19937 Generator(0);
-  for (unsigned i = 0; i < 16; ++i) {
-    std::shuffle(Updates.begin(), Updates.end(), Generator);
-    CFGHolder Holder;
-    CFGBuilder B(Holder.F, Arcs, Updates);
-    DominatorTree DT(*Holder.F);
-    EXPECT_TRUE(DT.verify());
-    PostDominatorTree PDT(*Holder.F);
-    EXPECT_TRUE(PDT.verify());
-
-    Optional<CFGBuilder::Update> LastUpdate;
-    while ((LastUpdate = B.applyUpdate())) {
-      BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
-      BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
-      if (LastUpdate->Action == Insert) {
-        DT.insertEdge(From, To);
-        PDT.insertEdge(From, To);
-      } else {
-        DT.deleteEdge(From, To);
-        PDT.deleteEdge(From, To);
-      }
-
-      EXPECT_TRUE(DT.verify());
-      EXPECT_TRUE(PDT.verify());
-    }
-  }
-}
-
-TEST(DominatorTree, InsertIntoIrreducible) {
-  std::vector<CFGBuilder::Arc> Arcs = {
-      {"0", "1"},
-      {"1", "27"}, {"1", "7"},
-      {"10", "18"},
-      {"13", "10"},
-      {"18", "13"}, {"18", "23"},
-      {"23", "13"}, {"23", "24"},
-      {"24", "1"}, {"24", "18"},
-      {"27", "24"}};
-
-  CFGHolder Holder;
-  CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}});
-  DominatorTree DT(*Holder.F);
-  EXPECT_TRUE(DT.verify());
-
-  B.applyUpdate();
-  BasicBlock *From = B.getOrAddBlock("7");
-  BasicBlock *To = B.getOrAddBlock("23");
-  DT.insertEdge(From, To);
-
-  EXPECT_TRUE(DT.verify());
-}
-