Create and use new change/depends flags for the GVN analysis.

lib/compiler/implementation/ssa/nodes.dart

 // Copyright (c) 2012, 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.
 
 abstract class HVisitor<R> {
   R visitAdd(HAdd node);
   R visitBailoutTarget(HBailoutTarget node);
   R visitBitAnd(HBitAnd node);
   R visitBitNot(HBitNot node);
   R visitBitOr(HBitOr node);
@@ skipping 739 matching lines @@
 
   final List<HInstruction> inputs;
   final List<HInstruction> usedBy;
 
   HBasicBlock block;
   HInstruction previous = null;
   HInstruction next = null;
   int flags = 0;
 
   // Changes flags.
-  static const int FLAG_CHANGES_SOMETHING    = 0;
-  static const int FLAG_CHANGES_COUNT        = FLAG_CHANGES_SOMETHING + 1;
+  static const int FLAG_CHANGES_INDEX             = 0;
+  static const int FLAG_CHANGES_PROPERTY          = FLAG_CHANGES_INDEX + 1;
+  static const int FLAG_CHANGES_STATIC            = FLAG_CHANGES_PROPERTY + 1;

[Søren Gjesse, 2012/10/01 07:22:20]

How about FLAG_CHANGES_STATIC_PROPERTY (and then maybe
FLAG_CHANGES_OBJECT_PROPERTY above)? - or will that be too long?

[ngeoffray, 2012/10/04 10:41:42]

Done.

+  static const int FLAG_CHANGES_SOMETHING         = FLAG_CHANGES_STATIC + 1;
+  static const int FLAG_CHANGES_COUNT             = FLAG_CHANGES_SOMETHING + 1;
 
   // Depends flags (one for each changes flag).
-  static const int FLAG_DEPENDS_ON_SOMETHING = FLAG_CHANGES_COUNT;
+  static const int FLAG_DEPENDS_ON_INDEX_STORE = FLAG_CHANGES_COUNT;
+  static const int FLAG_DEPENDS_ON_PROPERTY_STORE =
+      FLAG_DEPENDS_ON_INDEX_STORE + 1;
+  static const int FLAG_DEPENDS_ON_STATIC = FLAG_DEPENDS_ON_PROPERTY_STORE + 1;
+  static const int FLAG_DEPENDS_ON_SOMETHING = FLAG_DEPENDS_ON_STATIC + 1;
 
   // Other flags.
   static const int FLAG_USE_GVN              = FLAG_DEPENDS_ON_SOMETHING + 1;
 
   // Type codes.
   static const int UNDEFINED_TYPECODE = -1;
   static const int BOOLIFY_TYPECODE = 0;
   static const int TYPE_GUARD_TYPECODE = 1;
   static const int BOUNDS_CHECK_TYPECODE = 2;
   static const int INTEGER_CHECK_TYPECODE = 3;
@@ skipping 18 matching lines @@
   static const int GREATER_EQUAL_TYPECODE = 22;
   static const int LESS_TYPECODE = 23;
   static const int LESS_EQUAL_TYPECODE = 24;
   static const int STATIC_TYPECODE = 25;
   static const int STATIC_STORE_TYPECODE = 26;
   static const int FIELD_GET_TYPECODE = 27;
   static const int TYPE_CONVERSION_TYPECODE = 28;
   static const int BAILOUT_TARGET_TYPECODE = 29;
   static const int INVOKE_STATIC_TYPECODE = 30;
   static const int INVOKE_DYNAMIC_GETTER_TYPECODE = 31;
+  static const int INDEX_TYPECODE = 32;
 
   HInstruction(this.inputs)
       : id = idCounter++,
         usedBy = <HInstruction>[];
 
   int hashCode() => id;
 
   bool getFlag(int position) => (flags & (1 << position)) != 0;
   void setFlag(int position) { flags |= (1 << position); }
   void clearFlag(int position) { flags &= ~(1 << position); }
 
   static int computeDependsOnFlags(int flags) => flags << FLAG_CHANGES_COUNT;
 
   int getChangesFlags() => flags & ((1 << FLAG_CHANGES_COUNT) - 1);
   bool hasSideEffects(HTypeMap types) => getChangesFlags() != 0;
   void prepareGvn(HTypeMap types) { setAllSideEffects(); }
 
   void setAllSideEffects() { flags |= ((1 << FLAG_CHANGES_COUNT) - 1); }
   void clearAllSideEffects() { flags &= ~((1 << FLAG_CHANGES_COUNT) - 1); }
 
   bool dependsOnSomething() => getFlag(FLAG_DEPENDS_ON_SOMETHING);
   void setDependsOnSomething() { setFlag(FLAG_DEPENDS_ON_SOMETHING); }
 
+  bool dependsOnStatic() => getFlag(FLAG_DEPENDS_ON_STATIC);

[Søren Gjesse, 2012/10/01 07:22:20]

dependsOnStaticPropertyStore?

[ngeoffray, 2012/10/04 10:41:42]

Done.

+  void setDependsOnStatic() { setFlag(FLAG_DEPENDS_ON_STATIC); }
+  void setChangesStatic() { setFlag(FLAG_CHANGES_STATIC); }
+
+  bool dependsOnIndexStore() => getFlag(FLAG_DEPENDS_ON_INDEX_STORE);
+  void setDependsOnIndexStore() { setFlag(FLAG_DEPENDS_ON_INDEX_STORE); }
+  void setChangesIndex() { setFlag(FLAG_CHANGES_INDEX); }
+
+  bool dependsOnPropertyStore() => getFlag(FLAG_DEPENDS_ON_PROPERTY_STORE);
+  void setDependsOnPropertyStore() { setFlag(FLAG_DEPENDS_ON_PROPERTY_STORE); }
+  void setChangesProperty() { setFlag(FLAG_CHANGES_PROPERTY); }
+
   bool useGvn() => getFlag(FLAG_USE_GVN);
   void setUseGvn() { setFlag(FLAG_USE_GVN); }
   // Does this node potentially affect control flow.
   bool isControlFlow() => false;
 
   // All isFunctions work on the propagated types.
   bool isArray(HTypeMap types) => types[this].isArray();
   bool isReadableArray(HTypeMap types) => types[this].isReadableArray();
   bool isMutableArray(HTypeMap types) => types[this].isMutableArray();
   bool isExtendableArray(HTypeMap types) => types[this].isExtendableArray();
@@ skipping 455 matching lines @@
 }
 
 class HInvokeDynamicMethod extends HInvokeDynamic {
   HInvokeDynamicMethod(Selector selector, List<HInstruction> inputs)
     : super(selector, null, inputs);
   toString() => 'invoke dynamic method: $selector';
   accept(HVisitor visitor) => visitor.visitInvokeDynamicMethod(this);
 }
 
 class HInvokeDynamicField extends HInvokeDynamic {
-  HInvokeDynamicField(Selector selector, Element element,
-                      List<HInstruction> inputs)
+  final bool isSideEffectFree;
+  HInvokeDynamicField(
+      Selector selector, Element element, List<HInstruction> inputs,
+      this.isSideEffectFree)
       : super(selector, element, inputs);
   toString() => 'invoke dynamic field: $selector';
 
   // TODO(floitsch): make class abstract instead of adding an abstract method.
   abstract accept(HVisitor visitor);
 }
 
 class HInvokeDynamicGetter extends HInvokeDynamicField {
-  final bool isSideEffectFree;
   HInvokeDynamicGetter(
-      selector, element, receiver, this.isSideEffectFree)
-    : super(selector, element,[receiver]);
+      selector, element, receiver, isSideEffectFree)
+    : super(selector, element, [receiver], isSideEffectFree);
   toString() => 'invoke dynamic getter: $selector';
   accept(HVisitor visitor) => visitor.visitInvokeDynamicGetter(this);
 
   void prepareGvn(HTypeMap types) {
     if (isSideEffectFree) {
       setUseGvn();
       clearAllSideEffects();
-      setDependsOnSomething();
+      setDependsOnPropertyStore();
     } else {
       setAllSideEffects();
     }
   }
 
   int typeCode() => HInstruction.INVOKE_DYNAMIC_GETTER_TYPECODE;
   bool typeEquals(other) => other is HInvokeDynamicGetter;
   bool dataEquals(HInvokeDynamicGetter other) => selector == other.selector;
 }
 
 class HInvokeDynamicSetter extends HInvokeDynamicField {
-  HInvokeDynamicSetter(selector, element, receiver, value)
-    : super(selector, element, [receiver, value]);
+  HInvokeDynamicSetter(selector, element, receiver, value, isSideEffectFree)
+    : super(selector, element, [receiver, value], isSideEffectFree);
   toString() => 'invoke dynamic setter: $selector';
   accept(HVisitor visitor) => visitor.visitInvokeDynamicSetter(this);
+
+  void prepareGvn(HTypeMap types) {
+    if (isSideEffectFree) {
+      setChangesProperty();
+    } else {
+      setAllSideEffects();
+    }
+  }
 }
 
 class HInvokeStatic extends HInvoke {
   /** The first input must be the target. */
   HInvokeStatic(inputs, [HType knownType = HType.UNKNOWN]) : super(inputs) {
     guaranteedType = knownType;
   }
 
   toString() => 'invoke static: ${element.name}';
   accept(HVisitor visitor) => visitor.visitInvokeStatic(this);
@@ skipping 81 matching lines @@
   }
 
   void prepareGvn(HTypeMap types) {
     if (isLengthGetterOnStringOrArray(types)) {
       setUseGvn();
       clearAllSideEffects();
       // If the input is a string, we know the length cannot change.
       // We cannot do the same thing for non-extendable array because
       // we don't express that type yet: a mutable array might be
       // extendable.
-      if (!inputs[1].isString(types)) setDependsOnSomething();
+      if (!inputs[1].isString(types)) setDependsOnPropertyStore();
     } else if (isSideEffectFree) {
       setUseGvn();
       clearAllSideEffects();
       setDependsOnSomething();
+    } else if (selector.isGetter()) {
+      // Getter interceptors do not have side effects.

[floitsch, 2012/10/01 08:40:30]

I don't think this is true.
o.length is an HInvokeInterceptor, but you can't be sure that it won't have a
side-effect.

[ngeoffray, 2012/10/01 21:56:10]

Right, I was only thinking about getters on primitive types. Code removed.

+      setUseGvn();
+      clearAllSideEffects();
+      setDependsOnPropertyStore();
     } else {
       setAllSideEffects();
     }
   }
 
   int typeCode() => HInstruction.INVOKE_INTERCEPTOR_TYPECODE;
   bool typeEquals(other) => other is HInvokeInterceptor;
   bool dataEquals(HInvokeInterceptor other) => selector == other.selector;
 }
 
@@ skipping 14 matching lines @@
             : element.isAssignable(),
         super(element, <HInstruction>[receiver]);
 
   HInstruction get receiver => inputs[0];
 
   accept(HVisitor visitor) => visitor.visitFieldGet(this);
 
   void prepareGvn(HTypeMap types) {
     setUseGvn();
     clearAllSideEffects();
-    if (isAssignable) setDependsOnSomething();
+    if (isAssignable) {
+      setDependsOnPropertyStore();
+    }
   }
 
   int typeCode() => HInstruction.FIELD_GET_TYPECODE;
   bool typeEquals(other) => other is HFieldGet;
   bool dataEquals(HFieldGet other) => element == other.element;
   String toString() => "FieldGet $element";
 }
 
 class HFieldSet extends HFieldAccess {
   HFieldSet(Element element,
             HInstruction receiver,
             HInstruction value)
       : super(element, <HInstruction>[receiver, value]);
 
   HInstruction get receiver => inputs[0];
   HInstruction get value => inputs[1];
   accept(HVisitor visitor) => visitor.visitFieldSet(this);
 
   void prepareGvn(HTypeMap types) {
-    // TODO(ngeoffray): implement more fine grained side effects.
-    setAllSideEffects();
+    setChangesProperty();
   }
 
   bool isJsStatement(HTypeMap types) => true;
   String toString() => "FieldSet $element";
 }
 
 class HLocalGet extends HFieldGet {
   HLocalGet(Element element, HLocalValue local) : super(element, local);
 
   accept(HVisitor visitor) => visitor.visitLocalGet(this);
 
   HLocalValue get local => inputs[0];
-
-  void prepareGvn(HTypeMap types) {
-    setUseGvn();
-    // TODO(floitsch): if the variable is not captured then it only depends
-    // on assignments to the same variable. Otherwise we need to see if the
-    // variable is mutated inside closures.
-    setDependsOnSomething();
-  }
 }
 
 class HLocalSet extends HFieldSet {
   HLocalSet(Element element, HLocalValue local, HInstruction value)
       : super(element, local, value);
 
   accept(HVisitor visitor) => visitor.visitLocalSet(this);
 
   HLocalValue get local => inputs[0];
-
-  void prepareGvn(HTypeMap types) {
-    // TODO(floitsch): implement more fine grained side effects.
-    setAllSideEffects();
-  }
 }
 
 class HForeign extends HInstruction {
   final DartString code;
   final HType foreignType;
   final bool _isStatement;
 
   HForeign(this.code, DartString declaredType, List<HInstruction> inputs)
       : foreignType = computeTypeFromDeclaredType(declaredType),
         _isStatement = false,
@@ skipping 827 matching lines @@
 class HStatic extends HInstruction {
   final Element element;
   HStatic(this.element) : super(<HInstruction>[]) {
     assert(element !== null);
     assert(invariant(this, element.isDeclaration));
   }
 
   void prepareGvn(HTypeMap types) {
     if (!element.isAssignable()) {
       clearAllSideEffects();
-      setUseGvn();
+    } else {
+      setDependsOnStatic();
     }
+    setUseGvn();
   }
   toString() => 'static ${element.name}';
   accept(HVisitor visitor) => visitor.visitStatic(this);
 
   int gvnHashCode() => super.gvnHashCode() ^ element.hashCode();
   int typeCode() => HInstruction.STATIC_TYPECODE;
   bool typeEquals(other) => other is HStatic;
   bool dataEquals(HStatic other) => element == other.element;
   bool isCodeMotionInvariant() => !element.isAssignable();
 }
@@ skipping 19 matching lines @@
 class HStaticStore extends HInstruction {
   Element element;
   HStaticStore(this.element, HInstruction value) : super(<HInstruction>[value]);
   toString() => 'static store ${element.name}';
   accept(HVisitor visitor) => visitor.visitStaticStore(this);
 
   int typeCode() => HInstruction.STATIC_STORE_TYPECODE;
   bool typeEquals(other) => other is HStaticStore;
   bool dataEquals(HStaticStore other) => element == other.element;
   bool isJsStatement(HTypeMap types) => true;
+
+  void prepareGvn(HTypeMap types) {
+    setChangesStatic();
+  }
 }
 
 class HLiteralList extends HInstruction {
   HLiteralList(inputs) : super(inputs);
   toString() => 'literal list';
   accept(HVisitor visitor) => visitor.visitLiteralList(this);
 
   HType get guaranteedType => HType.EXTENDABLE_ARRAY;
 
   void prepareGvn(HTypeMap types) {
     assert(!hasSideEffects(types));
   }
 }
 
 class HIndex extends HInvokeStatic {
   HIndex(HStatic target, HInstruction receiver, HInstruction index)
       : super(<HInstruction>[target, receiver, index]);
   toString() => 'index operator';
   accept(HVisitor visitor) => visitor.visitIndex(this);
 
   void prepareGvn(HTypeMap types) {
     if (isBuiltin(types)) {
       clearAllSideEffects();
+      setDependsOnIndexStore();
+      setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
   HInstruction get receiver => inputs[1];
   HInstruction get index => inputs[2];
 
   HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                             HTypeMap types) {
     if (input == receiver &&
         (index.isTypeUnknown(types) || index.isNumber(types))) {
       return HType.INDEXABLE_PRIMITIVE;
     }
     // The index should be an int when the receiver is a string or array.
     // However it turns out that inserting an integer check in the optimized
     // version is cheaper than having another bailout case. This is true,
     // because the integer check will simply throw if it fails.
     return HType.UNKNOWN;
   }
 
   bool isBuiltin(HTypeMap types)
       => receiver.isIndexablePrimitive(types) && index.isInteger(types);
+
+  int typeCode() => HInstruction.INDEX_TYPECODE;
+  bool typeEquals(HInstruction other) => other is HIndex;
+  bool dataEquals(HIndex other) => true;
 }
 
 class HIndexAssign extends HInvokeStatic {
   HIndexAssign(HStatic target,
                HInstruction receiver,
                HInstruction index,
                HInstruction value)
       : super(<HInstruction>[target, receiver, index, value]);
   toString() => 'index assign operator';
   accept(HVisitor visitor) => visitor.visitIndexAssign(this);
 
   HInstruction get receiver => inputs[1];
   HInstruction get index => inputs[2];
   HInstruction get value => inputs[3];
 
+  void prepareGvn(HTypeMap types) {
+    if (isBuiltin(types)) {
+      setChangesIndex();
+    } else {
+      setAllSideEffects();
+    }
+  }
+
   // Note, that we don't have a computeTypeFromInputTypes, since [HIndexAssign]
   // is never used as input.
 
   HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                             HTypeMap types) {
     if (input == receiver &&
         (index.isTypeUnknown(types) || index.isNumber(types))) {
       return HType.MUTABLE_ARRAY;
     }
     // The index should be an int when the receiver is a string or array.
@@ skipping 424 matching lines @@
   HBasicBlock get start => expression.start;
   HBasicBlock get end {
     // We don't create a switch block if there are no cases.
     assert(!statements.isEmpty());
     return statements.last().end;
   }
 
   bool accept(HStatementInformationVisitor visitor) =>
       visitor.visitSwitchInfo(this);
 }