dart2js cps: Do not propagate uses of loop variables past their update.

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';
 
 /**
- * Performs the following transformations on the tree:
+ * Translates to direct-style.
+ *
+ * In addition to the general IR constraints (see [CheckTreeIntegrity]),
+ * the input is assumed to satisfy the following criteria:
+ *
+ * All expressions other than those nested in [Assign] or [ExpressionStatement]
+ * must be simple. A [VariableUse] and [This] is a simple expression.
+ * The right-hand of an [Assign] may not be an [Assign].
+ *
+ * Moreover, every variable must either be an SSA variable or a mutable
+ * variable, and must satisfy the corresponding criteria:
+ *
+ * SSA VARIABLE:
+ * An SSA variable must have a unique definition site, which is either an
+ * assignment or label. In case of a label, its target must act as the unique
+ * reaching definition of that variable at all uses of the variable and at
+ * all other label targets where the variable is in scope.
+ *
+ * (The second criterion is to ensure that we can move a use of an SSA variable
+ * across a label without changing its reaching definition).
+ *
+ * MUTABLE VARIABLE:
+ * Uses of mutable variables are considered complex expressions, and hence must
+ * not be nested in other expressions. Assignments to mutable variables must
+ * have simple right-hand sides.
+ *
+ * ----
+ *
+ * This pass performs the following transformations on the tree:
  * - Assignment inlining
  * - Assignment expression propagation
  * - If-to-conditional conversion
  * - Flatten nested ifs
  * - Break inlining
  * - Redirect breaks
  *
  * The above transformations all eliminate statements from the tree, and may
  * introduce redexes of each other.
  *
@@ skipping 84 matching lines @@
  *   {... jump L1 ...}
  *
  * This may trigger a flattening of nested ifs in case the eliminated label
  * separated two ifs.
  */
 class StatementRewriter extends Transformer implements Pass {
   String get passName => 'Statement rewriter';
 
   @override
   void rewrite(FunctionDefinition node) {
+    node.parameters.forEach(pushDominatingAssignment);
     node.body = visitStatement(node.body);
+    node.parameters.forEach(popDominatingAssignment);
   }
 
   /// 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.
   ///
@@ skipping 11 matching lines @@
 
   /// 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>{};
 
+  /// Number of assignments to a given variable that dominate the current
+  /// position.
+  ///
+  /// Pure expressions will not be inlined if it uses a variable with more than
+  /// one dominating assignment, because the reaching definition of the used
+  /// variable might have changed since it was put in the environment.
+  final Map<Variable, int> dominatingAssignments = <Variable, int>{};
+
   /// Rewriter for methods.
   StatementRewriter() : constantEnvironment = <Variable, Expression>{};
 
   /// Rewriter for nested functions.
   StatementRewriter.nested(StatementRewriter parent)
       : constantEnvironment = parent.constantEnvironment,
         unseenUses = parent.unseenUses;
 
   /// A set of labels that can be safely inlined at their use.
   ///
@@ skipping 31 matching lines @@
   }
 
   /// 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;
   }
 
+  /// True if the given expression (taken from [constantEnvironment]) uses a
+  /// variable that might have been reassigned since [node] was evaluated.
+  bool hasUnsafeVariableUse(Expression node) {
+    bool wasFound = false;
+    VariableUseVisitor.visit(node, (VariableUse use) {
+      if (dominatingAssignments[use.variable] > 1) {
+        wasFound = true;
+      }
+    });
+    return wasFound;
+  }
+
+  void pushDominatingAssignment(Variable variable) {
+    if (variable != null) {
+      dominatingAssignments.putIfAbsent(variable, () => 0);
+      ++dominatingAssignments[variable];
+    }
+  }
+
+  void popDominatingAssignment(Variable variable) {
+    if (variable != null) {
+      --dominatingAssignments[variable];
+    }
+  }
+
   @override
   Expression visitVariableUse(VariableUse node) {
     // Count of number of unseen uses remaining.
     unseenUses.putIfAbsent(node.variable, () => node.variable.readCount);
     --unseenUses[node.variable];
 
     // We traverse the tree right-to-left, so when we have seen all uses,
     // it means we are looking at the first use.
     assert(unseenUses[node.variable] < node.variable.readCount);
     assert(unseenUses[node.variable] >= 0);
     bool isFirstUse = unseenUses[node.variable] == 0;
 
     // Propagate constant to use site.
     Expression constant = constantEnvironment[node.variable];
-    if (constant != null) {
+    if (constant != null && !hasUnsafeVariableUse(constant)) {
       --node.variable.readCount;
       return visitExpression(constant);
     }
 
     // Try to propagate another expression into this variable use.
     if (!environment.isEmpty) {
       Expression binding = environment.last;
 
       // Is this variable assigned by the most recently evaluated impure
       // expression?
@@ skipping 70 matching lines @@
   }
 
   /// 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) {
+    Variable leftHand = getLeftHand(stmt.expression);
+    pushDominatingAssignment(leftHand);
     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.
+        // A single-use constant should always be propagated to its use site.
         constantEnvironment[assign.variable] = assign.value;
-        --assign.variable.writeCount;
-        return visitStatement(stmt.next);
+        Statement next = visitStatement(stmt.next);
+        popDominatingAssignment(leftHand);
+        if (assign.variable.readCount > 0) {
+          // The assignment could not be propagated.
+          assign.value = visitExpression(assign.value);
+          stmt.next = next;
+          return stmt;
+        } else {
+          --assign.variable.writeCount;
+          return next;
+        }
       } else {
         // With more than one use, we cannot propagate the constant.
         // Visit the following statement without polluting [environment] so
         // that any preceding non-constant assignments might still propagate.
         stmt.next = visitStatement(stmt.next);
+        popDominatingAssignment(leftHand);
         assign.value = visitExpression(assign.value);
         return stmt;
       }
     }
     // Try to propagate the expression, and block previous impure expressions
     // until this has propagated.
     environment.add(stmt.expression);
     stmt.next = visitStatement(stmt.next);
+    popDominatingAssignment(leftHand);
     if (!environment.isEmpty && environment.last == stmt.expression) {
       // Retain the expression statement.
       environment.removeLast();
       stmt.expression = visitExpression(stmt.expression);
       return stmt;
     } else {
       // Expression was propagated into the successor.
       return stmt.next;
     }
   }
@@ skipping 204 matching lines @@
     // Not introduced yet
     throw "Unexpected WhileCondition in StatementRewriter";
   }
 
   Statement visitTry(Try node) {
     inEmptyEnvironment(() {
       Set<Label> saved = safeForInlining;
       safeForInlining = new Set<Label>();
       node.tryBody = visitStatement(node.tryBody);
       safeForInlining = saved;
+      node.catchParameters.forEach(pushDominatingAssignment);
       node.catchBody = visitStatement(node.catchBody);
+      node.catchParameters.forEach(popDominatingAssignment);
     });
     return node;
   }
 
   Expression visitConstant(Constant node) {
     return node;
   }
 
   Expression visitThis(This node) {
     return node;
@@ skipping 185 matching lines @@
       // expressions if the statements could not be combined.
 
       // Combine the expressions.
       CombinedExpressions values =
           combineAsConditional(s.expression, t.expression, condition);
 
       // Put this into the environment and try to combine the statements.
       // We are not in risk of reprocessing the original subexpressions because
       // the combined expression will always hide them inside a Conditional.
       environment.add(values.combined);
+
+      Variable leftHand = getLeftHand(values.combined);
+      pushDominatingAssignment(leftHand);
       Statement next = combineStatements(s.next, t.next);
+      popDominatingAssignment(leftHand);
 
       if (next == null) {
         // Statements could not be combined.
         // Restore the environment and uncombine expressions again.
         environment.removeLast();
         values.uncombine();
         return null;
       } else if (!environment.isEmpty && environment.last == values.combined) {
         // Statements were combined but the combined expression could not be
         // propagated. Leave it as an expression statement here.
@@ skipping 54 matching lines @@
       CombinedExpressions values = combineExpressions(s.value, t.value);
       if (values != null) {
         return new Return(values.combined);
       }
     }
     if (s is ExpressionStatement && t is ExpressionStatement) {
       CombinedExpressions values =
           combineExpressions(s.expression, t.expression);
       if (values == null) return null;
       environment.add(values.combined);
+      Variable leftHand = getLeftHand(values.combined);
+      pushDominatingAssignment(leftHand);
       Statement next = combineStatements(s.next, t.next);
+      popDominatingAssignment(leftHand);
       if (next == null) {
         // The successors could not be combined.
         // Restore the environment and uncombine the values again.
         assert(environment.last == values.combined);
         environment.removeLast();
         values.uncombine();
         return null;
       } else if (!environment.isEmpty && environment.last == values.combined) {
         // The successors were combined but the combined expressions were not
         // propagated. Leave the combined expression as a statement.
@@ skipping 195 matching lines @@
   IsVariableUsedVisitor(this.variable);
 
   visitVariableUse(VariableUse node) {
     if (node.variable == variable) {
       wasFound = true;
     }
   }
 
   visitInnerFunction(FunctionDefinition node) {}
 }
+
+typedef VariableUseCallback(VariableUse use);
+
+class VariableUseVisitor extends RecursiveVisitor {
+  VariableUseCallback callback;
+
+  VariableUseVisitor(this.callback);
+
+  visitVariableUse(VariableUse use) => callback(use);
+
+  visitInnerFunction(FunctionDefinition node) {}
+
+  static void visit(Expression node, VariableUseCallback callback) {
+    new VariableUseVisitor(callback).visitExpression(node);
+  }
+}