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

pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart

Index: pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
diff --git a/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart b/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
index 345da913cb70b6c80db3fd49c6e79dffdc77b435..2e49e958412d112773444362b9e1de515cc314c4 100644
--- a/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
+++ b/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
@@ -10,6 +10,8 @@ import '../cps_ir/cps_ir_nodes.dart' as cps_ir;
 import '../util/util.dart' show CURRENT_ELEMENT_SPANNABLE;
 import 'tree_ir_nodes.dart';
 
+typedef Statement NodeCallback(Statement next);
+
 /**
  * Builder translates from CPS-based IR to direct-style Tree.
  *
@@ -42,7 +44,7 @@ import 'tree_ir_nodes.dart';
  * particular, intermediate values and blocks used for local control flow are
  * still all named.
  */
-class Builder implements cps_ir.Visitor<Node> {
+class Builder implements cps_ir.Visitor {

[karlklose, 2015/07/22 14:08:06]

Maybe you add a comment of the form
  class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ { ...

[asgerf, 2015/07/22 14:32:25]

Done.

   final dart2js.InternalErrorFunction internalError;
 
   final Map<cps_ir.Primitive, Variable> primitive2variable =
@@ -109,6 +111,10 @@ class Builder implements cps_ir.Visitor<Node> {
     return new VariableUse(getVariable(reference.definition));
   }
 
+  Label getLabel(cps_ir.Continuation cont) {
+    return labels.putIfAbsent(cont, () => new Label());
+  }
+
   Variable addFunctionParameter(cps_ir.Definition variable) {
     if (variable is cps_ir.Parameter) {
       return getVariable(variable);
@@ -130,7 +136,7 @@ class Builder implements cps_ir.Visitor<Node> {
         node.parameters.map(addFunctionParameter).toList();
     returnContinuation = node.returnContinuation;
     phiTempVar = new Variable(node.element, null);
-    Statement body = visit(node.body);
+    Statement body = translateExpression(node.body);
     return new FunctionDefinition(node.element, parameters, body);
   }
 
@@ -252,109 +258,135 @@ class Builder implements cps_ir.Visitor<Node> {
     return first;
   }
 
-  visit(cps_ir.Node node) => node.accept(this);
-
-  unexpectedNode(cps_ir.Node node) {
-    internalError(CURRENT_ELEMENT_SPANNABLE, 'Unexpected IR node: $node');
-  }
-
-  Expression visitSetField(cps_ir.SetField node) {
-    return new SetField(getVariableUse(node.object),
-                        node.field,
-                        getVariableUse(node.value));
-  }
-  
-  Expression visitInterceptor(cps_ir.Interceptor node) {
-    return new Interceptor(getVariableUse(node.input), node.interceptedClasses);
-  }
-
-  Expression visitCreateInstance(cps_ir.CreateInstance node) {
-    return new CreateInstance(
-        node.classElement,
-        translateArguments(node.arguments),
-        translateArguments(node.typeInformation),
-        node.sourceInformation);
-  }
-
-  Expression visitGetField(cps_ir.GetField node) {
-    return new GetField(getVariableUse(node.object), node.field,
-        objectIsNotNull: node.objectIsNotNull);
+  visit(cps_ir.Node node) => throw 'Use translateXXX instead of visit';
+
+  /// Translates a CPS expression into a tree statement.
+  /// 
+  /// To avoid deep recursion, we traverse each basic blocks without
+  /// recursion.
+  /// 
+  /// Non-tail expressions evaluate to a callback to be invoked once the
+  /// successor statement has been constructed. These callbacks are stored
+  /// in a stack until the block's tail expression has been translated.
+  Statement translateExpression(cps_ir.Expression node) {
+    // TODO(asgerf): Use a function typedef.

[karlklose, 2015/07/22 14:08:06]

A typedef different from NodeCallback?

[asgerf, 2015/07/22 14:32:25]

Oops, I forgot to remove this after resolving it.

+    List<NodeCallback> stack = <NodeCallback>[];
+    while (node is! cps_ir.TailExpression) {
+      stack.add(node.accept(this));
+      node = node.next;
+    }
+    Statement result = node.accept(this); // Translate the tail expression.
+    for (NodeCallback fun in stack.reversed) {

[karlklose, 2015/07/22 14:08:06]

Maybe a Link<NodeCallback> would work better for the stack, because you do not
need to get a reversed view on it.

[asgerf, 2015/07/22 14:32:25]

I don't think linked lists are faster.

[karlklose, 2015/07/23 06:55:54]

Not necessarily faster, but you can build the stack by prepending and then have
  for (NodeCallback fun in stack) {
    result = fun(result);
  }
here, which is a tiny bit easier to read.

But it is not that important.

+      result = fun(result);
+    }
+    return result;
   }
 
-  Expression visitCreateBox(cps_ir.CreateBox node) {
-    return new CreateBox();
+  /// Translates a CPS primitive to a tree expression.
+  /// 
+  /// This simply calls the visit method for the primitive.
+  Expression translatePrimitive(cps_ir.Primitive prim) {
+    return prim.accept(this);
   }
 
-  visitCreateInvocationMirror(cps_ir.CreateInvocationMirror node) {
-    return new CreateInvocationMirror(
-        node.selector,
-        translateArguments(node.arguments));
+  /// Translates a condition to a tree expression.
+  Expression translateCondition(cps_ir.Condition condition) {
+    cps_ir.IsTrue isTrue = condition;
+    return getVariableUse(isTrue.value);
   }
 
-  // Executable definitions are not visited directly.  They have 'build'
-  // functions as entry points.
-  visitFunctionDefinition(cps_ir.FunctionDefinition node) {
-    return unexpectedNode(node);
-  }
+  /************************ INTERIOR EXPRESSIONS  ************************/
+  //
+  // Visit methods for interior expressions must return a function:
+  //
+  //    (Statement next) => <result statement>
+  //
 
-  Statement visitLetPrim(cps_ir.LetPrim node) {
+  NodeCallback visitLetPrim(cps_ir.LetPrim node) => (Statement next) {
     Variable variable = getVariable(node.primitive);
-    Expression value = visit(node.primitive);
+    Expression value = translatePrimitive(node.primitive);
     if (node.primitive.hasAtLeastOneUse) {
-      return Assign.makeStatement(variable, value, visit(node.body));
+      return Assign.makeStatement(variable, value, next);
     } else {
-      return new ExpressionStatement(value, visit(node.body));
+      return new ExpressionStatement(value, next);
     }
-  }
-
-  Statement visitLetCont(cps_ir.LetCont node) {
-    // Introduce labels for continuations that need them.
+  };
+
+  // Continuations are bound at the same level, but they have to be
+  // translated as if nested.  This is because the body can invoke any
+  // of them from anywhere, so it must be nested inside all of them.
+  //
+  // The continuation bodies are not always translated directly here because
+  // they may have been already translated:
+  //   * For singly-used continuations, the continuation's body is
+  //     translated at the site of the continuation invocation.
+  //   * For recursive continuations, there is a single non-recursive
+  //     invocation.  The continuation's body is translated at the site
+  //     of the non-recursive continuation invocation.
+  // See visitInvokeContinuation for the implementation.

[floitsch, 2015/07/22 14:21:42]

make this a link.

[asgerf, 2015/07/22 14:32:25]

Done.

+  NodeCallback visitLetCont(cps_ir.LetCont node) => (Statement next) {
     for (cps_ir.Continuation continuation in node.continuations) {
-      if (continuation.hasMultipleUses || continuation.isRecursive) {
-        labels[continuation] = new Label();
-      }
-    }
-    Statement body = visit(node.body);
-    // Continuations are bound at the same level, but they have to be
-    // translated as if nested.  This is because the body can invoke any
-    // of them from anywhere, so it must be nested inside all of them.
-    //
-    // The continuation bodies are not always translated directly here because
-    // they may have been already translated:
-    //   * For singly-used continuations, the continuation's body is
-    //     translated at the site of the continuation invocation.
-    //   * For recursive continuations, there is a single non-recursive
-    //     invocation.  The continuation's body is translated at the site
-    //     of the non-recursive continuation invocation.
-    // See visitInvokeContinuation for the implementation.
-    Statement current = body;
-    for (cps_ir.Continuation continuation in node.continuations.reversed) {
+      // This happens after the body of the LetCont has been translated.
+      // Labels are created on-demand if the continuation could not be inlined,
+      // so the existence of the label indicates if a labeled statement should
+      // be emitted.
       Label label = labels[continuation];
       if (label != null && !continuation.isRecursive) {
-        current =
-            new LabeledStatement(label, current, visit(continuation.body));
+        // Recursively build the body. We only do this for join continuations,
+        // so we should not risk overly deep recursion.
+        next = new LabeledStatement(
+            label, 
+            next, 
+            translateExpression(continuation.body));
       }
     }
-    return current;
-  }
+    return next;
+  };
 
-  Statement visitLetHandler(cps_ir.LetHandler node) {
-    Statement tryBody = visit(node.body);
+  NodeCallback visitLetHandler(cps_ir.LetHandler node) => (Statement next) {
     List<Variable> catchParameters =
         node.handler.parameters.map(getVariable).toList();
-    Statement catchBody = visit(node.handler.body);
-    return new Try(tryBody, catchParameters, catchBody);
+    Statement catchBody = translateExpression(node.handler.body);
+    return new Try(next, catchParameters, catchBody);
+  };
+
+  NodeCallback visitLetMutable(cps_ir.LetMutable node) {
+    Variable variable = addMutableVariable(node.variable);
+    Expression value = getVariableUse(node.value);
+    return (Statement next) => Assign.makeStatement(variable, value, next);
+  }
+
+
+  /************************ CALL EXPRESSIONS  ************************/
+  //
+  // Visit methods for call expressions must return a function:
+  //
+  //    (Statement next) => <result statement>
+  //
+  // The result statement must include an assignment to the continuation
+  // parameter, if the parameter is used.
+  //
+
+  NodeCallback makeCallExpression(cps_ir.CallExpression call,
+                                  Expression expression) {
+    return (Statement next) {
+      cps_ir.Parameter result = call.continuation.definition.parameters.single;
+      if (result.hasAtLeastOneUse) {
+        return Assign.makeStatement(getVariable(result), expression, next);
+      } else {
+        return new ExpressionStatement(expression, next);
+      }
+    };
   }
 
-  Statement visitInvokeStatic(cps_ir.InvokeStatic node) {
-    // Calls are translated to direct style.
+  NodeCallback visitInvokeStatic(cps_ir.InvokeStatic node) {
     List<Expression> arguments = translateArguments(node.arguments);
     Expression invoke = new InvokeStatic(node.target, node.selector, arguments,
                                          node.sourceInformation);
-    return continueWithExpression(node.continuation, invoke);
+    return makeCallExpression(node, invoke);
   }
 
-  Statement visitInvokeMethod(cps_ir.InvokeMethod node) {
+  NodeCallback visitInvokeMethod(cps_ir.InvokeMethod node) {
     InvokeMethod invoke = new InvokeMethod(
         getVariableUse(node.receiver),
         node.selector,
@@ -362,84 +394,82 @@ class Builder implements cps_ir.Visitor<Node> {
         translateArguments(node.arguments),
         node.sourceInformation);
     invoke.receiverIsNotNull = node.receiverIsNotNull;
-    return continueWithExpression(node.continuation, invoke);
+    return makeCallExpression(node, invoke);
   }
 
-  Statement visitInvokeMethodDirectly(cps_ir.InvokeMethodDirectly node) {
+  NodeCallback visitInvokeMethodDirectly(cps_ir.InvokeMethodDirectly node) {
     Expression receiver = getVariableUse(node.receiver);
     List<Expression> arguments = translateArguments(node.arguments);
     Expression invoke = new InvokeMethodDirectly(receiver, node.target,
         node.selector, arguments, node.sourceInformation);
-    return continueWithExpression(node.continuation, invoke);
+    return makeCallExpression(node, invoke);
   }
 
-  Statement visitThrow(cps_ir.Throw node) {
+  NodeCallback visitTypeCast(cps_ir.TypeCast node) {
     Expression value = getVariableUse(node.value);
-    return new Throw(value);
-  }
-
-  Statement visitRethrow(cps_ir.Rethrow node) {
-    return new Rethrow();
+    List<Expression> typeArgs = translateArguments(node.typeArguments);
+    Expression expression =
+        new TypeOperator(value, node.type, typeArgs, isTypeTest: false);
+    return makeCallExpression(node, expression);
   }
 
-  Statement visitUnreachable(cps_ir.Unreachable node) {
-    return new Unreachable();
+  NodeCallback visitInvokeConstructor(cps_ir.InvokeConstructor node) {
+    List<Expression> arguments = translateArguments(node.arguments);
+    Expression invoke = new InvokeConstructor(
+        node.type,
+        node.target,
+        node.selector,
+        arguments,
+        node.sourceInformation);
+    return makeCallExpression(node, invoke);
   }
 
-  Statement continueWithExpression(cps_ir.Reference continuation,
-                                   Expression expression) {
-    cps_ir.Continuation cont = continuation.definition;
-    if (cont == returnContinuation) {
-      return new Return(expression);
+  NodeCallback visitForeignCode(cps_ir.ForeignCode node) {
+    if (node.codeTemplate.isExpression) {
+      Expression foreignCode = new ForeignExpression(
+          node.codeTemplate,
+          node.type,
+          node.arguments.map(getVariableUse).toList(growable: false),
+          node.nativeBehavior,
+          node.dependency);
+      return makeCallExpression(node, foreignCode);
     } else {
-      assert(cont.parameters.length == 1);
-      Function nextBuilder = cont.hasExactlyOneUse ?
-          () => visit(cont.body) : () => new Break(labels[cont]);
-      return buildContinuationAssignment(cont.parameters.single, expression,
-          nextBuilder);
+      return (Statement next) {
+        assert(next is Unreachable); // We are not using the `next` statement.
+        return new ForeignStatement(
+            node.codeTemplate,
+            node.type,
+            node.arguments.map(getVariableUse).toList(growable: false),
+            node.nativeBehavior,
+            node.dependency);
+      };
     }
   }
 
-  Statement visitLetMutable(cps_ir.LetMutable node) {
-    Variable variable = addMutableVariable(node.variable);
-    Expression value = getVariableUse(node.value);
-    Statement body = visit(node.body);
-    return Assign.makeStatement(variable, value, body);
+  NodeCallback visitGetLazyStatic(cps_ir.GetLazyStatic node) {
+    // In the tree IR, GetStatic handles lazy fields because we do not need
+    // as fine-grained control over side effects.
+    GetStatic value = new GetStatic(node.element, node.sourceInformation);
+    return makeCallExpression(node, value);
   }
 
-  Expression visitGetMutable(cps_ir.GetMutable node) {
-    return getMutableVariableUse(node.variable);
-  }
 
-  Expression visitSetMutable(cps_ir.SetMutable node) {
-    Variable variable = getMutableVariable(node.variable.definition);
-    Expression value = getVariableUse(node.value);
-    return new Assign(variable, value);
-  }
+  /************************** TAIL EXPRESSIONS  **************************/
+  //
+  // Visit methods for tail expressions must return a statement directly
+  // (not a function like interior and call expressions).
 
-  Statement visitTypeCast(cps_ir.TypeCast node) {
+  Statement visitThrow(cps_ir.Throw node) {
     Expression value = getVariableUse(node.value);
-    List<Expression> typeArgs = translateArguments(node.typeArguments);
-    Expression expression =
-        new TypeOperator(value, node.type, typeArgs, isTypeTest: false);
-    return continueWithExpression(node.continuation, expression);
+    return new Throw(value);
   }
 
-  Expression visitTypeTest(cps_ir.TypeTest node) {
-    Expression value = getVariableUse(node.value);
-    List<Expression> typeArgs = translateArguments(node.typeArguments);
-    return new TypeOperator(value, node.type, typeArgs, isTypeTest: true);
+  Statement visitRethrow(cps_ir.Rethrow node) {
+    return new Rethrow();
   }
 
-  Statement visitInvokeConstructor(cps_ir.InvokeConstructor node) {
-    List<Expression> arguments = translateArguments(node.arguments);
-    Expression invoke = new InvokeConstructor(
-        node.type,
-        node.target,
-        node.selector,
-        arguments,
-        node.sourceInformation);
-    return continueWithExpression(node.continuation, invoke);
+  Statement visitUnreachable(cps_ir.Unreachable node) {
+    return new Unreachable();
   }
 
   Statement visitInvokeContinuation(cps_ir.InvokeContinuation node) {
@@ -470,35 +500,83 @@ class Builder implements cps_ir.Visitor<Node> {
             //     - Translate the recursive invocations to Continue.
             if (cont.isRecursive) {
               return node.isRecursive
-                  ? new Continue(labels[cont])
-                  : new WhileTrue(labels[cont], visit(cont.body));
+                  ? new Continue(getLabel(cont))
+                  : new WhileTrue(getLabel(cont), 
+                                  translateExpression(cont.body));
             } else {
-              if (cont.hasExactlyOneUse) {
-                if (!node.isEscapingTry) {
-                  return visit(cont.body);
-                }
-                labels[cont] = new Label();
-              }
-              return new Break(labels[cont]);
+              return cont.hasExactlyOneUse && !node.isEscapingTry
+                  ? translateExpression(cont.body)
+                  : new Break(getLabel(cont));
             }
           });
     }
   }
 
   Statement visitBranch(cps_ir.Branch node) {
-    Expression condition = visit(node.condition);
+    Expression condition = translateCondition(node.condition);
     Statement thenStatement, elseStatement;
     cps_ir.Continuation cont = node.trueContinuation.definition;
     assert(cont.parameters.isEmpty);
-    thenStatement =
-        cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]);
+    thenStatement = cont.hasExactlyOneUse 
+        ? translateExpression(cont.body) 
+        : new Break(labels[cont]);
     cont = node.falseContinuation.definition;
     assert(cont.parameters.isEmpty);
-    elseStatement =
-        cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]);
+    elseStatement = cont.hasExactlyOneUse 
+        ? translateExpression(cont.body) 
+        : new Break(labels[cont]);
     return new If(condition, thenStatement, elseStatement);
   }
 
+
+  /************************** PRIMITIVES  **************************/
+  // 
+  // Visit methods for primitives must return an expression.
+  //
+
+  Expression visitSetField(cps_ir.SetField node) {
+    return new SetField(getVariableUse(node.object),
+                        node.field,
+                        getVariableUse(node.value));
+  }
+  
+  Expression visitInterceptor(cps_ir.Interceptor node) {
+    return new Interceptor(getVariableUse(node.input), node.interceptedClasses);
+  }
+
+  Expression visitCreateInstance(cps_ir.CreateInstance node) {
+    return new CreateInstance(
+        node.classElement,
+        translateArguments(node.arguments),
+        translateArguments(node.typeInformation),
+        node.sourceInformation);
+  }
+
+  Expression visitGetField(cps_ir.GetField node) {
+    return new GetField(getVariableUse(node.object), node.field,
+        objectIsNotNull: node.objectIsNotNull);
+  }
+
+  Expression visitCreateBox(cps_ir.CreateBox node) {
+    return new CreateBox();
+  }
+
+  Expression visitCreateInvocationMirror(cps_ir.CreateInvocationMirror node) {
+    return new CreateInvocationMirror(
+        node.selector,
+        translateArguments(node.arguments));
+  }
+
+  Expression visitGetMutable(cps_ir.GetMutable node) {
+    return getMutableVariableUse(node.variable);
+  }
+
+  Expression visitSetMutable(cps_ir.SetMutable node) {
+    Variable variable = getMutableVariable(node.variable.definition);
+    Expression value = getVariableUse(node.value);
+    return new Assign(variable, value);
+  }
+
   Expression visitConstant(cps_ir.Constant node) {
     return new Constant(node.value, sourceInformation: node.sourceInformation);
   }
@@ -529,28 +607,6 @@ class Builder implements cps_ir.Visitor<Node> {
     return new FunctionExpression(def);
   }
 
-  visitParameter(cps_ir.Parameter node) {
-    // Continuation parameters are not visited (continuations themselves are
-    // not visited yet).
-    unexpectedNode(node);
-  }
-
-  visitContinuation(cps_ir.Continuation node) {
-    // Until continuations with multiple uses are supported, they are not
-    // visited.
-    unexpectedNode(node);
-  }
-
-  visitMutableVariable(cps_ir.MutableVariable node) {
-    // These occur as parameters or bound by LetMutable.  They are not visited
-    // directly.
-    unexpectedNode(node);
-  }
-
-  Expression visitIsTrue(cps_ir.IsTrue node) {
-    return getVariableUse(node.value);
-  }
-
   Expression visitReifyRuntimeType(cps_ir.ReifyRuntimeType node) {
     return new ReifyRuntimeType(
         getVariableUse(node.value), node.sourceInformation);
@@ -563,22 +619,20 @@ class Builder implements cps_ir.Visitor<Node> {
         node.sourceInformation);
   }
 
-  @override
-  Node visitTypeExpression(cps_ir.TypeExpression node) {
+  Expression visitTypeExpression(cps_ir.TypeExpression node) {
     return new TypeExpression(
         node.dartType,
         node.arguments.map(getVariableUse).toList());
   }
 
-  Expression visitGetStatic(cps_ir.GetStatic node) {
-    return new GetStatic(node.element, node.sourceInformation);
+  Expression visitTypeTest(cps_ir.TypeTest node) {
+    Expression value = getVariableUse(node.value);
+    List<Expression> typeArgs = translateArguments(node.typeArguments);
+    return new TypeOperator(value, node.type, typeArgs, isTypeTest: true);
   }
 
-  Statement visitGetLazyStatic(cps_ir.GetLazyStatic node) {
-    // In the tree IR, GetStatic handles lazy fields because tree
-    // expressions are allowed to have side effects.
-    GetStatic value = new GetStatic(node.element, node.sourceInformation);
-    return continueWithExpression(node.continuation, value);
+  Expression visitGetStatic(cps_ir.GetStatic node) {
+    return new GetStatic(node.element, node.sourceInformation);
   }
 
   Expression visitSetStatic(cps_ir.SetStatic node) {
@@ -596,26 +650,6 @@ class Builder implements cps_ir.Visitor<Node> {
                                     translateArguments(node.arguments));
   }
 
-  Statement visitForeignCode(cps_ir.ForeignCode node) {
-    if (node.codeTemplate.isExpression) {
-      Expression foreignCode = new ForeignExpression(
-          node.codeTemplate,
-          node.type,
-          node.arguments.map(getVariableUse).toList(growable: false),
-          node.nativeBehavior,
-          node.dependency);
-      return continueWithExpression(node.continuation, foreignCode);
-    } else {
-      assert(node.continuation.definition.body is cps_ir.Unreachable);
-      return new ForeignStatement(
-          node.codeTemplate,
-          node.type,
-          node.arguments.map(getVariableUse).toList(growable: false),
-          node.nativeBehavior,
-          node.dependency);
-    }
-  }
-
   Expression visitGetLength(cps_ir.GetLength node) {
     return new GetLength(getVariableUse(node.object));
   }
@@ -630,5 +664,19 @@ class Builder implements cps_ir.Visitor<Node> {
                         getVariableUse(node.index),
                         getVariableUse(node.value));
   }
+
+  /********** UNUSED VISIT METHODS *************/
+
+  unexpectedNode(cps_ir.Node node) {
+    internalError(CURRENT_ELEMENT_SPANNABLE, 'Unexpected IR node: $node');
+  }
+
+  visitFunctionDefinition(cps_ir.FunctionDefinition node) {
+    unexpectedNode(node);
+  }
+  visitParameter(cps_ir.Parameter node) => unexpectedNode(node);
+  visitContinuation(cps_ir.Continuation node) => unexpectedNode(node);
+  visitMutableVariable(cps_ir.MutableVariable node) => unexpectedNode(node);
+  visitIsTrue(cps_ir.IsTrue node) => unexpectedNode(node);
 }