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 571 matching lines @@
 
   void addSuccessor(HBasicBlock block) {
     if (successors.isEmpty()) {
       successors = [block];
     } else {
       successors.add(block);
     }
     block.predecessors.add(this);
   }
 
+  void removeSuccessor(HBasicBlock successor) {
+    successors.removeAt(successors.indexOf(successor));
+    successor.predecessors.removeAt(successors.predecessors.indexOf(this));
+  }
+
   void postProcessLoopHeader() {
     assert(isLoopHeader());
     // Only the first entry into the loop is from outside the
     // loop. All other entries must be back edges.
     for (int i = 1, length = predecessors.length; i < length; i++) {
       loopInformation.addBackEdge(predecessors[i]);
     }
   }
 
   /**
@@ skipping 148 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_INSTANCE_PROPERTY = FLAG_CHANGES_INDEX + 1;
+  static const int FLAG_CHANGES_STATIC_PROPERTY
+      = FLAG_CHANGES_INSTANCE_PROPERTY + 1;
+  static const int FLAG_CHANGES_SOMETHING = FLAG_CHANGES_STATIC_PROPERTY + 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_INSTANCE_PROPERTY_STORE =
+      FLAG_DEPENDS_ON_INDEX_STORE + 1;
+  static const int FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE =
+      FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE + 1;
+  static const int FLAG_DEPENDS_ON_SOMETHING =
+      FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE + 1;
 
   // Other flags.
-  static const int FLAG_USE_GVN              = FLAG_DEPENDS_ON_SOMETHING + 1;
+  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;
   static const int INVOKE_INTERCEPTOR_TYPECODE = 4;
   static const int ADD_TYPECODE = 5;
   static const int DIVIDE_TYPECODE = 6;
@@ skipping 15 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 dependsOnStaticPropertyStore() {
+    return getFlag(FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE);
+  }
+  void setDependsOnStaticPropertyStore() {
+    setFlag(FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE);
+  }
+  void setChangesStaticProperty() { setFlag(FLAG_CHANGES_STATIC_PROPERTY); }
+
+  bool dependsOnIndexStore() => getFlag(FLAG_DEPENDS_ON_INDEX_STORE);
+  void setDependsOnIndexStore() { setFlag(FLAG_DEPENDS_ON_INDEX_STORE); }
+  void setChangesIndex() { setFlag(FLAG_CHANGES_INDEX); }
+
+  bool dependsOnInstancePropertyStore() {
+    return getFlag(FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE);
+  }
+  void setDependsOnInstancePropertyStore() {
+    setFlag(FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE);
+  }
+  void setChangesInstanceProperty() { setFlag(FLAG_CHANGES_INSTANCE_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 456 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);
 }
 
 abstract 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) {
+    clearAllSideEffects();
     if (isSideEffectFree) {
       setUseGvn();
-      clearAllSideEffects();
-      setDependsOnSomething();
+      setDependsOnInstancePropertyStore();
     } 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) {
+    clearAllSideEffects();
+    if (isSideEffectFree) {
+      setChangesInstanceProperty();
+    } 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 74 matching lines @@
       // TODO(kasperl): Should we check that the selector is a call selector?
       if (selector.name == const SourceString('add')
           || selector.name == const SourceString('removeLast')) {
         return HType.MUTABLE_ARRAY;
       }
     }
     return HType.UNKNOWN;
   }
 
   void prepareGvn(HTypeMap types) {
+    clearAllSideEffects();
     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)) setDependsOnInstancePropertyStore();
     } else if (isSideEffectFree) {
       setUseGvn();
-      clearAllSideEffects();
       setDependsOnSomething();
     } else {
       setAllSideEffects();
     }
   }
 
   int typeCode() => HInstruction.INVOKE_INTERCEPTOR_TYPECODE;
   bool typeEquals(other) => other is HInvokeInterceptor;
   bool dataEquals(HInvokeInterceptor other) => selector == other.selector;
 }
@@ skipping 13 matching lines @@
       : this.isAssignable = (isAssignable !== null)
             ? isAssignable
             : element.isAssignable(),
         super(element, <HInstruction>[receiver]);
 
   HInstruction get receiver => inputs[0];
 
   accept(HVisitor visitor) => visitor.visitFieldGet(this);
 
   void prepareGvn(HTypeMap types) {
+    clearAllSideEffects();
     setUseGvn();
-    clearAllSideEffects();
-    if (isAssignable) setDependsOnSomething();
+    if (isAssignable) {
+      setDependsOnInstancePropertyStore();
+    }
   }
 
   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();
+    clearAllSideEffects();
+    setChangesInstanceProperty();
   }
 
   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 35 matching lines @@
 
   abstract BinaryOperation operation(ConstantSystem constantSystem);
   abstract isBuiltin(HTypeMap types);
 }
 
 abstract class HBinaryArithmetic extends HInvokeBinary {
   HBinaryArithmetic(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
 
   void prepareGvn(HTypeMap types) {
+    clearAllSideEffects();
     // An arithmetic expression can take part in global value
     // numbering and do not have any side-effects if we know that all
     // inputs are numbers.
     if (isBuiltin(types)) {
-      clearAllSideEffects();
       setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
   bool isBuiltin(HTypeMap types)
       => left.isNumber(types) && right.isNumber(types);
 
   HType computeTypeFromInputTypes(HTypeMap types) {
@@ skipping 251 matching lines @@
   bool dataEquals(HInstruction other) => true;
 }
 
 abstract class HInvokeUnary extends HInvokeStatic {
   HInvokeUnary(HStatic target, HInstruction input)
       : super(<HInstruction>[target, input]);
 
   HInstruction get operand => inputs[1];
 
   void prepareGvn(HTypeMap types) {
+    clearAllSideEffects();
     // A unary arithmetic expression can take part in global value
     // numbering and does not have any side-effects if its input is a
     // number.
     if (isBuiltin(types)) {
-      clearAllSideEffects();
       setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
   bool isBuiltin(HTypeMap types) => operand.isNumber(types);
 
   HType computeTypeFromInputTypes(HTypeMap types) {
     HType operandType = types[operand];
@@ skipping 304 matching lines @@
   toString() => 'phi';
   accept(HVisitor visitor) => visitor.visitPhi(this);
 }
 
 abstract class HRelational extends HInvokeBinary {
   bool usesBoolifiedInterceptor = false;
   HRelational(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
 
   void prepareGvn(HTypeMap types) {
+    clearAllSideEffects();
     // Relational expressions can take part in global value numbering
     // and do not have any side-effects if we know all the inputs are
     // numbers. This can be improved for at least equality.
     if (isBuiltin(types)) {
-      clearAllSideEffects();
       setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
   HType computeTypeFromInputTypes(HTypeMap types) {
     if (left.isNumber(types) || usesBoolifiedInterceptor) return HType.BOOLEAN;
     return HType.UNKNOWN;
   }
@@ skipping 159 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();
+    clearAllSideEffects();
+    if (element.isAssignable()) {
+      setDependsOnStaticPropertyStore();
     }
+    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) {
+    clearAllSideEffects();
+    setChangesStaticProperty();
+  }
 }
 
 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) {
+    clearAllSideEffects();
     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) {
+    clearAllSideEffects();
+    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);
 }