cps-ir: Merge variables based on the source variable's name.

pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart

 // Copyright (c) 2015, 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.optimization.variable_merger;
 
 import 'optimization.dart' show Pass;
 import '../tree_ir_nodes.dart';
 import '../../elements/elements.dart' show Local, ParameterElement;
 
@@ skipping 16 matching lines @@
   }
 
   /// Rewrites the given function.
   /// This is called for the outermost function and inner functions.
   void rewriteFunction(RootNode node) {
     node.forEachBody((Statement body) {
       BlockGraphBuilder builder = new BlockGraphBuilder();
       builder.build(node.parameters, body);
       _computeLiveness(builder.blocks);
       Map<Variable, Variable> subst =
-          _computeRegisterAllocation(builder.blocks);
+          _computeRegisterAllocation(builder.blocks, node.parameters);
       new SubstituteVariables(subst).apply(node);
     });
   }
 }
 
 /// A read or write access to a variable.
 class VariableAccess {
   Variable variable;
   bool isRead;
   bool get isWrite => !isRead;
@@ skipping 300 matching lines @@
 ///
 /// Constructs a register interference graph. This is an undirected graph of
 /// variables, with an edge between two variables if they cannot be merged
 /// (because they are live simultaneously).
 ///
 /// We then compute a graph coloring, where the color of a node denotes which
 /// variable it will be substituted by.
 ///
 /// We never merge variables that originated from distinct source variables,
 /// so we build a separate register interference graph for each source variable.
-Map<Variable, Variable> _computeRegisterAllocation(List<Block> blocks) {
+Map<Variable, Variable> _computeRegisterAllocation(List<Block> blocks,
+                                                   List<Variable> parameters) {
   Map<Variable, Set<Variable>> interference = <Variable, Set<Variable>>{};
 
   /// Group for the given variable. We attempt to merge variables in the same
   /// group.
-  /// By default, variables are grouped based on their source variable, but
-  /// this can be disabled for testing purposes.
-  Local group(Variable variable) {
-    if (NO_PRESERVE_VARS) {
-      // Parameters may not occur more than once in a parameter list,
-      // so except for parameters, we try to merge all variables.
-      return variable.element is ParameterElement ? variable.element : null;
-    }
-    return variable.element;
+  /// By default, variables are grouped based on their source variable name,
+  /// but this can be disabled for testing purposes.
+  String group(Variable variable) {
+    if (NO_PRESERVE_VARS) return '';
+    // Group variables based on the source variable's name, not its element,
+    // so if multiple locals are declared with the same name, they will
+    // map to the same (hoisted) variable in the output.
+    return variable.element == null ? '' : variable.element.name;
   }
 
   Set<Variable> empty = new Set<Variable>();
 
   // At the assignment to a variable x, add an edge to every variable that is
   // live after the assignment (if it came from the same source variable).
   for (Block block in blocks) {
     // Group the liveOut set by source variable.
-    Map<Local, Set<Variable>> liveOut = <Local, Set<Variable>>{};
+    Map<String, Set<Variable>> liveOut = <String, Set<Variable>>{};
     for (Variable variable in block.liveOut) {
       liveOut.putIfAbsent(
           group(variable),
           () => new Set<Variable>()).add(variable);
       interference.putIfAbsent(variable, () => new Set<Variable>());
     }
     // Get variables that are live at the catch block.
     Set<Variable> liveCatch = block.catchBlock != null
         ? block.catchBlock.liveIn
         : empty;
@@ skipping 16 matching lines @@
         }
       }
     }
   }
 
   // Sort the variables by descending degree.
   // The most constrained variables will be assigned a color first.
   List<Variable> variables = interference.keys.toList();
   variables.sort((x, y) => interference[y].length - interference[x].length);
 
-  Map<Local, List<Variable>> registers = <Local, List<Variable>>{};
+  Map<String, List<Variable>> registers = <String, List<Variable>>{};
   Map<Variable, Variable> subst = <Variable, Variable>{};
 
+  // Parameters are special in that they must have a ParameterElement and
+  // cannot be merged with each other. Ensure that they are not substituted.
+  // Other variables can still be substituted by a parameter.
+  for (Variable parameter in parameters) {
+    subst[parameter] = parameter;
+    registers[group(parameter)] = <Variable>[parameter];
+  }
+
   for (Variable v1 in variables) {
+    // Parameters have already been assigned a substitute; skip those.
+    if (subst.containsKey(v1)) continue;
+
     List<Variable> register = registers[group(v1)];
 
     // Optimization: For the first variable in a group, allocate a new color
     // without iterating over its interference edges.
     if (register == null) {
       registers[group(v1)] = <Variable>[v1];
       subst[v1] = v1;
       continue;
     }
 
@@ skipping 98 matching lines @@
     // VariableDeclaration is only used for captured variables, which are never
     // merged, so this is not strictly necessary. But it's nicer if this class
     // works for arbitrary substitution maps.
     node.variable = replaceWrite(node.variable);
     node.value = visitExpression(node.value);
     node.next = visitStatement(node.next);
     return node;
   }
 
 }