dart2js: Initial implementation of inlining.

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 'cps_fragment.dart' show CpsFragment;
 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;
 import '../types/types.dart' show TypeMask;
 import '../universe/selector.dart' show Selector;
 
 import 'builtin_operator.dart';
 export 'builtin_operator.dart';
 
@@ skipping 271 matching lines @@
     assert(this is! Parameter);
     assert(newDefinition is! Parameter);
     assert(newDefinition.parent == null);
     replaceUsesWith(newDefinition);
     destroy();
     LetPrim let = parent;
     let.primitive = newDefinition;
     newDefinition.parent = let;
     newDefinition.useElementAsHint(hint);
   }
+
+  /// Replaces this definition with a CPS fragment (a term with a hole in it),
+  /// given the value to replace the uses of the definition with.
+  ///
+  /// This can be thought of as substituting:
+  ///
+  ///     let x = OLD in BODY
+  ///       ==>
+  ///     FRAGMENT[BODY{newPrimitive/x}]
+  void replaceWithFragment(CpsFragment fragment, Primitive newPrimitive) {
+    assert(this is! Parameter);
+    replaceUsesWith(newPrimitive);
+    destroy();
+    LetPrim let = parent;
+    fragment.insertBelow(let);
+    let.remove();
+  }
 }
 
 /// A primitive that is generally not safe for elimination, but may be marked
 /// as safe by type propagation
 //
 // TODO(asgerf): Store the flag in a bitmask in [Primitive] and get rid of this
 //               class.
 abstract class UnsafePrimitive extends Primitive {
   bool isSafeForElimination = false;
   bool isSafeForReordering = false;
@@ skipping 149 matching lines @@
 
   accept(Visitor visitor) => visitor.visitLetMutable(this);
 
   void setParentPointers() {
     variable.parent = this;
     value.parent = this;
     if (body != null) body.parent = this;
   }
 }
 
+/// Base class of function invocations.
+///
+/// This class defines the common interface of function invocations.
+abstract class InvocationPrimitive extends UnsafePrimitive {
+  Reference<Primitive> get receiver => null;
+  List<Reference<Primitive>> get arguments;
+  SourceInformation get sourceInformation;
+}
+
 /// 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 UnsafePrimitive {
+class InvokeStatic extends InvocationPrimitive {
   final FunctionElement target;
   final Selector selector;
   final List<Reference<Primitive>> arguments;
   final SourceInformation sourceInformation;
 
   InvokeStatic(this.target,
                this.selector,
                List<Primitive> args,
                [this.sourceInformation])
       : arguments = _referenceList(args);
@@ skipping 36 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 UnsafePrimitive {
+class InvokeMethod extends InvocationPrimitive {
   Reference<Primitive> receiver;
   Selector selector;
   TypeMask mask;
   final List<Reference<Primitive>> arguments;
   final SourceInformation sourceInformation;
 
   CallingConvention callingConvention = CallingConvention.Normal;
 
   Reference<Primitive> get dartReceiverReference {
     return callingConvention == CallingConvention.Intercepted
@@ skipping 56 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 UnsafePrimitive {
+class InvokeMethodDirectly extends InvocationPrimitive {
   Reference<Primitive> receiver;
   final FunctionElement target;
   final Selector selector;
   final List<Reference<Primitive>> arguments;
   final SourceInformation sourceInformation;
 
   CallingConvention callingConvention = CallingConvention.Normal;
 
   Reference<Primitive> get dartReceiverReference {
     return callingConvention == CallingConvention.Intercepted
@@ skipping 37 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 UnsafePrimitive {
+class InvokeConstructor extends InvocationPrimitive {
   final DartType dartType;
   final ConstructorElement target;
   final List<Reference<Primitive>> arguments;
   final Selector selector;
   final SourceInformation sourceInformation;
 
   /// If non-null, this is an allocation site-specific type that is potentially
   /// better than the inferred return type of [target].
   ///
   /// In particular, container type masks depend on the allocation site and
@@ skipping 1189 matching lines @@
 
   // Concrete classes.
   T visitFunctionDefinition(FunctionDefinition node);
 
   // Expressions.
   T visitLetPrim(LetPrim node);
   T visitLetCont(LetCont node);
   T visitLetHandler(LetHandler node);
   T visitLetMutable(LetMutable node);
   T visitInvokeContinuation(InvokeContinuation node);
+  T visitThrow(Throw node);
+  T visitRethrow(Rethrow node);
+  T visitBranch(Branch node);
+  T visitUnreachable(Unreachable node);
+
+  // Definitions.
   T visitInvokeStatic(InvokeStatic node);
   T visitInvokeMethod(InvokeMethod node);
   T visitInvokeMethodDirectly(InvokeMethodDirectly node);
   T visitInvokeConstructor(InvokeConstructor node);
-  T visitThrow(Throw node);
-  T visitRethrow(Rethrow node);
-  T visitBranch(Branch node);
   T visitTypeCast(TypeCast node);
   T visitSetMutable(SetMutable node);
   T visitSetStatic(SetStatic node);
+  T visitSetField(SetField node);
   T visitGetLazyStatic(GetLazyStatic node);
-  T visitSetField(SetField node);
-  T visitUnreachable(Unreachable node);
   T visitAwait(Await node);
   T visitYield(Yield node);
-
-  // Definitions.
   T visitLiteralList(LiteralList node);
   T visitLiteralMap(LiteralMap node);
   T visitConstant(Constant node);
   T visitGetMutable(GetMutable node);
   T visitParameter(Parameter node);
   T visitContinuation(Continuation node);
   T visitMutableVariable(MutableVariable node);
   T visitGetStatic(GetStatic node);
   T visitInterceptor(Interceptor node);
   T visitCreateInstance(CreateInstance node);
@@ skipping 481 matching lines @@
 /// Visit a just-deleted subterm and unlink all [Reference]s in it.
 class RemovalVisitor extends TrampolineRecursiveVisitor {
   processReference(Reference reference) {
     reference.unlink();
   }
 
   static void remove(Node node) {
     (new RemovalVisitor()).visit(node);
   }
 }
+
+/// A visitor to copy instances of [Definition] or its subclasses, except for
+/// instances of [Continuation].
+///
+/// The visitor maintains a map from original definitions to their copies.
+/// When the [copy] method is called for a non-Continuation definition,
+/// a copy is created, added to the map and returned as the result. Copying a
+/// definition assumes that the definitions of all references have already
+/// been copied by the same visitor.
+class DefinitionCopyingVisitor extends Visitor<Definition> {
+  Map<Definition, Definition> _copies = <Definition, Definition>{};
+
+  /// Put a copy into the map.
+  ///
+  /// This method should be used instead of directly adding copies to the map.
+  Definition putCopy(Definition original, Definition copy) {
+    if (copy is Variable) {
+      copy.type = (original as Variable).type;

[sra1, 2015/12/18 02:16:26]

We usually use a typed local rather than 'as'.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

I know, but it looks horrible.  We shouldn't have to rename it, it already has a
name!

Fixed.

+      if (copy is Primitive) {

[asgerf, 2015/12/17 15:40:34]

MutableVariable also has a hint, so we could just add hint to the interface.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Done.

+        copy.hint = (original as Primitive).hint;
+      }
+    }
+    return _copies[original] = copy;
+  }
+
+  /// Get the copy of a [Reference]'s definition from the map.
+  Definition getCopy(Reference reference) => _copies[reference.definition];
+
+  /// Map a list of [Reference]s to the list of their definition's copies.
+  List<Definition> getList(List<Reference> list) => list.map(getCopy).toList();
+
+  /// Copy a non-[Continuation] [Definition].
+  Definition copy(Definition node) {
+    assert (node is! Continuation);
+    return putCopy(node, visit(node));
+  }
+
+  Definition visit(Node node) => node.accept(this);
+
+  Definition visitFunctionDefinition(FunctionDefinition node) {}
+  Definition visitLetPrim(LetPrim node) {}
+  Definition visitLetCont(LetCont node) {}
+  Definition visitLetHandler(LetHandler node) {}
+  Definition visitLetMutable(LetMutable node) {}
+  Definition visitInvokeContinuation(InvokeContinuation node) {}
+  Definition visitThrow(Throw node) {}
+  Definition visitRethrow(Rethrow node) {}
+  Definition visitBranch(Branch node) {}
+  Definition visitUnreachable(Unreachable node) {}
+  Definition visitContinuation(Continuation node) {}
+
+  Definition visitInvokeStatic(InvokeStatic node) {
+    return new InvokeStatic(node.target, node.selector, getList(node.arguments),
+        node.sourceInformation);
+  }
+
+  Definition visitInvokeMethod(InvokeMethod node) {
+    return new InvokeMethod(getCopy(node.receiver), node.selector, node.mask,
+        getList(node.arguments),
+        node.sourceInformation);
+  }
+
+  Definition visitInvokeMethodDirectly(InvokeMethodDirectly node) {
+    return new InvokeMethodDirectly(getCopy(node.receiver), node.target,
+        node.selector,
+        getList(node.arguments),
+        node.sourceInformation);
+  }
+
+  Definition visitInvokeConstructor(InvokeConstructor node) {
+    return new InvokeConstructor(node.dartType, node.target, node.selector,
+        getList(node.arguments),
+        node.sourceInformation);
+  }
+
+  Definition visitTypeCast(TypeCast node) {
+    return new TypeCast(getCopy(node.value), node.dartType,
+        getList(node.typeArguments));
+  }
+
+  Definition visitSetMutable(SetMutable node) {
+    return new SetMutable(getCopy(node.variable), getCopy(node.value));
+  }
+
+  Definition visitSetStatic(SetStatic node) {
+    return new SetStatic(node.element, getCopy(node.value),
+        node.sourceInformation);
+  }
+
+  Definition visitSetField(SetField node) {
+    return new SetField(getCopy(node.object), node.field, getCopy(node.value));
+  }
+
+  Definition visitGetLazyStatic(GetLazyStatic node) {
+    return new GetLazyStatic(node.element, node.sourceInformation);
+  }
+
+  Definition visitAwait(Await node) {
+    return new Await(getCopy(node.input));
+  }
+
+  Definition visitYield(Yield node) {
+    return new Yield(getCopy(node.input), node.hasStar);
+  }
+
+  Definition visitLiteralList(LiteralList node) {
+    return new LiteralList(node.dartType, getList(node.values));
+  }
+
+  Definition visitLiteralMap(LiteralMap node) {
+    List<LiteralMapEntry> entries = node.entries.map((LiteralMapEntry entry) {
+      return new LiteralMapEntry(getCopy(entry.key), getCopy(entry.value));
+    }).toList();
+    return new LiteralMap(node.dartType, entries);
+  }
+
+  Definition visitConstant(Constant node) {
+    return new Constant(node.value, sourceInformation: node.sourceInformation);
+  }
+
+  Definition visitGetMutable(GetMutable node) {
+    return new GetMutable(getCopy(node.variable));
+  }
+
+  Definition visitParameter(Parameter node) {
+    return new Parameter(node.hint);
+  }
+
+  Definition visitMutableVariable(MutableVariable node) {
+    return new MutableVariable(node.hint);
+  }
+
+  Definition visitGetStatic(GetStatic node) {
+    return new GetStatic(node.element, node.sourceInformation);
+  }
+
+  Definition visitInterceptor(Interceptor node) {
+    return new Interceptor(getCopy(node.input), node.sourceInformation)
+        ..interceptedClasses.addAll(node.interceptedClasses);
+  }
+
+  Definition visitCreateInstance(CreateInstance node) {
+    return new CreateInstance(node.classElement, getList(node.arguments),
+        getList(node.typeInformation),
+        node.sourceInformation);
+  }
+
+  Definition visitGetField(GetField node) {
+    return new GetField(getCopy(node.object), node.field);
+  }
+
+  Definition visitCreateBox(CreateBox node) {
+    return new CreateBox();
+  }
+
+  Definition visitReifyRuntimeType(ReifyRuntimeType node) {
+    return new ReifyRuntimeType(getCopy(node.value), node.sourceInformation);
+  }
+
+  Definition visitReadTypeVariable(ReadTypeVariable node) {
+    return new ReadTypeVariable(node.variable, getCopy(node.target),
+        node.sourceInformation);
+  }
+
+  Definition visitTypeExpression(TypeExpression node) {
+    return new TypeExpression(node.dartType, getList(node.arguments));
+  }
+
+  Definition visitCreateInvocationMirror(CreateInvocationMirror node) {
+    return new CreateInvocationMirror(node.selector, getList(node.arguments));
+  }
+
+  Definition visitTypeTest(TypeTest node) {
+    return new TypeTest(getCopy(node.value), node.dartType,
+        getList(node.typeArguments));
+  }
+
+  Definition visitTypeTestViaFlag(TypeTestViaFlag node) {
+    return new TypeTestViaFlag(getCopy(node.interceptor), node.dartType);
+  }
+
+  Definition visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
+    return new ApplyBuiltinOperator(node.operator, getList(node.arguments),
+        node.sourceInformation);
+  }
+
+  Definition visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
+    return new ApplyBuiltinMethod(node.method, getCopy(node.receiver),
+        getList(node.arguments),
+        node.sourceInformation,
+        receiverIsNotNull: node.receiverIsNotNull);
+  }
+
+  Definition visitGetLength(GetLength node) {
+    return new GetLength(getCopy(node.object));
+  }
+
+  Definition visitGetIndex(GetIndex node) {
+    return new GetIndex(getCopy(node.object), getCopy(node.index));
+  }
+
+  Definition visitSetIndex(SetIndex node) {
+    return new SetIndex(getCopy(node.object), getCopy(node.index),
+        getCopy(node.value));
+  }
+
+  Definition visitRefinement(Refinement node) {
+    return new Refinement(getCopy(node.value), node.refineType);
+  }
+
+  Definition visitBoundsCheck(BoundsCheck node) {
+    if (node.hasNoChecks) {
+      return new BoundsCheck.noCheck(getCopy(node.object),
+          node.sourceInformation);
+    } else {
+      return new BoundsCheck(getCopy(node.object), getCopy(node.index),
+          getCopy(node.length),
+          node.checks,
+          node.sourceInformation);
+    }
+  }
+
+  Definition visitNullCheck(NullCheck node) {
+    return new NullCheck(getCopy(node.value), node.sourceInformation);
+  }
+
+  Definition visitForeignCode(ForeignCode node) {
+    return new ForeignCode(node.codeTemplate, node.type,
+        getList(node.arguments),
+        node.nativeBehavior,
+        dependency: node.dependency);
+  }
+}
+
+/// A trampolining visitor to copy [FunctionDefinition]s.
+class CopyingVisitor extends TrampolineRecursiveVisitor {
+  // The visitor maintains a map from original continuations to their copies.
+  Map<Continuation, Continuation> _copies = <Continuation, Continuation>{};
+
+  // The visitor uses an auxiliary visitor to copy definitions.
+  DefinitionCopyingVisitor _definitions = new DefinitionCopyingVisitor();
+
+  // While copying a block, the state of the visitor is a 'linked list' of
+  // the expressions in the block's body, with a pointer to the last element
+  // of the list.
+  Expression _first = null;
+  Expression _current = null;
+
+  void plug(Expression body) {
+    if (_first == null) {
+      _first = body;
+    } else {
+      assert(_current != null);
+      (_current as InteriorExpression).body = body;
+    }
+    _current = body;
+  }
+
+  // Continuations are added to the visitor's stack to be visited after copying
+  // the current block is finished.  The stack action saves the current block,
+  // copies the continuation's body, sets the body on the copy of the
+  // continuation, and restores the current block.
+  //
+  // Note that continuations are added to the copy map before the stack action
+  // to visit them is performed.
+  void push(Continuation cont) {
+    assert(!cont.isReturnContinuation);
+    _stack.add(() {
+      Expression savedFirst = _first;
+      Expression savedPrevious = _current;

[asgerf, 2015/12/17 15:40:34]

Do we need to cache _current?

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Nope.  And that nicely dodges the issue of whether I call it 'current' or
'previous'.

+      _first = _current = null;
+      _processBlock(cont.body);
+      _copies[cont].body = _first;
+      _first = savedFirst;
+      _current = savedPrevious;
+    });
+  }
+
+  FunctionDefinition copy(FunctionDefinition node) {
+    assert(_first == null && _current == null);
+    _first = _current = null;
+    // Definitions are copied where they are bound, before processing
+    // expressions in the scope of their binding.
+    Parameter thisParameter = node.thisParameter == null
+        ? null
+        : _definitions.copy(node.thisParameter);
+    List<Parameter> parameters =
+        node.parameters.map(_definitions.copy).toList();
+    // Though the return continuation's parameter does not have any uses,
+    // we still make a proper copy to ensure that hints, type, etc. are
+    // copied.
+    Parameter returnParameter =
+        _definitions.copy(node.returnContinuation.parameters.first);
+    Continuation returnContinuation = _copies[node.returnContinuation] =
+        new Continuation([returnParameter]);
+
+    visit(node.body);
+    FunctionDefinition copy = new FunctionDefinition(node.element,
+        thisParameter,
+        parameters,
+        returnContinuation,
+        _first);
+    _first = _current = null;
+    return copy;
+  }
+
+  Node visit(Node node) => node.accept(this);
+
+  Expression traverseLetCont(LetCont node) {
+    // Continuations are copied where they are bound, before processing
+    // expressions in the scope of their binding.
+    List<Continuation> continuations = node.continuations.map((Continuation c) {
+      push(c);
+      return _copies[c] =
+          new Continuation(c.parameters.map(_definitions.copy).toList());
+    }).toList();
+    plug(new LetCont.many(continuations, null));
+    return node.body;
+  }
+
+  Expression traverseLetHandler(LetHandler node) {
+    // Continuations are copied where they are bound, before processing
+    // expressions in the scope of their binding.
+    push(node.handler);
+    Continuation handler = _copies[node.handler] =
+        new Continuation(node.handler.parameters.map(_definitions.copy)
+            .toList());
+    plug(new LetHandler(handler, null));
+    return node.body;
+  }
+
+  Expression traverseLetPrim(LetPrim node) {
+    plug(new LetPrim(_definitions.copy(node.primitive)));
+    return node.body;
+  }
+
+  Expression traverseLetMutable(LetMutable node) {
+    plug(new LetMutable(_definitions.copy(node.variable),
+        _definitions.getCopy(node.value)));
+    return node.body;
+  }
+
+  // Tail expressions do not have references, so we do not need to map them
+  // to their copies.
+  visitInvokeContinuation(InvokeContinuation node) {
+    plug(new InvokeContinuation(_copies[node.continuation.definition],
+        _definitions.getList(node.arguments),
+        isRecursive: node.isRecursive,
+        isEscapingTry: node.isEscapingTry,
+        sourceInformation: node.sourceInformation));
+  }
+
+  Node visitThrow(Throw node) {
+    plug(new Throw(_definitions.getCopy(node.value)));
+  }
+
+  Node visitRethrow(Rethrow node) {
+    plug(new Rethrow());
+  }
+
+  Node visitBranch(Branch node) {
+    plug(new Branch.loose(_definitions.getCopy(node.condition),
+        _copies[node.trueContinuation.definition],
+        _copies[node.falseContinuation.definition])
+      ..isStrictCheck = node.isStrictCheck);
+  }
+
+  Node visitUnreachable(Unreachable node) {
+    plug(new Unreachable());
+  }
+}