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 =

[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
   // 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 12 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.
   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) {
       return buildConstructor(node);
     } else {
       assert(dart2js.invariant(
           CURRENT_ELEMENT_SPANNABLE,
           node is cps_ir.FunctionDefinition,
           message: 'expected FunctionDefinition or FieldDefinition, '
             ' found $node'));
@@ skipping 76 matching lines @@
   List<Variable> translatePhiArguments(List<cps_ir.Reference> args) {
     return new List<Variable>.generate(args.length,
          (int index) => getVariable(args[index].definition),
          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<Variable> arguments,
@@ skipping 392 matching lines @@
   }
 
   Expression visitReifyRuntimeType(cps_ir.ReifyRuntimeType node) {
     return new ReifyRuntimeType(getVariableUse(node.value));
   }
 
   Expression visitReadTypeVariable(cps_ir.ReadTypeVariable node) {
     return new ReadTypeVariable(node.variable, getVariableUse(node.target));
   }
 }
+