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 98 matching lines @@
  * separated two ifs.
  */
 class StatementRewriter extends Transformer implements Pass {
   String get passName => 'Statement rewriter';
 
   @override
   void rewrite(FunctionDefinition node) {
     node.body = visitStatement(node.body);
   }
 
-  /// True if targeting Dart.
-  final bool isDartMode;
-
   /// The most recently evaluated impure expressions, with the most recent
   /// expression being last.
   ///
   /// Most importantly, this contains [Assign] expressions that we attempt to
   /// inline at their use site. It also contains other impure expressions that
   /// we can propagate to a variable use if they are known to return the value
   /// of that variable.
   ///
+  /// Assignments with constant right-hand sides (see [isEffectivelyConstant])
+  /// are not considered impure and are put in [constantEnvironment] instead.
+  ///
   /// Except for [Conditional]s, expressions in the environment have
   /// not been processed, and all their subexpressions must therefore be
   /// variables uses.
   List<Expression> environment = <Expression>[];
 
   /// Binding environment for variables that are assigned to effectively
   /// constant expressions (see [isEffectivelyConstant]).
   final Map<Variable, Expression> constantEnvironment;
 
   /// Substitution map for labels. Any break to a label L should be substituted
   /// for a break to L' if L maps to L'.
   Map<Label, Jump> labelRedirects = <Label, Jump>{};
 
   /// Number of uses of the given variable that are still unseen.
   /// Used to detect the first use of a variable (since we do backwards
   /// traversal, the first use is the last one seen).
   Map<Variable, int> unseenUses = <Variable, int>{};
 
   /// Rewriter for methods.
-  StatementRewriter({this.isDartMode})
-      : constantEnvironment = <Variable, Expression>{} {
-    assert(isDartMode != null);
-  }
+  StatementRewriter() : constantEnvironment = <Variable, Expression>{};
 
   /// Rewriter for nested functions.
   StatementRewriter.nested(StatementRewriter parent)
       : constantEnvironment = parent.constantEnvironment,
-        unseenUses = parent.unseenUses,
-        isDartMode = parent.isDartMode;
+        unseenUses = parent.unseenUses;
 
   /// A set of labels that can be safely inlined at their use.
   ///
   /// The successor statements for labeled statements that have only one break
   /// from them are normally rewritten inline at the site of the break.  This
   /// is not safe if the code would be moved inside the scope of an exception
   /// handler (i.e., if the code would be moved into a try from outside it).
   Set<Label> safeForInlining = new Set<Label>();
 
   /// Returns the redirect target of [jump] or [jump] itself if it should not
@@ skipping 12 matching lines @@
   }
 
   /// Left-hand side of the given assignment, or `null` if not an assignment.
   Variable getLeftHand(Expression e) {
     return e is Assign ? e.variable : null;
   }
 
   /// If the given expression always returns the value of one of its
   /// subexpressions, returns that subexpression, otherwise `null`.
   Expression getValueSubexpression(Expression e) {
-    if (isDartMode &&
-        e is InvokeMethod &&
-        (e.selector.isSetter || e.selector.isIndexSet)) {
-      return e.arguments.last;
-    }
     if (e is SetField) return e.value;
     return null;
   }
 
   /// If the given expression always returns the value of one of its
   /// subexpressions, and that subexpression is a variable use, returns that
   /// variable. Otherwise `null`.
   Variable getRightHand(Expression e) {
     Expression value = getValueSubexpression(e);
     return value is VariableUse ? value.variable : null;
@@ skipping 51 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
+  /// most recently evaluated impure expression (constant assignments are not
+  /// considered impure).
+  ///
+  /// 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].
+  ///
+  /// [exp] must be an unprocessed expression, i.e. either a [Conditional] or
+  /// an expression whose subexpressions are all variable uses.
+  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
+/// 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) {}
+}