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 8017ba65f47139a2866f32c6084ffe7b5592055c..22126ab4d74c9bb979d7317dc717f3f21d0d3a8d 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 =

[Kevin Millikin (Google), 2015/03/20 11:12:03]

I don't really like this naming convention.  At the use site you normally want
to read this like a function from the key to the value.  There you normally
already know the type of the key so putting it in the name is redundant.  And
you'd rather know the interpretation of the value, not just its type.

As a concrete suggestion: primitive2varible => variables (or treeVariables) and
mutable2variable => mutableVariables (or mutableTreeVariables) though I'm not
sure if that's the best we can come up with.

[asgerf, 2015/03/31 12:14:19]

I don't think of it as the type of the key. We map variables in the input
language to variables in the output language, but since we have two kinds of
input variables (primitives and mutables), we need two maps and it seems natural
to name them accordingly.

We could also have a single map:

    Map<cps.Definition, Variable> variables;

That would work for me.

+      <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
@@ -83,9 +81,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;
   }
 
@@ -93,7 +91,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(
@@ -105,15 +103,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
@@ -121,18 +112,11 @@ class Builder implements cps_ir.Visitor<Node> {
   /// This increments the reference count for the given variable, so the
   /// returned expression must be used in the tree.
   VariableUse getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) {
-    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) {
@@ -229,12 +213,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;
@@ -647,3 +631,4 @@ class Builder implements cps_ir.Visitor<Node> {
     return new ReadTypeVariable(node.variable, getVariableUse(node.target));
   }
 }
+