[Dominators] Delete UpdateLevelsAfterInsertion in edge insertion of depth-based search for release builds
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.
Reviewers: kuhar
Reviewed By: kuhar
Subscribers: kristina, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D58369
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@354429 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index 1a57124..7ba907e 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -632,7 +632,9 @@
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,
@@ -800,8 +802,10 @@
// 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.
@@ -833,22 +837,15 @@
TN->setIDom(NCD);
}
- UpdateLevelsAfterInsertion(II);
+#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
+
if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
}
- static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
- LLVM_DEBUG(
- dbgs() << "Updating levels for visited but not affected nodes\n");
-
- for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
- LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
- << BlockNamePrinter(TN->getIDom()) << ") "
- << TN->getIDom()->getLevel() << " + 1\n");
- TN->UpdateLevel();
- }
- }
-
// Handles insertion to previously unreachable nodes.
static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr From, const NodePtr To) {
