[Dominators][CodeGen] Clean up MachineDominators

[kuhar]

Summary

This is a cleanup patch for MachineDominatorTree. It would be an NFC, except for replacing custom DomTree verification with the generic one.

[arsenm]

LGTM

[kuhar]

The changes to verifier caught a MDT bug on AArch64:

test/CodeGen/AArch64/tailmerging_in_mbp.ll -mtriple=aarch64-eabi -verify-machine-dom-info 
DominatorTree is different than a freshly computed one!
	Current:
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 25 slow queries.
  [1] %bb.0 {4294967295,4294967295} [0]
    [2] %bb.1 {4294967295,4294967295} [1]
      [3] %bb.2 {4294967295,4294967295} [2]
        [4] %bb.3 {4294967295,4294967295} [3]
          [5] %bb.7 {4294967295,4294967295} [4]
          [5] %bb.4 {4294967295,4294967295} [4]
            [6] %bb.5 {4294967295,4294967295} [5]
              [7] %bb.6 {4294967295,4294967295} [6]
    [2] %bb.8 {4294967295,4294967295} [1]
Roots: %bb.0 

	Freshly computed tree:
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
  [1] %bb.0 {4294967295,4294967295} [0]
    [2] %bb.1 {4294967295,4294967295} [1]
      [3] %bb.2 {4294967295,4294967295} [2]
        [4] %bb.9 {4294967295,4294967295} [3]
        [4] %bb.3 {4294967295,4294967295} [3]
          [5] %bb.7 {4294967295,4294967295} [4]
          [5] %bb.4 {4294967295,4294967295} [4]
            [6] %bb.10 {4294967295,4294967295} [5]
            [6] %bb.5 {4294967295,4294967295} [5]
              [7] %bb.6 {4294967295,4294967295} [6]
                [8] %bb.11 {4294967295,4294967295} [7]
    [2] %bb.8 {4294967295,4294967295} [1]
Roots: %bb.0 
MachineDominatorTree verification failed

Investigating

llvm/include/llvm/CodeGen/MachineDominators.h

 
 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
 
 //===-------------------------------------
 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 /// compute a normal dominator tree.
 ///
 class MachineDominatorTree : public MachineFunctionPass {
+  using DomTreeT = DomTreeBase<MachineBasicBlock>;
+
   /// Helper structure used to hold all the basic blocks
   /// involved in the split of a critical edge.
   struct CriticalEdge {
     MachineBasicBlock *FromBB;
     MachineBasicBlock *ToBB;
     MachineBasicBlock *NewBB;
   };
 
   /// Pile up all the critical edges to be split.
   /// The splitting of a critical edge is local and thus, it is possible
   /// to apply several of those changes at the same time.
   mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
 
   /// Remember all the basic blocks that are inserted during
   /// edge splitting.
   /// Invariant: NewBBs == all the basic blocks contained in the NewBB
   /// field of all the elements of CriticalEdgesToSplit.
   /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
   /// such as BB == elt.NewBB.
   mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
 
-  /// The DominatorTreeBase that is used to compute a normal dominator tree
-  std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT;
+  /// The DominatorTreeBase that is used to compute a normal dominator tree.
+  std::unique_ptr<DomTreeT> DT;
 
   /// Apply all the recorded critical edges to the DT.
   /// This updates the underlying DT information in a way that uses
   /// the fast query path of DT as much as possible.
   ///
   /// \post CriticalEdgesToSplit.empty().
   void applySplitCriticalEdges() const;
 
 public:
   static char ID; // Pass ID, replacement for typeid
 
   MachineDominatorTree();
 
-  DomTreeBase<MachineBasicBlock> &getBase() {
-    if (!DT) DT.reset(new DomTreeBase<MachineBasicBlock>());
+  DomTreeT &getBase() {
+    if (!DT) DT.reset(new DomTreeT());
     applySplitCriticalEdges();
     return *DT;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// getRoots -  Return the root blocks of the current CFG.  This may include
   /// multiple blocks if we are computing post dominators.  For forward
   /// dominators, this will always be a single block (the entry node).
   ///
-  inline const SmallVectorImpl<MachineBasicBlock*> &getRoots() const {
+  const SmallVectorImpl<MachineBasicBlock*> &getRoots() const {
     applySplitCriticalEdges();
     return DT->getRoots();
   }
 
-  inline MachineBasicBlock *getRoot() const {
+  MachineBasicBlock *getRoot() const {
     applySplitCriticalEdges();
     return DT->getRoot();
   }
 
-  inline MachineDomTreeNode *getRootNode() const {
+  MachineDomTreeNode *getRootNode() const {
     applySplitCriticalEdges();
     return DT->getRootNode();
   }
 
   bool runOnMachineFunction(MachineFunction &F) override;
 
-  inline bool dominates(const MachineDomTreeNode* A,
-                        const MachineDomTreeNode* B) const {
+  bool dominates(const MachineDomTreeNode *A,
+                 const MachineDomTreeNode *B) const {
     applySplitCriticalEdges();
     return DT->dominates(A, B);
   }
 
-  inline bool dominates(const MachineBasicBlock* A,
-                        const MachineBasicBlock* B) const {
+  bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
     applySplitCriticalEdges();
     return DT->dominates(A, B);
   }
 
   // dominates - Return true if A dominates B. This performs the
   // special checks necessary if A and B are in the same basic block.
   bool dominates(const MachineInstr *A, const MachineInstr *B) const {
     applySplitCriticalEdges();
     const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
     if (BBA != BBB) return DT->dominates(BBA, BBB);
 
     // Loop through the basic block until we find A or B.
     MachineBasicBlock::const_iterator I = BBA->begin();
     for (; &*I != A && &*I != B; ++I)
       /*empty*/ ;
 
-    //if(!DT.IsPostDominators) {
-      // A dominates B if it is found first in the basic block.
-      return &*I == A;
-    //} else {
-    //  // A post-dominates B if B is found first in the basic block.
-    //  return &*I == B;
-    //}
   }
 
-  inline bool properlyDominates(const MachineDomTreeNode* A,
-                                const MachineDomTreeNode* B) const {
+  bool properlyDominates(const MachineDomTreeNode *A,
+                         const MachineDomTreeNode *B) const {
     applySplitCriticalEdges();
     return DT->properlyDominates(A, B);
   }
 
-  inline bool properlyDominates(const MachineBasicBlock* A,
-                                const MachineBasicBlock* B) const {
+  bool properlyDominates(const MachineBasicBlock *A,
+                         const MachineBasicBlock *B) const {
     applySplitCriticalEdges();
     return DT->properlyDominates(A, B);
   }
 
   /// findNearestCommonDominator - Find nearest common dominator basic block
   /// for basic block A and B. If there is no such block then return NULL.
-  inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
-                                                       MachineBasicBlock *B) {
+  MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
     applySplitCriticalEdges();
     return DT->findNearestCommonDominator(A, B);
   }
 
-  inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
+  MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
     applySplitCriticalEdges();
     return DT->getNode(BB);
   }
 
   /// getNode - return the (Post)DominatorTree node for the specified basic
   /// block.  This is the same as using operator[] on this class.
   ///
-  inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
+  MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
     applySplitCriticalEdges();
     return DT->getNode(BB);
   }
 
   /// addNewBlock - Add a new node to the dominator tree information.  This
   /// creates a new node as a child of DomBB dominator node,linking it into
   /// the children list of the immediate dominator.
-  inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
-                                         MachineBasicBlock *DomBB) {
+  MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
     applySplitCriticalEdges();
     return DT->addNewBlock(BB, DomBB);
   }
 
   /// changeImmediateDominator - This method is used to update the dominator
   /// tree information when a node's immediate dominator changes.
   ///
-  inline void changeImmediateDominator(MachineBasicBlock *N,
-                                       MachineBasicBlock* NewIDom) {
+  void changeImmediateDominator(MachineBasicBlock *N,
+                                MachineBasicBlock *NewIDom) {
     applySplitCriticalEdges();
     DT->changeImmediateDominator(N, NewIDom);
   }
 
-  inline void changeImmediateDominator(MachineDomTreeNode *N,
-                                       MachineDomTreeNode* NewIDom) {
+  void changeImmediateDominator(MachineDomTreeNode *N,
+                                MachineDomTreeNode *NewIDom) {
     applySplitCriticalEdges();
     DT->changeImmediateDominator(N, NewIDom);
   }
 
   /// eraseNode - Removes a node from  the dominator tree. Block must not
   /// dominate any other blocks. Removes node from its immediate dominator's
   /// children list. Deletes dominator node associated with basic block BB.
-  inline void eraseNode(MachineBasicBlock *BB) {
+  void eraseNode(MachineBasicBlock *BB) {
     applySplitCriticalEdges();
     DT->eraseNode(BB);
   }
 
   /// splitBlock - BB is split and now it has one successor. Update dominator
   /// tree to reflect this change.
-  inline void splitBlock(MachineBasicBlock* NewBB) {
+  void splitBlock(MachineBasicBlock* NewBB) {
     applySplitCriticalEdges();
     DT->splitBlock(NewBB);
   }
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   bool isReachableFromEntry(const MachineBasicBlock *A) {
     applySplitCriticalEdges();

llvm/lib/CodeGen/MachineDominators.cpp

 }
 
 void MachineDominatorTree::releaseMemory() {
   CriticalEdgesToSplit.clear();
   DT.reset(nullptr);
 }
 
 void MachineDominatorTree::verifyAnalysis() const {
-  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());
+  if (DT && VerifyMachineDomInfo)
+    if (!DT->verify(DomTreeT::VerificationLevel::Basic)) {
+      errs() << "MachineDominatorTree verification failed\n";
       abort();
     }
-  }
-}
 
 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
   if (DT)
     DT->print(OS);
 }
 
 void MachineDominatorTree::applySplitCriticalEdges() const {
   // Bail out early if there is nothing to do.