[Dominators] Add parent and sibling property verification

[kuhar]

Summary

(This is just to test the old SLT and the new Semi-NCA DomTree construction algorithms. This patch is hacky and is not intended to be commited. It will be rewritten in a more clean way when SNCA/SLT-related info is moved out of DominatorTreeBase.)

This patch adds 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.

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

285

This misses one thing: It¸doesn't verify that a path exists in the first place :)

IE it should verify a path exists, then, when you remove the parent, a path no longer exists.

[kuhar]

Verify reachability.

[kuhar]

Make the code compile when building clang

include/llvm/IR/Dominators.h

 extern template class DominatorTreeBase<BasicBlock>;
 
 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);
+
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
 
 class BasicBlockEdge {
   const BasicBlock *Start;
   const BasicBlock *End;
 
 public:
   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :

include/llvm/Support/GenericDomTree.h

for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
        I != E; ++I)
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
 // 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);
 
+template <class N>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+
 /// \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);
struct InfoRec {
     NodeT *Label = nullptr;
 
     InfoRec() = default;
   };
 
   DenseMap<NodeT *, NodeT *> IDoms;
 
   // Vertex - Map the DFS number to the NodeT*
-  std::vector<NodeT *> Vertex;
+  mutable std::vector<NodeT *> Vertex;
 
   // Info - Collection of information used during the computation of idoms.
-  DenseMap<NodeT *, InfoRec> Info;
+  mutable DenseMap<NodeT *, InfoRec> Info;
 
   void reset() {
     DomTreeNodes.clear();
     IDoms.clear();
     this->Roots.clear();
     Vertex.clear();
     RootNode = nullptr;
     DFSInfoValid = false;
void Split(typename GraphTraits<N>::NodeRef NewBB) {
     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
     if (NewBBDominatesNewBBSucc) {
       DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
       changeImmediateDominator(NewBBSuccNode, NewBBNode);
     }
   }
 
 public:
+  using NodePtr = DomTreeNodeBase<NodeT> *;
   explicit DominatorTreeBase(bool isPostDom)
       : DominatorBase<NodeT>(isPostDom) {}
 
   DominatorTreeBase(DominatorTreeBase &&Arg)
       : DominatorBase<NodeT>(
             std::move(static_cast<DominatorBase<NodeT> &>(Arg))),
         DomTreeNodes(std::move(Arg.DomTreeNodes)),
         RootNode(std::move(Arg.RootNode)),

 
 protected:
   template <class GraphT>
   friend typename GraphT::NodeRef
   Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
        unsigned LastLinked);
 
   template <class GraphT>
-  friend unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+  friend unsigned ReverseDFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                                  typename GraphT::NodeRef V, unsigned N);
 
   template <class GraphT>
-  friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+  friend unsigned DFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                           typename GraphT::NodeRef V, unsigned N);
 
   template <class FuncT, class N>
   friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
                         FuncT &F);
 
+  template <class GraphT>
+  friend void RunDFS(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class GraphT>
+  friend bool VerifyReachability(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class GraphT>
+  friend bool VerifyParentProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class GraphT>
+  friend bool VerifySiblingProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class N>
+  friend bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
     if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
       return Node;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
     NodeT *IDom = getIDom(BB);
 
while (!WorkStack.empty()) {
         Child->DFSNumIn = DFSNum++;
       }
     }
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
+  /// verify - checks parent and sibling property
+  bool verify() const {
+    return this->isPostDominator() ? Verify<Inverse<NodeT *>>(*this)
+                                   : Verify<NodeT *>(*this);
+  }
+
   /// recalculate - compute a dominator tree for the given function
   template <class FT> void recalculate(FT &F) {
     using TraitsTy = GraphTraits<FT *>;
     reset();
     Vertex.push_back(nullptr);
 
     if (!this->IsPostDominators) {
       // Initialize root
       NodeT *entry = TraitsTy::getEntryNode(&F);
       addRoot(entry);
 
       Calculate<FT, NodeT *>(*this, F);
+      Verify<NodeT *>(*this);
     } 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);
+      Verify<Inverse<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 {

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"
+#include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 // External storage for depth first iterator that reuses the info lookup map
 // domtree already has.  We don't have a set, but a map instead, so we are
 // converting the one argument insert calls.
 template <class NodeRef, class InfoType> struct df_iterator_dom_storage {
 public:
   using BaseSet = DenseMap<NodeRef, InfoType>;
   df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
 
   using iterator = typename BaseSet::iterator;
   std::pair<iterator, bool> insert(NodeRef N) {
     return Storage.insert({N, InfoType()});
   }
   void completed(NodeRef) {}
 
 private:
   BaseSet &Storage;
 };
 
 template <class GraphT>
-unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+unsigned ReverseDFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                         typename GraphT::NodeRef V, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
       typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
       DFStorage(DT.Info);
   bool IsChildOfArtificialExit = (N != 0);
   for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
        I != E; ++I) {
for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
     if (IsChildOfArtificialExit)
       BBInfo.Parent = 1;
 
     IsChildOfArtificialExit = false;
   }
   return N;
 }
 template <class GraphT>
-unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+unsigned DFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                  typename GraphT::NodeRef V, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
       typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
       DFStorage(DT.Info);
   for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
        I != E; ++I) {
     typename GraphT::NodeRef BB = *I;
void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
   // Free temporary memory used to construct idom's
   DT.IDoms.clear();
   DT.Info.clear();
   DT.Vertex.clear();
   DT.Vertex.shrink_to_fit();
 
   DT.updateDFSNumbers();
 }
+
+
+template <class GraphT>
+void RunDFS(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  unsigned Num = 0;
+  for (auto *Root : DT.Roots)
+    if (!DT.isPostDominator())
+      Num = DFSPass<GraphT>(DT, Root, Num);
+    else
+      Num = ReverseDFSPass<GraphT>(DT, Root, Num);
+
+  DT.Vertex.clear();
+}
+
+template <class GraphT>
+bool VerifyReachability(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  using BlockPtr = typename GraphT::NodeRef;
+  using NodePtr =
+  DomTreeNodeBase<typename std::remove_pointer<BlockPtr>::type> *;
+
+  DT.Info.clear();
+  RunDFS<GraphT>(DT);
+
+  for (auto &NodeToTN : DT.DomTreeNodes) {
+    const NodePtr TN = NodeToTN.second.get();
+    const BlockPtr BB = TN->getBlock();
+    if (!BB)
+      continue;
+
+    if (DT.Info.count(BB) == 0) {
+      errs() << "DomTree node " << BB->getName() << " not found by DFS walk!\n";
+      DT.Info.clear();
+      return false;
+    }
+  }
+
+  DT.Info.clear();
+  return true;
+}
+
+template <class GraphT>
+bool VerifyParentProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  using BlockPtr = typename GraphT::NodeRef;
+  using NodePtr =
+                DomTreeNodeBase<typename std::remove_pointer<BlockPtr>::type> *;
+  for (auto &NodeToTN : DT.DomTreeNodes) {
+    const NodePtr TN = NodeToTN.second.get();
+    const BlockPtr BB = TN->getBlock();
+    if (!BB || TN->getChildren().empty())
+      continue;
+
+    DT.Info.clear();
+    DT.Info.insert({BB, {}});
+    RunDFS<GraphT>(DT);
+
+    for (NodePtr Child : TN->getChildren())
+      if (DT.Info.count(Child->getBlock()) != 0) {
+        errs() << "Child " << Child->getBlock()->getName()
+               << " reachable after its parent " << BB->getName()
+               << " is removed!\n";
+        errs().flush();
+        DT.Info.clear();
+        return false;
+      }
+  }
+
+  DT.Info.clear();
+  return true;
+}
+
+template <class GraphT>
+bool VerifySiblingProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  using BlockPtr = typename GraphT::NodeRef;
+  using NodePtr =
+  DomTreeNodeBase<typename std::remove_pointer<BlockPtr>::type> *;
+
+  for (auto &NodeToTN : DT.DomTreeNodes) {
+    const NodePtr TN = NodeToTN.second.get();
+    const BlockPtr BB = TN->getBlock();
+    if (!BB || TN->getChildren().empty())
+      continue;
+
+    const auto& Siblings = TN->getChildren();
+    for (const NodePtr N : Siblings) {
+      for (const NodePtr S : Siblings) {
+        if (S == N)
+          continue;
+
+        DT.Info.clear();
+        DT.Info.insert({S->getBlock(), {}});
+        RunDFS<GraphT>(DT);
+
+        if (DT.Info.count(N->getBlock()) == 0) {
+          errs() << "Node " << N->getBlock()->getName() << " not reachable "
+                 << "when its sibling " << S->getBlock()->getName()
+                 << " is removed!\n";
+          errs().flush();
+          DT.Info.clear();
+          return false;
+        }
+      }
+    }
+  }
+
+  DT.Info.clear();
+  return true;
+}
+
+template <class NodeT>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
+  bool Correct = VerifyReachability<GraphTraits<NodeT>>(DT) &&
+                 VerifyParentProperty<GraphTraits<NodeT>>(DT) &&
+                 VerifySiblingProperty<GraphTraits<NodeT>>(DT);
+  if (Correct)
+    return true;
+
+  errs() << "\n~~~~~~~~~~~~~~~~~~\n\t\tIncorrect DomTree!\n~~~~~~~~~~~~~~~~\n";
+  return false;
+}
+
 }
 
 #endif

lib/IR/Dominators.cpp

DominatorTreeBase<
         typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
         &DT,
     Function &F);
 template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
     DominatorTreeBase<typename std::remove_pointer<
         GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
     Function &F);
 
+template bool llvm::Verify<BasicBlock *>(
+    const DominatorTreeBase<
+        typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
+    &DT);
+template bool llvm::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())
+    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";