Fix DFS number calculation for postdominators

The DFS number calculation for postdominators was broken. In the case of
multiple exits that form the post dominator root nodes, do not iterate over
all exits, but start from the virtual root node. Otherwise bbs, that are not
post dominated by any exit but by the virtual root node, will never be assigned
a DFS number.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92967 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 2e149d59e98fb83ac43bc666a5ae211d306aad3e..7ac474aff3470af2a52aa05e30dd1d1d807acbbe 100644 (file)
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -585,29 +585,35 @@ protected:
     SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
                 typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
 
-    for (unsigned i = 0, e = (unsigned)this->Roots.size(); i != e; ++i) {
-      DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
-      WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
-      ThisRoot->DFSNumIn = DFSNum++;
-
-      while (!WorkStack.empty()) {
-        DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
-        typename DomTreeNodeBase<NodeT>::iterator ChildIt =
-                                                        WorkStack.back().second;
-
-        // If we visited all of the children of this node, "recurse" back up the
-        // stack setting the DFOutNum.
-        if (ChildIt == Node->end()) {
-          Node->DFSNumOut = DFSNum++;
-          WorkStack.pop_back();
-        } else {
-          // Otherwise, recursively visit this child.
-          DomTreeNodeBase<NodeT> *Child = *ChildIt;
-          ++WorkStack.back().second;
-
-          WorkStack.push_back(std::make_pair(Child, Child->begin()));
-          Child->DFSNumIn = DFSNum++;
-        }
+    DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
+
+    if (!ThisRoot)
+      return;
+
+    // Even in the case of multiple exits that form the post dominator root
+    // nodes, do not iterate over all exits, but start from the virtual root
+    // node. Otherwise bbs, that are not post dominated by any exit but by the
+    // virtual root node, will never be assigned a DFS number.
+    WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
+    ThisRoot->DFSNumIn = DFSNum++;
+
+    while (!WorkStack.empty()) {
+      DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
+      typename DomTreeNodeBase<NodeT>::iterator ChildIt =
+        WorkStack.back().second;
+
+      // If we visited all of the children of this node, "recurse" back up the
+      // stack setting the DFOutNum.
+      if (ChildIt == Node->end()) {
+        Node->DFSNumOut = DFSNum++;
+        WorkStack.pop_back();
+      } else {
+        // Otherwise, recursively visit this child.
+        DomTreeNodeBase<NodeT> *Child = *ChildIt;
+        ++WorkStack.back().second;
+
+        WorkStack.push_back(std::make_pair(Child, Child->begin()));
+        Child->DFSNumIn = DFSNum++;
       }
     }