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

pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.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.
 
 part of tree_ir.optimization;
 
 /**
  * Performs the following transformations on the tree:
  * - Assignment propagation
  * - If-to-conditional conversion
@@ skipping 377 matching lines @@
       node.elseStatement = visitStatement(node.elseStatement);
     });
 
     tryCollapseIf(node);
 
     Statement reduced = combineStatementsWithSubexpressions(
         node.thenStatement,
         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);
-      }
-      return reduced;
+      // TODO(asgerf): Avoid revisiting nodes or visiting nodes that we created.
+      //               This breaks the assumption that all subexpressions are
+      //               variable uses, and it can be expensive.
+      // Revisit in case the break can now be inlined.
+      return visitStatement(reduced);
     }
 
     return node;
   }
 
   Statement visitWhileTrue(WhileTrue node) {
     // Do not propagate assignments into loops.  Doing so is not safe for
     // variables modified in the loop (the initial value will be propagated).
     inEmptyEnvironment(() {
       node.body = visitStatement(node.body);
@@ skipping 154 matching lines @@
     if (s is Continue && t is Continue && s.target == t.target) {
       --t.target.useCount; // Two continues become one.
       return s;
     }
     if (s is Return && t is Return) {
       Expression e = combineExpressions(s.value, t.value);
       if (e != null) {
         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;
   }
 
   /// Returns an expression equivalent to both [e1] and [e2].
   /// If non-null is returned, the caller must discard [e1] and [e2] and use
   /// the resulting expression in the tree.
   static Expression combineExpressions(Expression e1, Expression e2) {
     if (e1 is VariableUse && e2 is VariableUse && e1.variable == e2.variable) {
       --e1.variable.readCount; // Two references become one.
       return e1;
@@ skipping 50 matching lines @@
       if (tryCollapseIfAux(node, false, false)) {
         changed = true;
       }
     }
   }
 
   bool tryCollapseIfAux(If outerIf, bool branch1, bool branch2) {
     // 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);
   }
 
   Statement getBranch(If node, bool polarity) {
     return polarity ? node.thenStatement : node.elseStatement;
   }
 }