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

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

Index: pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart
diff --git a/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart b/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart
index 40c7cacafc8993d147ab68a4fa9e78413df9b017..f3566df587f141b212b75a81aa3504b02c722569 100644
--- a/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart
+++ b/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart
@@ -395,10 +395,10 @@ class StatementRewriter extends Visitor<Statement, Expression> with PassMixin {
         node.elseStatement,
         (t,f) => new Conditional(node.condition, t, f)..processed = true);
     if (reduced != null) {
-      if (reduced.next is Break) {
-        // In case the break can now be inlined.
-        reduced = visitStatement(reduced);
-      }
+      // TODO(asgerf): Avoid quadratic cost from repeated processing. This
+      //               should be easier after we introduce basic blocks.
+      // In case the break can now be inlined.
+      reduced = visitStatement(reduced);

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

I like tail calls, just return visitStatement(reduced);.

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

Done.

       return reduced;
     }
 
@@ -574,6 +574,17 @@ class StatementRewriter extends Visitor<Statement, Expression> with PassMixin {
         return new Return(e);
       }
     }
+    if (s is Assign && t is Assign &&
+        s.variable == t.variable &&
+        isSameVariable(s.value, t.value)) {
+      Statement next = combineStatements(s.next, t.next);
+      if (next != null) {
+        s.next = next;
+        --t.variable.writeCount;
+        --(t.value as VariableUse).variable.readCount;
+        return s;
+      }
+    }
     return null;
   }
 
@@ -644,30 +655,36 @@ class StatementRewriter extends Visitor<Statement, Expression> with PassMixin {
     // NOTE: We name variables here as if S is in the then-then position.
     Statement outerThen = getBranch(outerIf, branch1);
     Statement outerElse = getBranch(outerIf, !branch1);
-    if (outerThen is If && outerElse is Break) {
+    if (outerThen is If) {
       If innerIf = outerThen;
       Statement innerThen = getBranch(innerIf, branch2);
       Statement innerElse = getBranch(innerIf, !branch2);
-      if (innerElse is Break && innerElse.target == outerElse.target) {
+      Statement combinedElse = combineStatements(innerElse, outerElse);
+      if (combinedElse != null) {
         // We always put S in the then branch of the result, and adjust the
         // condition expression if S was actually found in the else branch(es).
         outerIf.condition = new LogicalOperator.and(
             makeCondition(outerIf.condition, branch1),
             makeCondition(innerIf.condition, branch2));
         outerIf.thenStatement = innerThen;
-        --innerElse.target.useCount;
 
         // Try to inline the remaining break.  Do not propagate assignments.
         inEmptyEnvironment(() {
-          outerIf.elseStatement = visitStatement(outerElse);
+          // TODO(asgerf): Avoid quadratic cost from repeated processing. This
+          //               should be easier after we introduce basic blocks.
+          outerIf.elseStatement = visitStatement(combinedElse);
         });
 
-        return outerIf.elseStatement is If && innerThen is Break;
+        return outerIf.elseStatement is If;
       }
     }
     return false;
   }
 
+  static bool isSameVariable(Expression e1, Expression e2) {
+    return e1 is VariableUse && e2 is VariableUse && e1.variable == e2.variable;
+  }
+
   Expression makeCondition(Expression e, bool polarity) {
     return polarity ? e : new Not(e);
   }