[Dominators] Add DFS number verification

[kuhar]

Summary

This patch teaches the DominatorTree verifier to check DFS In/Out numbers which are used to answer dominance queries.
DFS number verification is done in O(nlogn), so it shouldn't add much overhead on top of the O(n^3) sibling property verification.
This check should detect errors like the one spotted in PR34466 and related bug reports.

The patch also cleans up the DFS calculation a bit, as all constructed trees should have a single root now.

I see 2 new test failures when running check-all after this change:

Failing Tests (2):
    Polly :: Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll
    Polly :: Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll

which seem to happen just after Create LLVM-IR from SCoPs -- I don't have much time now, so it would be awesome if the polly folks could help me with fixing that before sending this patch :).

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

1394 ↗

(On Diff #116870)

s/sort is/sort it

[grosser]

Dear Kuhar,

our OpenMP backend is currently experimental (and I am traveling). Feel free to XFAIL the test cases for now. I will fix them when I get back.

Best,
Tobias

[kuhar]

OK, I will XFAIL them when submitting this patch.

@dberlin, @grosser, @davide Can you please take a look at the patch?

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

1395 ↗

(On Diff #116870)

My only concern here is that this mutates the tree in a verification function.
Given its verification, i would probably push the children and dfs numbers into a new vector, and sort + check that, to avoid mutating the tree.

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

1395 ↗

(On Diff #116870)

It doesn't mutate children here -- a copy is made instead.
If it improves readability, I can change it into an construction of a new vector with explicit type instead of auto.

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

1395 ↗

(On Diff #116870)

Yeah, i missed totally missed that.

Even something like auto Children(Node->getChildren()) would be more obvious (if it works :P)

[kuhar]

Make explicit copy of Node's children. Fix a typo.

llvm/trunk/include/llvm/Support/GenericDomTree.h

public:
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
   /// dominator tree in dfs order.
   void updateDFSNumbers() const {
     if (DFSInfoValid) {
       SlowQueries = 0;
       return;
     }
 
-    unsigned DFSNum = 0;
-
     SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
                           typename DomTreeNodeBase<NodeT>::const_iterator>,
                 32> WorkStack;
 
     const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
-
+    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
     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()));
+    // Both dominators and postdominators have a single root node. In the case
+    // case of PostDominatorTree, this node is a virtual root.
+    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
+
+    unsigned DFSNum = 0;
     ThisRoot->DFSNumIn = DFSNum++;
 
     while (!WorkStack.empty()) {
       const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
-      typename DomTreeNodeBase<NodeT>::const_iterator ChildIt =
-          WorkStack.back().second;
+      const auto 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.
         const DomTreeNodeBase<NodeT> *Child = *ChildIt;
         ++WorkStack.back().second;
 
-        WorkStack.push_back(std::make_pair(Child, Child->begin()));
+        WorkStack.push_back({Child, Child->begin()});
         Child->DFSNumIn = DFSNum++;
       }
     }
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

for (auto &NodeToTN : DT.DomTreeNodes) {
 
         return false;
       }
     }
 
     return true;
   }
 
+  // Check if the computed DFS numbers are correct. Note that DFS info may not
+  // be valid, and when that is the case, we don't verify the numbers.
+  static bool VerifyDFSNumbers(const DomTreeT &DT) {
+    if (!DT.DFSInfoValid || !DT.Parent)
+      return true;
+
+    const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
+    const TreeNodePtr Root = DT.getNode(RootBB);
+
+    auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
+      errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
+             << TN->getDFSNumOut() << '}';
+    };
+
+    // Verify the root's DFS In number. Although DFS numbering would also work
+    // if we started from some other value, we assume 0-based numbering.
+    if (Root->getDFSNumIn() != 0) {
+      errs() << "DFSIn number for the tree root is not:\n\t";
+      PrintNodeAndDFSNums(Root);
+      errs() << '\n';
+      errs().flush();
+      return false;
+    }
+
+    // For each tree node verify if children's DFS numbers cover their parent's
+    // DFS numbers with no gaps.
+    for (const auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr Node = NodeToTN.second.get();
+
+      // Handle tree leaves.
+      if (Node->getChildren().empty()) {
+        if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
+          errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
+          PrintNodeAndDFSNums(Node);
+          errs() << '\n';
+          errs().flush();
+          return false;
+        }
+
+        continue;
+      }
+
+      // Make a copy and sort it such that it is possible to check if there are
+      // no gaps between DFS numbers of adjacent children.
+      SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
+      std::sort(Children.begin(), Children.end(),
+                [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
+                  return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
+                });
+
+      auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
+          const TreeNodePtr FirstCh, const TreeNodePtr SecondCh = nullptr) {
+        assert(FirstCh);
+
+        errs() << "Incorrect DFS numbers for:\n\tParent ";
+        PrintNodeAndDFSNums(Node);
+
+        errs() << "\n\tChild ";
+        PrintNodeAndDFSNums(FirstCh);
+
+        if (SecondCh) {
+          errs() << "\n\tSecond child ";
+          PrintNodeAndDFSNums(SecondCh);
+        }
+
+        errs() << "\nAll children: ";
+        for (const TreeNodePtr Ch : Children) {
+          PrintNodeAndDFSNums(Ch);
+          errs() << ", ";
+        }
+
+        errs() << '\n';
+        errs().flush();
+      };
+
+      if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
+        PrintChildrenError(Children.front());
+        return false;
+      }
+
+      if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
+        PrintChildrenError(Children.back());
+        return false;
+      }
+
+      for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
+        if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
+          PrintChildrenError(Children[i], Children[i + 1]);
+          return false;
+        }
+      }
+    }
+
+    return true;
+  }
+
   // Checks if for every edge From -> To in the graph
   //     NCD(From, To) == IDom(To) or To.
   bool verifyNCD(const DomTreeT &DT) {
     clear();
     doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &BlockToInfo : NodeToInfo) {
       auto &Info = BlockToInfo.second;
void ApplyUpdates(DomTreeT &DT,
   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
 }
 
 template <class DomTreeT>
 bool Verify(const DomTreeT &DT) {
   SemiNCAInfo<DomTreeT> SNCA(nullptr);
   return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
          SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) &&
-         SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
+         SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT) &&
+         SNCA.VerifyDFSNumbers(DT);
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif