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

pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart

Index: pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
diff --git a/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart b/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
index a1157813afb2d347afc99f3d2e1622580e4d7b3e..d8742d1b0ff4018deefa9641a9b498e7ffb60984 100644
--- a/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
+++ b/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
@@ -46,11 +46,9 @@ import 'tree_ir_nodes.dart';
 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
@@ -85,9 +83,9 @@ class Builder implements cps_ir.Visitor<Node> {
 
   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;
   }
 
@@ -95,7 +93,7 @@ class Builder implements cps_ir.Visitor<Node> {
     if (mutableVariable.host != currentElement) {
       return parent.getMutableVariable(mutableVariable)..isCaptured = true;
     }
-    return local2mutable[mutableVariable];
+    return mutable2variable[mutableVariable];
   }
 
   VariableUse getMutableVariableUse(
@@ -107,15 +105,8 @@ class Builder implements cps_ir.Visitor<Node> {
   /// 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
@@ -126,18 +117,11 @@ class Builder implements cps_ir.Visitor<Node> {
     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) {
@@ -230,12 +214,12 @@ class Builder implements cps_ir.Visitor<Node> {
       cps_ir.Parameter parameter,
       Expression argument,
       Statement buildRest()) {
-    Variable variable = getVariable(parameter);
     Statement assignment;
-    if (variable == null) {
-      assignment = new ExpressionStatement(argument, null);
-    } else {
+    if (parameter.hasAtLeastOneUse) {
+      Variable variable = getVariable(parameter);
       assignment = new Assign(variable, argument, null);
+    } else {
+      assignment = new ExpressionStatement(argument, null);
     }
     assignment.next = buildRest();
     return assignment;
@@ -662,3 +646,4 @@ class Builder implements cps_ir.Visitor<Node> {
         node.arguments.map(getVariableUse).toList());
   }
 }
+