From ae4273810c1bad35ffe0f745404cb14f2f20c104 Mon Sep 17 00:00:00 2001
From: Yong He <yonghe@outlook.com>
Date: Fri, 30 Jun 2023 14:47:17 -0700
Subject: Non-Recursive CFG DFS. (#2953)

Co-authored-by: Yong He <yhe@nvidia.com>
---
 source/slang/slang-ir-dominators.cpp | 25 +++++++++++++++++++++----
 1 file changed, 21 insertions(+), 4 deletions(-)

(limited to 'source')

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.
-- 
cgit v1.2.3