[Dominators] Remove the NCA check

[kuhar]

Summary

This patch removes the verifyNCD check.

The reason for this is that the other checks are sufficient to prove or disprove correctness of any DominatorTree, and that verifyNCD doesn't provide (in my option) better error messages then the other ones.
Additionally, this should give a (small) improvement to the total verification time, as the check is O(n), and checking the sibling property takes O(n^3).

[brzycki]

When working on JumpThreading I never saw a failure due to NCD verification so I think you're intuition about other checks makes sense.

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

for (const auto &NodeToTN : DT.DomTreeNodes) {
           return false;
         }
       }
     }
 
     return true;
   }
 
-  // Checks if for every edge From -> To in the graph
-  //     NCD(From, To) == IDom(To) or To.
-  bool verifyNCD(const DomTreeT &DT) {
-    clear();
-    doFullDFSWalk(DT, AlwaysDescend);
-
-    for (auto &BlockToInfo : NodeToInfo) {
-      auto &Info = BlockToInfo.second;
-
-      const NodePtr From = NumToNode[Info.Parent];
-      if (!From) continue;
-
-      const NodePtr To = BlockToInfo.first;
-      const TreeNodePtr ToTN = DT.getNode(To);
-      assert(ToTN);
-
-      const NodePtr NCD = DT.findNearestCommonDominator(From, To);
-      const TreeNodePtr NCDTN = DT.getNode(NCD);
-      const TreeNodePtr ToIDom = ToTN->getIDom();
-      if (NCDTN != ToTN && NCDTN != ToIDom) {
-        errs() << "NearestCommonDominator verification failed:\n\tNCD(From:"
-               << BlockNamePrinter(From) << ", To:" << BlockNamePrinter(To)
-               << ") = " << BlockNamePrinter(NCD)
-               << ",\t (should be To or IDom[To]: " << BlockNamePrinter(ToIDom)
-               << ")\n";
-        errs().flush();
-
-        return false;
-      }
-    }
-
-    return true;
-  }
-
   // The below routines verify the correctness of the dominator tree relative to
   // the CFG it's coming from.  A tree is a dominator tree iff it has two
   // properties, called the parent property and the sibling property.  Tarjan
   // and Lengauer prove (but don't explicitly name) the properties as part of
   // the proofs in their 1972 paper, but the proofs are mostly part of proving
   // things about semidominators and idoms, and some of them are simply asserted
   // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
   // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
void ApplyUpdates(DomTreeT &DT,
                   ArrayRef<typename DomTreeT::UpdateType> Updates) {
   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
 }
 
 template <class DomTreeT>
 bool Verify(const DomTreeT &DT) {
   SemiNCAInfo<DomTreeT> SNCA(nullptr);
   return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
-         SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) &&
-         SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT) &&
-         SNCA.VerifyDFSNumbers(DT);
+         SNCA.VerifyLevels(DT) && SNCA.verifyParentProperty(DT) &&
+         SNCA.verifySiblingProperty(DT) && SNCA.VerifyDFSNumbers(DT);
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif