SPIRV compiler performance fixes. (#3258)

* SPIRV compiler performance fixes.

* Cleanup.

* update project files

* Cleanup debug code.

* Make redundancy removal non-recursive.

---------

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

1 files changed, 55 insertions, 26 deletions

diff --git a/source/slang/slang-ir-reachability.cpp b/source/slang/slang-ir-reachability.cpp
index 1a3cab386..1a4aa271b 100644
--- a/source/slang/slang-ir-reachability.cpp
+++ b/source/slang/slang-ir-reachability.cpp
@@ -5,35 +5,64 @@ namespace Slang
 // Computes whether block1 can reach block2.
 // A block is considered not reachable from itself unless there is a backedge in the CFG.
 
-bool ReachabilityContext::computeReachability(IRBlock* block1, IRBlock* block2)
-{
-    workList.clear();
-    reachableBlocks.clear();
-    workList.add(block1);
-    for (Index i = 0; i < workList.getCount(); i++)
+    ReachabilityContext::ReachabilityContext(IRGlobalValueWithCode* code)
     {
-        auto src = workList[i];
-        for (auto successor : src->getSuccessors())
+        int id = 0;
+        for (auto block : code->getBlocks())
+        {
+            mapBlockToId[block] = id;
+            id++;
+            allBlocks.add(block);
+        }
+        sourceBlocks.setCount(allBlocks.getCount());
+        for (auto &srcBlock : sourceBlocks)
+            srcBlock.resizeAndClear(allBlocks.getCount());
+
+        if (allBlocks.getCount() == 0)
+            return;
+
+        List<IRBlock*> workList;
+        List<IRBlock*> pendingWorkList;
+        workList.add(allBlocks[0]);
+        while (workList.getCount())
         {
-            if (successor == block2)
-                return true;
-            if (reachableBlocks.add(successor))
-                workList.add(successor);
+            pendingWorkList.clear();
+            for (Index i = 0; i < workList.getCount(); i++)
+            {
+                auto src = workList[i];
+                auto srcId = mapBlockToId.getValue(src);
+                for (auto successor : src->getSuccessors())
+                {
+                    auto successorId = mapBlockToId.getValue(successor);
+                    auto& blockSet = sourceBlocks[successorId];
+                    bool changed = false;
+                    if (!blockSet.contains(srcId))
+                    {
+                        blockSet.add(srcId);
+                        changed = true;
+                    }
+                    if (!blockSet.contains(sourceBlocks[srcId]))
+                    {
+                        blockSet.unionWith(sourceBlocks[srcId]);
+                        changed = true;
+                    }
+                    if (changed)
+                        pendingWorkList.add(successor);
+                }
+            }
+            workList.swapWith(pendingWorkList);
         }
+
     }
-    return false;
-}
 
-bool ReachabilityContext::isBlockReachable(IRBlock* from, IRBlock* to)
-{
-    BlockPair pair;
-    pair.first = from;
-    pair.second = to;
-    bool result = false;
-    if (reachabilityResults.tryGetValue(pair, result))
-        return result;
-    result = computeReachability(from, to);
-    reachabilityResults[pair] = result;
-    return result;
-}
+    bool ReachabilityContext::isBlockReachable(IRBlock* from, IRBlock* to)
+    {
+        if (!from) return false;
+        if (!to) return false;
+        int* fromId = mapBlockToId.tryGetValue(from);
+        int* toId = mapBlockToId.tryGetValue(to);
+        if (!fromId || !toId)
+            return true;
+        return sourceBlocks[*toId].contains(*fromId);
+    }
 }