dart2dart: Preserve variable names throughout the IR.

sdk/lib/_internal/compiler/implementation/ir/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.
 
 // IrNodes are kept in a separate library to have precise control over their
 // dependencies on other parts of the system.
 library dart2js.ir_nodes;
 
 import '../dart2jslib.dart' as dart2js show Constant;
 import '../elements/elements.dart'
-    show FunctionElement, LibraryElement, ParameterElement, ClassElement;
+    show FunctionElement, LibraryElement, ParameterElement, ClassElement,
+    Element, VariableElement;
 import '../universe/universe.dart' show Selector, SelectorKind;
 import '../dart_types.dart' show DartType, GenericType;
+import '../helpers/helpers.dart';
 
 abstract class Node {
   static int hashCount = 0;
   final int hashCode = hashCount = (hashCount + 1) & 0x3fffffff;
 
   accept(Visitor visitor);
 }
 
 abstract class Expression extends Node {
   Expression plug(Expression expr) => throw 'impossible';
 }
 
 /// The base class of things that variables can refer to: primitives,
 /// continuations, function and continuation parameters, etc.
 abstract class Definition extends Node {
   // The head of a linked-list of occurrences, in no particular order.
   Reference firstRef = null;
 
+  /// The [LetCont], [LetPrim], [Continuation] or [FunctionDefinition] binding
+  /// this definition.
+  Node binding;
+
   bool get hasAtMostOneUse => firstRef == null || firstRef.nextRef == null;
   bool get hasExactlyOneUse => firstRef != null && firstRef.nextRef == null;
   bool get hasAtLeastOneUse => firstRef != null;
   bool get hasMultipleUses => !hasAtMostOneUse;
 
   void substituteFor(Definition other) {
     if (other.firstRef == null) return;
     Reference previous, current = other.firstRef;
     do {
       current.definition = this;
       previous = current;
       current = current.nextRef;
     } while (current != null);
     previous.nextRef = firstRef;
     firstRef = other.firstRef;
   }
 }
 
+/// A pure expression that cannot throw or diverge.
+/// All primitives are named using the identity of the [Primitive] object.
 abstract class Primitive extends Definition {
+  /// The [VariableElement] or [ParameterElement] from which the primitive
+  /// binding originated.
+  Element element;
+
+  /// Register in which the variable binding this primitive can be allocated.
+  /// Separate register spaces are used for primitives with different [element].
+  /// Assigned by [RegisterAllocator], is null before that phase.
+  int registerIndex;
 }
 
 /// Operands to invocations and primitives are always variables.  They point to
 /// their definition and are linked into a list of occurrences.
 class Reference {
   Definition definition;
   Reference nextRef = null;
 
   Reference(this.definition) {
     nextRef = definition.firstRef;
     definition.firstRef = this;
   }
 }
 
 /// Binding a value (primitive or constant): 'let val x = V in E'.  The bound
 /// value is in scope in the body.
 /// During one-pass construction a LetVal with an empty body is used to
 /// represent one-level context 'let val x = V in []'.
 class LetPrim extends Expression {
   final Primitive primitive;
   Expression body = null;
 
-  LetPrim(this.primitive);
+  LetPrim(this.primitive) {
+    primitive.binding = this;
+  }
 
   Expression plug(Expression expr) {
     assert(body == null);
     return body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitLetPrim(this);
 }
 
 
 /// Binding a continuation: 'let cont k(v) = E in E'.  The bound continuation
 /// is in scope in the body and the continuation parameter is in scope in the
 /// continuation body.
 /// During one-pass construction a LetCont with an empty continuation body is
 /// used to represent the one-level context 'let cont k(v) = [] in E'.
 class LetCont extends Expression {
   final Continuation continuation;
   final Expression body;
 
-  LetCont(this.continuation, this.body);
+  LetCont(this.continuation, this.body) {
+    continuation.binding = this;
+  }
 
   Expression plug(Expression expr) {
     assert(continuation.body == null);
     return continuation.body = expr;
   }
 
   accept(Visitor visitor) => visitor.visitLetCont(this);
 }
 
 abstract class Invoke {
@@ skipping 187 matching lines @@
   List<Reference> values;
 
   LiteralMap(List<Primitive> keys, List<Primitive> values)
       : this.keys = _referenceList(keys),
         this.values = _referenceList(values);
 
   accept(Visitor visitor) => visitor.visitLiteralMap(this);
 }
 
 class Parameter extends Primitive {
-  final ParameterElement element;
-
-  Parameter(this.element);
+  Parameter(Element element) {
+    super.element = element;
+  }
 
   accept(Visitor visitor) => visitor.visitParameter(this);
 }
 
 /// Continuations are normally bound by 'let cont'.  A continuation with no
 /// parameter (or body) is used to represent a function's return continuation.
 /// The return continuation is bound by the Function, not by 'let cont'.
 class Continuation extends Definition {
   final List<Parameter> parameters;
   Expression body = null;
 
   // A continuation is recursive if it has any recursive invocations.
   bool isRecursive = false;
 
-  Continuation(this.parameters);
+  Continuation(this.parameters) {
+    for (Parameter param in parameters) {
+      param.binding = this;
+    }
+  }
 
   Continuation.retrn() : parameters = null;
 
   accept(Visitor visitor) => visitor.visitContinuation(this);
 }
 
 /// A function definition, consisting of parameters and a body.  The parameters
 /// include a distinguished continuation parameter.
 class FunctionDefinition extends Node {
   final Continuation returnContinuation;
   final List<Parameter> parameters;
   final Expression body;
 
-  FunctionDefinition(this.returnContinuation, this.parameters, this.body);
+  FunctionDefinition(this.returnContinuation, this.parameters, this.body) {
+    for (Parameter param in parameters) {
+      param.binding = this;
+    }
+    returnContinuation.binding = this;
+  }
 
   accept(Visitor visitor) => visitor.visitFunctionDefinition(this);
 }
 
 List<Reference> _referenceList(List<Definition> definitions) {
   return definitions.map((e) => new Reference(e)).toList(growable: false);
 }
 
 abstract class Visitor<T> {
   T visit(Node node) => node.accept(this);
@@ skipping 151 matching lines @@
   String visitContinuation(Continuation node) {
     // Continuations are visited directly in visitLetCont.
     return '(Unexpected Continuation)';
   }
 
   String visitIsTrue(IsTrue node) {
     String value = names[node.value.definition];
     return '(IsTrue $value)';
   }
 }
+
+/// Determines for each continuations the highest scope to which it can be
+/// lifted without moving a reference out of scope.
+/// A scope is a [LetPrim], [Continuation], or top-level (represented as null).
+/// Does not mutate the IR.
+class FindLiftableContinuations extends Visitor {
+  final Map<Node, int> scope2depth = <Node, int>{};
+
+  /// Maps a scope to its enclosing continuation (prior to lifting) or null
+  /// if not inside a continuation.
+  final Map<Node, Continuation> enclosingContinuation = <Node, Continuation>{};
+
+  /// Maps a continuation to the outermost scope to which it can be lifted,
+  /// or null or absent if it can be lifted all the way to top-level.
+  final Map<Continuation, Node> liftTarget = <Continuation, Node>{};
+
+  /// Inverse of [liftTarget].
+  final Map<Node, List<Continuation>> liftedContinuations =
+      <Node, List<Continuation>>{};
+
+  Continuation currentContinuation;
+  int currentDepth = 0;
+
+  /// Restricts [child] so that it cannot be lifted outside of [ancestor].
+  void requireAncestor(Node child, Node ancestor) {
+    // Only continuations are lifted, but in doing so, all let bindings inside
+    // the continuation are also lifted with it. we therefore restrict the
+    // lifting of the continuation that encloses [child].
+    Continuation cont = enclosingContinuation[child];
+
+    // If [child] is in the top-level it cannot be lifted, hence no restrictions
+    // are necessary
+    if (cont == null) return;
+
+    // If [child] and [ancestor] are in the same continuation, their nesting
+    // order is unaffected by lifting, so no restrictions are necessary.
+    if (enclosingContinuation[ancestor] == cont) return;
+
+    // The continuation may not be lifted further than [ancestor].
+    liftTarget[cont] = join(liftTarget[cont], ancestor);
+
+    assert(liftTarget[cont] != cont);
+  }
+
+  /// Returns the deepest of the two given scopes. The nesting order of scopes

[Kevin Millikin (Google), 2014/06/10 11:33:01]

For doc comments, the first paragraph should be a one-line description:
https://www.dartlang.org/articles/doc-comment-guidelines/

+  /// may be affected by lifting, but this function will restrict lifting of
+  /// continuations to ensure that the returned scope remains the most deeply
+  /// nested scope also after lifting.
+  Node join(Node s1, Node s2) {

[Kevin Millikin (Google), 2014/06/10 11:33:01]

Maybe this reads better with a descriptive name.  deepest?  deepestOf?

+    if (s1 == null) return s2;
+    if (s2 == null) return s1;
+    if (s1 == s2) return s1;
+    int d1 = scope2depth[s1];
+    int d2 = scope2depth[s2];
+    assert(d1 != d2);
+    if (d1 < d2) { // s1 is ancestor of s2?
+      requireAncestor(s2, s1); // ensure that s2 remains inside of s1
+      return s2;
+    } else {
+      requireAncestor(s1, s2); // ensure that s1 remains inside of s2
+      return s1;
+    }
+  }
+
+  /// Returns the continuations that could be lifted to the given scope.
+  Iterable<Continuation> getContinuationsLiftedTo(Node scope) {
+    List list = liftedContinuations[scope];
+    if (list != null)

[Kevin Millikin (Google), 2014/06/10 11:33:01]

Put return list on the same line as the if.  Otherwise you need braces around
the body.

+      return list;
+    return const [];
+  }
+
+  void visitFunctionDefinition(FunctionDefinition node) {
+    scope2depth[node] = 0;
+    ++currentDepth;
+    visit(node.body);
+    --currentDepth;
+
+    // Build inverse of liftTarget
+    for (Continuation cont in liftTarget.keys) {
+      Node target = liftTarget[cont];
+      List<Continuation> list = liftedContinuations[target];
+      if (list == null) {
+        list = <Continuation>[];
+        liftedContinuations[target] = list;
+      }
+      list.add(cont);
+    }
+  }
+
+  // visit returns the outermost scope to which the given expression
+  // can be lifted without breaking scope.
+
+  Node visitReference(Reference ref) {
+    Definition definition = ref.definition;
+    if (definition is Continuation) {
+      // Non-recursive reference to a continuation. Its lift target has been
+      // completely resolved by now since we are inside the LetCont binding.
+      // This reference can be lifted as far as the continuation.
+      return liftTarget[definition];
+    } else {
+      return definition.binding;
+    }
+  }
+
+  Node visitReferenceList(List<Reference> refs) {
+    Node scope = null;
+    for (Reference ref in refs) {
+      scope = join(scope, visitReference(ref));
+    }
+    return scope;
+  }
+
+  Node visitRecursiveReference(Reference ref) {
+    // A recursive self-reference inside a continuation can be lifted to the
+    // body of the continuation, not the body of the LetCont.
+    return ref.definition as Continuation;
+  }
+
+  Node visitLetPrim(LetPrim node) {
+    Node primScope = visit(node.primitive);
+    scope2depth[node] = currentDepth;
+    enclosingContinuation[node] = currentContinuation;
+    ++currentDepth;
+    Node bodyScope = visit(node.body);
+    --currentDepth;
+    return join(primScope, bodyScope);
+  }
+
+  Node visitLetCont(LetCont node) {
+    scope2depth[node] = currentDepth;
+    enclosingContinuation[node] = currentContinuation;
+    ++currentDepth;
+    visit(node.continuation);
+    Node bodyScope = visit(node.body);
+    --currentDepth;
+    return bodyScope;
+  }
+
+  Node visitInvokeStatic(InvokeStatic node) {
+    Node argScope = visitReferenceList(node.arguments);
+    Node contScope = visitReference(node.continuation);
+    return join(argScope, contScope);
+  }
+
+  Node visitInvokeContinuation(InvokeContinuation node) {
+    Node argScope = visitReferenceList(node.arguments);
+    Node contScope = node.isRecursive
+        ? visitRecursiveReference(node.continuation)
+        : visitReference(node.continuation);
+    return join(argScope, contScope);
+  }
+
+  Node visitInvokeMethod(InvokeMethod node) {
+    Node receiverScope = visitReference(node.receiver);
+    Node argScope = visitReferenceList(node.arguments);
+    Node contScope = visitReference(node.continuation);
+    return join(receiverScope, join(argScope, contScope));
+  }
+
+  Node visitInvokeConstructor(InvokeConstructor node) {
+    Node argScope = visitReferenceList(node.arguments);
+    Node contScope = visitReference(node.continuation);
+    return join(argScope, contScope);
+  }
+
+  Node visitConcatenateStrings(ConcatenateStrings node) {
+    Node argScope = visitReferenceList(node.arguments);
+    Node contScope = visitReference(node.continuation);
+    return join(argScope, contScope);
+  }
+
+  Node visitBranch(Branch node) {
+    Node condScope = visit(node.condition);
+    Node thenScope = visitReference(node.trueContinuation);
+    Node elseScope = visitReference(node.falseContinuation);
+    return join(condScope, join(thenScope, elseScope));
+  }
+
+  Node visitInvokeConstConstructor(InvokeConstConstructor node) {
+    return visitReferenceList(node.arguments);
+  }
+
+  Node visitLiteralList(LiteralList node) {
+    return visitReferenceList(node.values);
+  }
+
+  Node visitLiteralMap(LiteralMap node) {
+    Node keyScope = visitReferenceList(node.keys);
+    Node valueScope = visitReferenceList(node.values);
+    return join(keyScope, valueScope);
+  }
+
+  Node visitConstant(Constant node) {
+    return null;
+  }
+
+  Node visitParameter(Parameter node) {
+    throw "Parameters should not be visited";
+  }
+
+  void visitContinuation(Continuation node) {
+    enclosingContinuation[node] = node;
+    liftTarget[node] = null;
+    scope2depth[node] = currentDepth;
+    Continuation oldCont = currentContinuation;
+    currentContinuation = node;
+    ++currentDepth;
+    Node bodyScope = visit(node.body);
+    --currentDepth;
+    // If the body contains a reference to one of the continuation parameters,
+    // then the scope will be the continuation itself, and the nesting
+    // restrictions on the continuation will have been added by join().
+    // In other cases we must add the nesting restrictions here.
+    if (bodyScope != node) {
+      requireAncestor(node, bodyScope);
+    }
+    currentContinuation = oldCont;
+  }
+
+  Node visitIsTrue(IsTrue node) {
+    return visitReference(node.value);
+  }
+
+}
+
+/// Keeps track of currently unused register indices.
+class RegisterArray {
+  int nextIndex = 0;
+  final List<int> freeStack = <int>[];
+
+  int makeIndex() {
+    if (freeStack.isEmpty) {
+      return nextIndex++;
+    } else {
+      return freeStack.removeLast();
+    }
+  }
+
+  void releaseIndex(int index) {
+    freeStack.add(index);
+  }
+}
+
+/// Assigns indices to each primitive in the IR such that primitives that are
+/// live simultaneously never get assigned the same index.
+/// This information is used by the dart tree builder to generate fewer
+/// redundant variables.
+/// Currently, the liveness analysis is very simple and is often inadequate
+/// for removing all of the redundant variables.
+class RegisterAllocator extends Visitor {
+  final FindLiftableContinuations lifts = new FindLiftableContinuations();
+
+  /// Separate register spaces for each source-level variable/parameter.
+  /// Note that null is used as key for primitives without elements.
+  final Map<Element, RegisterArray> elementRegisters =
+      <Element, RegisterArray>{};
+
+  RegisterArray getRegisterArray(Element element) {
+    RegisterArray registers = elementRegisters[element];
+    if (registers == null) {
+      registers = new RegisterArray();
+      elementRegisters[element] = registers;
+    }
+    return registers;
+  }
+
+  void allocate(Primitive primitive) {
+    if (primitive.registerIndex == null) {
+      primitive.registerIndex = getRegisterArray(primitive.element).makeIndex();
+    }
+  }
+
+  void release(Primitive primitive) {
+    // Do not share indices for temporaries as this may obstruct inlining.
+    if (primitive.element == null) return;
+    if (primitive.registerIndex != null) {
+      getRegisterArray(primitive.element).releaseIndex(primitive.registerIndex);
+    }
+  }
+
+  void visitLiftedContinuations(Node scope) {
+    for (Continuation cont in lifts.getContinuationsLiftedTo(scope)) {
+      assert(cont != scope);
+      visit(cont);
+    }
+  }
+
+  void visitReference(Reference reference) {
+    allocate(reference.definition);
+  }
+
+  void visitFunctionDefinition(FunctionDefinition node) {
+    lifts.visit(node);
+    visitLiftedContinuations(node);
+    visitLiftedContinuations(null);
+    visit(node.body);
+    node.parameters.forEach(allocate); // Assign indices to unused parameters.
+    elementRegisters.clear();
+  }
+
+  void visitLetPrim(LetPrim node) {
+    visitLiftedContinuations(node);
+    visit(node.body);
+    release(node.primitive);
+    visit(node.primitive);
+  }
+
+  void visitLetCont(LetCont node) {
+    assert(lifts.liftTarget.containsKey(node.continuation));
+    visit(node.body);
+  }
+
+  void visitInvokeStatic(InvokeStatic node) {
+    node.arguments.forEach(visitReference);
+  }
+
+  void visitInvokeContinuation(InvokeContinuation node) {
+    node.arguments.forEach(visitReference);
+  }
+
+  void visitInvokeMethod(InvokeMethod node) {
+    visitReference(node.receiver);
+    node.arguments.forEach(visitReference);
+  }
+
+  void visitInvokeConstructor(InvokeConstructor node) {
+    node.arguments.forEach(visitReference);
+  }
+
+  void visitConcatenateStrings(ConcatenateStrings node) {
+    node.arguments.forEach(visitReference);
+  }
+
+  void visitBranch(Branch node) {
+    visit(node.condition);
+  }
+
+  void visitInvokeConstConstructor(InvokeConstConstructor node) {
+    node.arguments.forEach(visitReference);
+  }
+
+  void visitLiteralList(LiteralList node) {
+    node.values.forEach(visitReference);
+  }
+
+  void visitLiteralMap(LiteralMap node) {
+    for (int i = 0; i < node.keys.length; ++i) {
+      visitReference(node.keys[i]);
+      visitReference(node.values[i]);
+    }
+  }
+
+  void visitConstant(Constant node) {
+  }
+
+  void visitParameter(Parameter node) {
+    throw "Parameters should not be visited by RegisterAllocator";
+  }
+
+  void visitContinuation(Continuation node) {
+    visitLiftedContinuations(node);
+    visit(node.body);
+
+    // Arguments get allocated left-to-right, so we release parameters
+    // right-to-left. This increases the likelihood that arguments can be
+    // transferred without intermediate assignments.
+    for (int i = node.parameters.length - 1; i >= 0; --i) {
+      release(node.parameters[i]);
+    }
+  }
+
+  void visitIsTrue(IsTrue node) {
+    visitReference(node.value);
+  }
+
+}