[Dominators] Add parent and sibling property verification (non-hacky)

[kuhar]

Summary

This patch adds an additional level of verification - it checks parent and sibling properties of a tree. By definition, every tree with these two properties is a dominator tree.

It is possible to run those check by running llvm with -verify-dom-info=1.

Bootstrapping clang and building the llvm test suite with this option enabled doesn't yield any errors.

[• dberlin]

You should document what the parent and sibling properties are.

[• dberlin]

This is fine once the properties are documented.

[kuhar]

I added comments explaining the checks.

[kuhar]

Update the diff to apply cleanly.

[grosser]

Hi Kuhar,

I unfortunately just saw this new patch (and all your others) as I was traveling for a little while. Thanks for providing verifiers that check some of the invariants you expect from a dominator tree. In my discussion with Daniel pointed out a scientific paper which explicitly discusses the parent and sibling properties you mention here: "Dominator Tree Certification and Independent Spanning Trees". I think it would be great to reference this (or earlier work) in the commit to help people who would like to have more background.

[chapuni]

It causes infinite loop in bootstrap. Investigating.

[chapuni]

It was not infinite loop but extreme slowness.
https://bugs.llvm.org/show_bug.cgi?id=33656

[• dberlin]

Tobias,
I added some simple explanation and references in r306912 and wordsmithed it a bit in r306916.
Please let me know if you think they are sufficient :)

llvm/trunk/include/llvm/IR/Dominators.h

 class Function;
 class Instruction;
 class Module;
 class raw_ostream;
 
 extern template class DomTreeNodeBase<BasicBlock>;
 extern template class DominatorTreeBase<BasicBlock>;
 
+namespace DomTreeBuilder {
 extern template void Calculate<Function, BasicBlock *>(
     DominatorTreeBaseByGraphTraits<GraphTraits<BasicBlock *>> &DT, Function &F);
+
 extern template void Calculate<Function, Inverse<BasicBlock *>>(
     DominatorTreeBaseByGraphTraits<GraphTraits<Inverse<BasicBlock *>>> &DT,
     Function &F);
 
+extern template bool Verify<BasicBlock *>(
+    const DominatorTreeBaseByGraphTraits<GraphTraits<BasicBlock *>> &DT);
+
+extern template bool Verify<Inverse<BasicBlock *>>(
+    const DominatorTreeBaseByGraphTraits<GraphTraits<Inverse<BasicBlock *>>>
+        &DT);
+}  // namespace DomTreeBuilder
+
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
 
 class BasicBlockEdge {
   const BasicBlock *Start;
   const BasicBlock *End;
 
 public:
   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :

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

for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
                                                        E = N->end();
        I != E; ++I)
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
 namespace DomTreeBuilder {
 template <class NodeT>
 struct SemiNCAInfo;
-}  // namespace DomTreeBuilder
 
 // The calculate routine is provided in a separate header but referenced here.
 template <class FuncT, class N>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, FuncT &F);
 
+// The verify function is provided in a separate header but referenced here.
+template <class N>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+}  // namespace DomTreeBuilder
+
 /// \brief Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
 /// various graphs in the LLVM IR or in the code generator.
 template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
                                const DomTreeNodeBase<NodeT> *B) const {
     assert(A != B);
template <class FT> void recalculate(FT &F) {
     using TraitsTy = GraphTraits<FT *>;
     reset();
 
     if (!this->IsPostDominators) {
       // Initialize root
       NodeT *entry = TraitsTy::getEntryNode(&F);
       addRoot(entry);
 
-      Calculate<FT, NodeT *>(*this, F);
+      DomTreeBuilder::Calculate<FT, NodeT *>(*this, F);
     } else {
       // Initialize the roots list
       for (auto *Node : nodes(&F))
         if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
           addRoot(Node);
 
-      Calculate<FT, Inverse<NodeT *>>(*this, F);
-    }
+      DomTreeBuilder::Calculate<FT, Inverse<NodeT *>>(*this, F);
+    }
+
+  /// verify - check parent and sibling property
+  bool verify() const {
+    return this->isPostDominator()
+           ? DomTreeBuilder::Verify<Inverse<NodeT *>>(*this)
+           : DomTreeBuilder::Verify<NodeT *>(*this);
   }
 };
 
 // These two functions are declared out of line as a workaround for building
 // with old (< r147295) versions of clang because of pr11642.
 template <class NodeT>
 bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const {
   if (A == B)

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

 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
-
 namespace DomTreeBuilder {
+
 // Information record used by Semi-NCA during tree construction.
 template <typename NodeT>
 struct SemiNCAInfo {
   using NodePtr = NodeT *;
   using DomTreeT = DominatorTreeBase<NodeT>;
   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
 
   struct InfoRec {
     unsigned DFSNum = 0;
     unsigned Parent = 0;
     unsigned Semi = 0;
     NodePtr Label = nullptr;
     NodePtr IDom = nullptr;
   };
 
-  DomTreeT &DT;
   std::vector<NodePtr> NumToNode;
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
-  SemiNCAInfo(DomTreeT &DT) : DT(DT) {}
+  void clear() {
+    NumToNode.clear();
+    NodeToInfo.clear();
+  }
 
   NodePtr getIDom(NodePtr BB) const {
     auto InfoIt = NodeToInfo.find(BB);
     if (InfoIt == NodeToInfo.end()) return nullptr;
 
     return InfoIt->second.IDom;
   }
 
-  TreeNodePtr getNodeForBlock(NodePtr BB) {
+  TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
     if (TreeNodePtr Node = DT.getNode(BB)) return Node;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
     NodePtr IDom = getIDom(BB);
 
     assert(IDom || DT.DomTreeNodes[nullptr]);
-    TreeNodePtr IDomNode = getNodeForBlock(IDom);
+    TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
 
     // Add a new tree node for this NodeT, and link it as a child of
     // IDomNode
     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
         .get();
   }
 
for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
       if (IsChildOfArtificialExit)
         BBInfo.Parent = 1;
 
       IsChildOfArtificialExit = false;
     }
     return N;
   }
 
-  unsigned runDFS(NodePtr V, unsigned N) {
+  unsigned runForwardDFS(NodePtr V, unsigned N) {
     auto DFStorage = getStorage();
 
     for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
          I != E; ++I) {
       NodePtr BB = *I;
       auto &BBInfo = NodeToInfo[BB];
       BBInfo.DFSNum = BBInfo.Semi = ++N;
       BBInfo.Label = BB;
while (!Work.empty()) {
         VInfo.Label = VAncestorLabel;
       VInfo.Parent = VAInfo.Parent;
     }
 
     return VInInfo.Label;
   }
 
   template <typename NodeType>
-  void runSemiNCA(unsigned NumBlocks) {
+  void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
     unsigned N = 0;
     NumToNode.push_back(nullptr);
 
     bool MultipleRoots = (DT.Roots.size() > 1);
     if (MultipleRoots) {
       auto &BBInfo = NodeToInfo[nullptr];
       BBInfo.DFSNum = BBInfo.Semi = ++N;
       BBInfo.Label = nullptr;
 
       NumToNode.push_back(nullptr); // NumToNode[n] = V;
     }
 
     // Step #1: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
     if (DT.isPostDominator()){
       for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
            i != e; ++i)
         N = runReverseDFS(DT.Roots[i], N);
     } else {
-      N = runDFS(DT.Roots[0], N);
+      N = runForwardDFS(DT.Roots[0], N);
     }
 
     // It might be that some blocks did not get a DFS number (e.g., blocks of
     // infinite loops). In these cases an artificial exit node is required.
     MultipleRoots |= (DT.isPostDominator() && N != NumBlocks);
 
     // Initialize IDoms to spanning tree parents.
     for (unsigned i = 1; i <= N; ++i) {
for (unsigned i = 2; i <= N; ++i) {
       if (DT.DomTreeNodes[W])
         continue; // Haven't calculated this node yet?
 
       NodePtr ImmDom = getIDom(W);
 
       assert(ImmDom || DT.DomTreeNodes[nullptr]);
 
       // Get or calculate the node for the immediate dominator
-      TreeNodePtr IDomNode = getNodeForBlock(ImmDom);
+      TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 
       // Add a new tree node for this BasicBlock, and link it as a child of
       // IDomNode
       DT.DomTreeNodes[W] = IDomNode->addChild(
           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     }
 
     DT.updateDFSNumbers();
   }
+
+  void doFullDFSWalk(const DomTreeT &DT) {
+    unsigned Num = 0;
+    for (auto *Root : DT.Roots)
+      if (!DT.isPostDominator())
+        Num = runForwardDFS(Root, Num);
+      else
+        Num = runReverseDFS(Root, Num);
+  }
+
+  static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
+    if (!Obj)
+      O << "nullptr";
+    else
+      Obj->printAsOperand(O, false);
+  }
+
+  // Checks if the tree contains all reachable nodes in the input graph.
+  bool verifyReachability(const DomTreeT &DT) {
+    clear();
+    doFullDFSWalk(DT);
+
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB) continue;
+
+      if (NodeToInfo.count(BB) == 0) {
+        errs() << "DomTree node ";
+        PrintBlockOrNullptr(errs(), BB);
+        errs() << " not found by DFS walk!\n";
+        errs().flush();
+
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  // 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) {
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB || TN->getChildren().empty()) continue;
+
+      clear();
+      NodeToInfo.insert({BB, {}});
+      doFullDFSWalk(DT);
+
+      for (TreeNodePtr Child : TN->getChildren())
+        if (NodeToInfo.count(Child->getBlock()) != 0) {
+          errs() << "Child ";
+          PrintBlockOrNullptr(errs(), Child->getBlock());
+          errs() << " reachable after its parent ";
+          PrintBlockOrNullptr(errs(), BB);
+          errs() << " is removed!\n";
+          errs().flush();
+
+          return false;
+        }
+    }
+
+    return true;
+  }
+
+  // Check if the tree has sibling property: if a node V does not dominate a
+  // node W for all siblings V and W in the tree.
+  //
+  // This means that if a node gets disconnected from the graph, then all of its
+  // siblings will now still be reachable.
+  bool verifySiblingProperty(const DomTreeT &DT) {
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB || TN->getChildren().empty()) continue;
+
+      const auto &Siblings = TN->getChildren();
+      for (const TreeNodePtr N : Siblings) {
+        clear();
+        NodeToInfo.insert({N->getBlock(), {}});
+        doFullDFSWalk(DT);
+
+        for (const TreeNodePtr S : Siblings) {
+          if (S == N) continue;
+
+          if (NodeToInfo.count(S->getBlock()) == 0) {
+            errs() << "Node ";
+            PrintBlockOrNullptr(errs(), S->getBlock());
+            errs() << " not reachable when its sibling ";
+            PrintBlockOrNullptr(errs(), N->getBlock());
+            errs() << " is removed!\n";
+            errs().flush();
+
+            return false;
+          }
+        }
+      }
+    }
+
+    return true;
+  }
 };
-}  // namespace DomTreeBuilder
 
 template <class FuncT, class NodeT>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
                FuncT &F) {
   using NodePtr = typename GraphTraits<NodeT>::NodeRef;
   static_assert(std::is_pointer<NodePtr>::value,
                 "NodePtr should be a pointer type");
+  SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
+  SNCA.template runSemiNCA<NodeT>(DT, GraphTraits<FuncT *>::size(&F));
+}
+
+template <class NodeT>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
+  using NodePtr = typename GraphTraits<NodeT>::NodeRef;
+  static_assert(std::is_pointer<NodePtr>::value,
+                "NodePtr should be a pointer type");
+  SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
+
+  return SNCA.verifyReachability(DT) && SNCA.verifyParentProperty(DT) &&
+         SNCA.verifySiblingProperty(DT);
 
-  DomTreeBuilder::SemiNCAInfo<typename std::remove_pointer<NodePtr>::type>
-      SNCA(DT);
-  SNCA.template runSemiNCA<NodeT>(GraphTraits<FuncT *>::size(&F));
 }
+
+}  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #endif

llvm/trunk/lib/IR/Dominators.cpp

 // can be found in Dominators.h, GenericDomTree.h, and
 // GenericDomTreeConstruction.h.
 //
 //===----------------------------------------------------------------------===//
 
 template class llvm::DomTreeNodeBase<BasicBlock>;
 template class llvm::DominatorTreeBase<BasicBlock>;
 
-template void llvm::Calculate<Function, BasicBlock *>(
+template void llvm::DomTreeBuilder::Calculate<Function, BasicBlock *>(
     DominatorTreeBase<
         typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
         &DT,
     Function &F);
-template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
+template void llvm::DomTreeBuilder::Calculate<Function, Inverse<BasicBlock *>>(
     DominatorTreeBase<typename std::remove_pointer<
         GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
     Function &F);
+template bool llvm::DomTreeBuilder::Verify<BasicBlock *>(
+    const DominatorTreeBase<
+        typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
+        &DT);
+template bool llvm::DomTreeBuilder::Verify<Inverse<BasicBlock *>>(
+    const DominatorTreeBase<typename std::remove_pointer<
+        GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT);
 
 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &) {
   // Check whether the analysis, all analyses on functions, or the function's
   // CFG have been preserved.
   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
bool DominatorTree::isReachableFromEntry(const Use &U) const {
   if (PHINode *PN = dyn_cast<PHINode>(I))
     return isReachableFromEntry(PN->getIncomingBlock(U));
 
   // Everything else uses their operands in their own block.
   return isReachableFromEntry(I->getParent());
 }
 
 void DominatorTree::verifyDomTree() const {
+  if (!verify()) {
+    errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n";
+    print(errs());
+    abort();
+  }
+
   Function &F = *getRoot()->getParent();
 
   DominatorTree OtherDT;
   OtherDT.recalculate(F);
   if (compare(OtherDT)) {
     errs() << "DominatorTree is not up to date!\nComputed:\n";
     print(errs());
     errs() << "\nActual:\n";