[Dominators] Remove verifyDomTree and add some verifying for Post Dom Trees

[dmgreen]

Summary

Removes verifyDomTree, using assert(verify()) everywhere instead. Also changes verify a little to always run IsSameAsFreshTree first, in order to print good output when we find errors. Then add verifyAnalysis for PostDomTrees. This will allow checking of PostDomTrees it the same way we check DomTrees and MachineDomTrees.

[davide]

should this be guarded by another flag temporarily?

Thanks!

Davide

lib/Analysis/PostDominators.cpp

48

verifyPostDomTree?

51

PostDomTree verification failed?

[dmgreen]

Hello. Sorry for the delay.

I have left this as verifyDomTree and using VerifyDomInfo to keep things consistent between the two dom trees. I can change this if you think it is best, but personally like the idea of treating the two trees similarly. Let me know what you think.

[kuhar]

My impression was that DT.verifyDomTree() was mostly there for legacy reasons, as it doesn't verify that the tree is correct or that it's even constructed correctly. It has historically been quite cheap, so some passes thought they can use it in asserts, and because of this we cannot replace it with DT.verify(), as it can blow up in pathological cases (O(N^3)).

I am more and more convinced that verifyDomTree() should be replaced altogether with two or three checks:

• full verification as it is today in .verify(), used when -verify-dom-info is passes.
• partial verification: reachability, roots, parent property, dfs numbers, and comparison with a freshly build tree. This would be O(N^2), just like verifyDomTree() now, but probably a bit slower in practise. This would be used with EXPENSIVE_CHECKS and in verifyAnalysis.
• 'light' version: reachability, roots, dfs numbers, and comparison with a freshly build tree. This would be used with asserts in passes, instead of verifyDomTree(). This is should take about the same time ass the current implementation.

If we moved forward in this direction, all what DomTree and PostDomTree would have to implement would be essentially:

PostDominatorTree::verifyDomTree() const { assert(verify(CheckLevel::Light)); }

[kuhar]

I went ahead and made a patch for having different levels of verification: D42337

[dmgreen]

Nice. Like it. I'll rebase this on that, once it's in.

[kuhar]

The verification levels are landed as of r323298.

[dmgreen]

Rebase!

[kuhar]

include/llvm/Analysis/PostDominators.h

41

I don't think it's a good idea to expose it externally. For debugging, you can just do assert(PDT.verify()).
The problem I see is that people will call it not realizing that it doesn't perform full verification and does not check each property individually, resulting in worse errors than plain PDT.verify().

I think we should just keep it internal and only use in verifyAnalysis, or just inline it there.

include/llvm/IR/Dominators.h

176–177

Here, I think we should change the docs to say that this is a legacy debugging function, and point users to DT.verify instead. When we first introduced the new verifiers, I completely replaced verifyDomTree with verify, but then realized that people use it in regular passes in debug builds and expect it to be fast.

With the new verification levels, I think it would be better to either completely replace all uses with DT.verify(Fast), or just keep it as a wrapper around .verify() that only prints CFG upon failure and asserts.
(This doesn't mean it propose to do all of it in one patch.)

[dmgreen]

include/llvm/Analysis/PostDominators.h

41

Interesting. I think there is value in keeping dom/postdom trees equivalent, whatever we end up doing.

My understanding is that there are two different usecases for checking the dom tree. There's the case for people like yourself who are writing the domtree construction code. This need good quality checks that are hard to do, and that check various properties of the tree are correct.

Then there's guys who are just trying to use the domtree updater to preserve the tree across passes. Here you can almost always presume that a newly calculated tree is correct. In my experience, the best error message says "The tree should look like -this-, but you made it look like -this!-". Messages like "node %x is not reachable when it's sibling %y is removed", whilst I can see the value in being more succinct (and better tests of the tree), they are often not as useful as being able to eyeball the difference between two trees and notice that y is in the wrong place.

So this may just be a difference in what we use these for. And may just be my two cents :) I found the error messages coming out of verifyDomTree often quite useful. That said, I have not used it it any code anywhere, just whilst debugging. And like you say, perhaps assert(DT.verify(Fast)) is a better option for this (the CFG output can be a bit noisy :) )

So having said all that.. (comment below)

include/llvm/IR/Dominators.h

176–177

Yeah, I think this sounds best. Removing verifyDomTree entirely and just using verify everywhere we need it. I can probably do that pretty quickly, it's just a fairly mechanical change of replacing one function call with another.

[kuhar]

include/llvm/Analysis/PostDominators.h

41

So instead, we could just add a fresh domtree printing upon error to verify(). I mean, this is what people usually do manually when they debug these things. The current error messages coming from verify() are usually quite concise, so I think it makes sense to just make it print a freshly constructed tree below in addition to that.

[dmgreen]

Updates. What do you think?

This exposes a bug in the DominatorTree.InsertReachable2 test that we need to sort. We may need something like this, I'm not 100%:

diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index 172efb5..53387db 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -697,25 +697,22 @@ struct SemiNCAInfo {
         }))
       return;
 
+
     // Recalculate the set of roots.
-    DT.Roots = FindRoots(DT, BUI);
-    for (const NodePtr R : DT.Roots) {
-      const TreeNodePtr TN = DT.getNode(R);
-      // A CFG node was selected as a tree root, but the corresponding tree node
-      // is not connected to the virtual root. This is because the incremental
+    auto Roots = FindRoots(DT, BUI);
+    if (DT.Roots.size() != Roots.size() ||
+        !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
+        Roots.begin())) {
+      // The roots chosen in the CFG have changed. This is because the incremental
       // algorithm does not really know or use the set of roots and can make a
       // different (implicit) decision about which nodes within an infinite loop
       // becomes a root.
-      if (TN && !DT.isVirtualRoot(TN->getIDom())) {
-        DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
-                     << " is not virtual root's child\n"
-                     << "The entire tree needs to be rebuilt\n");
-        // It should be possible to rotate the subtree instead of recalculating
-        // the whole tree, but this situation happens extremely rarely in
-        // practice.
-        CalculateFromScratch(DT, BUI);
-        return;
-      }
+      DEBUG(dbgs() << "Roots are different in updated trees\n"
+                   << "The entire tree needs to be rebuilt\n");
+      // It may be possible to rotate the subtree instead of recalculating
+      // the whole tree, but this situation happens extremely rarely in
+      // practice.
+      CalculateFromScratch(DT, BUI);
     }
   }

[kuhar]

This is blocked by the incorrect postdominators roots after insertion bug you discovered, right?

[dmgreen]

Hello

Sorry, other stuff has been keeping me busy :) From what I understand, both the old and the new code was wrong for when we force a recalc of the postdomtree, based on when the roots change.

This InsertReachable2 test, if I remember correctly, has three roots before the update:
"6" - a normal exit/no successor node
"9" - an infinite loop
"2" - the common descendant of both.
After the insert, the infinite loop becomes (reverse-)reachable from 6, so the 9 and 2 nodes are no longer roots. But the tree was updated with the implicit assumption that they were connected to the virtual root, so the tree is wrong and needs a recalc.

We update the roots to just "6", check that it has a virtual base (it does) so decide not to recalc. The old code would check and do the recalc if it _did_ have a virtual root. I don't think that's what was intended - correct me if I'm wrong. Changing that fixed cases where the tree only had infinite loops as roots, and the root gets changed during the update.

So I think we may need to do the recalc "if the roots have changed". Or scan though the nodes in the tree and recalc if there is a node that has a virtual base, but is not a root. Not 100% sure. My cryptic code in the comment above was a suggestion for the "recalc if the roots have changed" option.

[kuhar]

Hi @dmgreen,

Sorry it took me a while, but I looked at what at the problem with InstertReachable2 and I wasn't able to figure out any other way to end up with correct postdomtree other than recalculating it. I went ahead and used your patch to create a separate revision and put it here: D43140.

[kuhar]

This should be unblocked now.

[dmgreen]

Rebase and a couple of minor edits.

[dmgreen]

include/llvm/Support/GenericDomTree.h

322

Can you check this is correct. This function, unusually, returns false on same, true on different.

[kuhar]

include/llvm/Support/GenericDomTree.h

322

Good catch! Feel free to fix it -- I think you can change this and the next one in a separate commit without review.

[dmgreen]

include/llvm/Support/GenericDomTree.h

322

Thanks. I'll count that as a review :) https://reviews.llvm.org/rL325517

[kuhar]

LGTM

[brzycki]

+1 LGTM as well.

[dmgreen]

Updated with one last fix for release tests. DominatorTreeVerifierPass::run now requests a DomTree, even if asserts are disabled.

include/llvm/Analysis/PostDominators.h

public:
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 };
 
 /// \brief Analysis pass which computes a \c PostDominatorTree.
 class PostDominatorTreeAnalysis
     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
 
   static AnalysisKey Key;
 
 public:
   /// \brief Provide the result type for this analysis pass.
   using Result = PostDominatorTree;
 
   /// \brief Run the analysis pass over a function and produce a post dominator
PostDominatorTreeWrapperPass() : FunctionPass(ID) {
     initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
   }
 
   PostDominatorTree &getPostDomTree() { return DT; }
   const PostDominatorTree &getPostDomTree() const { return DT; }
 
   bool runOnFunction(Function &F) override;
 
+  void verifyAnalysis() const override;
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 
   void releaseMemory() override {
     DT.releaseMemory();
   }
 

include/llvm/CodeGen/MachineDominators.h

void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
                               MachineBasicBlock *ToBB,
                               MachineBasicBlock *NewBB) {
     bool Inserted = NewBBs.insert(NewBB).second;
     (void)Inserted;
     assert(Inserted &&
            "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;
 };
 
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
 
 template <class Node, class ChildIterator>

include/llvm/IR/Dominators.h

public:
   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
 
   // Ensure base class overloads are visible.
   using Base::isReachableFromEntry;
 
   /// \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();
 };
 
 //===-------------------------------------
 // DominatorTree GraphTraits specializations so the DominatorTree can be
 // iterable by generic graph iterators.
 

include/llvm/Support/GenericDomTree.h

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;
+      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())
       return true;
 
     for (const auto &DomTreeNode : DomTreeNodes) {
       NodeT *BB = DomTreeNode.first;
       typename DomTreeNodeMapType::const_iterator OI =

include/llvm/Support/GenericDomTreeConstruction.h

#endif
   //
   // 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"
+      errs() << (DT.isPostDominator() ? "Post" : "")
+             << "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;

 void ApplyUpdates(DomTreeT &DT,
                   ArrayRef<typename DomTreeT::UpdateType> Updates) {
   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
 }
 
 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
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif

lib/Analysis/PostDominators.cpp

 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "postdomtree"
 
+#ifdef EXPENSIVE_CHECKS
+static constexpr bool ExpensiveChecksEnabled = true;
+#else
+static constexpr bool ExpensiveChecksEnabled = false;
+#endif
+
 //===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
 char PostDominatorTreeWrapperPass::ID = 0;
 
 INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",
                 "Post-Dominator Tree Construction", true, true)
 
 bool PostDominatorTree::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<PostDominatorTreeAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(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);
 }
 
 FunctionPass* llvm::createPostDomTree() {
   return new PostDominatorTreeWrapperPass();
 }
 

lib/CodeGen/MachineDominators.cpp

 }
 
 void MachineDominatorTree::releaseMemory() {
   CriticalEdgesToSplit.clear();
   DT.reset(nullptr);
 }
 
 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 {
   if (DT)
     DT->print(OS);
 }
 
 void MachineDominatorTree::applySplitCriticalEdges() const {
for (CriticalEdge &Edge : CriticalEdgesToSplit) {
     // the new block doesn't dominate anything.
     if (IsNewIDom[Idx])
       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
     ++Idx;
   }
   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();
-  }
-}

lib/IR/Dominators.cpp

bool DominatorTree::isReachableFromEntry(const Use &U) const {
   // PHI nodes use their operands on their incoming edges.
   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.
-  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
 //===----------------------------------------------------------------------===//
 //
 // This implements the DominatorTreeAnalysis which is used with the new pass
 // manager. It also implements some methods from utility passes.
 //
 //===----------------------------------------------------------------------===//
PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
   OS << "DominatorTree for function: " << F.getName() << "\n";
   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
 
   return PreservedAnalyses::all();
 }
 
 PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
-  AM.getResult<DominatorTreeAnalysis>(F).verifyDomTree();
-
+  assert(AM.getResult<DominatorTreeAnalysis>(F).verify());
   return PreservedAnalyses::all();
 }
 
 //===----------------------------------------------------------------------===//
 //  DominatorTreeWrapperPass Implementation
 //===----------------------------------------------------------------------===//
 //
 // The implementation details of the wrapper pass that holds a DominatorTree
 // suitable for use with the legacy pass manager.
 //
 //===----------------------------------------------------------------------===//
 
 char DominatorTreeWrapperPass::ID = 0;
 INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
                 "Dominator Tree Construction", true, true)
 
 bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(F);
   return false;
 }
 
 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 {
   DT.print(OS);
 }
 
 //===----------------------------------------------------------------------===//
 //  DeferredDominance Implementation

lib/Transforms/Scalar/LoopDistribute.cpp

bool processLoop(std::function<const LoopAccessInfo &(Loop &)> &GetLAA) {
     // Now, we remove the instruction from each loop that don't belong to that
     // partition.
     Partitions.removeUnusedInsts();
     DEBUG(dbgs() << "\nAfter removing unused Instrs:\n");
     DEBUG(Partitions.printBlocks());
 
     if (LDistVerify) {
       LI->verify(*DT);
-      DT->verifyDomTree();
+      assert(DT->verify(DominatorTree::VerificationLevel::Fast));
     }
 
     ++NumLoopsDistributed;
     // Report the success.
     ORE->emit([&]() {
       return OptimizationRemark(LDIST_NAME, "Distribute", L->getStartLoc(),
                                 L->getHeader())
              << "distributed loop";

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
   // to recognize. Otherwise we potentially have to recognize the default case
   // pointing at unreachable and other complexity.
   if (CommonSuccBB) {
     BasicBlock *BB = SI.getParent();
     SI.eraseFromParent();
     BranchInst::Create(CommonSuccBB, BB);
   }
 
-  DT.verifyDomTree();
+  assert(DT.verify(DominatorTree::VerificationLevel::Fast));
   ++NumTrivial;
   ++NumSwitches;
   return true;
 }
 
 /// This routine scans the loop to find a branch or switch which occurs before
 /// any side effects occur. These can potentially be unswitched without
 /// duplicating the loop. If a branch or switch is successfully unswitched the
auto NonTrivialUnswitchCB = [&L, &U, &LoopName](bool CurrentLoopValid,
     else
       U.markLoopAsDeleted(L, LoopName);
   };
 
   if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC, AR.TTI, NonTrivial,
                     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();
 }
 
 namespace {
 
 class SimpleLoopUnswitchLegacyPass : public LoopPass {
   bool NonTrivial;
 
bool SimpleLoopUnswitchLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   bool Changed =
       unswitchLoop(*L, DT, LI, AC, TTI, NonTrivial, NonTrivialUnswitchCB);
 
   // If anything was unswitched, also clear any cached information about this
   // 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;
 }
 
 char SimpleLoopUnswitchLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch",
                       "Simple unswitch loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)

lib/Transforms/Utils/LibCallsShrinkWrap.cpp

static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
                     DominatorTree *DT) {
   if (F.hasFnAttribute(Attribute::OptimizeForSize))
     return false;
   LibCallsShrinkWrap CCDCE(TLI, DT);
   CCDCE.visit(F);
   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;
 }
 
 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) {
   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
   return runImpl(F, TLI, DT);

lib/Transforms/Utils/LoopUnroll.cpp

for (auto *BB : OriginalLoopBlocks) {
         // which dominates all copies of the previous idom.
         NewIDom = DT->findNearestCommonDominator(BB, LatchBlock);
       }
       for (auto *ChildBB : ChildrenToUpdate)
         DT->changeImmediateDominator(ChildBB, NewIDom);
     }
   }
 
-  if (DT && UnrollVerifyDomtree)
-    DT->verifyDomTree();
+  assert(!DT || !UnrollVerifyDomtree ||
+      DT->verify(DominatorTree::VerificationLevel::Fast));
 
   // Merge adjacent basic blocks, if possible.
   SmallPtrSet<Loop *, 4> ForgottenLoops;
   for (BasicBlock *Latch : Latches) {
     BranchInst *Term = cast<BranchInst>(Latch->getTerminator());
     if (Term->isUnconditional()) {
       BasicBlock *Dest = Term->getSuccessor(0);
       if (BasicBlock *Fold =

lib/Transforms/Utils/LoopUnrollPeel.cpp

for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
     remapInstructionsInBlocks(NewBlocks, VMap);
 
     if (DT) {
       // Latches of the cloned loops dominate over the loop exit, so idom of the
       // latter is the first cloned loop body, as original PreHeader dominates
       // 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,
                         PeelCount, ExitWeight);
 
     InsertTop = InsertBot;
     InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
     InsertBot->setName(Header->getName() + ".peel.next");

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::updateAnalysis() {
   assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
          "Entry does not dominate exit.");
 
   DT->addNewBlock(LoopMiddleBlock,
                   LI->getLoopFor(LoopVectorBody)->getLoopLatch());
   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.
 ///
 /// Phi nodes with constant expressions that can trap are not safe to if
 /// convert.
 static bool canIfConvertPHINodes(BasicBlock *BB) {
   for (PHINode &Phi : BB->phis()) {

unittests/IR/DominatorTreeTest.cpp

runWithDomTree(
         // Check levels after
         EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U);
         EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U);
         EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U);
         EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U);
         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());
       });
 }
 
 TEST(DominatorTree, NonUniqueEdges) {
   StringRef ModuleString =
       "define i32 @f(i32 %i, i32 *%p) {\n"
       "bb0:\n"
       "   store i32 %i, i32 *%p\n"

unittests/Transforms/Scalar/LoopPassManagerTest.cpp

EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
         Loop01BB.getTerminator()->replaceUsesOfWith(&Loop01BB, NewLoop010PHBB);
         BranchInst::Create(NewLoop010BB, NewLoop010PHBB);
         CreateCondBr(NewLoop01LatchBB, NewLoop010BB, "cond.0.1.0",
                      NewLoop010BB);
         BranchInst::Create(&Loop01BB, NewLoop01LatchBB);
         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);
         NewLoop->verifyLoop();
         L.verifyLoop();
         Updater.addChildLoops({NewLoop});
         return PreservedAnalyses::all();
       }));
EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
         NewLoop010BB->getTerminator()->replaceUsesOfWith(NewLoop01LatchBB,
                                                          NewLoop011PHBB);
         BranchInst::Create(NewLoop011BB, NewLoop011PHBB);
         CreateCondBr(NewLoop01LatchBB, NewLoop011BB, "cond.0.1.1",
                      NewLoop011BB);
         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();
         L.verifyLoop();
         Updater.addChildLoops({NewLoop});
         return PreservedAnalyses::all();
       }));
 
EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
         auto *NewLoop01PHBB = BasicBlock::Create(Context, "loop.0.1.ph", &F, &Loop02PHBB);
         auto *NewLoop01BB = BasicBlock::Create(Context, "loop.0.1", &F, &Loop02PHBB);
         BranchInst::Create(NewLoop01BB, NewLoop01PHBB);
         CreateCondBr(&Loop02PHBB, NewLoop01BB, "cond.0.1", NewLoop01BB);
         Loop00BB.getTerminator()->replaceUsesOfWith(&Loop02PHBB, NewLoop01PHBB);
         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();
         Updater.addSiblingLoops({NewLoop});
         return PreservedAnalyses::all();
       }));
   // We finish processing this loop as sibling loops don't perturb the
   // postorder walk.
EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
         AR.DT.addNewBlock(NewLoop03PHBB, &Loop02BB);
         AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB);
         AR.DT.addNewBlock(NewLoop04PHBB, NewLoop03BB);
         auto *NewDTNode = AR.DT.addNewBlock(NewLoop04BB, NewLoop04PHBB);
         AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], NewDTNode);
         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);
         NewLoops[1]->addBasicBlockToLoop(NewLoop04BB, AR.LI);
         NewLoops[1]->addBasicBlockToLoop(NewLoop040PHBB, AR.LI);
         NewLoops[2]->addBasicBlockToLoop(NewLoop040BB, AR.LI);
         NewLoops[1]->addBasicBlockToLoop(NewLoop04LatchBB, AR.LI);
         L.getParentLoop()->verifyLoop();
EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
         auto *NewLoop1PHBB = BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2BB);
         auto *NewLoop1BB = BasicBlock::Create(Context, "loop.1", &F, &Loop2BB);
         BranchInst::Create(NewLoop1BB, NewLoop1PHBB);
         CreateCondBr(&Loop2PHBB, NewLoop1BB, "cond.1", NewLoop1BB);
         Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB);
         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});
         return PreservedAnalyses::all();
       }));
   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
       .WillOnce(Invoke(getLoopAnalysisResult));
 
EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
                                       NewLoop03BB);
             BranchInst::Create(&Loop0LatchBB, NewLoop03BB, Cond, NewLoop03BB);
             Loop02PHBB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB,
                                                           NewLoop03PHBB);
             AR.DT.addNewBlock(NewLoop03PHBB, &Loop02PHBB);
             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();
             ParentL->verifyLoop();
             Updater.addSiblingLoops({NewSibling});
             return PreservedAnalyses::all();
           }));