dart2js cps: Compile some loops as 'for' loops.

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

Index: pkg/compiler/lib/src/tree_ir/optimization/loop_rewriter.dart
diff --git a/pkg/compiler/lib/src/tree_ir/optimization/loop_rewriter.dart b/pkg/compiler/lib/src/tree_ir/optimization/loop_rewriter.dart
index 8287bacdb751ff7c54394e5258fdfe5809522c4b..8dfa11089564a8212a63fc5f18598ad8bbb58bf4 100644
--- a/pkg/compiler/lib/src/tree_ir/optimization/loop_rewriter.dart
+++ b/pkg/compiler/lib/src/tree_ir/optimization/loop_rewriter.dart
@@ -7,7 +7,7 @@ library tree_ir.optimization.loop_rewriter;
 import 'optimization.dart' show Pass;
 import '../tree_ir_nodes.dart';
 
-/// Rewrites [WhileTrue] statements.
+/// Rewrites [WhileTrue] statements into [WhileCondition] statements.
 ///
 /// Before this phase, loops usually contain a lot of "exit code", that is,
 /// code that happens at a point where a [Continue] can no longer be reached,
@@ -50,16 +50,40 @@ import '../tree_ir_nodes.dart';
 ///
 /// A similar transformation is used when S2 occurs in the 'then' position.
 ///
-/// Note that the last pattern above needs no iteration since nested ifs
-/// have been collapsed previously in the [StatementRewriter] phase.
+/// Note that the pattern above needs no iteration since nested ifs have been
+/// collapsed previously in the [StatementRewriter] phase.
+/// 
 ///
-/// [WhileCondition] statements exist only after this phase.
+/// PULL INTO UPDATE EXPRESSION:
+/// 
+/// Assignment expressions before the unique continue to a [whileCondition] are
+/// pulled into the updates for the loop.
+/// 
+///   L:
+///   for (; condition; updates) {
+///     S [ x = E; continue L ]
+///   }
+///     ==>
+///   L:
+///   for (; condition; updates, x = E) {
+///     S [ continue L ]
+///   }
+///
+/// The decision to only pull in assignments is a heuristic to balance 
+/// readability and stack trace usability versus the modest code size
+/// reduction one might get by aggressively moving expressions into the
+/// updates.
 class LoopRewriter extends RecursiveTransformer
                    implements Pass {
   String get passName => 'Loop rewriter';
 
   Set<Label> usedContinueLabels = new Set<Label>();
 
+  /// Maps loop labels to a list, if that loop can accept update expressions.
+  /// The list will then be populated while traversing the body of that loop.
+  /// If a loop is not in the map, update expressions cannot be hoisted there.
+  Map<Label, List<Expression>> updateExpressions = <Label, List<Expression>>{};
+
   void rewrite(FunctionDefinition root) {
     root.body = visitStatement(root.body);
   }
@@ -100,6 +124,7 @@ class LoopRewriter extends RecursiveTransformer
     Statement loop = node;
     if (node.body is If) {
       If body = node.body;
+      updateExpressions[node.label] = <Expression>[];
       body.thenStatement = visitStatement(body.thenStatement);
       bool thenHasContinue = usedContinueLabels.remove(node.label);
       body.elseStatement = visitStatement(body.elseStatement);
@@ -109,6 +134,7 @@ class LoopRewriter extends RecursiveTransformer
         loop = new WhileCondition(
             node.label,
             body.condition,
+            updateExpressions[node.label],
             body.thenStatement,
             body.elseStatement);
       } else if (!thenHasContinue && elseHasContinue) {
@@ -116,6 +142,7 @@ class LoopRewriter extends RecursiveTransformer
         loop = new WhileCondition(
             node.label,
             new Not(body.condition),
+            updateExpressions[node.label],
             body.elseStatement,
             body.thenStatement);
       }
@@ -133,4 +160,44 @@ class LoopRewriter extends RecursiveTransformer
     tail.body = loop;
     return head;
   }
+
+  Statement visitExpressionStatement(ExpressionStatement node) {
+    if (updateExpressions.isEmpty) {
+      // Avoid allocating a list if there is no loop.
+      return super.visitExpressionStatement(node);
+    }
+    List<ExpressionStatement> statements = <ExpressionStatement>[];
+    while (node.next is ExpressionStatement) {
+      statements.add(node);
+      node = node.next;
+    }
+    statements.add(node);
+    Statement next = visitStatement(node.next);
+    if (next is Continue && next.target.useCount == 1) {
+      List<Expression> updates = updateExpressions[next.target];
+      if (updates != null) {
+        // Pull expressions before the continue into the for loop update.
+        // As a heuristic, we only pull in assignment expressions.
+        // Determine the index of the first assignment to pull in.
+        int assignIndex = 0;

[Kevin Millikin (Google), 2015/08/13 11:32:47]

Seems kind of tricky that this might be one past the end of the list, though the
code below handles that case properly.  Might be worth mentioning that it is
intentional and indicates no eligible assignment.

It seems more natural to me to iterate in reverse searching for the first
non-assignment.  That allows an early exit too:

int assignIndex = statements.length;
while (assignIndex > 0 && statements[assignIndex - 1) is! Assign) {
  --assignIndex;
}

(But my code is untested.)

[asgerf, 2015/08/13 12:06:42]

Yeah that looks better. Done.

+        for (int i = 0; i < statements.length; i++) {
+          if (statements[i].expression is! Assign) {
+            assignIndex = i + 1;
+          }
+        }
+        for (ExpressionStatement stmt in statements.skip(assignIndex)) {
+          updates.add(stmt.expression);
+        }
+        if (assignIndex > 0) {
+          statements[assignIndex - 1].next = next;
+          return statements.first;
+        } else {
+          return next;
+        }
+      }
+    }
+    // The expression statements could not be pulled into a loop update.
+    node.next = next;
+    return statements.first;
+  }
 }