dart2dart: Preserve variable names throughout the IR.

sdk/lib/_internal/compiler/implementation/dart_backend/dart_tree.dart

 // Copyright (c) 2014, 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 dart_tree;
 
 import '../dart2jslib.dart' as dart2js;
 import '../elements/elements.dart'
     show Element, FunctionElement, FunctionSignature, ParameterElement,
          ClassElement;
@@ skipping 65 matching lines @@
   int useCount = 0;
 
   /// The [LabeledStatement] or [WhileTrue] binding this label.
   JumpTarget binding;
 }
 
 /**
  * Variables are [Expression]s.
  */
 class Variable extends Expression {
-  // A counter used to generate names.  The counter is reset to 0 for each
-  // function emitted.
-  static int counter = 0;
-  static String _newName() => 'v${counter++}';
+  /// Element used for synthesizing a name for the variable.
+  /// Different variables may have the same element. May be null.
+  Element element;
 
-  Element element;
-  String cachedName;
-
-  String get name {
-    if (cachedName != null) return cachedName;
-    return cachedName = ((element == null) ? _newName() : element.name);
-  }
+  int readCount = 0;
 
   Variable(this.element);
 
   accept(ExpressionVisitor visitor) => visitor.visitVariable(this);
 }
 
 /**
  * Common interface for invocations with arguments.
  */
 abstract class Invoke {
@@ skipping 204 matching lines @@
 
   WhileCondition(this.label, this.condition, this.body,
                  this.next, this.updates) {
     assert(label.binding == null);
     label.binding = this;
   }
 
   accept(StatementVisitor visitor) => visitor.visitWhileCondition(this);
 }
 
-
 /// A [Break] or [Continue] statement.
 abstract class Jump extends Statement {
   Label get target;
 }
 
 /**
  * A break from an enclosing [LabeledStatement].  The break targets the
  * labeled statement's successor statement.
  */
 class Break extends Jump {
   final Label target;
 
   Statement get next => null;
   void set next(Statement s) => throw 'UNREACHABLE';
 
   Break(this.target) {
     ++target.useCount;
   }
 
   accept(StatementVisitor visitor) => visitor.visitBreak(this);
 }
 
 /**
- * A continue to an enclosing [WhileTrue] loop.  The continue targets the
- * loop's body.
+ * A continue to an enclosing [WhileTrue] or [WhileCondition] loop.
+ * The continue targets the loop's body.
  */
 class Continue extends Jump {
   final Label target;
 
   Statement get next => null;
   void set next(Statement s) => throw 'UNREACHABLE';
 
   Continue(this.target) {
     ++target.useCount;
   }
 
   accept(StatementVisitor visitor) => visitor.visitContinue(this);
 }
 
 /**
  * An assignments of an [Expression] to a [Variable].
  *
  * In contrast to the CPS-based IR, non-primitive expressions can be assigned
  * to variables.
  */
 class Assign extends Statement {
   Statement next;
   final Variable variable;
   Expression definition;
-  final bool hasExactlyOneUse;
 
-  Assign(this.variable, this.definition, this.next, this.hasExactlyOneUse);
+  Assign(this.variable, this.definition, this.next);
+
+  bool get hasExactlyOneUse => variable.readCount == 1;
 
   accept(StatementVisitor visitor) => visitor.visitAssign(this);
 }
 
-
 /**
  * A return exit from the function.
  *
  * In contrast to the CPS-based IR, the return value is an arbitrary
  * expression.
  */
 class Return extends Statement {
   /// Should not be null. Use [Constant] with [NullConstant] for void returns.
   Expression value;
 
   Statement get next => null;
   void set next(Statement s) => throw 'UNREACHABLE';
 
   Return(this.value);
 
   accept(StatementVisitor visitor) => visitor.visitReturn(this);
 }
 
-
-
-
 /**
  * A conditional branch based on the true value of an [Expression].
  */
 class If extends Statement {
   Expression condition;
   Statement thenStatement;
   Statement elseStatement;
 
   Statement get next => null;
   void set next(Statement s) => throw 'UNREACHABLE';
 
   If(this.condition, this.thenStatement, this.elseStatement);
 
   accept(StatementVisitor visitor) => visitor.visitIf(this);
 }
 
-
 class ExpressionStatement extends Statement {
   Statement next;
   Expression expression;
 
   ExpressionStatement(this.expression, this.next);
 
   accept(StatementVisitor visitor) => visitor.visitExpressionStatement(this);
 }
 
 class FunctionDefinition extends Node {
@@ skipping 66 matching lines @@
  * translation out of SSA.  Jumps are eliminated during the Tree-to-Tree
  * control-flow recognition.
  *
  * Otherwise, the output of Builder looks very much like the input.  In
  * particular, intermediate values and blocks used for local control flow are
  * still all named.
  */
 class Builder extends ir.Visitor<Node> {
   final dart2js.Compiler compiler;
 
-  // Uses of IR primitives are replaced with Tree variables.  This is the
-  // mapping from primitives to variables.
-  final Map<ir.Primitive, Variable> variables = <ir.Primitive, Variable>{};
+  /// Maps variable/parameter elements to the Tree variables that represent it.
+  final Map<Element, List<Variable>> element2variables =
+      <Element,List<Variable>>{};
 
   // Continuations with more than one use are replaced with Tree labels.  This
   // is the mapping from continuations to labels.
   final Map<ir.Continuation, Label> labels = <ir.Continuation, Label>{};
 
   FunctionDefinition function;
   ir.Continuation returnContinuation;
 
+  /// Variable used in [buildPhiAssignments] as a temporary when swapping
+  /// variables.
+  final Variable tempVar = new Variable(null);
+
   Builder(this.compiler);
 
+  /// Obtains the variable representing the given primitive. Returns null for
+  /// primitives that have no reference and do not need a variable.
+  Variable getVariable(ir.Primitive primitive) {
+    if (primitive.registerIndex == null) {
+      return null; // variable is unused
+    }
+    List<Variable> variables = element2variables[primitive.element];
+    if (variables == null) {
+      variables = <Variable>[];
+      element2variables[primitive.element] = variables;
+    }
+    while (variables.length <= primitive.registerIndex) {
+      variables.add(new Variable(primitive.element));
+    }
+    return variables[primitive.registerIndex];
+  }
+
+  /// Obtains a reference to the tree Variable corresponding to the IR primitive
+  /// referred to by [reference].
+  /// This increments the reference count for the given variable, so the
+  /// returned expression must be used in the tree.
+  Expression getVariableReference(ir.Reference reference) {
+    Variable variable = getVariable(reference.definition);
+    if (variable == null) {
+      compiler.internalError(
+          compiler.currentElement,
+          "Reference to ${reference.definition} has no register");
+    }
+    ++variable.readCount;
+    return variable;
+  }
+
   FunctionDefinition build(ir.FunctionDefinition node) {
+    new ir.RegisterAllocator().visit(node);
     visit(node);
     return function;
   }
 
   List<Expression> translateArguments(List<ir.Reference> args) {
     return new List<Expression>.generate(args.length,
-         (int index) => variables[args[index].definition]);
+         (int index) => getVariableReference(args[index]));
   }
 
-  Statement buildParameterAssignments(
+  List<Variable> translatePhiArguments(List<ir.Reference> args) {
+    return new List<Variable>.generate(args.length,
+         (int index) => getVariableReference(args[index]));
+  }
+
+  Statement buildContinuationAssignment(
+      ir.Parameter parameter,
+      Expression argument,
+      Statement buildRest()) {
+    Variable variable = getVariable(parameter);
+    Statement assignment;
+    if (variable == null) {
+      assignment = new ExpressionStatement(argument, null);
+    } else {
+      assignment = new Assign(variable, argument, null);
+    }
+    assignment.next = buildRest();
+    return assignment;
+  }
+
+  /// Simultaneously assigns each argument to the corresponding parameter,
+  /// then continues at the statement created by [buildRest].
+  Statement buildPhiAssignments(
       List<ir.Parameter> parameters,
-      List<Expression> arguments,
+      List<Variable> arguments,
       Statement buildRest()) {
     assert(parameters.length == arguments.length);
+    // We want a parallel assignment to all parameters simultaneously.
+    // Since we do not have parallel assignments in dart_tree, we must linearize
+    // the assignments without attempting to read a previously-overwritten
+    // value. For example {x,y = y,x} cannot be linearized to {x = y; y = x},
+    // for this we must introduce a temporary variable: {t = x; x = y; y = t}.
+
+    // [rightHand] is the inverse of [arguments], that is, it maps variables
+    // to the assignments on which is occurs as the right-hand side.
+    Map<Variable, List<int>> rightHand = <Variable, List<int>>{};
+    for (int i = 0; i < parameters.length; i++) {
+      Variable param = getVariable(parameters[i]);
+      Variable arg = arguments[i];
+      if (param == null || param == arg) {
+        continue; // No assignment necessary.
+      }
+      List<int> list = rightHand[arg];
+      if (list == null) {
+        rightHand[arg] = list = <int>[];
+      }
+      list.add(i);
+    }
+
     Statement first, current;
-    for (int i = 0; i < parameters.length; ++i) {
-      ir.Parameter parameter = parameters[i];
-      Statement assignment;
-      if (parameter.hasAtLeastOneUse) {
-        assignment = new Assign(variables[parameter], arguments[i], null,
-            parameter.hasExactlyOneUse);
+    void addAssignment(Variable dst, Variable src) {
+      if (first == null) {
+        first = current = new Assign(dst, src, null);
       } else {
-        assignment = new ExpressionStatement(arguments[i], null);
-      }
-
-      if (first == null) {
-        current = first = assignment;
-      } else {
-        current = current.next = assignment;
+        current = current.next = new Assign(dst, src, null);
       }
     }
 
+    List<Variable> assignmentSrc = new List<Variable>(parameters.length);
+    List<bool> done = new List<bool>(parameters.length);
+    void visitAssignment(int i) {
+      if (done[i] == true) {
+        return;
+      }
+      Variable param = getVariable(parameters[i]);
+      Variable arg = arguments[i];
+      if (param == null || param == arg) {
+        return; // No assignment necessary.
+      }
+      if (assignmentSrc[i] != null) {
+        // Cycle found; store argument in a temporary variable.
+        // The temporary will then be used as right-hand side when the
+        // assignment gets added.
+        if (assignmentSrc[i] != tempVar) { // Only move to temporary once.
+          assignmentSrc[i] = tempVar;
+          addAssignment(tempVar, arg);
+        }
+        return;
+      }
+      assignmentSrc[i] = arg;
+      List<int> paramUses = rightHand[param];
+      if (paramUses != null) {
+        for (int useIndex in paramUses) {
+          visitAssignment(useIndex);
+        }
+      }
+      addAssignment(param, assignmentSrc[i]);
+      done[i] = true;
+    }
+
+    for (int i = 0; i < parameters.length; i++) {
+      if (done[i] == null) {
+        visitAssignment(i);
+      }
+    }
+
     if (first == null) {
       first = buildRest();
     } else {
       current.next = buildRest();
     }
     return first;
   }
 
   Expression visitFunctionDefinition(ir.FunctionDefinition node) {
     returnContinuation = node.returnContinuation;
     List<Variable> parameters = <Variable>[];
     for (ir.Parameter p in node.parameters) {
-      Variable parameter = new Variable(p.element);
+      Variable parameter = getVariable(p);
+      assert(parameter != null);
       parameters.add(parameter);
-      variables[p] = parameter;
     }
     function = new FunctionDefinition(parameters, visit(node.body));
     return null;
   }
 
   Statement visitLetPrim(ir.LetPrim node) {
-    // LetPrim is translated to LetVal.
+    // LetPrim is translated to Assign.
     Expression definition = visit(node.primitive);
-    if (node.primitive.hasAtLeastOneUse) {
-      Variable variable = new Variable(null);
-      variables[node.primitive] = variable;
-      return new Assign(variable, definition, visit(node.body),
-          node.primitive.hasExactlyOneUse);
+    Variable variable = getVariable(node.primitive);
+    if (variable != null) { // Variable is null if primitive is unused.
+      return new Assign(variable, definition, visit(node.body));
     } else if (node.primitive is ir.Constant) {
       // TODO(kmillikin): Implement more systematic treatment of pure CPS
       // values (e.g., as part of a shrinking reductions pass).
       return visit(node.body);
     } else {
       return new ExpressionStatement(definition, visit(node.body));
     }
   }
 
   Statement visitLetCont(ir.LetCont node) {
     Label label;
     if (node.continuation.hasMultipleUses) {
       label = new Label();
       labels[node.continuation] = label;
     }
-    node.continuation.parameters.forEach((p) {
-        if (p.hasAtLeastOneUse) variables[p] = new Variable(null);
-    });
     Statement body = visit(node.body);
     // The continuation's body is not always translated directly here because
     // it may have been already translated:
     //   * For singly-used continuations, the continuation's body is
     //     translated at the site of the continuation invocation.
     //   * For recursive continuations, there is a single non-recursive
     //     invocation.  The continuation's body is translated at the site
     //     of the non-recursive continuation invocation.
     // See visitInvokeContinuation for the implementation.
     if (label == null || node.continuation.isRecursive) return body;
     return new LabeledStatement(label, body, visit(node.continuation.body));
   }
 
   Statement visitInvokeStatic(ir.InvokeStatic node) {
     // Calls are translated to direct style.
     List<Expression> arguments = translateArguments(node.arguments);
     Expression invoke = new InvokeStatic(node.target, node.selector, arguments);
     ir.Continuation cont = node.continuation.definition;
     if (cont == returnContinuation) {
       return new Return(invoke);
     } else {
       assert(cont.hasExactlyOneUse);
       assert(cont.parameters.length == 1);
-      return buildParameterAssignments(cont.parameters, [invoke],
+      return buildContinuationAssignment(cont.parameters.single, invoke,
           () => visit(cont.body));
     }
   }
 
   Statement visitInvokeMethod(ir.InvokeMethod node) {
-    Variable receiver = variables[node.receiver.definition];
+    Expression receiver = getVariableReference(node.receiver);
     List<Expression> arguments = translateArguments(node.arguments);
     Expression invoke = new InvokeMethod(receiver, node.selector, arguments);
     ir.Continuation cont = node.continuation.definition;
     if (cont == returnContinuation) {
       return new Return(invoke);
     } else {
       assert(cont.hasExactlyOneUse);
       assert(cont.parameters.length == 1);
-      return buildParameterAssignments(cont.parameters, [invoke],
+      return buildContinuationAssignment(cont.parameters.single, invoke,
           () => visit(cont.body));
     }
   }
 
   Statement visitConcatenateStrings(ir.ConcatenateStrings node) {
     List<Expression> arguments = translateArguments(node.arguments);
     Expression concat = new ConcatenateStrings(arguments);
     ir.Continuation cont = node.continuation.definition;
     if (cont == returnContinuation) {
       return new Return(concat);
     } else {
       assert(cont.hasExactlyOneUse);
       assert(cont.parameters.length == 1);
-      return buildParameterAssignments(cont.parameters, [concat],
+      return buildContinuationAssignment(cont.parameters.single, concat,
           () => visit(cont.body));
     }
   }
 
   Statement visitInvokeConstructor(ir.InvokeConstructor node) {
     List<Expression> arguments = translateArguments(node.arguments);
     Expression invoke =
         new InvokeConstructor(node.type, node.target, node.selector, arguments);
     ir.Continuation cont = node.continuation.definition;
     if (cont == returnContinuation) {
       return new Return(invoke);
     } else {
       assert(cont.hasExactlyOneUse);
       assert(cont.parameters.length == 1);
-      return buildParameterAssignments(cont.parameters, [invoke],
+      return buildContinuationAssignment(cont.parameters.single, invoke,
           () => visit(cont.body));
     }
   }
 
   Statement visitInvokeContinuation(ir.InvokeContinuation node) {
     // Invocations of the return continuation are translated to returns.
     // Other continuation invocations are replaced with assignments of the
     // arguments to formal parameter variables, followed by the body if
     // the continuation is singly reference or a break if it is multiply
     // referenced.
     ir.Continuation cont = node.continuation.definition;
     if (cont == returnContinuation) {
       assert(node.arguments.length == 1);
-      return new Return(variables[node.arguments[0].definition]);
+      return new Return(getVariableReference(node.arguments.single));
     } else {
-      List<Expression> arguments = translateArguments(node.arguments);
-      return buildParameterAssignments(cont.parameters, arguments,
+      List<Expression> arguments = translatePhiArguments(node.arguments);
+      return buildPhiAssignments(cont.parameters, arguments,
           () {
             // Translate invocations of recursive and non-recursive
             // continuations differently.
             //   * Non-recursive continuations
             //     - If there is one use, translate the continuation body
             //       inline at the invocation site.
             //     - If there are multiple uses, translate to Break.
             //   * Recursive continuations
             //     - There is a single non-recursive invocation.  Translate
             //       the continuation body inline as a labeled loop at the
@@ skipping 53 matching lines @@
   }
 
   Expression visitContinuation(ir.Continuation node) {
     // Until continuations with multiple uses are supported, they are not
     // visited.
     compiler.internalError(compiler.currentElement, 'Unexpected IR node.');
     return null;
   }
 
   Expression visitIsTrue(ir.IsTrue node) {
-    return variables[node.value.definition];
+    return getVariableReference(node.value);
   }
 }
 
 /**
  * Performs the following transformations on the tree:
  * - Assignment propagation
  * - If-to-conditional conversion
  * - Flatten nested ifs
  * - Break inlining
  * - Redirect breaks
@@ skipping 240 matching lines @@
       return result;
     }
 
     node.body = visitStatement(node.body);
 
     if (node.label.useCount == 0) {
       // Eliminate the label if next was inlined at a break
       return node.body;
     }
 
+    // Do not propagate assignments into the successor statements, since they
+    // may be overwritten by assignments in the body.
+    List<Assign> savedEnvironment = environment;
+    environment = <Assign>[];
     node.next = visitStatement(node.next);
+    environment = savedEnvironment;
+
     return node;
   }
 
   Statement visitIf(If node) {
     node.condition = visitExpression(node.condition);
 
     // Do not propagate assignments into branches.  Doing so will lead to code
     // duplication.
     // TODO(kmillikin): Rethink this.  Propagating some assignments (e.g.,
     // constants or variables) is benign.  If they can occur here, they should
@@ skipping 97 matching lines @@
       Statement t,
       Expression combine(Expression s, Expression t)) {
     if (s is Return && t is Return) {
       return new Return(combine(s.value, t.value));
     }
     if (s is Assign && t is Assign && s.variable == t.variable) {
       Statement next = combineStatements(s.next, t.next);
       if (next != null) {
         return new Assign(s.variable,
                           combine(s.definition, t.definition),
-                          next,
-                          s.hasExactlyOneUse);
+                          next);
       }
     }
     if (s is ExpressionStatement && t is ExpressionStatement) {
       Statement next = combineStatements(s.next, t.next);
       if (next != null) {
         return new ExpressionStatement(combine(s.expression, t.expression),
                                        next);
       }
     }
     return null;
   }
 
   /// Returns a statement equivalent to both [s] and [t], or null if [s] and
   /// [t] are incompatible.
   /// If non-null is returned, the caller MUST discard [s] and [t] and use
   /// the returned statement instead.
   /// If two breaks are combined, the label's break counter will be decremented.
   static Statement combineStatements(Statement s, Statement t) {
     if (s is Break && t is Break && s.target == t.target) {
       --t.target.useCount; // Two breaks become one.
       return s;
     }
     if (s is Continue && t is Continue && s.target == t.target) {
       --t.target.useCount; // Two continues become one.
       return s;
     }
-    if (s is Return && t is Return && equivalentExpressions(s.value, t.value)) {
-      return s;
+    if (s is Return && t is Return) {
+      Expression e = combineExpressions(s.value, t.value);
+      if (e != null) {
+        return new Return(e);
+      }
     }
     return null;
   }
 
-  /// True if the two expressions both syntactically and semantically
-  /// equivalent.
-  static bool equivalentExpressions(Expression e1, Expression e2) {
-    if (e1 == e2) { // Detect same variable reference
-      // TODO(asgerf): This might turn the variable into a single-use,
-      // but we currently don't discover this.
-      return true;
+  /// Returns an expression equivalent to both [e1] and [e2].
+  /// If non-null is returned, the caller must discard [e1] and [e2] and use
+  /// the resulting expression in the tree.
+  static Expression combineExpressions(Expression e1, Expression e2) {
+    if (e1 is Variable && e1 == e2) {
+      --e1.readCount; // Two references become one.
+      return e1;
     }
-    if (e1 is Constant && e2 is Constant) {
-      return e1.value == e2.value;
+    if (e1 is Constant && e2 is Constant && e1.value == e2.value) {
+      return e1;
     }
-    return false;
+    return null;
   }
 
   /// Try to collapse nested ifs using && and || expressions.
   /// For example:
   ///
   ///   if (E1) { if (E2) S else break L } else break L
   ///     ==>
   ///   if (E1 && E2) S else break L
   ///
   /// [branch1] and [branch2] control the position of the S statement.
@@ skipping 605 matching lines @@
     }
   }
 
   /// Destructively updates each entry of [l] with the result of visiting it.
   void _rewriteList(List<Expression> l) {
     for (int i = 0; i < l.length; i++) {
       l[i] = visitExpression(l[i]);
     }
   }
 }