Propagate pseudo-constants expressions separately in tree rewriter.

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 78 matching lines @@
  *   {... jump L1 ...}
  *
  * This may trigger a flattening of nested ifs in case the eliminated label
  * separated two ifs.
  */
 class StatementRewriter extends Visitor<Statement, Expression> with PassMixin {
   // The binding environment.  The rightmost element of the list is the nearest
   // available enclosing binding.
   List<Assign> environment;
 
+  /// 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>{};
 
+  /// Rewriter for methods.
+  StatementRewriter() : constantEnvironment = <Variable, Expression>{};
+
+  /// Rewriter for nested functions.
+  StatementRewriter.nested(StatementRewriter parent)
+      : constantEnvironment = parent.constantEnvironment;
+
   /// Returns the redirect target of [label] or [label] itself if it should not
   /// be redirected.
   Jump redirect(Jump jump) {
     Jump newJump = labelRedirects[jump.target];
     return newJump != null ? newJump : jump;
   }
 
-
   rewriteExecutableDefinition(ExecutableDefinition definition) {
-    definition.body = rewriteInEmptyEnvironment(definition.body);
+    inEmptyEnvironment(() {
+      definition.body = visitStatement(definition.body);
+    });
   }
 
   void rewriteConstructorDefinition(ConstructorDefinition definition) {
     if (definition.isAbstract) return;
     definition.initializers.forEach(visitExpression);
     rewriteExecutableDefinition(definition);
   }
 
-  Statement rewriteInEmptyEnvironment(Statement body) {
+  void inEmptyEnvironment(void action()) {
     List<Assign> oldEnvironment = environment;
     environment = <Assign>[];
-
-    Statement result = visitStatement(body);
-    // TODO(kmillikin):  Allow definitions that are not propagated.  Here,
-    // this means rebuilding the binding with a recursively unnamed definition,
-    // or else introducing a variable definition and an assignment.
+    action();
     assert(environment.isEmpty);
     environment = oldEnvironment;
-    return result;
   }
 
   Expression visitFieldInitializer(FieldInitializer node) {
-    node.body = rewriteInEmptyEnvironment(node.body);
+    inEmptyEnvironment(() {
+      node.body = visitStatement(node.body);
+    });
     return node;
   }
 
   Expression visitSuperInitializer(SuperInitializer node) {
-    for (int i = node.arguments.length - 1; i >= 0; --i) {
-      node.arguments[i] = rewriteInEmptyEnvironment(node.arguments[i]);
-    }
+    inEmptyEnvironment(() {
+      for (int i = node.arguments.length - 1; i >= 0; --i) {
+        node.arguments[i] = visitStatement(node.arguments[i]);
+        assert(environment.isEmpty);
+      }
+    });
     return node;
   }
 
   Expression visitExpression(Expression e) => e.processed ? e : e.accept(this);
 
   Expression visitVariable(Variable node) {
+    // Propagate constant to use site.
+    Expression constant = constantEnvironment[node];
+    if (constant != null) return constant;
+
     // Propagate a variable's definition to its use site if:
     // 1.  It has a single use, to avoid code growth and potential duplication
     //     of side effects, AND
     // 2.  It was the most recent expression evaluated so that we do not
     //     reorder expressions with side effects.
     if (!environment.isEmpty &&
         environment.last.variable == node &&
         environment.last.hasExactlyOneUse) {
       return visitExpression(environment.removeLast().definition);
     }
     // If the definition could not be propagated, leave the variable use.
     return node;
   }
 
+  /// 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 ReifyTypeVar ||
+           exp is Variable && constantEnvironment.containsKey(exp);
+  }
 
   Statement visitAssign(Assign node) {
-    environment.add(node);
-    Statement next = visitStatement(node.next);
-
-    if (!environment.isEmpty && environment.last == node) {
-      // The definition could not be propagated.  Residualize the let binding.
-      node.next = next;
-      environment.removeLast();
-      node.definition = visitExpression(node.definition);
-      return node;
+    if (isEffectivelyConstant(node.definition)) {
+      // 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 (node.variable.readCount <= 1 && node.variable.writeCount == 1) {
+        // A single-use constant should always be propagted to its use site.
+        constantEnvironment[node.variable] = visitExpression(node.definition);
+        return visitStatement(node.next);
+      } else {
+        // With more than one use, we cannot propagate the constant.
+        // Visit the following statement without polluting [environment] so
+        // the previous assignment might still propagate.

[Kevin Millikin (Google), 2015/02/12 11:52:51]

Maybe "previous non-constant assignment" or "immediately previous non-constant
assignment" just to make it more clear.

[asgerf, 2015/02/12 12:31:14]

Rephrased a bit.

+        node.next = visitStatement(node.next);
+        node.definition = visitExpression(node.definition);
+        return node;
+      }
+    } else {
+      // Try to propagate assignment, and block previous assignment until this
+      // has propagated.
+      environment.add(node);
+      Statement next = visitStatement(node.next);
+      if (!environment.isEmpty && environment.last == node) {
+        // The definition could not be propagated. Residualize the let binding.
+        node.next = next;
+        environment.removeLast();
+        node.definition = visitExpression(node.definition);
+        return node;
+      }
+      assert(!environment.contains(node));
+      return next;
     }
-    assert(!environment.contains(node));
-    return next;
   }
 
   Expression visitInvokeStatic(InvokeStatic node) {
     // Process arguments right-to-left, the opposite of evaluation order.
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     return node;
   }
 
@@ skipping 23 matching lines @@
   Expression visitConcatenateStrings(ConcatenateStrings node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     return node;
   }
 
   Expression visitConditional(Conditional node) {
     node.condition = visitExpression(node.condition);
 
-    List<Assign> savedEnvironment = environment;
-    environment = <Assign>[];
-    node.thenExpression = visitExpression(node.thenExpression);
-    assert(environment.isEmpty);
-    node.elseExpression = visitExpression(node.elseExpression);
-    assert(environment.isEmpty);
-    environment = savedEnvironment;
+    inEmptyEnvironment(() {
+      node.thenExpression = visitExpression(node.thenExpression);
+      node.elseExpression = visitExpression(node.elseExpression);
+    });
 
     return node;
   }
 
   Expression visitLogicalOperator(LogicalOperator node) {
     node.left = visitExpression(node.left);
 
-    environment.add(null); // impure expressions may not propagate across branch
-    node.right = visitExpression(node.right);
-    environment.removeLast();
+    // Impure expressions may not propagate across the branch.
+    inEmptyEnvironment(() {
+      node.right = visitExpression(node.right);
+    });
 
     return node;
   }
 
   Expression visitNot(Not node) {
     node.operand = visitExpression(node.operand);
     return node;
   }
 
   Expression visitFunctionExpression(FunctionExpression node) {
-    new StatementRewriter().rewrite(node.definition);
+    new StatementRewriter.nested(this).rewrite(node.definition);
     return node;
   }
 
   Statement visitFunctionDeclaration(FunctionDeclaration node) {
-    new StatementRewriter().rewrite(node.definition);
+    new StatementRewriter.nested(this).rewrite(node.definition);
     node.next = visitStatement(node.next);
     return node;
   }
 
   Statement visitReturn(Return node) {
     node.value = visitExpression(node.value);
     return node;
   }
 
 
@@ skipping 31 matching lines @@
 
     node.body = visitStatement(node.body);
 
     if (node.label.useCount == 0) {
       // Eliminate the label if next was inlined at a break
       return node.body;
     }
 
     // Do not propagate assignments into the successor statements, since they
     // may be overwritten by assignments in the body.
-    List<Assign> savedEnvironment = environment;
-    environment = <Assign>[];
-    node.next = visitStatement(node.next);
-    environment = savedEnvironment;
+    inEmptyEnvironment(() {
+      node.next = visitStatement(node.next);
+    });
 
     return node;
   }
 
   Statement visitIf(If node) {
     node.condition = visitExpression(node.condition);
 
     // Do not propagate assignments into branches.  Doing so will lead to code
     // duplication.
-    // TODO(kmillikin): Rethink this.  Propagating some assignments (e.g.,
-    // constants or variables) is benign.  If they can occur here, they should
+    // TODO(kmillikin): Rethink this. Propagating some assignments
+    // (e.g. variables) is benign.  If they can occur here, they should
     // be handled well.
-    List<Assign> savedEnvironment = environment;
-    environment = <Assign>[];
-    node.thenStatement = visitStatement(node.thenStatement);
-    assert(environment.isEmpty);
-    node.elseStatement = visitStatement(node.elseStatement);
-    assert(environment.isEmpty);
-    environment = savedEnvironment;
+    inEmptyEnvironment(() {
+      node.thenStatement = visitStatement(node.thenStatement);
+      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;
     }
 
     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).
-    List<Assign> savedEnvironment = environment;
-    environment = <Assign>[];
-    node.body = visitStatement(node.body);
-    assert(environment.isEmpty);
-    environment = savedEnvironment;
+    inEmptyEnvironment(() {
+      node.body = visitStatement(node.body);
+    });
     return node;
   }
 
   Statement visitWhileCondition(WhileCondition node) {
     // Not introduced yet
     throw "Unexpected WhileCondition in StatementRewriter";
   }
 
   Expression visitConstant(Constant node) {
     return node;
@@ skipping 26 matching lines @@
 
   Expression visitTypeOperator(TypeOperator node) {
     node.receiver = visitExpression(node.receiver);
     return node;
   }
 
   Statement visitExpressionStatement(ExpressionStatement node) {
     node.expression = visitExpression(node.expression);
     // Do not allow propagation of assignments past an expression evaluated
     // for its side effects because it risks reordering side effects.
-    // TODO(kmillikin): Rethink this.  Some propagation is benign, e.g.,
-    // constants, variables, or other pure values that are not destroyed by
+    // TODO(kmillikin): Rethink this.  Some propagation is benign,
+    // e.g. variables, or other pure values that are not destroyed by
     // the expression statement.  If they can occur here they should be
     // handled well.
-    List<Assign> savedEnvironment = environment;
-    environment = <Assign>[];
-    node.next = visitStatement(node.next);
-    assert(environment.isEmpty);
-    environment = savedEnvironment;
+    inEmptyEnvironment(() {
+      node.next = visitStatement(node.next);
+    });
     return node;
   }
 
   Statement visitSetField(SetField node) {
     node.next = visitStatement(node.next);
     node.value = visitExpression(node.value);
     node.object = visitExpression(node.object);
     return node;
   }
 
@@ skipping 152 matching lines @@
       if (innerElse is Break && innerElse.target == outerElse.target) {
         // 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.
-        List<Assign> savedEnvironment = environment;
-        environment = <Assign>[];
-        outerIf.elseStatement = visitStatement(outerElse);
-        assert(environment.isEmpty);
-        environment = savedEnvironment;
+        inEmptyEnvironment(() {
+          outerIf.elseStatement = visitStatement(outerElse);
+        });
 
         return outerIf.elseStatement is If && innerThen is Break;
       }
     }
     return false;
   }
 
   Expression makeCondition(Expression e, bool polarity) {
     return polarity ? e : new Not(e);
   }
 
   Statement getBranch(If node, bool polarity) {
     return polarity ? node.thenStatement : node.elseStatement;
   }
 }