--- a/unittests/IR/DominatorTreeTest.cpp	Sun Dec 23 19:23:36 2018 +0900
+++ b/unittests/IR/DominatorTreeTest.cpp	Wed Aug 14 19:46:37 2019 +0900
@@ -1,14 +1,14 @@
 //===- 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.
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #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"
@@ -21,19 +21,17 @@
 
 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);
 }
 
@@ -75,7 +73,7 @@
   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++;
@@ -264,14 +262,14 @@
         EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);
 
         // Change root node
-        DT->verifyDomTree();
+        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);
-        DT->verifyDomTree();
+        EXPECT_TRUE(DT->verify());
       });
 }
 
@@ -295,14 +293,14 @@
   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();
+        const Instruction *TI = BB0->getTerminator();
         assert(TI->getNumSuccessors() == 3 && "Switch has three successors");
 
         BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0));
@@ -359,7 +357,7 @@
 // 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 =
@@ -379,7 +377,7 @@
   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++;
@@ -406,7 +404,7 @@
         DominatorTree NDT(F);
         EXPECT_EQ(DT->compare(NDT), 0);
 
-        PostDomTree NPDT(F);
+        PostDominatorTree NPDT(F);
         EXPECT_EQ(PDT->compare(NPDT), 0);
       });
 }
@@ -473,7 +471,7 @@
   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++;
@@ -498,7 +496,7 @@
         DominatorTree NDT(F);
         EXPECT_EQ(DT->compare(NDT), 0);
 
-        PostDomTree NPDT(F);
+        PostDominatorTree NPDT(F);
         EXPECT_EQ(PDT->compare(NPDT), 0);
       });
 }
@@ -562,7 +560,7 @@
   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++;
@@ -593,11 +591,80 @@
         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:
+//
+//          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;
@@ -621,7 +688,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;
@@ -647,7 +714,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();
@@ -675,7 +742,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;
@@ -696,7 +763,7 @@
 
   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();
@@ -708,7 +775,9 @@
   PDT.insertEdge(From, To);
   EXPECT_TRUE(PDT.verify());
   EXPECT_TRUE(PDT.getRoots().size() == 2);
-  EXPECT_NE(PDT.getNode(B.getOrAddBlock("5")), nullptr);
+  // 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) {
@@ -724,7 +793,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;
@@ -754,7 +823,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;
@@ -781,7 +850,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;
@@ -807,7 +876,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;
@@ -837,7 +906,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;
@@ -875,7 +944,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;