summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/PostDominators.h2
-rw-r--r--llvm/include/llvm/CodeGen/MachineDominators.h6
-rw-r--r--llvm/include/llvm/IR/Dominators.h6
-rw-r--r--llvm/include/llvm/Support/GenericDomTreeConstruction.h42
-rw-r--r--llvm/lib/Analysis/PostDominators.cpp13
-rw-r--r--llvm/lib/CodeGen/MachineDominators.cpp35
-rw-r--r--llvm/lib/IR/Dominators.cpp28
-rw-r--r--llvm/lib/Transforms/Scalar/LoopDistribute.cpp2
-rw-r--r--llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp11
-rw-r--r--llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp5
-rw-r--r--llvm/lib/Transforms/Utils/LoopUnroll.cpp4
-rw-r--r--llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp5
-rw-r--r--llvm/lib/Transforms/Vectorize/LoopVectorize.cpp2
-rw-r--r--llvm/unittests/IR/DominatorTreeTest.cpp4
-rw-r--r--llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp12
15 files changed, 73 insertions, 104 deletions
diff --git a/llvm/include/llvm/Analysis/PostDominators.h b/llvm/include/llvm/Analysis/PostDominators.h
index 90de6bef42a..9a8c4d7807d 100644
--- a/llvm/include/llvm/Analysis/PostDominators.h
+++ b/llvm/include/llvm/Analysis/PostDominators.h
@@ -76,6 +76,8 @@ struct PostDominatorTreeWrapperPass : public FunctionPass {
bool runOnFunction(Function &F) override;
+ void verifyAnalysis() const override;
+
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();
}
diff --git a/llvm/include/llvm/CodeGen/MachineDominators.h b/llvm/include/llvm/CodeGen/MachineDominators.h
index 98fdb51aae2..af642d9cfc9 100644
--- a/llvm/include/llvm/CodeGen/MachineDominators.h
+++ b/llvm/include/llvm/CodeGen/MachineDominators.h
@@ -249,12 +249,6 @@ public:
"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;
};
//===-------------------------------------
diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h
index f41200283a4..f6811bc4470 100644
--- a/llvm/include/llvm/IR/Dominators.h
+++ b/llvm/include/llvm/IR/Dominators.h
@@ -174,12 +174,6 @@ class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
/// \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();
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
index 7524733b36b..7ec0638ad6e 100644
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -1602,7 +1602,8 @@ struct SemiNCAInfo {
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 +1643,27 @@ void ApplyUpdates(DomTreeT &DT,
template <class DomTreeT>
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
SemiNCAInfo<DomTreeT> 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
diff --git a/llvm/lib/Analysis/PostDominators.cpp b/llvm/lib/Analysis/PostDominators.cpp
index 2282401085d..8ccba689ec5 100644
--- a/llvm/lib/Analysis/PostDominators.cpp
+++ b/llvm/lib/Analysis/PostDominators.cpp
@@ -21,6 +21,12 @@ using namespace llvm;
#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 @@ bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
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);
}
diff --git a/llvm/lib/CodeGen/MachineDominators.cpp b/llvm/lib/CodeGen/MachineDominators.cpp
index 517ac29b645..6b280262645 100644
--- a/llvm/lib/CodeGen/MachineDominators.cpp
+++ b/llvm/lib/CodeGen/MachineDominators.cpp
@@ -65,8 +65,21 @@ void MachineDominatorTree::releaseMemory() {
}
void MachineDominatorTree::verifyAnalysis() const {
- if (DT && VerifyMachineDomInfo)
- verifyDomTree();
+ if (DT && VerifyMachineDomInfo) {
+ MachineFunction &F = *getRoot()->getParent();
+
+ DomTreeBase<MachineBasicBlock> 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 @@ void MachineDominatorTree::applySplitCriticalEdges() const {
NewBBs.clear();
CriticalEdgesToSplit.clear();
}
-
-void MachineDominatorTree::verifyDomTree() const {
- if (!DT)
- return;
- MachineFunction &F = *getRoot()->getParent();
-
- DomTreeBase<MachineBasicBlock> 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();
- }
-}
diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index 1429e1b9060..24b6c47d0fd 100644
--- a/llvm/lib/IR/Dominators.cpp
+++ b/llvm/lib/IR/Dominators.cpp
@@ -306,23 +306,6 @@ bool DominatorTree::isReachableFromEntry(const Use &U) const {
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,9 @@ PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
FunctionAnalysisManager &AM) {
- AM.getResult<DominatorTreeAnalysis>(F).verifyDomTree();
-
+ auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+ assert(DT.verify());
+ (void)DT;
return PreservedAnalyses::all();
}
@@ -377,8 +361,10 @@ bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
}
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 {
diff --git a/llvm/lib/Transforms/Scalar/LoopDistribute.cpp b/llvm/lib/Transforms/Scalar/LoopDistribute.cpp
index 0d7e3db901c..2f7b4923b33 100644
--- a/llvm/lib/Transforms/Scalar/LoopDistribute.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopDistribute.cpp
@@ -780,7 +780,7 @@ public:
if (LDistVerify) {
LI->verify(*DT);
- DT->verifyDomTree();
+ assert(DT->verify(DominatorTree::VerificationLevel::Fast));
}
++NumLoopsDistributed;
diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
index aba732bc413..e3d2c1702df 100644
--- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
+++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
@@ -637,7 +637,7 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
BranchInst::Create(CommonSuccBB, BB);
}
- DT.verifyDomTree();
+ assert(DT.verify(DominatorTree::VerificationLevel::Fast));
++NumTrivial;
++NumSwitches;
return true;
@@ -2079,11 +2079,9 @@ PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
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 @@ bool SimpleLoopUnswitchLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
// 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;
}
diff --git a/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp b/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp
index 42aca757c2a..80fb9cb1aae 100644
--- a/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp
+++ b/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp
@@ -529,10 +529,7 @@ static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
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;
}
diff --git a/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/llvm/lib/Transforms/Utils/LoopUnroll.cpp
index 92dfb1c7204..d7daf7aba9d 100644
--- a/llvm/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnroll.cpp
@@ -769,8 +769,8 @@ LoopUnrollResult llvm::UnrollLoop(
}
}
- if (DT && UnrollVerifyDomtree)
- DT->verifyDomTree();
+ assert(!DT || !UnrollVerifyDomtree ||
+ DT->verify(DominatorTree::VerificationLevel::Fast));
// Merge adjacent basic blocks, if possible.
SmallPtrSet<Loop *, 4> ForgottenLoops;
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp b/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
index 4642a50ba6d..13749300984 100644
--- a/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
@@ -500,10 +500,7 @@ bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
// the original loop body.
if (Iter == 0)
DT->changeImmediateDominator(Exit, cast<BasicBlock>(LVMap[Latch]));
-#ifndef NDEBUG
- if (VerifyDomInfo)
- DT->verifyDomTree();
-#endif
+ assert(DT->verify(DominatorTree::VerificationLevel::Fast));
}
updateBranchWeights(InsertBot, cast<BranchInst>(VMap[LatchBR]), Iter,
diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
index 963dad5ff20..47a767ccbbe 100644
--- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -4779,7 +4779,7 @@ void InnerLoopVectorizer::updateAnalysis() {
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.
diff --git a/llvm/unittests/IR/DominatorTreeTest.cpp b/llvm/unittests/IR/DominatorTreeTest.cpp
index 6b427d9c30c..d7f77af27b1 100644
--- a/llvm/unittests/IR/DominatorTreeTest.cpp
+++ b/llvm/unittests/IR/DominatorTreeTest.cpp
@@ -264,14 +264,14 @@ TEST(DominatorTree, Unreachable) {
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());
});
}
diff --git a/llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp b/llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp
index 2b8130b9e00..57fb57ec66c 100644
--- a/llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp
+++ b/llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp
@@ -962,7 +962,7 @@ TEST_F(LoopPassManagerTest, LoopChildInsertion) {
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 @@ TEST_F(LoopPassManagerTest, LoopChildInsertion) {
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 @@ TEST_F(LoopPassManagerTest, LoopPeerInsertion) {
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 @@ TEST_F(LoopPassManagerTest, LoopPeerInsertion) {
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 @@ TEST_F(LoopPassManagerTest, LoopPeerInsertion) {
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 @@ TEST_F(LoopPassManagerTest, LoopDeletion) {
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();
OpenPOWER on IntegriCloud