dart2js cps: Better GVN for fixed lengths and unmodified fields.

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;
 import 'loop_hierarchy.dart';
 import 'loop_effects.dart';
 import '../world.dart';
 import '../compiler.dart' show Compiler;
 import '../js_backend/js_backend.dart' show JavaScriptBackend;
 import '../constants/values.dart';
+import 'type_mask_system.dart';
 
 /// Eliminates redundant primitives by reusing the value of another primitive
 /// that is known to have the same result.  Primitives are also hoisted out of
 /// loops when possible.
 ///
 /// Reusing values can introduce new temporaries, which in some cases is more
 /// expensive than recomputing the value on-demand. For example, pulling an
 /// expression such as "n+1" out of a loop is generally not worth it.
 /// Such primitives are said to be "trivial".
 ///
@@ skipping 10 matching lines @@
 //
 //  TODO(asgerf): Put this pass at a better place in the pipeline.  We currently
 //    cannot put it anywhere we want, because this pass relies on refinement
 //    nodes being present (for safety), whereas other passes rely on refinement
 //    nodes being absent (for simplicity & precision).
 //
 class GVN extends TrampolineRecursiveVisitor implements Pass {
   String get passName => 'GVN';
 
   final Compiler compiler;
+  final TypeMaskSystem types;
   JavaScriptBackend get backend => compiler.backend;
   World get world => compiler.world;
 
   final GvnTable gvnTable = new GvnTable();
   GvnVectorBuilder gvnVectorBuilder;
   LoopHierarchy loopHierarchy;
   LoopSideEffects loopEffects;
 
   /// Effect numbers at the given join point.
   Map<Continuation, EffectNumbers> effectsAt = <Continuation, EffectNumbers>{};
@@ skipping 16 matching lines @@
       <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.
   final Map<Primitive, int> gvnFor = <Primitive, int>{};
 
   Continuation currentLoopHeader;
 
-  GVN(this.compiler);
+  GVN(this.compiler, this.types);
 
   int _usedEffectNumbers = 0;
   int makeNewEffect() => ++_usedEffectNumbers;
 
   void rewrite(FunctionDefinition node) {
-    gvnVectorBuilder = new GvnVectorBuilder(gvnFor, backend);
+    gvnVectorBuilder = new GvnVectorBuilder(gvnFor, compiler, types);
     loopHierarchy = new LoopHierarchy(node);
     loopEffects =
         new LoopSideEffects(node, world, loopHierarchy: loopHierarchy);
     visit(node);
   }
 
   // ------------------ GLOBAL VALUE NUMBERING ---------------------
 
   @override
   Expression traverseLetPrim(LetPrim node) {
@@ skipping 206 matching lines @@
   }
 
   /// Returns true if the given constant has almost no runtime cost.
   bool isTrivialConstant(ConstantValue value) {
     return value.isPrimitive || 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 && (element.isFinal || element.isConst) ||
+    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.
   bool canHoistHeapDependencyOutOfLoop(Primitive prim, Continuation loop) {
     assert(prim.isSafeForElimination);
-    if (prim is GetLength) {
+    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;
     }
@@ skipping 234 matching lines @@
 /// This includes the instruction type, inputs, effect numbers for any part
 /// of the heap being depended on, as well as any instruction-specific payload
 /// such as any DartTypes, Elements, and operator kinds.
 ///
 /// Each `visit` or `process` method for a primitive must initialize [vector]
 /// if the primitive is GVN'able and fill in any components except the inputs.
 /// The inputs will be filled in by [processReference].
 class GvnVectorBuilder extends DeepRecursiveVisitor {
   List vector;
   final Map<Primitive, int> gvnFor;
-  final JavaScriptBackend backend;
+  final Compiler compiler;
+  World get world => compiler.world;
+  JavaScriptBackend get backend => compiler.backend;
+  final TypeMaskSystem types;
   EffectNumbers effectNumbers;
 
-  GvnVectorBuilder(this.gvnFor, this.backend);
+  GvnVectorBuilder(this.gvnFor, this.compiler, this.types);
 
   List make(Primitive prim, EffectNumbers effectNumbers) {
     this.effectNumbers = effectNumbers;
     vector = null;
     visit(prim);
     return vector;
   }
 
   /// The `process` methods below do not insert the referenced arguments into
   /// the vector, but instead rely on them being inserted here.
   processReference(Reference ref) {
     if (vector == null) return;
     Primitive prim = ref.definition.effectiveDefinition;
     vector.add(gvnFor[prim] ?? prim);
   }
 
   processTypeTest(TypeTest node) {
     vector = [GvnCode.TYPE_TEST, node.dartType];
   }
 
   processTypeTestViaFlag(TypeTestViaFlag node) {
     vector = [GvnCode.TYPE_TEST_VIA_FLAG, node.dartType];
   }
 
   processApplyBuiltinOperator(ApplyBuiltinOperator node) {
     vector = [GvnCode.BUILTIN_OPERATOR, node.operator.index];
   }
 
   processGetLength(GetLength node) {
-    // TODO(asgerf): Take fixed lengths into account?
-    vector = [GvnCode.GET_LENGTH, effectNumbers.indexableLength];
+    if (isImmutableLength(node)) {
+      // Omit the effect number for fixed-length lists.  Note that if a the list
+      // gets refined to a fixed-length type, we still won't be able to GVN a
+      // GetLength across the refinement, because the first GetLength uses an
+      // effect number in its vector while the second one does not.
+      vector = [GvnCode.GET_LENGTH];
+    } else {
+      vector = [GvnCode.GET_LENGTH, effectNumbers.indexableLength];
+    }
   }
 
   bool isImmutable(Element element) {
     return element.isFunction ||
-           element.isField && (element.isFinal || element.isConst);
+           element.isField && world.fieldNeverChanges(element);
+  }
+
+  bool isImmutableLength(GetLength length) {
+    return types.isDefinitelyFixedLengthIndexable(length.object.definition.type,
+        allowNull: true);
   }
 
   bool isNativeField(FieldElement field) {
     // TODO(asgerf): We should add a GetNativeField instruction.
     return backend.isNative(field);
   }
 
   processGetField(GetField node) {
     if (isNativeField(node.field)) {
       vector = null; // Native field access cannot be GVN'ed.
@@ skipping 68 matching lines @@
 
   @override
   processReference(Reference ref) {
     callback(ref);
   }
 
   static void forEach(Primitive node, ReferenceCallback callback) {
     new InputVisitor(callback).visit(node);
   }
 }