dart2js cps: Fix performance issues in optimization passes.

pkg/compiler/lib/src/cps_ir/let_sinking.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.let_sinking;
 
 import 'cps_ir_nodes.dart';
 import 'optimizers.dart';
 
 /// Sinks single-use primitives to the use when this is safe and profitable.
@@ skipping 12 matching lines @@
 ///       InvokeContinuation kont x'
 ///     else 
 ///       <after loop>
 ///       return p.foo()
 /// 
 class LetSinker extends RecursiveVisitor implements Pass {
   String get passName => 'Let sinking';
 
   LoopHierarchy loopHierarchy;
   List<Continuation> stack = <Continuation>[];
-  Set<LetPrim> sunkNodes = new Set<LetPrim>();
+
+  /// Maps a sinkable primitive to its loop header.
+  Map<Primitive, Continuation> loopHeaderForPrimitive = 
+      <Primitive, Continuation>{};
+
+  Continuation currentLoopHeader;
 
   void rewrite(FunctionDefinition node) {
     new ParentVisitor().visit(node);
     loopHierarchy = new LoopHierarchy(node);
     visit(node.body);
   }
 
   @override
   Expression traverseLetPrim(LetPrim node) {
-    pushAction(() {
-      if (node.primitive != null) {
-        // The primitive could not be sunk. Sink dependencies to this location.
-        visit(node.primitive);
-      } else {
-        // The primitive was sunk. Destroy the old LetPrim.
-        InteriorNode parent = node.parent;
-        parent.body = node.body;
-        node.body.parent = parent;
-      }
-    });
+    Primitive prim = node.primitive;
+    if (prim.hasExactlyOneUse && prim.isSafeForReordering) {
+      // This can potentially be sunk. Register the loop header, so when we
+      // find the use site, we can check if they are in the same loop.
+      loopHeaderForPrimitive[prim] = currentLoopHeader;
+      pushAction(() {
+        if (node.primitive != null) {
+          // The primitive could not be sunk. Try to sink dependencies here.
+          visit(node.primitive);
+        } else {
+          // The primitive was sunk. Destroy the old LetPrim.
+          InteriorNode parent = node.parent;
+          parent.body = node.body;
+          node.body.parent = parent;
+        }
+      });
+    } else {
+      visit(node.primitive);
+    }
 
     // Visit the body, wherein this primitive may be sunk to its use site.
     return node.body;
   }
 
+  @override
+  Expression traverseContinuation(Continuation cont) {
+    Continuation oldLoopHeader = currentLoopHeader;
+    pushAction(() {
+      currentLoopHeader = oldLoopHeader;
+    });
+    currentLoopHeader = loopHierarchy.getLoopHeader(cont);
+    return cont.body;
+  }
+
   void processReference(Reference ref) {
     Definition definition = ref.definition;
     if (definition is Primitive && 
         definition is! Parameter &&
         definition.hasExactlyOneUse &&
         definition.isSafeForReordering) {
       // Check if use is in the same loop.
-      LetPrim binding = definition.parent;
-      Continuation bindingLoop = loopHierarchy.getLoopHeader(binding);
-      Expression use = getEnclosingExpression(ref.parent);
-      Continuation useLoop = loopHierarchy.getLoopHeader(use);
-      if (bindingLoop == useLoop || definition is Constant) {
+      Continuation bindingLoop = loopHeaderForPrimitive.remove(definition);
+      if (bindingLoop == currentLoopHeader || definition is Constant) {
         // Sink the definition.
 
+        Expression use = getEnclosingExpression(ref.parent);
+        LetPrim binding = definition.parent;
         binding.primitive = null;  // Mark old binding for deletion.
         LetPrim newBinding = new LetPrim(definition);
         definition.parent = newBinding;
         InteriorNode useParent = use.parent;
         useParent.body = newBinding;
         newBinding.body = use;
         use.parent = newBinding;
         newBinding.parent = useParent;
 
         // Now that the final binding location has been found, sink the
@@ skipping 40 matching lines @@
   /// Current nesting depth.
   int currentDepth = 0;
 
   /// Computes the loop hierarchy for the given function.
   /// 
   /// Parent pointers must be computed for [node].
   LoopHierarchy(FunctionDefinition node) {
     _processBlock(node.body, null);
   }
 
-  /// Returns the innermost loop which [node] is effectively part of.
-  Continuation getLoopHeader(Expression exp) {
-    Node node = exp.parent;
-    while (node != null && node is! Continuation) {
-      node = node.parent;
-    }
-    if (node is Continuation) {
-      if (node.isRecursive) { 
-        return node;
-      } else {
-        return loopTarget[node];
-      }
-    }
-    return null;
+  /// Returns the innermost loop which [cont] is effectively part of.
+  Continuation getLoopHeader(Continuation cont) {
+    return cont.isRecursive ? cont : loopTarget[cont];
   }
 
   /// Marks the innermost loop as a subloop of the other loop.
   /// 
   /// Returns the innermost loop.
   /// 
   /// Both continuations, [c1] and [c2] may be null (i.e. no loop).
   /// 
   /// A loop is said to be a subloop of an enclosing loop if it can invoke
   /// that loop recursively. This information is stored in [loopTarget].
@@ skipping 80 matching lines @@
     target = _markInnerLoop(target, catchLoop);
     for (Continuation cont in callContinuations) {
       // Store the loop target on each call continuation in the basic block.
       // Because we walk over call continuations as part of the basic block
       // traversal, these do not get their loop target set otherwise.
       loopTarget[cont] = target;
     }
     return target;
   }
 }