dart2js cps: Do GVN for all primitives except fast constants.

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 46 matching lines @@
   /// Effect numbers at the given join point.
   Map<Continuation, EffectNumbers> effectsAt = <Continuation, EffectNumbers>{};
 
   /// The effect numbers at the current position (during traversal).
   EffectNumbers effectNumbers = new EffectNumbers();
 
   /// The loop currently enclosing the binding of a given primitive.
   final Map<Primitive, Continuation> loopHeaderFor =
       <Primitive, Continuation>{};
 
-  /// The loop to which a given trivial primitive can be hoisted.
-  final Map<Primitive, Continuation> potentialLoopHeaderFor =
-      <Primitive, Continuation>{};
-
   /// The GVNs for primitives that have been hoisted outside the given loop.
   ///
   /// These should be removed from the environment when exiting the loop.
   final Map<Continuation, List<int>> loopHoistedBindings =
       <Continuation, List<int>>{};
 
   /// Maps GVNs to a currently-in-scope binding for that value.
   final Map<int, Primitive> environment = <int, Primitive>{};
 
   /// Maps GVN'able primitives to their global value number.
@@ skipping 67 matching lines @@
     }
 
     // Compute the GVN for this primitive.
     int gvn = gvnTable.insert(vector);
     gvnFor[prim] = gvn;
 
     // Try to reuse a previously computed value with the same GVN.
     Primitive existing = environment[gvn];
     if (existing != null &&
         canReplaceWithExistingValue(prim) &&
-        !isTrivialPrimitive(prim)) {
+        !isFastConstant(prim)) {
       if (prim is Interceptor) {
         Interceptor interceptor = existing;
         interceptor.interceptedClasses.addAll(prim.interceptedClasses);
       }
       prim..replaceUsesWith(existing)..destroy();
       node.remove();
       return next;
     }
 
     if (tryToHoistOutOfLoop(prim, gvn)) {
@@ skipping 25 matching lines @@
     // 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)) {
         input = input.effectiveDefinition;
       }
-      Continuation loopHeader;
-      if (potentialLoopHeaderFor.containsKey(input)) {
-        // This is a reference to a value that can be hoisted further out than
-        // it currently is.  If we decide to hoist [prim], we must also hoist
-        // such dependent values.
-        loopHeader = potentialLoopHeaderFor[input];
+      if (isFastConstant(input)) {
+        // Fast constants can be hoisted all the way out, but should only be
+        // hoisted if needed to hoist something else.
         inputsHoistedOnDemand.add(input);
       } else {
-        loopHeader = loopHeaderFor[input];
-      }
-      Continuation referencedLoop =
-          loopHierarchy.lowestCommonAncestor(loopHeader, currentLoopHeader);
-      int depth = loopHierarchy.getDepth(referencedLoop);
-      if (depth > hoistDepth) {
-        hoistDepth = depth;
+        Continuation loopHeader = loopHeaderFor[input];
+        Continuation referencedLoop =
+            loopHierarchy.lowestCommonAncestor(loopHeader, currentLoopHeader);
+        int depth = loopHierarchy.getDepth(referencedLoop);
+        if (depth > hoistDepth) {
+          hoistDepth = depth;
+        }
       }
     });
 
     // Bail out if it can not be hoisted further out than it is now.
     if (hoistDepth == loopHierarchy.getDepth(currentLoopHeader)) return false;
 
     // Walk up the loop hierarchy and check at every step that any heap
     // dependencies can safely be hoisted out of the loop.
     Continuation enclosingLoop = currentLoopHeader;
     Continuation hoistTarget = null;
     while (loopHierarchy.getDepth(enclosingLoop) > hoistDepth &&
            canHoistHeapDependencyOutOfLoop(prim, enclosingLoop)) {
       hoistTarget = enclosingLoop;
       enclosingLoop = loopHierarchy.getEnclosingLoop(enclosingLoop);
     }
 
     // Bail out if heap dependencies prohibit any hoisting at all.
     if (hoistTarget == null) return false;
 
-    if (isTrivialPrimitive(prim)) {
+    if (isFastConstant(prim)) {
       // The overhead from introducting a temporary might be greater than
       // the overhead of evaluating this primitive at every iteration.
       // Only hoist if this enables hoisting of a non-trivial primitive.
-      potentialLoopHeaderFor[prim] = enclosingLoop;
       return true;
     }
 
     LetCont loopBinding = hoistTarget.parent;
 
     // The primitive may depend on values that have not yet been
     // hoisted as far as they can.  Hoist those now.
     for (Primitive input in inputsHoistedOnDemand) {
       hoistTrivialPrimitive(input, loopBinding, enclosingLoop);
     }
@@ skipping 26 matching lines @@
         .putIfAbsent(hoistTarget, () => <int>[])
         .add(gvn);
     return true;
   }
 
   /// If the given primitive is a trivial primitive that should be hoisted
   /// on-demand, hoist it and its dependent values above [loopBinding].
   void hoistTrivialPrimitive(Primitive prim,
                              LetCont loopBinding,
                              Continuation enclosingLoop) {
-    if (!potentialLoopHeaderFor.containsKey(prim)) return;
-    assert(isTrivialPrimitive(prim));
+    assert(isFastConstant(prim));
 
     // The primitive might already be bound in an outer scope.  Do not relocate
     // the primitive unless we are lifting it. For example;
     //    t1 = a + b
     //    t2 = t1 + c
     //    t3 = t1 * t2
     // If it was decided that `t3` should be hoisted, `t1` will be seen twice by
     // this method: by the direct reference and by reference through `t2`.
     // The second time it is seen, it will already have been moved.
     Continuation currentLoop = loopHeaderFor[prim];
     int currentDepth = loopHierarchy.getDepth(currentLoop);
     int targetDepth = loopHierarchy.getDepth(enclosingLoop);
     if (currentDepth <= targetDepth) return;
 
     // Hoist the trivial primitives being depended on so they remain in scope.
     InputVisitor.forEach(prim, (Reference ref) {
       hoistTrivialPrimitive(ref.definition, loopBinding, enclosingLoop);
     });
 
     // Move the primitive.
     LetPrim binding = prim.parent;
     binding.remove();
     binding.insertAbove(loopBinding);
     loopHeaderFor[prim] = enclosingLoop;
-
-    if (potentialLoopHeaderFor[prim] == enclosingLoop) {
-      potentialLoopHeaderFor.remove(prim);
-    }
   }
 
   bool canIgnoreRefinementGuards(Primitive primitive) {
     return primitive is Interceptor;
   }
 
-  /// Returns true if the given primitive is so cheap at runtime that it is
-  /// better to (redundantly) recompute it rather than introduce a temporary.
-  bool isTrivialPrimitive(Primitive primitive) {
-    return primitive is ApplyBuiltinOperator ||
-           primitive is Constant && isTrivialConstant(primitive.value);
-  }
-
-  /// Returns true if the given constant has almost no runtime cost.
-  bool isTrivialConstant(ConstantValue value) {
-    return value.isPrimitive || value.isDummy;
+  /// Returns true if [prim] is a constant that has no significant runtime cost.
+  bool isFastConstant(Primitive prim) {
+    return prim is Constant && (prim.value.isPrimitive || prim.value.isDummy);
   }
 
   /// True if [element] is a final or constant field or a function.
   bool isImmutable(Element element) {
     if (element.isField && backend.isNative(element)) return false;
     return element.isField && world.fieldNeverChanges(element) ||
            element.isFunction;
   }
 
   bool isImmutableLength(GetLength length) {
@@ skipping 397 matching lines @@
 
   @override
   processReference(Reference ref) {
     callback(ref);
   }
 
   static void forEach(Primitive node, ReferenceCallback callback) {
     new InputVisitor(callback).visit(node);
   }
 }