dart2js: Avoid recursion in visiting blocks of subgraph

pkg/compiler/lib/src/ssa/codegen.dart

Index: pkg/compiler/lib/src/ssa/codegen.dart
diff --git a/pkg/compiler/lib/src/ssa/codegen.dart b/pkg/compiler/lib/src/ssa/codegen.dart
index 2e9291341ad7abcdbbf2bf7ac9327ea42e0f6201..74b53bde41578b298669da83c08c7f3790e84b7b 100644
--- a/pkg/compiler/lib/src/ssa/codegen.dart
+++ b/pkg/compiler/lib/src/ssa/codegen.dart
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 
 import 'dart:math' as math;
+import 'dart:collection' show Queue;
 import '../common.dart';
 import '../common/codegen.dart' show CodegenRegistry, CodegenWorkItem;
 import '../common/tasks.dart' show CompilerTask;
@@ -206,6 +207,9 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
   // if branches.
   SubGraph subGraph;
 
+  // Pending blocks than need to be visited as part of current subgraph.
+  Queue<HBasicBlock> blockQueue;
+
   SsaCodeGenerator(
       this._options,
       this._emitter,
@@ -419,15 +423,17 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
   visitGraph(HGraph graph) {
     preGenerateMethod(graph);
     currentGraph = graph;
-    subGraph = new SubGraph(graph.entry, graph.exit);
-    visitBasicBlock(graph.entry);
+    visitSubGraph(new SubGraph(graph.entry, graph.exit));
     handleDelayedVariableDeclarations(graph.sourceInformation);
   }
 
   void visitSubGraph(SubGraph newSubGraph) {
     SubGraph oldSubGraph = subGraph;
+    Queue<HBasicBlock> oldBlockQueue = blockQueue;
     subGraph = newSubGraph;
-    visitBasicBlock(subGraph.start);
+    blockQueue = new Queue<HBasicBlock>();
+    enterSubGraph(subGraph.start);
+    blockQueue = oldBlockQueue;
     subGraph = oldSubGraph;
   }
 
@@ -1201,27 +1207,40 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
     currentBlockInformation = info;
     bool success = info.accept(this);
     currentBlockInformation = oldBlockInformation;
+
     if (success) {
       HBasicBlock continuation = block.continuation;
       if (continuation != null) {
-        visitBasicBlock(continuation);
+        continueSubGraph(continuation);
       }
     }
     return success;
   }
 
-  void visitBasicBlock(HBasicBlock node) {
-    if (!node.isLive) return;
+  void enterSubGraph(HBasicBlock node) {
+    assert(blockQueue.isEmpty);
+    assert(node != null);
+    continueSubGraph(node);
+    while (blockQueue.isNotEmpty) {
+      node = blockQueue.removeFirst();
+      assert(node.isLive);
+      assert(subGraph.contains(node));
 
-    // Abort traversal if we are leaving the currently active sub-graph.
-    if (!subGraph.contains(node)) return;
+      // If this node has block-structure based information attached,
+      // try using that to traverse from here.
+      if (node.blockFlow != null && handleBlockFlow(node.blockFlow)) {
+        continue;
+      }
 
-    // If this node has block-structure based information attached,
-    // try using that to traverse from here.
-    if (node.blockFlow != null && handleBlockFlow(node.blockFlow)) {
-      return;
+      iterateBasicBlock(node);
     }
-    iterateBasicBlock(node);
+  }
+
+  void continueSubGraph(HBasicBlock node) {
+    if (!node.isLive) return;
+    // Don't follow edges out of the current sub-graph.
+    if (!subGraph.contains(node)) return;
+    blockQueue.add(node);
   }
 
   void emitAssignment(String destination, String source) {
@@ -1484,7 +1503,7 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
           node, 'node.block != currentGraph.entry');
     }
     assert(dominated[0] == block.successors[0]);
-    visitBasicBlock(dominated[0]);
+    continueSubGraph(dominated.first);
   }
 
   visitLoopBranch(HLoopBranch node) {
@@ -1563,7 +1582,7 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
     // of the catch and finally. Here, we continue visiting the try
     // body by visiting the block that contains the user-level control
     // flow instruction.
-    visitBasicBlock(node.bodyTrySuccessor);
+    continueSubGraph(node.bodyTrySuccessor);
   }
 
   visitTry(HTry node) {
@@ -1587,7 +1606,7 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
       return false;
     }
     if (!atUseSite) define(phi);
-    visitBasicBlock(node.joinBlock);
+    continueSubGraph(node.joinBlock);
     return true;
   }
 
@@ -1645,7 +1664,7 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
       // The join block is dominated by a block in one of the branches.
       // The subgraph traversal never reached it, so we visit it here
       // instead.
-      visitBasicBlock(joinBlock);
+      continueSubGraph(joinBlock);
     }
 
     // Visit all the dominated blocks that are not part of the then or else
@@ -1654,7 +1673,7 @@ class SsaCodeGenerator implements HVisitor, HBlockInformationVisitor {
     // (e.g., return/throw/break) there can be any number of these.
     List<HBasicBlock> dominated = node.block.dominatedBlocks;
     for (int i = 2; i < dominated.length; i++) {
-      visitBasicBlock(dominated[i]);
+      continueSubGraph(dominated[i]);
     }
   }