Index: tools/LLVMBuild.txt
===================================================================
--- tools/LLVMBuild.txt
+++ tools/LLVMBuild.txt
@@ -19,6 +19,7 @@
 subdirectories =
  bugpoint
  dsymutil
+ dt-benchmark
  llc
  lli
  llvm-ar
Index: tools/dt-benchmark/CFGB.h
===================================================================
--- /dev/null
+++ tools/dt-benchmark/CFGB.h
@@ -0,0 +1,98 @@
+//===- CFGBuilder.h - CFG building and updating utility ----------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// CFGBuilders provides utilities fo building and updating CFG for testing
+/// purposes.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_CFG_BUILDER_H
+#define LLVM_UNITTESTS_CFG_BUILDER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Debug.h"
+
+#include <memory>
+#include <set>
+#include <tuple>
+#include <vector>
+
+namespace llvm {
+
+  class LLVMContext;
+  class Module;
+  class Function;
+  class BasicBlock;
+  class raw_ostream;
+
+namespace Benchmark {
+
+  struct CFGHolder {
+    std::unique_ptr<LLVMContext> Context;
+    std::unique_ptr<Module> M;
+    Function *F;
+
+    CFGHolder(StringRef ModuleName = "m", StringRef FunctionName = "foo");
+    ~CFGHolder(); // Defined in the .cpp file so we can use forward declarations.
+  };
+
+/// \brief
+/// CFGBuilder builds IR with specific CFG, based on the supplied list of arcs.
+/// It's able to apply the provided updates and automatically modify the IR.
+///
+/// Internally it makes every basic block end with either SwitchInst or with
+/// UnreachableInst. When all arc to a BB are deleted, the BB remains in the
+/// function and doesn't get deleted.
+///
+  class CFGBuilder {
+  public:
+    struct Arc {
+      StringRef From;
+      StringRef To;
+
+      friend bool operator<(const Arc &LHS, const Arc &RHS) {
+        return std::tie(LHS.From, LHS.To) <
+               std::tie(RHS.From, RHS.To);
+      }
+    };
+
+    enum class ActionKind { Insert, Delete };
+    struct Update {
+      ActionKind Action;
+      Arc Edge;
+    };
+
+    CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
+               std::vector<Update> Updates);
+
+    BasicBlock *getOrAddBlock(StringRef BlockName);
+    Optional<Update> getNextUpdate() const;
+    Optional<Update> applyUpdate();
+    void dump(raw_ostream &OS = dbgs()) const;
+
+  private:
+    void buildCFG(const std::vector<Arc> &Arcs);
+    bool connect(const Arc &A);
+    bool disconnect(const Arc &A);
+
+    Function *F;
+    unsigned UpdateIdx = 0;
+    StringMap<BasicBlock *> NameToBlock;
+    std::set<Arc> Arcs;
+    std::vector<Update> Updates;
+  };
+
+} // namespace Benchmark
+
+} // namespace llvm
+
+#endif
Index: tools/dt-benchmark/CFGB.cpp
===================================================================
--- /dev/null
+++ tools/dt-benchmark/CFGB.cpp
@@ -0,0 +1,161 @@
+//===- llvm/Testing/Support/CFGBuilder.cpp --------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "CFGB.h"
+
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/TypeBuilder.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#define DEBUG_TYPE "cfg-builder"
+
+using namespace llvm;
+using namespace llvm::Benchmark;
+
+CFGHolder::CFGHolder(StringRef ModuleName, StringRef FunctionName)
+    : Context(llvm::make_unique<LLVMContext>()),
+      M(llvm::make_unique<Module>(ModuleName, *Context)) {
+  FunctionType *FTy = TypeBuilder<void(), false>::get(*Context);
+  F = cast<Function>(M->getOrInsertFunction(FunctionName, FTy));
+}
+CFGHolder::~CFGHolder() = default;
+
+CFGBuilder::CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
+                       std::vector<Update> Updates)
+    : F(F), Updates(std::move(Updates)) {
+  assert(F);
+  buildCFG(InitialArcs);
+}
+
+static void ConnectBlocks(BasicBlock *From, BasicBlock *To) {
+//  DEBUG(dbgs() << "Creating BB arc " << From->getName() << " -> "
+//               << To->getName() << "\n";
+//            dbgs().flush());
+  auto *IntTy = IntegerType::get(From->getContext(), 32);
+
+  if (isa<UnreachableInst>(From->getTerminator()))
+    From->getTerminator()->eraseFromParent();
+  if (!From->getTerminator()) {
+    IRBuilder<> IRB(From);
+    IRB.CreateSwitch(ConstantInt::get(IntTy, 0), To);
+    return;
+  }
+
+  SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
+  const auto Last = SI->getNumCases();
+
+  auto *IntVal = ConstantInt::get(IntTy, Last);
+  SI->addCase(IntVal, To);
+}
+
+static void DisconnectBlocks(BasicBlock *From, BasicBlock *To) {
+//  DEBUG(dbgs() << "Deleting BB arc " << From->getName() << " -> "
+//               << To->getName() << "\n";
+//            dbgs().flush());
+  SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
+
+  if (SI->getNumCases() == 0) {
+    SI->eraseFromParent();
+    IRBuilder<> IRB(From);
+    IRB.CreateUnreachable();
+    return;
+  }
+
+  if (SI->getDefaultDest() == To) {
+    auto FirstC = SI->case_begin();
+    SI->setDefaultDest(FirstC->getCaseSuccessor());
+    SI->removeCase(FirstC);
+    return;
+  }
+
+  for (auto CIt = SI->case_begin(); CIt != SI->case_end(); ++CIt)
+    if (CIt->getCaseSuccessor() == To) {
+      SI->removeCase(CIt);
+      return;
+    }
+}
+
+BasicBlock *CFGBuilder::getOrAddBlock(StringRef BlockName) {
+  auto BIt = NameToBlock.find(BlockName);
+  if (BIt != NameToBlock.end())
+    return BIt->second;
+
+  auto *BB = BasicBlock::Create(F->getParent()->getContext(), BlockName, F);
+  IRBuilder<> IRB(BB);
+  IRB.CreateUnreachable();
+  NameToBlock[BlockName] = BB;
+  return BB;
+}
+
+bool CFGBuilder::connect(const Arc &A) {
+  BasicBlock *From = getOrAddBlock(A.From);
+  BasicBlock *To = getOrAddBlock(A.To);
+  if (Arcs.count(A) != 0)
+    return false;
+
+  Arcs.insert(A);
+  ConnectBlocks(From, To);
+  return true;
+}
+
+bool CFGBuilder::disconnect(const Arc &A) {
+  assert(NameToBlock.count(A.From) != 0 && "No block to disconnect (From)");
+  assert(NameToBlock.count(A.To) != 0 && "No block to disconnect (To)");
+  if (Arcs.count(A) == 0)
+    return false;
+
+  BasicBlock *From = getOrAddBlock(A.From);
+  BasicBlock *To = getOrAddBlock(A.To);
+  Arcs.erase(A);
+  DisconnectBlocks(From, To);
+  return true;
+}
+
+void CFGBuilder::buildCFG(const std::vector<Arc> &NewArcs) {
+  for (const auto &A : NewArcs) {
+    connect(A);
+  }
+}
+
+Optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
+  if (UpdateIdx == Updates.size())
+    return None;
+  return Updates[UpdateIdx];
+}
+
+Optional<CFGBuilder::Update> CFGBuilder::applyUpdate() {
+  if (UpdateIdx == Updates.size())
+    return None;
+  Update NextUpdate = Updates[UpdateIdx++];
+  if (NextUpdate.Action == ActionKind::Insert)
+    connect(NextUpdate.Edge);
+  else
+    disconnect(NextUpdate.Edge);
+
+  return NextUpdate;
+}
+
+void CFGBuilder::dump(raw_ostream &OS) const {
+  OS << "Arcs:\n";
+  size_t i = 0;
+  for (const auto &A : Arcs)
+    OS << "  " << i++ << ":\t" << A.From << " -> " << A.To << "\n";
+
+  OS << "Updates:\n";
+  i = 0;
+  for (const auto &U : Updates) {
+    OS << (i + 1 == UpdateIdx ? "->" : "  ") << i
+       << ((U.Action == ActionKind::Insert) ? "\tIns " : "\tDel ")
+       << U.Edge.From << " -> " << U.Edge.To << "\n";
+    ++i;
+  }
+}
+
Index: tools/dt-benchmark/CMakeLists.txt
===================================================================
--- /dev/null
+++ tools/dt-benchmark/CMakeLists.txt
@@ -0,0 +1,13 @@
+set(LLVM_LINK_COMPONENTS
+  Analysis
+  BitReader
+  BitWriter
+  Core
+  IRReader
+  Support
+  )
+
+add_llvm_tool(dt-benchmark
+    dt-benchmark.cpp
+    CFGB.cpp
+  )
Index: tools/dt-benchmark/LLVMBuild.txt
===================================================================
--- /dev/null
+++ tools/dt-benchmark/LLVMBuild.txt
@@ -0,0 +1,22 @@
+;===- ./tools/dt-benchmark/LLVMBuild.txt -----------------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Tool
+name = dt-benchmark
+parent = Tools
+required_libraries = BitReader
Index: tools/dt-benchmark/dt-benchmark.cpp
===================================================================
--- /dev/null
+++ tools/dt-benchmark/dt-benchmark.cpp
@@ -0,0 +1,163 @@
+//===-- dt-benchmark.cpp - DomTrees benchmarking tool  --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/Dominators.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/IR/TypeBuilder.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/SourceMgr.h"
+
+#include "CFGB.h"
+
+#include <chrono>
+#include <fstream>
+#include <random>
+#include <sstream>
+
+#define DEBUG_TYPE "dt-benchmark"
+
+using namespace llvm;
+using namespace llvm::Benchmark;
+
+static cl::opt<std::string> InputFile(cl::Positional, cl::desc("<input file>"),
+                                      cl::Required);
+static cl::opt<unsigned> Iterations("i", cl::desc("No iterations"),
+                                    cl::init(1));
+
+static cl::opt<bool> BDT("dt", cl::desc("Benchmark DT"));
+static cl::opt<bool> BPDT("pdt", cl::desc("Benchmark PDT"));
+
+static cl::opt<bool> Verify("verify", cl::desc("Verify correctness"),
+                            cl::init(false));
+static cl::opt<bool> Progress("progress", cl::desc("Show progress"));
+
+extern bool llvm::VerifyDomInfo;
+
+static std::unique_ptr<Module> GetModule(StringRef Filename) {
+  auto *Context = new LLVMContext();
+  SMDiagnostic Diags;
+  auto M = parseIRFile(InputFile, Diags, *Context);
+  if (!M)
+    Diags.print(InputFile.c_str(), errs());
+
+  return M;
+}
+
+template <typename F>
+std::chrono::microseconds Time(StringRef Desc, F Fun, int No = -1,
+                               int Total = -1) {
+  const auto StartTime = std::chrono::steady_clock::now();
+  Fun();
+  const auto EndTime = std::chrono::steady_clock::now();
+  const auto ElapsedMs = std::chrono::duration_cast<std::chrono::microseconds>(
+      EndTime - StartTime);
+
+  if (Progress) {
+    std::string Buff;
+    raw_string_ostream RSO(Buff);
+    RSO << '[' << No << '/' << Total << "]\t";
+    RSO << Desc << "\t" << ElapsedMs.count() << "\tus\n";
+    RSO.flush();
+    outs() << Buff;
+  }
+  return ElapsedMs;
+};
+
+static void RunOld(Module &M) {
+  const int NumFun = M.getFunctionList().size();
+  int current = -1;
+  std::chrono::microseconds TotalElapsed{0};
+  for (auto &F : M.getFunctionList()) {
+    if (F.getBasicBlockList().empty())
+      continue;
+
+    DEBUG(dbgs() << F.getName() << "\n");
+
+    TotalElapsed += Time("Old DT",
+                         [&] {
+                           DominatorTree DT(F);
+                         },
+                         ++current, NumFun);
+  }
+
+  outs() << "Old DT\t" << TotalElapsed.count() << "\tus\n";
+}
+
+static bool AreConnected(BasicBlock *A, BasicBlock *B) {
+  assert(A && B);
+  return llvm::find(successors(A), B) != succ_end(A);
+}
+
+static void RunBenchmark(Module& M) {
+  DEBUG(dbgs() << "Converting to CFG-only\n");
+  LLVMContext Context;
+  Module CFGM("benchmark", Context);
+  FunctionType *FTy = TypeBuilder<void(), false>::get(Context);
+
+  for (auto &F : M.functions()) {
+    auto *NF = cast<Function>(CFGM.getOrInsertFunction(F.getName(), FTy));
+
+    std::vector<CFGBuilder::Arc> Arcs;
+    std::vector<StringRef> BBNames;
+    std::vector<BasicBlock *> BBs;
+
+    for (BasicBlock &BB : F) {
+      BBs.push_back(&BB);
+      BBNames.push_back(BB.getName());
+      StringRef BBName = BB.getName();
+      for (auto *Succ : successors(&BB))
+        Arcs.push_back({BBName, Succ->getName()});
+    }
+
+    DenseSet<std::pair<BasicBlock *, BasicBlock *>> Enqueued;
+    std::vector<CFGBuilder::Update> Updates;
+
+    const size_t NumUpdates = 10;
+    while(Updates.size() < NumUpdates) {
+      BasicBlock *A;
+      BasicBlock *B;
+
+      //if (!Enqueued.count({}))
+    }
+
+
+    CFGBuilder Builder(NF, Arcs, {});
+    DEBUG(dbgs() << (NF->getName()) << "\n");
+  }
+}
+
+int main(int argc, char **argv) {
+  sys::PrintStackTraceOnErrorSignal(argv[0]);
+  PrettyStackTraceProgram X(argc, argv);
+  cl::ParseCommandLineOptions(argc, argv, "dominators");
+
+  auto M = GetModule(InputFile);
+  if (!M)
+    return 1;
+
+  outs() << "Bitcode read; module has " << M->getFunctionList().size()
+         << " functions\n";
+
+  VerifyDomInfo = Verify.getValue();
+  if (VerifyDomInfo)
+    outs() << "=== Verification on ===\n";
+
+  if (BDT) {
+    RunBenchmark(*M);
+  }
+  return 0;
+}