dart2js cps: Maintain parent pointers instead of recomputing them.

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

 // Copyright (c) 2013, 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.
 library dart2js.ir_nodes;
 
 import 'dart:collection';
 import '../constants/values.dart' as values;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
 import '../io/source_information.dart' show SourceInformation;
@@ skipping 10 matching lines @@
 import '../native/native.dart' as native show NativeBehavior;
 
 abstract class Node {
   /// A pointer to the parent node. Is null until set by optimization passes.
   Node parent;
 
   /// Workaround for a slow Object.hashCode in the VM.
   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
 /// side-effects.
 ///
 /// Evaluation continues by stepping into a sub-expression, invoking a
 /// continuation, or throwing an exception.
 ///
 /// Expressions do not a return value. Expressions that produce values should
 /// invoke a [Continuation] with the result as argument. Alternatively, values
@@ skipping 269 matching lines @@
   Expression body;
 
   LetPrim(this.primitive, [this.body = null]);
 
   Expression plug(Expression expr) {
     assert(body == null);
     return body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitLetPrim(this);
+
+  void setParentPointers() {
+    primitive.parent = this;
+    if (body != null) body.parent = this;
+  }
 }
 
-
 /// Binding continuations.
 ///
 /// let cont k0(v0 ...) = E0
 ///          k1(v1 ...) = E1
 ///          ...
 ///   in E
 ///
 /// The bound continuations are in scope in the body and the continuation
 /// parameters are in scope in the respective continuation bodies.
 ///
@@ skipping 13 matching lines @@
   LetCont.many(this.continuations, this.body);
 
   Expression plug(Expression expr) {
     assert(continuations != null &&
            continuations.isNotEmpty &&
            continuations.first.body == null);
     return continuations.first.body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitLetCont(this);
+
+  void setParentPointers() {
+    _setParentsOnNodes(continuations, this);
+    if (body != null) body.parent = this;
+  }
 }
 
 // Binding an exception handler.
 //
 // let handler h(v0, v1) = E0 in E1
 //
 // The handler is a two-argument (exception, stack trace) continuation which
 // is implicitly the error continuation of all the code in its body E1.
 // [LetHandler] differs from a [LetCont] binding in that it (1) has the
 // runtime semantics of pushing/popping a handler from the dynamic exception
 // handler stack and (2) it does not have any explicit invocations.
 class LetHandler extends InteriorExpression {
   Continuation handler;
   Expression body;
 
   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.
 ///
 /// let mutable v = P in E
 ///
 /// [MutableVariable]s can be seen as ref cells that are not first-class
 /// values.  They are therefore not [Primitive]s and not bound by [LetPrim]
 /// to prevent unrestricted use of references to them.  During one-pass
 /// construction, a [LetMutable] with an empty body is use to represent the
 /// one-hole context 'let mutable v = P in []'.
 class LetMutable extends InteriorExpression {
   final MutableVariable variable;
   final Reference<Primitive> value;
   Expression body;
 
   LetMutable(this.variable, Primitive value)
       : this.value = new Reference<Primitive>(value);
 
   Expression plug(Expression expr) {
     return body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitLetMutable(this);
+
+  void setParentPointers() {
+    variable.parent = this;
+    value.parent = this;
+    if (body != null) body.parent = this;
+  }
 }
 
 /// Invoke a static function.
 ///
 /// All optional arguments declared by [target] are passed in explicitly, and
 /// occur at the end of [arguments] list, in normalized order.
 ///
 /// Discussion:
 /// All information in the [selector] is technically redundant; it will likely
 /// be removed.
@@ skipping 12 matching lines @@
       : arguments = _referenceList(args),
         continuation = new Reference<Continuation>(cont);
 
   InvokeStatic.byReference(this.target,
                            this.selector,
                            this.arguments,
                            this.continuation,
                            [this.sourceInformation]);
 
   accept(Visitor visitor) => visitor.visitInvokeStatic(this);
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 /// Invoke a method on an object.
 ///
 /// This includes getters, setters, operators, and index getter/setters.
 ///
 /// Tearing off a method is treated like a getter invocation (getters and
 /// tear-offs cannot be distinguished at compile-time).
 ///
 /// The [selector] records the names of named arguments. The value of named
@@ skipping 31 matching lines @@
         this.continuation = new Reference<Continuation>(continuation);
 
   InvokeMethod.byReference(this.receiver,
                            this.selector,
                            this.mask,
                            this.arguments,
                            this.continuation,
                            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.
 ///
 /// That is, if [receiver] is an instance of a class that overrides [target]
 /// with a different implementation, the overriding implementation is bypassed
 /// and [target]'s implementation is invoked.
 ///
 /// As with [InvokeMethod], this can be used to invoke a method, operator,
 /// getter, setter, or index getter/setter.
@@ skipping 20 matching lines @@
                        this.target,
                        this.selector,
                        List<Primitive> arguments,
                        Continuation continuation,
                        this.sourceInformation)
       : this.receiver = new Reference<Primitive>(receiver),
         this.arguments = _referenceList(arguments),
         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.
 ///
 /// The [target] may be a generative constructor (forwarding or normal)
 /// or a non-redirecting factory.
 ///
 /// All optional arguments declared by [target] are passed in explicitly, and
 /// occur in the [arguments] list, in normalized order.
 ///
@@ skipping 15 matching lines @@
   InvokeConstructor(this.dartType,
                     this.target,
                     this.selector,
                     List<Primitive> args,
                     Continuation cont,
                     this.sourceInformation)
       : arguments = _referenceList(args),
         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
 /// [type].
 ///
 /// Refinement nodes are inserted before the type propagator pass and removed
 /// afterwards, so as not to complicate passes that don't reason about types,
 /// but need to reason about value references being identical (i.e. referring
 /// to the same primitive).
 class Refinement extends Primitive {
   Reference<Primitive> value;
   final TypeMask refineType;
 
   Refinement(Primitive value, this.refineType)
     : value = new Reference<Primitive>(value);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => false;
 
   accept(Visitor visitor) => visitor.visitRefinement(this);
 
   Primitive get effectiveDefinition => value.definition.effectiveDefinition;
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// An "is" type test.
 ///
 /// Returns `true` if [value] is an instance of [type].
 ///
 /// [type] must not be the [Object], `dynamic` or [Null] types (though it might
 /// be a type variable containing one of these types). This design is chosen
 /// to simplify code generation for type tests.
 class TypeTest extends Primitive {
@@ skipping 22 matching lines @@
   TypeTest(Primitive value,
            this.dartType,
            List<Primitive> typeArguments)
       : this.value = new Reference<Primitive>(value),
         this.typeArguments = _referenceList(typeArguments);
 
   accept(Visitor visitor) => visitor.visitTypeTest(this);
 
   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.
 ///
 /// Returns `true` if [interceptor] is for [dartType].
 class TypeTestViaFlag extends Primitive {
   Reference<Primitive> interceptor;
   final DartType dartType;
 
   TypeTestViaFlag(Primitive interceptor, this.dartType)
       : this.interceptor = new Reference<Primitive>(interceptor);
 
   accept(Visitor visitor) => visitor.visitTypeTestViaFlag(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    interceptor.parent = this;
+  }
 }
 
 /// An "as" type cast.
 ///
 /// If [value] is `null` or is an instance of [type], [continuation] is invoked
 /// with [value] as argument. Otherwise, a [CastError] is thrown.
 ///
 /// Discussion:
 /// The parameter to [continuation] is redundant since it will always equal
 /// [value], which is typically in scope in the continuation. However, it might
 /// simplify type propagation, since a better type can be computed for the
 /// continuation parameter without needing flow-sensitive analysis.
 class TypeCast extends CallExpression {
   Reference<Primitive> value;
   final DartType dartType;
 
   /// See the corresponding field on [TypeTest].
   final List<Reference<Primitive>> typeArguments;
   final Reference<Continuation> continuation;
 
   TypeCast(Primitive value,
            this.dartType,
            List<Primitive> typeArguments,
            Continuation cont)
       : this.value = new Reference<Primitive>(value),
         this.typeArguments = _referenceList(typeArguments),
         this.continuation = new Reference<Continuation>(cont);
 
   accept(Visitor visitor) => visitor.visitTypeCast(this);
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Apply a built-in operator.
 ///
 /// It must be known that the arguments have the proper types.
 class ApplyBuiltinOperator extends Primitive {
   BuiltinOperator operator;
   List<Reference<Primitive>> arguments;
   final SourceInformation sourceInformation;
 
   ApplyBuiltinOperator(this.operator,
                        List<Primitive> arguments,
                        this.sourceInformation)
       : this.arguments = _referenceList(arguments);
 
   accept(Visitor visitor) => visitor.visitApplyBuiltinOperator(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+  }
 }
 
 /// Apply a built-in method.
 ///
 /// It must be known that the arguments have the proper types.
 class ApplyBuiltinMethod extends Primitive {
   BuiltinMethod method;
   Reference<Primitive> receiver;
   List<Reference<Primitive>> arguments;
   final SourceInformation sourceInformation;
 
   bool receiverIsNotNull;
 
   ApplyBuiltinMethod(this.method,
                      Primitive receiver,
                      List<Primitive> arguments,
                      this.sourceInformation,
                      {this.receiverIsNotNull: false})
       : this.receiver = new Reference<Primitive>(receiver),
         this.arguments = _referenceList(arguments);
 
   accept(Visitor visitor) => visitor.visitApplyBuiltinMethod(this);
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    receiver.parent = this;
+    _setParentsOnList(arguments, this);
+  }
 }
 
 /// Throw a value.
 ///
 /// Throw is an expression, i.e., it always occurs in tail position with
 /// respect to a body or expression.
 class Throw extends TailExpression {
   Reference<Primitive> value;
 
   Throw(Primitive value) : value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitThrow(this);
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Rethrow
 ///
 /// Rethrow can only occur inside a continuation bound by [LetHandler].  It
 /// implicitly throws the exception parameter of the enclosing handler with
 /// 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.
 ///
 /// This can be placed as the body of a call continuation, when the caller is
 /// 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].
 ///
 /// [MutableVariable]s can be seen as ref cells that are not first-class
 /// values.  A [LetPrim] with a [GetMutable] can then be seen as:
 ///
 ///   let prim p = ![variable] in [body]
 ///
 class GetMutable extends Primitive {
   final Reference<MutableVariable> variable;
 
   GetMutable(MutableVariable variable)
       : this.variable = new Reference<MutableVariable>(variable);
 
   accept(Visitor visitor) => visitor.visitGetMutable(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    variable.parent = this;
+  }
 }
 
 /// Assign a [MutableVariable].
 ///
 /// [MutableVariable]s can be seen as ref cells that are not first-class
 /// values.  This can be seen as a dereferencing assignment:
 ///
 ///   { [variable] := [value]; [body] }
 class SetMutable extends Primitive {
   final Reference<MutableVariable> variable;
   final Reference<Primitive> value;
 
   SetMutable(MutableVariable variable, Primitive value)
       : this.variable = new Reference<MutableVariable>(variable),
         this.value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitSetMutable(this);
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    variable.parent = this;
+    value.parent = this;
+  }
 }
 
 /// Invoke a continuation in tail position.
 class InvokeContinuation extends TailExpression {
   Reference<Continuation> continuation;
   List<Reference<Primitive>> arguments;
   SourceInformation sourceInformation;
 
   // An invocation of a continuation is recursive if it occurs in the body of
   // the continuation itself.
@@ skipping 18 matching lines @@
   ///
   /// Used as a placeholder for a jump whose target is not yet created
   /// (e.g., in the translation of break and continue).
   InvokeContinuation.uninitialized({this.isRecursive: false,
                                     this.isEscapingTry: false})
       : continuation = null,
         arguments = null,
         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.
 ///
 /// The two continuations must not declare any parameters.
 class Branch extends TailExpression {
   final Reference<Primitive> condition;
   final Reference<Continuation> trueContinuation;
   final Reference<Continuation> falseContinuation;
 
@@ skipping 14 matching lines @@
 
   Branch.loose(Primitive condition,
                Continuation trueCont,
                Continuation falseCont)
       : this.condition = new Reference<Primitive>(condition),
         trueContinuation = new Reference<Continuation>(trueCont),
         falseContinuation = new Reference<Continuation>(falseCont),
         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.
 class SetField extends Primitive {
   final Reference<Primitive> object;
   FieldElement field;
   final Reference<Primitive> value;
 
   SetField(Primitive object, this.field, Primitive value)
       : this.object = new Reference<Primitive>(object),
         this.value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitSetField(this);
 
   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.
 ///
 /// The [object] must either be `null` or an object that has [field].
 class GetField extends Primitive {
   final Reference<Primitive> object;
   FieldElement field;
 
   /// True if the object is known not to be null.
   // TODO(asgerf): This is a placeholder until we agree on how to track
   //               side effects.
   bool objectIsNotNull = false;
 
   GetField(Primitive object, this.field)
       : this.object = new Reference<Primitive>(object);
 
   accept(Visitor visitor) => visitor.visitGetField(this);
 
   bool get isSafeForElimination => objectIsNotNull;
   bool get isSafeForReordering => false;
 
   toString() => 'GetField($field)';
+
+  void setParentPointers() {
+    object.parent = this;
+  }
 }
 
 /// Get the length of a string or native list.
 class GetLength extends Primitive {
   final Reference<Primitive> object;
 
   /// True if the object is known not to be null.
   bool objectIsNotNull = false;
 
   GetLength(Primitive object) : this.object = new Reference<Primitive>(object);
 
   bool get isSafeForElimination => objectIsNotNull;
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitGetLength(this);
+
+  void setParentPointers() {
+    object.parent = this;
+  }
 }
 
 /// Read an entry from a string or native list.
 ///
 /// [object] must be null or a native list or a string, and [index] must be
 /// an integer.
 class GetIndex extends Primitive {
   final Reference<Primitive> object;
   final Reference<Primitive> index;
 
   /// True if the object is known not to be null.
   bool objectIsNotNull = false;
 
   GetIndex(Primitive object, Primitive index)
       : this.object = new Reference<Primitive>(object),
         this.index = new Reference<Primitive>(index);
 
   bool get isSafeForElimination => objectIsNotNull;
   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.
 ///
 /// [object] must be null or a native list, and [index] must be an integer.
 ///
 /// The primitive itself has no value and may not be referenced.
 class SetIndex extends Primitive {
   final Reference<Primitive> object;
   final Reference<Primitive> index;
   final Reference<Primitive> value;
 
   SetIndex(Primitive object, Primitive index, Primitive value)
       : this.object = new Reference<Primitive>(object),
         this.index = new Reference<Primitive>(index),
         this.value = new Reference<Primitive>(value);
 
   bool get isSafeForElimination => false;
   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.
 ///
 /// Note that lazily initialized fields should be read using GetLazyStatic.
 class GetStatic extends Primitive {
   /// Can be [FieldElement] or [FunctionElement].
   final Element element;
   final SourceInformation sourceInformation;
 
   GetStatic(this.element, [this.sourceInformation]);
 
   accept(Visitor visitor) => visitor.visitGetStatic(this);
 
   bool get isSafeForElimination {
     return true;
   }
   bool get isSafeForReordering {
     return element is FunctionElement || element.isFinal;
   }
+
+  void setParentPointers() {}
 }
 
 /// Sets the value of a static field.
 class SetStatic extends Primitive {
   final FieldElement element;
   final Reference<Primitive> value;
   final SourceInformation sourceInformation;
 
   SetStatic(this.element, Primitive value, [this.sourceInformation])
       : this.value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitSetStatic(this);
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Reads the value of a lazily initialized static field.
 ///
 /// If the field has not yet been initialized, its initializer is evaluated
 /// and assigned to the field.
 ///
 /// [continuation] is then invoked with the value of the field as argument.
 class GetLazyStatic extends CallExpression {
   final FieldElement element;
   final Reference<Continuation> continuation;
   final SourceInformation sourceInformation;
 
   GetLazyStatic(this.element,
                 Continuation continuation,
                 [this.sourceInformation])
       : 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.
 class CreateBox extends Primitive {
   accept(Visitor visitor) => visitor.visitCreateBox(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 /// Creates an instance of a class and initializes its fields and runtime type
 /// information.
 class CreateInstance extends Primitive {
   final ClassElement classElement;
 
   /// Initial values for the fields on the class.
   /// The order corresponds to the order of fields on the class.
   final List<Reference<Primitive>> arguments;
@@ skipping 12 matching lines @@
       this.sourceInformation)
       : this.arguments = _referenceList(arguments),
         this.typeInformation = _referenceList(typeInformation);
 
   accept(Visitor visitor) => visitor.visitCreateInstance(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
 
   toString() => 'CreateInstance($classElement)';
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    if (typeInformation != null) _setParentsOnList(typeInformation, this);
+  }
 }
 
 class Interceptor extends Primitive {
   final Reference<Primitive> input;
   final Set<ClassElement> interceptedClasses = new Set<ClassElement>();
   final SourceInformation sourceInformation;
 
   /// If non-null, all uses of this the interceptor call are guaranteed to
   /// see this value.
   ///
   /// The interceptor call is not immediately replaced by the constant, because
   /// that might prevent the interceptor from being shared.
   ///
   /// The precise input type is not known when sharing interceptors, because
   /// refinement nodes have been removed by then. So this field carries the
   /// known constant until we know if it should be shared or replaced by
   /// the constant.
   values.InterceptorConstantValue constantValue;
 
   Interceptor(Primitive input, this.sourceInformation)
       : this.input = new Reference<Primitive>(input);
 
   accept(Visitor visitor) => visitor.visitInterceptor(this);
 
   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`.
 class CreateInvocationMirror extends Primitive {
   final Selector selector;
   final List<Reference<Primitive>> arguments;
 
   CreateInvocationMirror(this.selector, List<Primitive> arguments)
       : this.arguments = _referenceList(arguments);
 
   accept(Visitor visitor) => visitor.visitCreateInvocationMirror(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+  }
 }
 
 class ForeignCode extends CallExpression {
   final js.Template codeTemplate;
   final TypeMask type;
   final List<Reference<Primitive>> arguments;
   final native.NativeBehavior nativeBehavior;
   final FunctionElement dependency;
   final Reference<Continuation> continuation;
 
   ForeignCode(this.codeTemplate, this.type, List<Primitive> arguments,
       this.nativeBehavior, Continuation continuation, {this.dependency})
       : this.arguments = _referenceList(arguments),
         this.continuation = new Reference<Continuation>(continuation);
 
   accept(Visitor visitor) => visitor.visitForeignCode(this);
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+    continuation.parent = this;
+  }
 }
 
 class Constant extends Primitive {
   final values.ConstantValue value;
   final SourceInformation sourceInformation;
 
   Constant(this.value, {this.sourceInformation}) {
     assert(value != null);
   }
 
   accept(Visitor visitor) => visitor.visitConstant(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 class LiteralList extends Primitive {
   /// The List type being created; this is not the type argument.
   final InterfaceType dartType;
   final List<Reference<Primitive>> values;
 
   LiteralList(this.dartType, List<Primitive> values)
       : this.values = _referenceList(values);
 
   accept(Visitor visitor) => visitor.visitLiteralList(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(values, this);
+  }
 }
 
 class LiteralMapEntry {
   final Reference<Primitive> key;
   final Reference<Primitive> value;
 
   LiteralMapEntry(Primitive key, Primitive value)
       : this.key = new Reference<Primitive>(key),
         this.value = new Reference<Primitive>(value);
 }
 
 class LiteralMap extends Primitive {
   final InterfaceType dartType;
   final List<LiteralMapEntry> entries;
 
   LiteralMap(this.dartType, this.entries);
 
   accept(Visitor visitor) => visitor.visitLiteralMap(this);
 
   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.
 ///
 /// Nested functions (from Dart code) are translated to classes by closure
 /// conversion, hence they are instantiated with [CreateInstance].
 ///
 /// We keep this around for now because it might come in handy when we
 /// handle async/await in the CPS IR.
 ///
 /// Instantiates a nested function. [MutableVariable]s are in scope in the
 /// inner function, but primitives are not shared across function boundaries.
 class CreateFunction extends Primitive {
   final FunctionDefinition definition;
 
   CreateFunction(this.definition);
 
   accept(Visitor visitor) => visitor.visitCreateFunction(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {}
 }
 
 class Parameter extends Primitive {
   Parameter(Entity hint) {
     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
 /// parameter and no body is used to represent a function's return continuation.
 /// The return continuation is bound by the function, not by 'let cont'.
 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;
 
   bool get isReturnContinuation => body == null;
 
   Continuation(this.parameters, {this.isRecursive: false});
 
   Continuation.retrn()
     : parameters = <Parameter>[new Parameter(null)],
       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].
 abstract class Variable<T extends Variable<T>> extends Definition<T> {
   /// Type of value held in the variable.
   ///
   /// Is `null` until initialized by type propagation.
   TypeMask type;
 }
 
 /// Identifies a mutable variable.
 class MutableVariable extends Variable<MutableVariable> {
   Entity hint;
 
   MutableVariable(this.hint);
 
   accept(Visitor v) => v.visitMutableVariable(this);
+
+  void setParentPointers() {}
 }
 
 /// A function definition, consisting of parameters and a body.
 ///
 /// There is an explicit parameter for the `this` argument, and a return
 /// continuation to invoke when returning from the function.
 class FunctionDefinition extends InteriorNode {
   final ExecutableElement element;
   final Parameter thisParameter;
   final List<Parameter> parameters;
   final Continuation returnContinuation;
   Expression body;
 
   FunctionDefinition(this.element,
       this.thisParameter,
       this.parameters,
       this.returnContinuation,
       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
 /// [Type].
 class ReifyRuntimeType extends Primitive {
   /// Reference to the internal representation of a type (as produced, for
   /// example, by [ReadTypeVariable]).
   final Reference<Primitive> value;
 
   final SourceInformation sourceInformation;
 
   ReifyRuntimeType(Primitive value, this.sourceInformation)
     : this.value = new Reference<Primitive>(value);
 
   @override
   accept(Visitor visitor) => visitor.visitReifyRuntimeType(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    value.parent = this;
+  }
 }
 
 /// Read the value the type variable [variable] from the target object.
 ///
 /// The resulting value is an internal representation (and not neccessarily a
 /// Dart object), and must be reified by [ReifyRuntimeType], if it should be
 /// used as a Dart value.
 class ReadTypeVariable extends Primitive {
   final TypeVariableType variable;
   final Reference<Primitive> target;
   final SourceInformation sourceInformation;
 
   ReadTypeVariable(this.variable, Primitive target, this.sourceInformation)
       : this.target = new Reference<Primitive>(target);
 
   @override
   accept(Visitor visitor) => visitor.visitReadTypeVariable(this);
 
   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).
 ///
 /// The resulting value is constructed from [dartType] by replacing the type
 /// variables with consecutive values from [arguments], in the order generated
 /// by [DartType.forEachTypeVariable].  The type variables in [dartType] are
 /// treated as 'holes' in the term, which means that it must be ensured at
 /// construction, that duplicate occurences of a type variable in [dartType]
 /// are assigned the same value.
 class TypeExpression extends Primitive {
   final DartType dartType;
   final List<Reference<Primitive>> arguments;
 
   TypeExpression(this.dartType,
                  [List<Primitive> arguments = const <Primitive>[]])
       : this.arguments = _referenceList(arguments);
 
   @override
   accept(Visitor visitor) {
     return visitor.visitTypeExpression(this);
   }
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
+
+  void setParentPointers() {
+    _setParentsOnList(arguments, this);
+  }
 }
 
 class Await extends CallExpression {
   final Reference<Primitive> input;
   final Reference<Continuation> continuation;
 
   Await(Primitive input, Continuation continuation)
     : this.input = new Reference<Primitive>(input),
       this.continuation = new Reference<Continuation>(continuation);
 
   @override
   accept(Visitor visitor) {
     return visitor.visitAwait(this);
   }
+
+  void setParentPointers() {
+    input.parent = this;
+    continuation.parent = this;
+  }
 }
 
 class Yield extends CallExpression {
   final Reference<Primitive> input;
   final Reference<Continuation> continuation;
   final bool hasStar;
 
   Yield(Primitive input, this.hasStar, Continuation continuation)
     : this.input = new Reference<Primitive>(input),
       this.continuation = new Reference<Continuation>(continuation);
 
   @override
   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();
 
   T visit(Node node);
 
   // Concrete classes.
   T visitFunctionDefinition(FunctionDefinition node);
 
   // Expressions.
   T visitLetPrim(LetPrim node);
@@ skipping 41 matching lines @@
   T visitApplyBuiltinMethod(ApplyBuiltinMethod node);
   T visitGetLength(GetLength node);
   T visitGetIndex(GetIndex node);
   T visitSetIndex(SetIndex node);
   T visitRefinement(Refinement node);
 
   // Support for literal foreign code.
   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);
 
   processReference(Reference ref) {}
 
   processFunctionDefinition(FunctionDefinition node) {}
   visitFunctionDefinition(FunctionDefinition node) {
     processFunctionDefinition(node);
     if (node.thisParameter != null) visit(node.thisParameter);
     node.parameters.forEach(visit);
     visit(node.returnContinuation);
+    visit(node.body);
+  }
+
+  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) {}
   visitLetMutable(LetMutable node) {
     processLetMutable(node);
     visit(node.variable);
     processReference(node.value);
+    visit(node.body);
   }
 
   processInvokeStatic(InvokeStatic node) {}
   visitInvokeStatic(InvokeStatic node) {
     processInvokeStatic(node);
     processReference(node.continuation);
     node.arguments.forEach(processReference);
   }
 
   processInvokeContinuation(InvokeContinuation node) {}
@@ skipping 115 matching lines @@
   visitGetMutable(GetMutable node) {
     processGetMutable(node);
     processReference(node.variable);
   }
 
   processParameter(Parameter node) {}
   visitParameter(Parameter node) {
     processParameter(node);
   }
 
-  processContinuation(Continuation node) {}
-  visitContinuation(Continuation node) {
-    processContinuation(node);
-    node.parameters.forEach(visitParameter);
-  }
-
   processInterceptor(Interceptor node) {}
   visitInterceptor(Interceptor node) {
     processInterceptor(node);
     processReference(node.input);
   }
 
   processCreateInstance(CreateInstance node) {}
   visitCreateInstance(CreateInstance node) {
     processCreateInstance(node);
     node.arguments.forEach(processReference);
@@ skipping 140 matching lines @@
 /// The `traverse*` methods return the expression to visit next, and may
 /// push other subterms onto the stack using [push] or [pushAction] to visit
 /// them later. Actions pushed onto the stack will be executed after the body
 /// has been processed (and the stack actions it pushed have been executed).
 ///
 /// By default, the `traverse` methods visit all non-recursive subterms,
 /// push all bound continuations on the stack, and return the body of the term.
 ///
 /// 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) {
     _stack.add(callback);
   }
 
   void push(Continuation cont) {
     _stack.add(() {
       if (cont.isReturnContinuation) {
         traverseContinuation(cont);
@@ skipping 74 matching lines @@
         node = traverseLetPrim(node);
       } else {
         node = traverseLetMutable(node);
       }
     }
     visit(node);
   }
 }
 
 /// 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();
   }
 
   static void remove(Node node) {
     (new RemovalVisitor()).visit(node);
   }
 }