dart2js cps: Avoid deep recursion using trampolines and basic blocks.

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';
 import '../../io/source_information.dart';
 
@@ skipping 350 matching lines @@
            exp is VariableUse && constantEnvironment.containsKey(exp.variable);
   }
 
   /// 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) {
+  Statement visitExpressionStatement(ExpressionStatement inputNode) {
+    // Analyze chains of expression statements.
+    // To avoid deep recursion, [processExpressionStatement] returns a callback
+    // to invoke after its successor node has been processed.
+    // These callbacks are stored in a list and invoked in reverse at the end.
+    List<Function> stack = [];
+    Statement node = inputNode;
+    while (node is ExpressionStatement) {
+      stack.add(processExpressionStatement(node));
+      node = node.next;
+    }
+    Statement result = visitStatement(node);
+    for (Function fun in stack.reversed) {
+      result = fun(result);
+    }
+    return result;
+  }
+
+  /// Attempts to propagate an assignment in an expression statement.
+  /// 
+  /// Returns a callback to be invoked after the sucessor statement has
+  /// been processed.
+  Function processExpressionStatement(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 propagated to its use site.
         constantEnvironment[assign.variable] = assign.value;
-        Statement next = visitStatement(stmt.next);
-        popDominatingAssignment(leftHand);
-        if (assign.variable.readCount > 0) {
-          // The assignment could not be propagated into the successor, either
-          // because it has an unsafe variable use (see [hasUnsafeVariableUse])
-          // or because the use is outside the current try block, and we do
-          // not currently support constant propagation out of a try block.
-          constantEnvironment.remove(assign.variable);
-          assign.value = visitExpression(assign.value);
-          stmt.next = next;
-          return stmt;
-        } else {
-          --assign.variable.writeCount;
-          return next;
-        }
+        return (Statement next) {
+          popDominatingAssignment(leftHand);
+          if (assign.variable.readCount > 0) {
+            // The assignment could not be propagated into the successor, 
+            // either because it [hasUnsafeVariableUse] or because the
+            // use is outside the current try block, and we do not currently
+            // support constant propagation out of a try block.
+            constantEnvironment.remove(assign.variable);
+            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);
+        return (Statement next) {
+          stmt.next = next;
+          popDominatingAssignment(leftHand);
+          assign.value = visitExpression(assign.value);
+          return stmt;
+        };
+      }
+    } else {
+      // Try to propagate the expression, and block previous impure expressions
+      // until this has propagated.
+      environment.add(stmt.expression);
+      return (Statement next) {
+        stmt.next = 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;
+        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;
+        }
+      };
     }
   }
 
   Expression visitAssign(Assign node) {
     node.value = visitExpression(node.value);
     // Remove assignments to variables without any uses. This can happen
     // because the assignment was propagated into its use, e.g:
     //
     //     { x = foo(); bar(x) } ==> bar(x = foo()) ==> bar(foo())
     //
@@ skipping 738 matching lines @@
   VariableUseVisitor(this.callback);
 
   visitVariableUse(VariableUse use) => callback(use);
 
   visitInnerFunction(FunctionDefinition node) {}
 
   static void visit(Expression node, VariableUseCallback callback) {
     new VariableUseVisitor(callback).visitExpression(node);
   }
 }