dart2dart: Preserve variable names throughout the IR.

sdk/lib/_internal/compiler/implementation/ir/ir_nodes.dart

Index: sdk/lib/_internal/compiler/implementation/ir/ir_nodes.dart
diff --git a/sdk/lib/_internal/compiler/implementation/ir/ir_nodes.dart b/sdk/lib/_internal/compiler/implementation/ir/ir_nodes.dart
index 6db0e8f63efd1467f477a7e39a424e42ddbfa36c..cae622f433d7a02c2cca2ade8c021e683e3d92cb 100644
--- a/sdk/lib/_internal/compiler/implementation/ir/ir_nodes.dart
+++ b/sdk/lib/_internal/compiler/implementation/ir/ir_nodes.dart
@@ -8,9 +8,11 @@ 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;
@@ -29,6 +31,10 @@ 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;
@@ -47,7 +53,17 @@ abstract class Definition extends Node {
   }
 }
 
+/// An pure expression that cannot throw or diverge.

[sigurdm, 2014/06/04 07:51:56]

An -> A

+/// 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
@@ -70,7 +86,9 @@ 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);
@@ -90,7 +108,9 @@ 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);
@@ -273,9 +293,9 @@ class LiteralMap extends Primitive {
 }
 
 class Parameter extends Primitive {
-  final ParameterElement element;
-
-  Parameter(this.element);
+  Parameter(Element element) {
+    super.element = element;
+  }
 
   accept(Visitor visitor) => visitor.visitParameter(this);
 }
@@ -290,7 +310,11 @@ class Continuation extends Definition {
   // 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;
 
@@ -304,7 +328,12 @@ class FunctionDefinition extends Node {
   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);
 }
@@ -346,6 +375,7 @@ abstract class Visitor<T> {
   T visitIsTrue(IsTrue node) => visitCondition(node);
 }
 
+

[sigurdm, 2014/06/04 07:51:56]

Extra newline

 /// Generate a Lisp-like S-expression representation of an IR node as a string.
 /// The representation is not pretty-printed, but it can easily be quoted and
 /// dropped into the REPL of one's favorite Lisp or Scheme implementation to be
@@ -475,3 +505,372 @@ class SExpressionStringifier extends Visitor<String> {
     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
+  /// 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) {
+    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)
+      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 ref.definition.binding;

[sigurdm, 2014/06/04 07:51:56]

You can use
return definition.binding

[asgerf, 2014/06/04 09:40:51]

Thanks

+    }
+  }
+
+  Node visitReferenceList(List<Reference> refs) {

[sigurdm, 2014/06/04 07:51:56]

Could be a fold

+    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 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 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);
+  }
+
+}