[OPT] Remove recursion from redundancy_elimination (#6141)

Remove unnecessary recursion from redundancy elimination. This should
avoid potenitail stack overflows for function with deep dominator trees.

Fixes #6104

source/opt/redundancy_elimination.cpp

diff --git a/source/opt/redundancy_elimination.cpp b/source/opt/redundancy_elimination.cpp
index 398225b..61234fa 100644
--- a/source/opt/redundancy_elimination.cpp
+++ b/source/opt/redundancy_elimination.cpp
@@ -33,12 +33,7 @@
     DominatorTree& dom_tree =
         context()->GetDominatorAnalysis(&func)->GetDomTree();
 
-    // Keeps track of all ids that contain a given value number. We keep
-    // track of multiple values because they could have the same value, but
-    // different decorations.
-    std::map<uint32_t, uint32_t> value_to_ids;
-
-    if (EliminateRedundanciesFrom(dom_tree.GetRoot(), vnTable, value_to_ids)) {
+    if (EliminateRedundanciesFrom(dom_tree.GetRoot(), vnTable)) {
       modified = true;
     }
   }
@@ -46,14 +41,21 @@
 }
 
 bool RedundancyEliminationPass::EliminateRedundanciesFrom(
-    DominatorTreeNode* bb, const ValueNumberTable& vnTable,
-    std::map<uint32_t, uint32_t> value_to_ids) {
-  bool modified = EliminateRedundanciesInBB(bb->bb_, vnTable, &value_to_ids);
-
-  for (auto dominated_bb : bb->children_) {
-    modified |= EliminateRedundanciesFrom(dominated_bb, vnTable, value_to_ids);
+    DominatorTreeNode* bb, const ValueNumberTable& vnTable) {
+  struct State {
+    DominatorTreeNode* node;
+    std::map<uint32_t, uint32_t> value_to_id_map;
+  };
+  std::vector<State> todo;
+  todo.push_back({bb, std::map<uint32_t, uint32_t>()});
+  bool modified = false;
+  for (size_t next_node = 0; next_node < todo.size(); next_node++) {
+    modified |= EliminateRedundanciesInBB(todo[next_node].node->bb_, vnTable,
+                                          &todo[next_node].value_to_id_map);
+    for (DominatorTreeNode* child : todo[next_node].node->children_) {
+      todo.push_back({child, todo[next_node].value_to_id_map});
+    }
   }
-
   return modified;
 }
 }  // namespace opt

source/opt/redundancy_elimination.h

diff --git a/source/opt/redundancy_elimination.h b/source/opt/redundancy_elimination.h
index 40451f4..8c6e16a 100644
--- a/source/opt/redundancy_elimination.h
+++ b/source/opt/redundancy_elimination.h
@@ -46,8 +46,7 @@
   //
   // Returns true if at least one instruction is deleted.
   bool EliminateRedundanciesFrom(DominatorTreeNode* bb,
-                                 const ValueNumberTable& vnTable,
-                                 std::map<uint32_t, uint32_t> value_to_ids);
+                                 const ValueNumberTable& vnTable);
 };
 
 }  // namespace opt