[Dominators] Introduce DomTree verification levels
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`.
Reviewers: dberlin, brzycki, davide, grosser, dmgreen
Reviewed By: dberlin, brzycki
Subscribers: MatzeB, llvm-commits
Differential Revision: https://reviews.llvm.org/D42337
llvm-svn: 323298
diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index e44e845..25e4ce4 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 @@
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 @@
void DominatorTree::verifyDomTree() const {
// Perform the expensive checks only when VerifyDomInfo is set.
- if (VerifyDomInfo && !verify()) {
+ 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";
- print(errs());
- abort();
- }
-
- Function &F = *getRoot()->getParent();
-
- 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());
errs() << "\nCFG:\n";
- F.print(errs());
+ getRoot()->getParent()->print(errs());
errs().flush();
abort();
}
@@ -382,8 +377,8 @@
}
void DominatorTreeWrapperPass::verifyAnalysis() const {
- if (VerifyDomInfo)
- DT.verifyDomTree();
+ if (ExpensiveChecksEnabled || VerifyDomInfo)
+ DT.verifyDomTree();
}
void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {