dart2js cps: Avoid deep recursion using trampolines and basic blocks.

pkg/compiler/lib/src/cps_ir/type_propagation.dart

Index: pkg/compiler/lib/src/cps_ir/type_propagation.dart
diff --git a/pkg/compiler/lib/src/cps_ir/type_propagation.dart b/pkg/compiler/lib/src/cps_ir/type_propagation.dart
index 25ee9add7af75f7546a528a9913e2fb9eafdc63b..839e666b56f68b23f078efcf1b942caa4ad99e04 100644
--- a/pkg/compiler/lib/src/cps_ir/type_propagation.dart
+++ b/pkg/compiler/lib/src/cps_ir/type_propagation.dart
@@ -546,7 +546,7 @@ final Map<String, BuiltinOperator> NumBinaryBuiltins =
  * Uses the information from a preceding analysis pass in order to perform the
  * actual transformations on the CPS graph.
  */
-class TransformingVisitor extends RecursiveVisitor {
+class TransformingVisitor extends LeafVisitor {
   final TypePropagationVisitor analyzer;
   final Map<Expression, ConstantValue> replacements;
   final ConstantPropagationLattice lattice;
@@ -560,6 +560,8 @@ class TransformingVisitor extends RecursiveVisitor {
 
   final dart2js.InternalErrorFunction internalError;
 
+  final List<Node> stack = <Node>[];
+
   TransformingVisitor(this.compiler,
                       this.lattice,
                       this.analyzer,
@@ -567,9 +569,81 @@ class TransformingVisitor extends RecursiveVisitor {
                       this.internalError);
 
   void transform(FunctionDefinition root) {
-    visit(root);
+    push(root.body);
+    while (stack.isNotEmpty) {
+      visit(stack.removeLast());
+    }
+  }
+
+  void push(Node node) {
+    assert(node != null);
+    stack.add(node);
+  }
+
+  void pushAll(Iterable<Node> nodes) {
+    nodes.forEach(push);
+  }
+
+  /************************* INTERIOR EXPRESSIONS *************************/
+  //
+  // These return nothing, and must push recursive children on the stack.
+
+  void visitLetCont(LetCont node) {
+    pushAll(node.continuations);
+    push(node.body);
+  }
+
+  void visitLetHandler(LetHandler node) {
+    push(node.handler);
+    push(node.body);
+  }
+
+  void visitLetMutable(LetMutable node) {
+    visit(node.variable);
+    push(node.body);
+  }
+
+  void visitLetPrim(LetPrim node) {
+    AbstractValue value = getValue(node.primitive);
+    if (node.primitive is! Constant && value.isConstant) {
+      // If the value is a known constant, compile it as a constant.
+      Constant newPrim = makeConstantPrimitive(value.constant);
+      newPrim.substituteFor(node.primitive);
+      RemovalVisitor.remove(node.primitive);
+      node.primitive = newPrim;
+      newPrim.parent = node;
+    } else {
+      Primitive newPrim = visit(node.primitive);
+      if (newPrim != null) {
+        newPrim.substituteFor(node.primitive);
+        RemovalVisitor.remove(node.primitive);
+        node.primitive = newPrim;
+        newPrim.parent = node;
+        reanalyze(newPrim);
+      }
+      if (node.primitive.hasNoUses && node.primitive.isSafeForElimination) {
+        // Remove unused primitives before entering the body.
+        // This would also be done by shrinking reductions, but usage analyses
+        // such as isAlwaysBoolified are more precise without the dead uses, so
+        // we prefer to remove them early.
+        RemovalVisitor.remove(node.primitive);
+        node.parent.body = node.body;
+        node.body.parent = node.parent;
+      }
+    }
+    push(node.body);
+  }
+
+  void visitContinuation(Continuation node) {
+    if (node.isReturnContinuation) return;
+    // Process the continuation body.
+    // Note that the continuation body may have changed since the continuation
+    // was put on the stack (e.g. [visitInvokeContinuation] may do this).
+    push(node.body);
   }
 
+  /************************* TRANSFORMATION HELPERS *************************/
+
   /// Sets parent pointers and computes types for the given subtree.
   void reanalyze(Node node) {
     new ParentVisitor().visit(node);
@@ -623,6 +697,16 @@ class TransformingVisitor extends RecursiveVisitor {
     context.body = node;
     node.parent = context;
   }
+  
+  /// Binds [prim] before [node].
+  void insertLetPrim(Expression node, Primitive prim) {
+    InteriorNode parent = node.parent;
+    LetPrim let = new LetPrim(prim);
+    parent.body = let;
+    let.body = node;
+    node.parent = let;
+    let.parent = parent;
+  }
 
   /// Make a constant primitive for [constant] and set its entry in [values].
   Constant makeConstantPrimitive(ConstantValue constant) {
@@ -648,23 +732,7 @@ class TransformingVisitor extends RecursiveVisitor {
     return letPrim;
   }
 
-  /// Side-effect free expressions with constant results are be replaced by:
-  ///
-  ///    (LetPrim p = constant (InvokeContinuation k p)).
-  ///
-  /// The new expression will be visited.
-  ///
-  /// Returns true if the node was replaced.
-  bool constifyExpression(CallExpression node) {
-    Continuation continuation = node.continuation.definition;
-    ConstantValue constant = replacements[node];
-    if (constant == null) return false;
-    Constant primitive = makeConstantPrimitive(constant);
-    LetPrim letPrim = makeLetPrimInvoke(primitive, continuation);
-    replaceSubtree(node, letPrim);
-    visitLetPrim(letPrim);
-    return true;
-  }
+  /************************* TAIL EXPRESSIONS *************************/
 
   // A branch can be eliminated and replaced by an invocation if only one of
   // the possible continuations is reachable. Removal often leads to both dead
@@ -684,13 +752,13 @@ class TransformingVisitor extends RecursiveVisitor {
     if (boolifiedValue == AbstractBool.True) {
       InvokeContinuation invoke = new InvokeContinuation(trueCont, []);
       replaceSubtree(node, invoke);
-      visitInvokeContinuation(invoke);
+      push(invoke);
       return;
     }
     if (boolifiedValue == AbstractBool.False) {
       InvokeContinuation invoke = new InvokeContinuation(falseCont, []);
       replaceSubtree(node, invoke);
-      visitInvokeContinuation(invoke);
+      push(invoke);
       return;
     }
 
@@ -718,6 +786,36 @@ class TransformingVisitor extends RecursiveVisitor {
     }
   }
 
+  void visitInvokeContinuation(InvokeContinuation node) {
+    // Inline the single-use continuations. These are often introduced when
+    // specializing an invocation node. These would also be inlined by a later
+    // pass, but doing it here helps simplify pattern matching code, since the
+    // effective definition of a primitive can then be found without going
+    // through redundant InvokeContinuations.
+    Continuation cont = node.continuation.definition;
+    if (cont.hasExactlyOneUse &&
+        !cont.isReturnContinuation &&
+        !cont.isRecursive &&
+        !node.isEscapingTry) {
+      for (int i = 0; i < node.arguments.length; ++i) {
+        node.arguments[i].definition.useElementAsHint(cont.parameters[i].hint);
+        node.arguments[i].definition.substituteFor(cont.parameters[i]);
+        node.arguments[i].unlink();
+      }
+      node.continuation.unlink();
+      InteriorNode parent = node.parent;
+      Expression body = cont.body;
+      parent.body = body;
+      body.parent = parent;
+      cont.body = new Unreachable();
+      cont.body.parent = cont;
+      push(body);
+    }
+  }
+
+
+  /************************* CALL EXPRESSIONS *************************/
+
   /// Replaces [node] with a more specialized instruction, if possible.
   ///
   /// Returns `true` if the node was replaced.
@@ -731,7 +829,7 @@ class TransformingVisitor extends RecursiveVisitor {
                                    node.sourceInformation);
       LetPrim let = makeLetPrimInvoke(prim, cont);
       replaceSubtree(node, let);
-      visitLetPrim(let);
+      push(let);
       return true; // So returning early is more convenient.
     }
 
@@ -829,7 +927,7 @@ class TransformingVisitor extends RecursiveVisitor {
       GetField get = new GetField(getDartReceiver(node), target);
       LetPrim let = makeLetPrimInvoke(get, cont);
       replaceSubtree(node, let);
-      visitLetPrim(let);
+      push(let);
       return true;
     } else {
       if (target.isFinal) return false;
@@ -841,7 +939,7 @@ class TransformingVisitor extends RecursiveVisitor {
                                getDartArgument(node, 0)));
       cps.invokeContinuation(cont);
       replaceSubtree(node, cps.result);
-      visit(cps.result);
+      push(cps.result);
       return true;
     }
   }
@@ -934,7 +1032,7 @@ class TransformingVisitor extends RecursiveVisitor {
         CpsFragment cps = new CpsFragment(sourceInfo);
         cps.invokeContinuation(cont, [cps.letPrim(new GetLength(list))]);
         replaceSubtree(node, cps.result);
-        visit(cps.result);
+        push(cps.result);
         return true;
 
       case '[]':
@@ -946,7 +1044,7 @@ class TransformingVisitor extends RecursiveVisitor {
         GetIndex get = cps.letPrim(new GetIndex(list, index));
         cps.invokeContinuation(cont, [get]);
         replaceSubtree(node, cps.result);
-        visit(cps.result);
+        push(cps.result);
         return true;
 
       case '[]=':
@@ -962,7 +1060,7 @@ class TransformingVisitor extends RecursiveVisitor {
         cont.parameters.clear();
         cps.invokeContinuation(cont, []);
         replaceSubtree(node, cps.result);
-        visit(cps.result);
+        push(cps.result);
         return true;
 
       case 'forEach':
@@ -1015,7 +1113,7 @@ class TransformingVisitor extends RecursiveVisitor {
         cps.continueLoop(loop, [addOne]);
 
         replaceSubtree(node, cps.result);
-        visit(cps.result);
+        push(cps.result);
         return true;
 
       case 'iterator':
@@ -1166,9 +1264,7 @@ class TransformingVisitor extends RecursiveVisitor {
         insertBefore(iteratorCont.body, cps);
         InvokeContinuation invoke = new InvokeContinuation(iteratorCont, []);
         replaceSubtree(node, invoke);
-        visit(invoke);
-        // TODO(asgerf): A procedure for rewriting mutables into parameters
-        //               might enable further optimizations after this.
+        push(invoke);
         return true;
 
       // TODO(asgerf): Rewrite 'add', 'removeLast', ...
@@ -1243,7 +1339,7 @@ class TransformingVisitor extends RecursiveVisitor {
           node.sourceInformation);
       node.receiver.unlink();
       replaceSubtree(node, invoke, unlink: false);
-      visitInvokeStatic(invoke);
+      push(invoke);
       return true;
     }
     CallExpression tearOffInvoke = getCallWithResult(tearOff);
@@ -1301,12 +1397,30 @@ class TransformingVisitor extends RecursiveVisitor {
         assert(isPure);
       }
 
-      visitInvokeMethod(invoke);
+      push(invoke);
       return true;
     }
     return false;
   }
 
+  /// Side-effect free expressions with constant results are be replaced by:
+  ///
+  ///    (LetPrim p = constant (InvokeContinuation k p)).
+  ///
+  /// The new expression will be visited.
+  ///
+  /// Returns true if the node was replaced.
+  bool constifyExpression(CallExpression node) {
+    Continuation continuation = node.continuation.definition;
+    ConstantValue constant = replacements[node];
+    if (constant == null) return false;
+    Constant primitive = makeConstantPrimitive(constant);
+    LetPrim letPrim = makeLetPrimInvoke(primitive, continuation);
+    replaceSubtree(node, letPrim);
+    push(letPrim);
+    return true;
+  }
+
   void visitInvokeMethod(InvokeMethod node) {
     if (constifyExpression(node)) return;
     if (specializeOperatorCall(node)) return;
@@ -1316,7 +1430,6 @@ class TransformingVisitor extends RecursiveVisitor {
 
     AbstractValue receiver = getValue(node.receiver.definition);
     node.receiverIsNotNull = receiver.isDefinitelyNotNull;
-    super.visitInvokeMethod(node);
   }
 
   void visitTypeCast(TypeCast node) {
@@ -1333,7 +1446,7 @@ class TransformingVisitor extends RecursiveVisitor {
         InvokeContinuation invoke =
             new InvokeContinuation(cont, <Primitive>[node.value.definition]);
         replaceSubtree(node, invoke);
-        visitInvokeContinuation(invoke);
+        push(invoke);
         return;
 
       case AbstractBool.False:
@@ -1342,8 +1455,6 @@ class TransformingVisitor extends RecursiveVisitor {
         replaceSubtree(cont.body, new Unreachable());
         break;
     }
-
-    super.visitTypeCast(node);
   }
 
   /// Specialize calls to internal static methods.
@@ -1362,7 +1473,7 @@ class TransformingVisitor extends RecursiveVisitor {
             InvokeContinuation invoke =
                 new InvokeContinuation(cont, <Primitive>[arg(0)]);
             replaceSubtree(node, invoke);
-            visitInvokeContinuation(invoke);
+            push(invoke);
             return true;
           }
           break;
@@ -1381,14 +1492,13 @@ class TransformingVisitor extends RecursiveVisitor {
     return value == null ? new AbstractValue.nothing() : value;
   }
 
-  void insertLetPrim(Expression node, Primitive prim) {
-    InteriorNode parent = node.parent;
-    LetPrim let = new LetPrim(prim);
-    parent.body = let;
-    let.body = node;
-    node.parent = let;
-    let.parent = parent;
-  }
+
+  /*************************** PRIMITIVES **************************/
+  //
+  // The visit method for a primitive may optionally return a new
+  // primitive. If non-null, the surrounding LetPrim will substitute it
+  // and bind the new primitive instead.
+  //
 
   void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
     DartString getString(AbstractValue value) {
@@ -1489,73 +1599,6 @@ class TransformingVisitor extends RecursiveVisitor {
     node.objectIsNotNull = getValue(node.object.definition).isDefinitelyNotNull;
   }
 
-  void visitLetPrim(LetPrim node) {
-    AbstractValue value = getValue(node.primitive);
-    if (node.primitive is! Constant && value.isConstant) {
-      // If the value is a known constant, compile it as a constant.
-      Constant newPrim = makeConstantPrimitive(value.constant);
-      newPrim.substituteFor(node.primitive);
-      RemovalVisitor.remove(node.primitive);
-      node.primitive = newPrim;
-      newPrim.parent = node;
-    } else {
-      Primitive newPrim = visit(node.primitive);
-      if (newPrim != null) {
-        newPrim.substituteFor(node.primitive);
-        RemovalVisitor.remove(node.primitive);
-        node.primitive = newPrim;
-        newPrim.parent = node;
-        reanalyze(newPrim);
-      }
-      if (node.primitive.hasNoUses && node.primitive.isSafeForElimination) {
-        // Remove unused primitives before entering the body.
-        // This would also be done by shrinking reductions, but usage analyses
-        // such as isAlwaysBoolified are more precise without the dead uses, so
-        // we prefer to remove them early.
-        RemovalVisitor.remove(node.primitive);
-        node.parent.body = node.body;
-        node.body.parent = node.parent;
-      }
-    }
-    visit(node.body);
-  }
-
-  void visitLetCont(LetCont node) {
-    // Visit body before continuations to ensure more information is available
-    // about the parameters. In particular, if this is a call continuation, its
-    // invocation should be specialized before the body is processed, because
-    // we specialize definitions before their uses.
-    visit(node.body);
-    node.continuations.forEach(visit);
-  }
-
-  void visitInvokeContinuation(InvokeContinuation node) {
-    // Inline the single-use continuations. These are often introduced when
-    // specializing an invocation node. These would also be inlined by a later
-    // pass, but doing it here helps simplify pattern matching code, since the
-    // effective definition of a primitive can then be found without going
-    // through redundant InvokeContinuations.
-    Continuation cont = node.continuation.definition;
-    if (cont.hasExactlyOneUse &&
-        !cont.isReturnContinuation &&
-        !cont.isRecursive &&
-        !node.isEscapingTry) {
-      for (int i = 0; i < node.arguments.length; ++i) {
-        node.arguments[i].definition.useElementAsHint(cont.parameters[i].hint);
-        node.arguments[i].definition.substituteFor(cont.parameters[i]);
-        node.arguments[i].unlink();
-      }
-      node.continuation.unlink();
-      InteriorNode parent = node.parent;
-      Expression body = cont.body;
-      parent.body = body;
-      body.parent = parent;
-      cont.body = new Unreachable();
-      cont.body.parent = cont;
-      visit(body);
-    }
-  }
-
   void visitInterceptor(Interceptor node) {
     // Filter out intercepted classes that do not match the input type.
     AbstractValue value = getValue(node.input.definition);