dart2js cps: Rewrite mutable variables to continuation parameters.

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 '../constants/values.dart' as values show ConstantValue;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
 import '../io/source_information.dart' show SourceInformation;
 import '../types/types.dart' show TypeMask;
@@ skipping 18 matching lines @@
 /// 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
 /// that can be obtained without side-effects, divergence, or throwing
 /// exceptions can be built using a [LetPrim].
+///
+/// All subclasses implement exactly one of [CallExpression],
+/// [InteriorExpression], or [TailExpression].
 abstract class Expression extends Node {
   InteriorNode get parent; // Only InteriorNodes may contain expressions.
 
   Expression plug(Expression expr) => throw 'impossible';
+
+  /// The next expression in the basic block.
+  /// 
+  /// For [InteriorExpression]s this is the body, for [CallExpressions] it is
+  /// the body of the continuation, and for [TailExpressions] it is `null`.
+  Expression get next;
+}
+
+/// Represents a node with a child node, which can be accessed through the
+/// `body` member. A typical usage is when removing a node from the CPS graph:
+///
+///     Node child          = node.body;
+///     InteriorNode parent = node.parent;
+///
+///     child.parent = parent;
+///     parent.body  = child;
+abstract class InteriorNode extends Node {
+  Expression get body;
+  void set body(Expression body);
+}
+
+/// An expression with a subexpression as body.
+abstract class InteriorExpression extends Expression implements InteriorNode {
+  Expression get next => body;
+}
+
+/// An expression that passes a continuation to a call.
+abstract class CallExpression extends Expression {
+  Reference<Continuation> get continuation;
+  Expression get next => continuation.definition.body;
+}
+
+/// An expression without a continuation or a subexpression body.
+///
+/// These break straight-line control flow and can be throught of as ending a
+/// basic block.
+abstract class TailExpression extends Expression {
+  Expression get next => null;
 }
 
 /// The base class of things that variables can refer to: primitives,
 /// continuations, function and continuation parameters, etc.
 abstract class Definition<T extends Definition<T>> extends Node {
   // The head of a linked-list of occurrences, in no particular order.
   Reference<T> firstRef;
 
   bool get hasAtMostOneUse  => firstRef == null || firstRef.next == null;
   bool get hasExactlyOneUse => firstRef != null && firstRef.next == null;
@@ skipping 87 matching lines @@
     definition.firstRef = this;
   }
 }
 
 /// Evaluates a primitive and binds it to variable: `let val x = V in E`.
 ///
 /// The bound value is in scope in the body.
 ///
 /// During one-pass construction a LetPrim with an empty body is used to
 /// represent the one-hole context `let val x = V in []`.
-class LetPrim extends Expression implements InteriorNode {
+class LetPrim extends InteriorExpression {
   Primitive primitive;
   Expression body;
 
   LetPrim(this.primitive, [this.body = null]);
 
   Expression plug(Expression expr) {
     assert(body == null);
     return body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitLetPrim(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.
 ///
 /// During one-pass construction a LetCont whose first continuation has an empty
 /// body is used to represent the one-hole context
 /// `let cont ... k(v) = [] ... in E`.
-class LetCont extends Expression implements InteriorNode {
+class LetCont extends InteriorExpression {
   List<Continuation> continuations;
   Expression body;
 
   LetCont(Continuation continuation, this.body)
       : continuations = <Continuation>[continuation];
 
   LetCont.two(Continuation first, Continuation second, this.body)
       : continuations = <Continuation>[first, second];
 
   LetCont.many(this.continuations, this.body);
@@ skipping 10 matching lines @@
 
 // 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 Expression implements InteriorNode {
+class LetHandler extends InteriorExpression {
   Continuation handler;
   Expression body;
 
   LetHandler(this.handler, this.body);
 
   accept(Visitor visitor) => visitor.visitLetHandler(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 Expression implements InteriorNode {
+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);
 }
 
-abstract class Invoke implements Expression {
-  Selector get selector;
-  List<Reference<Primitive>> get arguments;
-  Reference<Continuation> get continuation;
-}
-
-/// Represents a node with a child node, which can be accessed through the
-/// `body` member. A typical usage is when removing a node from the CPS graph:
-///
-///     Node child          = node.body;
-///     InteriorNode parent = node.parent;
-///
-///     child.parent = parent;
-///     parent.body  = child;
-abstract class InteriorNode extends Node {
-  Expression get body;
-  void set body(Expression body);
-}
-
 /// 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.
-class InvokeStatic extends Expression implements Invoke {
+class InvokeStatic extends CallExpression {
   final FunctionElement target;
   final Selector selector;
   final List<Reference<Primitive>> arguments;
   final Reference<Continuation> continuation;
   final SourceInformation sourceInformation;
 
   InvokeStatic(this.target,
                this.selector,
                List<Primitive> args,
                Continuation cont,
@@ skipping 12 matching lines @@
 
 /// 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
 /// arguments occur at the end of the [arguments] list, in normalized order.
-class InvokeMethod extends Expression implements Invoke {
+class InvokeMethod extends CallExpression {
   Reference<Primitive> receiver;
   Selector selector;
   TypeMask mask;
   final List<Reference<Primitive>> arguments;
   final Reference<Continuation> continuation;
   final SourceInformation sourceInformation;
 
   /// If true, it is known that the receiver cannot be `null`.
   bool receiverIsNotNull = false;
 
@@ skipping 29 matching lines @@
 /// If it is known that [target] does not use its receiver argument, then
 /// [receiver] may refer to a null constant primitive. This happens for direct
 /// invocations to intercepted methods, where the effective receiver is instead
 /// passed as a formal parameter.
 ///
 /// TODO(sra): Review. A direct call to a method that is mixed into a native
 /// class will still require an explicit argument.
 ///
 /// All optional arguments declared by [target] are passed in explicitly, and
 /// occur at the end of [arguments] list, in normalized order.
-class InvokeMethodDirectly extends Expression implements Invoke {
+class InvokeMethodDirectly extends CallExpression {
   Reference<Primitive> receiver;
   final FunctionElement target;
   final Selector selector;
   final List<Reference<Primitive>> arguments;
   final Reference<Continuation> continuation;
   final SourceInformation sourceInformation;
 
   InvokeMethodDirectly(Primitive receiver,
                        this.target,
                        this.selector,
@@ skipping 15 matching lines @@
 /// All optional arguments declared by [target] are passed in explicitly, and
 /// occur in the [arguments] list, in normalized order.
 ///
 /// Last in the [arguments] list, after the mandatory and optional arguments,
 /// the internal representation of each type argument occurs, unless it could
 /// be determined at build-time that the constructed class has no need for its
 /// runtime type information.
 ///
 /// Note that [InvokeConstructor] does it itself allocate an object.
 /// The invoked constructor will do that using [CreateInstance].
-class InvokeConstructor extends Expression implements Invoke {
+class InvokeConstructor extends CallExpression {
   final DartType type;
   final ConstructorElement target;
   final List<Reference<Primitive>> arguments;
   final Reference<Continuation> continuation;
   final Selector selector;
   final SourceInformation sourceInformation;
 
   InvokeConstructor(this.type,
                     this.target,
                     this.selector,
@@ skipping 45 matching lines @@
 /// 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 Expression {
+class TypeCast extends CallExpression {
   Reference<Primitive> value;
   final DartType type;
 
   /// See the corresponding field on [TypeTest].
   final List<Reference<Primitive>> typeArguments;
   final Reference<Continuation> continuation;
 
   TypeCast(Primitive value,
            this.type,
            List<Primitive> typeArguments,
@@ skipping 18 matching lines @@
   accept(Visitor visitor) => visitor.visitApplyBuiltinOperator(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
 }
 
 /// 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 Expression {
+class Throw extends TailExpression {
   Reference<Primitive> value;
 
   Throw(Primitive value) : value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitThrow(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 Expression {
+class Rethrow extends TailExpression {
   accept(Visitor visitor) => visitor.visitRethrow(this);
 }
 
 /// A throw occurring in non-tail position.
 ///
 /// The CPS translation of an expression produces a primitive as the value
 /// of the expression.  For convenience in the implementation of the
 /// translation, a [NonTailThrow] is used as that value.  A cleanup pass
 /// removes these and replaces them with [Throw] expressions.
 class NonTailThrow extends Primitive {
   final Reference<Primitive> value;
 
   NonTailThrow(Primitive value) : value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitNonTailThrow(this);
 
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
 }
 
 /// 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 Expression {
+class Unreachable extends TailExpression {
   accept(Visitor visitor) => visitor.visitUnreachable(this);
 }
 
 /// Gets the value from a [MutableVariable].
 ///
 /// [MutableVariable]s can be seen as ref cells that are not first-class
 /// values.  A [LetPrim] with a [GetMutableVariable] can then be seen as:
 ///
 ///   let prim p = ![variable] in [body]
 ///
 class GetMutableVariable extends Primitive {
   final Reference<MutableVariable> variable;
 
   GetMutableVariable(MutableVariable variable)
       : this.variable = new Reference<MutableVariable>(variable);
 
   accept(Visitor visitor) => visitor.visitGetMutableVariable(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => false;
 }
 
 /// 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 SetMutableVariable extends Expression implements InteriorNode {
+class SetMutableVariable extends InteriorExpression {
   final Reference<MutableVariable> variable;
   final Reference<Primitive> value;
   Expression body;
 
   SetMutableVariable(MutableVariable variable, Primitive value)
       : this.variable = new Reference<MutableVariable>(variable),
         this.value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitSetMutableVariable(this);
 
   Expression plug(Expression expr) {
     assert(body == null);
     return body = expr;
   }
 }
 
 /// Invoke a continuation in tail position.
-class InvokeContinuation extends Expression {
+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.
   bool isRecursive;
 
   /// True if this invocation escapes from the body of a [LetHandler]
   /// (i.e. a try block). Notably, such an invocation cannot be inlined.
@@ skipping 31 matching lines @@
   final Reference<Primitive> value;
 
   IsTrue(Primitive val) : value = new Reference<Primitive>(val);
 
   accept(Visitor visitor) => visitor.visitIsTrue(this);
 }
 
 /// Choose between a pair of continuations based on a condition value.
 ///
 /// The two continuations must not declare any parameters.
-class Branch extends Expression {
+class Branch extends TailExpression {
   final Condition condition;
   final Reference<Continuation> trueContinuation;
   final Reference<Continuation> falseContinuation;
 
   Branch(this.condition, Continuation trueCont, Continuation falseCont)
       : trueContinuation = new Reference<Continuation>(trueCont),
         falseContinuation = new Reference<Continuation>(falseCont);
 
   accept(Visitor visitor) => visitor.visitBranch(this);
 }
 
 /// Directly assigns to a field on a given object.
-class SetField extends Expression implements InteriorNode {
+class SetField extends InteriorExpression {
   final Reference<Primitive> object;
   FieldElement field;
   final Reference<Primitive> value;
   Expression body;
 
   SetField(Primitive object, this.field, Primitive value)
       : this.object = new Reference<Primitive>(object),
         this.value = new Reference<Primitive>(value);
 
   Expression plug(Expression expr) {
@@ skipping 95 matching lines @@
 
   bool get isSafeForElimination {
     return true;
   }
   bool get isSafeForReordering {
     return element is FunctionElement || element.isFinal;
   }
 }
 
 /// Sets the value of a static field.
-class SetStatic extends Expression implements InteriorNode {
+class SetStatic extends InteriorExpression {
   final FieldElement element;
   final Reference<Primitive> value;
   Expression body;
   final SourceInformation sourceInformation;
 
   SetStatic(this.element, Primitive value, [this.sourceInformation])
       : this.value = new Reference<Primitive>(value);
 
   Expression plug(Expression expr) {
     assert(body == null);
     return body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitSetStatic(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 Expression {
+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);
@@ skipping 55 matching lines @@
 
   CreateInvocationMirror(this.selector, List<Primitive> arguments)
       : this.arguments = _referenceList(arguments);
 
   accept(Visitor visitor) => visitor.visitCreateInvocationMirror(this);
 
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
 }
 
-class ForeignCode extends Expression {
+class ForeignCode extends CallExpression {
   final js.Template codeTemplate;
   final TypeMask type;
   final List<Reference<Primitive>> arguments;
   final native.NativeBehavior nativeBehavior;
   final FunctionElement dependency;
-
-  /// The continuation, if the foreign code is not a JavaScript 'throw',
-  /// otherwise null.
   final Reference<Continuation> continuation;
 
   ForeignCode(this.codeTemplate, this.type, List<Primitive> arguments,
-      this.nativeBehavior, {Continuation continuation, this.dependency})
-      : arguments = _referenceList(arguments),
-        continuation = continuation == null ? null
-            : new Reference<Continuation>(continuation);
+      this.nativeBehavior, Continuation continuation, {this.dependency})
+      : this.arguments = _referenceList(arguments),
+        this.continuation = new Reference<Continuation>(continuation);
 
   accept(Visitor visitor) => visitor.visitForeignCode(this);
 }
 
 class Constant extends Primitive {
   final values.ConstantValue value;
   final SourceInformation sourceInformation;
 
   Constant(this.value, {this.sourceInformation});
 
@@ skipping 101 matching lines @@
     : parameters = <Parameter>[new Parameter(null)],
       isRecursive = false;
 
   accept(Visitor visitor) => visitor.visitContinuation(this);
 }
 
 /// Identifies a mutable variable.
 class MutableVariable extends Definition {
   Entity hint;
 
-  MutableVariable(this.hint);
+MutableVariable(this.hint);
 
   accept(Visitor v) => v.visitMutableVariable(this);
 }
 
 /// 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;
@@ skipping 449 matching lines @@
   const RemovalVisitor();
 
   processReference(Reference reference) {
     reference.unlink();
   }
 
   static void remove(Node node) {
     (const RemovalVisitor()).visit(node);
   }
 }