Start propagating non-primitive types in the backend, and fold instructions that know about the typ…

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 136 matching lines @@
     return result;
   }
 
   static HType mapConstantTypeToSsaType(Constant constant) {
     if (constant.isNull()) return HType.UNKNOWN;
     if (constant.isBool()) return HType.BOOLEAN;
     if (constant.isInt()) return HType.INTEGER;
     if (constant.isDouble()) return HType.DOUBLE;
     if (constant.isString()) return HType.STRING;
     if (constant.isList()) return HType.READABLE_ARRAY;
+    if (constant.isMap()) {
+      MapConstant map = constant;
+      return new HNonPrimitiveType(map.type);
+    }
     return HType.UNKNOWN;
   }
 
   HConstant addConstant(Constant constant) {
     HConstant result = constants[constant];
     if (result === null) {
       HType type = mapConstantTypeToSsaType(constant);
       result = new HConstant.internal(constant, type);
       entry.addAtExit(result);
       constants[constant] = result;
@@ skipping 496 matching lines @@
 
   static final int FLAG_CONFLICTING = 0;
   static final int FLAG_UNKNOWN = 1;
   static final int FLAG_BOOLEAN = FLAG_UNKNOWN << 1;
   static final int FLAG_INTEGER = FLAG_BOOLEAN << 1;
   static final int FLAG_STRING = FLAG_INTEGER << 1;
   static final int FLAG_READABLE_ARRAY = FLAG_STRING << 1;
   // FLAG_WRITABLE_ARRAY implies FLAG_READABLE_ARRAY.
   static final int FLAG_WRITEABLE_ARRAY = FLAG_READABLE_ARRAY << 1;
   static final int FLAG_DOUBLE = FLAG_WRITEABLE_ARRAY << 1;
+  static final int FLAG_NON_PRIMITIVE = FLAG_DOUBLE << 1;
 
   static final HType CONFLICTING = const HType(FLAG_CONFLICTING);
   static final HType UNKNOWN = const HType(FLAG_UNKNOWN);
   static final HType BOOLEAN = const HType(FLAG_BOOLEAN);
   static final HType STRING = const HType(FLAG_STRING);
   static final HType READABLE_ARRAY = const HType(FLAG_READABLE_ARRAY);
   static final HType MUTABLE_ARRAY =
       const HType(FLAG_READABLE_ARRAY | FLAG_WRITEABLE_ARRAY);
   static final HType INTEGER = const HType(FLAG_INTEGER);
   static final HType DOUBLE = const HType(FLAG_DOUBLE);
   static final HType STRING_OR_ARRAY =
       const HType(FLAG_STRING | FLAG_READABLE_ARRAY | FLAG_WRITEABLE_ARRAY);
   static final HType NUMBER = const HType(FLAG_DOUBLE | FLAG_INTEGER);
 
   bool isConflicting() => this === CONFLICTING;
   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 isNonPrimitive() => this.flag === FLAG_NON_PRIMITIVE;
   /** 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;
     if (flag === NUMBER.flag) return NUMBER;
     if (flag === STRING_OR_ARRAY.flag) return STRING_OR_ARRAY;
-    assert(false);
+    unreachable();
   }
 
   String toString() {
     if (isConflicting()) return 'conflicting';
     if (isUnknown()) return 'unknown';
     if (isBoolean()) return 'boolean';
     if (isInteger()) return 'integer';
     if (isDouble()) return 'double';
     if (isString()) return 'string';
     if (isMutableArray()) return 'mutable array';
     if (isArray()) return 'array';
     if (isNumber()) return 'number';
     if (isStringOrArray()) return 'string or array';
     unreachable();
   }
 
   HType combine(HType other) {
     if (isUnknown()) return other;
     if (other.isUnknown()) return this;
     return getTypeFromFlag(this.flag & other.flag);
   }
 }
 
+class HNonPrimitiveType extends HType {

[kasperl, 2012/04/19 06:46:19]

Would it make sense to have a HPrimitiveType too so you don't need the flag on
HNonPrimitiveType?

[ngeoffray, 2012/04/19 08:09:33]

Yes, added a TODO.

+  final Type type;
+
+  const HNonPrimitiveType(Type this.type) : super(FLAG_NON_PRIMITIVE);
+
+  HType combine(HType other) {
+    if (this === other) return this;

[floitsch, 2012/04/18 19:18:48]

Why do you not look at the type?
We could even have a operator == that looks at the type.

[ngeoffray, 2012/04/19 08:09:33]

Well spotted. We don;t need to think about canonicalizing these HType for now,
but I wrote the code wrongly assuming they were canonicalized.

+    if (other.isUnknown()) return this;
+    return CONFLICTING;
+  }
+
+  String toString() => type.toString();
+  Element lookupMember(SourceString name) => type.element.lookupMember(name);
+}
+
 class HInstruction implements Hashable {
   final int id;
   static int idCounter;
 
   final List<HInstruction> inputs;
   final List<HInstruction> usedBy;
 
   HBasicBlock block;
   HInstruction previous = null;
   HInstruction next = null;
@@ skipping 38 matching lines @@
   // 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();
+  bool isNonPrimitive() => propagatedType.isNonPrimitive();
 
   /**
    * 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();
 
   /**
    * The [propagatedType] is the type the instruction is assumed to have.
@@ skipping 122 matching lines @@
       }
     }
     this.block = null;
     assert(isValid());
   }
 
   bool isConstant() => false;
   bool isConstantNull() => false;
   bool isConstantNumber() => false;
   bool isConstantString() => false;
+  bool isConstantList() => false;
+  bool isConstantMap() => false;
 
   bool isValid() {
     HValidator validator = new HValidator();
     validator.currentBlock = block;
     validator.visitInstruction(this);
     return validator.isValid;
   }
 
   /**
    * The code for computing a bailout environment, and the code
@@ skipping 105 matching lines @@
     */
   final Selector selector;
   HInvoke(Selector this.selector, List<HInstruction> inputs) : super(inputs);
   static final int ARGUMENTS_OFFSET = 1;
 
   // TODO(floitsch): make class abstract instead of adding an abstract method.
   abstract accept(HVisitor visitor);
 }
 
 class HInvokeDynamic extends HInvoke {
+  Element element;
   SourceString name;
   HInvokeDynamic(Selector selector, this.name, List<HInstruction> inputs)
       : super(selector, inputs);
   toString() => 'invoke dynamic: $name';
   HInstruction get receiver() => inputs[0];
 
   // TODO(floitsch): make class abstract instead of adding an abstract method.
   abstract accept(HVisitor visitor);
 }
 
 class HInvokeClosure extends HInvokeDynamic {
-  Element element;
   HInvokeClosure(Selector selector, List<HInstruction> inputs)
     : super(selector, const SourceString('call'), inputs);
   accept(HVisitor visitor) => visitor.visitInvokeClosure(this);
 }
 
 class HInvokeDynamicMethod extends HInvokeDynamic {
   HInvokeDynamicMethod(Selector selector,
                        SourceString methodName,
                        List<HInstruction> inputs)
     : super(selector, methodName, inputs);
   toString() => 'invoke dynamic method: $name';
   accept(HVisitor visitor) => visitor.visitInvokeDynamicMethod(this);
 }
 
 class HInvokeDynamicField extends HInvokeDynamic {
-  Element element;
   HInvokeDynamicField(Selector selector,
-                      Element this.element,
+                      Element element,
                       SourceString name,
                       List<HInstruction>inputs)
-      : super(selector, name, inputs);
+      : super(selector, name, inputs) {
+    this.element = element;

[floitsch, 2012/04/18 19:18:48]

I would prefer passing the element in the super call.

[ngeoffray, 2012/04/19 08:09:33]

Done.

+  }
   toString() => 'invoke dynamic field: $name';
 
   // TODO(floitsch): make class abstract instead of adding an abstract method.
   abstract accept(HVisitor visitor);
 }
 
 class HInvokeDynamicGetter extends HInvokeDynamicField {
   HInvokeDynamicGetter(selector, element, name, receiver)
     : super(selector, element, name, [receiver]);
   toString() => 'invoke dynamic getter: $name';
   accept(HVisitor visitor) => visitor.visitInvokeDynamicGetter(this);
 }
 
 class HInvokeDynamicSetter extends HInvokeDynamicField {
   HInvokeDynamicSetter(selector, element, name, receiver, value)
     : super(selector, element, name, [receiver, value]);
   toString() => 'invoke dynamic setter: $name';
   accept(HVisitor visitor) => visitor.visitInvokeDynamicSetter(this);
 }
 
 class HInvokeStatic extends HInvoke {
+  final HType concreteType;
   /** The first input must be the target. */
-  HInvokeStatic(selector, inputs) : super(selector, inputs);
+  HInvokeStatic(selector, inputs, [this.concreteType = HType.UNKNOWN])
+      : super(selector, inputs);
   toString() => 'invoke static: ${element.name}';
   accept(HVisitor visitor) => visitor.visitInvokeStatic(this);
   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 get guaranteedType() {
-    if (isArrayConstructor()) {
-      return HType.MUTABLE_ARRAY;
-    }
-    return HType.UNKNOWN;
-  }
+  HType get guaranteedType() => concreteType;
 
   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;
   }
@@ skipping 12 matching lines @@
   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 isLengthGetter() {
+    return getter

[floitsch, 2012/04/18 19:18:48]

one line.

[kasperl, 2012/04/19 06:46:19]

Fits on one line?

[ngeoffray, 2012/04/19 08:09:33]

Done.

+        && name == const SourceString('length');
+  }
+
   bool isLengthGetterOnStringOrArray() {
-    return getter
-        && name == const SourceString('length')
+    return isLengthGetter()
         && inputs[1].isStringOrArray();
   }
 
   String get builtinJsName() {
     if (isLengthGetterOnStringOrArray()) {
       return 'length';
     } else if (name == const SourceString('add')
                && inputs[1].isMutableArray()) {
       return 'push';
     } else if (name == const SourceString('removeLast')
@@ skipping 535 matching lines @@
   toString() => 'literal: $constant';
   accept(HVisitor visitor) => visitor.visitConstant(this);
 
   HType get guaranteedType() => constantType;
 
   bool isConstant() => true;
   bool isConstantBoolean() => constant.isBool();
   bool isConstantNull() => constant.isNull();
   bool isConstantNumber() => constant.isNum();
   bool isConstantString() => constant.isString();
+  bool isConstantList() => constant.isList();
+  bool isConstantMap() => constant.isMap();
 
   // 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();
@@ skipping 521 matching lines @@
   final bool isAnd;
   final SubExpression left;
   final SubExpression right;
   final HBasicBlock joinBlock;
   HAndOrBlockInformation(this.isAnd,
                          this.left,
                          this.right,
                          this.joinBlock);
   bool accept(HBlockInformationVisitor visitor) => visitor.visitAndOrInfo(this);
 }