Index: include/llvm/Analysis/PostDominators.h =================================================================== --- include/llvm/Analysis/PostDominators.h +++ include/llvm/Analysis/PostDominators.h @@ -76,6 +76,8 @@ bool runOnFunction(Function &F) override; + void verifyAnalysis() const override; + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); } Index: include/llvm/CodeGen/MachineDominators.h =================================================================== --- include/llvm/CodeGen/MachineDominators.h +++ include/llvm/CodeGen/MachineDominators.h @@ -249,12 +249,6 @@ "A basic block inserted via edge splitting cannot appear twice"); CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); } - - /// \brief Verify the correctness of the domtree by re-computing it. - /// - /// This should only be used for debugging as it aborts the program if the - /// verification fails. - void verifyDomTree() const; }; //===------------------------------------- Index: include/llvm/IR/Dominators.h =================================================================== --- include/llvm/IR/Dominators.h +++ include/llvm/IR/Dominators.h @@ -174,12 +174,6 @@ /// \brief Provide an overload for a Use. bool isReachableFromEntry(const Use &U) const; - /// \brief Verify the correctness of the domtree by re-computing it. - /// - /// This should only be used for debugging as it aborts the program if the - /// verification fails. - void verifyDomTree() const; - // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`. void viewGraph(const Twine &Name, const Twine &Title); void viewGraph(); Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -319,10 +319,10 @@ if (Parent != Other.Parent) return true; if (Roots.size() != Other.Roots.size()) - return false; + return true; if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) - return false; + return true; const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; if (DomTreeNodes.size() != OtherDomTreeNodes.size()) Index: include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- include/llvm/Support/GenericDomTreeConstruction.h +++ include/llvm/Support/GenericDomTreeConstruction.h @@ -1600,9 +1600,9 @@ DomTreeT FreshTree; FreshTree.recalculate(*DT.Parent); const bool Different = DT.compare(FreshTree); - if (Different) { - errs() << "DominatorTree is different than a freshly computed one!\n" + errs() << (DT.isPostDominator() ? "Post" : "") + << "DominatorTree is different than a freshly computed one!\n" << "\tCurrent:\n"; DT.print(errs()); errs() << "\n\tFreshly computed tree:\n"; @@ -1642,34 +1642,27 @@ template bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) { SemiNCAInfo SNCA(nullptr); - const bool InitialChecks = SNCA.verifyRoots(DT) && - SNCA.verifyReachability(DT) && - SNCA.VerifyLevels(DT) && SNCA.VerifyDFSNumbers(DT); - if (!InitialChecks) + // Simplist check is to compare against a new tree. This will also + // usefully print the old and new trees, if they are different. + if (!SNCA.IsSameAsFreshTree(DT)) 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: { - bool FullRes - = SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT); - - // Postdominators depend on root selection, make sure that a fresh tree - // looks the same. - if (DT.isPostDominator()) - FullRes &= SNCA.IsSameAsFreshTree(DT); + // Common checks to verify the properties of the tree. O(N log N) at worst + if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) || + !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT)) + return false; - return FullRes; - } - } + // Extra checks depending on VerificationLevel. Up to O(N^3) + if (VL == DomTreeT::VerificationLevel::Basic || + VL == DomTreeT::VerificationLevel::Full) + if (!SNCA.verifyParentProperty(DT)) + return false; + if (VL == DomTreeT::VerificationLevel::Full) + if (!SNCA.verifySiblingProperty(DT)) + return false; - llvm_unreachable("Unhandled DomTree VerificationLevel"); + return true; } } // namespace DomTreeBuilder Index: lib/Analysis/PostDominators.cpp =================================================================== --- lib/Analysis/PostDominators.cpp +++ lib/Analysis/PostDominators.cpp @@ -21,6 +21,12 @@ #define DEBUG_TYPE "postdomtree" +#ifdef EXPENSIVE_CHECKS +static constexpr bool ExpensiveChecksEnabled = true; +#else +static constexpr bool ExpensiveChecksEnabled = false; +#endif + //===----------------------------------------------------------------------===// // PostDominatorTree Implementation //===----------------------------------------------------------------------===// @@ -44,6 +50,13 @@ return false; } +void PostDominatorTreeWrapperPass::verifyAnalysis() const { + if (VerifyDomInfo) + assert(DT.verify(PostDominatorTree::VerificationLevel::Full)); + else if (ExpensiveChecksEnabled) + assert(DT.verify(PostDominatorTree::VerificationLevel::Basic)); +} + void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { DT.print(OS); } Index: lib/CodeGen/MachineDominators.cpp =================================================================== --- lib/CodeGen/MachineDominators.cpp +++ lib/CodeGen/MachineDominators.cpp @@ -65,8 +65,21 @@ } void MachineDominatorTree::verifyAnalysis() const { - if (DT && VerifyMachineDomInfo) - verifyDomTree(); + if (DT && VerifyMachineDomInfo) { + MachineFunction &F = *getRoot()->getParent(); + + DomTreeBase OtherDT; + OtherDT.recalculate(F); + if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() || + DT->compare(OtherDT)) { + errs() << "MachineDominatorTree for function " << F.getName() + << " is not up to date!\nComputed:\n"; + DT->print(errs()); + errs() << "\nActual:\n"; + OtherDT.print(errs()); + abort(); + } + } } void MachineDominatorTree::print(raw_ostream &OS, const Module*) const { @@ -138,21 +151,3 @@ NewBBs.clear(); CriticalEdgesToSplit.clear(); } - -void MachineDominatorTree::verifyDomTree() const { - if (!DT) - return; - MachineFunction &F = *getRoot()->getParent(); - - DomTreeBase OtherDT; - OtherDT.recalculate(F); - if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() || - DT->compare(OtherDT)) { - errs() << "MachineDominatorTree for function " << F.getName() - << " is not up to date!\nComputed:\n"; - DT->print(errs()); - errs() << "\nActual:\n"; - OtherDT.print(errs()); - abort(); - } -} Index: lib/IR/Dominators.cpp =================================================================== --- lib/IR/Dominators.cpp +++ lib/IR/Dominators.cpp @@ -306,23 +306,6 @@ return isReachableFromEntry(I->getParent()); } -void DominatorTree::verifyDomTree() const { - // Perform the expensive checks only when VerifyDomInfo is set. - VerificationLevel VL = VerificationLevel::Fast; - if (VerifyDomInfo) - VL = VerificationLevel::Full; - else if (ExpensiveChecksEnabled) - VL = VerificationLevel::Basic; - - if (!verify(VL)) { - errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n"; - errs() << "\nCFG:\n"; - getRoot()->getParent()->print(errs()); - errs().flush(); - abort(); - } -} - //===----------------------------------------------------------------------===// // DominatorTreeAnalysis and related pass implementations //===----------------------------------------------------------------------===// @@ -353,8 +336,7 @@ PreservedAnalyses DominatorTreeVerifierPass::run(Function &F, FunctionAnalysisManager &AM) { - AM.getResult(F).verifyDomTree(); - + assert(AM.getResult(F).verify()); return PreservedAnalyses::all(); } @@ -377,8 +359,10 @@ } void DominatorTreeWrapperPass::verifyAnalysis() const { - if (ExpensiveChecksEnabled || VerifyDomInfo) - DT.verifyDomTree(); + if (VerifyDomInfo) + assert(DT.verify(DominatorTree::VerificationLevel::Full)); + else if (ExpensiveChecksEnabled) + assert(DT.verify(DominatorTree::VerificationLevel::Basic)); } void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { Index: lib/Transforms/Scalar/LoopDistribute.cpp =================================================================== --- lib/Transforms/Scalar/LoopDistribute.cpp +++ lib/Transforms/Scalar/LoopDistribute.cpp @@ -780,7 +780,7 @@ if (LDistVerify) { LI->verify(*DT); - DT->verifyDomTree(); + assert(DT->verify(DominatorTree::VerificationLevel::Fast)); } ++NumLoopsDistributed; Index: lib/Transforms/Scalar/SimpleLoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -637,7 +637,7 @@ BranchInst::Create(CommonSuccBB, BB); } - DT.verifyDomTree(); + assert(DT.verify(DominatorTree::VerificationLevel::Fast)); ++NumTrivial; ++NumSwitches; return true; @@ -2079,11 +2079,9 @@ NonTrivialUnswitchCB)) return PreservedAnalyses::all(); -#ifndef NDEBUG // Historically this pass has had issues with the dominator tree so verify it // in asserts builds. - AR.DT.verifyDomTree(); -#endif + assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast)); return getLoopPassPreservedAnalyses(); } @@ -2147,11 +2145,10 @@ // loop. LPM.deleteSimpleAnalysisLoop(L); -#ifndef NDEBUG // Historically this pass has had issues with the dominator tree so verify it // in asserts builds. - DT.verifyDomTree(); -#endif + assert(DT.verify(DominatorTree::VerificationLevel::Fast)); + return Changed; } Index: lib/Transforms/Utils/LibCallsShrinkWrap.cpp =================================================================== --- lib/Transforms/Utils/LibCallsShrinkWrap.cpp +++ lib/Transforms/Utils/LibCallsShrinkWrap.cpp @@ -529,10 +529,7 @@ bool Changed = CCDCE.perform(); // Verify the dominator after we've updated it locally. -#ifndef NDEBUG - if (DT) - DT->verifyDomTree(); -#endif + assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast)); return Changed; } Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -769,8 +769,8 @@ } } - if (DT && UnrollVerifyDomtree) - DT->verifyDomTree(); + assert(!DT || !UnrollVerifyDomtree || + DT->verify(DominatorTree::VerificationLevel::Fast)); // Merge adjacent basic blocks, if possible. SmallPtrSet ForgottenLoops; Index: lib/Transforms/Utils/LoopUnrollPeel.cpp =================================================================== --- lib/Transforms/Utils/LoopUnrollPeel.cpp +++ lib/Transforms/Utils/LoopUnrollPeel.cpp @@ -500,10 +500,7 @@ // the original loop body. if (Iter == 0) DT->changeImmediateDominator(Exit, cast(LVMap[Latch])); -#ifndef NDEBUG - if (VerifyDomInfo) - DT->verifyDomTree(); -#endif + assert(DT->verify(DominatorTree::VerificationLevel::Fast)); } updateBranchWeights(InsertBot, cast(VMap[LatchBR]), Iter, Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -4777,7 +4777,7 @@ DT->addNewBlock(LoopScalarPreHeader, LoopBypassBlocks[0]); DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader); DT->changeImmediateDominator(LoopExitBlock, LoopBypassBlocks[0]); - DEBUG(DT->verifyDomTree()); + assert(DT->verify(DominatorTree::VerificationLevel::Fast)); } /// \brief Check whether it is safe to if-convert this phi node. Index: unittests/IR/DominatorTreeTest.cpp =================================================================== --- unittests/IR/DominatorTreeTest.cpp +++ unittests/IR/DominatorTreeTest.cpp @@ -264,14 +264,14 @@ EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); // Change root node - DT->verifyDomTree(); + EXPECT_TRUE(DT->verify()); BasicBlock *NewEntry = BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); BranchInst::Create(BB0, NewEntry); EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); EXPECT_TRUE(&F.getEntryBlock() == NewEntry); DT->setNewRoot(NewEntry); - DT->verifyDomTree(); + EXPECT_TRUE(DT->verify()); }); } Index: unittests/Transforms/Scalar/LoopPassManagerTest.cpp =================================================================== --- unittests/Transforms/Scalar/LoopPassManagerTest.cpp +++ unittests/Transforms/Scalar/LoopPassManagerTest.cpp @@ -962,7 +962,7 @@ AR.DT.addNewBlock(NewLoop010PHBB, &Loop01BB); AR.DT.addNewBlock(NewLoop010BB, NewLoop010PHBB); AR.DT.addNewBlock(NewLoop01LatchBB, NewLoop010BB); - AR.DT.verifyDomTree(); + EXPECT_TRUE(AR.DT.verify()); L.addBasicBlockToLoop(NewLoop010PHBB, AR.LI); NewLoop->addBasicBlockToLoop(NewLoop010BB, AR.LI); L.addBasicBlockToLoop(NewLoop01LatchBB, AR.LI); @@ -1004,7 +1004,7 @@ AR.DT.addNewBlock(NewLoop011PHBB, NewLoop010BB); auto *NewDTNode = AR.DT.addNewBlock(NewLoop011BB, NewLoop011PHBB); AR.DT.changeImmediateDominator(AR.DT[NewLoop01LatchBB], NewDTNode); - AR.DT.verifyDomTree(); + EXPECT_TRUE(AR.DT.verify()); L.addBasicBlockToLoop(NewLoop011PHBB, AR.LI); NewLoop->addBasicBlockToLoop(NewLoop011BB, AR.LI); NewLoop->verifyLoop(); @@ -1149,7 +1149,7 @@ AR.DT.addNewBlock(NewLoop01PHBB, &Loop00BB); auto *NewDTNode = AR.DT.addNewBlock(NewLoop01BB, NewLoop01PHBB); AR.DT.changeImmediateDominator(AR.DT[&Loop02PHBB], NewDTNode); - AR.DT.verifyDomTree(); + EXPECT_TRUE(AR.DT.verify()); L.getParentLoop()->addBasicBlockToLoop(NewLoop01PHBB, AR.LI); NewLoop->addBasicBlockToLoop(NewLoop01BB, AR.LI); L.getParentLoop()->verifyLoop(); @@ -1216,7 +1216,7 @@ AR.DT.addNewBlock(NewLoop040PHBB, NewLoop04BB); AR.DT.addNewBlock(NewLoop040BB, NewLoop040PHBB); AR.DT.addNewBlock(NewLoop04LatchBB, NewLoop040BB); - AR.DT.verifyDomTree(); + EXPECT_TRUE(AR.DT.verify()); L.getParentLoop()->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); NewLoops[0]->addBasicBlockToLoop(NewLoop03BB, AR.LI); L.getParentLoop()->addBasicBlockToLoop(NewLoop04PHBB, AR.LI); @@ -1271,7 +1271,7 @@ AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB); auto *NewDTNode = AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB); AR.DT.changeImmediateDominator(AR.DT[&Loop2PHBB], NewDTNode); - AR.DT.verifyDomTree(); + EXPECT_TRUE(AR.DT.verify()); NewLoop->addBasicBlockToLoop(NewLoop1BB, AR.LI); NewLoop->verifyLoop(); Updater.addSiblingLoops({NewLoop}); @@ -1508,7 +1508,7 @@ AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB); AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], AR.DT[NewLoop03BB]); - AR.DT.verifyDomTree(); + EXPECT_TRUE(AR.DT.verify()); ParentL->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); NewSibling->addBasicBlockToLoop(NewLoop03BB, AR.LI); NewSibling->verifyLoop();