Refactor type propagation.

lib/compiler/implementation/ssa/nodes.dart

 // Copyright (c) 2011, 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.
 
 interface HVisitor<R> {
   R visitAdd(HAdd node);
   R visitBitAnd(HBitAnd node);
   R visitBitNot(HBitNot node);
   R visitBitOr(HBitOr node);
   R visitBitXor(HBitXor node);
@@ skipping 770 matching lines @@
   bool isUnknown() => this === UNKNOWN;
   bool isBoolean() => this === BOOLEAN;
   bool isInteger() => this === INTEGER;
   bool isDouble() => this === DOUBLE;
   bool isString() => this === STRING;
   bool isArray() => (this.flag & FLAG_READABLE_ARRAY) != 0;
   bool isMutableArray() => this === MUTABLE_ARRAY;
   bool isNumber() => (this.flag & (FLAG_INTEGER | FLAG_DOUBLE)) != 0;
   bool isStringOrArray() =>
       (this.flag & (FLAG_STRING | FLAG_READABLE_ARRAY)) != 0;
-  bool isKnown() => this !== UNKNOWN && this !== CONFLICTING;
+  /** A type is useful it is not unknown and not conflicting. */
+  bool isUseful() => this !== UNKNOWN && this !== CONFLICTING;
 
   static HType getTypeFromFlag(int flag) {
     if (flag === CONFLICTING.flag) return CONFLICTING;
     if (flag === UNKNOWN.flag) return UNKNOWN;
     if (flag === BOOLEAN.flag) return BOOLEAN;
     if (flag === INTEGER.flag) return INTEGER;
     if (flag === DOUBLE.flag) return DOUBLE;
     if (flag === STRING.flag) return STRING;
     if (flag === READABLE_ARRAY.flag) return READABLE_ARRAY;
     if (flag === MUTABLE_ARRAY.flag) return MUTABLE_ARRAY;
@@ skipping 27 matching lines @@
   final int id;
   static int idCounter;
 
   final List<HInstruction> inputs;
   final List<HInstruction> usedBy;
 
   HBasicBlock block;
   HInstruction previous = null;
   HInstruction next = null;
   int flags = 0;
-  HType type = HType.UNKNOWN;
 
   // Changes flags.
   static final int FLAG_CHANGES_SOMETHING    = 0;
   static final int FLAG_CHANGES_COUNT        = FLAG_CHANGES_SOMETHING + 1;
 
   // Depends flags (one for each changes flag).
   static final int FLAG_DEPENDS_ON_SOMETHING = FLAG_CHANGES_COUNT;
 
   // Other flags.
   static final int FLAG_USE_GVN              = FLAG_DEPENDS_ON_SOMETHING + 1;
 
-  HInstruction(this.inputs) : id = idCounter++, usedBy = <HInstruction>[];
+  HInstruction(this.inputs)
+      : id = idCounter++,
+        usedBy = <HInstruction>[] {
+    if (guaranteedType.isUseful()) propagatedType = guaranteedType;
+  }
 
   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() => getChangesFlags() != 0;
   void prepareGvn() { setAllSideEffects(); }
 
   void setAllSideEffects() { flags |= ((1 << FLAG_CHANGES_COUNT) - 1); }
   void clearAllSideEffects() { flags &= ~((1 << FLAG_CHANGES_COUNT) - 1); }
 
   bool useGvn() => getFlag(FLAG_USE_GVN);
   void setUseGvn() { setFlag(FLAG_USE_GVN); }
   // Does this node potentially affect control flow.
   bool isControlFlow() => false;
 
-  bool isArray() => type.isArray();
-  bool isMutableArray() => type.isMutableArray();
-  bool isBoolean() => type.isBoolean();
-  bool isInteger() => type.isInteger();
-  bool isNumber() => type.isNumber();
-  bool isString() => type.isString();
-  bool isTypeUnknown() => type.isUnknown();
-  bool isStringOrArray() => type.isStringOrArray();
+  // All isFunctions work on the propagated types.
+  bool isArray() => propagatedType.isArray();
+  bool isMutableArray() => propagatedType.isMutableArray();
+  bool isBoolean() => propagatedType.isBoolean();
+  bool isInteger() => propagatedType.isInteger();
+  bool isDouble() => propagatedType.isDouble();
+  bool isNumber() => propagatedType.isNumber();
+  bool isString() => propagatedType.isString();
+  bool isTypeUnknown() => propagatedType.isUnknown();
+  bool isStringOrArray() => propagatedType.isStringOrArray();
 
-  // Compute the type of the instruction.
-  HType computeType() => HType.UNKNOWN;
+  /**
+   * This is the type the instruction is guaranteed to have. It does not
+   * take any propagation into account.
+   */
+  HType get guaranteedType() => HType.UNKNOWN;
+  bool hasGuaranteedType() => !guaranteedType.isUnknown();
 
-  HType computeDesiredInputType(HInstruction input) => HType.UNKNOWN;
+  /**
+   * The [propagatedType] is the type the instruction is assumed to have.
+   * Without speculative type assumptions it is computed frome the propagated
+   * type of the instruction's inputs and does not any guess work.
+   *
+   * With speculative types [computeTypeFromInputTypes()] and [propagatedType]
+   * may differ. In this case the instruction's type must be guarded.
+   *
+   * Note that the [propagatedType] may only be set to [HType.CONFLICTING] with
+   * speculative types (as otherwise the instruction either sets the output
+   * type to [HType.UNKNOWN] or a specific type.
+   */
+  HType propagatedType = HType.UNKNOWN;
 
-  // Returns whether the instruction does produce the type it claims.
-  // For most instructions, this returns false. A type guard will be
-  // inserted to make sure the users get the right type in.
-  bool hasExpectedType() => false;
+  /**
+   * Some instructions have a good idea of their return type, but cannot
+   * guarantee the type. The [likelyType] does not need to be more specialized
+   * than the [propagatedType]. 
+   *
+   * Examples: the [likelyType] of [:x == y:] is a boolean. In most cases this
+   * cannot be guaranteed, but when merging types we still want to use this
+   * information.
+   *
+   * Similarily the [HAdd] instruction is likely a number. Note that, even if
+   * the [propagatedType] is already set to integer, the [likelyType] still
+   * might just return the number type. 
+   */ 
+  HType get likelyType() => propagatedType;
+
+  /**
+   * Compute the type of the instruction by propagating the input types through
+   * the instruction.
+   *
+   * By default just copy the guaranteed type.
+   */
+  HType computeTypeFromInputTypes() => guaranteedType;
+
+  /**
+   * Compute the desired type for the the given [input]. Aside from using
+   * other inputs to compute the desired type one should also use
+   * the [propagatedType] which, during the invocation of this method,
+   * represents the desired type of [this].
+   */
+  HType computeDesiredTypeForInput(HInstruction input) => HType.UNKNOWN;
 
   bool isInBasicBlock() => block !== null;
 
   String inputsToString() {
     void addAsCommaSeparated(StringBuffer buffer, List<HInstruction> list) {
       for (int i = 0; i < list.length; i++) {
         if (i != 0) buffer.add(', ');
         buffer.add("@${list[i].id}");
       }
     }
@@ skipping 93 matching lines @@
   bool isCodeMotionInvariant() => false;
 }
 
 class HBoolify extends HInstruction {
   HBoolify(HInstruction value) : super(<HInstruction>[value]);
   void prepareGvn() {
     assert(!hasSideEffects());
     setUseGvn();
   }
 
-  HType computeType() => HType.BOOLEAN;
-  bool hasExpectedType() => true;
+  HType get guaranteedType() => HType.BOOLEAN;
 
   accept(HVisitor visitor) => visitor.visitBoolify(this);
   int typeCode() => 0;
   bool typeEquals(other) => other is HBoolify;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HCheck extends HInstruction {
   HCheck(inputs) : super(inputs);
 
   // TODO(floitsch): make class abstract instead of adding an abstract method.
   abstract accept(HVisitor visitor);
 
   bool isControlFlow() => true;
 }
 
 class HTypeGuard extends HInstruction {
   int state;
   HTypeGuard(int this.state, List<HInstruction> env) : super(env);
 
   void prepareGvn() {
     assert(!hasSideEffects());
     setUseGvn();
   }
 
   HInstruction get guarded() => inputs.last();
 
-  HType computeType() => type;
-  bool hasExpectedType() => true;
-
   bool isControlFlow() => true;
 
   accept(HVisitor visitor) => visitor.visitTypeGuard(this);
   int typeCode() => 1;
   bool typeEquals(other) => other is HTypeGuard;
-  bool dataEquals(HTypeGuard other) => type == other.type;
+  bool dataEquals(HTypeGuard other) => propagatedType == other.propagatedType;
 }
 
 class HBoundsCheck extends HCheck {
-  HBoundsCheck(length, index) : super(<HInstruction>[length, index]) {
-    type = HType.INTEGER;
-  }
+  HBoundsCheck(length, index) : super(<HInstruction>[length, index]);
 
   HInstruction get length() => inputs[0];
   HInstruction get index() => inputs[1];
 
   void prepareGvn() {
     assert(!hasSideEffects());
     setUseGvn();
   }
 
-  HType computeType() => HType.INTEGER;
-  bool hasExpectedType() => true;
+  HType get guaranteedType() => HType.INTEGER;
 
   accept(HVisitor visitor) => visitor.visitBoundsCheck(this);
   int typeCode() => 2;
   bool typeEquals(other) => other is HBoundsCheck;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HIntegerCheck extends HCheck {
   HIntegerCheck(value) : super(<HInstruction>[value]);
 
   HInstruction get value() => inputs[0];
 
   void prepareGvn() {
     assert(!hasSideEffects());
     setUseGvn();
   }
 
-  HType computeType() => HType.INTEGER;
-  bool hasExpectedType() => true;
+  HType get guaranteedType() => HType.INTEGER;
 
   accept(HVisitor visitor) => visitor.visitIntegerCheck(this);
   int typeCode() => 3;
   bool typeEquals(other) => other is HIntegerCheck;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HConditionalBranch extends HControlFlow {
   HConditionalBranch(inputs) : super(inputs);
   HInstruction get condition() => inputs[0];
@@ skipping 84 matching lines @@
   Element get element() => target.element;
   HStatic get target() => inputs[0];
 
   bool isArrayConstructor() {
     // TODO(ngeoffray): This is not the right way to do the check,
     // nor the right place. We need to move it to a phase.
     return (element.isFactoryConstructor()
         && element.enclosingElement.name.slowToString() == 'List');
   }
 
-  HType computeType() {
+  HType get guaranteedType() {
     if (isArrayConstructor()) {
       return HType.MUTABLE_ARRAY;
     }
     return HType.UNKNOWN;
   }
 
+  HType computeDesiredTypeForInput(HInstruction input) {
+    // TODO(floitsch): we want the target to be a function.
+    if (input == target) return HType.UNKNOWN;
+    return computeDesiredTypeForNonTargetInput(input);
+  }
+
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    return HType.UNKNOWN;
+  }
+
   bool get builtin() => isArrayConstructor();
-  bool hasExpectedType() => isArrayConstructor();
 }
 
 class HInvokeSuper extends HInvokeStatic {
   HInvokeSuper(selector, inputs) : super(selector, inputs);
   toString() => 'invoke super: ${element.name}';
   accept(HVisitor visitor) => visitor.visitInvokeSuper(this);
 }
 
 class HInvokeInterceptor extends HInvokeStatic {
   final SourceString name;
   final bool getter;
 
   HInvokeInterceptor(Selector selector,
                      SourceString this.name,
                      bool this.getter,
                      List<HInstruction> inputs)
       : super(selector, inputs);
   toString() => 'invoke interceptor: ${element.name}';
   accept(HVisitor visitor) => visitor.visitInvokeInterceptor(this);
 
+  bool isLengthGetterOnStringOrArray() {
+    return getter
+        && name == const SourceString('length')
+        && inputs[1].isStringOrArray();
+  }
+
   String get builtinJsName() {
-    if (getter
-        && name == const SourceString('length')
-        && inputs[1].isStringOrArray()) {
+    if (isLengthGetterOnStringOrArray()) {
       return 'length';
     } else if (name == const SourceString('add')
                && inputs[1].isMutableArray()) {
       return 'push';
     } else if (name == const SourceString('removeLast')
                && inputs[1].isMutableArray()) {
       return 'pop';
     }
     return null;
   }
 
-  HType computeType() {
-    if (getter
-        && name == const SourceString('length')
-        && inputs[1].isStringOrArray()) {
-      return HType.INTEGER;
-    }
+  HType get guaranteedType() => HType.UNKNOWN;
+
+  HType get likelyType() {
+    // In general a length getter or method returns an int.
+    if (name == const SourceString('length')) return HType.INTEGER;
     return HType.UNKNOWN;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    if (input == inputs[0]) return HType.UNKNOWN;
+  HType computeTypeFromInputTypes() {
+    if (isLengthGetterOnStringOrArray()) return HType.INTEGER;
+    return HType.UNKNOWN;
+  }
+
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // If the first argument is a string or an array and we invoke methods
+    // on it that mutate it, then we want to restrict the incoming type to be
+    // a mutable array.
     if (input == inputs[1] && input.isStringOrArray()) {
       if (name == const SourceString('add')
           || name == const SourceString('removeLast')) {
         return HType.MUTABLE_ARRAY;
       }
     }
     return HType.UNKNOWN;
   }
 
-  bool hasExpectedType() => builtinJsName != null;
-
   void prepareGvn() {
-    if (builtinJsName == 'length') {
+    if (isLengthGetterOnStringOrArray()) {
       clearAllSideEffects();
     } else {
       setAllSideEffects();
     }
   }
 
   int typeCode() => 4;
   bool typeEquals(other) => other is HInvokeInterceptor;
   bool dataEquals(HInvokeInterceptor other) {
     return builtinJsName == other.builtinJsName && name == other.name;
@@ skipping 22 matching lines @@
   accept(HVisitor visitor) => visitor.visitFieldSet(this);
 
   void prepareGvn() {
     // TODO(ngeoffray): implement more fine grain side effects.
     setAllSideEffects();
   }
 }
 
 class HForeign extends HInstruction {
   final DartString code;
-  final DartString declaredType;
-  HForeign(this.code, this.declaredType, List<HInstruction> inputs)
-      : super(inputs);
+  final HType foreignType;
+  HForeign(this.code, DartString declaredType, List<HInstruction> inputs)
+      : foreignType = computeTypeFromDeclaredType(declaredType),
+        super(inputs);
   accept(HVisitor visitor) => visitor.visitForeign(this);
 
-  HType computeType() {
+  static HType computeTypeFromDeclaredType(DartString declaredType) {
     if (declaredType.slowToString() == 'bool') return HType.BOOLEAN;
     if (declaredType.slowToString() == 'int') return HType.INTEGER;
     if (declaredType.slowToString() == 'num') return HType.NUMBER;
     if (declaredType.slowToString() == 'String') return HType.STRING;
     return HType.UNKNOWN;
   }
 
-  bool hasExpectedType() => true;
+  HType get guaranteedType() => foreignType;
 }
 
 class HForeignNew extends HForeign {
   ClassElement element;
   HForeignNew(this.element, List<HInstruction> inputs)
       : super(const LiteralDartString("new"),
               const LiteralDartString("Object"), inputs);
   accept(HVisitor visitor) => visitor.visitForeignNew(this);
 }
 
 class HInvokeBinary extends HInvokeStatic {
   HInvokeBinary(HStatic target, HInstruction left, HInstruction right)
       : super(Selector.BINARY_OPERATOR, <HInstruction>[target, left, right]);
 
   HInstruction get left() => inputs[1];
   HInstruction get right() => inputs[2];
 
-  HType computeInputsType() {
-    HType leftType = left.type;
-    HType rightType = right.type;
-    if (leftType.isUnknown() || rightType.isUnknown()) {
-      return HType.UNKNOWN;
-    }
-    return leftType.combine(rightType);
-  }
-
   abstract BinaryOperation get operation();
 }
 
 class HBinaryArithmetic extends HInvokeBinary {
   HBinaryArithmetic(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
 
   void prepareGvn() {
     // 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 (builtin) {
       clearAllSideEffects();
       setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
   bool get builtin() => left.isNumber() && right.isNumber();
 
-  HType computeType() {
-    HType inputsType = computeInputsType();
-    if (inputsType.isKnown()) return inputsType;
-    if (left.isNumber()) return HType.NUMBER;
+  HType computeTypeFromInputTypes() {
+    if (left.isInteger() && right.isInteger()) return left.propagatedType;
+    if (left.isNumber()) {
+      if (left.isDouble() || right.isDouble()) return HType.DOUBLE;
+      return HType.NUMBER;
+    }
     return HType.UNKNOWN;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    if (isNumber() || left.isNumber() || right.isNumber()) return HType.NUMBER;
-    if (type.isUnknown()) return HType.NUMBER;
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // If the desired output type should be an integer we want to get two
+    // integers as arguments.
+    if (propagatedType.isInteger()) return HType.INTEGER;
+    // If the outgoing type should be a number we can get that if both inputs
+    // are numbers. If we don't know the outgoing type we try to make it a
+    // number.
+    if (propagatedType.isUnknown() || propagatedType.isNumber()) {
+      return HType.NUMBER;
+    }
     return HType.UNKNOWN;
   }
 
-  bool hasExpectedType() => left.isNumber() && right.isNumber();
+  HType get likelyType() {
+    if (left.isTypeUnknown()) return HType.NUMBER;
+    return HType.UNKNOWN;
+  }
+
   // TODO(1603): The class should be marked as abstract.
   abstract BinaryOperation get operation();
 }
 
 class HAdd extends HBinaryArithmetic {
   HAdd(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
   accept(HVisitor visitor) => visitor.visitAdd(this);
 
   bool get builtin() {
     return (left.isNumber() && right.isNumber())
             || (left.isString() && right.isString())
             || (left.isString() && right is HConstant);
   }
 
-  HType computeType() {
-    HType computedType = computeInputsType();
-    if (computedType.isConflicting() && left.isString()) return HType.STRING;
-    if (computedType.isKnown()) return computedType;
-    if (left.isNumber()) return HType.NUMBER;
+  HType computeTypeFromInputTypes() {
+    if (left.isInteger() && right.isInteger()) return left.propagatedType;
+    if (left.isNumber()) {
+      if (left.isDouble() || right.isDouble()) return HType.DOUBLE;
+      return HType.NUMBER;
+    }
+    if (left.isString()) return HType.STRING;
     return HType.UNKNOWN;
   }
 
-  bool hasExpectedType() => builtin || type.isUnknown() || left.isString();
-
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    if (isString() || left.isString()) {
-      return (input == left) ? HType.STRING : HType.UNKNOWN;
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // If the desired output type is an integer we want two integers as input.
+    if (propagatedType.isInteger()) {
+      return HType.INTEGER;
     }
-    if (right.isString()) return HType.STRING;
-    if (isNumber() || left.isNumber() || right.isNumber()) return HType.NUMBER;
+    // TODO(floitsch): remove string specialization once string+ is removed
+    // from dart2js.
+    if (propagatedType.isString() || left.isString() || right.isString()) {
+      return HType.STRING;
+    }
+    // If the desired output is a number or any of the inputs is a number
+    // ask for a number. Note that we might return the input's (say 'left')
+    // type depending on its (the 'left's) type. But that shouldn't matter.
+    if (propagatedType.isNumber() || left.isNumber() || right.isNumber()) {
+      return HType.NUMBER;
+    }
     return HType.UNKNOWN;
   }
 
+  HType get likelyType() {
+    if (left.isString() || right.isString()) return HType.STRING;
+    if (left.isTypeUnknown() || left.isNumber()) return HType.NUMBER;
+    return HType.UNKNOWN;
+  }
+
   AddOperation get operation() => const AddOperation();
 
   int typeCode() => 5;
   bool typeEquals(other) => other is HAdd;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HDivide extends HBinaryArithmetic {
   HDivide(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
   accept(HVisitor visitor) => visitor.visitDivide(this);
 
   bool get builtin() => left.isNumber() && right.isNumber();
 
-  HType computeType() {
-    HType inputsType = computeInputsType();
+  HType computeTypeFromInputTypes() {
     if (left.isNumber()) return HType.DOUBLE;
     return HType.UNKNOWN;
   }
 
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // A division can never return an integer. So don't ask for integer inputs.
+    if (propagatedType.isInteger()) return HType.UNKNOWN;
+    return super.computeDesiredTypeForNonTargetInput(input);
+  }
+
   DivideOperation get operation() => const DivideOperation();
   int typeCode() => 6;
   bool typeEquals(other) => other is HDivide;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HModulo extends HBinaryArithmetic {
   HModulo(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
   accept(HVisitor visitor) => visitor.visitModulo(this);
@@ skipping 40 matching lines @@
 
 
 // TODO(floitsch): Should HBinaryArithmetic really be the super class of
 // HBinaryBitOp?
 class HBinaryBitOp extends HBinaryArithmetic {
   HBinaryBitOp(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
 
   bool get builtin() => left.isInteger() && right.isInteger();
 
-  HType computeType() {
-    HType inputsType = computeInputsType();
-    if (inputsType.isKnown()) return inputsType;
+  HType computeTypeFromInputTypes() {
     if (left.isInteger()) return HType.INTEGER;
     return HType.UNKNOWN;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    return HType.INTEGER;
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // If the outgoing type should be a number we can get that only if both
+    // inputs are integers. If we don't know the outgoing type we try to make
+    // it an integer.
+    if (propagatedType.isUnknown() || propagatedType.isNumber()) {
+      return HType.INTEGER;
+    }
+    return HType.UNKNOWN;
+  }
+
+  HType get likelyType() {
+    if (left.isTypeUnknown()) return HType.INTEGER;
+    return HType.UNKNOWN;
   }
 
   // TODO(floitsch): make class abstract instead of adding an abstract method.
   abstract accept(HVisitor visitor);
 }
 
 class HShiftLeft extends HBinaryBitOp {
   HShiftLeft(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
   accept(HVisitor visitor) => visitor.visitShiftLeft(this);
@@ skipping 61 matching lines @@
     if (builtin) {
       clearAllSideEffects();
       setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
   bool get builtin() => operand.isNumber();
 
-  HType computeType() {
-    HType operandType = operand.type;
-    if (!operandType.isUnknown()) return operandType;
+  HType computeTypeFromInputTypes() {
+    HType operandType = operand.propagatedType;
+    if (operandType.isNumber()) return operandType;
     return HType.UNKNOWN;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    if (type.isUnknown() || type.isNumber()) return HType.NUMBER;
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // If the outgoing type should be a number (integer, double or both) we
+    // want the outgoing type to be the input too.
+    // If we don't know the outgoing type we try to make it a number.
+    if (propagatedType.isNumber()) return propagatedType;
+    if (propagatedType.isUnknown()) return HType.NUMBER;
     return HType.UNKNOWN;
   }
 
-  bool hasExpectedType() => builtin || type.isUnknown();
+  HType get likelyType() => HType.NUMBER;
 
   abstract UnaryOperation get operation();
 }
 
 class HNegate extends HInvokeUnary {
   HNegate(HStatic target, HInstruction input) : super(target, input);
   accept(HVisitor visitor) => visitor.visitNegate(this);
 
   NegateOperation get operation() => const NegateOperation();
   int typeCode() => 16;
   bool typeEquals(other) => other is HNegate;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HBitNot extends HInvokeUnary {
   HBitNot(HStatic target, HInstruction input) : super(target, input);
   accept(HVisitor visitor) => visitor.visitBitNot(this);
 
   bool get builtin() => operand.isInteger();
 
-  HType computeType() {
-    HType operandType = operand.type;
-    if (!operandType.isUnknown()) return operandType;
+  HType computeTypeFromInputTypes() {
+    HType operandType = operand.propagatedType;
+    if (operandType.isInteger()) return HType.INTEGER;
     return HType.UNKNOWN;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    return HType.INTEGER;
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // Bit operations only work on integers. If there is no desired output
+    // type or if it as a number we want to get an integer as input.
+    if (propagatedType.isUnknown() || propagatedType.isNumber()) {
+      return HType.INTEGER;
+    }
+    return HType.UNKNOWN;
   }
 
   BitNotOperation get operation() => const BitNotOperation();
   int typeCode() => 17;
   bool typeEquals(other) => other is HBitNot;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HExit extends HControlFlow {
   HExit() : super(const <HInstruction>[]);
@@ skipping 68 matching lines @@
   toString() => 'loop-branch';
   accept(HVisitor visitor) => visitor.visitLoopBranch(this);
 
   bool isDoWhile() {
     return kind === DO_WHILE_LOOP;
   }
 }
 
 class HConstant extends HInstruction {
   final Constant constant;
-  HConstant.internal(this.constant, HType type) : super(<HInstruction>[]) {
-    this.type = type;
-  }
+  final HType constantType;
+  HConstant.internal(this.constant, HType this.constantType)
+      : super(<HInstruction>[]);
 
   void prepareGvn() {
     assert(!hasSideEffects());
   }
 
   toString() => 'literal: $constant';
   accept(HVisitor visitor) => visitor.visitConstant(this);
-  HType computeType() => type;
 
-  bool hasExpectedType() => true;
+  HType get guaranteedType() => constantType;
 
   bool isConstant() => true;
   bool isConstantBoolean() => constant.isBool();
   bool isConstantNull() => constant.isNull();
   bool isConstantNumber() => constant.isNum();
   bool isConstantString() => constant.isString();
 
   // Maybe avoid this if the literal is big?
   bool isCodeMotionInvariant() => true;
 }
 
 class HNot extends HInstruction {
   HNot(HInstruction value) : super(<HInstruction>[value]);
   void prepareGvn() {
     assert(!hasSideEffects());
     setUseGvn();
   }
 
-  HType computeType() => HType.BOOLEAN;
-  bool hasExpectedType() => true;
-  HType computeDesiredInputType(HInstruction input) {
-    return HType.BOOLEAN;
-  }
+  HType get guaranteedType() => HType.BOOLEAN;
+
+  // 'Not' only works on booleans. That's what we want as input.
+  HType computeDesiredTypeForInput(HInstruction input) => HType.BOOLEAN;
 
   accept(HVisitor visitor) => visitor.visitNot(this);
   int typeCode() => 18;
   bool typeEquals(other) => other is HNot;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HParameterValue extends HInstruction {
   final Element element;
 
@@ skipping 35 matching lines @@
   void addInput(HInstruction input) {
     assert(isInBasicBlock());
     inputs.add(input);
     input.usedBy.add(this);
   }
 
   // Compute the (shared) type of the inputs if any. If all inputs
   // have the same known type return it. If any two inputs have
   // different known types, we'll return a conflict -- otherwise we'll
   // simply return an unknown type.
-  HType computeInputsType() {
+  HType computeInputsType(bool unknownWins) {
     bool seenUnknown = false;
-    HType candidateType = inputs[0].type;
+    HType candidateType = inputs[0].propagatedType;
     for (int i = 1, length = inputs.length; i < length; i++) {
-      HType inputType = inputs[i].type;
-      if (inputType.isUnknown()) return HType.UNKNOWN;
-      candidateType = candidateType.combine(inputType);
-      if (candidateType.isConflicting()) return HType.CONFLICTING;
+      HType inputType = inputs[i].propagatedType;
+      if (inputType.isUnknown()) {
+        seenUnknown = true;
+      } else {
+        candidateType = candidateType.combine(inputType);
+        if (candidateType.isConflicting()) return HType.CONFLICTING;
+      }
     }
+    if (seenUnknown && unknownWins) return HType.UNKNOWN;
     return candidateType;
   }
 
-  HType computeType() {
-    HType inputsType = computeInputsType();
-    if (!inputsType.isUnknown()) return inputsType;
-    return super.computeType();
+  HType computeTypeFromInputTypes() {
+    HType inputsType = computeInputsType(true);
+    if (inputsType.isConflicting()) return HType.UNKNOWN;
+    return inputsType;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    if (type.isNumber()) return HType.NUMBER;
-    if (type.isStringOrArray()) return HType.STRING_OR_ARRAY;
-    return type;
+  HType computeDesiredTypeForInput(HInstruction input) {
+    // Best case scenario for a phi is, when all inputs have the same type. If
+    // there is no desired outgoing type we therefore try to unify the input
+    // types (which is basically the [likelyType]).
+    if (propagatedType.isUnknown()) return likelyType;
+    // When the desired outgoing type is conflicting we don't need to give any
+    // requirements on the inputs.
+    if (propagatedType.isConflicting()) return HType.UNKNOWN;
+    // Otherwise the input type must match the desired outgoing type.
+    return propagatedType;
   }
 
-  bool hasExpectedType() {
-    for (int i = 0; i < inputs.length; i++) {
-      if (type.combine(inputs[i].type).isConflicting()) return false;
-    }
-    return true;
+  HType get likelyType() {
+    HType agreedType = computeInputsType(false);
+    if (agreedType.isConflicting()) return HType.UNKNOWN;
+    // Don't be too restrictive. If the agreed type is integer or double just
+    // say that the likely type is number. If more is expected the type will be
+    // propagated back.
+    if (agreedType.isNumber()) return HType.NUMBER;
+    return agreedType;
   }
 
   bool isLogicalOperator() => logicalOperatorType != IS_NOT_LOGICAL_OPERATOR;
 
   String logicalOperator() {
     assert(isLogicalOperator());
     if (logicalOperatorType == IS_AND) return "&&";
     assert(logicalOperatorType == IS_OR);
     return "||";
   }
 
   toString() => 'phi';
   accept(HVisitor visitor) => visitor.visitPhi(this);
 }
 
 class HRelational extends HInvokeBinary {
   HRelational(HStatic target, HInstruction left, HInstruction right)
-      : super(target, left, right) {
-    type = HType.BOOLEAN;
-  }
+      : super(target, left, right);
 
   void prepareGvn() {
     // 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 (builtin) {
       clearAllSideEffects();
       setUseGvn();
     } else {
       setAllSideEffects();
     }
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    // For all relational operations exept HEquals, we expect to only
-    // get numbers.
-    return HType.NUMBER;
+  HType computeTypeFromInputTypes() {
+    if (left.isNumber()) return HType.BOOLEAN;
+    return HType.UNKNOWN;
   }
 
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    // For all relational operations exept HEquals, we expect to get numbers
+    // only. With numbers the outgoing type is a boolean. If something else
+    // is desired, then numbers are incorrect, though.
+    if (propagatedType.isUnknown() || propagatedType.isBoolean()) {
+      if (left.isTypeUnknown() || left.isNumber()) return HType.NUMBER;
+    }
+    return HType.UNKNOWN;
+  }
+
+  HType get likelyType() => HType.BOOLEAN;
+
   bool get builtin() => left.isNumber() && right.isNumber();
-  HType computeType() => HType.BOOLEAN;
-  // A HRelational goes through the builtin operator or the top level
-  // element. Therefore, it always has the expected type.
-  bool hasExpectedType() => true;
   // TODO(1603): the class should be marked as abstract.
   abstract BinaryOperation get operation();
 }
 
 class HEquals extends HRelational {
   HEquals(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
   accept(HVisitor visitor) => visitor.visitEquals(this);
 
   bool get builtin() {
-    if (left.isNumber() && right.isNumber()) return true;
-    if (left is !HConstant) return false;
-    HConstant leftConstant = left;
-    // TODO(floitsch): we can do better if we know that the constant does not
-    // have the equality operator overridden.
-    return !leftConstant.constant.isConstructedObject();
+    // All useful types have === semantics.
+    // Note that this includes all constants except the user-constructed
+    // objects.
+    return left.isConstantNull() || left.propagatedType.isUseful();
   }
 
-  HType computeType() => HType.BOOLEAN;
-
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    if (left.isNumber() || right.isNumber()) return HType.NUMBER;
+  HType computeTypeFromInputTypes() {
+    if (builtin) return HType.BOOLEAN;
     return HType.UNKNOWN;
   }
 
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    if (input == left && right.propagatedType.isUseful()) {
+      // All our useful types have === semantics. But we don't want to
+      // speculatively test for all possible types. Therefore we try to match
+      // the two types. That is, if we see x == 3, then we speculatively test
+      // if x is a number and bailout if it isn't.
+      if (right.isNumber()) return HType.NUMBER;  // No need to be more precise.
+      // String equality testing is much more common than array equality
+      // testing.
+      if (right.isStringOrArray()) return HType.STRING; 
+      return right.propagatedType;
+    }
+    // String equality testing is much more common than array equality testing.
+    if (input == left && left.isStringOrArray()) {
+      return HType.READABLE_ARRAY;
+    }
+    // String equality testing is much more common than array equality testing.
+    if (input == right && right.isStringOrArray()) {
+      return HType.STRING;
+    }
+    return HType.UNKNOWN;
+  }
+
   EqualsOperation get operation() => const EqualsOperation();
   int typeCode() => 19;
   bool typeEquals(other) => other is HEquals;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HIdentity extends HRelational {
   HIdentity(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
   accept(HVisitor visitor) => visitor.visitIdentity(this);
 
   bool get builtin() => true;
-  HType computeType() => HType.BOOLEAN;
-  bool hasExpectedType() => true;
 
-  HType computeDesiredInputType(HInstruction input) => HType.UNKNOWN;
+  HType get guaranteedType() => HType.BOOLEAN;
+  HType computeTypeFromInputTypes() => HType.BOOLEAN;
+  // Note that the identity operator really does not care for its input types.
+  HType computeDesiredTypeForInput(HInstruction input) => HType.UNKNOWN;
 
   IdentityOperation get operation() => const IdentityOperation();
   int typeCode() => 20;
   bool typeEquals(other) => other is HIdentity;
   bool dataEquals(HInstruction other) => true;
 }
 
 class HGreater extends HRelational {
   HGreater(HStatic target, HInstruction left, HInstruction right)
       : super(target, left, right);
@@ skipping 79 matching lines @@
 
   int typeCode() => 26;
   bool typeEquals(other) => other is HStaticStore;
   bool dataEquals(HStaticStore other) => element == other.element;
 }
 
 class HLiteralList extends HInstruction {
   HLiteralList(inputs) : super(inputs);
   toString() => 'literal list';
   accept(HVisitor visitor) => visitor.visitLiteralList(this);
-  HType computeType() => HType.MUTABLE_ARRAY;
-  bool hasExpectedType() => true;
+
+  HType get guaranteedType() => HType.MUTABLE_ARRAY;
 
   void prepareGvn() {
     assert(!hasSideEffects());
   }
 }
 
 class HIndex extends HInvokeStatic {
   HIndex(HStatic target, HInstruction receiver, HInstruction index)
       : super(Selector.INDEX, <HInstruction>[target, receiver, index]);
   toString() => 'index operator';
   accept(HVisitor visitor) => visitor.visitIndex(this);
 
   void prepareGvn() {
     if (builtin) {
       clearAllSideEffects();
     } else {
       setAllSideEffects();
     }
   }
 
   HInstruction get receiver() => inputs[1];
   HInstruction get index() => inputs[2];
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    if (input == receiver) return HType.STRING_OR_ARRAY;
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    if (input == receiver && (index.isTypeUnknown() || index.isNumber())) {
+      return HType.STRING_OR_ARRAY;
+    }
+    // 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 get builtin() => receiver.isStringOrArray();
-  HType computeType() => HType.UNKNOWN;
-  bool hasExpectedType() => false;
+  bool get builtin() => receiver.isStringOrArray() && index.isInteger();
 }
 
 class HIndexAssign extends HInvokeStatic {
   HIndexAssign(HStatic target,
                HInstruction receiver,
                HInstruction index,
                HInstruction value)
       : super(Selector.INDEX_SET,
               <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];
 
-  HType computeDesiredInputType(HInstruction input) {
-    // TODO(floitsch): we want the target to be a function.
-    if (input == target) return HType.UNKNOWN;
-    if (input == receiver) return HType.MUTABLE_ARRAY;
+  // Note, that we don't have a computeTypeFromInputTypes, since [HIndexAssign]
+  // is never used as input.
+
+  HType computeDesiredTypeForNonTargetInput(HInstruction input) {
+    if (input == receiver && (index.isTypeUnknown() || index.isNumber())) {
+      return HType.MUTABLE_ARRAY;
+    }
+    // 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 get builtin() => receiver.isMutableArray();
-  HType computeType() => value.type;
-  // This instruction does not yield a new value, so it always
-  // has the expected type (void).
-  bool hasExpectedType() => true;
+  bool get builtin() => receiver.isMutableArray() && index.isInteger();
 }
 
 class HIs extends HInstruction {
   final Type typeName;
   final bool nullOk;
 
   HIs(this.typeName, HInstruction expression, [nullOk = false])
     : this.nullOk = nullOk, super(<HInstruction>[expression]);
 
   HInstruction get expression() => inputs[0];
 
-  HType computeType() => HType.BOOLEAN;
-  bool hasExpectedType() => true;
+  HType get guaranteedType() => HType.BOOLEAN;
 
   accept(HVisitor visitor) => visitor.visitIs(this);
 
   toString() => "$expression is $typeName";
 }
 
 class HIfBlockInformation {
   final HIf branch;
   final SubGraph thenGraph;
   final SubGraph elseGraph;
   final HBasicBlock joinBlock;
   HIfBlockInformation(this.branch,
                       this.thenGraph,
                       this.elseGraph,
                       this.joinBlock);
 }