cps-ir: Merge variables based on set-based liveness and graph coloring.

pkg/compiler/lib/src/tree_ir/tree_ir_builder.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 tree_ir_builder;
 
 import '../dart2jslib.dart' as dart2js;
 import '../dart_types.dart';
 import '../elements/elements.dart';
 import '../cps_ir/cps_ir_nodes.dart' as cps_ir;
@@ skipping 28 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 implements cps_ir.Visitor<Node> {
   final dart2js.InternalErrorFunction internalError;
 
-  /// Maps variable/parameter elements to the Tree variables that represent it.
-  final Map<Local, List<Variable>> local2variables = <Local, List<Variable>>{};
-
-  /// Like [local2variables], except for mutable variables.
-  final Map<cps_ir.MutableVariable, Variable> local2mutable =
+  final Map<cps_ir.Primitive, Variable> primitive2variable =
+      <cps_ir.Primitive, Variable>{};
+  final Map<cps_ir.MutableVariable, Variable> mutable2variable =
       <cps_ir.MutableVariable, Variable>{};
 
   // Continuations with more than one use are replaced with Tree labels.  This
   // is the mapping from continuations to labels.
   final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{};
 
   /// A stack of singly-used labels that can be safely inlined at their use
   /// site.
   ///
   /// Code for continuations with exactly one use is inlined at the use site.
@@ skipping 14 matching lines @@
   Builder createInnerBuilder() {
     return new Builder(internalError, this);
   }
 
   /// Variable used in [buildPhiAssignments] as a temporary when swapping
   /// variables.
   Variable phiTempVar;
 
   Variable addMutableVariable(cps_ir.MutableVariable irVariable) {
     assert(irVariable.host == currentElement);
-    assert(!local2mutable.containsKey(irVariable));
+    assert(!mutable2variable.containsKey(irVariable));
     Variable variable = new Variable(currentElement, irVariable.hint);
-    local2mutable[irVariable] = variable;
+    mutable2variable[irVariable] = variable;
     return variable;
   }
 
   Variable getMutableVariable(cps_ir.MutableVariable mutableVariable) {
     if (mutableVariable.host != currentElement) {
       return parent.getMutableVariable(mutableVariable)..isCaptured = true;
     }
-    return local2mutable[mutableVariable];
+    return mutable2variable[mutableVariable];
   }
 
   VariableUse getMutableVariableUse(
         cps_ir.Reference<cps_ir.MutableVariable> reference) {
     Variable variable = getMutableVariable(reference.definition);
     return new VariableUse(variable);
   }
 
   /// Obtains the variable representing the given primitive. Returns null for
   /// primitives that have no reference and do not need a variable.
   Variable getVariable(cps_ir.Primitive primitive) {
-    if (primitive.registerIndex == null) {
-      return null; // variable is unused
-    }
-    List<Variable> variables = local2variables.putIfAbsent(primitive.hint,
-        () => <Variable>[]);
-    while (variables.length <= primitive.registerIndex) {
-      variables.add(new Variable(currentElement, primitive.hint));
-    }
-    return variables[primitive.registerIndex];
+    return primitive2variable.putIfAbsent(primitive,
+        () => new Variable(currentElement, primitive.hint));
   }
 
   /// 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 getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) {
     if (thisParameter != null && reference.definition == thisParameter) {
       return new This();
     }
-    Variable variable = getVariable(reference.definition);
-    if (variable == null) {
-      // Note: this may fail because you forgot to implement a visit-function
-      // in the RegisterAllocator.
-      internalError(
-          CURRENT_ELEMENT_SPANNABLE,
-          "Reference to ${reference.definition} has no register");
-    }
-    return new VariableUse(variable);
+    return new VariableUse(getVariable(reference.definition));
   }
 
   ExecutableDefinition build(cps_ir.ExecutableDefinition node) {
+    // TODO(asgerf): Don't have build AND buildXXX as public API.
     if (node is cps_ir.FieldDefinition) {
       return buildField(node);
     } else if (node is cps_ir.ConstructorDefinition) {
       return buildConstructor(node);
     } else {
       assert(dart2js.invariant(
           CURRENT_ELEMENT_SPANNABLE,
           node is cps_ir.FunctionDefinition,
           message: 'expected FunctionDefinition or FieldDefinition, '
             ' found $node'));
@@ skipping 72 matching lines @@
   List<Expression> translateArguments(List<cps_ir.Reference> args) {
     return new List<Expression>.generate(args.length,
          (int index) => getVariableUse(args[index]),
          growable: false);
   }
 
   Statement buildContinuationAssignment(
       cps_ir.Parameter parameter,
       Expression argument,
       Statement buildRest()) {
-    Variable variable = getVariable(parameter);
     Statement assignment;
-    if (variable == null) {
+    if (parameter.hasAtLeastOneUse) {
+      Variable variable = getVariable(parameter);
+      assignment = new Assign(variable, argument, null);
+    } else {
       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<cps_ir.Parameter> parameters,
       List<Expression> arguments,
@@ skipping 406 matching lines @@
     return new ReadTypeVariable(node.variable, getVariableUse(node.target));
   }
 
   @override
   Node visitTypeExpression(cps_ir.TypeExpression node) {
     return new TypeExpression(
         node.dartType,
         node.arguments.map(getVariableUse).toList());
   }
 }
+