[DomTree] Use a non-recursive DFS instead of a recursive one; NFC

[sanjoy]

Summary

The recursive DFS can stack overflow in pathological cases.

[kuhar]

LGTM.

Out of curiosity: what kind of IR triggers stack overflow here? I'd suspect it would be have to a very large and nested loop.

include/llvm/Support/GenericDomTreeConstruction.h

437 ↗

(On Diff #110134)

Nitpick: in other places in the file, stack are initialized like this:
SmallVector<Ptr, 8> Stack = {FirstElem};

[sanjoy]

In D36442#834834, @kuhar wrote:

LGTM.

Out of curiosity: what kind of IR triggers stack overflow here? I'd suspect it would be have to a very large and nested loop.

It is a large and nested loop. :)

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

struct SemiNCAInfo {
 
   // Visits an affected node and collect its affected successors.
   static void VisitInsertion(DomTreeT &DT, const TreeNodePtr TN,
                              const unsigned RootLevel, const TreeNodePtr NCD,
                              InsertionInfo &II) {
     const unsigned NCDLevel = NCD->getLevel();
     DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
 
-    assert(TN->getBlock());
+    SmallVector<TreeNodePtr, 8> Stack = {TN};
+    assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
+
+    do {
+      TreeNodePtr Next = Stack.pop_back_val();
+
       for (const NodePtr Succ :
-        ChildrenGetter<NodePtr, IsPostDom>::Get(TN->getBlock())) {
+           ChildrenGetter<NodePtr, IsPostDom>::Get(Next->getBlock())) {
         const TreeNodePtr SuccTN = DT.getNode(Succ);
         assert(SuccTN && "Unreachable successor found at reachable insertion");
         const unsigned SuccLevel = SuccTN->getLevel();
 
         DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
                      << ", level = " << SuccLevel << "\n");
 
         // Succ dominated by subtree From -- not affected.
         // (Based on the lemma 2.5 from the second paper.)
         if (SuccLevel > RootLevel) {
           DEBUG(dbgs() << "\t\tDominated by subtree From\n");
-        if (II.Visited.count(SuccTN) != 0) continue;
+          if (II.Visited.count(SuccTN) != 0)
+            continue;
 
           DEBUG(dbgs() << "\t\tMarking visited not affected "
                        << BlockNamePrinter(Succ) << "\n");
           II.Visited.insert(SuccTN);
           II.VisitedNotAffectedQueue.push_back(SuccTN);
-        VisitInsertion(DT, SuccTN, RootLevel, NCD, II);
-      } else if ((SuccLevel > NCDLevel + 1) && II.Affected.count(SuccTN) == 0) {
+          Stack.push_back(SuccTN);
+        } else if ((SuccLevel > NCDLevel + 1) &&
+                   II.Affected.count(SuccTN) == 0) {
           DEBUG(dbgs() << "\t\tMarking affected and adding "
                        << BlockNamePrinter(Succ) << " to a Bucket\n");
           II.Affected.insert(SuccTN);
           II.Bucket.push({SuccLevel, SuccTN});
         }
       }
+    } while (!Stack.empty());
   }
 
   // Updates immediate dominators and levels after insertion.
   static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD,
                               InsertionInfo &II) {
     DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
 
     for (const TreeNodePtr TN : II.AffectedQueue) {