Assignment expressions in tree IR.

pkg/compiler/lib/src/tree_ir/optimization/pull_into_initializers.dart

+// Copyright (c) 2015, 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.
+
+import 'optimization.dart' show Pass;
+import '../tree_ir_nodes.dart';
+
+/// Pulls assignment expressions to the top of the function body so they can be
+/// translated into declaration-site variable initializaters.
+///
+/// This reverts the assignment expression propagation performed by
+/// [StatementRewriter] in cases where it not beneficial.
+///
+/// EXAMPLE:
+///
+///     var x = foo(),
+///         y = bar(x);
+///
+///     ==> [StatementRewriter]
+///
+///     var x,
+///         y = bar(x = foo());
+///
+///     ==> [PullIntoInitializers] restores the initializer for x
+///
+///     var x = foo(),
+///         y = bar(x);
+///
+///
+/// Sometimes the assignment propagation will trigger another optimization
+/// in the [StatementRewriter] which then prevents [PullIntoInitializers] from
+/// restoring the initializer. This is acceptable, since most optimizations
+/// at that level are better than restoring an initializer.
+///
+/// EXAMPLE:
+///
+///     var x = foo(),
+///         y = bar();
+///     baz(x, y, y);
+///
+///     ==> [StatementRewriter]
+///
+///     var y;
+///     baz(foo(), y = bar(), y);
+///
+/// [PullIntoInitializers] cannot pull `y` into an initializer because
+/// the impure expressions `foo()` and `bar()` would then be swapped.
+///
+class PullIntoInitializers implements Pass {
+  String get passName => 'Pull into initializers';
+
+  void rewrite(RootNode node) {
+    node.replaceEachBody((Statement body) {
+      return new BodyRewriter().rewriteBody(node.parameters, body);
+    });
+  }
+}
+
+class BodyRewriter {
+  Set<Variable> assignedVariables = new Set<Variable>();
+
+  /// The fragment between [first] and [last] holds the statements
+  /// we pulled into the initializer block.

[Kevin Millikin (Google), 2015/04/14 08:41:00]

Here and below 'initializer block' is non-standard.  The comments would benefit
from a brief description of what we mean by it.

[asgerf, 2015/04/14 10:12:14]

Done.

+  ///
+  /// It is empty when both are `null`.
+  Statement first, last;
+
+  /// Appends a statement to the initializer block.
+  void append(Statement node) {
+    if (first == null) {
+      first = last = node;
+    } else {
+      last.next = node;
+      last = node;
+    }
+  }
+
+  /// Pulls assignment expressions from [node] into the initializer block
+  /// by calling [append].
+  ///
+  /// Returns a transformed expression where the pulled assignments are
+  /// replaced by variable uses.
+  Expression rewriteExpression(Expression node) {
+    return new ExpressionToInitializerVisitor(this).visitExpression(node);
+  }
+
+  Statement rewriteBody(List<Variable> parameters, Statement node) {
+    assignedVariables.addAll(parameters);
+
+    // [node] represents the first statement after the initializer block.
+    // Repeatedly pull assignment statements into the initializer block.
+    while (node is ExpressionStatement) {
+      ExpressionStatement stmt = node;
+      stmt.expression = rewriteExpression(stmt.expression);
+      if (stmt.expression is VariableUse) {
+        // The entire expression was pulled into an initializer.
+        // This can happen when the expression was an assignment that was
+        // pulled into the initializer block and replaced by a variable use.
+        // Discard the statement and try to pull in more initializers from
+        // the next statement.
+        destroyVariableUse(stmt.expression);
+        node = stmt.next;

[Kevin Millikin (Google), 2015/04/14 08:41:00]

It's a bit clearer to introduce a Statement 'current' which is mutated instead
of the parameter.

[asgerf, 2015/04/14 10:12:14]

I don't like stale variables that you are likely to reference in a place where
you meant something else. I.e one could easily reference 'node' by accident
instead of 'current'.

I've renamed node to 'body' to hopefully clarify a little bit.

+      } else {
+        // The whole expression could not be pulled into an initializer, so we
+        // have reached the end of the initializer block.
+        break;
+      }
+    }
+
+    // [If] and [Return] statements terminate the initializer block, but the
+    // initial expression they contain may be pulled up into an initializer.
+    // It's ok to pull an assignment across a label so look for the first
+    // non-labeled statement and try to pull its initial subexpression.
+    Statement entryNode = unfoldLabeledStatements(node);
+    if (entryNode is If) {
+      entryNode.condition = rewriteExpression(entryNode.condition);
+    } else if (entryNode is Return) {
+      entryNode.value = rewriteExpression(entryNode.value);
+    }
+
+    // Join the initializer block with the rest of the body.
+    append(node);

[Kevin Millikin (Google), 2015/04/14 08:41:00]

The code is backwards from the comment, so I'd make it say something like: join
the rest of the body to the initializer block.  (I don't think that it
necessarily needs a comment, though.)

[asgerf, 2015/04/14 10:12:14]

Removed the comment. Even less necessary after the node->body rename.

+
+    assert(first != null); // Because we just appended node.
+    return first;
+  }
+
+  void destroyVariableUse(VariableUse node) {
+    --node.variable.readCount;
+  }
+
+  Statement unfoldLabeledStatements(Statement node) {
+    while (node is LabeledStatement) {
+      node = (node as LabeledStatement).body;
+    }
+    return node;
+  }
+}
+
+
+class ExpressionToInitializerVisitor extends ExpressionVisitor<Expression> {

[Kevin Millikin (Google), 2015/04/14 08:41:00]

On the one hand, this class only has one bit of state so allocating one per
top-level expression is cheap.  On the other hand, it only has one bit of state
so allocating one per top-level expressions seems like overkill.

Couldn't we just make the BodyRewriter be an ExpressionVisitor, with a top-level
rewriteExpression method that clears the seenImpure flag?  That seems simpler.

[asgerf, 2015/04/14 10:12:14]

I don't think it's simpler, but either way is fine.

+  BodyRewriter parent;
+
+  /// True if an impure expression has been returned by visitExpression.
+  ///
+  /// Expressions cannot be pulled into an initializer if this might reorder
+  /// impure expressions.
+  ///
+  /// A visit method may not be called while this flag is set, meaning all
+  /// visitor methods must check the flag between visiting subexpressions.
+  bool seenImpure = false;
+
+  ExpressionToInitializerVisitor(this.parent);
+
+  Expression visitAssign(Assign node) {
+    assert(!seenImpure);
+    node.value = visitExpression(node.value);
+    if (!parent.assignedVariables.add(node.variable)) {
+      // This is not the first assignment to the variable, so it cannot be
+      // pulled into an initializer.
+      // We have to leave the assignment here, and assignments are impure.
+      seenImpure = true;
+      return node;
+    } else {
+      // Pull the assignment into an initializer.
+      // We will leave behind a variable use, which is pure, so we can
+      // disregard any impure expressions seen in the right-side.

[Kevin Millikin (Google), 2015/04/14 08:41:00]

'right-hand side' or 'right side' (no hyphen).

[asgerf, 2015/04/14 10:12:14]

Done.

+      seenImpure = false;
+      parent.append(new ExpressionStatement(node, null));
+      return new VariableUse(node.variable);
+    }
+  }
+
+  void rewriteList(List<Expression> list) {
+    for (int i = 0; i < list.length; i++) {
+      list[i] = visitExpression(list[i]);
+      if (seenImpure) return;
+    }
+  }
+
+  Expression visitInvokeStatic(InvokeStatic node) {
+    rewriteList(node.arguments);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitInvokeMethod(InvokeMethod node) {
+    node.receiver = visitExpression(node.receiver);
+    if (seenImpure) return node;
+    rewriteList(node.arguments);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitInvokeMethodDirectly(InvokeMethodDirectly node) {
+    node.receiver = visitExpression(node.receiver);
+    if (seenImpure) return node;
+    rewriteList(node.arguments);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitInvokeConstructor(InvokeConstructor node) {
+    rewriteList(node.arguments);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitConcatenateStrings(ConcatenateStrings node) {
+    rewriteList(node.arguments);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitTypeExpression(TypeExpression node) {
+    rewriteList(node.arguments);
+    return node;
+  }
+
+  Expression visitConditional(Conditional node) {
+    node.condition = visitExpression(node.condition);
+    if (seenImpure) return node;
+    node.thenExpression = visitExpression(node.thenExpression);
+    if (seenImpure) return node;
+    node.elseExpression = visitExpression(node.elseExpression);
+    return node;
+  }
+
+  Expression visitLogicalOperator(LogicalOperator node) {
+    node.left = visitExpression(node.left);
+    if (seenImpure) return node;
+    node.right = visitExpression(node.right);
+    return node;
+  }
+
+  Expression visitLiteralList(LiteralList node) {
+    rewriteList(node.values);
+    if (node.type != null) seenImpure = true; // Type casts can throw.
+    return node;
+  }
+
+  Expression visitLiteralMap(LiteralMap node) {
+    for (LiteralMapEntry entry in node.entries) {
+      entry.key = visitExpression(entry.key);
+      if (seenImpure) return node;
+      entry.value = visitExpression(entry.value);
+      if (seenImpure) return node;
+    }
+    if (node.type != null) seenImpure = true; // Type casts can throw.
+    return node;
+  }
+
+  Expression visitTypeOperator(TypeOperator node) {
+    node.receiver = visitExpression(node.receiver);
+    if (!node.isTypeTest) seenImpure = true; // Type cast can throw.
+    return node;
+  }
+
+  void visitInnerFunction(FunctionDefinition node) {
+    node.body = new BodyRewriter().rewriteBody(node.parameters, node.body);
+  }
+
+  Expression visitFunctionExpression(FunctionExpression node) {
+    visitInnerFunction(node.definition);
+    return node;
+  }
+
+  Expression visitGetField(GetField node) {
+    node.object = visitExpression(node.object);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitSetField(SetField node) {
+    node.object = visitExpression(node.object);
+    if (seenImpure) return node;
+    node.value = visitExpression(node.value);
+    seenImpure = true;
+    return node;
+  }
+
+  Expression visitCreateBox(CreateBox node) {
+    return node;
+  }
+
+  Expression visitCreateInstance(CreateInstance node) {
+    rewriteList(node.arguments);
+    return node;
+  }
+
+  Expression visitReifyRuntimeType(ReifyRuntimeType node) {
+    node.value = visitExpression(node.value);
+    return node;
+  }
+
+  Expression visitReadTypeVariable(ReadTypeVariable node) {
+    node.target = visitExpression(node.target);
+    return node;
+  }
+
+  Expression visitConstant(Constant node) {
+    return node;
+  }
+
+  Expression visitThis(This node) {
+    return node;
+  }
+
+  Expression visitReifyTypeVar(ReifyTypeVar node) {
+    return node;
+  }
+
+  Expression visitNot(Not node) {
+    node.operand = visitExpression(node.operand);
+    return node;
+  }
+
+  Expression visitVariableUse(VariableUse node) {
+    return node;
+  }
+}