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

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.
 
 library tree_ir.optimization.statement_rewriter;
 
 import 'optimization.dart' show Pass;
 import '../tree_ir_nodes.dart';
 
 /**
@@ skipping 246 matching lines @@
         environment.removeLast();
         --node.variable.readCount;
         return visitExpression(binding);
       }
     }
 
     // If the definition could not be propagated, leave the variable use.
     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) {
     // TODO(asgerf): Can be made more aggressive e.g. by checking conditional
     // expressions recursively. Determine if that is a valuable optimization
     // and/or if it is better handled at the CPS level.
     return exp is Constant ||
            exp is This ||
            exp is CreateInvocationMirror ||
            exp is InvokeStatic && exp.isEffectivelyConstant ||
+           exp is ApplyBuiltinOperator ||
            exp is VariableUse && constantEnvironment.containsKey(exp.variable);
   }
 
   /// True if [node] is an assignment that can be propagated as a constant.
   bool isEffectivelyConstantAssignment(Expression node) {
     return node is Assign &&
            node.variable.writeCount == 1 &&
            isEffectivelyConstant(node.value);
   }
 
   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).
       // Moreover, they should not prevent other expressions from propagating.
       if (assign.variable.readCount <= 1) {
         // A single-use constant should always be propagted to its use site.
         constantEnvironment[assign.variable] = assign.value;
         --assign.variable.writeCount;
         return visitStatement(stmt.next);
       } else {
@@ skipping 313 matching lines @@
   Expression visitTypeExpression(TypeExpression node) {
     _rewriteList(node.arguments);
     return node;
   }
 
   Expression visitCreateInvocationMirror(CreateInvocationMirror node) {
     _rewriteList(node.arguments);
     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:
   ///
   ///   combineStatements(Return E1, Return E2) = Return combine(E1, E2)
   ///
   /// If [combine] returns E1 then the unified statement is equivalent to [s],
   /// and if [combine] returns E2 the unified statement is equivalence to [t].
   ///
   /// It is guaranteed that no side effects occur between the beginning of the
@@ skipping 284 matching lines @@
 }
 
 /// Result of combining two expressions that do not affect reference counting.
 class GenericCombinedExpressions implements CombinedExpressions {
   Expression combined;
 
   GenericCombinedExpressions(this.combined);
 
   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) {}
+}