dart2js cps: Hoist loop-invariant branches from loop entry.

pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart

 // Copyright (c) 2013, 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 dart2js.ir_nodes;
 
 import 'dart:collection';
 import 'cps_fragment.dart' show CpsFragment;
 import '../constants/values.dart' as values;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
@@ skipping 1178 matching lines @@
   final Reference<Continuation> trueContinuation;
   final Reference<Continuation> falseContinuation;
 
   /// If true, only the value `true` satisfies the condition. Otherwise, any
   /// truthy value satisfies the check.
   ///
   /// Non-strict checks are preferable when the condition is known to be a
   /// boolean.
   bool isStrictCheck;
 
+  Branch(Primitive condition,
+         Continuation trueCont,
+         Continuation falseCont,
+         {bool strict})
+      : this.condition = new Reference<Primitive>(condition),
+        trueContinuation = new Reference<Continuation>(trueCont),
+        falseContinuation = new Reference<Continuation>(falseCont),
+        isStrictCheck = strict {
+    assert(strict != null);
+  }
+
   Branch.strict(Primitive condition,
                 Continuation trueCont,
                 Continuation falseCont)
-      : this.condition = new Reference<Primitive>(condition),
-        trueContinuation = new Reference<Continuation>(trueCont),
-        falseContinuation = new Reference<Continuation>(falseCont),
-        isStrictCheck = true;
+        : this(condition, trueCont, falseCont, strict: true);
 
   Branch.loose(Primitive condition,
                Continuation trueCont,
                Continuation falseCont)
-      : this.condition = new Reference<Primitive>(condition),
-        trueContinuation = new Reference<Continuation>(trueCont),
-        falseContinuation = new Reference<Continuation>(falseCont),
-        this.isStrictCheck = false;
+      : this(condition, trueCont, falseCont, strict: false);
 
   accept(BlockVisitor visitor) => visitor.visitBranch(this);
 
   void setParentPointers() {
     condition.parent = this;
     trueContinuation.parent = this;
     falseContinuation.parent = this;
   }
 }
 
@@ skipping 678 matching lines @@
         node = node.next;
         nodes.add(node);
       }
     }
     walkBlock(root);
     while (stack.isNotEmpty) {
       walkBlock(stack.removeLast());
     }
     nodes.reversed.forEach(v.visit);
   }
+
+  /// Visits block-level nodes in lexical pre-order.
+  ///
+  /// Continuations and function definitions are considered "block headers".
+  /// The block itself is the sequence of interior expressions in the body,
+  /// terminated by a tail expression.
+  ///
+  /// Each block is visited starting with its tail expression, then every
+  /// interior expression from bottom to top, and finally the block header
+  /// is visited.
+  ///
+  /// Blocks are visited in pre-order, so the body of a continuation is always
+  /// processed after its non-recursive invocation sites.
+  ///
+  /// The IR may be transformed during the traversal, but only the original
+  /// nodes will be visited.
+  static void traverseInPreOrder(FunctionDefinition root, BlockVisitor v) {
+    List<Continuation> stack = <Continuation>[];
+    void walkBlock(InteriorNode block) {
+      v.visit(block);
+      Expression node = block.body;
+      v.visit(node);
+      while (node.next != null) {
+        if (node is LetCont) {
+          stack.addAll(node.continuations);
+        } else if (node is LetHandler) {
+          stack.add(node.handler);
+        }
+        node = node.next;
+        v.visit(node);
+      }
+    }
+    walkBlock(root);
+    while (stack.isNotEmpty) {
+      walkBlock(stack.removeLast());
+    }
+  }
 }
 
 abstract class Visitor<T> implements BlockVisitor<T> {
   const Visitor();
 
   T visit(Node node);
 
   // Definitions.
   T visitInvokeStatic(InvokeStatic node);
   T visitInvokeMethod(InvokeMethod node);
@@ skipping 872 matching lines @@
     plug(new Branch.loose(_definitions.getCopy(node.condition),
         _copies[node.trueContinuation.definition],
         _copies[node.falseContinuation.definition])
       ..isStrictCheck = node.isStrictCheck);
   }
 
   visitUnreachable(Unreachable node) {
     plug(new Unreachable());
   }
 }