dart2js cps: LICM, GVN, and constify for interceptors in one pass.

pkg/compiler/lib/src/cps_ir/loop_invariant_code_motion.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.loop_invariant_code_motion;
-
-import 'optimizers.dart';
-import 'cps_ir_nodes.dart';
-import 'loop_hierarchy.dart';
-
-/// Lifts primitives out of loops when it is safe and profitable.
-/// 
-/// Currently we only do this for interceptors.
-class LoopInvariantCodeMotion extends RecursiveVisitor implements Pass {
-  String get passName => 'Loop-invariant code motion';
-
-  final Map<Primitive, Continuation> primitiveLoop = 
-      <Primitive, Continuation>{};
-
-  LoopHierarchy loopHierarchy;
-  Continuation currentLoopHeader;
-
-  /// When processing the dependencies of a primitive, [referencedLoop]
-  /// refers to the innermost loop that contains one of the dependencies
-  /// seen so far (or `null` if none of the dependencies are bound in a loop).
-  ///
-  /// This is used to determine how far the primitive can be lifted without
-  /// falling out of scope of its dependencies.
-  Continuation referencedLoop;
-
-  void rewrite(FunctionDefinition node) {
-    loopHierarchy = new LoopHierarchy(node);
-    visit(node.body);
-  }
-
-  @override
-  Expression traverseContinuation(Continuation cont) {
-    Continuation oldLoopHeader = currentLoopHeader;
-    pushAction(() {
-      currentLoopHeader = oldLoopHeader;
-    });
-    currentLoopHeader = loopHierarchy.getLoopHeader(cont);
-    for (Parameter param in cont.parameters) {
-      primitiveLoop[param] = currentLoopHeader;
-    }
-    return cont.body;
-  }
-
-  @override
-  Expression traverseLetPrim(LetPrim node) {
-    primitiveLoop[node.primitive] = currentLoopHeader;
-    if (!shouldLift(node.primitive)) {
-      return node.body;
-    }
-    referencedLoop = null;
-    visit(node.primitive); // Sets referencedLoop.
-    Expression next = node.body;
-    if (referencedLoop != currentLoopHeader) {
-      // Bind the primitive inside [referencedLoop] (possibly null),
-      // immediately before the binding of the inner loop.
-
-      // Find the inner loop.
-      Continuation loop = currentLoopHeader;
-      Continuation enclosing = loopHierarchy.getEnclosingLoop(loop);
-      while (enclosing != referencedLoop) {
-        assert(loop != null);
-        loop = enclosing;
-        enclosing = loopHierarchy.getEnclosingLoop(loop);
-      }
-      assert(loop != null);
-
-      // Remove LetPrim from its current position.
-      node.parent.body = node.body;
-      node.body.parent = node.parent;
-
-      // Insert the LetPrim immediately before the loop.
-      LetCont loopBinding = loop.parent;
-      InteriorNode newParent = loopBinding.parent;
-      newParent.body = node;
-      node.body = loopBinding;
-      loopBinding.parent = node;
-      node.parent = newParent;
-
-      // A different loop now contains the primitive.
-      primitiveLoop[node.primitive] = enclosing;
-    }
-    return next;
-  }
-
-  /// Returns the the innermost loop that effectively encloses both
-  /// c1 and c2 (or `null` if there is no such loop).
-  Continuation leastCommonAncestor(Continuation c1, Continuation c2) {
-    int d1 = getDepth(c1), d2 = getDepth(c2);
-    while (c1 != c2) {
-      if (d1 <= d2) {
-        c2 = loopHierarchy.getEnclosingLoop(c2);
-        d2 = getDepth(c2);
-      } else {
-        c1 = loopHierarchy.getEnclosingLoop(c1);
-        d1 = getDepth(c1);
-      }
-    }
-    return c1;
-  }
-
-  @override
-  void processReference(Reference ref) {
-    Continuation loop = 
-        leastCommonAncestor(currentLoopHeader, primitiveLoop[ref.definition]);
-    referencedLoop = getInnerLoop(loop, referencedLoop);
-  }
-
-  int getDepth(Continuation loop) {
-    if (loop == null) return -1;
-    return loopHierarchy.loopDepth[loop];
-  }
-
-  Continuation getInnerLoop(Continuation loop1, Continuation loop2) {
-    if (loop1 == null) return loop2;
-    if (loop2 == null) return loop1;
-    if (loopHierarchy.loopDepth[loop1] > loopHierarchy.loopDepth[loop2]) {
-      return loop1;
-    } else {
-      return loop2;
-    }
-  }
-
-  bool shouldLift(Primitive prim) {
-    // Interceptors are generally safe and almost always profitable for lifting
-    // out of loops. Several other primitive could be lifted too, but it's not
-    // always profitable to do so.
-
-    // Note that the type of the interceptor is technically not sound after
-    // lifting because its current type might have been computed based on a
-    // refinement node (which has since been removed). As a whole, it still
-    // works out because all uses of the interceptor must occur in a context
-    // where it indeed has the type it claims to have.
-    return prim is Interceptor;
-  }
-}