Revert "dart2js cps: Refactor tracking of side effects."

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';
-import 'effects.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".
 ///
 /// Trivial primitives are shared on-demand, i.e. they are only shared if
 /// this enables a non-trivial primitive to be hoisted out of a loop.
 //
 //  TODO(asgerf): Enable hoisting across refinement guards when this is safe:
 //    - Determine the type required for a given primitive to be "safe"
 //    - Recompute the type of a primitive after hoisting.
 //        E.g. GetIndex on a String can become a GetIndex on an arbitrary
 //             indexable, which is still safe but the type may change
 //    - Since the new type may be worse, insert a refinement at the old
 //      definition site, so we do not degrade existing type information.
 //
+//  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;
 
-  final EffectNumberer effectNumberer = new EffectNumberer();
-
   /// Effect numbers at the given join point.
   Map<Continuation, EffectNumbers> effectsAt = <Continuation, EffectNumbers>{};
 
   /// The effect numbers at the current position (during traversal).
-  EffectNumbers effectNumbers;
+  EffectNumbers effectNumbers = new EffectNumbers();
 
   /// The loop currently enclosing the binding of a given primitive.
   final Map<Primitive, Continuation> loopHeaderFor =
       <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.
   final Map<Primitive, int> gvnFor = <Primitive, int>{};
 
   Continuation currentLoopHeader;
 
   GVN(this.compiler, this.types);
 
+  int _usedEffectNumbers = 0;
+  int makeNewEffect() => ++_usedEffectNumbers;
+
   void rewrite(FunctionDefinition node) {
-    effectNumbers = new EffectNumbers.fresh(effectNumberer);
     gvnVectorBuilder = new GvnVectorBuilder(gvnFor, compiler, types);
     loopHierarchy = new LoopHierarchy(node);
     loopEffects =
         new LoopSideEffects(node, world, loopHierarchy: loopHierarchy);
     visit(node);
   }
 
   // ------------------ GLOBAL VALUE NUMBERING ---------------------
 
   /// True if [prim] can be eliminated if its value is already in scope.
@@ skipping 21 matching lines @@
       // Do not share refinements (they have no runtime or code size cost), and
       // do not put them in the GVN table because GvnVectorBuilder unfolds
       // refinements by itself.
       return next;
     }
 
     // Update effect numbers due to side effects from a static initializer.
     // GetLazyStatic is GVN'ed like a GetStatic, but the effects of the static
     // initializer occur before reading the field.
     if (prim is GetLazyStatic) {
-      addSideEffectsOfPrimitive(prim);
+      visit(prim);
     }
 
     // Compute the GVN vector for this computation.
     List vector = gvnVectorBuilder.make(prim, effectNumbers);
 
     // Update effect numbers due to side effects.
     // Do this after computing the GVN vector so the primitive's GVN is not
     // influenced by its own side effects, except in the case of GetLazyStatic.
     if (prim is! GetLazyStatic) {
-      addSideEffectsOfPrimitive(prim);
+      visit(prim);
     }
 
     if (vector == null) {
       // The primitive is not GVN'able. Move on.
       return next;
     }
 
     // Compute the GVN for this primitive.
     int gvn = gvnTable.insert(vector);
     gvnFor[prim] = gvn;
@@ skipping 191 matching lines @@
 
   bool canIgnoreRefinementGuards(Primitive primitive) {
     return primitive is Interceptor;
   }
 
   /// 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) {
+    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 or changing the timing
   /// of a thrown exception.
   bool canHoistHeapDependencyOutOfLoop(Primitive prim, Continuation loop) {
     // If the primitive might throw, we have to check that it is the first
     // impure expression in the loop.  This has already been checked if
     // [loop] is the current loop header, but for other loops we just give up.
     if (!prim.isSafeForElimination && loop != currentLoopHeader) {
       return false;
     }
-    int effects = loopEffects.getSideEffectsInLoop(loop);
-    return Effects.changesToDepends(effects) & prim.effects == 0;
+    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;
+    }
   }
 
   // ------------------ TRAVERSAL AND EFFECT NUMBERING ---------------------
   //
   // These methods traverse the IR while updating the current effect numbers.
   // They are not specific to GVN.
+  //
+  // TODO(asgerf): Avoid duplicated code for side effect analysis.
+  // Should be easier to fix once primitives and call expressions are the same.
 
-  void addSideEffectsOfPrimitive(Primitive prim) {
-    addSideEffects(prim.effects);
+  void addSideEffects(SideEffects fx, {bool length: true}) {
+    if (fx.changesInstanceProperty()) {
+      effectNumbers.instanceField = makeNewEffect();
+    }
+    if (fx.changesStaticProperty()) {
+      effectNumbers.staticField = makeNewEffect();
+    }
+    if (fx.changesIndex()) {
+      effectNumbers.indexableContent = makeNewEffect();
+    }
+    if (length && fx.changesIndex()) {
+      effectNumbers.indexableLength = makeNewEffect();
+    }
   }
 
-  void addSideEffects(int effectFlags) {
-    effectNumbers.change(effectNumberer, effectFlags);
+  void addAllSideEffects() {
+    effectNumbers.instanceField = makeNewEffect();
+    effectNumbers.staticField = makeNewEffect();
+    effectNumbers.indexableContent = makeNewEffect();
+    effectNumbers.indexableLength = makeNewEffect();
   }
 
   Expression traverseLetHandler(LetHandler node) {
     // Assume any kind of side effects may occur in the try block.
-    effectsAt[node.handler] = new EffectNumbers.fresh(effectNumberer);
+    effectsAt[node.handler] = new EffectNumbers()
+      ..instanceField = makeNewEffect()
+      ..staticField = makeNewEffect()
+      ..indexableContent = makeNewEffect()
+      ..indexableLength = makeNewEffect();
     push(node.handler);
     return node.body;
   }
 
   Expression traverseContinuation(Continuation cont) {
     Continuation oldLoopHeader = currentLoopHeader;
     currentLoopHeader = loopHierarchy.getLoopHeader(cont);
     pushAction(() {
       currentLoopHeader = oldLoopHeader;
     });
     for (Parameter param in cont.parameters) {
       loopHeaderFor[param] = currentLoopHeader;
     }
     if (cont.isRecursive) {
-      addSideEffects(loopEffects.getSideEffectsInLoop(cont));
+      addSideEffects(loopEffects.getSideEffectsInLoop(cont), length: false);
+      if (loopEffects.loopChangesLength(cont)) {
+        effectNumbers.indexableLength = makeNewEffect();
+      }
       pushAction(() {
         List<int> hoistedBindings = loopHoistedBindings[cont];
         if (hoistedBindings != null) {
           hoistedBindings.forEach(environment.remove);
         }
       });
     } else {
-      effectNumbers = effectsAt[cont];
-      assert(effectNumbers != null);
+      EffectNumbers join = effectsAt[cont];
+      if (join != null) {
+        effectNumbers = join;
+      } else {
+        // This is a call continuation seen immediately after its use.
+        // Reuse the current effect numbers.
+      }
     }
 
     return cont.body;
   }
 
   void visitInvokeContinuation(InvokeContinuation node) {
     Continuation cont = node.continuation.definition;
     if (cont.isRecursive) return;
     EffectNumbers join = effectsAt[cont];
     if (join == null) {
       effectsAt[cont] = effectNumbers.copy();
     } else {
-      join.join(effectNumberer, effectNumbers);
+      if (effectNumbers.instanceField != join.instanceField) {
+        join.instanceField = makeNewEffect();
+      }
+      if (effectNumbers.staticField != join.staticField) {
+        join.staticField = makeNewEffect();
+      }
+      if (effectNumbers.indexableContent != join.indexableContent) {
+        join.indexableContent = makeNewEffect();
+      }
+      if (effectNumbers.indexableLength != join.indexableLength) {
+        join.indexableLength = makeNewEffect();
+      }
     }
   }
 
   void visitBranch(Branch node) {
     Continuation trueCont = node.trueContinuation.definition;
     Continuation falseCont = node.falseContinuation.definition;
     // Copy the effect number vector once, so the analysis of one branch does
     // not influence the other.
     effectsAt[trueCont] = effectNumbers;
     effectsAt[falseCont] = effectNumbers.copy();
   }
+
+  void visitInvokeMethod(InvokeMethod node) {
+    addSideEffects(world.getSideEffectsOfSelector(node.selector, node.mask));
+  }
+
+  void visitInvokeStatic(InvokeStatic node) {
+    addSideEffects(world.getSideEffectsOfElement(node.target));
+  }
+
+  void visitInvokeMethodDirectly(InvokeMethodDirectly node) {
+    FunctionElement target = node.target;
+    if (target is ConstructorBodyElement) {
+      ConstructorBodyElement body = target;
+      target = body.constructor;
+    }
+    addSideEffects(world.getSideEffectsOfElement(target));
+  }
+
+  void visitInvokeConstructor(InvokeConstructor node) {
+    addSideEffects(world.getSideEffectsOfElement(node.target));
+  }
+
+  void visitSetStatic(SetStatic node) {
+    effectNumbers.staticField = makeNewEffect();
+  }
+
+  void visitSetField(SetField node) {
+    effectNumbers.instanceField = makeNewEffect();
+  }
+
+  void visitSetIndex(SetIndex node) {
+    effectNumbers.indexableContent = makeNewEffect();
+  }
+
+  void visitForeignCode(ForeignCode node) {
+    addSideEffects(node.nativeBehavior.sideEffects);
+  }
+
+  void visitGetLazyStatic(GetLazyStatic node) {
+    // TODO(asgerf): How do we get the side effects of a lazy field initializer?
+    addAllSideEffects();
+  }
+
+  void visitAwait(Await node) {
+    addAllSideEffects();
+  }
+
+  void visitYield(Yield node) {
+    addAllSideEffects();
+  }
+
+  void visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
+    // Push and pop.
+    effectNumbers.indexableContent = makeNewEffect();
+    effectNumbers.indexableLength = makeNewEffect();
+  }
+}
+
+/// For each of the four categories of heap locations, the IR is divided into
+/// regions wherein the given heap locations are known not to be modified.
+///
+/// Each region is identified by its "effect number".  Effect numbers from
+/// different categories have no relationship to each other.
+class EffectNumbers {
+  int indexableLength = 0;
+  int indexableContent = 0;
+  int staticField = 0;
+  int instanceField = 0;
+
+  EffectNumbers copy() {
+    return new EffectNumbers()
+      ..indexableLength = indexableLength
+      ..indexableContent = indexableContent
+      ..staticField = staticField
+      ..instanceField = instanceField;
+  }
 }
 
 /// Maps vectors to numbers, such that two vectors with the same contents
 /// map to the same number.
 class GvnTable {
   Map<GvnEntry, int> _table = <GvnEntry, int>{};
   int _usedGvns = 0;
   int _makeNewGvn() => ++_usedGvns;
 
   int insert(List vector) {
@@ skipping 77 matching lines @@
 
   processTypeTestViaFlag(TypeTestViaFlag node) {
     vector = [GvnCode.TYPE_TEST_VIA_FLAG, node.dartType];
   }
 
   processApplyBuiltinOperator(ApplyBuiltinOperator node) {
     vector = [GvnCode.BUILTIN_OPERATOR, node.operator.index];
   }
 
   processGetLength(GetLength node) {
-    if (node.isFinal) {
+    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 && 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.
-    } else if (node.isFinal) {
+    } else if (isImmutable(node.field)) {
       vector = [GvnCode.GET_FIELD, node.field];
     } else {
       vector = [GvnCode.GET_FIELD, node.field, effectNumbers.instanceField];
     }
   }
 
   processGetIndex(GetIndex node) {
     vector = [GvnCode.GET_INDEX, effectNumbers.indexableContent];
   }
 
   visitGetStatic(GetStatic node) {
-    if (node.isFinal) {
+    if (isImmutable(node.element)) {
       vector = [GvnCode.GET_STATIC, node.element];
     } else {
       vector = [GvnCode.GET_STATIC, node.element, effectNumbers.staticField];
     }
     // Suppress visit to witness argument.
   }
 
   processGetLazyStatic(GetLazyStatic node) {
-    if (node.isFinal) {
+    if (isImmutable(node.element)) {
       vector = [GvnCode.GET_STATIC, node.element];
     } else {
       vector = [GvnCode.GET_STATIC, node.element, effectNumbers.staticField];
     }
   }
 
   processConstant(Constant node) {
     vector = [GvnCode.CONSTANT, node.value];
   }
 
@@ skipping 37 matching lines @@
 
   @override
   processReference(Reference ref) {
     callback(ref);
   }
 
   static void forEach(Primitive node, ReferenceCallback callback) {
     new InputVisitor(callback).visit(node);
   }
 }