dart2js: Avoid recursion in visiting blocks of subgraph

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

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // 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;
 import '../constants/constant_system.dart';
 import '../constants/values.dart';
 import '../common_elements.dart' show CommonElements;
 import '../elements/elements.dart'
     show AsyncMarker, JumpTarget, LabelDefinition, MethodElement, ResolvedAst;
 import '../elements/entities.dart';
 import '../elements/types.dart';
@@ skipping 183 matching lines @@
 
   HGraph currentGraph;
 
   // Records a block-information that is being handled specially.
   // Used to break bad recursion.
   HBlockInformation currentBlockInformation;
   // The subgraph is used to delimit traversal for some constructions, e.g.,
   // if branches.
   SubGraph subGraph;
 
+  // Pending blocks than need to be visited as part of current subgraph.
+  Queue<HBasicBlock> blockQueue;
+
   SsaCodeGenerator(
       this._options,
       this._emitter,
       this._nativeEnqueuer,
       this._helpers,
       this._checkedModeHelpers,
       this._nativeData,
       this._interceptorData,
       this._oneShotInterceptorData,
       this._rtiSubstitutions,
@@ skipping 193 matching lines @@
       var declarationList = new js.VariableDeclarationList(declarations)
           .withSourceInformation(sourceInformation);
       ;
       insertStatementAtStart(new js.ExpressionStatement(declarationList));
     }
   }
 
   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;
   }
 
   /**
    * Check whether a sub-graph can be generated as an expression, or even
    * as a declaration, or if it has to fall back to being generated as
    * a statement.
    * Expressions are anything that doesn't generate control flow constructs.
    * Declarations must only generate assignments on the form "id = expression",
    * and not, e.g., expressions where the value isn't assigned, or where it's
@@ skipping 753 matching lines @@
     // the same block, don't handle it again.
     // When the structure graph is complete, we will be able to have
     // different structures starting on the same basic block (e.g., an
     // "if" and its condition).
     if (identical(info, currentBlockInformation)) return false;
 
     HBlockInformation oldBlockInformation = currentBlockInformation;
     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) {
+  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));
+
+      // If this node has block-structure based information attached,
+      // try using that to traverse from here.
+      if (node.blockFlow != null && handleBlockFlow(node.blockFlow)) {
+        continue;
+      }
+
+      iterateBasicBlock(node);
+    }
+  }
+
+  void continueSubGraph(HBasicBlock node) {
     if (!node.isLive) return;
-
-    // Abort traversal if we are leaving the currently active sub-graph.
+    // Don't follow edges out of the current 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)) {
-      return;
-    }
-    iterateBasicBlock(node);
+    blockQueue.add(node);
   }
 
   void emitAssignment(String destination, String source) {
     assignVariable(destination, new js.VariableUse(source), null);
   }
 
   /**
    * Sequentialize a list of conceptually parallel copies. Parallel
    * copies may contain cycles, that this method breaks.
    */
@@ skipping 242 matching lines @@
     if (dominated.isEmpty) return;
     if (dominated.length > 2) {
       throw new SpannableAssertionFailure(
           node, 'dominated.length = ${dominated.length}');
     }
     if (dominated.length == 2 && block != currentGraph.entry) {
       throw new SpannableAssertionFailure(
           node, 'node.block != currentGraph.entry');
     }
     assert(dominated[0] == block.successors[0]);
-    visitBasicBlock(dominated[0]);
+    continueSubGraph(dominated.first);
   }
 
   visitLoopBranch(HLoopBranch node) {
     assert(node.block == subGraph.end);
     // We are generating code for a loop condition.
     // If we are generating the subgraph as an expression, the
     // condition will be generated as the expression.
     // Otherwise, we don't generate the expression, and leave that
     // to the code that called [visitSubGraph].
     if (isGeneratingExpression) {
@@ skipping 58 matching lines @@
       }
     }
   }
 
   visitExitTry(HExitTry node) {
     // An [HExitTry] is used to represent the control flow graph of a
     // try/catch block, ie the try body is always a predecessor
     // 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) {
     // We should never get here. Try/catch/finally is always handled using block
     // information in [visitTryInfo].
     throw new SpannableAssertionFailure(node, 'visitTry should not be called.');
   }
 
   bool tryControlFlowOperation(HIf node) {
     if (!controlFlowOperators.contains(node)) return false;
     HPhi phi = node.joinBlock.phis.first;
     bool atUseSite = isGenerateAtUseSite(phi);
     // Don't generate a conditional operator in this situation:
     // i = condition ? bar() : i;
     // But generate this instead:
     // if (condition) i = bar();
     // Usually, the variable name is longer than 'if' and it takes up
     // more space to duplicate the name.
     if (!atUseSite &&
         variableNames.getName(phi) == variableNames.getName(phi.inputs[1])) {
       return false;
     }
     if (!atUseSite) define(phi);
-    visitBasicBlock(node.joinBlock);
+    continueSubGraph(node.joinBlock);
     return true;
   }
 
   void generateIf(HIf node, HIfBlockInformation info) {
     use(node.inputs[0]);
     js.Expression test = pop();
 
     HStatementInformation thenGraph = info.thenGraph;
     HStatementInformation elseGraph = info.elseGraph;
     js.Statement thenPart =
@@ skipping 37 matching lines @@
       }
     } else {
       generateIf(node, info);
     }
 
     HBasicBlock joinBlock = node.joinBlock;
     if (joinBlock != null && !identical(joinBlock.dominator, node.block)) {
       // 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
     // branches, and is not the join block.
     // Depending on how the then/else branches terminate
     // (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]);
     }
   }
 
   void visitInterceptor(HInterceptor node) {
     if (node.isConditionalConstantInterceptor) {
       assert(node.inputs.length == 2);
       use(node.receiver);
       js.Expression receiverExpression = pop();
       use(node.conditionalConstantInterceptor);
       js.Expression constant = pop();
@@ skipping 1344 matching lines @@
     return _closedWorld.anyStrictSubclassOf(cls, (ClassEntity subclass) {
       return !_rtiSubstitutions.isTrivialSubstitution(subclass, cls);
     });
   }
 
   @override
   void visitRef(HRef node) {
     visit(node.value);
   }
 }