dart2js cps: Global value numbering and loop-invariant code motion.

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

 library dart2js.cps_ir.loop_effects;
 
 import 'cps_ir_nodes.dart';
 import 'loop_hierarchy.dart';
 import 'type_mask_system.dart';
 import '../universe/side_effects.dart';
 import '../elements/elements.dart';
 import '../world.dart';
 
 /// Determines which the [SideEffects] that may occur during each loop in
@@ skipping 28 matching lines @@
   /// True if the length of an indexable object may change between the loop
   /// entry and a recursive invocation of the loop.
   bool loopChangesLength(Continuation loop) {
     return loopsChangingLength.contains(loop);
   }
 
   @override
   Expression traverseContinuation(Continuation cont) {
     if (cont.isRecursive) {
       SideEffects oldEffects = currentLoopSideEffects;
-      Continuation oldLoopHeader = currentLoopHeader;
       bool oldChangesLength = currentLoopChangesLength;
-      currentLoopHeader = cont;
       loopSideEffects[cont] = currentLoopSideEffects = new SideEffects.empty();
       exitContinuations[cont] = <Continuation>[];
       pushAction(() {
         oldEffects.add(currentLoopSideEffects);
         if (currentLoopChangesLength) {
           loopsChangingLength.add(cont);
         }
         currentLoopChangesLength = currentLoopChangesLength || oldChangesLength;
-        currentLoopHeader = oldLoopHeader;
         currentLoopSideEffects = oldEffects;
         exitContinuations[cont].forEach(push);
       });
     }
+    Continuation oldLoopHeader = currentLoopHeader;
+    currentLoopHeader = loopHierarchy.getLoopHeader(cont);
+    pushAction(() {
+      currentLoopHeader = oldLoopHeader;
+    });
     return cont.body;
   }
 
   @override
   Expression traverseLetHandler(LetHandler node) {
     enqueueContinuation(node.handler);
     return node.body;
   }
 
   @override
   Expression traverseLetCont(LetCont node) {
     node.continuations.forEach(enqueueContinuation);
     return node.body;
   }
 
   void enqueueContinuation(Continuation cont) {
     Continuation loop = loopHierarchy.getEnclosingLoop(cont);
     if (loop == currentLoopHeader) {
       push(cont);
     } else {
       // Multiple loops can be exited at once.
       // Register as an exit from the outermost loop being exited.
       Continuation inner = currentLoopHeader;
       Continuation outer = loopHierarchy.getEnclosingLoop(currentLoopHeader);
       while (outer != loop) {
+        if (inner == null) {
+          // The shrinking reductions pass must run before any pass that relies
+          // on computing loop side effects.
+          throw 'Unreachable continuations must be removed before computing '
+                'loop side effects.';

[asgerf, 2015/11/16 15:42:39]

This is similar to the problem of putting unreachable blocks into a dominator
tree. There is no correct place to put it, and putting it in an arbitrary place
can break some assumptions in the client analysis.

[sra1, 2015/11/17 05:41:14]

Use the proper internal error (possibly as separate CL)

[asgerf, 2015/11/17 12:43:43]

Done.

+        }
         inner = outer;
         outer = loopHierarchy.getEnclosingLoop(outer);
       }
       exitContinuations[inner].add(cont);
     }
   }
 
   void addSideEffects(SideEffects effects) {
     currentLoopSideEffects.add(effects);
     if (effects.changesIndex()) {
@@ skipping 64 matching lines @@
 
   void visitAwait(Await node) {
     addAllSideEffects();
   }
 
   void visitYield(Yield node) {
     addAllSideEffects();
   }
 
   void visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
+    currentLoopSideEffects.setChangesIndex();
     currentLoopChangesLength = true; // Push and pop.
   }
 }