diff options
| -rw-r--r-- | llvm/include/llvm/IR/Dominators.h | 15 | ||||
| -rw-r--r-- | llvm/include/llvm/Support/GenericDomTree.h | 33 | ||||
| -rw-r--r-- | llvm/include/llvm/Support/GenericDomTreeConstruction.h | 55 | ||||
| -rw-r--r-- | llvm/lib/IR/Dominators.cpp | 45 |
4 files changed, 102 insertions, 46 deletions
diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h index c5373376ade..d80fbdd552f 100644 --- a/llvm/include/llvm/IR/Dominators.h +++ b/llvm/include/llvm/IR/Dominators.h @@ -63,8 +63,10 @@ extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT, 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>; @@ -148,15 +150,6 @@ class DominatorTree : public DominatorTreeBase<BasicBlock, false> { 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; diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h index 635c87a106f..7b3a1a554c5 100644 --- a/llvm/include/llvm/Support/GenericDomTree.h +++ b/llvm/include/llvm/Support/GenericDomTree.h @@ -234,7 +234,7 @@ 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. @@ -259,7 +259,9 @@ class DominatorTreeBase { static constexpr UpdateKind Insert = UpdateKind::Insert; static constexpr UpdateKind Delete = UpdateKind::Delete; - protected: + enum class VerificationLevel { Fast, Basic, Full }; + +protected: // Dominators always have a single root, postdominators can have more. SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots; @@ -316,6 +318,12 @@ class DominatorTreeBase { 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; @@ -750,10 +758,25 @@ public: 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: +protected: void addRoot(NodeT *BB) { this->Roots.push_back(BB); } void reset() { diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h index 25175fe66aa..5cd0ba04070 100644 --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -1281,6 +1281,7 @@ struct SemiNCAInfo { // 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"; @@ -1321,6 +1322,7 @@ struct SemiNCAInfo { } // 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); @@ -1356,6 +1358,7 @@ struct SemiNCAInfo { // 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(); @@ -1387,6 +1390,7 @@ struct SemiNCAInfo { // 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; @@ -1517,10 +1521,10 @@ struct SemiNCAInfo { // 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. @@ -1553,6 +1557,7 @@ struct SemiNCAInfo { // 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. @@ -1587,6 +1592,30 @@ struct SemiNCAInfo { 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> @@ -1615,11 +1644,27 @@ void ApplyUpdates(DomTreeT &DT, } 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 diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp index e44e845b324..25e4ce4e4ef 100644 --- a/llvm/lib/IR/Dominators.cpp +++ b/llvm/lib/IR/Dominators.cpp @@ -28,16 +28,17 @@ #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; @@ -88,9 +89,11 @@ 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 &) { @@ -305,24 +308,16 @@ bool DominatorTree::isReachableFromEntry(const Use &U) const { 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(); } @@ -382,8 +377,8 @@ bool DominatorTreeWrapperPass::runOnFunction(Function &F) { } void DominatorTreeWrapperPass::verifyAnalysis() const { - if (VerifyDomInfo) - DT.verifyDomTree(); + if (ExpensiveChecksEnabled || VerifyDomInfo) + DT.verifyDomTree(); } void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { |
