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 768 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 computed from the propagated types of the
+   * instruction's inputs. It is not allowed to do any guess work and can not
+   * be conflicting.
+   *
+   * The type propagator may also use this field to set the desired type. In
+   * this case [computeTypeFromInputTypes()] and [propagatedType] may differ.
+   * If this bad type is used then the use must be guarded.
+   *

[Lasse Reichstein Nielsen, 2012/04/16 11:37:04]

This is still confusing.
The propagatedType is named from how it's derived, not what it is. Then there is
an exception where it's not derived that way, making the name entirely wrong.
Is there some way to name it for what it is? If it is anything meaningful, and
not just an intermediate value for our algorithms.

[floitsch, 2012/04/16 19:59:37]

Reworded the description: The propagated type is the type that the instruction
is assumed to have. If [computeType...] and [propagatedType] differ than we have
done some optimistic type assumptions which must be guarded.

+   * Note that the [propagatedType] may be set to [HType.CONFLICTING].
+   */
+  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.

[kasperl, 2012/04/16 09:09:43]

Fold this comment into the /** doc */ comment?

[Lasse Reichstein Nielsen, 2012/04/16 11:37:04]

Or into a proper method body, instead of using an expression body.

[floitsch, 2012/04/16 19:59:37]

Done.

+  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 94 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;
   }
 
   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()) {
+  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 type;
+  }
+
+  HType computeTypeFromInputTypes() {
+    if (isLengthGetterOnStringOrArray()) {
       return HType.INTEGER;
     }
     return HType.UNKNOWN;
   }
 
-  HType computeDesiredInputType(HInstruction input) {
-    if (input == inputs[0]) return HType.UNKNOWN;
+  HType computeDesiredTypeForInput(HInstruction input) {
+    // TODO(floitsch): we want the target to be a function.
+    if (input == target) return HType.UNKNOWN;
     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) {
+  HType computeDesiredTypeForInput(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;
+    if (propagatedType.isInteger()) {
+      return HType.INTEGER;
+    }
+    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) {
+  HType computeDesiredTypeForInput(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;
+    if (propagatedType.isInteger()) {
+      return HType.INTEGER;
     }
-    if (right.isString()) return HType.STRING;
-    if (isNumber() || left.isNumber() || right.isNumber()) return HType.NUMBER;
+    if (propagatedType.isString() || left.isString() || right.isString()) {
+      return HType.STRING;
+    }
+    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 computeDesiredTypeForInput(HInstruction input) {
+    // TODO(floitsch): we want the target to be a function.
+    if (input == target) return HType.UNKNOWN;    
+    // A division can never return an integer. So don't ask for integer inputs.
+    if (propagatedType.isInteger()) return HType.UNKNOWN;
+    return super.computeDesiredTypeForInput(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) {
+  HType computeDesiredTypeForInput(HInstruction input) {
     // TODO(floitsch): we want the target to be a function.
     if (input == target) return HType.UNKNOWN;
-    return HType.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) {
+  HType computeDesiredTypeForInput(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;
+    if (propagatedType.isInteger()) return HType.INTEGER;
+    if (propagatedType.isUnknown() || propagatedType.isNumber()) {

[kasperl, 2012/04/16 09:09:43]

Maybe we should add more documentation to the computeDesiredTypeForInput methods
so they contain explanations on why we choose certain desired types? Whenever I
read these methods, I have to think.

[floitsch, 2012/04/16 19:59:37]

Added a lot of comments. I hope that's what you had in mind.

+      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) {
+  HType computeDesiredTypeForInput(HInstruction input) {
     // TODO(floitsch): we want the target to be a function.
     if (input == target) return HType.UNKNOWN;
-    return HType.INTEGER;
+    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 type)

[kasperl, 2012/04/16 09:09:43]

this.constantType in the parameter list?

[floitsch, 2012/04/16 19:59:37]

Done.

+      : this.constantType = type,
+        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) {
+  HType get guaranteedType() => HType.BOOLEAN;
+
+  HType computeDesiredTypeForInput(HInstruction input) {
     return 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 {
@@ skipping 37 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) {
+    if (propagatedType.isUnknown()) return likelyType;
+    if (propagatedType.isConflicting()) return HType.UNKNOWN;
+    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) {
+  HType computeTypeFromInputTypes() {
+    if (left.isNumber()) return HType.BOOLEAN;
+    return HType.UNKNOWN;
+  }
+
+  HType computeDesiredTypeForInput(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;
+    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) {

[kasperl, 2012/04/16 09:09:43]

Single-line return for consistency.

[floitsch, 2012/04/16 19:59:37]

Done.

+      return HType.BOOLEAN;
+    }
     return HType.UNKNOWN;
   }
 
+  HType computeDesiredTypeForInput(HInstruction input) {
+    // TODO(floitsch): we want the target to be a function.
+    if (input == target) return HType.UNKNOWN;
+    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;
+  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) {
+  HType computeDesiredTypeForInput(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;
+    if (input == receiver) {
+      if (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) {
+  // Note, that we don't have a computeTypeFromInputTypes, since [HIndexAssign]
+  // is never used as input.
+
+  HType computeDesiredTypeForInput(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;
+    if (input == receiver) {
+      if (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 {
   // TODO(ahe): This should be a Type, not Element.
   final Element typeExpression;
   final bool nullOk;
 
   HIs(this.typeExpression, 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 $typeExpression";
 }
 
 class HIfBlockInformation {
   final HIf branch;
   final SubGraph thenGraph;
   final SubGraph elseGraph;
   final HBasicBlock joinBlock;
   HIfBlockInformation(this.branch,
                       this.thenGraph,
                       this.elseGraph,
                       this.joinBlock);
 }