[Dominators] Introduce DomTree verification levels

[kuhar]

Summary

Currently, there are 2 ways to verify a DomTree:

• DT.verify() -- runs full tree verification and checks all the properties and gives a reason why the tree is incorrect. This is run by when EXPENSIVE_CHECKS are enabled or when -verify-dom-info flag is set.
• DT.verifyDominatorTree() -- constructs a fresh tree and compares it against the old one. This does not check any other tree properties (DFS number, levels), nor ensures that the construction algorithm is correct. Used by some passes inside assertions.

This patch introduces DomTree verification levels, that try to close the gape between the two ways of checking trees by introducing 3 verification levels:

• Full -- checks all properties, but can be slow (O(N^3)). Used when manually requested (e.g. assert(DT.verify())) or when -verify-dom-info is set.
• Basic -- checks all properties except the sibling property, and compares the current tree with a freshly constructed one instead. This should catch almost all errors, but does not guarantee that the construction algorithm is correct. Used when EXPENSIVE checks are enabled.
• Fast -- checks only basic properties (reachablility, dfs numbers, levels, roots), and compares with a fresh tree. This is meant to replace the legacy DT.verifyDominatorTree() and in my tests doesn't cause any noticeable performance impact even in the most pessimistic examples.

When used to verify dom tree wrapper pass analysis on sqlite3, the 3 new levels make opt -O3 take the following amount of time on my machine:

• no verification: 8.3s
• DT.verify(VerificationLevel::Fast): 10.1s
• DT.verify(VerificationLevel::Basic): 44.8s
• DT.verify(VerificationLevel::Full): 1m 46.2s

(and the previous DT.verifyDominatorTree() is within the noise of the Fast level)

This patch makes DT.verifyDominatorTree() pick between the 3 verification levels depending on EXPENSIVE_CHECKS and -verify-dom-info.

[kuhar]

@dberlin:

I assume if we ever bothered to make the verification O(N) again using better algorithms, we'd go back to one level of verification?

I think it's very unlikely that someone will implement this in the foreseeable future. As far as I understand, this would disallow to perform any manual updates and require extra data to be sorted in the tree and the tree nodes.
But if someone implements this, it would be best to go back one verification level. And if it tells us the tree is incorrect, we could run the current full verification to get a descriptive error message telling us what exactly went wrong.

[brzycki]

LGTM. I just have one question about the patch, see inline.

include/llvm/Support/GenericDomTree.h

775 ↗

(On Diff #130776)

Is the Full level the same as what verify did before this patch? I'm curious how the default level was chosen.

[kuhar]

include/llvm/Support/GenericDomTree.h

775 ↗

(On Diff #130776)

Yes. This is to preserve behavior of the existing code.
I also expect DT.verify() to be used for debugging, where you don't really care how long it takes. And then if it becomes a performance issue for someone, they can explicitly request a faster (but imprecise) level.

[• dberlin]

In D42337#983023, @kuhar wrote:

@dberlin:

I assume if we ever bothered to make the verification O(N) again using better algorithms, we'd go back to one level of verification?

I think it's very unlikely that someone will implement this in the foreseeable future.

Sure, i was just asking

As far as I understand, this would disallow to perform any manual updates and require extra data to be sorted in the tree and the tree nodes.

That's just the current state. These things always improve :)

But if someone implements this, it would be best to go back one verification level. And if it tells us the tree is incorrect, we could run the current full verification to get a descriptive error message telling us what exactly went wrong.

SGTM

[brzycki]

LGTM.

[MatzeB]

Thanks!

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

extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);
 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
                                                BasicBlock *From,
                                                BasicBlock *To);
 
 extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
 extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
 
-extern template bool Verify<BBDomTree>(const BBDomTree &DT);
-extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT);
+extern template bool Verify<BBDomTree>(const BBDomTree &DT,
+                                       BBDomTree::VerificationLevel VL);
+extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
+                                           BBPostDomTree::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
 
 class BasicBlockEdge {
   const BasicBlock *Start;
   const BasicBlock *End;
 
public:
 
   DominatorTree() = default;
   explicit DominatorTree(Function &F) { recalculate(F); }
 
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 
-  /// \brief Returns *false* if the other dominator tree matches this dominator
-  /// tree.
-  inline bool compare(const DominatorTree &Other) const {
-    const DomTreeNode *R = getRootNode();
-    const DomTreeNode *OtherR = Other.getRootNode();
-    return !R || !OtherR || R->getBlock() != OtherR->getBlock() ||
-           Base::compare(Other);
-  }
-
   // Ensure base-class overloads are visible.
   using Base::dominates;
 
   /// \brief Return true if Def dominates a use in User.
   ///
   /// This performs the special checks necessary if Def and User are in the same
   /// basic block. Note that Def doesn't dominate a use in Def itself!
   bool dominates(const Instruction *Def, const Use &U) const;

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

struct Update {
   }
 };
 
 template <typename DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
                   ArrayRef<typename DomTreeT::UpdateType> Updates);
 
 template <typename DomTreeT>
-bool Verify(const DomTreeT &DT);
+bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
 }  // 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 <typename NodeT, bool IsPostDom>
 class DominatorTreeBase {
  public:
   static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
                 "Currently DominatorTreeBase supports only pointer nodes");
   using NodeType = NodeT;
   using NodePtr = NodeT *;
   using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
   static_assert(std::is_pointer<ParentPtr>::value,
                 "Currently NodeT's parent must be a pointer type");
   using ParentType = typename std::remove_pointer<ParentPtr>::type;
   static constexpr bool IsPostDominator = IsPostDom;
 
   using UpdateType = DomTreeBuilder::Update<NodePtr>;
   using UpdateKind = DomTreeBuilder::UpdateKind;
   static constexpr UpdateKind Insert = UpdateKind::Insert;
   static constexpr UpdateKind Delete = UpdateKind::Delete;
 
- protected:
+  enum class VerificationLevel { Fast, Basic, Full };
+
   // Dominators always have a single root, postdominators can have more.
   SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
 
   using DomTreeNodeMapType =
      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
   DomTreeNodeMapType DomTreeNodes;
   DomTreeNodeBase<NodeT> *RootNode;
   ParentPtr Parent = nullptr;
public:
   ///
   bool isPostDominator() const { return IsPostDominator; }
 
   /// compare - Return false if the other dominator tree base matches this
   /// dominator tree base. Otherwise return true.
   bool compare(const DominatorTreeBase &Other) const {
     if (Parent != Other.Parent) return true;
 
+    if (Roots.size() != Other.Roots.size())
+      return false;
+
+    if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
+      return false;
+
     const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
     if (DomTreeNodes.size() != OtherDomTreeNodes.size())
       return true;
 
     for (const auto &DomTreeNode : DomTreeNodes) {
       NodeT *BB = DomTreeNode.first;
       typename DomTreeNodeMapType::const_iterator OI =
           OtherDomTreeNodes.find(BB);
public:
   }
 
   /// recalculate - compute a dominator tree for the given function
   void recalculate(ParentType &Func) {
     Parent = &Func;
     DomTreeBuilder::Calculate(*this);
   }
 
-  /// verify - check parent and sibling property
-  bool verify() const { return DomTreeBuilder::Verify(*this); }
+  /// verify - checks if the tree is correct. There are 3 level of verification:
+  ///  - Full --  verifies if the tree is correct by making sure all the
+  ///             properties (including the parent and the sibling property)
+  ///             hold.
+  ///             Takes O(N^3) time.
+  ///
+  ///  - Basic -- checks if the tree is correct, but compares it to a freshly
+  ///             constructed tree instead of checking the sibling property.
+  ///             Takes O(N^2) time.
+  ///
+  ///  - Fast  -- checks basic tree structure and compares it with a freshly
+  ///             constructed tree.
+  ///             Takes O(N^2) time worst case, but is faster in practise (same
+  ///             as tree construction).
+  bool verify(VerificationLevel VL = VerificationLevel::Full) const {
+    return DomTreeBuilder::Verify(*this, VL);
+  }
 
- protected:
   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 
   void reset() {
     DomTreeNodes.clear();
     Roots.clear();
     RootNode = nullptr;
     Parent = nullptr;
     DFSInfoValid = false;

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

#endif
   //~~
   //===--------------- 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 PostDominatorTree can have
   // multiple roots - one for each node with no successors and for infinite
   // loops.
+  // Running time: O(N).
   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.size() != ComputedRoots.size() ||
       errs().flush();
       return false;
     }
 
     return true;
   }
 
   // Checks if the tree contains all reachable nodes in the input graph.
+  // Running time: O(N).
   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();
 
for (const NodePtr N : NumToNode) {
       }
     }
 
     return true;
   }
 
   // Check if for every parent with a level L in the tree all of its children
   // have level L + 1.
+  // Running time: O(N).
   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;
 
       const TreeNodePtr IDom = TN->getIDom();
       if (!IDom && TN->getLevel() != 0) {
for (auto &NodeToTN : DT.DomTreeNodes) {
       }
     }
 
     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.
+  // Running time: O(N log(N)).
   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) {
#endif
   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
   // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
   // RIGHT, not a sibling.
 
   // It is possible to verify the parent and sibling properties in
   // linear time, but the algorithms are complex. Instead, we do it in a
   // straightforward N^2 and N^3 way below, using direct path reachability.
 
-
   // 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.
+  // Running time: O(N^2).
   //
   // 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;
for (auto &NodeToTN : DT.DomTreeNodes) {
         }
     }
 
     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.
+  // Running time: O(N^3).
   //
   // 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;
for (auto &NodeToTN : DT.DomTreeNodes) {
             return false;
           }
         }
       }
     }
 
     return true;
   }
+
+  // Check if the given tree is the same as a freshly computed one for the same
+  // Parent.
+  // Running time: O(N^2), but faster in practise (same as tree construction).
+  //
+  // Note that this does not check if that the tree construction algorithm is
+  // correct and should be only used for fast (but possibly unsound)
+  // verification.
+  static bool IsSameAsFreshTree(const DomTreeT &DT) {
+    DomTreeT FreshTree;
+    FreshTree.recalculate(*DT.Parent);
+    const bool Different = DT.compare(FreshTree);
+
+    if (Different) {
+      errs() << "DominatorTree is different than a freshly computed one!\n"
+             << "\tCurrent:\n";
+      DT.print(errs());
+      errs() << "\n\tFreshly computed tree:\n";
+      FreshTree.print(errs());
+      errs().flush();
+    }
+
+    return !Different;
+  }
 };
 
 template <class DomTreeT>
 void Calculate(DomTreeT &DT) {
   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
 }
 
 template <class DomTreeT>

 
 template <class DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
                   ArrayRef<typename DomTreeT::UpdateType> Updates) {
   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
 }
 
 template <class DomTreeT>
-bool Verify(const DomTreeT &DT) {
+bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
   SemiNCAInfo<DomTreeT> SNCA(nullptr);
-  return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
-         SNCA.VerifyLevels(DT) && SNCA.verifyParentProperty(DT) &&
-         SNCA.verifySiblingProperty(DT) && SNCA.VerifyDFSNumbers(DT);
+  const bool InitialChecks = SNCA.verifyRoots(DT) &&
+                             SNCA.verifyReachability(DT) &&
+                             SNCA.VerifyLevels(DT) && SNCA.VerifyDFSNumbers(DT);
+
+  if (!InitialChecks)
+    return false;
+
+  switch (VL) {
+  case DomTreeT::VerificationLevel::Fast:
+    return SNCA.IsSameAsFreshTree(DT);
+
+  case DomTreeT::VerificationLevel::Basic:
+    return SNCA.verifyParentProperty(DT) && SNCA.IsSameAsFreshTree(DT);
+
+  case DomTreeT::VerificationLevel::Full:
+    return SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
+  }
+
+  llvm_unreachable("Unhandled DomTree VerificationLevel");
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif

llvm/trunk/lib/IR/Dominators.cpp

 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 using namespace llvm;
 
-// Always verify dominfo if expensive checking is enabled.
-#ifdef EXPENSIVE_CHECKS
-bool llvm::VerifyDomInfo = true;
-#else
 bool llvm::VerifyDomInfo = false;
-#endif
 static cl::opt<bool, true>
     VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
                    cl::desc("Verify dominator info (time consuming)"));
 
+#ifdef EXPENSIVE_CHECKS
+static constexpr bool ExpensiveChecksEnabled = true;
+#else
+static constexpr bool ExpensiveChecksEnabled = false;
+#endif
+
 bool BasicBlockEdge::isSingleEdge() const {
   const TerminatorInst *TI = Start->getTerminator();
   unsigned NumEdgesToEnd = 0;
   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
     if (TI->getSuccessor(i) == End)
       ++NumEdgesToEnd;
     if (NumEdgesToEnd >= 2)
       return false;
template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
 
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
-    const DomTreeBuilder::BBDomTree &DT);
+    const DomTreeBuilder::BBDomTree &DT,
+    DomTreeBuilder::BBDomTree::VerificationLevel VL);
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
-    const DomTreeBuilder::BBPostDomTree &DT);
+    const DomTreeBuilder::BBPostDomTree &DT,
+    DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
 
 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>());
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 {
   // Perform the expensive checks only when VerifyDomInfo is set.
-  if (VerifyDomInfo && !verify()) {
-    errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n";
-    print(errs());
-    abort();
-  }
-
-  Function &F = *getRoot()->getParent();
+  VerificationLevel VL = VerificationLevel::Fast;
+  if (VerifyDomInfo)
+    VL = VerificationLevel::Full;
+  else if (ExpensiveChecksEnabled)
+    VL = VerificationLevel::Basic;
 
-  DominatorTree OtherDT;
-  OtherDT.recalculate(F);
-  if (compare(OtherDT)) {
-    errs() << "DominatorTree for function " << F.getName()
-           << " is not up to date!\nComputed:\n";
-    print(errs());
-    errs() << "\nActual:\n";
-    OtherDT.print(errs());
+  if (!verify(VL)) {
+    errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n";
     errs() << "\nCFG:\n";
-    F.print(errs());
+    getRoot()->getParent()->print(errs());
     errs().flush();
     abort();
   }
 }
 
 //===----------------------------------------------------------------------===//
 //  DominatorTreeAnalysis and related pass implementations
 //===----------------------------------------------------------------------===//
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
                 "Dominator Tree Construction", true, true)
 
 bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(F);
   return false;
 }
 
 void DominatorTreeWrapperPass::verifyAnalysis() const {
-    if (VerifyDomInfo)
-      DT.verifyDomTree();
+  if (ExpensiveChecksEnabled || VerifyDomInfo)
 }
 
 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
   DT.print(OS);
 }
 
 //===----------------------------------------------------------------------===//
 //  DeferredDominance Implementation