dart2js cps: Maintain parent pointers instead of recomputing them.

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

Index: pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
diff --git a/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart b/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
index 0c28fa4cc9a53283df59ac6913a62231fc5a9492..cbb45f0e81aa9504dbe05bdf5a26d544672b77a4 100644
--- a/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
+++ b/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
@@ -28,7 +28,16 @@ abstract class Node {
   static int _usedHashCodes = 0;
   final int hashCode = ++_usedHashCodes;
 
+  Node() {
+    setParentPointers();
+  }
+
   accept(Visitor visitor);
+
+  /// Updates the [parent] of the immediate children to refer to this node.
+  ///
+  /// All constructors call this method to initialize parent pointers.
+  void setParentPointers();
 }
 
 /// Expressions can be evaluated, and may diverge, throw, and/or have
@@ -318,8 +327,12 @@ class LetPrim extends InteriorExpression {
   }
 
   accept(Visitor visitor) => visitor.visitLetPrim(this);
-}
 
+  void setParentPointers() {
+    primitive.parent = this;
+    if (body != null) body.parent = this;
+  }
+}
 
 /// Binding continuations.
 ///
@@ -354,6 +367,11 @@ class LetCont extends InteriorExpression {
   }
 
   accept(Visitor visitor) => visitor.visitLetCont(this);
+
+  void setParentPointers() {
+    _setParentsOnNodes(continuations, this);
+    if (body != null) body.parent = this;
+  }
 }
 
 // Binding an exception handler.
@@ -372,6 +390,11 @@ class LetHandler extends InteriorExpression {
   LetHandler(this.handler, this.body);
 
   accept(Visitor visitor) => visitor.visitLetHandler(this);
+
+  void setParentPointers() {
+    handler.parent = this;
+    if (body != null) body.parent = this;
+  }
 }
 
 /// Binding mutable variables.
@@ -396,6 +419,12 @@ class LetMutable extends InteriorExpression {
   }
 
   accept(Visitor visitor) => visitor.visitLetMutable(this);
+
+  void setParentPointers() {
+    variable.parent = this;
+    value.parent = this;
+    if (body != null) body.parent = this;
+  }
 }
 
 /// Invoke a static function.
@@ -428,6 +457,11 @@ class InvokeStatic extends CallExpression {
                            [this.sourceInformation]);
 
   accept(Visitor visitor) => visitor.visitInvokeStatic(this);
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 /// Invoke a method on an object.
@@ -479,6 +513,12 @@ class InvokeMethod extends CallExpression {
                            this.sourceInformation);
 
   accept(Visitor visitor) => visitor.visitInvokeMethod(this);
+
+  void setParentPointers() {
+    receiver.parent = this;
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 /// Invoke [target] on [receiver], bypassing dispatch and override semantics.
@@ -519,6 +559,12 @@ class InvokeMethodDirectly extends CallExpression {
         this.continuation = new Reference<Continuation>(continuation);
 
   accept(Visitor visitor) => visitor.visitInvokeMethodDirectly(this);
+
+  void setParentPointers() {
+    receiver.parent = this;
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 /// Non-const call to a constructor.
@@ -554,6 +600,11 @@ class InvokeConstructor extends CallExpression {
         continuation = new Reference<Continuation>(cont);
 
   accept(Visitor visitor) => visitor.visitInvokeConstructor(this);
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 /// An alias for [value] in a context where the value is known to satisfy
@@ -576,6 +627,10 @@ class Refinement extends Primitive {
   accept(Visitor visitor) => visitor.visitRefinement(this);
 
   Primitive get effectiveDefinition => value.definition.effectiveDefinition;
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// An "is" type test.
@@ -618,6 +673,12 @@ class TypeTest extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    value.parent = this;
+    _setParentsOnList(typeArguments, this);
+    if (interceptor != null) interceptor.parent = this;
+  }
 }
 
 /// An "is" type test for a raw type, performed by testing a flag property.
@@ -634,6 +695,10 @@ class TypeTestViaFlag extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    interceptor.parent = this;
+  }
 }
 
 /// An "as" type cast.
@@ -663,6 +728,10 @@ class TypeCast extends CallExpression {
         this.continuation = new Reference<Continuation>(cont);
 
   accept(Visitor visitor) => visitor.visitTypeCast(this);
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Apply a built-in operator.
@@ -682,6 +751,10 @@ class ApplyBuiltinOperator extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+  }
 }
 
 /// Apply a built-in method.
@@ -707,6 +780,11 @@ class ApplyBuiltinMethod extends Primitive {
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    receiver.parent = this;
+    _setParentsOnList(arguments, this);
+  }
 }
 
 /// Throw a value.
@@ -719,6 +797,10 @@ class Throw extends TailExpression {
   Throw(Primitive value) : value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitThrow(this);
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Rethrow
@@ -728,6 +810,7 @@ class Throw extends TailExpression {
 /// the same stack trace as the enclosing handler.
 class Rethrow extends TailExpression {
   accept(Visitor visitor) => visitor.visitRethrow(this);
+  void setParentPointers() {}
 }
 
 /// An expression that is known to be unreachable.
@@ -736,6 +819,7 @@ class Rethrow extends TailExpression {
 /// known never to invoke it, e.g. because the calling expression always throws.
 class Unreachable extends TailExpression {
   accept(Visitor visitor) => visitor.visitUnreachable(this);
+  void setParentPointers() {}
 }
 
 /// Gets the value from a [MutableVariable].
@@ -755,6 +839,10 @@ class GetMutable extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    variable.parent = this;
+  }
 }
 
 /// Assign a [MutableVariable].
@@ -775,6 +863,11 @@ class SetMutable extends Primitive {
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    variable.parent = this;
+    value.parent = this;
+  }
 }
 
 /// Invoke a continuation in tail position.
@@ -813,6 +906,11 @@ class InvokeContinuation extends TailExpression {
         sourceInformation = null;
 
   accept(Visitor visitor) => visitor.visitInvokeContinuation(this);
+
+  void setParentPointers() {
+    if (continuation != null) continuation.parent = this;
+    if (arguments != null) _setParentsOnList(arguments, this);
+  }
 }
 
 /// Choose between a pair of continuations based on a condition value.
@@ -847,6 +945,12 @@ class Branch extends TailExpression {
         this.isStrictCheck = false;
 
   accept(Visitor visitor) => visitor.visitBranch(this);
+
+  void setParentPointers() {
+    condition.parent = this;
+    trueContinuation.parent = this;
+    falseContinuation.parent = this;
+  }
 }
 
 /// Directly assigns to a field on a given object.
@@ -863,6 +967,11 @@ class SetField extends Primitive {
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    object.parent = this;
+    value.parent = this;
+  }
 }
 
 /// Directly reads from a field on a given object.
@@ -886,6 +995,10 @@ class GetField extends Primitive {
   bool get isSafeForReordering => false;
 
   toString() => 'GetField($field)';
+
+  void setParentPointers() {
+    object.parent = this;
+  }
 }
 
 /// Get the length of a string or native list.
@@ -901,6 +1014,10 @@ class GetLength extends Primitive {
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitGetLength(this);
+
+  void setParentPointers() {
+    object.parent = this;
+  }
 }
 
 /// Read an entry from a string or native list.
@@ -922,6 +1039,11 @@ class GetIndex extends Primitive {
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitGetIndex(this);
+
+  void setParentPointers() {
+    object.parent = this;
+    index.parent = this;
+  }
 }
 
 /// Set an entry on a native list.
@@ -943,6 +1065,12 @@ class SetIndex extends Primitive {
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitSetIndex(this);
+
+  void setParentPointers() {
+    object.parent = this;
+    index.parent = this;
+    value.parent = this;
+  }
 }
 
 /// Reads the value of a static field or tears off a static method.
@@ -963,6 +1091,8 @@ class GetStatic extends Primitive {
   bool get isSafeForReordering {
     return element is FunctionElement || element.isFinal;
   }
+
+  void setParentPointers() {}
 }
 
 /// Sets the value of a static field.
@@ -978,6 +1108,10 @@ class SetStatic extends Primitive {
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Reads the value of a lazily initialized static field.
@@ -997,6 +1131,10 @@ class GetLazyStatic extends CallExpression {
       : continuation = new Reference<Continuation>(continuation);
 
   accept(Visitor visitor) => visitor.visitGetLazyStatic(this);
+
+  void setParentPointers() {
+    continuation.parent = this;
+  }
 }
 
 /// Creates an object for holding boxed variables captured by a closure.
@@ -1005,6 +1143,8 @@ class CreateBox extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 /// Creates an instance of a class and initializes its fields and runtime type
@@ -1037,6 +1177,11 @@ class CreateInstance extends Primitive {
   bool get isSafeForReordering => true;
 
   toString() => 'CreateInstance($classElement)';
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    if (typeInformation != null) _setParentsOnList(typeInformation, this);
+  }
 }
 
 class Interceptor extends Primitive {
@@ -1063,6 +1208,10 @@ class Interceptor extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    input.parent = this;
+  }
 }
 
 /// Create an instance of [Invocation] for use in a call to `noSuchMethod`.
@@ -1077,6 +1226,10 @@ class CreateInvocationMirror extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+  }
 }
 
 class ForeignCode extends CallExpression {
@@ -1093,6 +1246,11 @@ class ForeignCode extends CallExpression {
         this.continuation = new Reference<Continuation>(continuation);
 
   accept(Visitor visitor) => visitor.visitForeignCode(this);
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 class Constant extends Primitive {
@@ -1107,6 +1265,8 @@ class Constant extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 class LiteralList extends Primitive {
@@ -1121,6 +1281,10 @@ class LiteralList extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(values, this);
+  }
 }
 
 class LiteralMapEntry {
@@ -1142,6 +1306,13 @@ class LiteralMap extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    for (LiteralMapEntry entry in entries) {
+      entry.key.parent = this;
+      entry.value.parent = this;
+    }
+  }
 }
 
 /// Currently unused.
@@ -1163,6 +1334,8 @@ class CreateFunction extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 class Parameter extends Primitive {
@@ -1170,18 +1343,14 @@ class Parameter extends Primitive {
     super.hint = hint;
   }
 
-  // In addition to a parent pointer to the containing Continuation or
-  // FunctionDefinition, parameters have an index into the list of parameters
-  // bound by the parent.  This gives constant-time access to the continuation
-  // from the parent.
-  int parentIndex;
-
   accept(Visitor visitor) => visitor.visitParameter(this);
 
   String toString() => 'Parameter(${hint == null ? null : hint.name})';
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 /// Continuations are normally bound by 'let cont'.  A continuation with one
@@ -1191,11 +1360,6 @@ class Continuation extends Definition<Continuation> implements InteriorNode {
   final List<Parameter> parameters;
   Expression body = null;
 
-  // In addition to a parent pointer to the containing LetCont, continuations
-  // have an index into the list of continuations bound by the LetCont.  This
-  // gives constant-time access to the continuation from the parent.
-  int parent_index;
-
   // A continuation is recursive if it has any recursive invocations.
   bool isRecursive;
 
@@ -1208,6 +1372,11 @@ class Continuation extends Definition<Continuation> implements InteriorNode {
       isRecursive = false;
 
   accept(Visitor visitor) => visitor.visitContinuation(this);
+
+  void setParentPointers() {
+    _setParentsOnNodes(parameters, this);
+    if (body != null) body.parent = this;
+  }
 }
 
 /// Common interface for [Primitive] and [MutableVariable].
@@ -1225,6 +1394,8 @@ class MutableVariable extends Variable<MutableVariable> {
   MutableVariable(this.hint);
 
   accept(Visitor v) => v.visitMutableVariable(this);
+
+  void setParentPointers() {}
 }
 
 /// A function definition, consisting of parameters and a body.
@@ -1245,6 +1416,13 @@ class FunctionDefinition extends InteriorNode {
       this.body);
 
   accept(Visitor visitor) => visitor.visitFunctionDefinition(this);
+
+  void setParentPointers() {
+    if (thisParameter != null) thisParameter.parent = this;
+    _setParentsOnNodes(parameters, this);
+    returnContinuation.parent = this;
+    if (body != null) body.parent = this;
+  }
 }
 
 /// Converts the internal representation of a type to a Dart object of type
@@ -1264,6 +1442,10 @@ class ReifyRuntimeType extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Read the value the type variable [variable] from the target object.
@@ -1284,6 +1466,10 @@ class ReadTypeVariable extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    target.parent = this;
+  }
 }
 
 /// Representation of a closed type (that is, a type without type variables).
@@ -1309,6 +1495,10 @@ class TypeExpression extends Primitive {
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+  }
 }
 
 class Await extends CallExpression {
@@ -1323,6 +1513,11 @@ class Await extends CallExpression {
   accept(Visitor visitor) {
     return visitor.visitAwait(this);
   }
+
+  void setParentPointers() {
+    input.parent = this;
+    continuation.parent = this;
+  }
 }
 
 class Yield extends CallExpression {
@@ -1338,12 +1533,29 @@ class Yield extends CallExpression {
   accept(Visitor visitor) {
     return visitor.visitYield(this);
   }
+
+  void setParentPointers() {
+    input.parent = this;
+    continuation.parent = this;
+  }
 }
 
 List<Reference<Primitive>> _referenceList(Iterable<Primitive> definitions) {
   return definitions.map((e) => new Reference<Primitive>(e)).toList();
 }
 
+void _setParentsOnNodes(List<Node> nodes, Node parent) {
+  for (Node node in nodes) {
+    node.parent = parent;
+  }
+}
+
+void _setParentsOnList(List<Reference> nodes, Node parent) {
+  for (Reference node in nodes) {
+    node.parent = parent;
+  }
+}
+
 abstract class Visitor<T> {
   const Visitor();
 
@@ -1405,13 +1617,20 @@ abstract class Visitor<T> {
   T visitForeignCode(ForeignCode node);
 }
 
-/// Visits all non-recursive children of a CPS term, i.e. anything
-/// not of type [Expression] or [Continuation].
+/// Recursively visits all children of a CPS term.
+///
+/// The user of the class is responsible for avoiding stack overflows from
+/// deep recursion, e.g. by overriding methods to cut off recursion at certain
+/// points.
+///
+/// All recursive invocations occur through the [visit] method, which the
+/// subclass may override as a generic way to control the visitor without
+/// overriding all visitor methods.
 ///
 /// The `process*` methods are called in pre-order for every node visited.
 /// These can be overridden without disrupting the visitor traversal.
-class LeafVisitor implements Visitor {
-  const LeafVisitor();
+class DeepRecursiveVisitor implements Visitor {
+  const DeepRecursiveVisitor();
 
   visit(Node node) => node.accept(this);
 
@@ -1423,25 +1642,36 @@ class LeafVisitor implements Visitor {
     if (node.thisParameter != null) visit(node.thisParameter);
     node.parameters.forEach(visit);
     visit(node.returnContinuation);
+    visit(node.body);
   }
 
-  // Expressions.
+  processContinuation(Continuation node) {}
+  visitContinuation(Continuation node) {
+    processContinuation(node);
+    node.parameters.forEach(visit);
+    if (node.body != null) visit(node.body);
+  }
 
+  // Expressions.
   processLetPrim(LetPrim node) {}
   visitLetPrim(LetPrim node) {
     processLetPrim(node);
     visit(node.primitive);
+    visit(node.body);
   }
 
   processLetCont(LetCont node) {}
   visitLetCont(LetCont node) {
     processLetCont(node);
     node.continuations.forEach(visit);
+    visit(node.body);
   }
 
   processLetHandler(LetHandler node) {}
   visitLetHandler(LetHandler node) {
     processLetHandler(node);
+    visit(node.handler);
+    visit(node.body);
   }
 
   processLetMutable(LetMutable node) {}
@@ -1449,6 +1679,7 @@ class LeafVisitor implements Visitor {
     processLetMutable(node);
     visit(node.variable);
     processReference(node.value);
+    visit(node.body);
   }
 
   processInvokeStatic(InvokeStatic node) {}
@@ -1584,12 +1815,6 @@ class LeafVisitor implements Visitor {
     processParameter(node);
   }
 
-  processContinuation(Continuation node) {}
-  visitContinuation(Continuation node) {
-    processContinuation(node);
-    node.parameters.forEach(visitParameter);
-  }
-
   processInterceptor(Interceptor node) {}
   visitInterceptor(Interceptor node) {
     processInterceptor(node);
@@ -1750,7 +1975,7 @@ typedef void StackAction();
 ///
 /// Subclasses should not override the `visit` methods for the nodes that have
 /// a `traverse` method.
-class RecursiveVisitor extends LeafVisitor {
+class TrampolineRecursiveVisitor extends DeepRecursiveVisitor {
   List<StackAction> _stack = <StackAction>[];
 
   void pushAction(StackAction callback) {
@@ -1845,7 +2070,7 @@ class RecursiveVisitor extends LeafVisitor {
 }
 
 /// Visit a just-deleted subterm and unlink all [Reference]s in it.
-class RemovalVisitor extends RecursiveVisitor {
+class RemovalVisitor extends TrampolineRecursiveVisitor {
   processReference(Reference reference) {
     reference.unlink();
   }