Refactor types in ssa nodes.

lib/compiler/implementation/ssa/types.dart

Index: lib/compiler/implementation/ssa/types.dart
diff --git a/lib/compiler/implementation/ssa/types.dart b/lib/compiler/implementation/ssa/types.dart
index 0f12bb9e8e1b3d6998147afeddea202411b5822c..c98282ac345ccda01b38bd958193e686020ea79c 100644
--- a/lib/compiler/implementation/ssa/types.dart
+++ b/lib/compiler/implementation/ssa/types.dart
@@ -1,139 +1,282 @@
-// 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);
-      });
-    }
+abstract class HType {
+  const HType();
 
-    HInstruction instruction = block.first;
-    while (instruction !== null) {
-      if (updateType(instruction)) {
-        addDependentInstructionsToWorkList(instruction);
-      }
-      instruction = instruction.next;
-    }
+  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 = const HIndexableType();
+  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 isIndexable() => 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(INTEGER_OR_DOUBLE) => NUMBER.

[ngeoffray, 2012/04/25 11:41:13]

INTEGER_OR_DOUBLE -> NUMBER

[floitsch, 2012/04/25 19:52:15]

Done.

+   *   * DOUBLE.union(INTEGER) => DOUBLE.

[ngeoffray, 2012/04/25 11:41:13]

=> NUMBER

[floitsch, 2012/04/25 19:52:15]

Done.

+   *   * 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);

[ngeoffray, 2012/04/25 11:41:13]

Could you actually write unit tests for union and intersection. The code to
implement them is not trivial (eg sometimes you return this, sometimes you
return HType.FOO).

The tests should be trivial to write and will prevent us from making refactoring
bugs.

[floitsch, 2012/04/25 19:52:15]

Done.

+}
+
+/** 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;
   }
 
-  void processWorklist() {
-    while (!worklist.isEmpty()) {
-      int id = worklist.removeLast();
-      HInstruction instruction = workmap[id];
-      assert(instruction !== null);
-      workmap.remove(id);
-      if (updateType(instruction)) {
-        addDependentInstructionsToWorkList(instruction);
-      }
-    }
+  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 this;

[ngeoffray, 2012/04/25 11:41:13]

Instead of returning [this] in these methods, I would prefer if you explicitely
write it (eg HType.BOOLEAN).

[floitsch, 2012/04/25 19:52:15]

Done.

+    return HType.CONFLICTING;
   }
 
-  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]);
-    }
+  // 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 this;
+    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 this;
+    return super.union(other);
   }
 
-  void addToWorkList(HInstruction instruction) {
-    final int id = instruction.id;
-    if (!workmap.containsKey(id)) {
-      worklist.add(id);
-      workmap[id] = instruction;
+  HType intersection(HType other) {
+    if (other.isUnknown()) return this;
+    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 this;
+    return super.union(other);

[ngeoffray, 2012/04/25 11:41:13]

Personal preference, but I'd prefer if you inlined the code here. Making it rely
on how the super is implemented looks brittle to me.

[floitsch, 2012/04/25 19:52:15]

Done.

+  }
+
+  HType intersection(HType other) {
+    if (other.isUnknown()) return this;
+    if (other.isInteger()) return HType.CONFLICTING;
+    if (other.isNumber()) return this;
+    return HType.CONFLICTING;
+  }
+}
+
+class HIndexableType extends HPrimitiveType {
+  const HIndexableType();
+  bool isIndexable() => true;
+  String toString() => "indexable";
+
+  HType union(HType other) {
+    if (other.isIndexable() || other.isUnknown()) return HType.INDEXABLE;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isUnknown()) return this;
+    if (other.isIndexable()) return other;
+    return HType.CONFLICTING;
+  }
+}
+
+class HStringType extends HPrimitiveType {
+  const HStringType();
+  bool isString() => true;
+  String toString() => "string";
+
+  HType union(HType other) {
+    if (other.isString() || other.isUnknown()) return this;
+    return HType.CONFLICTING;
+  }
+
+  HType intersection(HType other) {
+    if (other.isString() || other.isUnknown()) return this;
+    if (other.isArray()) return HType.CONFLICTING;
+    if (other.isIndexable()) return this;
+    return HType.CONFLICTING;
+  }
+}
+
+class HReadableArrayType extends HIndexableType {
+  const HReadableArrayType();
+  bool isReadableArray() => true;
+  String toString() => "readable array";
+
+  HType union(HType other) {
+    if (other.isReadableArray() || other.isUnknown()) {
+      return HType.READABLE_ARRAY;
     }
+    return super.union(other);
+  }
+
+  HType intersection(HType other) {
+    if (this === other || other.isUnknown()) return this;
+    if (other.isString()) return HType.CONFLICTING;
+    if (other.isReadableArray()) return other;
+    if (other.isIndexable()) return this;
+    return HType.CONFLICTING;
   }
 }
 
-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]);
+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;
     }
-    for (int i = 0, length = instruction.inputs.length; i < length; i++) {
-      addToWorkList(instruction.inputs[i]);
+    return super.union(other);
+  }
+
+  HType intersection(HType other) {
+    if (this === other || other.isUnknown()) return this;
+    if (other.isString()) return HType.CONFLICTING;
+    if (other.isMutableArray()) return other;
+    if (other.isIndexable()) return this;
+    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;
     }
+    return super.union(other);
+  }
+
+  HType intersection(HType other) {
+    if (this === other || other.isUnknown()) return this;
+    if (other.isString()) return HType.CONFLICTING;
+    if (other.isIndexable()) return this;
+    return HType.CONFLICTING;
   }
+}
+
+

[ngeoffray, 2012/04/25 11:41:13]

extra space

[floitsch, 2012/04/25 19:52:15]

Done.

+class HNonPrimitiveType extends HType {
+  final Type type;
 
-  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;
+  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;
     }
-    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);
+    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);
   }
 }