Refactor types in ssa nodes.

lib/compiler/implementation/ssa/types.dart

-// Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
+// 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.
 
-class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase {
-
-  final Map<int, HInstruction> workmap;
-  final List<int> worklist;
-  final Compiler compiler;
-  String get name() => 'type propagator';
-
-  SsaTypePropagator(Compiler this.compiler)
-      : workmap = new Map<int, HInstruction>(),
-        worklist = new List<int>();
-
-
-  HType computeType(HInstruction instruction) {
-    return instruction.computeTypeFromInputTypes();
-  }
-
-  // Re-compute and update the type of the instruction. Returns
-  // whether or not the type was changed.
-  bool updateType(HInstruction instruction) {
-    HType oldType = instruction.propagatedType;
-    HType newType = instruction.hasGuaranteedType()
-                    ? instruction.guaranteedType
-                    : computeType(instruction);
-    // We unconditionally replace the propagated type with the new type. The
-    // computeType must make sure that we eventually reach a stable state.
-    instruction.propagatedType = newType;
-    return oldType !== newType;
-  }
-
-  void visitGraph(HGraph graph) {
-    visitDominatorTree(graph);
-    processWorklist();
-  }
-
-  visitBasicBlock(HBasicBlock block) {
-    if (block.isLoopHeader()) {
-      block.forEachPhi((HPhi phi) {
-        // Set the initial type for the phi. In theory we would need to mark the
-        // type of all other incoming edges as "unitialized" and take this into
-        // account when doing the propagation inside the phis. Just setting
-        // the [propagatedType] is however easier.
-        phi.propagatedType = phi.inputs[0].propagatedType;
-        addToWorkList(phi);
-      });
-    } else {
-      block.forEachPhi((HPhi phi) {
-        if (updateType(phi)) addDependentInstructionsToWorkList(phi);
-      });
-    }
-
-    HInstruction instruction = block.first;
-    while (instruction !== null) {
-      if (updateType(instruction)) {
-        addDependentInstructionsToWorkList(instruction);
-      }
-      instruction = instruction.next;
-    }
-  }
-
-  void processWorklist() {
-    while (!worklist.isEmpty()) {
-      int id = worklist.removeLast();
-      HInstruction instruction = workmap[id];
-      assert(instruction !== null);
-      workmap.remove(id);
-      if (updateType(instruction)) {
-        addDependentInstructionsToWorkList(instruction);
-      }
-    }
-  }
-
-  void addDependentInstructionsToWorkList(HInstruction instruction) {
-    for (int i = 0, length = instruction.usedBy.length; i < length; i++) {
-      // The non-speculative type propagator only propagates types forward. We
-      // thus only need to add the users of the [instruction] to the list.
-      addToWorkList(instruction.usedBy[i]);
-    }
-  }
-
-  void addToWorkList(HInstruction instruction) {
-    final int id = instruction.id;
-    if (!workmap.containsKey(id)) {
-      worklist.add(id);
-      workmap[id] = instruction;
-    }
-  }
-}
-
-class SsaSpeculativeTypePropagator extends SsaTypePropagator {
-  final String name = 'speculative type propagator';
-  SsaSpeculativeTypePropagator(Compiler compiler) : super(compiler);
-
-  void addDependentInstructionsToWorkList(HInstruction instruction) {
-    // The speculative type propagator propagates types forward and backward.
-    // Not only do we need to add the users of the [instruction] to the list.
-    // We also need to add the inputs fo the [instruction], since they might
-    // want to propagate the desired outgoing type.
-    for (int i = 0, length = instruction.usedBy.length; i < length; i++) {
-      addToWorkList(instruction.usedBy[i]);
-    }
-    for (int i = 0, length = instruction.inputs.length; i < length; i++) {
-      addToWorkList(instruction.inputs[i]);
-    }
-  }
-
-  HType computeDesiredType(HInstruction instruction) {
-    HType desiredType = HType.UNKNOWN;
-    for (final user in instruction.usedBy) {
-      desiredType =
-          desiredType.combine(user.computeDesiredTypeForInput(instruction));
-      // No need to continue if two users disagree on the type.
-      if (desiredType.isConflicting()) break;
-    }
-    return desiredType;
-  }
-
-  HType computeType(HInstruction instruction) {
-    // Once we are in a conflicting state don't update the type anymore.
-    HType oldType = instruction.propagatedType;
-    if (oldType.isConflicting()) return oldType;
-
-    HType newType = super.computeType(instruction);
-    // [computeDesiredType] goes to all usedBys and lets them compute their
-    // desired type. By setting the [newType] here we give them more context to
-    // work with.
-    instruction.propagatedType = newType;
-    HType desiredType = computeDesiredType(instruction);
-    // If the desired type is conflicting just return the computed type.
-    if (desiredType.isConflicting()) return newType;
-    // TODO(ngeoffray): Allow speculative optimizations on
-    // non-primitive types?
-    if (desiredType.isNonPrimitive()) return newType;
-    return newType.combine(desiredType);
-  }
-}
+abstract class HType {
+  const HType();
+
+  static final HType CONFLICTING = const HAnalysisType("conflicting");
+  static final HType UNKNOWN = const HAnalysisType("unknown");
+  static final HType BOOLEAN = const HBooleanType();
+  static final HType NUMBER = const HNumberType();
+  static final HType INTEGER = const HIntegerType();
+  static final HType DOUBLE = const HDoubleType();
+  static final HType INDEXABLE_PRIMITIVE = const HIndexablePrimitiveType();
+  static final HType STRING = const HStringType();
+  static final HType READABLE_ARRAY = const HReadableArrayType();
+  static final HType MUTABLE_ARRAY = const HMutableArrayType();
+  static final HType EXTENDABLE_ARRAY = const HExtendableArrayType();
+
+  bool isConflicting() => this === CONFLICTING;
+  bool isUnknown() => this === UNKNOWN;
+  bool isBoolean() => false;
+  bool isNumber() => false;
+  bool isInteger() => false;
+  bool isDouble() => false;
+  bool isString() => false;
+  bool isIndexablePrimitive() => false;
+  bool isReadableArray() => false;
+  bool isMutableArray() => false;
+  bool isExtendableArray() => false;
+  bool isPrimitive() => false;
+  bool isNonPrimitive() => false;
+
+  /** A type is useful it is not unknown and not conflicting. */
+  bool isUseful() => !isUnknown() && !isConflicting();
+  /** Alias for isReadableArray. */
+  bool isArray() => isReadableArray();
+
+  /**
+   * The intersection of two types is the intersection of its values. For
+   * example:
+   *   * INTEGER.intersect(NUMBER) => INTEGER.
+   *   * DOUBLE.intersect(INTEGER) => CONFLICTING.
+   *   * MUTABLE_ARRAY.intersect(READABLE_ARRAY) => MUTABLE_ARRAY.
+   *
+   * When there is no predefined type to represent the intersection returns
+   * [CONFLICTING].
+   *
+   * An intersection with [UNKNOWN] returns the non-UNKNOWN type. An
+   * intersection with [CONFLICTING] returns [CONFLICTING].
+   */
+  abstract HType intersection(HType other);
+
+  /**
+   * The union of two types is the union of its values. For example:
+   *   * INTEGER.union(NUMBER) => NUMBER.
+   *   * DOUBLE.union(INTEGER) => NUMBER.
+   *   * MUTABLE_ARRAY.union(READABLE_ARRAY) => READABLE_ARRAY.
+   *
+   * When there is no predefined type to represent the union returns
+   * [CONFLICTING].
+   *
+   * A union with [UNKNOWN] returns the non-UNKNOWN type. A union with
+   * [CONFLICTING] returns [CONFLICTING].
+   */
+  abstract HType union(HType other);
+}
+
+/** Used to represent [HType.UNKNOWN] and [HType.CONFLICTING]. */
+class HAnalysisType extends HType {
+  final String name;
+  const HAnalysisType(this.name);
+  String toString() => name;
+
+  HType combine(HType other) {
+    if (isUnknown()) return other;
+    if (other.isUnknown()) return this;
+    return HType.CONFLICTING;
+  }
+
+  HType union(HType other) => combine(other);
+  HType intersection(HType other) => combine(other);
+}
+
+abstract class HPrimitiveType extends HType {
+  const HPrimitiveType();
+  bool isPrimitive() => true;
+}
+
+class HBooleanType extends HPrimitiveType {
+  const HBooleanType();
+  bool isBoolean() => true;
+  String toString() => "boolean";
+
+  HType combine(HType other) {
+    if (other.isBoolean() || other.isUnknown()) return HType.BOOLEAN;
+    return HType.CONFLICTING;
+  }
+
+  // Since the boolean type is a one-element set the union and intersection are
+  // the same.
+  HType union(HType other) => combine(other);
+  HType intersection(HType other) => combine(other);
+}
+
+class HNumberType extends HPrimitiveType {
+  const HNumberType();
+  bool isNumber() => true;
+  String toString() => "number";
+
+  HType union(HType other) {
+    if (other.isNumber() || other.isUnknown()) return HType.NUMBER;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isUnknown()) return HType.NUMBER;
+    if (other.isNumber()) return other;
+    return HType.CONFLICTING;
+  }
+}
+
+class HIntegerType extends HNumberType {
+  const HIntegerType();
+  bool isInteger() => true;
+  String toString() => "integer";
+
+  HType union(HType other) {
+    if (other.isInteger() || other.isUnknown()) return HType.INTEGER;
+    if (other.isNumber()) return HType.NUMBER;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isUnknown()) return HType.INTEGER;
+    if (other.isDouble()) return HType.CONFLICTING;
+    if (other.isNumber()) return this;
+    return HType.CONFLICTING;
+  }
+}
+
+class HDoubleType extends HNumberType {
+  const HDoubleType();
+  bool isDouble() => true;
+  String toString() => "double";
+
+  HType union(HType other) {
+    if (other.isDouble() || other.isUnknown()) return HType.DOUBLE;
+    if (other.isNumber()) return HType.NUMBER;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isUnknown()) return HType.DOUBLE;
+    if (other.isInteger()) return HType.CONFLICTING;
+    if (other.isNumber()) return this;
+    return HType.CONFLICTING;
+  }
+}
+
+class HIndexablePrimitiveType extends HPrimitiveType {
+  const HIndexablePrimitiveType();
+  bool isIndexablePrimitive() => true;
+  String toString() => "indexable";
+
+  HType union(HType other) {
+    if (other.isIndexablePrimitive() || other.isUnknown()) {
+      return HType.INDEXABLE_PRIMITIVE;
+    }
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isUnknown()) return HType.INDEXABLE_PRIMITIVE;
+    if (other.isIndexablePrimitive()) return other;
+    return HType.CONFLICTING;
+  }
+}
+
+class HStringType extends HIndexablePrimitiveType {
+  const HStringType();
+  bool isString() => true;
+  String toString() => "string";
+
+  HType union(HType other) {
+    if (other.isString() || other.isUnknown()) return HType.STRING;
+    if (other.isIndexablePrimitive()) return HType.INDEXABLE_PRIMITIVE;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isString() || other.isUnknown()) return HType.STRING;
+    if (other.isArray()) return HType.CONFLICTING;
+    if (other.isIndexablePrimitive()) return HType.STRING;
+    return HType.CONFLICTING;
+  }
+}
+
+class HReadableArrayType extends HIndexablePrimitiveType {
+  const HReadableArrayType();
+  bool isReadableArray() => true;
+  String toString() => "readable array";
+
+  HType union(HType other) {
+    if (other.isReadableArray() || other.isUnknown()) {
+      return HType.READABLE_ARRAY;
+    }
+    if (other.isIndexablePrimitive()) return HType.INDEXABLE_PRIMITIVE;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (this === other || other.isUnknown()) return HType.READABLE_ARRAY;
+    if (other.isString()) return HType.CONFLICTING;
+    if (other.isReadableArray()) return other;
+    if (other.isIndexablePrimitive()) return this;
+    return HType.CONFLICTING;
+  }
+}
+
+class HMutableArrayType extends HReadableArrayType {
+  const HMutableArrayType();
+  bool isMutableArray() => true;
+  String toString() => "mutable array";
+
+  HType union(HType other) {
+    if (other.isMutableArray() || other.isUnknown()) {
+      return HType.MUTABLE_ARRAY;
+    }
+    if (other.isReadableArray()) return HType.READABLE_ARRAY;
+    if (other.isIndexablePrimitive()) return HType.INDEXABLE_PRIMITIVE;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (this === other || other.isUnknown()) return HType.MUTABLE_ARRAY;
+    if (other.isString()) return HType.CONFLICTING;
+    if (other.isMutableArray()) return other;
+    if (other.isIndexablePrimitive()) return HType.MUTABLE_ARRAY;
+    return HType.CONFLICTING;
+  }
+}
+
+class HExtendableArrayType extends HMutableArrayType {
+  const HExtendableArrayType();
+  bool isExtendableArray() => true;
+  String toString() => "extendable array";
+
+  HType union(HType other) {
+    if (other.isExtendableArray() || other.isUnknown()) {
+      return HType.EXTENDABLE_ARRAY;
+    }
+    if (other.isMutableArray()) return HType.MUTABLE_ARRAY;
+    if (other.isReadableArray()) return HType.READABLE_ARRAY;
+    if (other.isIndexablePrimitive()) return HType.INDEXABLE_PRIMITIVE;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (this === other || other.isUnknown()) return HType.EXTENDABLE_ARRAY;
+    if (other.isString()) return HType.CONFLICTING;
+    if (other.isIndexablePrimitive()) return HType.EXTENDABLE_ARRAY;
+    return HType.CONFLICTING;
+  }
+}
+
+class HNonPrimitiveType extends HType {
+  final Type type;
+
+  const HNonPrimitiveType(Type this.type);
+  bool isNonPrimitive() => true;
+  String toString() => type.toString();
+
+  HType combine(HType other) {
+    if (other.isNonPrimitive()) {
+      HNonPrimitiveType temp = other;
+      if (this.type === temp.type) return this;
+    }
+    if (other.isUnknown()) return this;
+    return HType.CONFLICTING;
+  }
+
+  // As long as we don't keep track of super/sub types for non-primitive types
+  // the intersection and union is the same.
+  HType intersection(HType other) => combine(other);
+  HType union(HType other) => combine(other);
+
+  Element lookupMember(SourceString name) {
+    ClassElement classElement = type.element;
+    return classElement.lookupMember(name);
+  }
+}