From 06f7ef354cdde4cf8e8797d8853ed2d9c3208b5b Mon Sep 17 00:00:00 2001
From: Sai Praveen Bangaru <31557731+saipraveenb25@users.noreply.github.com>
Date: Fri, 25 Aug 2023 14:53:12 -0400
Subject: Fix various issues with trivial loops (#3149)

* Fix issue with trivial loop detection

* Fix issue with unreachable blocks in break elimination

Add logic to avoid eliminating loops with multi-level breaks.

* Incorporate feedback

- Use a boolean for multi-level break check
- Use dominator trees for region check instead of exhaustive enumeration
- Fix potential issue with enumerating parent break blocks.

* fix
---
 source/slang/slang-ir-dominators.cpp | 25 +++++++++++++++++++++++--
 1 file changed, 23 insertions(+), 2 deletions(-)

(limited to 'source/slang/slang-ir-dominators.cpp')

diff --git a/source/slang/slang-ir-dominators.cpp b/source/slang/slang-ir-dominators.cpp
index e57099321..8527fbf36 100644
--- a/source/slang/slang-ir-dominators.cpp
+++ b/source/slang/slang-ir-dominators.cpp
@@ -188,7 +188,7 @@ Int IRDominatorTree::getBlockIndex(IRBlock* block)
 
 bool IRDominatorTree::isUnreachable(IRBlock* block)
 {
-    return !mapBlockToIndex.containsKey(block);
+    return !reachableSet.contains(block);
 }
 
 
@@ -333,8 +333,23 @@ struct PostorderComputationContext : public DepthFirstSearchContext
     }
 };
 
+void computeReachableSet(IRGlobalValueWithCode* code, HashSet<IRBlock*>& outSet)
+{
+    DepthFirstSearchContext context;
+    if (code->getFirstBlock())
+        context.walk(code->getFirstBlock(), [](IRBlock* block) {return block->getSuccessors(); });
+    outSet = _Move(context.visited);
+}
+
 /// Compute a postorder traversal of the blocks in `code`, writing the resulting order to `outOrder`.
 void computePostorder(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder)
+{
+    HashSet<IRBlock*> reachableSet;
+    computePostorder(code, outOrder, reachableSet);
+}
+
+/// Compute a postorder traversal of the blocks in `code`, writing the resulting order to `outOrder`.
+void computePostorder(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder, HashSet<IRBlock*>& outReachableSet)
 {
     PostorderComputationContext context;
     context.order = &outOrder;
@@ -352,6 +367,7 @@ void computePostorder(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder)
     }
     prefix.addRange(outOrder);
     outOrder = _Move(prefix);
+    outReachableSet = _Move(context.visited);
 }
 
 void computePostorderOnReverseCFG(IRGlobalValueWithCode* code, List<IRBlock*>& outOrder)
@@ -397,6 +413,10 @@ struct DominatorTreeComputationContext
     // traversal, so that we can look up a block based on its "name"
     //
     List<IRBlock*> postorder;
+    // 
+    // Also maintain a set of reachable blocks.
+    //
+    HashSet<IRBlock*> reachableSet;
 
     //
     // We need a way to map our actual IR blocks to their names for
@@ -426,7 +446,7 @@ struct DominatorTreeComputationContext
     void iterativelyComputeImmediateDominators(IRGlobalValueWithCode* code)
     {
         // First we compute the postorder traversal order for the blocks in the CFG.
-        computePostorder(code, postorder);
+        computePostorder(code, postorder, reachableSet);
 
         // We will initialize our map from the block objects to their "name"
         // (index in the traversal order), before moving on.
@@ -746,6 +766,7 @@ struct DominatorTreeComputationContext
         RefPtr<IRDominatorTree> dominatorTree = new IRDominatorTree();
         dominatorTree->code = code;
         dominatorTree->nodes.setCount(blockCount);
+        dominatorTree->reachableSet = _Move(reachableSet);
 
         // We will iterate over all of the blocks, and fill in the corresponding
         // dominator tree node for each.
-- 
cgit v1.2.3