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

pkg/compiler/lib/src/cps_ir/gvn.dart

Index: pkg/compiler/lib/src/cps_ir/gvn.dart
diff --git a/pkg/compiler/lib/src/cps_ir/gvn.dart b/pkg/compiler/lib/src/cps_ir/gvn.dart
index 4d57744558b33062ce407edb853f1810a1579099..46f5d936ca7e65cf81570ffe4ccaece32f05a88e 100644
--- a/pkg/compiler/lib/src/cps_ir/gvn.dart
+++ b/pkg/compiler/lib/src/cps_ir/gvn.dart
@@ -15,7 +15,6 @@ 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
@@ -37,6 +36,11 @@ import 'effects.dart';
 //    - 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';
 
@@ -50,13 +54,11 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
   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 =
@@ -78,8 +80,10 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
 
   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 =
@@ -121,7 +125,7 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
     // 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.
@@ -131,7 +135,7 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
     // 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) {
@@ -343,6 +347,18 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
     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.
@@ -353,26 +369,56 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
     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;
   }
@@ -387,7 +433,10 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
       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) {
@@ -395,8 +444,13 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
         }
       });
     } 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;
@@ -409,7 +463,18 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
     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();
+      }
     }
   }
 
@@ -421,6 +486,82 @@ class GVN extends TrampolineRecursiveVisitor implements Pass {
     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
@@ -518,7 +659,7 @@ class GvnVectorBuilder extends DeepRecursiveVisitor {
   }
 
   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
@@ -529,6 +670,16 @@ class GvnVectorBuilder extends DeepRecursiveVisitor {
     }
   }
 
+  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);
@@ -537,7 +688,7 @@ class GvnVectorBuilder extends DeepRecursiveVisitor {
   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];
@@ -549,7 +700,7 @@ class GvnVectorBuilder extends DeepRecursiveVisitor {
   }
 
   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];
@@ -558,7 +709,7 @@ class GvnVectorBuilder extends DeepRecursiveVisitor {
   }
 
   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];