Use closure conversion in new dart2js backend.

pkg/compiler/lib/src/cps_ir/cps_ir_builder.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_builder;
 
 import '../constants/expressions.dart';
 import '../constants/values.dart' show PrimitiveConstantValue;
 import '../dart_types.dart';
 import '../dart2jslib.dart';
 import '../elements/elements.dart';
 import '../source_file.dart';
 import '../tree/tree.dart' as ast;
 import '../scanner/scannerlib.dart' show Token, isUserDefinableOperator;
 import '../universe/universe.dart' show SelectorKind;
 import 'cps_ir_nodes.dart' as ir;
 import '../elements/modelx.dart' show SynthesizedConstructorElementX;
+import '../closure.dart';
+import '../closure.dart' as closurelib;
+import '../js_backend/js_backend.dart' show JavaScriptBackend;
 
 part 'cps_ir_builder_visitor.dart';
 
 /// A mapping from variable elements to their compile-time values.
 ///
 /// Map elements denoted by parameters and local variables to the
 /// [ir.Primitive] that is their value.  Parameters and locals are
 /// assigned indexes which can be used to refer to them.
 class Environment {
   /// A map from elements to their environment index.
-  final Map<Element, int> variable2index;
+  final Map<Local, int> variable2index;
 
   /// A reverse map from environment indexes to the variable.
-  final List<Element> index2variable;
+  final List<Local> index2variable;
 
   /// A map from environment indexes to their value.
   final List<ir.Primitive> index2value;
 
   Environment.empty()
-      : variable2index = <Element, int>{},
-        index2variable = <Element>[],
+      : variable2index = <Local, int>{},
+        index2variable = <Local>[],
         index2value = <ir.Primitive>[];
 
   /// Construct an environment that is a copy of another one.
   ///
   /// The mapping from elements to indexes is shared, not copied.
   Environment.from(Environment other)
       : variable2index = other.variable2index,
-        index2variable = new List<Element>.from(other.index2variable),
+        index2variable = new List<Local>.from(other.index2variable),
         index2value = new List<ir.Primitive>.from(other.index2value);
 
   get length => index2variable.length;
 
   ir.Primitive operator [](int index) => index2value[index];
 
-  void extend(Element element, ir.Primitive value) {
+  void extend(Local element, ir.Primitive value) {
     // Assert that the name is not already in the environment.  `null` is used
     // as the name of anonymous variables.  Because the variable2index map is
     // shared, `null` can already occur.  This is safe because such variables
     // are not looked up by name.
     //
     // TODO(kmillikin): This is still kind of fishy.  Refactor to not share
     // name maps or else garbage collect unneeded names.
     assert(element == null || !variable2index.containsKey(element));
     variable2index[element] = index2variable.length;
     index2variable.add(element);
     index2value.add(value);
   }
 
-  ir.Primitive lookup(Element element) {
-    assert(!element.isConst);
+  ir.Primitive lookup(Local element) {
     assert(invariant(element, variable2index.containsKey(element),
                      message: "Unknown variable: $element."));
     return index2value[variable2index[element]];
   }
 
-  void update(Element element, ir.Primitive value) {
+  void update(Local element, ir.Primitive value) {
     index2value[variable2index[element]] = value;
   }
 
   /// Verify that the variable2index and index2variable maps agree up to the
   /// index [length] exclusive.
   bool sameDomain(int length, Environment other) {
     assert(this.length >= length);
     assert(other.length >= length);
     for (int i = 0; i < length; ++i) {
       // An index maps to the same variable in both environments.
-      Element variable = index2variable[i];
+      Local variable = index2variable[i];
       if (variable != other.index2variable[i]) return false;
 
       // The variable maps to the same index in both environments.
       int index = variable2index[variable];
       if (index == null || index != other.variable2index[variable]) {
         return false;
       }
     }
     return true;
   }
@@ skipping 75 matching lines @@
   // TODO(johnniwinther): Type [nodes] as `Iterable<N>` when `NodeList` uses
   // `List` instead of `Link`.
   SubbuildFunction subbuildSequence(/*Iterable<N>*/ nodes) {
     return (IrBuilder builder) {
       return withBuilder(builder, () => builder.buildSequence(nodes, build));
     };
   }
 }
 
 /// Shared state between IrBuilders of nested functions.
 class IrBuilderClosureState {

[floitsch, 2015/01/08 18:29:35]

Probably different CL, but I'm not sure the names are really good:
the state that is active for all nested functions is the "ClosureState", but the
state that is active for just my local function (aka "closure") is called
"SharedState".

[asgerf, 2015/01/12 13:15:42]

I completely agree, but I can't seem to think of better names.
SharedClosureState and SharedLocalState? It still seems to imply that
ClosureState is bound to one closure as opposed to shared across closure
boundaries.

-  final Iterable<Entity> closureLocals;
-
   /// Maps local variables to their corresponding [ClosureVariable] object.
   final Map<Local, ir.ClosureVariable> local2closure =
       <Local, ir.ClosureVariable>{};
 
   /// Maps functions to the list of closure variables declared in that function.
   final Map<ExecutableElement, List<ir.ClosureVariable>> function2closures =
       <ExecutableElement, List<ir.ClosureVariable>>{};
 
   /// Returns the closure variables declared in the given function.
   List<ir.ClosureVariable> getClosureList(ExecutableElement element) {
     return function2closures.putIfAbsent(element, () => <ir.ClosureVariable>[]);
   }
 
-  IrBuilderClosureState(this.closureLocals) {
-    for (Local local in closureLocals) {
-      ExecutableElement context = local.executableContext;
-      ir.ClosureVariable variable = new ir.ClosureVariable(context, local);
-      local2closure[local] = variable;
-      getClosureList(context).add(variable);
-    }
+  /// Creates a closure variable for the given local.
+  void makeClosureVariable(Local local) {
+    ir.ClosureVariable variable =
+        new ir.ClosureVariable(local.executableContext, local);
+    local2closure[local] = variable;
+    getClosureList(local.executableContext).add(variable);
   }
 }
 
 /// Shared state between delimited IrBuilders within the same function.
 class IrBuilderSharedState {
   final ConstantSystem constantSystem;
 
   /// A stack of collectors for breaks.
   final List<JumpCollector> breakCollectors = <JumpCollector>[];
 
   /// A stack of collectors for continues.
   final List<JumpCollector> continueCollectors = <JumpCollector>[];
 
   final List<ConstDeclaration> localConstants = <ConstDeclaration>[];
 
   final ExecutableElement currentElement;
 
   final ir.Continuation returnContinuation = new ir.Continuation.retrn();
 
   final List<ir.Definition> functionParameters = <ir.Definition>[];
 
+  /// Maps boxed locals to their location. These locals are not part of
+  /// the environment.
+  final Map<Local, ClosureLocation> boxedVariables = {};
+
+  /// If non-null, this refers to the receiver in the enclosing method.

[floitsch, 2015/01/08 18:29:35]

to the receiver (`this`) in ...

[asgerf, 2015/01/12 13:15:42]

Done.

+  ir.Primitive receiver;
+
   IrBuilderSharedState(this.constantSystem, this.currentElement);
 }
 
 /// A factory for building the cps IR.
-class IrBuilder {
+///
+/// [DartIrBuilder] and [JsIrBuilder] implement nested functions and captured
+/// variables in different ways.
+abstract class IrBuilder {
+  IrBuilder _makeInstance();
+
+  void declareLocalVariable(LocalVariableElement element, {ir.Primitive initialValue});

[floitsch, 2015/01/08 18:29:36]

long line.

+  void declareLocalFunction(LocalFunctionElement element, Object function);
+  ir.Primitive buildFunctionExpression(Object function);
+  ir.Primitive buildLocalGet(LocalElement element);
+  ir.Primitive buildLocalSet(LocalElement element, ir.Primitive value);
+
+  void _enterClosureEnvironment(ClosureEnvironment env);

[floitsch, 2015/01/08 18:29:36]

comments!

+  void _enterScope(ClosureScope scope);
+  void _createFunctionParameter(ParameterElement parameterElement);
+  void _migrateLoopVariables(ClosureScope scope);
+
   // TODO(johnniwinther): Make these field final and remove the default values
   // when [IrBuilder] is a property of [IrBuilderVisitor] instead of a mixin.
 
   final List<ir.Parameter> _parameters = <ir.Parameter>[];
 
-  final IrBuilderSharedState state;
+  IrBuilderSharedState state;
 
-  final IrBuilderClosureState closure;
+  IrBuilderClosureState closure;

[floitsch, 2015/01/08 18:29:36]

Again, probably different CL:
closureState, or even sharedState (if we rename the classes).

 
   /// A map from variable indexes to their values.
+  /// [BoxLocal]s map to their box. [LocalElement]s that are boxed are not

[floitsch, 2015/01/08 18:29:35]

New line before. (Otherwise markdown merges them).

+  /// in the map; look up their [BoxLocal] instead.
   Environment environment;
 
   // The IR builder maintains a context, which is an expression with a hole in
   // it.  The hole represents the focus where new expressions can be added.
   // The context is implemented by 'root' which is the root of the expression
   // and 'current' which is the expression that immediately contains the hole.
   // Not all expressions have a hole (e.g., invocations, which always occur in
   // tail position, do not have a hole).  Expressions with a hole have a plug
   // method.
   //
   // Conceptually, visiting a statement takes a context as input and returns
   // either a new context or else an expression without a hole if all
   // control-flow paths through the statement have exited.  An expression
   // without a hole is represented by a (root, current) pair where root is the
   // expression and current is null.
   //
   // Conceptually again, visiting an expression takes a context as input and
   // returns either a pair of a new context and a definition denoting
   // the expression's value, or else an expression without a hole if all
   // control-flow paths through the expression have exited.
   //
   // We do not pass contexts as arguments or return them.  Rather we use the
   // current context (root, current) as the visitor state and mutate current.
   // Visiting a statement returns null; visiting an expression returns the
   // primitive denoting its value.
 
   ir.Expression _root = null;
   ir.Expression _current = null;
 
-  IrBuilder(ConstantSystem constantSystem,
-            ExecutableElement currentElement,
-            Iterable<Entity> closureLocals)
-      : this.state = new IrBuilderSharedState(constantSystem, currentElement),
-        this.closure = new IrBuilderClosureState(closureLocals),
-        this.environment = new Environment.empty();
+  void _init(ConstantSystem constantSystem, ExecutableElement currentElement) {

[floitsch, 2015/01/08 18:29:36]

add comment.

Could you keep this a constructor?
Both subclasses call it first thing in the constructor.

[asgerf, 2015/01/12 13:15:42]

Added comment.

The subclasses have two constructors, because the makeInstance() should not do
this initialization. Duplicating the code for makeDelimitedBuilder,
makeRecursiveBuilder and for _init seems a bit much.

+    state = new IrBuilderSharedState(constantSystem, currentElement);
+    closure = new IrBuilderClosureState();
+    environment = new Environment.empty();
+  }
 
   /// Construct a delimited visitor for visiting a subtree.
   ///
   /// The delimited visitor has its own compile-time environment mapping
   /// local variables to their values, which is initially a copy of the parent
   /// environment.  It has its own context for building an IR expression, so
   /// the built expression is not plugged into the parent's context.
-  IrBuilder.delimited(IrBuilder parent)
-      : this.state = parent.state,
-        this.closure = parent.closure,
-        this.environment = new Environment.from(parent.environment);
+  IrBuilder makeDelimitedBuilder() {
+    return _makeInstance()
+            ..state = state

[floitsch, 2015/01/08 18:29:36]

nit: indentation. (by 4).

+            ..closure = closure
+            ..environment = new Environment.from(environment);
+  }
 
   /// Construct a visitor for a recursive continuation.
   ///
   /// The recursive continuation builder has fresh parameters (i.e. SSA phis)

[floitsch, 2015/01/08 18:29:35]

"i.e." doesn't seem right. It's more of a "like" no?

[asgerf, 2015/01/12 13:15:42]

Parameters are like SSA phis, but using "like" here I think could easily be
misinterpreted as "for example".

   /// for all the local variables in the parent, because the invocation sites
   /// of the continuation are not all known when the builder is created.  The
   /// recursive invocations will be passed values for all the local variables,
   /// which may be eliminated later if they are redundant---if they take on
   /// the same value at all invocation sites.
-  IrBuilder.recursive(IrBuilder parent)
-      : this.state = parent.state,
-        this.closure = parent.closure,
-        this.environment = new Environment.empty() {
-    parent.environment.index2variable.forEach(createLocalParameter);
+  IrBuilder makeRecursiveBuilder() {
+    IrBuilder inner = _makeInstance()
+        ..state = state
+        ..closure = closure
+        ..environment = new Environment.empty();
+    environment.index2variable.forEach(inner.createLocalParameter);
+    return inner;
   }
 
   /// Construct a builder for an inner function.
-  IrBuilder.innerFunction(IrBuilder parent,
-                          ExecutableElement currentElement)
-      : this.state = new IrBuilderSharedState(parent.state.constantSystem,
-                                              currentElement),
-        this.closure = parent.closure,
-        this.environment = new Environment.empty();
-
+  IrBuilder makeInnerFunctionBuilder(ExecutableElement currentElement) {
+    return _makeInstance()
+        ..state = new IrBuilderSharedState(state.constantSystem, currentElement)
+        ..closure = closure
+        ..environment = new Environment.empty();
+  }
 
   bool get isOpen => _root == null || _current != null;
 
-  /// True if [element] is a local variable, local function, or parameter that
-  /// is accessed from an inner function. Recursive self-references in a local
-  /// function count as closure accesses.
-  ///
-  /// If `true`, [element] is a [LocalElement].
-  bool isClosureVariable(Element element) {
-    return closure.closureLocals.contains(element);
+  void beginField({ ClosureScope closureScope }) {

[floitsch, 2015/01/08 18:29:36]

nit: apparently we don't put spaces after "{" and before "}". (same for other
functions.

[floitsch, 2015/01/08 18:29:36]

comment.
Is this the rhs of a field-init?

[asgerf, 2015/01/12 13:15:43]

Done.

+    beginFunction([], closureScope: closureScope);
   }
 
-  /// Returns the [ClosureVariable] corresponding to the given variable.
-  /// Returns `null` for non-closure variables.
-  ir.ClosureVariable getClosureVariable(LocalElement element) {
-    return closure.local2closure[element];
+  void beginFunction(Iterable<ParameterElement> parameters,

[floitsch, 2015/01/08 18:29:36]

Apparently this method is not just used for functions (see call from
beginField).

I think it would be safer to factor out the shared part (altough I'm missing a
good name right now).

[asgerf, 2015/01/12 13:15:43]

Fixed.

The only shared part was _enterScope, so I just copied that into beginField.
With the null check now inside _enterScope, there is no real code duplication
anyway.

+                     { ClosureScope closureScope,
+                       ClosureEnvironment closureEnvironment } ) {
+    if (closureEnvironment != null) {
+      _enterClosureEnvironment(closureEnvironment);

[floitsch, 2015/01/08 18:29:35]

unconditionally _enterClosureEnvironment(...) and test in there if the argument
is `null`.

rename to _buildClosureEnvironmentSetup(...); ?

[asgerf, 2015/01/12 13:15:43]

Done.

+    }
+    if (closureScope != null) {
+      _enterScope(closureScope);

[floitsch, 2015/01/08 18:29:35]

ditto.

[asgerf, 2015/01/12 13:15:42]

Done.

+    }
+    parameters.forEach(_createFunctionParameter);
   }
 
-  /// Adds the given parameter to the function currently being built.
-  void createFunctionParameter(ParameterElement parameterElement) {
-    if (isClosureVariable(parameterElement)) {
-      state.functionParameters.add(getClosureVariable(parameterElement));
-    } else {
-      state.functionParameters.add(createLocalParameter(parameterElement));
-    }
-  }
-
-  /// Create a parameter for [parameterElement] and add it to the current
-  /// environment.
-  ir.Parameter createLocalParameter(LocalElement parameterElement) {
-    ir.Parameter parameter = new ir.Parameter(parameterElement);
+  /// Create a parameter for [local] and add it to the current environment.

[floitsch, 2015/01/08 18:29:36]

Creates ... adds ...

[asgerf, 2015/01/12 13:15:43]

Done.

+  ir.Parameter createLocalParameter(Local local) {
+    ir.Parameter parameter = new ir.Parameter(local);
     _parameters.add(parameter);
-    environment.extend(parameterElement, parameter);
+    environment.extend(local, parameter);
     return parameter;
   }
 
   /// Add the constant [variableElement] to the environment with [value] as its

[floitsch, 2015/01/08 18:29:35]

Adds

[asgerf, 2015/01/12 13:15:42]

Done.

   /// constant value.
   void declareLocalConstant(LocalVariableElement variableElement,
                             ConstantExpression value) {
     state.localConstants.add(new ConstDeclaration(variableElement, value));
   }
 
-  /// Add [variableElement] to the environment with [initialValue] as its
-  /// initial value.
-  void declareLocalVariable(LocalVariableElement variableElement,
-                            {ir.Primitive initialValue}) {
-    assert(isOpen);
-    if (initialValue == null) {
-      // TODO(kmillikin): Consider pooling constants.
-      // The initial value is null.
-      initialValue = buildNullLiteral();
-    }
-    if (isClosureVariable(variableElement)) {
-      add(new ir.SetClosureVariable(getClosureVariable(variableElement),
-                                    initialValue,
-                                    isDeclaration: true));
-    } else {
-      // In case a primitive was introduced for the initializer expression,
-      // use this variable element to help derive a good name for it.
-      initialValue.useElementAsHint(variableElement);
-      environment.extend(variableElement, initialValue);
-    }
-  }
-
-  /// Add [functionElement] to the environment with provided [definition].
-  void declareLocalFunction(LocalFunctionElement functionElement,
-                            ir.FunctionDefinition definition) {
-    assert(isOpen);
-    if (isClosureVariable(functionElement)) {
-      ir.ClosureVariable variable = getClosureVariable(functionElement);
-      add(new ir.DeclareFunction(variable, definition));
-    } else {
-      ir.CreateFunction prim = new ir.CreateFunction(definition);
-      add(new ir.LetPrim(prim));
-      environment.extend(functionElement, prim);
-      prim.useElementAsHint(functionElement);
-    }
-  }
-
   // Plug an expression into the 'hole' in the context being accumulated.  The
   // empty context (just a hole) is represented by root (and current) being
   // null.  Since the hole in the current context is filled by this function,
   // the new hole must be in the newly added expression---which becomes the
   // new value of current.
   void add(ir.Expression expr) {
     assert(isOpen);
     if (_root == null) {
       _root = _current = expr;
     } else {
@@ skipping 115 matching lines @@
   /// then and else expression are created through the [buildThenExpression] and
   /// [buildElseExpression] functions, respectively.
   ir.Primitive buildConditional(
       ir.Primitive condition,
       ir.Primitive buildThenExpression(IrBuilder builder),
       ir.Primitive buildElseExpression(IrBuilder builder)) {
 
     assert(isOpen);
 
     // The then and else expressions are delimited.
-    IrBuilder thenBuilder = new IrBuilder.delimited(this);
-    IrBuilder elseBuilder = new IrBuilder.delimited(this);
+    IrBuilder thenBuilder = makeDelimitedBuilder();
+    IrBuilder elseBuilder = makeDelimitedBuilder();
     ir.Primitive thenValue = buildThenExpression(thenBuilder);
     ir.Primitive elseValue = buildElseExpression(elseBuilder);
 
     // Treat the values of the subexpressions as named values in the
     // environment, so they will be treated as arguments to the join-point
     // continuation.
     assert(environment.length == thenBuilder.environment.length);
     assert(environment.length == elseBuilder.environment.length);
     thenBuilder.environment.extend(null, thenValue);
     elseBuilder.environment.extend(null, elseValue);
@@ skipping 17 matching lines @@
                 new ir.LetCont(elseContinuation,
                     new ir.Branch(new ir.IsTrue(condition),
                                   thenContinuation,
                                   elseContinuation)))));
     return (thenValue == elseValue)
         ? thenValue
         : joinContinuation.parameters.last;
 
   }
 
-  /// Create a function expression from [definition].
-  ir.Primitive buildFunctionExpression(ir.FunctionDefinition definition) {
-    ir.CreateFunction prim = new ir.CreateFunction(definition);
-    add(new ir.LetPrim(prim));
-    return prim;
-  }
-
   /**
    * Add an explicit `return null` for functions that don't have a return
    * statement on each branch. This includes functions with an empty body,
    * such as `foo(){ }`.
    */
   void _ensureReturn() {
     if (!isOpen) return;
     ir.Constant constant = buildNullLiteral();
     add(new ir.InvokeContinuation(state.returnContinuation, [constant]));
     _current = null;
@@ skipping 178 matching lines @@
         (k) => new ir.InvokeConstructor(type, element, selector, k, arguments));
   }
 
   /// Create a string concatenation of the [arguments].
   ir.Primitive buildStringConcatenation(List<ir.Primitive> arguments) {
     assert(isOpen);
     return _continueWithExpression(
         (k) => new ir.ConcatenateStrings(k, arguments));
   }
 
-  /// Create a read access of [local].
-  ir.Primitive buildLocalGet(LocalElement local) {
-    assert(isOpen);
-    if (isClosureVariable(local)) {
-      ir.Primitive result =
-          new ir.GetClosureVariable(getClosureVariable(local));
-      add(new ir.LetPrim(result));
-      return result;
-    } else {
-      return environment.lookup(local);
-    }
-  }
-
-  /// Create a write access to [local] with the provided [value].
-  ir.Primitive buildLocalSet(LocalElement local, ir.Primitive value) {
-    assert(isOpen);
-    if (isClosureVariable(local)) {
-      add(new ir.SetClosureVariable(getClosureVariable(local), value));
-    } else {
-      value.useElementAsHint(local);
-      environment.update(local, value);
-    }
-    return value;
-  }
-
   /// Create an invocation of [local] where the argument structure is defined
   /// by [selector] and the argument values are defined by [arguments].
   ir.Primitive buildLocalInvocation(LocalElement local,
                                     Selector selector,
                                     List<ir.Definition> arguments) {
-    ir.Primitive receiver;
-    if (isClosureVariable(local)) {
-      receiver = new ir.GetClosureVariable(getClosureVariable(local));
-      add(new ir.LetPrim(receiver));
-    } else {
-      receiver = environment.lookup(local);
-    }
-    return _buildInvokeCall(receiver, selector, arguments);
+    return _buildInvokeCall(buildLocalGet(local), selector, arguments);
   }
 
   /// Create an invocation of the [functionExpression] where the argument
   /// structure are defined by [selector] and the argument values are defined by
   /// [arguments].
   ir.Primitive buildFunctionExpressionInvocation(
       ir.Primitive functionExpression,
       Selector selector,
       List<ir.Definition> arguments) {
     return _buildInvokeCall(functionExpression, selector, arguments);
   }
 
   /// Creates an if-then-else statement with the provided [condition] where the
   /// then and else branches are created through the [buildThenPart] and
   /// [buildElsePart] functions, respectively.
   ///
   /// An if-then statement is created if [buildElsePart] is a no-op.
   // TODO(johnniwinther): Unify implementation with [buildConditional] and
   // [_buildLogicalOperator].
   void buildIf(ir.Primitive condition,
                void buildThenPart(IrBuilder builder),
                void buildElsePart(IrBuilder builder)) {
     assert(isOpen);
 
     // The then and else parts are delimited.
-    IrBuilder thenBuilder = new IrBuilder.delimited(this);
-    IrBuilder elseBuilder = new IrBuilder.delimited(this);
+    IrBuilder thenBuilder = makeDelimitedBuilder();
+    IrBuilder elseBuilder = makeDelimitedBuilder();
     buildThenPart(thenBuilder);
     buildElsePart(elseBuilder);
 
     // Build the term
     // (Result =) let cont then() = [[thenPart]] in
     //            let cont else() = [[elsePart]] in
     //              if condition (then, else)
     ir.Continuation thenContinuation = new ir.Continuation([]);
     ir.Continuation elseContinuation = new ir.Continuation([]);
     ir.Expression letElse =
@@ skipping 66 matching lines @@
   /// Creates a for loop in which the initializer, condition, body, update are
   /// created by [buildInitializer], [buildCondition], [buildBody] and
   /// [buildUpdate], respectively.
   ///
   /// The jump [target] is used to identify which `break` and `continue`
   /// statements that have this `for` statement as their target.
   void buildFor({SubbuildFunction buildInitializer,
                  SubbuildFunction buildCondition,
                  SubbuildFunction buildBody,
                  SubbuildFunction buildUpdate,
-                 JumpTarget target}) {
+                 JumpTarget target,
+                 ClosureScope closureScope}) {

[floitsch, 2015/01/08 18:29:36]

add comment about closureScope variable.

     assert(isOpen);
 
     // For loops use four named continuations: the entry to the condition,
     // the entry to the body, the loop exit, and the loop successor (break).
     // The CPS translation of
     // [[for (initializer; condition; update) body; successor]] is:
     //
     // [[initializer]];
     // let cont loop(x, ...) =
     //     let prim cond = [[condition]] in
     //     let cont break() = [[successor]] in
     //     let cont exit() = break(v, ...) in
     //     let cont body() =
     //       let cont continue(x, ...) = [[update]]; loop(v, ...) in
     //       [[body]]; continue(v, ...) in
     //     branch cond (body, exit) in
     // loop(v, ...)
     //
     // If there are no breaks in the body, the break continuation is inlined
     // in the exit continuation (i.e., the translation of the successor
     // statement occurs in the exit continuation).  If there is only one
     // invocation of the continue continuation (i.e., no continues in the
     // body), the continue continuation is inlined in the body.
 
+    if (closureScope != null) {
+      _enterScope(closureScope);

[floitsch, 2015/01/08 18:29:36]

as above (and for the remaining ones): unconditionally call and test in the
function.

+    }
+
     buildInitializer(this);
 
-    IrBuilder condBuilder = new IrBuilder.recursive(this);
+    IrBuilder condBuilder = makeRecursiveBuilder();
     ir.Primitive condition = buildCondition(condBuilder);
     if (condition == null) {
       // If the condition is empty then the body is entered unconditionally.
       condition = condBuilder.buildBooleanLiteral(true);
     }
 
     JumpCollector breakCollector = new JumpCollector(target);
     JumpCollector continueCollector = new JumpCollector(target);
     state.breakCollectors.add(breakCollector);
     state.continueCollectors.add(continueCollector);
 
-    IrBuilder bodyBuilder = new IrBuilder.delimited(condBuilder);
+    IrBuilder bodyBuilder = condBuilder.makeDelimitedBuilder();
     buildBody(bodyBuilder);
     assert(state.breakCollectors.last == breakCollector);
     assert(state.continueCollectors.last == continueCollector);
     state.breakCollectors.removeLast();
     state.continueCollectors.removeLast();
 
     // The binding of the continue continuation should occur as late as
     // possible, that is, at the nearest common ancestor of all the continue
     // sites in the body.  However, that is difficult to compute here, so it
     // is instead placed just outside the body of the body continuation.
     bool hasContinues = !continueCollector.isEmpty;
     IrBuilder updateBuilder = hasContinues
-        ? new IrBuilder.recursive(condBuilder)
+        ? condBuilder.makeRecursiveBuilder()
         : bodyBuilder;
+    if (closureScope != null) {
+      updateBuilder._migrateLoopVariables(closureScope);

[floitsch, 2015/01/08 18:29:35]

ditto

+    }
     buildUpdate(updateBuilder);
 
     // Create body entry and loop exit continuations and a branch to them.
     ir.Continuation bodyContinuation = new ir.Continuation([]);
     ir.Continuation exitContinuation = new ir.Continuation([]);
     ir.LetCont branch =
         new ir.LetCont(exitContinuation,
             new ir.LetCont(bodyContinuation,
                 new ir.Branch(new ir.IsTrue(condition),
                               bodyContinuation,
@@ skipping 65 matching lines @@
   ///     3) `v` is an instance variable in which case [variableSelector]
   ///        defines its write access.
   /// [buildBody] creates the body, `b`, of the loop. The jump [target] is used
   /// to identify which `break` and `continue` statements that have this for-in
   /// statement as their target.
   void buildForIn({SubbuildFunction buildExpression,
                    SubbuildFunction buildVariableDeclaration,
                    Element variableElement,
                    Selector variableSelector,
                    SubbuildFunction buildBody,
-                   JumpTarget target}) {
+                   JumpTarget target,
+                   ClosureScope closureScope}) {
     // The for-in loop
     //
     // for (a in e) s;
     //
     // Is compiled analogously to:
     //
-    // a = e.iterator;
-    // while (a.moveNext()) {
-    //   var n0 = a.current;
+    // it = e.iterator;
+    // while (it.moveNext()) {
+    //   var a = it.current;
     //   s;
     // }
 
     // The condition and body are delimited.
-    IrBuilder condBuilder = new IrBuilder.recursive(this);
+    IrBuilder condBuilder = makeRecursiveBuilder();
 
     ir.Primitive expressionReceiver = buildExpression(this);
     List<ir.Primitive> emptyArguments = new List<ir.Primitive>();
 
     ir.Parameter iterator = new ir.Parameter(null);
     ir.Continuation iteratorInvoked = new ir.Continuation([iterator]);
     add(new ir.LetCont(iteratorInvoked,
         new ir.InvokeMethod(expressionReceiver,
             new Selector.getter("iterator", null), iteratorInvoked,
             emptyArguments)));
 
     ir.Parameter condition = new ir.Parameter(null);
     ir.Continuation moveNextInvoked = new ir.Continuation([condition]);
     condBuilder.add(new ir.LetCont(moveNextInvoked,
         new ir.InvokeMethod(iterator,
             new Selector.call("moveNext", null, 0),
             moveNextInvoked, emptyArguments)));
 
     JumpCollector breakCollector = new JumpCollector(target);
     JumpCollector continueCollector = new JumpCollector(target);
     state.breakCollectors.add(breakCollector);
     state.continueCollectors.add(continueCollector);
 
-    IrBuilder bodyBuilder = new IrBuilder.delimited(condBuilder);
+    IrBuilder bodyBuilder = condBuilder.makeDelimitedBuilder();
+    if (closureScope != null) {
+      bodyBuilder._enterScope(closureScope);
+    }
     if (buildVariableDeclaration != null) {
       buildVariableDeclaration(bodyBuilder);
     }
 
     ir.Parameter currentValue = new ir.Parameter(null);
     ir.Continuation currentInvoked = new ir.Continuation([currentValue]);
     bodyBuilder.add(new ir.LetCont(currentInvoked,
         new ir.InvokeMethod(iterator, new Selector.getter("current", null),
             currentInvoked, emptyArguments)));
     if (Elements.isLocal(variableElement)) {
@@ skipping 55 matching lines @@
     }
   }
 
   /// Creates a while loop in which the condition and body are created by
   /// [buildCondition] and [buildBody], respectively.
   ///
   /// The jump [target] is used to identify which `break` and `continue`
   /// statements that have this `while` statement as their target.
   void buildWhile({SubbuildFunction buildCondition,
                    SubbuildFunction buildBody,
-                   JumpTarget target}) {
+                   JumpTarget target,
+                   ClosureScope closureScope}) {
     assert(isOpen);
     // While loops use four named continuations: the entry to the body, the
     // loop exit, the loop back edge (continue), and the loop exit (break).
     // The CPS translation of [[while (condition) body; successor]] is:
     //
     // let cont continue(x, ...) =
     //     let prim cond = [[condition]] in
     //     let cont break() = [[successor]] in
     //     let cont exit() = break(v, ...) in
     //     let cont body() = [[body]]; continue(v, ...) in
     //     branch cond (body, exit) in
     // continue(v, ...)
     //
     // If there are no breaks in the body, the break continuation is inlined
     // in the exit continuation (i.e., the translation of the successor
     // statement occurs in the exit continuation).
 
     // The condition and body are delimited.
-    IrBuilder condBuilder = new IrBuilder.recursive(this);
+    IrBuilder condBuilder = makeRecursiveBuilder();
     ir.Primitive condition = buildCondition(condBuilder);
 
     JumpCollector breakCollector = new JumpCollector(target);
     JumpCollector continueCollector = new JumpCollector(target);
     state.breakCollectors.add(breakCollector);
     state.continueCollectors.add(continueCollector);
 
-    IrBuilder bodyBuilder = new IrBuilder.delimited(condBuilder);
+    IrBuilder bodyBuilder = condBuilder.makeDelimitedBuilder();
+    if (closureScope != null) {
+      bodyBuilder._enterScope(closureScope);
+    }
     buildBody(bodyBuilder);
     assert(state.breakCollectors.last == breakCollector);
     assert(state.continueCollectors.last == continueCollector);
     state.breakCollectors.removeLast();
     state.continueCollectors.removeLast();
 
     // Create body entry and loop exit continuations and a branch to them.
     ir.Continuation bodyContinuation = new ir.Continuation([]);
     ir.Continuation exitContinuation = new ir.Continuation([]);
     ir.LetCont branch =
@@ skipping 157 matching lines @@
   /// operand in the context of its own [IrBuilder].
   ir.Primitive buildLogicalOperator(
       ir.Primitive leftValue,
       ir.Primitive buildRightValue(IrBuilder builder),
       {bool isLazyOr: false}) {
     // e0 && e1 is translated as if e0 ? (e1 == true) : false.
     // e0 || e1 is translated as if e0 ? true : (e1 == true).
     // The translation must convert both e0 and e1 to booleans and handle
     // local variable assignments in e1.
 
-    IrBuilder rightBuilder = new IrBuilder.delimited(this);
+    IrBuilder rightBuilder = makeDelimitedBuilder();
     ir.Primitive rightValue = buildRightValue(rightBuilder);
     // A dummy empty target for the branch on the left subexpression branch.
     // This enables using the same infrastructure for join-point continuations
     // as in visitIf and visitConditional.  It will hold a definition of the
     // appropriate constant and an invocation of the join-point continuation.
-    IrBuilder emptyBuilder = new IrBuilder.delimited(this);
+    IrBuilder emptyBuilder = makeDelimitedBuilder();
     // Dummy empty targets for right true and right false.  They hold
     // definitions of the appropriate constant and an invocation of the
     // join-point continuation.
-    IrBuilder rightTrueBuilder = new IrBuilder.delimited(rightBuilder);
-    IrBuilder rightFalseBuilder = new IrBuilder.delimited(rightBuilder);
+    IrBuilder rightTrueBuilder = rightBuilder.makeDelimitedBuilder();
+    IrBuilder rightFalseBuilder = rightBuilder.makeDelimitedBuilder();
 
     // If we don't evaluate the right subexpression, the value of the whole
     // expression is this constant.
     ir.Constant leftBool = emptyBuilder.buildBooleanLiteral(isLazyOr);
     // If we do evaluate the right subexpression, the value of the expression
     // is a true or false constant.
     ir.Constant rightTrue = rightTrueBuilder.buildBooleanLiteral(true);
     ir.Constant rightFalse = rightFalseBuilder.buildBooleanLiteral(false);
 
     // Treat the result values as named values in the environment, so they
@@ skipping 41 matching lines @@
             new ir.LetCont(leftTrueContinuation,
                 new ir.LetCont(leftFalseContinuation,
                     new ir.Branch(new ir.IsTrue(leftValue),
                                   leftTrueContinuation,
                                   leftFalseContinuation)))));
     // There is always a join parameter for the result value, because it
     // is different on at least two paths.
     return joinContinuation.parameters.last;
   }
 
-  /// Creates an access to `this`.
+  /// Creates an access to the receiver from the current (or enclosing) method.
+  ///
+  /// If inside a closure class, [buildThis] will redirect acess through closure
+  /// fields in order to access the receiver from the enclosing method.
   ir.Primitive buildThis() {
-    assert(isOpen);
-    ir.Primitive result = new ir.This();
-    add(new ir.LetPrim(result));
-    return result;
+    if (state.receiver != null) return state.receiver;
+    ir.Primitive thisPrim = new ir.This();
+    add(new ir.LetPrim(thisPrim));
+    return thisPrim;
   }
 
   /// Create a non-recursive join-point continuation.
   ///
   /// Given the environment length at the join point and a list of
   /// jumps that should reach the join point, create a join-point
   /// continuation.  The join-point continuation has a parameter for each
   /// variable that has different values reaching on different paths.
   ///
   /// The jumps are uninitialized [ir.InvokeContinuation] expressions.
@@ skipping 87 matching lines @@
     index = 0;
     for (int i = 0; i < environment.length; ++i) {
       if (common[i] == null) {
         environment.index2value[i] = parameters[index++];
       }
     }
 
     return join;
   }
 }
+
+/// Dart-specific subclass of [IrBuilder].
+///
+/// Inner functions are represented by an [ir.FunctionDefinition] with the
+/// IR for the inner function nested inside.
+///
+/// Captured variables are translated to ref cells using [GetClosureVariable]
+/// and [SetClosureVariable].
+class DartIrBuilder extends IrBuilder {
+  ClosureVariableInfo closureVariables;
+
+  IrBuilder _makeInstance() => new DartIrBuilder._blank(closureVariables);
+  DartIrBuilder._blank(this.closureVariables);
+
+  DartIrBuilder(ConstantSystem constantSystem,
+                ExecutableElement currentElement,
+                this.closureVariables) {
+    _init(constantSystem, currentElement);
+    closureVariables.capturedVariables.forEach(closure.makeClosureVariable);
+  }
+
+  /// True if [local] is stored in a ref cell.

[floitsch, 2015/01/08 18:29:35]

What's a "ref cell" ?
Explain more.

[asgerf, 2015/01/12 13:15:42]

Changed to isInClosureVariable. I was thinking about renaming ClosureVariable to
RefCell but then changed my mind halfway through.

+  bool isInRefCell(Local local) {
+    return closure.local2closure.containsKey(local);
+  }
+
+  ir.ClosureVariable getRefCell(Local local) => closure.local2closure[local];
+
+  void _enterScope(ClosureScope scope) {
+    throw 'Not supported';
+  }
+
+  void _enterClosureEnvironment(ClosureEnvironment env) {
+    throw 'Not supported';
+  }
+
+  void _migrateLoopVariables(ClosureScope scope) {
+    throw 'Not supported';
+  }
+
+  void _createFunctionParameter(ParameterElement parameterElement) {
+    ir.Parameter parameter = new ir.Parameter(parameterElement);
+    _parameters.add(parameter);
+    if (isInRefCell(parameterElement)) {
+      state.functionParameters.add(getRefCell(parameterElement));
+    } else {
+      state.functionParameters.add(parameter);
+      environment.extend(parameterElement, parameter);
+    }
+  }
+
+  void declareLocalVariable(LocalVariableElement variableElement,
+                            {ir.Primitive initialValue}) {
+    assert(isOpen);
+    if (initialValue == null) {
+      initialValue = buildNullLiteral();
+    }
+    if (isInRefCell(variableElement)) {
+      add(new ir.SetClosureVariable(getRefCell(variableElement),
+                                    initialValue,
+                                    isDeclaration: true));
+    } else {
+      initialValue.useElementAsHint(variableElement);
+      environment.extend(variableElement, initialValue);
+    }
+  }
+
+  /// Add [functionElement] to the environment with provided [definition].
+  void declareLocalFunction(LocalFunctionElement functionElement,
+                            ir.FunctionDefinition definition) {
+    assert(isOpen);
+    if (isInRefCell(functionElement)) {
+      ir.ClosureVariable variable = getRefCell(functionElement);
+      add(new ir.DeclareFunction(variable, definition));
+    } else {
+      ir.CreateFunction prim = new ir.CreateFunction(definition);
+      add(new ir.LetPrim(prim));
+      environment.extend(functionElement, prim);
+      prim.useElementAsHint(functionElement);
+    }
+  }
+
+  /// Create a function expression from [definition].
+  ir.Primitive buildFunctionExpression(ir.FunctionDefinition definition) {
+    ir.CreateFunction prim = new ir.CreateFunction(definition);
+    add(new ir.LetPrim(prim));
+    return prim;
+  }
+
+  /// Create a read access of [local].
+  ir.Primitive buildLocalGet(LocalElement local) {
+    assert(isOpen);
+    if (isInRefCell(local)) {
+      ir.Primitive result = new ir.GetClosureVariable(getRefCell(local));
+      result.useElementAsHint(local);
+      add(new ir.LetPrim(result));
+      return result;
+    } else {
+      return environment.lookup(local);
+    }
+  }
+
+  /// Create a write access to [local] with the provided [value].
+  ir.Primitive buildLocalSet(LocalElement local, ir.Primitive value) {
+    assert(isOpen);
+    if (isInRefCell(local)) {
+      add(new ir.SetClosureVariable(getRefCell(local), value));
+    } else {
+      value.useElementAsHint(local);
+      environment.update(local, value);
+    }
+    return value;
+  }
+
+
+}
+
+/// JS-specific subclass of [IrBuilder].
+///
+/// Inner functions are repsented by a [ClosureClassElement], and captured

[floitsch, 2015/01/08 18:29:36]

represented

[asgerf, 2015/01/12 13:15:42]

Done.

+/// variables are boxed as necessary using [CreateBox], [GetField], [SetField].
+class JsIrBuilder extends IrBuilder {
+  IrBuilder _makeInstance() => new JsIrBuilder._blank();
+  JsIrBuilder._blank();
+
+  JsIrBuilder(ConstantSystem constantSystem, ExecutableElement currentElement) {
+    _init(constantSystem, currentElement);
+  }
+
+  void _enterClosureEnvironment(ClosureEnvironment env) {
+    ir.Primitive thisPrim = new ir.This();

[floitsch, 2015/01/08 18:29:36]

more comments.

[asgerf, 2015/01/12 13:15:42]

Done.

+    add(new ir.LetPrim(thisPrim));
+    env.freeVariables.forEach((Local local, ClosureLocation location) {
+      if (location.isBox) {
+        state.boxedVariables[local] = location;
+      } else {
+        ir.Primitive load = new ir.GetField(thisPrim, location.field);

[floitsch, 2015/01/08 18:29:35]

Add comment, that dead-code elimination will remove unnecessary loads.
(correct?)

[asgerf, 2015/01/12 13:15:43]

Shrinking reductions will remove a dead GetField, but I think the comment would
be misleading.

Assuming [freeVariables] does not have superfluous entries, then unless the free
occurrence is unreachable control-flow wise, there will be no unnecessary loads.
And besides, there is no check we can reasonably perform here that would prevent
creating such a GetField.

+        add(new ir.LetPrim(load));
+        environment.extend(local, load);
+      }
+    });
+    if (env.thisLocal != null && env.freeVariables.containsKey(env.thisLocal)) {
+      state.receiver = environment.lookup(env.thisLocal);
+    }
+    if (env.selfReference != null) {
+      environment.extend(env.selfReference, thisPrim);
+    }
+  }
+
+  void _enterScope(ClosureScope scope) {
+    if (scope.box != null) {
+      ir.CreateBox boxPrim = new ir.CreateBox();
+      add(new ir.LetPrim(boxPrim));
+      environment.extend(scope.box, boxPrim);
+      boxPrim.useElementAsHint(scope.box);
+    }
+    scope.capturedVariables.forEach((Local local, ClosureLocation location) {
+      assert(!state.boxedVariables.containsKey(local));
+      if (location.isBox) {
+        state.boxedVariables[local] = location;
+      }
+    });
+  }
+
+  void _createFunctionParameter(ParameterElement parameterElement) {
+    ir.Parameter parameter = new ir.Parameter(parameterElement);
+    _parameters.add(parameter);
+    state.functionParameters.add(parameter);
+    ClosureLocation location = state.boxedVariables[parameterElement];
+    if (location != null) {
+      add(new ir.SetField(environment.lookup(location.box),
+                          location.field,
+                          parameter));
+    } else {
+      environment.extend(parameterElement, parameter);
+    }
+  }
+
+  void declareLocalVariable(LocalElement variableElement,
+                            {ir.Primitive initialValue}) {
+    assert(isOpen);
+    if (initialValue == null) {
+      initialValue = buildNullLiteral();
+    }
+    ClosureLocation location = state.boxedVariables[variableElement];
+    if (location != null) {
+      add(new ir.SetField(environment.lookup(location.box),
+                          location.field,
+                          initialValue));
+    } else {
+      initialValue.useElementAsHint(variableElement);
+      environment.extend(variableElement, initialValue);
+    }
+  }
+
+  /// Add [functionElement] to the environment with provided [definition].
+  void declareLocalFunction(LocalFunctionElement functionElement,
+                            ClosureClassElement classElement) {
+    ir.Primitive closure = buildFunctionExpression(classElement);
+    declareLocalVariable(functionElement, initialValue: closure);
+  }
+
+  ir.Primitive buildFunctionExpression(ClosureClassElement classElement) {
+    List<ir.Primitive> arguments = <ir.Primitive>[];
+    for (ClosureFieldElement field in classElement.closureFields) {
+      arguments.add(environment.lookup(field.local));
+    }
+    ir.Primitive closure = new ir.CreateClosureClass(classElement, arguments);
+    add(new ir.LetPrim(closure));
+    return closure;
+  }
+
+  /// Create a read access of [local].
+  ir.Primitive buildLocalGet(LocalElement local) {
+    assert(isOpen);
+    ClosureLocation location = state.boxedVariables[local];
+    if (location != null) {
+      ir.Primitive result = new ir.GetField(environment.lookup(location.box),
+                                            location.field);
+      result.useElementAsHint(local);
+      add(new ir.LetPrim(result));
+      return result;
+    } else {
+      return environment.lookup(local);
+    }
+  }
+
+  /// Create a write access to [local] with the provided [value].
+  ir.Primitive buildLocalSet(LocalElement local, ir.Primitive value) {
+    assert(isOpen);
+    ClosureLocation location = state.boxedVariables[local];
+    if (location != null) {
+      add(new ir.SetField(environment.lookup(location.box),
+                          location.field,
+                          value));
+    } else {
+      value.useElementAsHint(local);
+      environment.update(local, value);
+    }
+    return value;
+  }
+
+  void _migrateLoopVariables(ClosureScope scope) {
+    if (scope.boxedLoopVariables.isEmpty) return;
+    ir.Primitive box = environment.lookup(scope.box);
+    ir.Primitive newBox = new ir.CreateBox();
+    newBox.useElementAsHint(scope.box);
+    add(new ir.LetPrim(newBox));
+    for (VariableElement loopVar in scope.boxedLoopVariables) {
+      ClosureLocation location = scope.capturedVariables[loopVar];
+      ir.Primitive get = new ir.GetField(box, location.field);
+      add(new ir.LetPrim(get));
+      add(new ir.SetField(newBox, location.field, get));
+    }
+    environment.update(scope.box, newBox);
+  }
+
+}
+
+
+/// Location of a variable relative to a given closure.
+class ClosureLocation {
+  /// If not `null`, this location is [box].[field].
+  /// The location of [box] can be obtained separately from an
+  /// enclosing [ClosureEnvironment] or [ClosureScope].
+  /// If `null`, then the location is [field] on the enclosing function object.
+  final BoxLocal box;
+
+  /// The field in which the variable is stored.
+  final Entity field;
+
+  bool get isBox => box != null;
+
+  ClosureLocation(this.box, this.field);
+}
+
+/// Introduces a new box and binds local variables to this box.
+///
+/// A [ClosureScope] may exist for each function and for each loop.
+/// Generally, one may pass `null` to the [IrBuilder] instead of a
+/// [ClosureScope] when a given scope has no boxed variables.
+class ClosureScope {
+  /// This box is now in scope and [capturedVariables] may use it.
+  final BoxLocal box;
+
+  /// Maps [LocalElement]s to their location.
+  final Map<Local, ClosureLocation> capturedVariables;
+
+  /// If this is the scope of a for-loop, [boxedLoopVariables] is the list
+  /// of boxed variables that are declared in the initializer.
+  final List<VariableElement> boxedLoopVariables;
+
+  ClosureScope(this.box, this.capturedVariables, this.boxedLoopVariables);
+}
+
+/// Environment passed when building a nested function, describing how
+/// to access variables from the enclosing scope.
+class ClosureEnvironment {
+  /// References to this local should be treated as recursive self-reference.
+  /// (This is *not* in [freeVariables]).
+  final LocalFunctionElement selfReference;
+
+  /// If non-null, [thisLocal] has an entry in [freeVariables] describing where
+  /// to find the captured value of `this`.
+  final ThisLocal thisLocal;
+
+  /// Maps [LocalElement]s, [BoxLocal]s and [ThisLocal] to their location.
+  final Map<Local, ClosureLocation> freeVariables;
+
+  ClosureEnvironment(this.selfReference, this.thisLocal, this.freeVariables);
+}
+
+/// Information about which variables are captured in a closure.
+/// This is used by the [DartIrBuilder] instead of [ClosureScope] and
+/// [ClosureEnvironment].
+abstract class ClosureVariableInfo {
+  Iterable<Local> get capturedVariables;
+}