[RFC] Make infinite loops available in postdom tree, but do not connect them to the reverse reachable part of the CFG

[grosser]

Summary

This patch is not intended for submission, but to illustrate my comments in
https://reviews.llvm.org/D35851. Please use D35851 for the discussion.

The difference to D35851 is that we connect unreachable parts to the CFG, but
that we disconnect these very parts from the reachable part of the CFG. As
such, they do not affect the dominance relations in the reachable part of the
CFG, but are still modeled in the PDT.

[kuhar]

Marking it so that it doesn't take place in my to-review queue.

include/llvm/IR/Dominators.h

 
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/GenericDomTree.h"
 #include <utility>
 
 namespace llvm {
 
 class Function;
 class Instruction;
 class Module;
 class raw_ostream;
 
 extern template class DomTreeNodeBase<BasicBlock>;
 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
 
 namespace DomTreeBuilder {
+template <typename T>
+struct ExitChecker;
+/// Basic blocks that end with a return statement are exit basic blocks. Basic
+/// blocks that end with an unreachable instructions or basic blocks that belong
+/// to an infinite loop may be backward unreachable and may consequently become
+/// virtual exit nodes. Virtual exit nodes are not identified as graph exits
+/// to allow the easy differentiation between virtual exit nodes and graph
+/// exit nodes.
+template <>
+struct ExitChecker<BasicBlock*> {
+  static bool IsGraphExit(const BasicBlock *N) {
+  assert(N && "N must be a valid node");
+  return isa<ReturnInst>(N->getTerminator());
+}
+};
 using BBDomTree = DomTreeBase<BasicBlock>;
 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
 
 extern template void Calculate<BBDomTree>(BBDomTree &DT);
 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
 
 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);

include/llvm/Support/GenericDomTree.h

#endif
   bool dominates(const NodeT *A, const NodeT *B) const;
 
   NodeT *getRoot() const {
     assert(this->Roots.size() == 1 && "Should always have entry node!");
     return this->Roots[0];
   }
 
   /// findNearestCommonDominator - Find nearest common dominator basic block
-  /// for basic block A and B. If there is no such block then return NULL.
+  /// for basic block A and B. If there is no such block then return nullptr.
   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
+    assert(A && B && "Pointers are not valid");
     assert(A->getParent() == B->getParent() &&
            "Two blocks are not in same function");
 
     // If either A or B is a entry block then it is nearest common dominator
     // (for forward-dominators).
-    if (!this->isPostDominator()) {
+    if (!isPostDominator()) {
       NodeT &Entry = A->getParent()->front();
       if (A == &Entry || B == &Entry)
         return &Entry;
     }
 
     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
 
void splitBlock(NodeT *NewBB) {
     else
       Split<NodeT *>(NewBB);
   }
 
   /// print - Convert to human readable form
   ///
   void print(raw_ostream &O) const {
     O << "=============================--------------------------------\n";
-    if (this->isPostDominator())
+    if (IsPostDominator)
       O << "Inorder PostDominator Tree: ";
     else
       O << "Inorder Dominator Tree: ";
     if (!DFSInfoValid)
       O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
     O << "\n";
 
     // The postdom tree can have a null root if there are no returns.
     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
+    if (IsPostDominator) {
+      O << "Roots: ";
+      for (const NodePtr Block : Roots) {
+        Block->printAsOperand(O, false);
+        O << " ";
+      }
+      O << "\n";
+    }
   }
 
 public:
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
   /// dominator tree in dfs order.
   void updateDFSNumbers() const {
     if (DFSInfoValid) {
       SlowQueries = 0;

include/llvm/Support/GenericDomTreeConstruction.h

 
 template <typename NodePtr>
 struct ChildrenGetter<NodePtr, true> {
   static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) {
     return inverse_children<NodePtr>(N);
   }
 };
 
+// For postdominators and without further information, nodes with no forward
+// successors are trivial roots that are always selected as tree roots. Roots
+// with forward successors correspond to CFG nodes within infinite loops and
+// cannot be identified easily as exit nodes of the graph, but must be found
+// via a DFS search.
+//
+// By specializing this function, it is possible to further refine the set of
+// forward successor free roots, e.g., by distinguishing between real exit
+// nodes and unreachable nodes.
+template <typename NodePtr>
+struct ExitChecker {
+  static bool IsGraphExit(const NodePtr N) {
+  assert(N && "N must be a valid node");
+  using TraitsTy = GraphTraits<NodePtr>;
+  return TraitsTy::child_begin(N) == TraitsTy::child_end(N);
+}
+};
+
 template <typename DomTreeT>
 struct SemiNCAInfo {
   using NodePtr = typename DomTreeT::NodePtr;
   using NodeT = typename DomTreeT::NodeType;
   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
+  using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
     unsigned DFSNum = 0;
     unsigned Parent = 0;
     unsigned Semi = 0;
     NodePtr Label = nullptr;
     NodePtr IDom = nullptr;
     SmallVector<NodePtr, 2> ReverseChildren;
   };
 
+  // The DFS number after which only "unreachable" nodes are processed.
+  unsigned UnreachableMinDFS;
+
   // Number to node mapping is 1-based. Initialize the mapping to start with
   // a dummy element.
   std::vector<NodePtr> NumToNode = {nullptr};
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
   void clear() {
     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
     NodeToInfo.clear();
friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
 
       return O;
     }
   };
 
   // Custom DFS implementation which can skip nodes based on a provided
   // predicate. It also collects ReverseChildren so that we don't have to spend
   // time getting predecessors in SemiNCA.
-  template <typename DescendCondition>
+  //
+  // If IsReverse is set to true, the DFS walk will be performed backwards
+  // relative to IsPostDom -- using reverse edges for dominators and forward
+  // edges for postdominators.
+  template <bool IsReverse = false, typename DescendCondition>
   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
                   unsigned AttachToNum) {
     assert(V);
     SmallVector<NodePtr, 64> WorkList = {V};
     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
 
     while (!WorkList.empty()) {
       const NodePtr BB = WorkList.pop_back_val();
       auto &BBInfo = NodeToInfo[BB];
 
       // Visited nodes always have positive DFS numbers.
       if (BBInfo.DFSNum != 0) continue;
       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
       NumToNode.push_back(BB);
 
-      for (const NodePtr Succ : ChildrenGetter<NodePtr, IsPostDom>::Get(BB)) {
+      constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
+      for (const NodePtr Succ : ChildrenGetter<NodePtr, Direction>::Get(BB)) {
         const auto SIT = NodeToInfo.find(Succ);
         // Don't visit nodes more than once but remember to collect
         // RerverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }
 
for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
         if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
           continue;
 
         const TreeNodePtr TN = DT.getNode(N);
         // Skip predecessors whose level is above the subtree we are processing.
         if (TN && TN->getLevel() < MinLevel)
           continue;
 
-        unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
+        auto &NInfo = NodeToInfo[eval(N, i + 1)];
+
+        if (NInfo.DFSNum >= UnreachableMinDFS &&
+            WInfo.DFSNum < UnreachableMinDFS)
+          continue;
+
+        unsigned SemiU = NInfo.Semi;
         if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
       }
     }
 
     // Step #2: Explicitly define the immediate dominator of each vertex.
     //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
     // Note that the parents were stored in IDoms and later got invalidated
     // during path compression in Eval.
     for (unsigned i = 2; i < NextDFSNum; ++i) {
       const NodePtr W = NumToNode[i];
       auto &WInfo = NodeToInfo[W];
       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
       NodePtr WIDomCandidate = WInfo.IDom;
       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
 
       WInfo.IDom = WIDomCandidate;
     }
   }
 
-  template <typename DescendCondition>
-  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
-    unsigned Num = 0;
+  // PostDominatorTree always has a virtual root that represents a virtual CFG
+  // node that serves as a single exit from the function. All the other exits
+  // (CFG nodes with termninators and nodes in infinite loops are logically
+  // connected to this virtual CFG exit node).
+  // This functions maps a nullptr CFG node to the virtual root tree node.
+  void addVirtualRoot() {
+    assert(IsPostDom && "Only postdominators have a virtual root");
+    assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
 
-    // If the DT is a PostDomTree, always add a virtual root.
-    if (IsPostDom) {
-      auto &BBInfo = NodeToInfo[nullptr];
-      BBInfo.DFSNum = BBInfo.Semi = ++Num;
-      BBInfo.Label = nullptr;
+    BBInfo.DFSNum = BBInfo.Semi = 1;
 
-      NumToNode.push_back(nullptr);  // NumToNode[n] = V;
-    }
+    NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;
 
-    const unsigned InitialNum = Num;
-    for (auto *Root : DT.Roots) Num = runDFS(Root, Num, DC, InitialNum);
+  // For postdominators, nodes with no forward successors are trivial roots that
+  // are always selected as tree roots. Roots with forward successors correspond
+  // to CFG nodes within infinite loops.
+  static bool IsGraphExit(const NodePtr N) {
+    return ExitChecker<NodePtr>::IsGraphExit(N);
+  }
 
-    return Num;
+  static NodePtr GetEntryNode(const DomTreeT &DT) {
+    assert(DT.Parent && "Parent not set");
+    return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
   }
 
-  static void FindAndAddRoots(DomTreeT &DT) {
+  // Finds all roots without relaying on the set of roots already stored in the
+  // tree.
+  // We define roots to be some non-redundant set of the CFG nodes
+  static RootsT FindRoots(const DomTreeT &DT,
+                          unsigned *UnreachableMinDFS = nullptr) {
     assert(DT.Parent && "Parent pointer is not set");
-    using TraitsTy = GraphTraits<typename DomTreeT::ParentPtr>;
+    RootsT Roots;
+
+    // For dominators, function entry CFG node is always a tree root node.
+    if (!IsPostDom) {
+      Roots.push_back(GetEntryNode(DT));
+      if (UnreachableMinDFS)
+        *UnreachableMinDFS = std::numeric_limits<unsigned>::max();
+      return Roots;
+    }
+
+    SemiNCAInfo SNCA;
+
+    // PostDominatorTree always has a virtual root.
+    SNCA.addVirtualRoot();
+    unsigned Num = 1;
+
+    DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
+
+    // Step #1: Find all the trivial roots that are going to will definitely
+    // remain tree roots.
+    unsigned Total = 0;
+    for (const NodePtr N : nodes(DT.Parent)) {
+      ++Total;
+      // If it has no *successors*, it is definitely a root.
+      if (IsGraphExit(N)) {
+        Roots.push_back(N);
+        // Run DFS not to walk this part of CFG later.
+        Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
+        DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
+                     << "\n");
+        DEBUG(dbgs() << "Last visited node: "
+                     << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
+      }
+    }
+
+    if (UnreachableMinDFS)
+      *UnreachableMinDFS = Num + 1;
+    DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
+
+    // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
+    // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
+    // nodes in infinite loops).
+    bool HasNonTrivialRoots = false;
+    // Accounting for the virtual exit, see if we had any reverse-unreachable
+    // nodes.
+    if (Total + 1 != Num) {
+      HasNonTrivialRoots = true;
+      // Make another DFS pass over all other nodes to find the
+      // reverse-unreachable blocks, and find the furthest paths we'll be able
+      // to make.
+      // Note that this looks N^2, but it's really 2N worst case, if every node
+      // is unreachable. This is because we are still going to only visit each
+      // unreachable node once, we may just visit it in two directions,
+      // depending on how lucky we get.
+      SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
+      for (const NodePtr I : nodes(DT.Parent)) {
+        if (SNCA.NodeToInfo.count(I) == 0) {
+          DEBUG(dbgs() << "\t\t\tVisiting node " << BlockNamePrinter(I)
+                       << "\n");
+          // Find the furthest away we can get by following successors, then
+          // follow them in reverse.  This gives us some reasonable answer about
+          // the post-dom tree inside any infinite loop. In particular, it
+          // guarantees we get to the farthest away point along *some*
+          // path. This also matches the GCC's behavior.
+          // If we really wanted a totally complete picture of dominance inside
+          // this infinite loop, we could do it with SCC-like algorithms to find
+          // the lowest and highest points in the infinite loop.  In theory, it
+          // would be nice to give the canonical backedge for the loop, but it's
+          // expensive and does not always lead to a minimal set of roots.
+          DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
+
+          const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
+          const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
+          DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
+                       << "(non-trivial root): "
+                       << BlockNamePrinter(FurthestAway) << "\n");
+          ConnectToExitBlock.insert(FurthestAway);
+          Roots.push_back(FurthestAway);
+          DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
+                       << NewNum << "\n\t\t\tRemoving DFS info\n");
+          for (unsigned i = NewNum; i > Num; --i) {
+            const NodePtr N = SNCA.NumToNode[i];
+            DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
+                         << BlockNamePrinter(N) << "\n");
+            SNCA.NodeToInfo.erase(N);
+            SNCA.NumToNode.pop_back();
+          }
+          const unsigned PrevNum = Num;
+          DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
+          Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
+          for (unsigned i = PrevNum + 1; i <= Num; ++i)
+            DEBUG(dbgs() << "\t\t\t\tfound node "
+                         << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
+        }
+      }
+    }
+
+    DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
+    DEBUG(dbgs() << "Discovered CFG nodes:\n");
+    DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
+          << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
+
+    assert((Total + 1 == Num) && "Everything should have been visited");
+
+    // Step #3: If we found some non-trivial roots, make them non-redundant.
+    if (HasNonTrivialRoots) RemoveRedundantRoots(DT, Roots);
+
+    DEBUG(dbgs() << "Found roots: ");
+    DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " ");
+    DEBUG(dbgs() << "\n");
+
+    return Roots;
+  }
+
+  // This function only makes sense for postdominators.
+  // We define roots to be some set of CFG nodes where (reverse) DFS walks have
+  // to start in order to visit all the CFG nodes (including the
+  // reverse-unreachable ones).
+  // When the search for non-trivial roots is done it may happen that some of
+  // the non-trivial roots are reverse-reachable from other non-trivial roots,
+  // which makes them redundant. This function removes them from the set of
+  // input roots.
+  static void RemoveRedundantRoots(const DomTreeT &DT, RootsT &Roots) {
+    assert(IsPostDom && "This function is for postdominators only");
+    DEBUG(dbgs() << "Removing redundant roots\n");
+
+    SemiNCAInfo SNCA;
+
+    for (unsigned i = 0; i < Roots.size(); ++i) {
+      auto &Root = Roots[i];
+      // Trivial roots are always non-redundant.
+      if (IsGraphExit(Root)) continue;
+      DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
+                   << " remains a root\n");
+      SNCA.clear();
+      // Do a forward walk looking for the other roots.
+      const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
+      // Skip the start node and begin from the second one (note that DFS uses
+      // 1-based indexing).
+      for (unsigned x = 2; x <= Num; ++x) {
+        const NodePtr N = SNCA.NumToNode[x];
+        // If we wound another root in a (forward) DFS walk, remove the current
+        // root from the set of roots, as it is reverse-reachable from the other
+        // one.
+        if (llvm::find(Roots, N) != Roots.end()) {
+          DEBUG(dbgs() << "\tForward DFS walk found another root "
+                       << BlockNamePrinter(N) << "\n\tRemoving root "
+                       << BlockNamePrinter(Root) << "\n");
+          std::swap(Root, Roots.back());
+          Roots.pop_back();
+
+          // Root at the back takes the current root's place.
+          // Start the next loop iteration with the same index.
+          --i;
+          break;
+        }
+      }
+    }
+  }
 
+  template <typename DescendCondition>
+  void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     if (!IsPostDom) {
-      // Dominators have a single root that is the function's entry.
-      NodeT *entry = TraitsTy::getEntryNode(DT.Parent);
-      DT.addRoot(entry);
-    } else {
-      // Initialize the roots list for PostDominators.
-      for (auto *Node : nodes(DT.Parent))
-        if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
-          DT.addRoot(Node);
+      assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
+      runDFS(DT.Roots[0], 0, DC, 0);
+      return;
     }
+
+    addVirtualRoot();
+    unsigned Num = 1;
+    for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
   }
 
   void calculateFromScratch(DomTreeT &DT) {
     // Step #0: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
-    FindAndAddRoots(DT);
+    DT.Roots = FindRoots(DT, &UnreachableMinDFS);
     doFullDFSWalk(DT, AlwaysDescend);
 
     runSemiNCA(DT);
 
     if (DT.Roots.empty()) return;
 
     // Add a node for the root. If the tree is a PostDominatorTree it will be
     // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
       DEBUG(dbgs() << "\tdiscovered a new reachable node "
                    << BlockNamePrinter(W) << "\n");
 
       // Don't replace this with 'count', the insertion side effect is important
       if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
 
       NodePtr ImmDom = getIDom(W);
 
-      // Get or calculate the node for the immediate dominator
+      // Get or calculate the node for the immediate dominator.
       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 
       // Add a new tree node for this BasicBlock, and link it as a child of
-      // IDomNode
+      // IDomNode.
       DT.DomTreeNodes[W] = IDomNode->addChild(
           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     }
   }
 
   void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
         Bucket;  // Queue of tree nodes sorted by level in descending order.
     SmallDenseSet<TreeNodePtr, 8> Affected;
     SmallDenseSet<TreeNodePtr, 8> Visited;
     SmallVector<TreeNodePtr, 8> AffectedQueue;
     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
   };
 
   static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
-    assert(From && To && "Cannot connect nullptrs");
+    assert((From || IsPostDom) &&
+           "From has to be a valid CFG node or a virtual root");
+    assert(To && "Cannot be a nullptr");
     DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
                  << BlockNamePrinter(To) << "\n");
-    const TreeNodePtr FromTN = DT.getNode(From);
+    TreeNodePtr FromTN = DT.getNode(From);
 
-    // Ignore edges from unreachable nodes.
-    if (!FromTN) return;
+    if (!FromTN) {
+      // Ignore edges from unreachable nodes for (forward) dominators.
+      if (!IsPostDom) return;
+
+      // The unreachable node becomes a new root -- a tree node for it.
+      TreeNodePtr VirtualRoot = DT.getNode(nullptr);
+      FromTN =
+          (DT.DomTreeNodes[From] = VirtualRoot->addChild(
+               llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
+              .get();
+      DT.Roots.push_back(From);
+    }
 
     DT.DFSInfoValid = false;
 
     const TreeNodePtr ToTN = DT.getNode(To);
     if (!ToTN)
       InsertUnreachable(DT, FromTN, To);
     else
       InsertReachable(DT, FromTN, ToTN);
   }
 
+  // Determines if some existing root becomes reverse-reachable after the
+  // insertion. Rebuilds the whole tree if that situation happens.
+  static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const TreeNodePtr From,
+                                         const TreeNodePtr To) {
+    assert(IsPostDom && "This function is only for postdominators");
+    // Destination node is not attached to the virtual root, so it cannot be a
+    // root.
+    if (!DT.isVirtualRoot(To->getIDom())) return false;
+
+    auto RIt = llvm::find(DT.Roots, To->getBlock());
+    if (RIt == DT.Roots.end())
+      return false;  // To is not a root, nothing to update.
+
+    DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
+                 << " is no longer a root\n\t\tRebuilding the tree!!!\n");
+
+    DT.recalculate(*DT.Parent);
+    return true;
+  }
+
+  // Updates the set of roots after insertion or deletion. This ensures that
+  // roots are the same when after a series of updates and when the tree would
+  // be built from scratch.
+  static void UpdateRootsAfterUpdate(DomTreeT &DT) {
+    assert(IsPostDom && "This function is only for postdominators");
+
+    // The tree has only trivial roots -- nothing to update.
+    if (std::all_of(DT.Roots.begin(), DT.Roots.end(), IsGraphExit))
+      return;
+
+    // Recalculate the set of roots.
+    DT.Roots = FindRoots(DT);
+    for (const NodePtr R : DT.Roots) {
+      const TreeNodePtr TN = DT.getNode(R);
+      // A CFG node was selected as a tree root, but the corresponding tree node
+      // is not connected to the virtual root. This is because the incremental
+      // algorithm does not really know or use the set of roots and can make a
+      // different (implicit) decision about which nodes within an infinite loop
+      // becomes a root.
+      if (DT.isVirtualRoot(TN->getIDom())) {
+        DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
+                     << " is not virtual root's child\n"
+                     << "The entire tree needs to be rebuilt\n");
+        // It should be possible to rotate the subtree instead of recalculating
+        // the whole tree, but this situation happens extremely rarely in
+        // practice.
+        DT.recalculate(*DT.Parent);
+        return;
+      }
+    }
+  }
+
   // Handles insertion to a node already in the dominator tree.
   static void InsertReachable(DomTreeT &DT, const TreeNodePtr From,
                               const TreeNodePtr To) {
     DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
                  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
+    if (IsPostDom && UpdateRootsBeforeInsertion(DT, From, To)) return;
+    // DT.findNCD expects both pointers to be valid. When From is a virtual
+    // root, then its CFG block pointer is a nullptr, so we have to 'compute'
+    // the NCD manually.
     const NodePtr NCDBlock =
-        DT.findNearestCommonDominator(From->getBlock(), To->getBlock());
+        (From->getBlock() && To->getBlock())
+            ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
+            : nullptr;
     assert(NCDBlock || DT.isPostDominator());
     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     assert(NCD);
 
     DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
     const TreeNodePtr ToIDom = To->getIDom();
 
     // Nothing affected -- NCA property holds.
static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD,
 
     for (const TreeNodePtr TN : II.AffectedQueue) {
       DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
                    << ") = " << BlockNamePrinter(NCD) << "\n");
       TN->setIDom(NCD);
     }
 
     UpdateLevelsAfterInsertion(II);
+    if (IsPostDom) UpdateRootsAfterUpdate(DT);
   }
 
   static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
     DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n");
 
     for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
       DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
                    << BlockNamePrinter(TN->getIDom()) << ") "
static void ComputeUnreachableDominators(
     SNCA.runDFS(Root, 0, UnreachableDescender, 0);
     SNCA.runSemiNCA(DT);
     SNCA.attachNewSubtree(DT, Incoming);
 
     DEBUG(dbgs() << "After adding unreachable nodes\n");
     DEBUG(DT.print(dbgs()));
   }
 
-  // Checks if the tree contains all reachable nodes in the input graph.
-  bool verifyReachability(const DomTreeT &DT) {
-    clear();
-    doFullDFSWalk(DT, AlwaysDescend);
-
-    for (auto &NodeToTN : DT.DomTreeNodes) {
-      const TreeNodePtr TN = NodeToTN.second.get();
-      const NodePtr BB = TN->getBlock();
-
-      // Virtual root has a corresponding virtual CFG node.
-      if (DT.isVirtualRoot(TN)) continue;
-
-      if (NodeToInfo.count(BB) == 0) {
-        errs() << "DomTree node " << BlockNamePrinter(BB)
-               << " not found by DFS walk!\n";
-        errs().flush();
-
-        return false;
-      }
-    }
-
-    for (const NodePtr N : NumToNode) {
-      if (N && !DT.getNode(N)) {
-        errs() << "CFG node " << BlockNamePrinter(N)
-               << " not found in the DomTree!\n";
-        errs().flush();
-
-        return false;
-      }
-    }
-
-    return true;
-  }
-
   static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
     assert(From && To && "Cannot disconnect nullptrs");
     DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
                  << BlockNamePrinter(To) << "\n");
 
 #ifndef NDEBUG
     // Ensure that the edge was in fact deleted from the CFG before informing
     // the DomTree about it.
DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
                  << BlockNamePrinter(ToIDom) << "\n");
 
     // To remains reachable after deletion.
     // (Based on the caption under Figure 4. from the second paper.)
     if (FromTN != ToIDom || HasProperSupport(DT, ToTN))
       DeleteReachable(DT, FromTN, ToTN);
     else
       DeleteUnreachable(DT, ToTN);
+
+    if (IsPostDom) UpdateRootsAfterUpdate(DT);
   }
 
   // Handles deletions that leave destination nodes reachable.
   static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
                               const TreeNodePtr ToTN) {
     DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
                  << BlockNamePrinter(ToTN) << "\n");
     DEBUG(dbgs() << "\tRebuilding subtree\n");
#endif
   // Handle deletions that make destination node unreachable.
   // (Based on the lemma 2.7 from the second paper.)
   static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
     DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
                  << "\n");
     assert(ToTN);
     assert(ToTN->getBlock());
 
+    if (IsPostDom) {
+      // Deletion makes a region reverse-unreachable and creates a new root.
+      // Simulate that by inserting an edge from the virtual root to ToTN and
+      // adding it as a new root.
+      DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
+      InsertReachable(DT, DT.getNode(nullptr), ToTN);
+      DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n");
+      DT.Roots.push_back(ToTN->getBlock());
+      return;
+    }
+
     SmallVector<NodePtr, 16> AffectedQueue;
     const unsigned Level = ToTN->getLevel();
 
     // Traverse destination node's descendants with greater level in the tree
     // and collect visited nodes.
     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
       const TreeNodePtr TN = DT.getNode(To);
       assert(TN);
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
 
     DT.DomTreeNodes.erase(TN->getBlock());
   }
 
   //~~
   //===--------------- DomTree correctness verification ---------------------===
   //~~
 
+  // Check if the tree has correct roots. A DominatorTree always has a single
+  // root which is the function's entry node. A PostdDominatorTree can have
+  // multiple roots - one for each node with no successors and for infinite
+  // loops.
+  bool verifyRoots(const DomTreeT &DT) {
+    if (!DT.Parent && !DT.Roots.empty()) {
+      errs() << "Tree has no parent but has roots!\n";
+      errs().flush();
+      return false;
+    }
+
+    if (!IsPostDom) {
+      if (DT.Roots.empty()) {
+        errs() << "Tree doesn't have a root!\n";
+        errs().flush();
+        return false;
+      }
+
+      if (DT.getRoot() != GetEntryNode(DT)) {
+        errs() << "Tree's root is not its parent's entry node!\n";
+        errs().flush();
+        return false;
+      }
+    }
+
+    RootsT ComputedRoots = FindRoots(DT);
+    if (DT.Roots.size() != ComputedRoots.size() ||
+        !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
+                             ComputedRoots.begin())) {
+      errs() << "Tree has different roots than freshly computed ones!\n";
+      errs() << "\tPDT roots: ";
+      for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
+      errs() << "\n\tComputed roots: ";
+      for (const NodePtr N : ComputedRoots)
+        errs() << BlockNamePrinter(N) << ", ";
+      errs() << "\n";
+      errs().flush();
+      return false;
+    }
+
+    return true;
+  }
+
+  // Checks if the tree contains all reachable nodes in the input graph.
+  bool verifyReachability(const DomTreeT &DT) {
+    clear();
+    doFullDFSWalk(DT, AlwaysDescend);
+
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+
+      // Virtual root has a corresponding virtual CFG node.
+      if (DT.isVirtualRoot(TN)) continue;
+
+      if (NodeToInfo.count(BB) == 0) {
+        errs() << "DomTree node " << BlockNamePrinter(BB)
+               << " not found by DFS walk!\n";
+        errs().flush();
+
+        return false;
+      }
+    }
+
+    for (const NodePtr N : NumToNode) {
+      if (N && !DT.getNode(N)) {
+        errs() << "CFG node " << BlockNamePrinter(N)
+               << " not found in the DomTree!\n";
+        errs().flush();
+
+        return false;
+      }
+    }
+
+    return true;
+  }
+
   // Check if for every parent with a level L in the tree all of its children
   // have level L + 1.
   static bool VerifyLevels(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
       if (!BB) continue;
 
#endif
 
   // Checks if the tree has the parent property: if for all edges from V to W in
   // the input graph, such that V is reachable, the parent of W in the tree is
   // an ancestor of V in the tree.
   //
   // This means that if a node gets disconnected from the graph, then all of
   // the nodes it dominated previously will now become unreachable.
   bool verifyParentProperty(const DomTreeT &DT) {
+    auto &Roots = DT.Roots;
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
       if (!BB || TN->getChildren().empty()) continue;
 
+      DEBUG(dbgs() << "Verifying parrent property of node "
+                   << BlockNamePrinter(TN) << "\n");
       clear();
-      doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
+      doFullDFSWalk(DT, [BB, Roots](NodePtr From, NodePtr To) {
+        // Exclude anything that is backwards unreachable.
+        for (auto Root : Roots)
+          if (From == Root && !IsGraphExit(Root))
+            return false;
         return From != BB && To != BB;
       });
 
       for (TreeNodePtr Child : TN->getChildren())
         if (NodeToInfo.count(Child->getBlock()) != 0) {
           errs() << "Child " << BlockNamePrinter(Child)
                  << " reachable after its parent " << BlockNamePrinter(BB)
                  << " is removed!\n";
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To) {
   if (DT.isPostDominator()) std::swap(From, To);
   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, From, To);
 }
 
 template <class DomTreeT>
 bool Verify(const DomTreeT &DT) {
   SemiNCAInfo<DomTreeT> SNCA;
-  return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
-         SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
-         SNCA.verifySiblingProperty(DT);
+  return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
+         SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) &&
+         SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif

lib/Transforms/Scalar/ADCE.cpp

for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {
         if (State.onStack(Succ)) {
           // back edge....
           markLive(Term);
           break;
         }
     }
   }
 
-  // Mark blocks live if there is no path from the block to the
-  // return of the function or a successor for which this is true.
-  // This protects IDFCalculator which cannot handle such blocks.
-  for (auto &BBInfoPair : BlockInfo) {
-    auto &BBInfo = BBInfoPair.second;
-    if (BBInfo.terminatorIsLive())
-      continue;
-    auto *BB = BBInfo.BB;
-    if (!PDT.getNode(BB)) {
-      DEBUG(dbgs() << "Not post-dominated by return: " << BB->getName()
+  // Mark blocks live if there is no path from the block to a
+  // return of the function.
+  // We do this by seeing which of the postdomtree root children exit the
+  // program, and for all others, mark the subtree live.
+  for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
+    auto *BB = PDTChild->getBlock();
+    auto &Info = BlockInfo[BB];
+    // Real function return
+    if (isa<ReturnInst>(Info.Terminator)) {
+      DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()
                    << '\n';);
-      markLive(BBInfo.Terminator);
       continue;
     }
-    for (auto *Succ : successors(BB))
-      if (!PDT.getNode(Succ)) {
-        DEBUG(dbgs() << "Successor not post-dominated by return: "
-                     << BB->getName() << '\n';);
-        markLive(BBInfo.Terminator);
-        break;
-      }
+
+    // This child is something else, like an infinite loop.
+    for (auto DFNode : depth_first(PDTChild)) {
+      markLive(BlockInfo[DFNode->getBlock()].Terminator);
+      for (auto *Pred : predecessors(DFNode->getBlock()))
+        markLive(BlockInfo[Pred].Terminator);
   }
 
   // Treat the entry block as always live
   auto *BB = &F.getEntryBlock();
   auto &EntryInfo = BlockInfo[BB];
   EntryInfo.Live = true;
   if (EntryInfo.UnconditionalBranch)
     markLive(EntryInfo.Terminator);

test/Analysis/PostDominators/pr6047_a.ll

 ; RUN: opt < %s -postdomtree -analyze | FileCheck %s
 define internal void @f() {
 entry:
   br i1 undef, label %bb35, label %bb3.i
 
 bb3.i:
   br label %bb3.i
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [3] %entry
+;CHECK:Inorder PostDominator Tree:
+;CHECK-NEXT:  [1]  <<exit node>>
+;CHECK-NEXT:    [2] %bb35
+;CHECK-NEXT:      [3] %entry
+;CHECK-NEXT:      [3] %bb35.loopexit3
+;CHECK-NEXT:    [2] %bb3.i

test/Analysis/PostDominators/pr6047_b.ll

 
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [4] %entry
+; CHECK: Inorder PostDominator Tree:
+; CHECK-NEXT:   [1]  <<exit node>>
+; CHECK-NEXT:     [2] %bb35
+; CHECK-NEXT:       [3] %a
+; CHECK-NEXT:         [4] %entry
+; CHECK-NEXT:       [3] %bb35.loopexit3
+; CHECK-NEXT:     [2] %bb3.i

test/Analysis/PostDominators/pr6047_c.ll

bb35.loopexit:
   br label %bb35
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [3] %entry
+
+; CHECK: Inorder PostDominator Tree:
+; CHECK-NEXT:   [1]  <<exit node>>
+; CHECK-NEXT:     [2] %bb35
+; CHECK-NEXT:       [3] %entry
+; CHECK-NEXT:       [3] %bb
+; CHECK-NEXT:       [3] %bb.i
+; CHECK-NEXT:       [3] %_float32_unpack.exit
+; CHECK-NEXT:       [3] %bb.i5
+; CHECK-NEXT:       [3] %_float32_unpack.exit8
+; CHECK-NEXT:       [3] %bb32.preheader
+; CHECK-NEXT:       [3] %bb3
+; CHECK-NEXT:       [3] %bb3.split.us
+; CHECK-NEXT:       [3] %bb.i4.us
+; CHECK-NEXT:       [3] %bb7.i.us
+; CHECK-NEXT:       [3] %bb.i4.us.backedge
+; CHECK-NEXT:       [3] %bb1.i.us
+; CHECK-NEXT:       [3] %bb6.i.us
+; CHECK-NEXT:       [3] %bb4.i.us
+; CHECK-NEXT:       [3] %bb8.i.us
+; CHECK-NEXT:       [3] %bb3.i.loopexit.us
+; CHECK-NEXT:       [3] %bb.nph21
+; CHECK-NEXT:       [3] %bb4
+; CHECK-NEXT:       [3] %bb5
+; CHECK-NEXT:       [3] %bb14.preheader
+; CHECK-NEXT:       [3] %bb.nph18
+; CHECK-NEXT:       [3] %bb8.us.preheader
+; CHECK-NEXT:       [3] %bb8.preheader
+; CHECK-NEXT:       [3] %bb8.us
+; CHECK-NEXT:       [3] %bb8
+; CHECK-NEXT:       [3] %bb15.loopexit
+; CHECK-NEXT:       [3] %bb15.loopexit2
+; CHECK-NEXT:       [3] %bb15
+; CHECK-NEXT:       [3] %bb16
+; CHECK-NEXT:       [3] %bb17.loopexit.split
+; CHECK-NEXT:       [3] %bb.nph14
+; CHECK-NEXT:       [3] %bb19
+; CHECK-NEXT:       [3] %bb20
+; CHECK-NEXT:       [3] %bb29.preheader
+; CHECK-NEXT:       [3] %bb.nph
+; CHECK-NEXT:       [3] %bb23.us.preheader
+; CHECK-NEXT:       [3] %bb23.preheader
+; CHECK-NEXT:       [3] %bb23.us
+; CHECK-NEXT:       [3] %bb23
+; CHECK-NEXT:       [3] %bb30.loopexit
+; CHECK-NEXT:       [3] %bb30.loopexit1
+; CHECK-NEXT:       [3] %bb30
+; CHECK-NEXT:       [3] %bb31
+; CHECK-NEXT:       [3] %bb35.loopexit
+; CHECK-NEXT:       [3] %bb35.loopexit3
+; CHECK-NEXT:     [2] %bb3.i
+; CHECK-NEXT: Roots: %bb35 %bb3.i

test/Analysis/PostDominators/pr6047_d.ll

 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
 ; CHECK: [4] %entry
+
+; CHECK: Inorder PostDominator Tree
+; CHECK-NEXT:   [1]  <<exit node>>
+; CHECK-NEXT:     [2] %bb35
+; CHECK-NEXT:       [3] %c
+; CHECK-NEXT:         [4] %a
+; CHECK-NEXT:         [4] %entry
+; CHECK-NEXT:         [4] %b
+; CHECK-NEXT:       [3] %bb35.loopexit3
+; CHECK-NEXT:     [2] %bb3.i
+; CHECK-NEXT: Roots: %bb35 %bb3.i

test/Analysis/RegionInfo/infinite_loop_4.ll

14:
         br label %"10"
 10:
         br label %"8"
 3:
   br label %"4"
 4:
   ret void
 }
-; CHECK-NOT: =>
+
 ; CHECK: [0] 0 => <Function Return>
-; CHECK-NEXT: [1] 7 => 3
-; STAT: 2 region - The # of regions
-; STAT: 1 region - The # of simple regions
+; CHECK-NEXT:   [1] 7 => 3
+; CHECK-NEXT:     [2] 2 => 10
+; CHECK-NEXT:       [3] 5 => 6
+
+; STAT: 4 region - The # of regions
+; STAT: 2 region - The # of simple regions
+
+; BBIT:      Region tree:
+; BBIT-NEXT: [0] 0 => <Function Return>
+; BBIT-NEXT: {
+; BBIT-NEXT:   0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4,
+; BBIT-NEXT:   [1] 7 => 3
+; BBIT-NEXT:   {
+; BBIT-NEXT:     7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
+; BBIT-NEXT:     [2] 2 => 10
+; BBIT-NEXT:     {
+; BBIT-NEXT:       2, 5, 11, 6, 12,
+; BBIT-NEXT:       [3] 5 => 6
+; BBIT-NEXT:       {
+; BBIT-NEXT:         5, 11, 12,
+; BBIT-NEXT:       }
+; BBIT-NEXT:     }
+; BBIT-NEXT:   }
+; BBIT-NEXT: }
+; BBIT-NEXT: End region tree
+
 
-; BBIT: 0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4,
-; BBIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
+; RNIT:      Region tree:
+; RNIT-NEXT: [0] 0 => <Function Return>
+; RNIT-NEXT: {
+; RNIT-NEXT:   0, 7 => 3, 3, 4,
+; RNIT-NEXT:   [1] 7 => 3
+; RNIT-NEXT:   {
+; RNIT-NEXT:     7, 1, 2 => 10, 10, 8, 9, 13, 14,
+; RNIT-NEXT:     [2] 2 => 10
+; RNIT-NEXT:     {
+; RNIT-NEXT:       2, 5 => 6, 6,
+; RNIT-NEXT:       [3] 5 => 6
+; RNIT-NEXT:       {
+; RNIT-NEXT:         5, 11, 12,
+; RNIT-NEXT:       }
+; RNIT-NEXT:     }
+; RNIT-NEXT:   }
+; RNIT-NEXT: }
+; RNIT-NEXT: End region tree
 
-; RNIT: 0, 7 => 3, 3, 4,
-; RNIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,

test/Analysis/RegionInfo/infinite_loop_5_a.ll

 4:
     ret void
 }
 
 ; CHECK:      Region tree:
 ; CHECK-NEXT: [0] 0 => <Function Return>
 ; CHECK-NEXT:   [1] 7 => 3
 ; CHECK-NEXT: End region tree
-

unittests/IR/DominatorTreeTest.cpp

runWithDomTree(
         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.
+//
+// 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                     D
+//           | \                   |
+//           v  \                  B
+//          /    D                  \
+//         C      \                  A
+//        |       v
+// unreachable    Exit
+//
+// WARNING: PDT-updated is inconsistent with PDT-recalculated, which is
+//          constructed from CFG' when recalculating the PDT from scratch.
+//
+//         PDT-recalculated
+//
+//            Exit
+//           / | \
+//          C  B  D
+//             |
+//             A
+//
+// TODO: document the wanted behavior after resolving this inconsistency.
+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) {
+        Function::iterator FI = F.begin();
+
+        FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *D = &*FI++;
+
+        assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+
+        C->getTerminator()->eraseFromParent();
+        new UnreachableInst(C->getContext(), C);
+
+        DT->deleteEdge(C, B);
+        PDT->deleteEdge(C, B);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+
+        PDT->recalculate(F);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+      });
+}
+
+// Verify that the PDT is correctly updated in case an edge removal results
+// in an infinite loop.
+//
+// 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                     D
+//           | \                   |
+//           v  \                  B
+//          /    D                  \
+//         C      \                  A
+//        / \      v
+//       ^  v      Exit
+//        \_/
+//
+// In PDT, D post-dominates B. We verify that this post-dominance
+// relation is preserved _after_ deleting the edge C->B from CFG.
+//
+// As C now becomes backwards unreachable, it is not anymore part of the
+// PDT. We also verify this property.
+//
+// TODO: Can we change the PDT definition such that C remains part of the
+//       CFG, at best without loosing the dominance relation D postdom B.
+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, PostDomTree *PDT) {
+        Function::iterator FI = F.begin();
+
+        FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *D = &*FI++;
+
+        assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+
+        auto SwitchC = cast<SwitchInst>(C->getTerminator());
+        SwitchC->removeCase(SwitchC->case_begin());
+        DT->deleteEdge(C, B);
+        PDT->deleteEdge(C, B);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+
+        PDT->recalculate(F);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+      });
+}
+
+// Verify that the PDT is correctly updated in case an edge removal results
+// in an infinite loop.
+//
+// Test case:
+//
+//          CFG                   PDT
+//
+//           A                    Exit
+//           |                   / | \
+//           B--                C  B  D
+//           |  \                  |
+//           v   \                 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                     D
+//           | \                   |
+//           v  \                  B
+//          /    D                  \
+//         C      \                  A
+//        / \      v
+//       ^  v      Exit
+//        \_/
+//
+// In PDT, D does not post-dominate B. After the edge C->E is removed, a new
+// post-dominance relation is introduced.
+//
+// As C now becomes backwards unreachable, it is not anymore part of the
+// PDT. We also verify this property.
+//
+// TODO: Can we change the PDT definition such that C remains part of the
+//       CFG, at best without loosing the dominance relation D postdom B.
+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, PostDomTree *PDT) {
+        Function::iterator FI = F.begin();
+
+        FI++;
+        BasicBlock *B = &*FI++;
+        BasicBlock *C = &*FI++;
+        BasicBlock *C2 = &*FI++;
+        BasicBlock *D = &*FI++;
+
+        auto SwitchC = cast<SwitchInst>(C->getTerminator());
+        SwitchC->removeCase(SwitchC->case_begin());
+        DT->deleteEdge(C, C2);
+        PDT->deleteEdge(C, C2);
+        C2->eraseFromParent();
+
+        EXPECT_EQ(DT->getNode(C2), nullptr);
+        PDT->eraseNode(C2);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+        EXPECT_EQ(PDT->getNode(C2), nullptr);
+
+        PDT->recalculate(F);
+
+        EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
+        EXPECT_NE(PDT->getNode(C), nullptr);
+        EXPECT_EQ(PDT->getNode(C2), nullptr);
+      });
+}
+
 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);
 }
while ((LastUpdate = B.applyUpdate())) {
     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);
+  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);
+  EXPECT_NE(PDT.getNode(B.getOrAddBlock("5")), 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"}},