[Dominators] Delete UpdateLevelsAfterInsertion in edge insertion of depth-based search for release builds

[MaskRay]

Summary

After insertion of (From, To), v is affected iff
depth(NCD)+1 < depth(v) && path P from To to v exists where every w on P s.t. depth(v) <= depth(w)

All affected vertices change their idom to NCD.

If a vertex u has changed its depth, it must be a descendant of an
affected vertex v. Its depth must have been updated by UpdateLevel()
called by setIDom() of the first affected ancestor.

So UpdateLevelsAfterInsertion and its bookkeeping variable VisitedNotAffectedQueue are redundant.
Run them only in debug builds as a sanity check.

[MaskRay]

Update description

[kuhar]

As a sanity check, to account for possible bugs somewhere else, have you tried adding an assertion ensuring that levels don't change in the function?

[MaskRay]

assert TN->getLevel() == TN->getIDom()->getLevel()+1 in debug builds

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

struct InsertionInfo {
 
     // Bucket queue of tree nodes ordered by descending level. For simplicity,
     // we use a priority_queue here.
     std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
                         Compare>
         Bucket;
     SmallDenseSet<TreeNodePtr, 8> Visited;
     SmallVector<TreeNodePtr, 8> Affected;
-    SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
+#ifndef NDEBUG
+    SmallVector<TreeNodePtr, 8> VisitedUnaffected;
+#endif
   };
 
   static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
                          const NodePtr From, const NodePtr To) {
     assert((From || IsPostDom) &&
            "From has to be a valid CFG node or a virtual root");
     assert(To && "Cannot be a nullptr");
     LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
while (!II.Bucket.empty()) {
           if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
             continue;
 
           if (SuccLevel > CurrentLevel) {
             // Succ is unaffected but it may (transitively) expand to affected
             // vertices. Store it in UnaffectedOnCurrentLevel.
             LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
                               << BlockNamePrinter(Succ) << "\n");
-            II.VisitedNotAffectedQueue.push_back(SuccTN);
             UnaffectedOnCurrentLevel.push_back(SuccTN);
+#ifndef NDEBUG
+            II.VisitedUnaffected.push_back(SuccTN);
+#endif
           } else {
             // The condition is satisfied (Succ is affected). Add Succ to the
             // bucket queue.
             LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ)
                               << " to a Bucket\n");
             II.Bucket.push(SuccTN);
           }
         }
static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
 
     for (const TreeNodePtr TN : II.Affected) {
       LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
                         << ") = " << BlockNamePrinter(NCD) << "\n");
       TN->setIDom(NCD);
     }
 
-    UpdateLevelsAfterInsertion(II);
-    if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
-  }
-
-  static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
-    LLVM_DEBUG(
-        dbgs() << "Updating levels for visited but not affected nodes\n");
+#ifndef NDEBUG
+    for (const TreeNodePtr TN : II.VisitedUnaffected)
+      assert(TN->getLevel() == TN->getIDom()->getLevel() + 1 &&
+             "TN should have been updated by an affected ancestor");
+#endif
 
-    for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
-      LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
-                        << BlockNamePrinter(TN->getIDom()) << ") "
-                        << TN->getIDom()->getLevel() << " + 1\n");
-      TN->UpdateLevel();
-    }
+    if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }
 
   // Handles insertion to previously unreachable nodes.
   static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
                                 const TreeNodePtr From, const NodePtr To) {
     LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
                       << " -> (unreachable) " << BlockNamePrinter(To) << "\n");