[MachineDominatorTree] Add a verifier for the MDT. NFC.

[mcrosier]

Summary

For the most part, this mirrors the verified for the IR level Dominator tree.

By default the verifier is off until we can make sure the MDT is being properly preserved. Once any/all issues have been address we should default 'VerifyMachineDomInfo' to true when expensive checks are enabled.

I still need to add test cases, which will soon follow. This is done by adding '-verify-machine-dom-info' to a RUN command for an existing (or new) lit test.

Hopefully, this will help shake out any bugs.

Chad

[mcrosier]

-Add a test case.

llvm/trunk/include/llvm/CodeGen/MachineDominators.h

public:
   /// block of the function containing it.
   bool isReachableFromEntry(const MachineBasicBlock *A) {
     applySplitCriticalEdges();
     return DT->isReachableFromEntry(A);
   }
 
   void releaseMemory() override;
 
+  void verifyAnalysis() const override;
+
   void print(raw_ostream &OS, const Module*) const override;
 
   /// \brief Record that the critical edge (FromBB, ToBB) has been
   /// split with NewBB.
   /// This is best to use this method instead of directly update the
   /// underlying information, because this helps mitigating the
   /// number of time the DT information is invalidated.
   ///
   /// \note Do not use this method with regular edges.
   ///
   /// \note To benefit from the compile time improvement incurred by this
   /// method, the users of this method have to limit the queries to the DT
   /// interface between two edges splitting. In other words, they have to
   /// pack the splitting of critical edges as much as possible.
   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 Returns *false* if the other dominator tree matches this dominator
+  /// tree.
+  inline bool compare(const MachineDominatorTree &Other) const {
+    const MachineDomTreeNode *R = getRootNode();
+    const MachineDomTreeNode *OtherR = Other.getRootNode();
+
+    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
+      return true;
+
+    if (DT->compare(*Other.DT))
+      return true;
+
+    return false;
+  }
+
+  /// \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>

llvm/trunk/lib/CodeGen/MachineDominators.cpp

 // This file implements simple dominator construction algorithms for finding
 // forward dominators on machine functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/SmallBitVector.h"
+#include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
+// FIXME: Always verify dominfo if expensive checking is enabled.
+#ifdef EXPENSIVE_CHECKS
+static bool VerifyMachineDomInfo = false;
+#else
+static bool VerifyMachineDomInfo = false;
+#endif
+static cl::opt<bool, true> VerifyMachineDomInfoX(
+    "verify-machine-dom-info", cl::location(VerifyMachineDomInfo),
+    cl::desc("Verify machine dominator info (time consuming)"));
+
 namespace llvm {
 template class DomTreeNodeBase<MachineBasicBlock>;
 template class DominatorTreeBase<MachineBasicBlock>;
 }
 
 char MachineDominatorTree::ID = 0;
 
 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",

 MachineDominatorTree::~MachineDominatorTree() {
   delete DT;
 }
 
 void MachineDominatorTree::releaseMemory() {
   DT->releaseMemory();
 }
 
+void MachineDominatorTree::verifyAnalysis() const {
+  if (VerifyMachineDomInfo)
+    verifyDomTree();
+}
+
 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
   DT->print(OS);
 }
 
 void MachineDominatorTree::applySplitCriticalEdges() const {
   // Bail out early if there is nothing to do.
   if (CriticalEdgesToSplit.empty())
     return;
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 {
+  MachineFunction &F = *getRoot()->getParent();
+
+  MachineDominatorTree OtherDT;
+  OtherDT.DT->recalculate(F);
+  if (compare(OtherDT)) {
+    errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
+    print(errs(), nullptr);
+    errs() << "\nActual:\n";
+    OtherDT.print(errs(), nullptr);
+    abort();
+  }
+}

llvm/trunk/test/CodeGen/AArch64/tailmerging_in_mbp.ll

-; RUN: llc <%s -march=aarch64 | FileCheck %s
+; RUN: llc <%s -march=aarch64 -verify-machine-dom-info | FileCheck %s
 
 ; CHECK-LABEL: test:
 ; CHECK:       LBB0_7:
 ; CHECK:         b.hi 
 ; CHECK-NEXT:    b  
 ; CHECK-NEXT:  LBB0_8:
 ; CHECK-NEXT:    mov   x8, x9
 ; CHECK-NEXT:  LBB0_9: