[Dominators] Add PDT constructor from Function

[NutshellySima]

Summary

This patch adds a PDT constructor from Function and lets codes previously using a local class to do this use PostDominatorTree class directly.

[kuhar]

We can also try to refactor other places in the codebase that first construct PDT and then immediately do PDT.recalculate(F).

unittests/IR/DominatorTreeBatchUpdatesTest.cpp

25 ↗

(On Diff #146166)

I think it would be better to replace all uses od PostDomTree with PostDominatorTree

unittests/IR/DominatorTreeTest.cpp

24 ↗

(On Diff #146166)

Same as above.

[NutshellySima]

1. Replace PostDomTree with PostDominatorTree in unittests.
2. Refactor codes that first construct PDT and do recalculation immediately in PostDominators.cpp.
3. Replace PostDomTreeBase<BasicBlock> with PostDominatorTree in lib/Transforms/IPO/SampleProfile.cpp.

[kuhar]

Looks almost ready -- I found only a couple of cosmetic issues. Once they are fix I can commit it for you.

lib/Transforms/IPO/SampleProfile.cpp

1369 ↗

(On Diff #148066)

I think we can construct it directly here, like:
new PostDominatorTree(F))

unittests/IR/DominatorTreeTest.cpp

29 ↗

(On Diff #148066)

This seems to exceed the 80-character line limit. Can you format you patch with clang-format-diff.py?

[NutshellySima]

1. Construct PostDominatorTree directly from Function in lib/Transforms/IPO/SampleProfile.cpp.
2. Format the patch.

[kuhar]

LGTM.

llvm/trunk/include/llvm/Analysis/PostDominators.h

 class raw_ostream;
 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the post-dominator tree.
 class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
 public:
   using Base = PostDomTreeBase<BasicBlock>;
 
+  PostDominatorTree() = default;
+  explicit PostDominatorTree(Function &F) { recalculate(F); }
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 };
 
 /// Analysis pass which computes a \c PostDominatorTree.
 class PostDominatorTreeAnalysis
     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {

llvm/trunk/lib/Analysis/PostDominators.cpp

 FunctionPass* llvm::createPostDomTree() {
   return new PostDominatorTreeWrapperPass();
 }
 
 AnalysisKey PostDominatorTreeAnalysis::Key;
 
 PostDominatorTree PostDominatorTreeAnalysis::run(Function &F,
                                                  FunctionAnalysisManager &) {
-  PostDominatorTree PDT;
-  PDT.recalculate(F);
+  PostDominatorTree PDT(F);
   return PDT;
 }
 
 PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS)
   : OS(OS) {}
 
 PreservedAnalyses
 PostDominatorTreePrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
   OS << "PostDominatorTree for function: " << F.getName() << "\n";
   AM.getResult<PostDominatorTreeAnalysis>(F).print(OS);
 
   return PreservedAnalyses::all();
 }

llvm/trunk/lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DiagnosticInfo.h"
protected:
   /// Map from function name to Function *. Used to find the function from
   /// the function name. If the function name contains suffix, additional
   /// entry is added to map from the stripped name to the function if there
   /// is one-to-one mapping.
   StringMap<Function *> SymbolMap;
 
   /// Dominance, post-dominance and loop information.
   std::unique_ptr<DominatorTree> DT;
-  std::unique_ptr<PostDomTreeBase<BasicBlock>> PDT;
+  std::unique_ptr<PostDominatorTree> PDT;
   std::unique_ptr<LoopInfo> LI;
 
   std::function<AssumptionCache &(Function &)> GetAC;
   std::function<TargetTransformInfo &(Function &)> GetTTI;
 
   /// Predecessors for each basic block in the CFG.
   BlockEdgeMap Predecessors;
 
F.getContext().diagnose(DiagnosticInfoSampleProfile(
       DS_Warning));
   return 0;
 }
 
 void SampleProfileLoader::computeDominanceAndLoopInfo(Function &F) {
   DT.reset(new DominatorTree);
   DT->recalculate(F);
 
-  PDT.reset(new PostDomTreeBase<BasicBlock>());
-  PDT->recalculate(F);
+  PDT.reset(new PostDominatorTree(F));
 
   LI.reset(new LoopInfo);
   LI->analyze(*DT);
 }
 
 /// Generate branch weight metadata for all branches in \p F.
 ///
 /// Branch weights are computed out of instruction samples using a

llvm/trunk/unittests/IR/DominatorTreeBatchUpdatesTest.cpp

 #define DEBUG_TYPE "batch-update-tests"
 
 using namespace llvm;
 
 namespace {
 const auto CFGInsert = CFGBuilder::ActionKind::Insert;
 const auto CFGDelete = CFGBuilder::ActionKind::Delete;
 
-struct PostDomTree : PostDomTreeBase<BasicBlock> {
-  PostDomTree(Function &F) { recalculate(F); }
-};
 
 using DomUpdate = DominatorTree::UpdateType;
 static_assert(
-    std::is_same<DomUpdate, PostDomTree::UpdateType>::value,
+    std::is_same<DomUpdate, PostDominatorTree::UpdateType>::value,
     "Trees differing only in IsPostDom should have the same update types");
 using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
 using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
 const auto Insert = DominatorTree::Insert;
 const auto Delete = DominatorTree::Delete;
 
 std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,
                                     std::vector<CFGBuilder::Update> &In) {

 }
 
 TEST(DominatorTreeBatchUpdates, SingleInsertion) {
   CFGHolder Holder;
   CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});
 
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   BasicBlock *B = Builder.getOrAddBlock("B");
   BasicBlock *C = Builder.getOrAddBlock("C");
   std::vector<DomUpdate> Updates = {{Insert, B, C}};
 
   ASSERT_TRUE(Builder.applyUpdate());
 
   DT.applyUpdates(Updates);
   EXPECT_TRUE(DT.verify());
   PDT.applyUpdates(Updates);
   EXPECT_TRUE(PDT.verify());
 }
 
 TEST(DominatorTreeBatchUpdates, SingleDeletion) {
   CFGHolder Holder;
   CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},
                      {{CFGDelete, {"B", "C"}}});
 
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   BasicBlock *B = Builder.getOrAddBlock("B");
   BasicBlock *C = Builder.getOrAddBlock("C");
   std::vector<DomUpdate> Updates = {{Delete, B, C}};
 
   ASSERT_TRUE(Builder.applyUpdate());
 
std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}},
                                                 {CFGInsert, {"C", "D"}},
                                                 {CFGInsert, {"D", "E"}}};
 
   CFGHolder Holder;
   CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);
 
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   BasicBlock *B = Builder.getOrAddBlock("B");
   BasicBlock *C = Builder.getOrAddBlock("C");
   BasicBlock *D = Builder.getOrAddBlock("D");
   BasicBlock *E = Builder.getOrAddBlock("E");
 
   std::vector<DomUpdate> Updates = {
TEST(DominatorTreeBatchUpdates, FewDeletions) {
 
   CFGHolder Holder;
   CFGBuilder Builder(
       Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},
       CFGUpdates);
 
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   auto Updates = ToDomUpdates(Builder, CFGUpdates);
 
   while (Builder.applyUpdate())
     ;
 
   DT.applyUpdates(Updates);
std::vector<CFGBuilder::Update> Updates = {
       {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
       {CFGDelete, {"3", "4"}},  {CFGDelete, {"8", "9"}},
       {CFGDelete, {"11", "12"}}};
 
   CFGHolder Holder;
   CFGBuilder B(Holder.F, Arcs, Updates);
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   while (B.applyUpdate())
     ;
 
   auto DomUpdates = ToDomUpdates(B, Updates);
   DT.applyUpdates(DomUpdates);
   EXPECT_TRUE(DT.verify());
TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
 
   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());
-    PostDomTree PDT(*Holder.F);
+    PostDominatorTree PDT(*Holder.F);
     EXPECT_TRUE(PDT.verify());
 
     while (B.applyUpdate())
       ;
 
     auto DomUpdates = ToDomUpdates(B, Updates);
     DT.applyUpdates(DomUpdates);
     EXPECT_TRUE(DT.verify());
TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
   // SplitBlock on 3 -> 5
   std::vector<CFGBuilder::Update> Updates = {
       {CFGInsert, {"N", "5"}},  {CFGInsert, {"3", "N"}}, {CFGDelete, {"3", "5"}}};
 
   CFGHolder Holder;
   CFGBuilder B(Holder.F, Arcs, Updates);
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   while (B.applyUpdate())
     ;
 
   auto DomUpdates = ToDomUpdates(B, Updates);
   DT.applyUpdates(DomUpdates);
   EXPECT_TRUE(DT.verify());
TEST(DominatorTreeBatchUpdates, DeadBlocks) {
   std::vector<CFGBuilder::Update> Updates = {
       {CFGDelete, {"6", "7"}},  {CFGDelete, {"5", "7"}}, {CFGDelete, {"5", "6"}},
       {CFGInsert, {"N", "8"}},  {CFGInsert, {"7", "N"}}, {CFGDelete, {"7", "8"}}};
 
   CFGHolder Holder;
   CFGBuilder B(Holder.F, Arcs, Updates);
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   while (B.applyUpdate())
     ;
 
   auto DomUpdates = ToDomUpdates(B, Updates);
   DT.applyUpdates(DomUpdates);
   EXPECT_TRUE(DT.verify());
TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
   // SplitBlock on 4 -> 6
   std::vector<CFGBuilder::Update> Updates = {
       {CFGInsert, {"N", "6"}},  {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};
 
   CFGHolder Holder;
   CFGBuilder B(Holder.F, Arcs, Updates);
   DominatorTree DT(*Holder.F);
   EXPECT_TRUE(DT.verify());
-  PostDomTree PDT(*Holder.F);
+  PostDominatorTree PDT(*Holder.F);
   EXPECT_TRUE(PDT.verify());
 
   while (B.applyUpdate())
     ;
 
   auto DomUpdates = ToDomUpdates(B, Updates);
   DT.applyUpdates(DomUpdates);
   EXPECT_TRUE(DT.verify());
   PDT.applyUpdates(DomUpdates);
   EXPECT_TRUE(PDT.verify());
 }

llvm/trunk/unittests/IR/DominatorTreeTest.cpp

 #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;
 
-struct PostDomTree : PostDomTreeBase<BasicBlock> {
-  PostDomTree(Function &F) { recalculate(F); }
-};
 
 /// 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, PostDomTree *PDT)> Test) {
+    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);
-  PostDomTree PDT(*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?");
StringRef ModuleString =
       "  ret void\n"
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+      *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++;
 
StringRef ModuleString =
       "   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, PostDomTree *PDT) {
+      *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
         Function::iterator FI = F.begin();
 
         BasicBlock *BB0 = &*FI++;
         BasicBlock *BB1 = &*FI++;
         BasicBlock *BB2 = &*FI++;
 
         const TerminatorInst *TI = BB0->getTerminator();
         assert(TI->getNumSuccessors() == 3 && "Switch has three successors");

 //           | \                   |
 //           v  \                  A
 //          /    D
 //         C      \
 //         |       \
 // unreachable    Exit
 //
 // Both the blocks that end with ret and with unreachable become trivial
-// PostDomTree roots, as they have no successors.
+// 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, PostDomTree *PDT) {
+      *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)));
runWithDomTree(
         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);
 
-        PostDomTree NPDT(F);
+        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.
 //
StringRef ModuleString =
       "  ret void\n"
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+      *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);
 
-        PostDomTree NPDT(F);
+        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:
StringRef ModuleString =
       "  ret void\n"
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+      *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++;
 
runWithDomTree(
         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);
 
-        PostDomTree NPDT(F);
+        PostDominatorTree NPDT(F);
         EXPECT_EQ(PDT->compare(NPDT), 0);
       });
 }
 
 // Verify that the IDF returns blocks in a deterministic way.
 //
 // Test case:
 //
StringRef ModuleString =
       "  ret void\n"
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+      *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;
TEST(DominatorTree, InsertReachable) {
 
   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());
-  PostDomTree PDT(*Holder.F);
+  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);
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());
-  PostDomTree PDT(*Holder.F);
+  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);
TEST(DominatorTree, InsertUnreachable) {
 
   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());
-  PostDomTree PDT(*Holder.F);
+  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);
-  PostDomTree PDT(*Holder.F);
+  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);
TEST(DominatorTree, InsertMixed) {
 
   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());
-  PostDomTree PDT(*Holder.F);
+  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);
std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "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());
-    PostDomTree PDT(*Holder.F);
+    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);
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());
-  PostDomTree PDT(*Holder.F);
+  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);
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());
-  PostDomTree PDT(*Holder.F);
+  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);
std::vector<CFGBuilder::Update> Updates = {
       {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());
-  PostDomTree PDT(*Holder.F);
+  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);
TEST(DominatorTree, InsertDeleteExhaustive) {
 
   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());
-    PostDomTree PDT(*Holder.F);
+    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);