dart2js cps: Hoist unsafe expressions from loop entry.

pkg/compiler/lib/src/cps_ir/gvn.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.
 
 library dart2js.cps_ir.gvn;
 
 import 'cps_ir_nodes.dart';
 import '../universe/side_effects.dart';
 import '../elements/elements.dart';
 import 'optimizers.dart' show Pass;
@@ skipping 158 matching lines @@
     // environment while processing the body of the LetPrim.
     environment[gvn] = prim;
     pushAction(() {
       assert(environment[gvn] == prim);
       environment[gvn] = existing;
     });
 
     return next;
   }
 
+  bool isFirstImpureExpressionInLoop(Expression exp) {
+    InteriorNode node = exp.parent;
+    for (; node is Expression; node = node.parent) {
+      if (node is LetPrim && node.primitive.isSafeForElimination) {
+        continue;
+      }
+      if (node is LetCont) {
+        continue;
+      }
+      return false;
+    }
+    return node == currentLoopHeader;
+  }
+
+  bool isHoistablePrimitive(Primitive prim) {
+    if (prim.isSafeForElimination) return true;
+    if (prim is NullCheck ||
+        prim is BoundsCheck ||
+        prim is GetLength ||
+        prim is GetField ||
+        prim is GetIndex) {
+      // Expressions that potentially throw but have no other effects can be
+      // hoisted if they occur as the first impure expression in a loop.
+      // Note regarding BoundsCheck: the current array length is an input to
+      // check, so the check itself has no heap dependency.  It will only be
+      // hoisted if the length was hoisted.
+      // TODO(asgerf): In general we could hoist these out of multiple loops,
+      //   but the trick we use here only works for one loop level.
+      return isFirstImpureExpressionInLoop(prim.parent);
+    }
+    return false;
+  }
+
   /// Try to hoist the binding of [prim] out of loops. Returns `true` if it was
   /// hoisted or marked as a trivial hoist-on-demand primitive.
   bool tryToHoistOutOfLoop(Primitive prim, int gvn) {
-    // Do not hoist primitives with side effects.
-    if (!prim.isSafeForElimination) return false;
-
     // Bail out fast if the primitive is not inside a loop.
     if (currentLoopHeader == null) return false;
 
+    // Do not hoist primitives with side effects.
+    if (!isHoistablePrimitive(prim)) return false;
+
     LetPrim letPrim = prim.parent;
 
     // Find the depth of the outermost scope where we can bind the primitive
     // without bringing a reference out of scope. 0 is the depth of the
     // top-level scope.
     int hoistDepth = 0;
     List<Primitive> inputsHoistedOnDemand = <Primitive>[];
     InputVisitor.forEach(prim, (Reference ref) {
       Primitive input = ref.definition;
       if (canIgnoreRefinementGuards(prim)) {
@@ skipping 122 matching lines @@
     return element.isField && world.fieldNeverChanges(element) ||
            element.isFunction;
   }
 
   bool isImmutableLength(GetLength length) {
     return types.isDefinitelyFixedLengthIndexable(length.object.definition.type,
         allowNull: true);
   }
 
   /// Assuming [prim] has no side effects, returns true if it can safely
-  /// be hoisted out of [loop] without changing its value.
+  /// be hoisted out of [loop] without changing its value or changing the timing
+  /// of a thrown exception.
   bool canHoistHeapDependencyOutOfLoop(Primitive prim, Continuation loop) {
-    assert(prim.isSafeForElimination);
+    // If the primitive might throw, we have to check that it is the first
+    // impure expression in the loop.  This has already been checked if
+    // [loop] is the current loop header, but for other loops we just give up.
+    if (!prim.isSafeForElimination && loop != currentLoopHeader) {
+      return false;
+    }
     if (prim is GetLength && !isImmutableLength(prim)) {
       return !loopEffects.loopChangesLength(loop);
     } else if (prim is GetField && !isImmutable(prim.field)) {
       return !loopEffects.getSideEffectsInLoop(loop).changesInstanceProperty();
     } else if (prim is GetStatic && !isImmutable(prim.element)) {
       return !loopEffects.getSideEffectsInLoop(loop).changesStaticProperty();
     } else if (prim is GetIndex) {
       return !loopEffects.getSideEffectsInLoop(loop).changesIndex();
     } else {
       return true;
     }
   }
 
-
   // ------------------ TRAVERSAL AND EFFECT NUMBERING ---------------------
   //
   // These methods traverse the IR while updating the current effect numbers.
   // They are not specific to GVN.
   //
   // TODO(asgerf): Avoid duplicated code for side effect analysis.
   // Should be easier to fix once primitives and call expressions are the same.
 
   void addSideEffects(SideEffects fx, {bool length: true}) {
     if (fx.changesInstanceProperty()) {
@@ skipping 365 matching lines @@
 
   @override
   processReference(Reference ref) {
     callback(ref);
   }
 
   static void forEach(Primitive node, ReferenceCallback callback) {
     new InputVisitor(callback).visit(node);
   }
 }