Non-Recursive CFG DFS. (#2953)

Co-authored-by: Yong He <yhe@nvidia.com>

1 files changed, 21 insertions, 4 deletions

diff --git a/source/slang/slang-ir-dominators.cpp b/source/slang/slang-ir-dominators.cpp
index 6c2045b7f..e57099321 100644
--- a/source/slang/slang-ir-dominators.cpp
+++ b/source/slang/slang-ir-dominators.cpp
@@ -279,16 +279,33 @@ struct DepthFirstSearchContext
     template<typename SuccessorFunc>
     void walk(IRBlock* block, const SuccessorFunc& getSuccessors)
     {
+        List<IRBlock*> nodeStack;
+        nodeStack.add(block);
         visited.add(block);
         preVisit(block);
-        for(auto succ : getSuccessors(block))
+
+        while (nodeStack.getCount())
         {
-            if(!visited.contains(succ))
+            auto curNode = nodeStack.getLast();
+            bool pushedChild = false;
+            for (auto succ : getSuccessors(curNode))
+            {
+                if (!visited.contains(succ))
+                {
+                    pushedChild = true;
+                    nodeStack.add(succ);
+                    visited.add(succ);
+
+                    preVisit(succ);
+                    break;
+                }
+            }
+            if (!pushedChild)
             {
-                walk(succ, getSuccessors);
+                postVisit(curNode);
+                nodeStack.removeLast();
             }
         }
-        postVisit(block);
     }
 
     /// Overridable action to perform on first entering a CFG node.