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

pkg/compiler/lib/src/tree_ir/optimization/loop_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.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,
 /// and is therefore not really part of the loop.
 /// Exit code is moved down after the loop using the following rewrites rules:
 ///
 /// EXTRACT LABELED STATEMENT:
 ///
 ///   L:
 ///   while (true) {
@@ skipping 22 matching lines @@
 ///   }
 ///     ==>
 ///   L:
 ///   while (E) {
 ///     S1
 ///   };
 ///   S2
 ///
 /// 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);
   }
 
   @override
   void visitInnerFunction(FunctionDefinition node) {
     node.body = new LoopRewriter().visitStatement(node.body);
   }
 
   Statement visitContinue(Continue node) {
@@ skipping 20 matching lines @@
       } else {
         tail.body = inner;
         tail = inner;
       }
     }
 
     // Rewrite while(true) to while(condition).
     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);
       bool elseHasContinue = usedContinueLabels.remove(node.label);
       if (thenHasContinue && !elseHasContinue) {
         node.label.binding = null; // Prepare to rebind the label.
         loop = new WhileCondition(
             node.label,
             body.condition,
+            updateExpressions[node.label],
             body.thenStatement,
             body.elseStatement);
       } else if (!thenHasContinue && elseHasContinue) {
         node.label.binding = null;
         loop = new WhileCondition(
             node.label,
             new Not(body.condition),
+            updateExpressions[node.label],
             body.elseStatement,
             body.thenStatement);
       }
     } else if (node.body is LabeledStatement) {
       // If the body is a labeled statement, its .next has already been visited.
       LabeledStatement body = node.body;
       body.body = visitStatement(body.body);
       usedContinueLabels.remove(node.label);
     } else {
       node.body = visitStatement(node.body);
       usedContinueLabels.remove(node.label);
     }
 
     if (head == null) return loop;
     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;
+  }
 }