[INFER] Introduce packed arrays, bug 604045.
authorBrian Hackett <bhackett1024@gmail.com>
Fri, 05 Nov 2010 07:37:09 -0700
changeset 74609 022de3c39539d4c4f76c0eb6ceec770bd96c2e04
parent 74608 c8d33e4cb418d42901e136140ef56c94c8b409d3
child 74610 bff8be4223d31a6ae2f510e8b7a4925fb5f63b5b
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
bugs604045
milestone2.0b8pre
[INFER] Introduce packed arrays, bug 604045.
js/src/jsapi.cpp
js/src/jsarray.cpp
js/src/jsarray.h
js/src/jsbuiltins.h
js/src/jscntxt.h
js/src/jscompartment.cpp
js/src/jsexn.cpp
js/src/jsgc.cpp
js/src/jsgcinlines.h
js/src/jsinfer.cpp
js/src/jsinfer.h
js/src/jsinferinlines.h
js/src/jsinterp.cpp
js/src/jsiter.cpp
js/src/jsmath.cpp
js/src/jsobj.cpp
js/src/jsobj.h
js/src/jsobjinlines.h
js/src/json.cpp
js/src/jsproxy.cpp
js/src/jsreflect.cpp
js/src/jsregexp.cpp
js/src/jsscopeinlines.h
js/src/jstracer.cpp
js/src/jstypedarray.cpp
js/src/jsxml.cpp
js/src/methodjit/BaseAssembler.h
js/src/methodjit/Compiler.cpp
js/src/methodjit/Compiler.h
js/src/methodjit/FastOps.cpp
js/src/methodjit/NunboxAssembler.h
js/src/methodjit/PolyIC.cpp
js/src/methodjit/PunboxAssembler.h
js/src/methodjit/RematInfo.h
js/src/methodjit/StubCalls.cpp
js/src/tests/ecma_3/Array/jstests.list
js/src/tests/js1_6/Array/jstests.list
js/src/tracejit/Writer.cpp
js/src/tracejit/Writer.h
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -1408,19 +1408,19 @@ js_InitFunctionAndObjectClasses(JSContex
     if (!js_GetClassPrototype(cx, obj, JSProto_Object, &obj_proto))
         return NULL;
     if (!obj_proto)
         obj_proto = js_InitObjectClass(cx, obj);
     if (!obj_proto)
         return NULL;
 
     /* Function.prototype and the global object delegate to Object.prototype. */
-    fun_proto->setProto(obj_proto);
+    fun_proto->setProto(cx, obj_proto);
     if (!obj->getProto())
-        obj->setProto(obj_proto);
+        obj->setProto(cx, obj_proto);
 
 #ifdef JS_TYPE_INFERENCE
     {
         /* Do remaining propagation for the Function and Object type information. */
         TypeObject *protoObject = cx->getFixedTypeObject(TYPE_OBJECT_OBJECT_PROTOTYPE);
         TypeObject *protoFunction = cx->getFixedTypeObject(TYPE_OBJECT_FUNCTION_PROTOTYPE);
         protoObject->addPropagate(cx, protoFunction);
         protoFunction->addPropagate(cx, cx->getFixedTypeObject(TYPE_OBJECT_OBJECT));
@@ -3421,17 +3421,19 @@ JS_DefineObject(JSContext *cx, JSObject 
 {
     CHECK_REQUEST(cx);
     assertSameCompartment(cx, obj, proto);
 
     Class *clasp = Valueify(jsclasp);
     if (!clasp)
         clasp = &js_ObjectClass;    /* default class is Object */
 
-    TypeObject *nobjType = cx->getTypeObject(name, clasp == &js_FunctionClass);
+    TypeObject *nobjType = cx->getTypeObject(name,
+                                             clasp == &js_ArrayClass,
+                                             clasp == &js_FunctionClass);
     if (proto)
         cx->addTypePrototype(nobjType, proto->getTypeObject());
 
     JSObject *nobj = NewObject<WithProto::Class>(cx, clasp, proto, obj, nobjType);
     if (!nobj)
         return NULL;
     cx->addTypeProperty(obj->getTypeObject(), name, ObjectValue(*nobj));
     if (!DefineProperty(cx, obj, name, ObjectValue(*nobj), NULL, NULL, attrs, 0, 0))
@@ -4806,17 +4808,17 @@ JS_CompileUCFunctionForPrincipalsVersion
     return JS_CompileUCFunctionForPrincipals(cx, obj, principals, name, nargs, argnames, chars,
                                              length, filename, lineno);
 }
 
 JS_PUBLIC_API(JSTypeObject *)
 JS_MakeTypeObject(JSContext *cx, const char *name, JSBool monitorNeeded, JSBool isArray)
 {
 #ifdef JS_TYPE_INFERENCE
-    TypeObject *type = cx->getTypeObject(name, false);
+    TypeObject *type = cx->getTypeObject(name, isArray, false);
     TypeObject *proto = cx->getFixedTypeObject(isArray ? TYPE_OBJECT_ARRAY_PROTOTYPE : TYPE_OBJECT_OBJECT_PROTOTYPE);
     if (proto)
         proto->addPropagate(cx, type);
 
     if (monitorNeeded)
         type->setMonitored(cx);
 
     return (JSTypeObject*) type;
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -46,24 +46,28 @@
  * optimize for denseness by testing that the object's class is
  * &js_ArrayClass, and can then directly manipulate the slots for efficiency.
  *
  * We track these pieces of metadata for arrays in dense mode:
  *  - The array's length property as a uint32, accessible with
  *    getArrayLength(), setArrayLength().
  *  - The number of element slots (capacity), gettable with
  *    getDenseArrayCapacity().
+ *  - The array's initialized length, accessible with getDenseArrayInitializedLength().
  *
  * In dense mode, holes in the array are represented by (JS_ARRAY_HOLE) invalid
- * values.  The final slot in fslots is unused.
+ * values.  Elements between the initialized length and the length property
+ * are left uninitialized, but are conceptually holes.  Arrays with no holes
+ * below the initialized length are "packed" arrays.
  *
  * NB: the capacity and length of a dense array are entirely unrelated!  The
  * length may be greater than, less than, or equal to the capacity.  See
  * array_length_setter for an explanation of how the first, most surprising
- * case may occur.
+ * case may occur.  The initialized length is always less than or equal to both
+ * the length and capacity.
  *
  * Arrays are converted to use js_SlowArrayClass when any of these conditions
  * are met:
  *  - the load factor (COUNT / capacity) is less than 0.25, and there are
  *    more than MIN_SPARSE_INDEX slots total
  *  - a property is set that is not indexed (and not "length"); or
  *  - a property is defined that has non-default property attributes.
  *
@@ -348,17 +352,17 @@ IndexToId(JSContext* cx, JSObject* obj, 
  * to JSVAL_VOID. This function assumes that the location pointed by vp is
  * properly rooted and can be used as GC-protected storage for temporaries.
  */
 static JSBool
 GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
                 Value *vp)
 {
     JS_ASSERT(index >= 0);
-    if (obj->isDenseArray() && index < obj->getDenseArrayCapacity() &&
+    if (obj->isDenseArray() && index < obj->getDenseArrayInitializedLength() &&
         !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
         *hole = JS_FALSE;
         return JS_TRUE;
     }
     if (obj->isArguments() &&
         index < obj->getArgsInitialLength() &&
         !(*vp = obj->getArgsElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
         *hole = JS_FALSE;
@@ -391,33 +395,57 @@ GetArrayElement(JSContext *cx, JSObject 
         if (!obj->getProperty(cx, idr.id(), vp))
             return JS_FALSE;
         *hole = JS_FALSE;
     }
     return JS_TRUE;
 }
 
 /*
+ * Prepare a dense array for a write to the specified index, updating its
+ * length, capacity and initialized length as required.
+ */
+static inline bool
+EnsureDenseArrayWrite(JSContext *cx, JSObject *obj, jsuint index)
+{
+    JS_ASSERT(obj->isDenseArray());
+    JS_ASSERT(!INDEX_TOO_SPARSE(obj, index));
+
+    jsuint initlen = obj->getDenseArrayInitializedLength();
+    if (index >= initlen) {
+        if (!obj->ensureDenseArrayElements(cx, index + 1))
+            return false;
+        if (index > initlen) {
+            ClearValueRange(obj->getDenseArrayElements() + initlen, index - initlen, true);
+            obj->setDenseArrayNotPacked(cx);
+        }
+        if (index >= obj->getArrayLength())
+            obj->setArrayLength(cx, index + 1);
+        obj->setDenseArrayInitializedLength(index + 1);
+    }
+
+    return true;
+}
+
+/*
  * Set the value of the property at the given index to v assuming v is rooted.
  */
 static JSBool
 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, const Value &v)
 {
     JS_ASSERT(index >= 0);
 
     if (obj->isDenseArray()) {
         /* Predicted/prefetched code should favor the remains-dense case. */
         if (index <= jsuint(-1)) {
             jsuint idx = jsuint(index);
             if (!INDEX_TOO_SPARSE(obj, idx)) {
                 JS_ASSERT(idx + 1 > idx);
-                if (!obj->ensureDenseArrayElements(cx, idx + 1))
+                if (!EnsureDenseArrayWrite(cx, obj, idx))
                     return JS_FALSE;
-                if (idx >= obj->getArrayLength())
-                    obj->setArrayLength(cx, idx + 1);
                 obj->setDenseArrayElement(idx, v);
                 return JS_TRUE;
             }
         }
 
         if (!obj->makeDenseArraySlow(cx))
             return JS_FALSE;
     }
@@ -429,48 +457,56 @@ SetArrayElement(JSContext *cx, JSObject 
     JS_ASSERT(!JSID_IS_VOID(idr.id()));
 
     Value tmp = v;
     return obj->setProperty(cx, idr.id(), &tmp, true);
 }
 
 #ifdef JS_TRACER
 JSBool JS_FASTCALL
-js_EnsureDenseArrayCapacity(JSContext *cx, JSObject *obj, jsint i)
+js_Array_dense_setelem_uninitialized(JSContext *cx, JSObject *obj, jsint i)
 {
 #ifdef DEBUG
     Class *origObjClasp = obj->clasp; 
 #endif
+
     jsuint u = jsuint(i);
-    jsuint capacity = obj->getDenseArrayCapacity();
-    if (u < capacity)
-        return true;
     if (INDEX_TOO_SPARSE(obj, u))
         return false;
-
-    JSBool ret = obj->ensureDenseArrayElements(cx, u + 1);
+    if (js_PrototypeHasIndexedProperties(cx, obj))
+        return false;
+
+    if (!EnsureDenseArrayWrite(cx, obj, u))
+        return false;
+
+    /*
+     * Write undefined to the element so the tracer doesn't see an uninitialized value
+     * when testing for a hole, and doesn't call dense_setelem_hole.
+     */
+    obj->setDenseArrayElement(i, UndefinedValue());
 
     /* Partially check the CallInfo's storeAccSet is correct. */
     JS_ASSERT(obj->clasp == origObjClasp);
-    return ret;
+    return true;
 }
 /* This function and its callees do not touch any object's .clasp field. */
-JS_DEFINE_CALLINFO_3(extern, BOOL, js_EnsureDenseArrayCapacity, CONTEXT, OBJECT, INT32,
+JS_DEFINE_CALLINFO_3(extern, BOOL, js_Array_dense_setelem_uninitialized, CONTEXT, OBJECT, INT32,
                      0, nanojit::ACCSET_STORE_ANY & ~tjit::ACCSET_OBJ_CLASP)
 #endif
 
 static JSBool
 DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool strict)
 {
     JS_ASSERT(index >= 0);
     if (obj->isDenseArray()) {
         if (index <= jsuint(-1)) {
             jsuint idx = jsuint(index);
-            if (idx < obj->getDenseArrayCapacity()) {
+            if (idx < obj->getDenseArrayInitializedLength()) {
                 obj->setDenseArrayElement(idx, MagicValue(JS_ARRAY_HOLE));
+                obj->setDenseArrayNotPacked(cx);
                 return JS_TRUE;
             }
         }
         return JS_TRUE;
     }
 
     AutoIdRooter idr(cx);
 
@@ -575,23 +611,26 @@ array_length_setter(JSContext *cx, JSObj
     if (oldlen < newlen) {
         obj->setArrayLength(cx, newlen);
         return true;
     }
 
     if (obj->isDenseArray()) {
         /*
          * Don't reallocate if we're not actually shrinking our slots. If we do
-         * shrink slots here, ensureDenseArrayElements will fill all slots to the
-         * right of newlen with JS_ARRAY_HOLE. This permits us to disregard
-         * length when reading from arrays as long we are within the capacity.
+         * shrink slots here, shrink the initialized length too.  This permits us
+         * us to disregard length when reading from arrays as long we are within
+         * the initialized capacity.
          */
         jsuint oldcap = obj->getDenseArrayCapacity();
         if (oldcap > newlen)
             obj->shrinkDenseArrayElements(cx, newlen);
+        jsuint oldinit = obj->getDenseArrayInitializedLength();
+        if (oldinit > newlen)
+            obj->setDenseArrayInitializedLength(newlen);
         obj->setArrayLength(cx, newlen);
     } else if (oldlen - newlen < (1 << 24)) {
         do {
             --oldlen;
             if (!JS_CHECK_OPERATION_LIMIT(cx)) {
                 obj->setArrayLength(cx, oldlen + 1);
                 return false;
             }
@@ -632,29 +671,27 @@ array_length_setter(JSContext *cx, JSObj
         }
         obj->setArrayLength(cx, newlen);
     }
 
     return true;
 }
 
 /*
- * We have only indexed properties up to capacity (excepting holes), plus the
+ * We have only indexed properties up to initialized length, plus the
  * length property. For all else, we delegate to the prototype.
  */
 static inline bool
 IsDenseArrayId(JSContext *cx, JSObject *obj, jsid id)
 {
     JS_ASSERT(obj->isDenseArray());
 
     uint32 i;
     return JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
-           (js_IdIsIndex(id, &i) &&
-            obj->getArrayLength() != 0 &&
-            i < obj->getDenseArrayCapacity() &&
+           (js_IdIsIndex(id, &i) && i < obj->getDenseArrayInitializedLength() &&
             !obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE));
 }
 
 static JSBool
 array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
                      JSProperty **propp)
 {
     if (!obj->isDenseArray())
@@ -703,17 +740,17 @@ array_getProperty(JSContext *cx, JSObjec
     if (JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom)) {
         vp->setObjectOrNull(obj->getProto());
         return JS_TRUE;
     }
 
     if (!obj->isDenseArray())
         return js_GetProperty(cx, obj, id, vp);
 
-    if (!js_IdIsIndex(id, &i) || i >= obj->getDenseArrayCapacity() ||
+    if (!js_IdIsIndex(id, &i) || i >= obj->getDenseArrayInitializedLength() ||
         obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
         JSObject *obj2;
         JSProperty *prop;
         const Shape *shape;
 
         JSObject *proto = obj->getProto();
         if (!proto) {
             vp->setUndefined();
@@ -769,21 +806,19 @@ array_setProperty(JSContext *cx, JSObjec
 
     if (!js_IdIsIndex(id, &i) || js_PrototypeHasIndexedProperties(cx, obj) ||
         INDEX_TOO_SPARSE(obj, i)) {
         if (!obj->makeDenseArraySlow(cx))
             return false;
         return js_SetProperty(cx, obj, id, vp, strict);
     }
 
-    if (!obj->ensureDenseArrayElements(cx, i + 1))
+    if (!EnsureDenseArrayWrite(cx, obj, i))
         return false;
 
-    if (i >= obj->getArrayLength())
-        obj->setArrayLength(cx, i + 1);
     obj->setDenseArrayElement(i, *vp);
     return true;
 }
 
 static JSBool
 slowarray_setProperty(JSContext *cx, JSObject *obj, jsid id, Value *vp, JSBool strict)
 {
     JS_ASSERT(obj->isSlowArray());
@@ -879,42 +914,44 @@ array_deleteProperty(JSContext *cx, JSOb
     if (!obj->isDenseArray())
         return js_DeleteProperty(cx, obj, id, rval, strict);
 
     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)) {
         rval->setBoolean(false);
         return JS_TRUE;
     }
 
-    if (js_IdIsIndex(id, &i) && i < obj->getDenseArrayCapacity())
+    if (js_IdIsIndex(id, &i) && i < obj->getDenseArrayInitializedLength()) {
         obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
+        obj->setDenseArrayNotPacked(cx);
+    }
 
     if (!js_SuppressDeletedProperty(cx, obj, id))
         return false;
 
     rval->setBoolean(true);
     return JS_TRUE;
 }
 
 static void
 array_trace(JSTracer *trc, JSObject *obj)
 {
     JS_ASSERT(obj->isDenseArray());
 
     size_t holes = 0;
-    uint32 capacity = obj->getDenseArrayCapacity();
-    for (uint32 i = 0; i < capacity; i++) {
+    uint32 initlen = obj->getDenseArrayInitializedLength();
+    for (uint32 i = 0; i < initlen; i++) {
         Value v = obj->getDenseArrayElement(i);
         if (v.isMagic(JS_ARRAY_HOLE))
             ++holes;
         else
             MarkValue(trc, obj->getDenseArrayElement(i), "dense_array_elems");
     }
 
-    if (IS_GC_MARKING_TRACER(trc) && holes > MIN_SPARSE_INDEX && holes > capacity / 4 * 3) {
+    if (IS_GC_MARKING_TRACER(trc) && holes > MIN_SPARSE_INDEX && holes > initlen / 4 * 3) {
         /* This might fail, in which case we don't slowify it. */
         static_cast<GCMarker *>(trc)->arraysToSlowify.append(obj);
     }
 }
 
 static JSBool
 array_fix(JSContext *cx, JSObject *obj, bool *success, AutoIdVector *props)
 {
@@ -1013,45 +1050,48 @@ Class js_SlowArrayClass = {
 /*
  * Convert an array object from fast-and-dense to slow-and-flexible.
  */
 JSBool
 JSObject::makeDenseArraySlow(JSContext *cx)
 {
     JS_ASSERT(isDenseArray());
 
+    cx->markTypeArrayNotPacked(getTypeObject(), true);
+    setDenseArrayNotPacked(cx);
+
     /*
      * Save old map now, before calling InitScopeForObject. We'll have to undo
      * on error. This is gross, but a better way is not obvious.
      */
     JSObjectMap *oldMap = map;
 
     /*
      * Create a native scope. All slow arrays other than Array.prototype get
      * the same initial shape.
      */
     JSObject *arrayProto = getProto();
     if (!InitScopeForObject(cx, this, &js_SlowArrayClass, arrayProto, FINALIZE_OBJECT0))
         return false;
 
-    uint32 capacity = getDenseArrayCapacity();
+    uint32 initlen = getDenseArrayInitializedLength();
 
     /*
      * Begin with the length property to share more of the property tree.
      * The getter/setter here will directly access the object's private value.
      */
     if (!addProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom),
                      array_length_getter, NULL,
                      SHAPE_INVALID_SLOT, JSPROP_PERMANENT | JSPROP_SHARED, 0, 0)) {
         setMap(oldMap);
         return false;
     }
 
     /* Create new properties pointing to existing elements. */
-    for (uint32 i = 0; i < capacity; i++) {
+    for (uint32 i = 0; i < initlen; i++) {
         jsid id;
         if (!ValueToId(cx, Int32Value(i), &id)) {
             setMap(oldMap);
             return false;
         }
 
         if (getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
             setDenseArrayElement(i, UndefinedValue());
@@ -1059,16 +1099,23 @@ JSObject::makeDenseArraySlow(JSContext *
         }
 
         if (!addDataProperty(cx, id, i, JSPROP_ENUMERATE)) {
             setMap(oldMap);
             return false;
         }
     }
 
+    /* Clear values out to the capacity with undefined. */
+    ClearValueRange(getDenseArrayElements() + initlen, getDenseArrayCapacity() - initlen, false);
+
+    /* initialized length is not used anymore. */
+    initializedLength = 0;
+    JS_ASSERT(emptyShapes == NULL);
+
     /*
      * Finally, update class. If |this| is Array.prototype, then js_InitClass
      * will create an emptyShape whose class is &js_SlowArrayClass, to ensure
      * that delegating instances can share shapes in the tree rooted at the
      * proto's empty shape.
      */
     clasp = &js_SlowArrayClass;
     return true;
@@ -1341,34 +1388,37 @@ array_toLocaleString(JSContext *cx, uint
     return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
 }
 
 static JSBool
 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, Value *vector)
 {
     JS_ASSERT(count < MAXINDEX);
 
+    if (count == 0)
+        return JS_TRUE;
+
     /*
      * Optimize for dense arrays so long as adding the given set of elements
      * wouldn't otherwise make the array slow.
      */
     if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
         start <= MAXINDEX - count && !INDEX_TOO_BIG(start + count)) {
 
         jsuint newlen = start + count;
         JS_ASSERT(jsdouble(start) + count == jsdouble(newlen));
         if (!obj->ensureDenseArrayElements(cx, newlen))
             return JS_FALSE;
 
-        if (newlen > obj->getArrayLength())
-            obj->setArrayLength(cx, newlen);
+        if (!EnsureDenseArrayWrite(cx, obj, newlen - 1))
+            return JS_FALSE;
 
         JS_ASSERT(count < uint32(-1) / sizeof(Value));
         memcpy(obj->getDenseArrayElements() + start, vector, sizeof(jsval) * count);
-        JS_ASSERT_IF(count != 0, !obj->getDenseArrayElement(newlen - 1).isMagic(JS_ARRAY_HOLE));
+        JS_ASSERT(!obj->getDenseArrayElement(newlen - 1).isMagic(JS_ARRAY_HOLE));
         return JS_TRUE;
     }
 
     Value* end = vector + count;
     while (vector != end && start < MAXINDEX) {
         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
             !SetArrayElement(cx, obj, start++, *vector++)) {
             return JS_FALSE;
@@ -1404,17 +1454,22 @@ InitArrayObject(JSContext *cx, JSObject 
     JS_ASSERT(obj->isArray());
 
     JS_ASSERT(obj->isDenseArray());
     obj->setArrayLength(cx, length);
     if (!vector || !length)
         return true;
     if (!obj->ensureDenseArrayElements(cx, length))
         return false;
-    memcpy(obj->getDenseArrayElements(), vector, length * sizeof(Value));
+    obj->setDenseArrayInitializedLength(length);
+    for (jsuint i = 0; i < length; i++) {
+        obj->setDenseArrayElement(i, vector[i]);
+        if (vector[i].isMagic(JS_ARRAY_HOLE))
+            obj->setDenseArrayNotPacked(cx);
+    }
     return true;
 }
 
 /*
  * Perl-inspired join, reverse, and sort.
  */
 static JSBool
 array_join(JSContext *cx, uintN argc, Value *vp)
@@ -1453,16 +1508,24 @@ array_reverse(JSContext *cx, uintN argc,
          * be a common operation than other array mass-mutation methods, so for
          * now just take a probably-small memory hit (in the absence of too many
          * holes in the array at its start) and ensure that the capacity is
          * sufficient to hold all the elements in the array if it were full.
          */
         if (!obj->ensureDenseArrayElements(cx, len))
             return JS_FALSE;
 
+        /* Fill out the array's initialized length to its proper length. */
+        jsuint initlen = obj->getDenseArrayInitializedLength();
+        if (len > initlen) {
+            ClearValueRange(obj->getDenseArrayElements() + initlen, len - initlen, true);
+            obj->setDenseArrayNotPacked(cx);
+            obj->setDenseArrayInitializedLength(len);
+        }
+
         uint32 lo = 0, hi = len - 1;
         for (; lo < hi; lo++, hi--) {
             Value tmp = obj->getDenseArrayElement(lo);
             obj->setDenseArrayElement(lo, obj->getDenseArrayElement(hi));
             obj->setDenseArrayElement(hi, tmp);
         }
 
         /*
@@ -1982,44 +2045,40 @@ array_push1_dense(JSContext* cx, JSObjec
     uint32 length = obj->getArrayLength();
     if (INDEX_TOO_SPARSE(obj, length)) {
         if (!obj->makeDenseArraySlow(cx))
             return JS_FALSE;
         Value tmp = v;
         return array_push_slowly(cx, obj, 1, &tmp, rval);
     }
 
-    if (!obj->ensureDenseArrayElements(cx, length + 1))
+    if (!EnsureDenseArrayWrite(cx, obj, length))
         return JS_FALSE;
-    obj->setArrayLength(cx, length + 1);
-
-    JS_ASSERT(obj->getDenseArrayElement(length).isMagic(JS_ARRAY_HOLE));
+
     obj->setDenseArrayElement(length, v);
     rval->setNumber(obj->getArrayLength());
     return JS_TRUE;
 }
 
 JS_ALWAYS_INLINE JSBool
 ArrayCompPushImpl(JSContext *cx, JSObject *obj, const Value &v)
 {
     JS_ASSERT(obj->isDenseArray());
     uint32_t length = obj->getArrayLength();
     JS_ASSERT(length <= obj->getDenseArrayCapacity());
 
-    if (length == obj->getDenseArrayCapacity()) {
-        if (length > JS_ARGS_LENGTH_MAX) {
-            JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
-                                   JSMSG_ARRAY_INIT_TOO_BIG);
-            return JS_FALSE;
-        }
-
-        if (!obj->ensureDenseArrayElements(cx, length + 1))
-            return JS_FALSE;
+    if (length > JS_ARGS_LENGTH_MAX) {
+        JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
+                               JSMSG_ARRAY_INIT_TOO_BIG);
+        return JS_FALSE;
     }
-    obj->setArrayLength(cx, length + 1);
+
+    if (!EnsureDenseArrayWrite(cx, obj, length))
+        return JS_FALSE;
+
     obj->setDenseArrayElement(length, v);
     return JS_TRUE;
 }
 
 JSBool
 js_ArrayCompPush(JSContext *cx, JSObject *obj, const Value &vp)
 {
     return ArrayCompPushImpl(cx, obj, vp);
@@ -2080,16 +2139,18 @@ array_pop_dense(JSContext *cx, JSObject*
         return JS_TRUE;
     }
     index--;
     if (!GetArrayElement(cx, obj, index, &hole, vp))
         return JS_FALSE;
     if (!hole && !DeleteArrayElement(cx, obj, index, true))
         return JS_FALSE;
     obj->setArrayLength(cx, index);
+    if (index == obj->getDenseArrayInitializedLength() - 1)
+        obj->setDenseArrayInitializedLength(index);
     return JS_TRUE;
 }
 
 static JSBool
 array_pop(JSContext *cx, uintN argc, Value *vp)
 {
     JSObject *obj = ComputeThisFromVp(cx, vp);
     if (!obj)
@@ -2109,24 +2170,28 @@ array_shift(JSContext *cx, uintN argc, V
     if (!obj || !js_GetLengthProperty(cx, obj, &length))
         return JS_FALSE;
 
     if (length == 0) {
         vp->setUndefined();
     } else {
         length--;
 
-        if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
-            length < obj->getDenseArrayCapacity()) {
-            *vp = obj->getDenseArrayElement(0);
-            if (vp->isMagic(JS_ARRAY_HOLE))
+        if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj)) {
+            Value *elems = obj->getDenseArrayElements();
+            jsuint initlen = obj->getDenseArrayInitializedLength();
+            if (initlen > 0) {
+                *vp = obj->getDenseArrayElement(0);
+                if (vp->isMagic(JS_ARRAY_HOLE))
+                    vp->setUndefined();
+                memmove(elems, elems + 1, (initlen - 1) * sizeof(jsval));
+                obj->setDenseArrayInitializedLength(initlen - 1);
+            } else {
                 vp->setUndefined();
-            Value *elems = obj->getDenseArrayElements();
-            memmove(elems, elems + 1, length * sizeof(jsval));
-            obj->setDenseArrayElement(length, MagicValue(JS_ARRAY_HOLE));
+            }
             obj->setArrayLength(cx, length);
             return JS_TRUE;
         }
 
         /* Get the to-be-deleted property's value into vp ASAP. */
         if (!GetArrayElement(cx, obj, 0, &hole, vp))
             return JS_FALSE;
 
@@ -2161,22 +2226,21 @@ array_unshift(JSContext *cx, uintN argc,
     newlen = length;
     if (argc > 0) {
         /* Slide up the array to make room for argc at the bottom. */
         argv = JS_ARGV(cx, vp);
         if (length > 0) {
             if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
                 !INDEX_TOO_SPARSE(obj, unsigned(newlen + argc))) {
                 JS_ASSERT(newlen + argc == length + argc);
-                if (!obj->ensureDenseArrayElements(cx, length + argc))
+                if (!EnsureDenseArrayWrite(cx, obj, length + argc - 1))
                     return JS_FALSE;
                 Value *elems = obj->getDenseArrayElements();
                 memmove(elems + argc, elems, length * sizeof(jsval));
-                for (uint32 i = 0; i < argc; i++)
-                    obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
+                ClearValueRange(obj->getDenseArrayElements(), argc, false);
             } else {
                 last = length;
                 jsdouble upperIndex = last + argc;
                 AutoValueRooter tvr(cx);
                 do {
                     --last, --upperIndex;
                     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
                         !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
@@ -2305,42 +2369,40 @@ array_splice(JSContext *cx, uintN argc, 
 
     /* Find the direction (up or down) to copy and make way for argv. */
     if (argc > count) {
         delta = (jsuint)argc - count;
         last = length;
         if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
             length <= obj->getDenseArrayCapacity() &&
             (length == 0 || !obj->getDenseArrayElement(length - 1).isMagic(JS_ARRAY_HOLE))) {
-            if (!obj->ensureDenseArrayElements(cx, length + delta))
+            if (!EnsureDenseArrayWrite(cx, obj, length + delta - 1))
                 return JS_FALSE;
 
             Value *arraybeg = obj->getDenseArrayElements();
             Value *srcbeg = arraybeg + last - 1;
             Value *srcend = arraybeg + end - 1;
             Value *dstbeg = srcbeg + delta;
             for (Value *src = srcbeg, *dst = dstbeg; src > srcend; --src, --dst)
                 *dst = *src;
-
-            obj->setArrayLength(cx, obj->getArrayLength() + delta);
         } else {
             /* (uint) end could be 0, so we can't use a vanilla >= test. */
             while (last-- > end) {
                 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
                     !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
                     !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
                     return JS_FALSE;
                 }
             }
         }
         length += delta;
     } else if (argc < count) {
         delta = count - (jsuint)argc;
         if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
-            length <= obj->getDenseArrayCapacity()) {
+            length <= obj->getDenseArrayInitializedLength()) {
 
             Value *arraybeg = obj->getDenseArrayElements();
             Value *srcbeg = arraybeg + end;
             Value *srcend = arraybeg + length;
             Value *dstbeg = srcbeg - delta;
             for (Value *src = srcbeg, *dst = dstbeg; src < srcend; ++src, ++dst)
                 *dst = *src;
         } else {
@@ -3236,16 +3298,19 @@ JS_DEFINE_CALLINFO_3(extern, OBJECT, js_
 JSObject* JS_FASTCALL
 js_NewPreallocatedArray(JSContext* cx, JSObject* proto, int32 len)
 {
     JSObject *obj = js_NewEmptyArray(cx, proto, len);
     if (!obj)
         return NULL;
     if (!obj->ensureDenseArrayElements(cx, len))
         return NULL;
+    ClearValueRange(obj->getDenseArrayElements(), len, true);
+    obj->setDenseArrayInitializedLength(len);
+    obj->setDenseArrayNotPacked(cx);
     return obj;
 }
 #ifdef JS_TRACER
 JS_DEFINE_CALLINFO_3(extern, OBJECT, js_NewPreallocatedArray, CONTEXT, OBJECT, INT32,
                      0, nanojit::ACCSET_STORE_ANY)
 #endif
 
 // specialized handler for Array() that propagates arguments into indexes
@@ -3319,16 +3384,18 @@ js_NewArrayObject(JSContext *cx, jsuint 
 }
 
 JSObject *
 js_NewSlowArrayObject(JSContext *cx, TypeObject *type)
 {
     JSObject *obj = NewNonFunction<WithProto::Class>(cx, &js_SlowArrayClass, NULL, NULL, type);
     if (obj)
         obj->setArrayLength(cx, 0);
+
+    cx->markTypeArrayNotPacked(type, true);
     return obj;
 }
 
 #ifdef DEBUG
 JSBool
 js_ArrayInfo(JSContext *cx, uintN argc, jsval *vp)
 {
     uintN i;
--- a/js/src/jsarray.h
+++ b/js/src/jsarray.h
@@ -268,11 +268,11 @@ js_CloneDensePrimitiveArray(JSContext *c
 /*
  * Returns JS_TRUE if the given object is a dense array that contains only
  * primitive values.
  */
 JS_FRIEND_API(JSBool)
 js_IsDensePrimitiveArray(JSObject *obj);
 
 extern JSBool JS_FASTCALL
-js_EnsureDenseArrayCapacity(JSContext *cx, JSObject *obj, jsint i);
+js_Array_dense_setelem_uninitialized(JSContext *cx, JSObject *obj, jsint i);
 
 #endif /* jsarray_h___ */
--- a/js/src/jsbuiltins.h
+++ b/js/src/jsbuiltins.h
@@ -571,21 +571,21 @@ js_dmod(jsdouble a, jsdouble b);
 #define JS_DEFINE_TRCINFO_2(name, tn0, tn1)
 #define JS_DEFINE_TRCINFO_3(name, tn0, tn1, tn2)
 #define JS_DEFINE_TRCINFO_4(name, tn0, tn1, tn2, tn3)
 
 #endif /* !JS_TRACER */
 
 /* Defined in jsarray.cpp. */
 JS_DECLARE_CALLINFO(js_Array_dense_setelem_hole)
+JS_DECLARE_CALLINFO(js_Array_dense_setelem_uninitialized)
 JS_DECLARE_CALLINFO(js_NewEmptyArray)
 JS_DECLARE_CALLINFO(js_NewPreallocatedArray)
 JS_DECLARE_CALLINFO(js_InitializerArray)
 JS_DECLARE_CALLINFO(js_ArrayCompPush_tn)
-JS_DECLARE_CALLINFO(js_EnsureDenseArrayCapacity)
 
 /* Defined in jsbuiltins.cpp. */
 JS_DECLARE_CALLINFO(js_UnboxDouble)
 JS_DECLARE_CALLINFO(js_UnboxInt32)
 JS_DECLARE_CALLINFO(js_dmod)
 JS_DECLARE_CALLINFO(js_imod)
 JS_DECLARE_CALLINFO(js_DoubleToInt32)
 JS_DECLARE_CALLINFO(js_DoubleToUint32)
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -2356,17 +2356,17 @@ public:
 
     /*
      * Get a type object or function with the specified name.  Fetching the same
      * name repeatedly will produce the same value.
      */
 
     /* Get a function or non-function object. */
     inline js::types::TypeObject *
-    getTypeObject(const char *name, bool isFunction);
+    getTypeObject(const char *name, bool isArray, bool isFunction);
 
     /* Get a function with the specified handler. */
     inline js::types::TypeFunction *
     getTypeFunctionHandler(const char *name, JSTypeHandler handler);
 
     /* Set the type information for fun to the specified script. */
     inline void
     setTypeFunctionScript(JSFunction *fun, JSScript *script);
@@ -2413,16 +2413,19 @@ public:
     inline void addTypeProperty(js::types::TypeObject *obj, const char *name, js::types::jstype type);
     inline void addTypeProperty(js::types::TypeObject *obj, const char *name, const js::Value &value);
     inline void addTypePropertyId(js::types::TypeObject *obj, jsid id, js::types::jstype type);
     inline void addTypePropertyId(js::types::TypeObject *obj, jsid id, const js::Value &value);
 
     /* Alias two properties in the type information for obj. */
     inline void aliasTypeProperties(js::types::TypeObject *obj, jsid first, jsid second);
 
+    /* Mark an array type as being not packed and, possibly, not dense. */
+    inline void markTypeArrayNotPacked(js::types::TypeObject *obj, bool notDense);
+
   private:
     /* To silence MSVC warning about using 'this' in a member initializer. */
     JSContext *thisInInitializer() { return this; }
 };
 
 #ifdef JS_THREADSAFE
 # define JS_THREAD_ID(cx)       ((cx)->thread ? (cx)->thread->id : 0)
 #endif
--- a/js/src/jscompartment.cpp
+++ b/js/src/jscompartment.cpp
@@ -236,17 +236,17 @@ JSCompartment::wrap(JSContext *cx, Value
      * to the object.
      */
     JSObject *wrapper = cx->runtime->wrapObjectCallback(cx, obj, proto, global, flags);
     if (!wrapper)
         return false;
 
     vp->setObject(*wrapper);
 
-    wrapper->setProto(proto);
+    wrapper->setProto(cx, proto);
     if (!crossCompartmentWrappers.put(wrapper->getProxyPrivate(), *vp))
         return false;
 
     wrapper->setParent(global);
     return true;
 }
 
 bool
--- a/js/src/jsexn.cpp
+++ b/js/src/jsexn.cpp
@@ -1029,17 +1029,17 @@ js_InitExceptionClasses(JSContext *cx, J
 #ifdef __GNUC__
     error_proto = NULL;   /* quell GCC overwarning */
 #endif
 
     /*
      * use a single type object for Error and all exceptions which
      * inherit properties from it.
      */
-    TypeObject *protoType = cx->getTypeObject("Error.prototype", false);
+    TypeObject *protoType = cx->getTypeObject("Error.prototype", false, false);
     TypeObject *errorType = cx->getFixedTypeObject(TYPE_OBJECT_NEW_ERROR);
     cx->addTypePrototype(protoType, obj_proto->getTypeObject());
     cx->addTypePrototype(errorType, protoType);
 
     jsval empty = STRING_TO_JSVAL(cx->runtime->emptyString);
 
     /* Initialize the prototypes first. */
     for (intN i = JSEXN_ERR; i != JSEXN_LIMIT; i++) {
@@ -1065,17 +1065,17 @@ js_InitExceptionClasses(JSContext *cx, J
         /* Get the text name of this function, needs to be in sync with jsatom.h.  Blech. */
         JSProtoKey protoKey = GetExceptionProtoKey(i);
         const char *fullName = js_common_atom_names[1 + 2 + JSTYPE_LIMIT + 1 + protoKey];
 
         /*
          * Mark the function as a builtin before constructing and adding it to the global
          * object, which could trigger accesses on its properties.
          */
-        cx->markTypeBuiltinFunction(cx->getTypeObject(fullName, true));
+        cx->markTypeBuiltinFunction(cx->getTypeObject(fullName, false, true));
 
         /* Make a constructor function for the current name. */
         JSAtom *atom = cx->runtime->atomState.classAtoms[protoKey];
         JSFunction *fun = js_DefineFunction(cx, obj, atom, Exception, 3, JSFUN_CONSTRUCTOR,
                                             error_TypeNew, fullName);
         if (!fun)
             return NULL;
         roots[2] = OBJECT_TO_JSVAL(FUN_OBJECT(fun));
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -2632,17 +2632,17 @@ SetProtoCheckingForCycles(JSContext *cx,
     for (JSObject *obj2 = proto; obj2;) {
         if (obj2 == obj) {
             cycle = true;
             break;
         }
         obj2 = obj2->getProto();
     }
     if (!cycle)
-        obj->setProto(proto);
+        obj->setProto(cx, proto);
 
     return !cycle;
 }
 
 JSCompartment *
 NewCompartment(JSContext *cx, JSPrincipals *principals)
 {
     JSRuntime *rt = cx->runtime;
--- a/js/src/jsgcinlines.h
+++ b/js/src/jsgcinlines.h
@@ -248,17 +248,17 @@ MarkChildren(JSTracer *trc, JSObject *ob
         return;
 
     /* Trace universal (ops-independent) members. */
     if (JSObject *proto = obj->getProto())
         MarkObject(trc, *proto, "proto");
     if (JSObject *parent = obj->getParent())
         MarkObject(trc, *parent, "parent");
 
-    if (obj->emptyShapes) {
+    if (!obj->isDenseArray() && obj->emptyShapes) {
         int count = FINALIZE_OBJECT_LAST - FINALIZE_OBJECT0 + 1;
         for (int i = 0; i < count; i++) {
             if (obj->emptyShapes[i])
                 obj->emptyShapes[i]->trace(trc);
         }
     }
 
     /* Delegate to ops or the native marking op. */
--- a/js/src/jsinfer.cpp
+++ b/js/src/jsinfer.cpp
@@ -535,16 +535,20 @@ TypeConstraintProp::newType(JSContext *c
         cx->compartment->types.monitorBytecode(code);
         return;
     }
 
     TypeObject *object = GetPropertyObject(cx, type);
     if (!object)
         return;
 
+    /* Mark arrays with possible non-integer properties as not dense. */
+    if (assign && !JSID_IS_VOID(id))
+        cx->markTypeArrayNotPacked(object, true);
+
     TypeSet *types = object->properties(cx).getVariable(cx, id);
 
     /* Capture the effects of a standard property access. */
     if (target) {
         if (assign)
             target->addSubset(cx, code->pool(), types);
         else
             types->addMonitorRead(cx, object->pool(), code, target);
@@ -862,21 +866,255 @@ public:
         }
 
         typeUnknown = true;
 
         /* Need to trigger recompilation of the script here. :FIXME: bug 608746 */
     }
 };
 
-void
-TypeSet::addFreezeTypeTag(JSContext *cx, JSScript *script, bool isConstructing)
+static inline JSValueType
+GetValueTypeFromTypeFlags(TypeFlags flags)
+{
+    switch (flags) {
+      case TYPE_FLAG_UNDEFINED:
+        return JSVAL_TYPE_UNDEFINED;
+      case TYPE_FLAG_NULL:
+        return JSVAL_TYPE_NULL;
+      case TYPE_FLAG_BOOLEAN:
+        return JSVAL_TYPE_BOOLEAN;
+      case TYPE_FLAG_INT32:
+        return JSVAL_TYPE_INT32;
+      case TYPE_FLAG_STRING:
+        return JSVAL_TYPE_STRING;
+      case TYPE_FLAG_OBJECT:
+        return JSVAL_TYPE_OBJECT;
+      default:
+        return JSVAL_TYPE_UNKNOWN;
+    }
+}
+
+JSValueType
+TypeSet::getKnownTypeTag(JSContext *cx, JSScript *script, bool isConstructing)
 {
     JS_ASSERT(this->pool == &script->analysis->pool);
-    add(cx, ArenaNew<TypeConstraintFreezeTypeTag>(script->analysis->pool, script, isConstructing), false);
+
+    JSValueType type = GetValueTypeFromTypeFlags(typeFlags);
+
+    if (type != JSVAL_TYPE_UNKNOWN)
+        add(cx, ArenaNew<TypeConstraintFreezeTypeTag>(script->analysis->pool, script, isConstructing), false);
+
+    return type;
+}
+
+/* Compute the meet of kind with the kind of object, per the ObjectKind lattice. */
+static inline ObjectKind
+CombineObjectKind(TypeObject *object, ObjectKind kind)
+{
+    ObjectKind nkind;
+    if (object->isFunction)
+        nkind = object->asFunction()->script ? OBJECT_SCRIPTED_FUNCTION : OBJECT_NATIVE_FUNCTION;
+    else if (object->isPackedArray)
+        nkind = OBJECT_PACKED_ARRAY;
+    else if (object->isDenseArray)
+        nkind = OBJECT_DENSE_ARRAY;
+    else
+        nkind = OBJECT_UNKNOWN;
+
+    if (kind == OBJECT_UNKNOWN || nkind == OBJECT_UNKNOWN)
+        return OBJECT_UNKNOWN;
+
+    if (kind == nkind || kind == OBJECT_NONE)
+        return nkind;
+
+    if ((kind == OBJECT_PACKED_ARRAY && nkind == OBJECT_DENSE_ARRAY) ||
+        (kind == OBJECT_DENSE_ARRAY && nkind == OBJECT_PACKED_ARRAY)) {
+        return OBJECT_DENSE_ARRAY;
+    }
+
+    return OBJECT_UNKNOWN;
+}
+
+/* Constraint which triggers recompilation if an array becomes not-packed or not-dense. */
+class TypeConstraintFreezeArray : public TypeConstraint
+{
+public:
+    /*
+     * Array kind being specialized on by the FreezeObjectConstraint.  This may have
+     * become OBJECT_UNKNOWN due to subsequent type changes and recompilation.
+     */
+    ObjectKind *pkind;
+
+    JSScript *script;
+    bool isConstructing;
+
+    TypeConstraintFreezeArray(ObjectKind *pkind, JSScript *script, bool isConstructing)
+        : TypeConstraint("freezeArray"),
+          pkind(pkind), script(script), isConstructing(isConstructing)
+    {
+        JS_ASSERT(*pkind == OBJECT_PACKED_ARRAY || *pkind == OBJECT_DENSE_ARRAY);
+    }
+
+    void newType(JSContext *cx, TypeSet *source, jstype type) {}
+
+    void arrayNotPacked(JSContext *cx, bool notDense)
+    {
+        if (*pkind == OBJECT_UNKNOWN) {
+            /* Despecialized the kind we were interested in due to recompilation. */
+            return;
+        }
+
+        JS_ASSERT(*pkind == OBJECT_PACKED_ARRAY || *pkind == OBJECT_DENSE_ARRAY);
+
+        if (!notDense && *pkind == OBJECT_DENSE_ARRAY) {
+            /* Marking an array as not packed, but we were already accounting for this. */
+            return;
+        }
+
+        /* Need to trigger recompilation of the script here. :FIXME: bug 608746 */
+    }
+};
+
+/*
+ * Constraint which triggers recompilation if objects of a different kind are
+ * added to a type set.
+ */
+class TypeConstraintFreezeObjectKind : public TypeConstraint
+{
+public:
+    ObjectKind kind;
+    JSScript *script;
+    bool isConstructing;
+
+    TypeConstraintFreezeObjectKind(ObjectKind kind, JSScript *script, bool isConstructing)
+        : TypeConstraint("freezeObjectKind"),
+          kind(kind), script(script), isConstructing(isConstructing)
+    {}
+
+    void newType(JSContext *cx, TypeSet *source, jstype type)
+    {
+        if (kind == OBJECT_UNKNOWN) {
+            /* Despecialized the kind we were interested in due to recompilation. */
+            return;
+        }
+
+        if (type == TYPE_UNKNOWN) {
+            kind = OBJECT_UNKNOWN;
+        } else if (TypeIsObject(type)) {
+            TypeObject *object = (TypeObject *) type;
+            ObjectKind nkind = CombineObjectKind(object, kind);
+
+            if (nkind != OBJECT_UNKNOWN &&
+                (kind == OBJECT_PACKED_ARRAY || kind == OBJECT_DENSE_ARRAY)) {
+                /*
+                 * Arrays can become not-packed or not-dense dynamically.
+                 * Add a constraint on the element type of the object to pick
+                 * up such changes.
+                 */
+                TypeSet *elementTypes = object->indexTypes(cx);
+                elementTypes->add(cx,
+                    ArenaNew<TypeConstraintFreezeArray>(object->pool(),
+                                                        &kind, script, isConstructing), false);
+            }
+
+            if (nkind == kind) {
+                /* New object with the same kind we are interested in. */
+                return;
+            }
+            kind = nkind;
+        }
+
+        /* Need to trigger recompilation of the script here. :FIXME: bug 608746 */
+    }
+};
+
+ObjectKind
+TypeSet::getKnownObjectKind(JSContext *cx, JSScript *script, bool isConstructing)
+{
+    JS_ASSERT(this->pool == &script->analysis->pool);
+
+    ObjectKind kind = OBJECT_NONE;
+
+    if (objectCount >= 2) {
+        unsigned objectCapacity = HashSetCapacity(objectCount);
+        for (unsigned i = 0; i < objectCapacity; i++) {
+            TypeObject *object = objectSet[i];
+            if (object)
+                kind = CombineObjectKind(object, kind);
+        }
+    } else if (objectCount == 1) {
+        kind = CombineObjectKind((TypeObject *) objectSet, kind);
+    }
+
+    if (kind != OBJECT_UNKNOWN) {
+        /*
+         * Watch for new objects of different kind, and re-traverse existing types
+         * in this set to add any needed FreezeArray constraints.
+         */
+        add(cx, ArenaNew<TypeConstraintFreezeObjectKind>(script->analysis->pool,
+                                                         kind, script, isConstructing), true);
+    }
+
+    return kind;
+}
+
+/*
+ * Constraint which triggers recompilation of a script if a getter or setter is added
+ * to a type set.
+ */
+class TypeConstraintFreezeGetSet : public TypeConstraint
+{
+public:
+    JSScript *script;
+    bool isConstructing;
+
+    bool hasGetSet;
+
+    TypeConstraintFreezeGetSet(JSScript *script, bool isConstructing)
+        : TypeConstraint("freezeGetSet"),
+          script(script), isConstructing(isConstructing), hasGetSet(false)
+    {}
+
+    void newType(JSContext *cx, TypeSet *source, jstype type)
+    {
+        if (hasGetSet)
+            return;
+
+        if (type != TYPE_UNKNOWN) {
+            if (!TypeIsObject(type))
+                return;
+            if (cx->getFixedTypeObject(TYPE_OBJECT_GETSET) != (TypeObject *) type)
+                return;
+        }
+
+        hasGetSet = true;
+
+        /* Need to trigger recompilation of the script here. :FIXME: bug 608746 */
+    }
+};
+
+bool
+TypeSet::hasGetterSetter(JSContext *cx, JSScript *script, bool isConstructing)
+{
+    TypeObject *getset = cx->getFixedTypeObject(TYPE_OBJECT_GETSET);
+
+    if (objectCount >= 2) {
+        unsigned objectCapacity = HashSetCapacity(objectCount);
+        for (unsigned i = 0; i < objectCapacity; i++) {
+            if (getset == objectSet[i])
+                return true;
+        }
+    } else if (objectCount == 1) {
+        if (getset == (TypeObject *) objectSet)
+            return true;
+    }
+
+    add(cx, ArenaNew<TypeConstraintFreezeGetSet>(script->analysis->pool, script, isConstructing), true);
+
+    return false;
 }
 
 /////////////////////////////////////////////////////////////////////
 // TypeCompartment
 /////////////////////////////////////////////////////////////////////
 
 /*
  * These names need to be consistent with those of the function, prototype and new
@@ -985,56 +1223,63 @@ TypeCompartment::growPendingArray()
 }
 
 TypeObject *
 TypeCompartment::makeFixedTypeObject(JSContext *cx, FixedTypeObjectName which)
 {
     JS_ASSERT(which < TYPE_OBJECT_FIXED_LIMIT);
     JS_ASSERT(!fixedTypeObjects[which]);
 
-    TypeObject *type = cx->getTypeObject(fixedTypeObjectNames[which], which <= TYPE_OBJECT_FUNCTION_LAST);
+    bool isArray = (which > TYPE_OBJECT_MONITOR_LAST && which <= TYPE_OBJECT_ARRAY_LAST);
+    bool isFunction = (which <= TYPE_OBJECT_FUNCTION_LAST);
+
+    TypeObject *type = cx->getTypeObject(fixedTypeObjectNames[which], isArray, isFunction);
     fixedTypeObjects[which] = type;
 
     if (which <= TYPE_OBJECT_BASE_LAST) {
         /* Nothing */
     } else if (which <= TYPE_OBJECT_MONITOR_LAST) {
         type->setMonitored(cx);
     } else if (which <= TYPE_OBJECT_ARRAY_LAST) {
         cx->addTypePrototype(type, cx->getFixedTypeObject(TYPE_OBJECT_ARRAY_PROTOTYPE));
     } else {
         cx->addTypePrototype(type, cx->getFixedTypeObject(TYPE_OBJECT_OBJECT_PROTOTYPE));
     }
 
     return type;
 }
 
 TypeObject *
-TypeCompartment::getTypeObject(JSContext *cx, analyze::Script *script, const char *name, bool isFunction)
+TypeCompartment::getTypeObject(JSContext *cx, analyze::Script *script, const char *name,
+                               bool isArray, bool isFunction)
 {
 #ifdef JS_TYPE_INFERENCE
     jsid id = ATOM_TO_JSID(js_Atomize(cx, name, strlen(name), 0));
 
     JSArenaPool &pool = script ? script->pool : this->pool;
 
     /*
      * Check for an existing object with the same name first.  If we have one
      * then reuse it.
      */
     ObjectNameTable::AddPtr p = objectNameTable->lookupForAdd(id);
     if (p) {
-        JS_ASSERT(p->value->isFunction == isFunction);
-        JS_ASSERT(&p->value->pool() == &pool);
-        return p->value;
+        js::types::TypeObject *object = p->value;
+        JS_ASSERT(object->isFunction == isFunction);
+        JS_ASSERT(&object->pool() == &pool);
+        if (!isArray && object->isDenseArray)
+            cx->markTypeArrayNotPacked(object, true);
+        return object;
     }
 
     js::types::TypeObject *object;
     if (isFunction)
         object = ArenaNew<TypeFunction>(pool, cx, &pool, id);
     else
-        object = ArenaNew<TypeObject>(pool, cx, &pool, id);
+        object = ArenaNew<TypeObject>(pool, cx, &pool, id, isArray);
 
     TypeObject *&objects = script ? script->objects : this->objects;
     object->next = objects;
     objects = object;
 
     objectNameTable->add(p, id, object);
     return object;
 #else
@@ -1220,20 +1465,21 @@ VariableSet::print(JSContext *cx, FILE *
 
     fprintf(out, "\n}\n");
 }
 
 /////////////////////////////////////////////////////////////////////
 // TypeObject
 /////////////////////////////////////////////////////////////////////
 
-TypeObject::TypeObject(JSContext *cx, JSArenaPool *pool, jsid name)
+TypeObject::TypeObject(JSContext *cx, JSArenaPool *pool, jsid name, bool isArray)
     : name(name), isFunction(false), monitored(false),
       propertySet(pool), propertiesFilled(false), next(NULL),
-      hasObjectPropagation(false), hasArrayPropagation(false), isInitObject(false)
+      hasObjectPropagation(false), hasArrayPropagation(false), isInitObject(false),
+      isDenseArray(isArray), isPackedArray(isArray)
 {
 #ifdef JS_TYPES_DEBUG_SPEW
     propertySet.name = name;
     fprintf(cx->typeOut(), "newObject: %s\n", cx->getTypeId(name));
 #endif
 }
 
 bool
@@ -1279,17 +1525,17 @@ TypeFunction::fillProperties(JSContext *
      */
     TypeObject *funcProto = cx->getFixedTypeObject(TYPE_OBJECT_FUNCTION_PROTOTYPE);
     funcProto->addPropagate(cx, this);
 
     const char *baseName = cx->getTypeId(name);
     unsigned len = strlen(baseName) + 15;
     char *prototypeName = (char *)alloca(len);
     JS_snprintf(prototypeName, len, "%s:prototype", baseName);
-    prototypeObject = cx->getTypeObject(prototypeName, false);
+    prototypeObject = cx->getTypeObject(prototypeName, false, false);
 
     TypeSet *prototypeTypes = propertySet.getVariable(cx, id_prototype(cx));
     prototypeTypes->addType(cx, (jstype) prototypeObject);
 
     /* The prototype inherits properties from Object.prototype. */
     TypeObject *objectProto = cx->getFixedTypeObject(TYPE_OBJECT_OBJECT_PROTOTYPE);
     objectProto->addPropagate(cx, prototypeObject);
 }
@@ -1330,17 +1576,17 @@ TypeObject::print(JSContext *cx, FILE *o
     fputs("\n", out);
 }
 
 /////////////////////////////////////////////////////////////////////
 // TypeFunction
 /////////////////////////////////////////////////////////////////////
 
 TypeFunction::TypeFunction(JSContext *cx, JSArenaPool *pool, jsid name)
-    : TypeObject(cx, pool, name), handler(NULL), script(NULL),
+    : TypeObject(cx, pool, name, false), handler(NULL), script(NULL),
       prototypeObject(NULL), newObject(NULL), returnTypes(pool),
       isBuiltin(false), isGeneric(false)
 {
     isFunction = true;
 
 #ifdef JS_TYPES_DEBUG_SPEW
     fprintf(cx->typeOut(), "newFunction: %s return T%u\n",
             cx->getTypeId(name), returnTypes.id);
@@ -1437,16 +1683,34 @@ JSScript::typeCheckBytecode(JSContext *c
     if (!useCount || code.missingTypes)
         return;
 
     js::types::TypeStack *stack = code.inStack->group();
     for (int i = 0; i < useCount; i++) {
         const js::Value &val = sp[-1 - i];
         js::types::jstype type = js::types::GetValueType(cx, val);
 
+        if (js::types::TypeIsObject(type)) {
+            /* Make sure information about the array status of this object is right. */
+            JS_ASSERT(val.isObject());
+            js::types::TypeObject *object = (js::types::TypeObject *) type;
+
+            JS_ASSERT_IF(object->isPackedArray, object->isDenseArray);
+            if (object->isDenseArray) {
+                if (!val.toObject().isDenseArray() ||
+                    (object->isPackedArray && !val.toObject().isPackedDenseArray())) {
+                    fprintf(cx->typeOut(), "warning: Object not %s array at #%u:%05u: %s",
+                            object->isPackedArray ? "packed" : "dense",
+                            analysis->id, code.offset, cx->getTypeId(object->name));
+                    cx->compartment->types.warnings = true;
+                    object->isDenseArray = object->isPackedArray = false;
+                }
+            }
+        }
+
         bool matches = IgnorePopped(op, i) || stack->types.hasType(type);
 
         stack = stack->innerStack ? stack->innerStack->group() : NULL;
 
         if (!matches) {
             fprintf(cx->typeOut(), "warning: Missing type at #%u:%05u popped %u: ",
                     analysis->id, code.offset, i);
             js::types::PrintType(cx, type);
--- a/js/src/jsinfer.h
+++ b/js/src/jsinfer.h
@@ -154,16 +154,44 @@ public:
 #ifdef JS_TYPES_DEBUG_SPEW
         id = ++constraintCount;
         kind = _kind;
 #endif
     }
 
     /* Register a new type for the set this constraint is listening to. */
     virtual void newType(JSContext *cx, TypeSet *source, jstype type) = 0;
+
+    /*
+     * Mark the object containing the set this constraint is listening to
+     * as not a packed array and, possibly, not a dense array.
+     */
+    virtual void arrayNotPacked(JSContext *cx, bool notDense) {}
+};
+
+/*
+ * Coarse kinds of a set of objects.  These form the following lattice:
+ *
+ *                    NONE
+ *       ___________ /  | \______________
+ *      /               |                \
+ * PACKED_ARRAY  SCRIPTED_FUNCTION  NATIVE_FUNCTION
+ *      |               |                 |
+ * DENSE_ARRAY          |                 |
+ *      \____________   |   _____________/
+ *                   \  |  /
+ *                   UNKNOWN
+ */
+enum ObjectKind {
+    OBJECT_NONE,
+    OBJECT_UNKNOWN,
+    OBJECT_PACKED_ARRAY,
+    OBJECT_DENSE_ARRAY,
+    OBJECT_SCRIPTED_FUNCTION,
+    OBJECT_NATIVE_FUNCTION
 };
 
 /* Information about the set of types associated with an lvalue. */
 struct TypeSet
 {
 #ifdef JS_TYPES_DEBUG_SPEW
     static unsigned typesetCount;
     unsigned id;
@@ -207,46 +235,49 @@ struct TypeSet
 
     /*
      * Add a type to this set, calling any constraint handlers if this is a new
      * possible type.
      */
     inline void addType(JSContext *cx, jstype type);
 
     /* Add specific kinds of constraints to this set. */
+    inline void add(JSContext *cx, TypeConstraint *constraint, bool callExisting = true);
     void addSubset(JSContext *cx, JSArenaPool &pool, TypeSet *target);
     void addGetProperty(JSContext *cx, analyze::Bytecode *code, TypeSet *target, jsid id);
     void addSetProperty(JSContext *cx, analyze::Bytecode *code, TypeSet *target, jsid id);
     void addGetElem(JSContext *cx, analyze::Bytecode *code, TypeSet *object, TypeSet *target);
     void addSetElem(JSContext *cx, analyze::Bytecode *code, TypeSet *object, TypeSet *target);
     void addCall(JSContext *cx, TypeCallsite *site);
     void addArith(JSContext *cx, JSArenaPool &pool, analyze::Bytecode *code,
                   TypeSet *target, TypeSet *other = NULL);
     void addTransformThis(JSContext *cx, JSArenaPool &pool, TypeSet *target);
     void addFilterPrimitives(JSContext *cx, JSArenaPool &pool, TypeSet *target, bool onlyNullVoid);
     void addMonitorRead(JSContext *cx, JSArenaPool &pool, analyze::Bytecode *code, TypeSet *target);
 
-    /* Constraints inducing recompilation. */
-    void addFreezeTypeTag(JSContext *cx, JSScript *script, bool isConstructing);
+    /*
+     * Make an intermediate type set with the specified debugging name,
+     * not embedded in another structure.
+     */
+    static inline TypeSet* make(JSContext *cx, JSArenaPool &pool, const char *name);
+
+    /* Methods for JIT compilation. */
 
     /*
      * Get any type tag which all values in this set must have.  Should this type
      * set change in the future so that another type tag is possible, mark script
      * for recompilation.
      */
-    inline JSValueType getKnownTypeTag(JSContext *cx, JSScript *script, bool isConstructing);
+    JSValueType getKnownTypeTag(JSContext *cx, JSScript *script, bool isConstructing);
 
-    /*
-     * Make an intermediate type set with the specified debugging name,
-     * not embedded in another structure.
-     */
-    static inline TypeSet* make(JSContext *cx, JSArenaPool &pool, const char *name);
+    /* Get information about the kinds of objects in this type set. */
+    ObjectKind getKnownObjectKind(JSContext *cx, JSScript *script, bool isConstructing);
 
-  private:
-    inline void add(JSContext *cx, TypeConstraint *constraint, bool callExisting = true);
+    /* Get whether this type set contains any scripted getter or setter. */
+    bool hasGetterSetter(JSContext *cx, JSScript *script, bool isConstructing);
 };
 
 /*
  * Type information for a value pushed onto the stack at some execution point.
  * Stack nodes form equivalence classes: if at any time two stack nodes might
  * be at the same depth in the stack, they are considered equivalent.
  */
 struct TypeStack
@@ -407,17 +438,17 @@ struct TypeObject
      * this object instead.
      */
     jsid name;
 
     /* Whether this is a function object, and may be cast into TypeFunction. */
     bool isFunction;
 
     /*
-     * Whether all accesses to this object need to be monitored.  This includes
+     * Whether all reads from this object need to be monitored.  This includes
      * all property and element accesses, and for functions all calls to the function.
      */
     bool monitored;
 
     /*
      * Properties of this object.  This is filled in lazily for function objects
      * to avoid unnecessary property and prototype object creation.  Don't access
      * this directly, use properties() below.
@@ -437,31 +468,33 @@ struct TypeObject
 
     /*
      * Whether this object is keyed to some allocation site.  If a type set only
      * contains objects allocated at different sites, it is not considered
      * to be polymorphic.
      */
     bool isInitObject;
 
+    /* Whether all objects this represents are dense arrays. */
+    bool isDenseArray;
+
+    /* Whether all objects this represents are packed arrays (implies isDenseArray). */
+    bool isPackedArray;
+
     /* Make an object with the specified name. */
-    TypeObject(JSContext *cx, JSArenaPool *pool, jsid id);
+    TypeObject(JSContext *cx, JSArenaPool *pool, jsid id, bool isArray);
 
     /* Propagate properties from this object to target. */
     bool addPropagate(JSContext *cx, TypeObject *target, bool excludePrototype = true);
 
     /* Coerce this object to a function. */
     TypeFunction* asFunction()
     {
-        if (isFunction) {
-            return (TypeFunction*) this;
-        } else {
-            JS_NOT_REACHED("Object is not a function");
-            return NULL;
-        }
+        JS_ASSERT(isFunction);
+        return (TypeFunction *) this;
     }
 
     JSArenaPool & pool() { return *propertySet.pool; }
 
     /* Get the properties of this object, filled in lazily. */
     inline VariableSet& properties(JSContext *cx);
 
     /* Get the type set for all integer index properties of this object. */
@@ -749,17 +782,17 @@ struct TypeCompartment
 
     /* Resolve pending type registrations, excluding delayed ones. */
     inline void resolvePending(JSContext *cx);
 
     void print(JSContext *cx, JSCompartment *compartment);
 
     /* Get a function or non-function object associated with an optional script. */
     TypeObject *getTypeObject(JSContext *cx, js::analyze::Script *script,
-                              const char *name, bool isFunction);
+                              const char *name, bool isArray, bool isFunction);
 
     /*
      * Add the specified type to the specified set, and do any necessary reanalysis
      * stemming from the change.
      */
     void addDynamicType(JSContext *addCx, TypeSet *types, jstype type,
                         const char *format, ...);
 
--- a/js/src/jsinferinlines.h
+++ b/js/src/jsinferinlines.h
@@ -133,31 +133,31 @@ MakeTypeId(jsid id)
 
 #endif /* JS_TYPE_INFERENCE */
 
 /////////////////////////////////////////////////////////////////////
 // JSContext
 /////////////////////////////////////////////////////////////////////
 
 inline js::types::TypeObject *
-JSContext::getTypeObject(const char *name, bool isFunction)
+JSContext::getTypeObject(const char *name, bool isArray, bool isFunction)
 {
 #ifdef JS_TYPE_INFERENCE
-    return compartment->types.getTypeObject(this, NULL, name, isFunction);
+    return compartment->types.getTypeObject(this, NULL, name, isArray, isFunction);
 #else
     return NULL;
 #endif
 }
 
 inline js::types::TypeObject *
 JSContext::getGlobalTypeObject()
 {
 #ifdef JS_TYPE_INFERENCE
     if (!compartment->types.globalObject)
-        compartment->types.globalObject = getTypeObject("Global", false);
+        compartment->types.globalObject = getTypeObject("Global", false, false);
     return compartment->types.globalObject;
 #else
     return NULL;
 #endif
 }
 
 inline FILE *
 JSContext::typeOut()
@@ -221,17 +221,17 @@ JSContext::getTypeId(jsid id)
 inline void
 JSContext::setTypeFunctionScript(JSFunction *fun, JSScript *script)
 {
 #ifdef JS_TYPE_INFERENCE
     char name[8];
     JS_snprintf(name, 16, "#%u", script->analysis->id);
 
     js::types::TypeFunction *typeFun =
-        compartment->types.getTypeObject(this, script->analysis, name, true)->asFunction();
+        compartment->types.getTypeObject(this, script->analysis, name, false, true)->asFunction();
 
     /* We should not be attaching multiple scripts to the same function. */
     if (typeFun->script) {
         JS_ASSERT(typeFun->script == script);
         fun->typeObject = typeFun;
         return;
     }
 
@@ -242,17 +242,17 @@ JSContext::setTypeFunctionScript(JSFunct
 #endif
 }
 
 inline js::types::TypeFunction *
 JSContext::getTypeFunctionHandler(const char *name, JSTypeHandler handler)
 {
 #ifdef JS_TYPE_INFERENCE
     js::types::TypeFunction *typeFun =
-        compartment->types.getTypeObject(this, NULL, name, true)->asFunction();
+        compartment->types.getTypeObject(this, NULL, name, false, true)->asFunction();
 
     if (typeFun->handler) {
         /* Saw this function before, make sure it has the same behavior. */
         JS_ASSERT(typeFun->handler == handler);
         return typeFun;
     }
 
     typeFun->handler = handler;
@@ -413,16 +413,39 @@ JSContext::aliasTypeProperties(js::types
     js::types::TypeSet *secondTypes = obj->properties(this).getVariable(this, second);
 
     firstTypes->addSubset(this, obj->pool(), secondTypes);
     secondTypes->addSubset(this, obj->pool(), firstTypes);
 #endif
 }
 
 inline void
+JSContext::markTypeArrayNotPacked(js::types::TypeObject *obj, bool notDense)
+{
+#ifdef JS_TYPE_INFERENCE
+    if (notDense) {
+        if (!obj->isDenseArray)
+            return;
+        obj->isDenseArray = false;
+    } else if (!obj->isPackedArray) {
+        return;
+    }
+    obj->isPackedArray = false;
+
+    /* All constraints listening to changes in packed/dense status are on the element types. */
+    js::types::TypeSet *elementTypes = obj->properties(this).getVariable(this, JSID_VOID);
+    js::types::TypeConstraint *constraint = elementTypes->constraintList;
+    while (constraint) {
+        constraint->arrayNotPacked(this, notDense);
+        constraint = constraint->next;
+    }
+#endif
+}
+
+inline void
 JSContext::typeMonitorCall(JSScript *caller, const jsbytecode *callerpc,
                            const js::CallArgs &args, bool constructing, bool force)
 {
     JS_ASSERT_IF(caller == NULL, force);
 #ifdef JS_TYPE_INFERENCE
     if (!args.callee().isObject() || !args.callee().toObject().isFunction())
         return;
     js::types::TypeFunction *fun = args.callee().toObject().getTypeObject()->asFunction();
@@ -687,17 +710,17 @@ Bytecode::setFixed(JSContext *cx, unsign
 }
 
 inline types::TypeObject *
 Bytecode::getInitObject(JSContext *cx, bool isArray)
 {
     if (!initObject) {
         char name[32];
         JS_snprintf(name, 32, "#%u:%u", script->id, offset);
-        initObject = cx->compartment->types.getTypeObject(cx, script, name, false);
+        initObject = cx->compartment->types.getTypeObject(cx, script, name, isArray, false);
         initObject->isInitObject = true;
     }
 
     /*
      * Add the propagation even if there was already an object, as Object/Array
      * could *both* be invoked for this value.
      */
 
@@ -1114,49 +1137,16 @@ TypeSet::addType(JSContext *cx, jstype t
     while (constraint) {
         cx->compartment->types.addPending(cx, constraint, this, type);
         constraint = constraint->next;
     }
 
     cx->compartment->types.resolvePending(cx);
 }
 
-inline JSValueType
-TypeSet::getKnownTypeTag(JSContext *cx, JSScript *script, bool isConstructing)
-{
-    JSValueType type;
-    switch (typeFlags) {
-      case TYPE_FLAG_UNDEFINED:
-        type = JSVAL_TYPE_UNDEFINED;
-        break;
-      case TYPE_FLAG_NULL:
-        type = JSVAL_TYPE_NULL;
-        break;
-      case TYPE_FLAG_BOOLEAN:
-        type = JSVAL_TYPE_BOOLEAN;
-        break;
-      case TYPE_FLAG_INT32:
-        type = JSVAL_TYPE_INT32;
-        break;
-      case TYPE_FLAG_STRING:
-        type = JSVAL_TYPE_STRING;
-        break;
-      case TYPE_FLAG_OBJECT:
-        type = JSVAL_TYPE_OBJECT;
-        break;
-      default:
-        /* Return directly to avoid adding a type constraint. */
-        return JSVAL_TYPE_UNKNOWN;
-    }
-
-    addFreezeTypeTag(cx, script, isConstructing);
-
-    return type;
-}
-
 inline TypeSet *
 TypeSet::make(JSContext *cx, JSArenaPool &pool, const char *name)
 {
     TypeSet *res = ArenaNew<TypeSet>(pool, &pool);
 
 #ifdef JS_TYPES_DEBUG_SPEW
     fprintf(cx->typeOut(), "intermediate %s T%u\n", name, res->id);
 #endif
@@ -1290,17 +1280,17 @@ TypeFunction::getNewObject(JSContext *cx
         return newObject;
 
     const char *baseName = cx->getTypeId(name);
 
     unsigned len = strlen(baseName) + 10;
     char *newName = (char *) alloca(len);
     JS_snprintf(newName, len, "%s:new", baseName);
     newObject = cx->compartment->types.getTypeObject(cx, script ? script->analysis : NULL,
-                                                     newName, false);
+                                                     newName, false, false);
 
     properties(cx);
     JS_ASSERT_IF(!prototypeObject, isBuiltin);
 
     /*
      * Propagate properties from the prototype of this script to any objects
      * to any objects created using 'new' on this script.
      */
--- a/js/src/jsinterp.cpp
+++ b/js/src/jsinterp.cpp
@@ -4542,18 +4542,17 @@ BEGIN_CASE(JSOP_GETELEM)
 
     const Value *copyFrom;
     Value rval;
     jsid id;
     if (rref.isInt32()) {
         int32_t i = rref.toInt32();
         if (obj->isDenseArray()) {
             jsuint idx = jsuint(i);
-
-            if (idx < obj->getDenseArrayCapacity()) {
+            if (idx < obj->getDenseArrayInitializedLength()) {
                 copyFrom = obj->addressOfDenseArrayElement(idx);
                 if (!copyFrom->isMagic())
                     goto end_getelem;
             }
         } else if (obj->isArguments()) {
             uint32 arg = uint32(i);
 
             if (arg < obj->getArgsInitialLength()) {
@@ -4628,17 +4627,17 @@ BEGIN_CASE(JSOP_SETELEM)
     JSObject *obj;
     FETCH_OBJECT(cx, -3, obj);
     jsid id;
     FETCH_ELEMENT_ID(obj, -2, id);
     Value rval;
     TYPE_MONITOR_ASSIGN(cx, obj, id, regs.sp[-1]);
     do {
         if (obj->isDenseArray() && JSID_IS_INT(id)) {
-            jsuint length = obj->getDenseArrayCapacity();
+            jsuint length = obj->getDenseArrayInitializedLength();
             jsint i = JSID_TO_INT(id);
             if ((jsuint)i < length) {
                 if (obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
                     if (js_PrototypeHasIndexedProperties(cx, obj))
                         break;
                     if ((jsuint)i >= obj->getArrayLength())
                         obj->setArrayLength(cx, i + 1);
                 }
--- a/js/src/jsiter.cpp
+++ b/js/src/jsiter.cpp
@@ -283,19 +283,19 @@ EnumerateDenseArrayProperties(JSContext 
                               IdSet &ht, typename EnumPolicy::ResultVector *props)
 {
     if (!Enumerate<EnumPolicy>(cx, obj, pobj, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom), false, true,
                                flags, ht, props)) {
         return false;
     }
 
     if (pobj->getArrayLength() > 0) {
-        size_t capacity = pobj->getDenseArrayCapacity();
+        size_t initlen = pobj->getDenseArrayInitializedLength();
         Value *vp = pobj->getDenseArrayElements();
-        for (size_t i = 0; i < capacity; ++i, ++vp) {
+        for (size_t i = 0; i < initlen; ++i, ++vp) {
             if (!vp->isMagic(JS_ARRAY_HOLE)) {
                 /* Dense arrays never get so large that i would not fit into an integer id. */
                 if (!Enumerate<EnumPolicy>(cx, obj, pobj, INT_TO_JSID(i), true, false, flags, ht, props))
                     return false;
             }
         }
     }
 
--- a/js/src/jsmath.cpp
+++ b/js/src/jsmath.cpp
@@ -892,17 +892,17 @@ js_IsMathFunction(JSNative native)
             return true;
     }
     return false;
 }
 
 JSObject *
 js_InitMathClass(JSContext *cx, JSObject *obj)
 {
-    types::TypeObject *type = cx->getTypeObject(js_Math_str, false);
+    types::TypeObject *type = cx->getTypeObject(js_Math_str, false, false);
     JSObject *Math = NewNonFunction<WithProto::Class>(cx, &js_MathClass, NULL, obj, type);
     if (!Math)
         return NULL;
     if (!JS_DefinePropertyWithType(cx, obj, js_Math_str, OBJECT_TO_JSVAL(Math),
                                    JS_PropertyStub, JS_PropertyStub, 0)) {
         return NULL;
     }
 
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -3632,17 +3632,17 @@ js_InitClass(JSContext *cx, JSObject *ob
     TypeObject *protoType = NULL;
 #ifdef JS_TYPE_INFERENCE
     size_t protoLen = strlen(clasp->name) + 15;
     char *protoName = (char*) alloca(protoLen);
     JS_snprintf(protoName, protoLen, "%s:prototype", clasp->name);
     if (clasp == &js_FunctionClass)
         protoType = cx->getTypeFunctionHandler(protoName, JS_TypeHandlerVoid);
     else
-        protoType = cx->getTypeObject(protoName, false);
+        protoType = cx->getTypeObject(protoName, false, false);
 #endif
 
     /*
      * Create a prototype object for this class.
      *
      * FIXME: lazy standard (built-in) class initialization and even older
      * eager boostrapping code rely on all of these properties:
      *
@@ -3731,17 +3731,17 @@ js_InitClass(JSContext *cx, JSObject *ob
         /* Connect constructor and prototype by named properties. */
         if (!js_SetClassPrototype(cx, ctor, proto,
                                   JSPROP_READONLY | JSPROP_PERMANENT)) {
             goto bad;
         }
 
         /* Bootstrap Function.prototype (see also JS_InitStandardClasses). */
         if (ctor->getClass() == clasp)
-            ctor->setProto(proto);
+            ctor->setProto(cx, proto);
 
 #ifdef JS_TYPE_INFERENCE
         if (clasp == &js_FunctionClass) {
             /*
              * Fixup the type information for the prototype class. protoType
              * was ignored when proto was constructed.
              */
             proto->typeObject = protoType;
@@ -3901,33 +3901,35 @@ void
 JSObject::shrinkSlots(JSContext *cx, size_t newcap)
 {
     uint32 oldcap = numSlots();
     JS_ASSERT(newcap <= oldcap);
     JS_ASSERT(newcap >= slotSpan());
 
     if (oldcap <= SLOT_CAPACITY_MIN || !hasSlotsArray()) {
         /* We won't shrink the slots any more.  Clear excess holes. */
-        ClearValueRange(slots + newcap, oldcap - newcap, isDenseArray());
+        if (!isDenseArray())
+            ClearValueRange(slots + newcap, oldcap - newcap, false);
         return;
     }
 
     uint32 fill = newcap;
     if (newcap < SLOT_CAPACITY_MIN)
         newcap = SLOT_CAPACITY_MIN;
 
     Value *tmpslots = (Value*) cx->realloc(slots, newcap * sizeof(Value));
     if (!tmpslots)
         return;  /* Leave slots at its old size. */
     slots = tmpslots;
     capacity = newcap;
 
     if (fill < newcap) {
         /* Clear any excess holes if we tried to shrink below SLOT_CAPACITY_MIN. */
-        ClearValueRange(slots + fill, newcap - fill, isDenseArray());
+        if (!isDenseArray())
+            ClearValueRange(slots + fill, newcap - fill, false);
     }
 }
 
 bool
 JSObject::ensureInstanceReservedSlots(JSContext *cx, size_t nreserved)
 {
     JS_ASSERT_IF(isNative(),
                  isBlock() || isCall() || (isFunction() && isBoundFunction()));
@@ -3973,17 +3975,17 @@ SetProto(JSContext *cx, JSObject *obj, J
      */
     JSObject *oldproto = obj;
     while (oldproto && oldproto->isNative()) {
         oldproto->protoShapeChange(cx);
         oldproto = oldproto->getProto();
     }
 
     if (!proto || !checkForCycles) {
-        obj->setProto(proto);
+        obj->setProto(cx, proto);
     } else if (!SetProtoCheckingForCycles(cx, obj, proto)) {
         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_CYCLIC_VALUE, js_proto_str);
         return false;
     }
     return true;
 }
 
 }
@@ -6571,17 +6573,17 @@ js_DumpObject(JSObject *obj)
             anyFlags = true;
         }
     }
     if (!anyFlags)
         fprintf(stderr, " none");
     fprintf(stderr, "\n");
 
     if (obj->isDenseArray()) {
-        unsigned slots = JS_MIN(obj->getArrayLength(), obj->getDenseArrayCapacity());
+        unsigned slots = obj->getDenseArrayInitializedLength();
         fprintf(stderr, "elements\n");
         for (unsigned i = 0; i < slots; i++) {
             fprintf(stderr, " %3d: ", i);
             dumpValue(obj->getDenseArrayElement(i));
             fprintf(stderr, "\n");
             fflush(stderr);
         }
         return;
--- a/js/src/jsobj.h
+++ b/js/src/jsobj.h
@@ -334,33 +334,39 @@ struct JSObject : js::gc::Cell {
         SYSTEM          = 0x02,
         NOT_EXTENSIBLE  = 0x04,
         BRANDED         = 0x08,
         GENERIC         = 0x10,
         METHOD_BARRIER  = 0x20,
         INDEXED         = 0x40,
         OWN_SHAPE       = 0x80,
         BOUND_FUNCTION  = 0x100,
-        HAS_EQUALITY    = 0x200
+        HAS_EQUALITY    = 0x200,
+        PACKED_ARRAY    = 0x400
     };
 
     /*
      * Impose a sane upper bound, originally checked only for dense arrays, on
      * number of slots in an object.
      */
     enum {
         NSLOTS_BITS     = 29,
         NSLOTS_LIMIT    = JS_BIT(NSLOTS_BITS)
     };
 
     uint32      flags;                      /* flags */
     uint32      objShape;                   /* copy of lastProp->shape, or override if different */
 
-    /* If prototype, lazily filled array of empty shapes for each object size. */
-    js::EmptyShape **emptyShapes;
+    union {
+        /* If prototype, lazily filled array of empty shapes for each object size. */
+        js::EmptyShape **emptyShapes;
+
+        /* If dense array, initialized length of the array. */
+        jsuword initializedLength;
+    };
 
     JSObject    *proto;                     /* object's prototype */
     JSObject    *parent;                    /* object's parent */
     void        *privateData;               /* private data */
     jsuword     capacity;                   /* capacity of slots */
     js::Value   *slots;                     /* dynamically allocated slots,
                                                or pointer to fixedSlots() */
 
@@ -650,24 +656,17 @@ struct JSObject : js::gc::Cell {
     inline void updateFlags(const js::Shape *shape, bool isDefinitelyAtom = false);
 
     /* Extend this object to have shape as its last-added property. */
     inline void extend(JSContext *cx, const js::Shape *shape, bool isDefinitelyAtom = false);
 
     JSObject *getProto() const  { return proto; }
     void clearProto()           { proto = NULL; }
 
-    void setProto(JSObject *newProto) {
-#ifdef DEBUG
-        for (JSObject *obj = newProto; obj; obj = obj->getProto())
-            JS_ASSERT(obj != this);
-#endif
-        setDelegateNullSafe(newProto);
-        proto = newProto;
-    }
+    inline void setProto(JSContext *cx, JSObject *newProto);
 
     JSObject *getParent() const {
         return parent;
     }
 
     void clearParent() {
         parent = NULL;
     }
@@ -749,23 +748,28 @@ struct JSObject : js::gc::Cell {
     /*
      * Array-specific getters and setters (for both dense and slow arrays).
      */
 
     inline uint32 getArrayLength() const;
     inline void setArrayLength(JSContext *cx, uint32 length);
 
     inline uint32 getDenseArrayCapacity();
+    inline uint32 getDenseArrayInitializedLength();
+    inline void setDenseArrayInitializedLength(uint32 length);
     inline js::Value* getDenseArrayElements();
     inline const js::Value &getDenseArrayElement(uintN idx);
     inline js::Value* addressOfDenseArrayElement(uintN idx);
     inline void setDenseArrayElement(uintN idx, const js::Value &val);
     inline bool ensureDenseArrayElements(JSContext *cx, uintN cap);
     inline void shrinkDenseArrayElements(JSContext *cx, uintN cap);
 
+    inline bool isPackedDenseArray();
+    inline void setDenseArrayNotPacked(JSContext *cx);
+
     JSBool makeDenseArraySlow(JSContext *cx);
 
     /*
      * Arguments-specific getters and setters.
      */
 
   private:
     /*
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -293,41 +293,56 @@ JSObject::setArrayLength(JSContext *cx, 
 
 inline uint32
 JSObject::getDenseArrayCapacity()
 {
     JS_ASSERT(isDenseArray());
     return numSlots();
 }
 
+inline uint32
+JSObject::getDenseArrayInitializedLength()
+{
+    JS_ASSERT(isDenseArray());
+    return initializedLength;
+}
+
+inline void
+JSObject::setDenseArrayInitializedLength(uint32 length)
+{
+    JS_ASSERT(isDenseArray());
+    JS_ASSERT(length <= getDenseArrayCapacity() && length <= getArrayLength());
+    initializedLength = length;
+}
+
 inline js::Value*
 JSObject::getDenseArrayElements()
 {
     JS_ASSERT(isDenseArray());
     return getSlots();
 }
 
 inline const js::Value &
 JSObject::getDenseArrayElement(uintN idx)
 {
-    JS_ASSERT(isDenseArray());
+    JS_ASSERT(isDenseArray() && idx < getDenseArrayInitializedLength());
     return getSlot(idx);
 }
 
 inline js::Value *
 JSObject::addressOfDenseArrayElement(uintN idx)
 {
     JS_ASSERT(isDenseArray());
     return &getSlotRef(idx);
 }
 
 inline void
 JSObject::setDenseArrayElement(uintN idx, const js::Value &val)
 {
-    JS_ASSERT(isDenseArray());
+    JS_ASSERT(isDenseArray() && idx < getDenseArrayInitializedLength());
     setSlot(idx, val);
 }
 
 inline bool
 JSObject::ensureDenseArrayElements(JSContext *cx, uintN cap)
 {
     JS_ASSERT(isDenseArray());
     return ensureSlots(cx, cap);
@@ -335,16 +350,33 @@ JSObject::ensureDenseArrayElements(JSCon
 
 inline void
 JSObject::shrinkDenseArrayElements(JSContext *cx, uintN cap)
 {
     JS_ASSERT(isDenseArray());
     shrinkSlots(cx, cap);
 }
 
+inline bool
+JSObject::isPackedDenseArray()
+{
+    JS_ASSERT(isDenseArray());
+    return flags & PACKED_ARRAY;
+}
+
+inline void
+JSObject::setDenseArrayNotPacked(JSContext *cx)
+{
+    JS_ASSERT(isDenseArray());
+    if (flags & PACKED_ARRAY) {
+        flags ^= PACKED_ARRAY;
+        cx->markTypeArrayNotPacked(getTypeObject(), false);
+    }
+}
+
 inline void
 JSObject::setArgsLength(uint32 argc)
 {
     JS_ASSERT(isArguments());
     JS_ASSERT(argc <= JS_ARGS_LENGTH_MAX);
     JS_ASSERT(UINT32_MAX > (uint64(argc) << ARGS_PACKED_BITS_COUNT));
     getSlotRef(JSSLOT_ARGS_LENGTH).setInt32(argc << ARGS_PACKED_BITS_COUNT);
     JS_ASSERT(!isArgsLengthOverridden());
@@ -586,64 +618,83 @@ JSObject::getWithThis() const
 
 inline void
 JSObject::setWithThis(JSObject *thisp)
 {
     getSlotRef(JSSLOT_WITH_THIS).setObject(*thisp);
 }
 
 inline void
+JSObject::setProto(JSContext *cx, JSObject *newProto)
+{
+#ifdef DEBUG
+    for (JSObject *obj = newProto; obj; obj = obj->getProto())
+        JS_ASSERT(obj != this);
+#endif
+    if (newProto && newProto->isDenseArray())
+        newProto->makeDenseArraySlow(cx);
+
+    setDelegateNullSafe(newProto);
+    proto = newProto;
+}
+
+inline void
 JSObject::init(JSContext *cx, js::Class *aclasp, JSObject *proto, JSObject *parent,
                js::types::TypeObject *type, void *priv, bool useHoles)
 {
     clasp = aclasp;
-    flags = 0;
 
 #ifdef DEBUG
     /*
      * NB: objShape must not be set here; rather, the caller must call setMap
      * or setSharedNonNativeMap after calling init. To defend this requirement
      * we set map to null in DEBUG builds, and set objShape to a value we then
      * assert obj->shape() never returns.
      */
     map = NULL;
     objShape = JSObjectMap::INVALID_SHAPE;
 #endif
 
-    setProto(proto);
+    setProto(cx, proto);
     setParent(parent);
 
     privateData = priv;
     slots = fixedSlots();
 
     /*
-     * Fill the fixed slots with undefined or array holes.  This object must
+     * Fill the fixed slots with undefined if needed.  This object must
      * already have its capacity filled in, as by js_NewGCObject.
      */
     JS_ASSERT(capacity == numFixedSlots());
-    ClearValueRange(slots, capacity, useHoles);
+    JS_ASSERT(useHoles == (aclasp == &js_ArrayClass));
+    if (useHoles) {
+        initializedLength = 0;
+        flags = PACKED_ARRAY;
+    } else {
+        ClearValueRange(slots, capacity, false);
+        emptyShapes = NULL;
+        flags = 0;
+    }
 
 #ifdef JS_TYPE_INFERENCE
     JS_ASSERT_IF(aclasp != &js_FunctionClass, type);
     typeObject = type;
 #endif
-
-    emptyShapes = NULL;
 }
 
 inline void
 JSObject::finish(JSContext *cx)
 {
 #ifdef DEBUG
     if (isNative())
         JS_LOCK_RUNTIME_VOID(cx->runtime, cx->runtime->liveObjectProps -= propertyCount());
 #endif
     if (hasSlotsArray())
         freeSlotsArray(cx);
-    if (emptyShapes)
+    if (!isDenseArray() && emptyShapes)
         cx->free(emptyShapes);
 }
 
 inline bool
 JSObject::initSharingEmptyShape(JSContext *cx,
                                 js::Class *aclasp,
                                 JSObject *proto,
                                 JSObject *parent,
--- a/js/src/json.cpp
+++ b/js/src/json.cpp
@@ -1254,17 +1254,17 @@ static JSFunctionSpec json_static_method
     JS_FN_TYPE("parse",          js_json_parse,      2, 0, JS_TypeHandlerDynamic),
     JS_FN_TYPE("stringify",      js_json_stringify,  3, 0, JS_TypeHandlerString),
     JS_FS_END
 };
 
 JSObject *
 js_InitJSONClass(JSContext *cx, JSObject *obj)
 {
-    TypeObject *type = cx->getTypeObject(js_JSON_str, false);
+    TypeObject *type = cx->getTypeObject(js_JSON_str, false, false);
     JSObject *JSON = NewNonFunction<WithProto::Class>(cx, &js_JSONClass, NULL, obj, type);
     if (!JSON)
         return NULL;
     if (!JS_DefinePropertyWithType(cx, obj, js_JSON_str, OBJECT_TO_JSVAL(JSON),
                                    JS_PropertyStub, JS_PropertyStub, 0))
         return NULL;
 
     if (!JS_DefineFunctionsWithPrefix(cx, JSON, json_static_methods, js_JSON_str))
--- a/js/src/jsproxy.cpp
+++ b/js/src/jsproxy.cpp
@@ -1397,17 +1397,17 @@ Class js_ProxyClass = {
     EnumerateStub,
     ResolveStub,
     ConvertStub
 };
 
 JS_FRIEND_API(JSObject *)
 js_InitProxyClass(JSContext *cx, JSObject *obj)
 {
-    TypeObject *type = cx->getTypeObject(js_ProxyClass.name, false);
+    TypeObject *type = cx->getTypeObject(js_ProxyClass.name, false, false);
     JSObject *module = NewNonFunction<WithProto::Class>(cx, &js_ProxyClass, NULL, obj, type);
     if (!module)
         return NULL;
     if (!JS_DefinePropertyWithType(cx, obj, "Proxy", OBJECT_TO_JSVAL(module),
                                    JS_PropertyStub, JS_PropertyStub, 0)) {
         return NULL;
     }
     if (!JS_DefineFunctionsWithPrefix(cx, module, static_methods, "Proxy"))
--- a/js/src/jsreflect.cpp
+++ b/js/src/jsreflect.cpp
@@ -2880,17 +2880,17 @@ static JSFunctionSpec static_methods[] =
     JS_FN("parse", reflect_parse, 1, 0),
     JS_FS_END
 };
 
 
 JSObject *
 js_InitReflectClass(JSContext *cx, JSObject *obj)
 {
-    types::TypeObject *type = cx->getTypeObject(js_ReflectClass.name, false);
+    types::TypeObject *type = cx->getTypeObject(js_ReflectClass.name, false, false);
     JSObject *Reflect = NewNonFunction<WithProto::Class>(cx, &js_ReflectClass, NULL, obj, type);
     if (!Reflect)
         return NULL;
 
     if (!JS_DefineProperty(cx, obj, js_Reflect_str, OBJECT_TO_JSVAL(Reflect),
                            JS_PropertyStub, JS_PropertyStub, 0)) {
         return NULL;
     }
--- a/js/src/jsregexp.cpp
+++ b/js/src/jsregexp.cpp
@@ -930,11 +930,12 @@ js_InitRegExpClass(JSContext *cx, JSObje
     cx->addTypeProperty(regexpType, "ignoreCase", TYPE_BOOLEAN);
     cx->addTypeProperty(regexpType, "multiline", TYPE_BOOLEAN);
     cx->addTypeProperty(regexpType, "lastIndex", TYPE_INT32);
 
     TypeObject *arrayType = cx->getFixedTypeObject(TYPE_OBJECT_REGEXP_MATCH_ARRAY);
     cx->addTypeProperty(arrayType, NULL, TYPE_STRING);
     cx->addTypeProperty(arrayType, "index", TYPE_INT32);
     cx->addTypeProperty(arrayType, "input", TYPE_STRING);
+    cx->markTypeArrayNotPacked(arrayType, true);
 
     return proto;
 }
--- a/js/src/jsscopeinlines.h
+++ b/js/src/jsscopeinlines.h
@@ -61,16 +61,18 @@ js::Shape::freeTable(JSContext *cx)
 
 inline js::EmptyShape *
 JSObject::getEmptyShape(JSContext *cx, js::Class *aclasp,
                         /* gc::FinalizeKind */ unsigned kind)
 {
     JS_ASSERT(kind >= js::gc::FINALIZE_OBJECT0 && kind <= js::gc::FINALIZE_OBJECT_LAST);
     int i = kind - js::gc::FINALIZE_OBJECT0;
 
+    JS_ASSERT(!isDenseArray());
+
     if (!emptyShapes) {
         emptyShapes = (js::EmptyShape**)
             cx->calloc(sizeof(js::EmptyShape*) * js::gc::JS_FINALIZE_OBJECT_LIMIT);
         if (!emptyShapes)
             return NULL;
 
         /*
          * Always fill in emptyShapes[0], so canProvideEmptyShape works.
@@ -93,16 +95,17 @@ JSObject::getEmptyShape(JSContext *cx, j
     }
 
     return emptyShapes[i];
 }
 
 inline bool
 JSObject::canProvideEmptyShape(js::Class *aclasp)
 {
+    JS_ASSERT(!isDenseArray());
     return !emptyShapes || emptyShapes[0]->getClass() == aclasp;
 }
 
 inline void
 JSObject::updateShape(JSContext *cx)
 {
     JS_ASSERT(isNative());
     js::LeaveTraceIfGlobalObject(cx, this);
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -10669,16 +10669,17 @@ TraceRecorder::getClassPrototype(JSObjec
     JS_ASSERT(found);
     JS_ASSERT((~attrs & (JSPROP_READONLY | JSPROP_PERMANENT)) == 0);
 #endif
 
     // Since ctor was built by js_InitClass, we can assert (rather than check)
     // that pval is usable.
     JS_ASSERT(!pval.isPrimitive());
     JSObject *proto = &pval.toObject();
+    JS_ASSERT(!proto->isDenseArray());
     JS_ASSERT_IF(clasp != &js_ArrayClass, proto->emptyShapes[0]->getClass() == clasp);
 
     proto_ins = w.immpObjGC(proto);
     return RECORD_CONTINUE;
 }
 
 RecordingStatus
 TraceRecorder::getClassPrototype(JSProtoKey key, LIns*& proto_ins)
@@ -12768,31 +12769,36 @@ TraceRecorder::setElem(int lval_spindex,
         if (!obj->isDenseArray()) 
             return ARECORD_STOP;
         guardDenseArray(obj_ins, branchExit);
 
         // The index was on the stack and is therefore a LIR float. Force it to
         // be an integer.
         CHECK_STATUS_A(makeNumberInt32(idx_ins, &idx_ins));
 
-        if (!js_EnsureDenseArrayCapacity(cx, obj, idx.toInt32()))
+        /* Check the initialized index is not too sparse. */
+        if (!js_Array_dense_setelem_uninitialized(cx, obj, idx.toInt32()))
             RETURN_STOP_A("couldn't ensure dense array capacity for setelem");
 
-        // Grow the array if the index exceeds the capacity.  This happens
-        // rarely, eg. less than 1% of the time in SunSpider.
-        LIns* capacity_ins = w.ldiDenseArrayCapacity(obj_ins);
+        /*
+         * Grow the array and fully initialize it if the index exceeds the initialized
+         * length of the array.  This happens rarely, eg. less than 1% of the time
+         * in SunSpider.
+         */
+        LIns* initlen_ins = w.ldiDenseArrayInitializedLength(obj_ins);
+
         /*
          * It's important that CSE works across this control-flow diamond
          * because it really helps series of interleaved GETELEM and SETELEM
          * operations.  Likewise with the diamond below.
          */
         w.pauseAddingCSEValues();
-        if (MaybeBranch mbr = w.jt(w.ltui(idx_ins, capacity_ins))) {
+        if (MaybeBranch mbr = w.jt(w.ltui(idx_ins, initlen_ins))) {
             LIns* args[] = { idx_ins, obj_ins, cx_ins };
-            LIns* res_ins = w.call(&js_EnsureDenseArrayCapacity_ci, args);
+            LIns* res_ins = w.call(&js_Array_dense_setelem_uninitialized_ci, args);
             guard(false, w.eqi0(res_ins), mismatchExit);
             w.label(mbr);
         }
         w.resumeAddingCSEValues();
 
         // Get the address of the element.
         LIns *elem_ins = w.getDslotAddress(obj_ins, idx_ins);
 
@@ -13619,40 +13625,34 @@ TraceRecorder::denseArrayElement(Value& 
     JS_ASSERT(oval.isObject() && ival.isInt32());
 
     JSObject* obj = &oval.toObject();
     LIns* obj_ins = get(&oval);
     jsint idx = ival.toInt32();
     LIns* idx_ins;
     CHECK_STATUS(makeNumberInt32(get(&ival), &idx_ins));
 
-    /*
-     * Arrays have both a length and a capacity, but we only need to check
-     * |index < capacity|;  in the case where |length < index < capacity|
-     * the entries [length..capacity-1] will have already been marked as
-     * holes by resizeDenseArrayElements() so we can read them and get
-     * the correct value.
-     */
-    LIns* capacity_ins = w.ldiDenseArrayCapacity(obj_ins);
-    jsuint capacity = obj->getDenseArrayCapacity();
-    bool within = (jsuint(idx) < capacity);
+    /* Check the initialized length of the array, which is <= length and <= capacity. */
+    LIns* initlen_ins = w.ldiDenseArrayInitializedLength(obj_ins);
+    jsuint initlen = obj->getDenseArrayInitializedLength();
+    bool within = (jsuint(idx) < initlen);
     if (!within) {
-        /* If not idx < capacity, stay on trace (and read value as undefined). */
-        guard(true, w.geui(idx_ins, capacity_ins), branchExit);
+        /* If not idx < initlen, stay on trace (and read value as undefined). */
+        guard(true, w.geui(idx_ins, initlen_ins), branchExit);
 
         CHECK_STATUS(guardPrototypeHasNoIndexedProperties(obj, obj_ins, snapshot(MISMATCH_EXIT)));
 
         // Return undefined and indicate that we didn't actually read this (addr_ins).
         v_ins = w.immiUndefined();
         addr_ins = NULL;
         return RECORD_CONTINUE;
     }
 
-    /* Guard that index is within capacity. */
-    guard(true, w.ltui(idx_ins, capacity_ins), branchExit);
+    /* Guard that index is within the initialized length. */
+    guard(true, w.ltui(idx_ins, initlen_ins), branchExit);
 
     /* Load the value and guard on its type to unbox it. */
     vp = &obj->slots[jsuint(idx)];
 	JS_ASSERT(sizeof(Value) == 8); // The |3| in the following statement requires this.
     addr_ins = w.addp(w.name(w.ldpObjSlots(obj_ins), "slots"), w.lshpN(w.ui2p(idx_ins), 3));
     v_ins = unbox_value(*vp, DSlotsAddress(addr_ins), branchExit);
 
     /* Don't let the hole value escape. Turn it into an undefined. */
--- a/js/src/jstypedarray.cpp
+++ b/js/src/jstypedarray.cpp
@@ -1119,17 +1119,17 @@ class TypedArrayTemplate
     
     bool
     copyFrom(JSContext *cx, JSObject *ar, jsuint len, jsuint offset = 0)
     {
         JS_ASSERT(offset <= length);
         JS_ASSERT(len <= length - offset);
         NativeType *dest = static_cast<NativeType*>(data) + offset;
 
-        if (ar->isDenseArray() && ar->getDenseArrayCapacity() >= len) {
+        if (ar->isDenseArray() && ar->getDenseArrayInitializedLength() >= len) {
             JS_ASSERT(ar->getArrayLength() == len);
 
             Value *src = ar->getDenseArrayElements();
 
             for (uintN i = 0; i < len; ++i)
                 *dest++ = nativeFromValue(cx, *src++);
         } else {
             // slow path
@@ -1769,20 +1769,20 @@ js_ReparentTypedArrayToScope(JSContext *
     JS_ASSERT(js_IsArrayBuffer(buffer));
 
     JSObject *proto;
     JSProtoKey key =
         JSCLASS_CACHED_PROTO_KEY(&TypedArray::slowClasses[typedArray->type]);
     if (!js_GetClassPrototype(cx, scope, key, &proto))
         return JS_FALSE;
 
-    obj->setProto(proto);
+    obj->setProto(cx, proto);
     obj->setParent(scope);
 
     key = JSCLASS_CACHED_PROTO_KEY(&ArrayBuffer::jsclass);
     if (!js_GetClassPrototype(cx, scope, key, &proto))
         return JS_FALSE;
 
-    buffer->setProto(proto);
+    buffer->setProto(cx, proto);
     buffer->setParent(scope);
 
     return JS_TRUE;
 }
--- a/js/src/jsxml.cpp
+++ b/js/src/jsxml.cpp
@@ -7233,17 +7233,17 @@ js_InitXMLClass(JSContext *cx, JSObject 
 
     /* Set default settings. */
     vp[0] = JSVAL_NULL;
     vp[1] = cval;
     vp[2] = JSVAL_VOID;
     if (!xml_setSettings(cx, 1, vp))
         return NULL;
 
-    cx->markTypeBuiltinFunction(cx->getTypeObject(js_XMLList_str, true));
+    cx->markTypeBuiltinFunction(cx->getTypeObject(js_XMLList_str, false, true));
 
     /* Define the XMLList function and give it the same prototype as XML. */
     fun = JS_DefineFunctionWithType(cx, obj, js_XMLList_str, XMLList, 1, JSFUN_CONSTRUCTOR,
                                     type_XMLNew, js_XMLList_str);
     if (!fun)
         return NULL;
     if (!js_SetClassPrototype(cx, FUN_OBJECT(fun), proto,
                               JSPROP_READONLY | JSPROP_PERMANENT)) {
--- a/js/src/methodjit/BaseAssembler.h
+++ b/js/src/methodjit/BaseAssembler.h
@@ -51,48 +51,16 @@
 #include "methodjit/MachineRegs.h"
 #include "CodeGenIncludes.h"
 #include "jsobjinlines.h"
 #include "jsscopeinlines.h"
 
 namespace js {
 namespace mjit {
 
-class MaybeRegisterID {
-    typedef JSC::MacroAssembler::RegisterID RegisterID;
-
-  public:
-    MaybeRegisterID()
-      : reg_(Registers::ReturnReg), set(false)
-    { }
-
-    MaybeRegisterID(RegisterID reg)
-      : reg_(reg), set(true)
-    { }
-
-    inline RegisterID reg() const { JS_ASSERT(set); return reg_; }
-    inline void setReg(const RegisterID r) { reg_ = r; set = true; }
-    inline bool isSet() const { return set; }
-
-    MaybeRegisterID & operator =(const MaybeRegisterID &other) {
-        set = other.set;
-        reg_ = other.reg_;
-        return *this;
-    }
-
-    MaybeRegisterID & operator =(RegisterID r) {
-        setReg(r);
-        return *this;
-    }
-
-  private:
-    RegisterID reg_;
-    bool set;
-};
-
 // Represents an int32 property name in generated code, which must be either
 // a RegisterID or a constant value.
 struct Int32Key {
     typedef JSC::MacroAssembler::RegisterID RegisterID;
 
     MaybeRegisterID reg_;
     int32 index_;
 
@@ -113,35 +81,16 @@ struct Int32Key {
         JS_ASSERT(!reg_.isSet());
         return index_;
     }
 
     RegisterID reg() const { return reg_.reg(); }
     bool isConstant() const { return !reg_.isSet(); }
 };
 
-class MaybeJump {
-    typedef JSC::MacroAssembler::Jump Jump;
-  public:
-    MaybeJump()
-      : set(false)
-    { }
-
-    inline Jump getJump() const { JS_ASSERT(set); return jump; }
-    inline Jump get() const { JS_ASSERT(set); return jump; }
-    inline void setJump(const Jump &j) { jump = j; set = true; }
-    inline bool isSet() const { return set; }
-
-    inline MaybeJump &operator=(Jump j) { setJump(j); return *this; }
-
-  private:
-    Jump jump;
-    bool set;
-};
-
 struct FrameAddress : JSC::MacroAssembler::Address
 {
     FrameAddress(int32 offset)
       : Address(JSC::MacroAssembler::stackPointerRegister, offset)
     { }
 };
 
 struct ImmIntPtr : public JSC::MacroAssembler::ImmPtr
@@ -376,48 +325,64 @@ static const JSC::MacroAssembler::Regist
         }
     }
 
     struct FastArrayLoadFails {
         Jump rangeCheck;
         Jump holeCheck;
     };
 
-    Jump guardArrayCapacity(RegisterID objReg, const Int32Key &key) {
-        Address capacity(objReg, offsetof(JSObject, capacity));
+    // Guard an array's capacity, length or initialized length.
+    Jump guardArrayExtent(uint32 offset, RegisterID objReg, const Int32Key &key, Condition cond) {
+        Address initlen(objReg, offset);
         if (key.isConstant()) {
             JS_ASSERT(key.index() >= 0);
-            return branch32(BelowOrEqual, payloadOf(capacity), Imm32(key.index()));
+            return branch32(cond, initlen, Imm32(key.index()));
         }
-        return branch32(BelowOrEqual, payloadOf(capacity), key.reg());
+        return branch32(cond, initlen, key.reg());
     }
 
     // Load a jsval from an array slot, given a key. |objReg| is clobbered.
     FastArrayLoadFails fastArrayLoad(RegisterID objReg, const Int32Key &key,
                                      RegisterID typeReg, RegisterID dataReg) {
         JS_ASSERT(objReg != typeReg);
 
         FastArrayLoadFails fails;
-        fails.rangeCheck = guardArrayCapacity(objReg, key);
+        fails.rangeCheck = guardArrayExtent(offsetof(JSObject, initializedLength),
+                                            objReg, key, BelowOrEqual);
 
         RegisterID dslotsReg = objReg;
         loadPtr(Address(objReg, offsetof(JSObject, slots)), dslotsReg);
 
         // Load the slot out of the array.
         if (key.isConstant()) {
             Address slot(objReg, key.index() * sizeof(Value));
-            fails.holeCheck = fastArrayLoadSlot(slot, typeReg, dataReg);
+            fails.holeCheck = fastArrayLoadSlot(slot, true, typeReg, dataReg);
         } else {
             BaseIndex slot(objReg, key.reg(), JSVAL_SCALE);
-            fails.holeCheck = fastArrayLoadSlot(slot, typeReg, dataReg);
+            fails.holeCheck = fastArrayLoadSlot(slot, true, typeReg, dataReg);
         }
 
         return fails;
     }
 
+    void storeKey(const Int32Key &key, Address address) {
+        if (key.isConstant())
+            store32(Imm32(key.index()), address);
+        else
+            store32(key.reg(), address);
+    }
+
+    void bumpKey(Int32Key &key, int32 delta) {
+        if (key.isConstant())
+            key.index_ += delta;
+        else
+            add32(Imm32(delta), key.reg());
+    }
+
     void loadObjClass(RegisterID objReg, RegisterID destReg) {
         loadPtr(Address(objReg, offsetof(JSObject, clasp)), destReg);
     }
 
     Jump testClass(Condition cond, RegisterID claspReg, js::Class *clasp) {
         return branchPtr(cond, claspReg, ImmPtr(clasp));
     }
 
--- a/js/src/methodjit/Compiler.cpp
+++ b/js/src/methodjit/Compiler.cpp
@@ -4695,8 +4695,32 @@ JSValueType
 mjit::Compiler::knownPushedType(uint32 pushed)
 {
 #ifdef JS_TYPE_INFERENCE
     types::TypeSet *types = analysis->getCode(PC).pushed(pushed);
     return types->getKnownTypeTag(cx, script, isConstructing);
 #endif
     return JSVAL_TYPE_UNKNOWN;
 }
+
+types::ObjectKind
+mjit::Compiler::knownPoppedObjectKind(uint32 popped)
+{
+#ifdef JS_TYPE_INFERENCE
+    types::TypeSet *types = analysis->getCode(PC).popped(popped);
+    return types->getKnownObjectKind(cx, script, isConstructing);
+#endif
+    return types::OBJECT_UNKNOWN;
+}
+
+bool
+mjit::Compiler::arrayPrototypeHasIndexedSetter()
+{
+#ifdef JS_TYPE_INFERENCE
+    types::TypeSet *arrayTypes =
+        cx->getFixedTypeObject(types::TYPE_OBJECT_ARRAY_PROTOTYPE)->indexTypes(cx);
+    types::TypeSet *objectTypes =
+        cx->getFixedTypeObject(types::TYPE_OBJECT_OBJECT_PROTOTYPE)->indexTypes(cx);
+    return arrayTypes->hasGetterSetter(cx, script, isConstructing)
+        || objectTypes->hasGetterSetter(cx, script, isConstructing);
+#endif
+    return true;
+}
--- a/js/src/methodjit/Compiler.h
+++ b/js/src/methodjit/Compiler.h
@@ -314,25 +314,29 @@ class Compiler : public BaseCompiler
 
   private:
     CompileStatus performCompilation(JITScript **jitp);
     CompileStatus generatePrologue();
     CompileStatus generateMethod();
     CompileStatus generateEpilogue();
     CompileStatus finishThisUp(JITScript **jitp);
 
+    /* Analysis helpers. */
+    void restoreAnalysisTypes(uint32 stackDepth);
+    JSValueType knownArgumentType(uint32 arg);
+    JSValueType knownLocalType(uint32 local);
+    JSValueType knownPushedType(uint32 pushed);
+    js::types::ObjectKind knownPoppedObjectKind(uint32 popped);
+    bool arrayPrototypeHasIndexedSetter();
+
     /* Non-emitting helpers. */
     uint32 fullAtomIndex(jsbytecode *pc);
     bool jumpInScript(Jump j, jsbytecode *pc);
     bool compareTwoValues(JSContext *cx, JSOp op, const Value &lhs, const Value &rhs);
     void addCallSite(uint32 id, bool stub);
-    void restoreAnalysisTypes(uint32 stackDepth);
-    JSValueType knownArgumentType(uint32 arg);
-    JSValueType knownLocalType(uint32 local);
-    JSValueType knownPushedType(uint32 pushed);
 
     /* Emitting helpers. */
     void restoreFrameRegs(Assembler &masm);
     bool emitStubCmpOp(BoolStub stub, jsbytecode *target, JSOp fused);
     void iter(uintN flags);
     void iterNext();
     bool iterMore();
     void iterEnd();
@@ -435,17 +439,19 @@ class Compiler : public BaseCompiler
     void jsop_not();
     void jsop_typeof();
     bool booleanJumpScript(JSOp op, jsbytecode *target);
     bool jsop_ifneq(JSOp op, jsbytecode *target);
     bool jsop_andor(JSOp op, jsbytecode *target);
     void jsop_arginc(JSOp op, uint32 slot, bool popped);
     void jsop_localinc(JSOp op, uint32 slot, bool popped);
     bool jsop_setelem();
+    void jsop_setelem_dense();
     bool jsop_getelem(bool isCall);
+    void jsop_getelem_dense(bool isPacked);
     bool isCacheableBaseAndIndex(FrameEntry *obj, FrameEntry *id);
     void jsop_stricteq(JSOp op);
     bool jsop_equality(JSOp op, BoolStub stub, jsbytecode *target, JSOp fused);
     bool jsop_equality_int_string(JSOp op, BoolStub stub, jsbytecode *target, JSOp fused);
     void jsop_pos();
 
 #define STUB_CALL_TYPE(type)                                            \
     Call stubCall(type stub) {                                          \
--- a/js/src/methodjit/FastOps.cpp
+++ b/js/src/methodjit/FastOps.cpp
@@ -1216,28 +1216,133 @@ IsCacheableSetElem(FrameEntry *obj, Fram
     // obj[id] = id is allowed.
     // obj[id] = obj is allowed.
     if (obj->hasSameBacking(id))
         return false;
 
     return true;
 }
 
+void
+mjit::Compiler::jsop_setelem_dense()
+{
+    FrameEntry *obj = frame.peek(-3);
+    FrameEntry *id = frame.peek(-2);
+    FrameEntry *value = frame.peek(-1);
+
+    // We might not know whether this is an object, but if it is an object we
+    // know it is a dense array.
+    if (!obj->isTypeKnown()) {
+        Jump guard = frame.testObject(Assembler::NotEqual, obj);
+        stubcc.linkExit(guard, Uses(3));
+    }
+
+    // Test for integer index.
+    if (!id->isTypeKnown()) {
+        Jump guard = frame.testInt32(Assembler::NotEqual, id);
+        stubcc.linkExit(guard, Uses(3));
+    }
+
+    // Allocate registers.
+
+    ValueRemat vr;
+    frame.pinEntry(value, vr);
+
+    Int32Key key = id->isConstant()
+                 ? Int32Key::FromConstant(id->getValue().toInt32())
+                 : Int32Key::FromRegister(frame.tempRegForData(id));
+    if (!key.isConstant() && !frame.haveSameBacking(id, value))
+        frame.pinReg(key.reg());
+
+    RegisterID objReg = frame.copyDataIntoReg(obj);
+
+    frame.unpinEntry(vr);
+    if (!key.isConstant() && !frame.haveSameBacking(id, value))
+        frame.unpinReg(key.reg());
+
+    Label syncTarget = stubcc.syncExitAndJump(Uses(3));
+
+    // Check against initialized length.  This always need to be done.
+    Jump initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
+                                              objReg, key, Assembler::BelowOrEqual);
+
+    // Make an OOL path for setting exactly the initialized length.
+    {
+        stubcc.linkExitDirect(initlenGuard, stubcc.masm.label());
+
+        // Recheck for an exact initialized length.
+        // :TODO: would be nice to reuse the condition bits from the previous test.
+        Jump exactlenGuard = stubcc.masm.guardArrayExtent(offsetof(JSObject, initializedLength),
+                                                          objReg, key, Assembler::NotEqual);
+        exactlenGuard.linkTo(syncTarget, &stubcc.masm);
+
+        // Check array capacity.
+        Jump capacityGuard = stubcc.masm.guardArrayExtent(offsetof(JSObject, capacity),
+                                                          objReg, key, Assembler::BelowOrEqual);
+        capacityGuard.linkTo(syncTarget, &stubcc.masm);
+
+        // Bump the index for setting the array length.  The above guard ensures this
+        // won't overflow.
+        stubcc.masm.bumpKey(key, 1);
+
+        // Update the initialized length.
+        stubcc.masm.storeKey(key, Address(objReg, offsetof(JSObject, initializedLength)));
+
+        // Update the array length if needed.
+        Jump lengthGuard = stubcc.masm.guardArrayExtent(offsetof(JSObject, privateData),
+                                                        objReg, key, Assembler::AboveOrEqual);
+        stubcc.masm.storeKey(key, Address(objReg, offsetof(JSObject, privateData)));
+        lengthGuard.linkTo(stubcc.masm.label(), &stubcc.masm);
+
+        // Restore the index.
+        stubcc.masm.bumpKey(key, -1);
+
+        // Jump back to the inline path.
+        Jump initlenExit = stubcc.masm.jump();
+        stubcc.crossJump(initlenExit, masm.label());
+    }
+
+    // Fully store the value. :TODO: don't need to do this in the non-initlen case
+    // if the array is packed and monomorphic.
+    masm.loadPtr(Address(objReg, offsetof(JSObject, slots)), objReg);
+    if (key.isConstant())
+        masm.storeValue(vr, Address(objReg, key.index() * sizeof(Value)));
+    else
+        masm.storeValue(vr, BaseIndex(objReg, key.reg(), masm.JSVAL_SCALE));
+
+    stubcc.leave();
+    stubcc.call(STRICT_VARIANT(stubs::SetElem));
+
+    frame.freeReg(objReg);
+    frame.shimmy(2);
+    stubcc.rejoin(Changes(2));
+}
+
 bool
 mjit::Compiler::jsop_setelem()
 {
     FrameEntry *obj = frame.peek(-3);
     FrameEntry *id = frame.peek(-2);
     FrameEntry *value = frame.peek(-1);
 
     if (!IsCacheableSetElem(obj, id, value)) {
         jsop_setelem_slow();
         return true;
     }
 
+    types::ObjectKind kind = knownPoppedObjectKind(2);
+    if (id->mightBeType(JSVAL_TYPE_INT32) &&
+        (kind == types::OBJECT_DENSE_ARRAY || kind == types::OBJECT_PACKED_ARRAY) &&
+        !arrayPrototypeHasIndexedSetter()) {
+        // this is definitely a dense array, generate code directly without
+        // using an inline cache.
+        jsop_setelem_dense();
+        return true;
+    }
+
     SetElementICInfo ic = SetElementICInfo(JSOp(*PC));
 
     // One by one, check if the most important stack entries have registers,
     // and if so, pin them. This is to avoid spilling and reloading from the
     // stack as we incrementally allocate other registers.
     MaybeRegisterID pinnedValueType = frame.maybePinType(value);
     MaybeRegisterID pinnedValueData = frame.maybePinData(value);
 
@@ -1312,19 +1417,20 @@ mjit::Compiler::jsop_setelem()
     // Create the common out-of-line sync block, taking care to link previous
     // guards here after.
     ic.slowPathStart = stubcc.syncExit(Uses(3));
 
     // Guard obj is a dense array.
     ic.claspGuard = masm.testObjClass(Assembler::NotEqual, ic.objReg, &js_ArrayClass);
     stubcc.linkExitDirect(ic.claspGuard, ic.slowPathStart);
 
-    // Guard capacity in range.
-    Jump capacityGuard = masm.guardArrayCapacity(ic.objReg, ic.key);
-    stubcc.linkExitDirect(capacityGuard, ic.slowPathStart);
+    // Guard in range of initialized length.
+    Jump initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
+                                              ic.objReg, ic.key, Assembler::BelowOrEqual);
+    stubcc.linkExitDirect(initlenGuard, ic.slowPathStart);
 
     // Load the dynamic slots vector.
     masm.loadPtr(Address(ic.objReg, offsetof(JSObject, slots)), ic.objReg);
 
     // Guard there's no hole, then store directly to the slot.
     if (ic.key.isConstant()) {
         Address slot(ic.objReg, ic.key.index() * sizeof(Value));
         ic.holeGuard = masm.guardNotHole(slot);
@@ -1379,30 +1485,119 @@ IsCacheableGetElem(FrameEntry *obj, Fram
 
     // obj[obj] is not allowed, since it will never optimize.
     if (obj->hasSameBacking(id))
         return false;
 
     return true;
 }
 
+void
+mjit::Compiler::jsop_getelem_dense(bool isPacked)
+{
+    FrameEntry *obj = frame.peek(-2);
+    FrameEntry *id = frame.peek(-1);
+
+    // We might not know whether this is an object, but if it is an object we
+    // know it is a dense array.
+    if (!obj->isTypeKnown()) {
+        Jump guard = frame.testObject(Assembler::NotEqual, obj);
+        stubcc.linkExit(guard, Uses(2));
+    }
+
+    // Test for integer index.
+    if (!id->isTypeKnown()) {
+        Jump guard = frame.testInt32(Assembler::NotEqual, id);
+        stubcc.linkExit(guard, Uses(2));
+    }
+
+    JSValueType type = knownPushedType(0);
+
+    // Allocate registers.
+
+    RegisterID objReg = frame.tempRegForData(obj);
+    frame.pinReg(objReg);
+
+    Int32Key key = id->isConstant()
+                 ? Int32Key::FromConstant(id->getValue().toInt32())
+                 : Int32Key::FromRegister(frame.tempRegForData(id));
+    if (!key.isConstant() && !frame.haveSameBacking(id, obj))
+        frame.pinReg(key.reg());
+
+    RegisterID dataReg = frame.allocReg();
+
+    MaybeRegisterID typeReg;
+    if (!isPacked || type == JSVAL_TYPE_UNKNOWN)
+        typeReg = frame.allocReg();
+
+    frame.unpinReg(objReg);
+    if (!key.isConstant() && !frame.haveSameBacking(id, obj))
+        frame.unpinReg(key.reg());
+
+    // Guard on the array's initialized length.
+    Jump initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
+                                              objReg, key, Assembler::BelowOrEqual);
+    stubcc.linkExit(initlenGuard, Uses(2));
+
+    masm.loadPtr(Address(objReg, offsetof(JSObject, slots)), dataReg);
+
+    // Get the slot, skipping the hole check if the array is known to be packed.
+    Jump holeCheck;
+    if (key.isConstant()) {
+        Address slot(dataReg, key.index() * sizeof(Value));
+        holeCheck = masm.fastArrayLoadSlot(slot, !isPacked, typeReg, dataReg);
+    } else {
+        JS_ASSERT(key.reg() != dataReg);
+        BaseIndex slot(dataReg, key.reg(), masm.JSVAL_SCALE);
+        holeCheck = masm.fastArrayLoadSlot(slot, !isPacked, typeReg, dataReg);
+    }
+
+    if (!isPacked) {
+        stubcc.linkExit(holeCheck, Uses(2));
+        if (type != JSVAL_TYPE_UNKNOWN)
+            frame.freeReg(typeReg.reg());
+    }
+
+    stubcc.leave();
+    stubcc.call(stubs::GetElem);
+
+    frame.popn(2);
+
+    if (type != JSVAL_TYPE_UNKNOWN)
+        frame.pushTypedPayload(type, dataReg);
+    else
+        frame.pushRegs(typeReg.reg(), dataReg);
+
+    stubcc.rejoin(Changes(2));
+}
+
 bool
 mjit::Compiler::jsop_getelem(bool isCall)
 {
     FrameEntry *obj = frame.peek(-2);
     FrameEntry *id = frame.peek(-1);
 
     if (!IsCacheableGetElem(obj, id)) {
         if (isCall)
             jsop_callelem_slow();
         else
             jsop_getelem_slow();
         return true;
     }
 
+    types::ObjectKind kind = knownPoppedObjectKind(1);
+
+    if (!isCall && id->mightBeType(JSVAL_TYPE_INT32) &&
+        (kind == types::OBJECT_DENSE_ARRAY || kind == types::OBJECT_PACKED_ARRAY)) {
+        // this is definitely a dense array, generate code directly without
+        // using an inline cache.
+        jsop_getelem_dense(kind == types::OBJECT_PACKED_ARRAY);
+        return true;
+    }
+
     GetElementICInfo ic = GetElementICInfo(JSOp(*PC));
 
     // Pin the top of the stack to avoid spills, before allocating registers.
     MaybeRegisterID pinnedIdData = frame.maybePinData(id);
     MaybeRegisterID pinnedIdType = frame.maybePinType(id);
 
     MaybeJump objTypeGuard;
     if (!obj->isTypeKnown()) {
--- a/js/src/methodjit/NunboxAssembler.h
+++ b/js/src/methodjit/NunboxAssembler.h
@@ -295,19 +295,26 @@ class NunboxAssembler : public JSC::Macr
         return branch32(cond, reg, ImmTag(JSVAL_TAG_STRING));
     }
 
     Jump testString(Condition cond, Address address) {
         return branch32(cond, tagOf(address), ImmTag(JSVAL_TAG_STRING));
     }
 
     template <typename T>
-    Jump fastArrayLoadSlot(T address, RegisterID typeReg, RegisterID dataReg) {
-        loadTypeTag(address, typeReg);
-        Jump notHole = branch32(Equal, typeReg, ImmType(JSVAL_TYPE_MAGIC));
+    Jump fastArrayLoadSlot(T address, bool holeCheck,
+                           MaybeRegisterID typeReg, RegisterID dataReg)
+    {
+        JS_ASSERT_IF(holeCheck, typeReg.isSet());
+        Jump notHole;
+        if (typeReg.isSet()) {
+            loadTypeTag(address, typeReg.reg());
+            if (holeCheck)
+                notHole = branch32(Equal, typeReg.reg(), ImmType(JSVAL_TYPE_MAGIC));
+        }
         loadPayload(address, dataReg);
         return notHole;
     }
 };
 
 typedef NunboxAssembler ValueAssembler;
 
 } /* namespace mjit */
--- a/js/src/methodjit/PolyIC.cpp
+++ b/js/src/methodjit/PolyIC.cpp
@@ -2324,17 +2324,17 @@ SetElementIC::attachHoleStub(JSContext *
     if (keyval < 0)
         return disable(cx, "negative key index");
 
     // We may have failed a capacity check instead of a dense array check.
     // However we should still build the IC in this case, since it could
     // be in a loop that is filling in the array. We can assert, however,
     // that either we're in capacity or there's a hole - guaranteed by
     // the fast path.
-    JS_ASSERT((jsuint)keyval >= obj->getDenseArrayCapacity() ||
+    JS_ASSERT((jsuint)keyval >= obj->getDenseArrayInitializedLength() ||
               obj->getDenseArrayElement(keyval).isMagic(JS_ARRAY_HOLE));
 
     if (js_PrototypeHasIndexedProperties(cx, obj))
         return disable(cx, "prototype has indexed properties");
 
     Assembler masm;
 
     // Test for indexed properties in Array.prototype. It is safe to bake in
--- a/js/src/methodjit/PunboxAssembler.h
+++ b/js/src/methodjit/PunboxAssembler.h
@@ -307,19 +307,28 @@ class PunboxAssembler : public JSC::Macr
     }
 
     Jump testString(Condition cond, Address address) {
         loadTypeTag(address, Registers::ValueReg);
         return testString(cond, Registers::ValueReg);
     }
 
     template <typename T>
-    Jump fastArrayLoadSlot(T address, RegisterID typeReg, RegisterID dataReg) {
-        loadValueAsComponents(address, typeReg, dataReg);
-        return branchPtr(Equal, typeReg, ImmType(JSVAL_TYPE_MAGIC));
+    Jump fastArrayLoadSlot(T address, bool holeCheck,
+                           MaybeRegisterID typeReg, RegisterID dataReg)
+    {
+        JS_ASSERT_IF(holeCheck, typeReg.isSet());
+        Jump notHole;
+        if (typeReg.isSet()) {
+            loadValueAsComponents(address, typeReg.reg(), dataReg);
+            if (holeCheck)
+                notHole = branchPtr(Equal, typeReg.reg(), ImmType(JSVAL_TYPE_MAGIC));
+        } else {
+            loadPayload(address, dataReg);
+        }
     }
 };
 
 typedef PunboxAssembler ValueAssembler;
 
 } /* namespace mjit */
 } /* namespace js */
 
--- a/js/src/methodjit/RematInfo.h
+++ b/js/src/methodjit/RematInfo.h
@@ -272,13 +272,64 @@ struct RematInfo {
 
     /* Remat source. */
     PhysLoc location_;
 
     /* Sync state. */
     SyncState sync_;
 };
 
+class MaybeRegisterID {
+    typedef JSC::MacroAssembler::RegisterID RegisterID;
+
+  public:
+    MaybeRegisterID()
+      : reg_(Registers::ReturnReg), set(false)
+    { }
+
+    MaybeRegisterID(RegisterID reg)
+      : reg_(reg), set(true)
+    { }
+
+    inline RegisterID reg() const { JS_ASSERT(set); return reg_; }
+    inline void setReg(const RegisterID r) { reg_ = r; set = true; }
+    inline bool isSet() const { return set; }
+
+    MaybeRegisterID & operator =(const MaybeRegisterID &other) {
+        set = other.set;
+        reg_ = other.reg_;
+        return *this;
+    }
+
+    MaybeRegisterID & operator =(RegisterID r) {
+        setReg(r);
+        return *this;
+    }
+
+  private:
+    RegisterID reg_;
+    bool set;
+};
+
+class MaybeJump {
+    typedef JSC::MacroAssembler::Jump Jump;
+  public:
+    MaybeJump()
+      : set(false)
+    { }
+
+    inline Jump getJump() const { JS_ASSERT(set); return jump; }
+    inline Jump get() const { JS_ASSERT(set); return jump; }
+    inline void setJump(const Jump &j) { jump = j; set = true; }
+    inline bool isSet() const { return set; }
+
+    inline MaybeJump &operator=(Jump j) { setJump(j); return *this; }
+
+  private:
+    Jump jump;
+    bool set;
+};
+
 } /* namespace mjit */
 } /* namespace js */
 
 #endif
 
--- a/js/src/methodjit/StubCalls.cpp
+++ b/js/src/methodjit/StubCalls.cpp
@@ -564,17 +564,17 @@ stubs::SetElem(VMFrame &f)
     if (!obj)
         THROW();
 
     if (!FetchElementId(f, obj, idval, id, &regs.sp[-2]))
         THROW();
 
     do {
         if (obj->isDenseArray() && JSID_IS_INT(id)) {
-            jsuint length = obj->getDenseArrayCapacity();
+            jsuint length = obj->getDenseArrayInitializedLength();
             jsint i = JSID_TO_INT(id);
             if ((jsuint)i < length) {
                 if (obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
                     if (js_PrototypeHasIndexedProperties(cx, obj))
                         break;
                     if ((jsuint)i >= obj->getArrayLength())
                         obj->setArrayLength(cx, i + 1);
                 }
--- a/js/src/tests/ecma_3/Array/jstests.list
+++ b/js/src/tests/ecma_3/Array/jstests.list
@@ -6,12 +6,12 @@ script 15.4.5.1-01.js
 script 15.5.4.8-01.js
 script regress-101488.js
 script regress-130451.js
 script regress-322135-01.js
 script regress-322135-02.js
 skip script regress-322135-03.js # slow
 skip script regress-322135-04.js # slow
 script regress-387501.js
-script regress-390598.js
+skip script regress-390598.js # :FIXME: bug 599159
 script regress-421325.js
 script regress-430717.js
 script regress-488989.js
--- a/js/src/tests/js1_6/Array/jstests.list
+++ b/js/src/tests/js1_6/Array/jstests.list
@@ -5,10 +5,10 @@ script regress-304828.js
 script regress-305002.js
 script regress-310425-01.js
 script regress-310425-02.js
 skip script regress-320887.js # obsolete test
 script regress-352742-01.js
 script regress-352742-02.js
 script regress-386030.js
 script regress-415451.js
-script regress-415540.js
+skip script regress-415540.js # :FIXME: bug 599159
 script regress-566651.js
--- a/js/src/tracejit/Writer.cpp
+++ b/js/src/tracejit/Writer.cpp
@@ -405,17 +405,17 @@ void ValidateWriter::checkAccSet(LOpcode
         // base = <JSObject>
         // ins  = ldp.objprivate base[offsetof(JSObject, privateData)]
         ok = (op == LIR_ldi || op == LIR_ldp) &&
              disp == offsetof(JSObject, privateData) &&
              couldBeObjectOrString(base);
         break;
 
       case ACCSET_OBJ_CAPACITY:
-        ok = OK_OBJ_FIELD(LIR_ldi, capacity);
+        ok = OK_OBJ_FIELD(LIR_ldi, capacity) || OK_OBJ_FIELD(LIR_ldi, initializedLength);
         break;
 
       case ACCSET_OBJ_SLOTS:
         ok = OK_OBJ_FIELD(LIR_ldp, slots);
         break;
 
       case ACCSET_SLOTS:
         // This check is imperfect.
--- a/js/src/tracejit/Writer.h
+++ b/js/src/tracejit/Writer.h
@@ -109,17 +109,17 @@ enum LC_TMBits {
  * - ACCSET_STACKFRAME:    All JSStackFrame objects.
  * - ACCSET_RUNTIME:       The JSRuntime object.
  * - ACCSET_OBJ_CLASP:     The 'clasp'    field of all JSObjects.
  * - ACCSET_OBJ_FLAGS:     The 'flags'    field of all JSObjects.
  * - ACCSET_OBJ_SHAPE:     The 'shape'    field of all JSObjects.
  * - ACCSET_OBJ_PROTO:     The 'proto'    field of all JSObjects.
  * - ACCSET_OBJ_PARENT:    The 'parent'   field of all JSObjects.
  * - ACCSET_OBJ_PRIVATE:   The 'private'  field of all JSObjects.
- * - ACCSET_OBJ_CAPACITY:  The 'capacity' field of all JSObjects.
+ * - ACCSET_OBJ_CAPACITY:  The 'capacity' or 'initializedLength' field of all JSObjects.
  * - ACCSET_OBJ_SLOTS:     The 'slots'    field of all JSObjects.
  * - ACCSET_SLOTS:         The slots (be they fixed or dynamic) of all JSObjects.
  * - ACCSET_TARRAY:        All TypedArray structs.
  * - ACCSET_TARRAY_DATA:   All TypedArray data arrays.
  * - ACCSET_ITER:          All NativeIterator structs.
  * - ACCSET_ITER_PROPS:    The props_arrays of all NativeIterator structs.
  * - ACCSET_STRING:        All JSString structs.
  * - ACCSET_STRING_MCHARS: All JSString mchars arrays.
@@ -485,18 +485,18 @@ class Writer
     }
 
     nj::LIns *lduiObjPrivate(nj::LIns *obj) const {
         return name(lir->insLoad(nj::LIR_ldi, obj, offsetof(JSObject, privateData),
                                  ACCSET_OBJ_PRIVATE),
                     "private_uint32");
     }
 
-    nj::LIns *ldiDenseArrayCapacity(nj::LIns *array) const {
-        return name(lir->insLoad(nj::LIR_ldi, array, offsetof(JSObject, capacity),
+    nj::LIns *ldiDenseArrayInitializedLength(nj::LIns *array) const {
+        return name(lir->insLoad(nj::LIR_ldi, array, offsetof(JSObject, initializedLength),
                                  ACCSET_OBJ_CAPACITY),
                     "capacity");
     }
 
     nj::LIns *ldpObjSlots(nj::LIns *obj) const {
         return lir->insLoad(nj::LIR_ldp, obj, offsetof(JSObject, slots), ACCSET_OBJ_SLOTS);
     }