dart2js cps: Introduce some built-in operators in type propagation.

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 27638c40409bb44c24ab51d8054a0529a0fad51f..e7a888b8c357a3d90e4f81a8d63d56fd11b94c67 100644
--- a/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart
+++ b/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart
@@ -264,6 +264,25 @@ class StatementRewriter extends Transformer implements Pass {
     return node;
   }
 
+  /// True if [exp] contains a use of a variable that was assigned to by the

[Kevin Millikin (Google), 2015/06/12 12:19:10]

"a variable" ==> "the variable" seems more clear.  Also, you mean that the
right-hand side of the assignment was impure (not the assignment itself)?

[asgerf, 2015/06/15 09:26:18]

Not all expressions assign to a variable, so "the" variable is also a bit
misleading.

And yes, for assignments, I mean the right-hand side. I've extended the comment
to clarify.

I also updated the comment on the environment field to indicate that it does not
contain constant assignments.

+  /// most recently evaluated impure expression.
+  ///
+  /// This implies that the assignment can be propagated into this use unless
+  /// the use is moved further away.
+  ///
+  /// In this case, we will refrain from moving [exp] across other impure
+  /// expressions, even when this is safe, because doing so would immediately
+  /// prevent the previous expression from propagating, canceling out the
+  /// benefit we might otherwise gain from propagating [exp].
+  bool usesRecentlyAssignedVariable(Expression exp) {
+    if (environment.isEmpty) return false;
+    Variable variable = getLeftHand(environment.last);
+    if (variable == null) return false;
+    IsVariableUsedVisitor visitor = new IsVariableUsedVisitor(variable);
+    visitor.visitExpression(exp);
+    return visitor.wasFound;
+  }
+
   /// Returns true if [exp] has no side effects and has a constant value within
   /// any given activation of the enclosing method.
   bool isEffectivelyConstant(Expression exp) {
@@ -274,6 +293,7 @@ class StatementRewriter extends Transformer implements Pass {
            exp is This ||
            exp is CreateInvocationMirror ||
            exp is InvokeStatic && exp.isEffectivelyConstant ||
+           exp is ApplyBuiltinOperator ||
            exp is VariableUse && constantEnvironment.containsKey(exp.variable);
   }
 
@@ -285,7 +305,8 @@ class StatementRewriter extends Transformer implements Pass {
   }
 
   Statement visitExpressionStatement(ExpressionStatement stmt) {
-    if (isEffectivelyConstantAssignment(stmt.expression)) {
+    if (isEffectivelyConstantAssignment(stmt.expression) &&
+        !usesRecentlyAssignedVariable(stmt.expression)) {
       Assign assign = stmt.expression;
       // Handle constant assignments specially.
       // They are always safe to propagate (though we should avoid duplication).
@@ -619,6 +640,80 @@ class StatementRewriter extends Transformer implements Pass {
     return node;
   }
 
+  /// True if [operator] is a binary operator that always has the same value
+  /// if its arguments are swapped.
+  bool isSymmetricOperator(BuiltinOperator operator) {
+    switch (operator) {
+      case BuiltinOperator.StrictEq:
+      case BuiltinOperator.StrictNeq:
+      case BuiltinOperator.LooseEq:
+      case BuiltinOperator.LooseNeq:
+      case BuiltinOperator.NumAnd:
+      case BuiltinOperator.NumOr:
+      case BuiltinOperator.NumXor:
+      case BuiltinOperator.NumAdd:
+      case BuiltinOperator.NumMultiply:
+        return true;
+      default:
+        return false;
+    }
+  }
+
+  /// If [operator] is a commutable binary operator, returns the commuted
+  /// operator, possibly the operator itself, otherwise returns `null`.
+  BuiltinOperator commuteBinaryOperator(BuiltinOperator operator) {
+    if (isSymmetricOperator(operator)) {
+      // Symmetric operators are their own commutes.
+      return operator;
+    }
+    switch(operator) {
+      case BuiltinOperator.NumLt: return BuiltinOperator.NumGt;
+      case BuiltinOperator.NumLe: return BuiltinOperator.NumGe;
+      case BuiltinOperator.NumGt: return BuiltinOperator.NumLt;
+      case BuiltinOperator.NumGe: return BuiltinOperator.NumLe;
+      default: return null;
+    }
+  }
+
+  /// Built-in binary operators are commuted when it is safe and can enable an
+  /// assignment propagation. For example:
+  ///
+  ///    var x = foo();
+  ///    var y = bar();
+  ///    var z = y < x;
+  ///
+  ///      ==>
+  ///
+  ///    var z = foo() > bar();
+  ///
+  /// foo() must be evaluated before bar(), so the propagation is only possible
+  /// by commuting the operator.
+  Expression visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
+    if (environment.isEmpty || getLeftHand(environment.last) == null) {
+      // If there is no recent assignment that might propagate, so there is no
+      // opportunity for optimization here.
+      _rewriteList(node.arguments);
+      return node;
+    }
+    Variable propagatableVariable = getLeftHand(environment.last);
+    BuiltinOperator commuted = commuteBinaryOperator(node.operator);
+    if (commuted != null) {
+      assert(node.arguments.length == 2); // Only binary operators can commute.
+      VariableUse arg1 = node.arguments[0];
+      VariableUse arg2 = node.arguments[1];
+      if (propagatableVariable == arg1.variable &&
+          propagatableVariable != arg2.variable &&
+          !constantEnvironment.containsKey(arg2.variable)) {
+        // An assignment can be propagated if we commute the operator.
+        node.operator = commuted;
+        node.arguments[0] = arg2;
+        node.arguments[1] = arg1;
+      }
+    }
+    _rewriteList(node.arguments);
+    return node;
+  }
+
   /// If [s] and [t] are similar statements we extract their subexpressions
   /// and returns a new statement of the same type using expressions combined
   /// with the [combine] callback. For example:
@@ -923,3 +1018,23 @@ class GenericCombinedExpressions implements CombinedExpressions {
 
   void uncombine() {}
 }
+
+/// Looks for uses of a specific variable.
+///
+/// Note that this visitor is only applied to expressions where all

[Kevin Millikin (Google), 2015/06/12 12:19:10]

You might mention this as well (that it's cheap) at the use of this
visitor---I'd probably wonder about it when I saw the use, not the definition,
and I don't want to have to scroll down to find out :)

[asgerf, 2015/06/15 09:26:18]

Added another comment at the use-site to clarify.

+/// sub-expressions are known to be variable uses, so there is no risk of
+/// explosive reprocessing.
+class IsVariableUsedVisitor extends RecursiveVisitor {
+  Variable variable;
+  bool wasFound = false;
+
+  IsVariableUsedVisitor(this.variable);
+
+  visitVariableUse(VariableUse node) {
+    if (node.variable == variable) {
+      wasFound = true;
+    }
+  }
+
+  visitInnerFunction(FunctionDefinition node) {}
+}