[INFER] Introduce cutoff for total contribution of type objects to type sets, bug 619433.
authorBrian Hackett <bhackett1024@gmail.com>
Wed, 09 Mar 2011 11:04:36 -0800
changeset 74745 c288ca4152d11a5a2fce09073dc5ce36baca8be0
parent 74744 ab1e10fb626f63ec2a41b593d81d53f8d634a835
child 74746 12eb2698dfdbd9a2480fa201c8e3f3f7e2ca9f78
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
bugs619433
milestone2.0b13pre
[INFER] Introduce cutoff for total contribution of type objects to type sets, bug 619433.
js/src/jsinfer.h
js/src/jsinferinlines.h
--- a/js/src/jsinfer.h
+++ b/js/src/jsinfer.h
@@ -308,16 +308,19 @@ struct TypeSet
      */
     JSValueType getKnownTypeTag(JSContext *cx, JSScript *script);
 
     /* Get information about the kinds of objects in this type set. */
     ObjectKind getKnownObjectKind(JSContext *cx, JSScript *script);
 
     /* Get whether this type set is non-empty. */
     bool knownNonEmpty(JSContext *cx, JSScript *script);
+
+  private:
+    inline void markUnknown(JSContext *cx);
 };
 
 /* Type information about a property. */
 struct Property
 {
     /* Identifier for this property, JSID_VOID for the aggregate integer index property. */
     jsid id;
 
@@ -359,16 +362,30 @@ struct TypeObject
      * Whether this is an Object or Array keyed to an offset in the script containing
      * this in its objects list.
      */
     bool initializerObject;
     bool initializerArray;
     uint32 initializerOffset;
 
     /*
+     * Estimate of the contribution of this object to the type sets it appears in.
+     * This is the sum of the sizes of those sets at the point when the object
+     * was added.
+     *
+     * When the contribution exceeds the CONTRIBUTION_LIMIT, any type sets the
+     * object is added to are instead marked as unknown. If we get to this point
+     * we are probably not adding types which will let us do meaningful optimization
+     * later, and we want to ensure in such cases that our time/space complexity
+     * is linear, not worst-case cubic as it would otherwise be.
+     */
+    uint32 contribution;
+    static const uint32 CONTRIBUTION_LIMIT = 20000;
+
+    /*
      * Properties of this object. This may contain JSID_VOID, representing the types
      * of all integer indexes of the object, and/or JSID_EMPTY, representing the types
      * of new objects that can be created with different instances of this type.
      */
     Property **propertySet;
     unsigned propertyCount;
 
     /* List of objects using this one as their prototype. */
--- a/js/src/jsinferinlines.h
+++ b/js/src/jsinferinlines.h
@@ -857,28 +857,37 @@ TypeSet::hasType(jstype type)
         return ((1 << type) & typeFlags) != 0;
     } else {
         return HashSetLookup<TypeObject*,TypeObject,TypeObjectKey>
             (objectSet, objectCount, (TypeObject *) type) != NULL;
     }
 }
 
 inline void
+TypeSet::markUnknown(JSContext *cx)
+{
+    typeFlags = TYPE_FLAG_UNKNOWN | (typeFlags & TYPE_FLAG_INTERMEDIATE_SET);
+    if (objectCount >= 2 && !(typeFlags & TYPE_FLAG_INTERMEDIATE_SET))
+        cx->free(objectSet);
+    objectCount = 0;
+    objectSet = NULL;
+}
+
+inline void
 TypeSet::addType(JSContext *cx, jstype type)
 {
     JS_ASSERT(type);
     JS_ASSERT(cx->compartment->types.inferenceDepth);
-    JS_ASSERT_IF(unknown(), typeFlags == TYPE_FLAG_UNKNOWN);
     InferSpew(ISpewOps, "addType: T%p %s", this, TypeString(type));
 
     if (unknown())
         return;
 
     if (type == TYPE_UNKNOWN) {
-        typeFlags = TYPE_FLAG_UNKNOWN;
+        markUnknown(cx);
     } else if (TypeIsPrimitive(type)) {
         TypeFlags flag = 1 << type;
         if (typeFlags & flag)
             return;
 
         /* If we add float to a type set it is also considered to contain int. */
         if (flag == TYPE_FLAG_DOUBLE)
             flag |= TYPE_FLAG_INT32;
@@ -887,16 +896,23 @@ TypeSet::addType(JSContext *cx, jstype t
     } else {
         TypeObject *object = (TypeObject*) type;
         TypeObject **pentry = HashSetInsert<TypeObject *,TypeObject,TypeObjectKey>
                                   (cx, objectSet, objectCount, object,
                                    typeFlags & TYPE_FLAG_INTERMEDIATE_SET);
         if (!pentry || *pentry)
             return;
         *pentry = object;
+
+        object->contribution += objectCount;
+        if (object->contribution >= TypeObject::CONTRIBUTION_LIMIT) {
+            InferSpew(ISpewOps, "limitUnknown: T%p", this);
+            type = TYPE_UNKNOWN;
+            markUnknown(cx);
+        }
     }
 
     /* Propagate the type to all constraints. */
     TypeConstraint *constraint = constraintList;
     while (constraint) {
         cx->compartment->types.addPending(cx, constraint, this, type);
         constraint = constraint->next;
     }
@@ -1030,17 +1046,17 @@ TypeObject::name()
 #else
     return NULL;
 #endif
 }
 
 inline TypeObject::TypeObject(jsid name, JSObject *proto)
     : proto(proto), emptyShapes(NULL), isFunction(false), marked(false),
       initializerObject(false), initializerArray(false), initializerOffset(0),
-      propertySet(NULL), propertyCount(0),
+      contribution(0), propertySet(NULL), propertyCount(0),
       instanceList(NULL), instanceNext(NULL), next(NULL), unknownProperties(false),
       isDenseArray(false), isPackedArray(false)
 {
 #ifdef DEBUG
     this->name_ = name;
 #endif
 
     InferSpew(ISpewOps, "newObject: %s", this->name());