8 files changed, 445 insertions, 5 deletions

diff --git a/js/src/vm/Interpreter-inl.h b/js/src/vm/Interpreter-inl.h
index adefa6e93..0e81dfef4 100644
--- a/js/src/vm/Interpreter-inl.h
+++ b/js/src/vm/Interpreter-inl.h
@@ -22,6 +22,7 @@
 #include "vm/EnvironmentObject-inl.h"
 #include "vm/Stack-inl.h"
 #include "vm/String-inl.h"
+#include "vm/UnboxedObject-inl.h"
 
 namespace js {
 
@@ -336,10 +337,14 @@ InitGlobalLexicalOperation(JSContext* cx, LexicalEnvironmentObject* lexicalEnvAr
 inline bool
 InitPropertyOperation(JSContext* cx, JSOp op, HandleObject obj, HandleId id, HandleValue rhs)
 {
-  MOZ_ASSERT(obj->is<PlainObject>() || obj->is<JSFunction>());
-  unsigned propAttrs = GetInitDataPropAttrs(op);
-  return NativeDefineProperty(cx, obj.as<NativeObject>(), id, rhs,
-                              nullptr, nullptr, propAttrs);
+    if (obj->is<PlainObject>() || obj->is<JSFunction>()) {
+        unsigned propAttrs = GetInitDataPropAttrs(op);
+        return NativeDefineProperty(cx, obj.as<NativeObject>(), id, rhs, nullptr, nullptr,
+                                    propAttrs);
+    }
+
+    MOZ_ASSERT(obj->as<UnboxedPlainObject>().layout().lookup(id));
+    return PutProperty(cx, obj, id, rhs, false);
 }
 
 inline bool
diff --git a/js/src/vm/Interpreter.cpp b/js/src/vm/Interpreter.cpp
index 834084c4d..274392335 100644
--- a/js/src/vm/Interpreter.cpp
+++ b/js/src/vm/Interpreter.cpp
@@ -4157,7 +4157,7 @@ CASE(JSOP_INITHOMEOBJECT)
     /* Load the home object */
     ReservedRooted<JSObject*> obj(&rootObject0);
     obj = &REGS.sp[int(-2 - skipOver)].toObject();
-    MOZ_ASSERT(obj->is<PlainObject>() || obj->is<JSFunction>());
+    MOZ_ASSERT(obj->is<PlainObject>() || obj->is<UnboxedPlainObject>() || obj->is<JSFunction>());
 
     func->setExtendedSlot(FunctionExtended::METHOD_HOMEOBJECT_SLOT, ObjectValue(*obj));
 }
@@ -4973,10 +4973,15 @@ js::NewObjectOperation(JSContext* cx, HandleScript script, jsbytecode* pc,
             return nullptr;
         if (group->maybePreliminaryObjects()) {
             group->maybePreliminaryObjects()->maybeAnalyze(cx, group);
+            if (group->maybeUnboxedLayout())
+                group->maybeUnboxedLayout()->setAllocationSite(script, pc);
         }
 
         if (group->shouldPreTenure() || group->maybePreliminaryObjects())
             newKind = TenuredObject;
+
+        if (group->maybeUnboxedLayout())
+            return UnboxedPlainObject::create(cx, group, newKind);
     }
 
     RootedObject obj(cx);
diff --git a/js/src/vm/ReceiverGuard.cpp b/js/src/vm/ReceiverGuard.cpp
index 11c2d0727..97df908c3 100644
--- a/js/src/vm/ReceiverGuard.cpp
+++ b/js/src/vm/ReceiverGuard.cpp
@@ -7,6 +7,7 @@
 #include "vm/ReceiverGuard.h"
 
 #include "builtin/TypedObject.h"
+#include "vm/UnboxedObject.h"
 #include "jsobjinlines.h"
 
 using namespace js;
diff --git a/js/src/vm/ReceiverGuard.h b/js/src/vm/ReceiverGuard.h
index c14f0d83b..459cc0012 100644
--- a/js/src/vm/ReceiverGuard.h
+++ b/js/src/vm/ReceiverGuard.h
@@ -28,6 +28,11 @@ namespace js {
 // TypedObject: The structure of a typed object is determined by its group.
 //   All typed objects with the same group have the same class, prototype, and
 //   own properties.
+//
+// UnboxedPlainObject: The structure of an unboxed plain object is determined
+//   by its group and its expando object's shape, if there is one. All unboxed
+//   plain objects with the same group and expando shape have the same
+//   properties except those stored in the expando's dense elements.
 
 class HeapReceiverGuard;
 class RootedReceiverGuard;
diff --git a/js/src/vm/TypeInference.cpp b/js/src/vm/TypeInference.cpp
index ee5bbef5d..438188a36 100644
--- a/js/src/vm/TypeInference.cpp
+++ b/js/src/vm/TypeInference.cpp
@@ -1999,6 +1999,17 @@ TypeSet::ObjectKey::watchStateChangeForTypedArrayData(CompilerConstraintList* co
                                     ConstraintDataFreezeObjectForTypedArrayData(tarray)));
 }
 
+void
+TypeSet::ObjectKey::watchStateChangeForUnboxedConvertedToNative(CompilerConstraintList* constraints)
+{
+    HeapTypeSetKey objectProperty = property(JSID_EMPTY);
+    LifoAlloc* alloc = constraints->alloc();
+
+    typedef CompilerConstraintInstance<ConstraintDataFreezeObjectForUnboxedConvertedToNative> T;
+    constraints->add(alloc->new_<T>(alloc, objectProperty,
+                                    ConstraintDataFreezeObjectForUnboxedConvertedToNative()));
+}
+
 static void
 ObjectStateChange(ExclusiveContext* cxArg, ObjectGroup* group, bool markingUnknown)
 {
@@ -3573,6 +3584,7 @@ PreliminaryObjectArrayWithTemplate::maybeAnalyze(ExclusiveContext* cx, ObjectGro
         }
     }
 
+    TryConvertToUnboxedLayout(cx, enter, shape(), group, preliminaryObjects);
     if (group->maybeUnboxedLayout())
         return;
 
@@ -3901,6 +3913,10 @@ TypeNewScript::maybeAnalyze(JSContext* cx, ObjectGroup* group, bool* regenerate,
         PodCopy(initializerList, initializerVector.begin(), initializerVector.length());
     }
 
+    // Try to use an unboxed representation for the group.
+    if (!TryConvertToUnboxedLayout(cx, enter, templateObject()->lastProperty(), group, preliminaryObjects))
+        return false;
+
     js_delete(preliminaryObjects);
     preliminaryObjects = nullptr;
 
diff --git a/js/src/vm/TypeInference.h b/js/src/vm/TypeInference.h
index 537baa21f..9ec1bf927 100644
--- a/js/src/vm/TypeInference.h
+++ b/js/src/vm/TypeInference.h
@@ -262,6 +262,7 @@ class TypeSet
         bool hasStableClassAndProto(CompilerConstraintList* constraints);
         void watchStateChangeForInlinedCall(CompilerConstraintList* constraints);
         void watchStateChangeForTypedArrayData(CompilerConstraintList* constraints);
+        void watchStateChangeForUnboxedConvertedToNative(CompilerConstraintList* constraints);
         HeapTypeSetKey property(jsid id);
         void ensureTrackedProperty(JSContext* cx, jsid id);
 
diff --git a/js/src/vm/UnboxedObject.cpp b/js/src/vm/UnboxedObject.cpp
index 059293a2d..d8c9c774a 100644
--- a/js/src/vm/UnboxedObject.cpp
+++ b/js/src/vm/UnboxedObject.cpp
@@ -1635,12 +1635,227 @@ const Class UnboxedArrayObject::class_ = {
 // API
 /////////////////////////////////////////////////////////////////////
 
+static bool
+UnboxedTypeIncludes(JSValueType supertype, JSValueType subtype)
+{
+    if (supertype == JSVAL_TYPE_DOUBLE && subtype == JSVAL_TYPE_INT32)
+        return true;
+    if (supertype == JSVAL_TYPE_OBJECT && subtype == JSVAL_TYPE_NULL)
+        return true;
+    return false;
+}
+
+static bool
+CombineUnboxedTypes(const Value& value, JSValueType* existing)
+{
+    JSValueType type = value.isDouble() ? JSVAL_TYPE_DOUBLE : value.extractNonDoubleType();
+
+    if (*existing == JSVAL_TYPE_MAGIC || *existing == type || UnboxedTypeIncludes(type, *existing)) {
+        *existing = type;
+        return true;
+    }
+    if (UnboxedTypeIncludes(*existing, type))
+        return true;
+    return false;
+}
+
+// Return whether the property names and types in layout are a subset of the
+// specified vector.
+static bool
+PropertiesAreSuperset(const UnboxedLayout::PropertyVector& properties, UnboxedLayout* layout)
+{
+    for (size_t i = 0; i < layout->properties().length(); i++) {
+        const UnboxedLayout::Property& layoutProperty = layout->properties()[i];
+        bool found = false;
+        for (size_t j = 0; j < properties.length(); j++) {
+            if (layoutProperty.name == properties[j].name) {
+                found = (layoutProperty.type == properties[j].type);
+                break;
+            }
+        }
+        if (!found)
+            return false;
+    }
+    return true;
+}
+
+static bool
+CombinePlainObjectProperties(PlainObject* obj, Shape* templateShape,
+                             UnboxedLayout::PropertyVector& properties)
+{
+    // All preliminary objects must have been created with enough space to
+    // fill in their unboxed data inline. This is ensured either by using
+    // the largest allocation kind (which limits the maximum size of an
+    // unboxed object), or by using an allocation kind that covers all
+    // properties in the template, as the space used by unboxed properties
+    // is less than or equal to that used by boxed properties.
+    MOZ_ASSERT(gc::GetGCKindSlots(obj->asTenured().getAllocKind()) >=
+               Min(NativeObject::MAX_FIXED_SLOTS, templateShape->slotSpan()));
+
+    if (obj->lastProperty() != templateShape || obj->hasDynamicElements()) {
+        // Only use an unboxed representation if all created objects match
+        // the template shape exactly.
+        return false;
+    }
+
+    for (size_t i = 0; i < templateShape->slotSpan(); i++) {
+        Value val = obj->getSlot(i);
+
+        JSValueType& existing = properties[i].type;
+        if (!CombineUnboxedTypes(val, &existing))
+            return false;
+    }
+
+    return true;
+}
+
+static bool
+CombineArrayObjectElements(ExclusiveContext* cx, ArrayObject* obj, JSValueType* elementType)
+{
+    if (obj->inDictionaryMode() ||
+        obj->lastProperty()->propid() != AtomToId(cx->names().length) ||
+        !obj->lastProperty()->previous()->isEmptyShape())
+    {
+        // Only use an unboxed representation if the object has no properties.
+        return false;
+    }
+
+    for (size_t i = 0; i < obj->getDenseInitializedLength(); i++) {
+        Value val = obj->getDenseElement(i);
+
+        // For now, unboxed arrays cannot have holes.
+        if (val.isMagic(JS_ELEMENTS_HOLE))
+            return false;
+
+        if (!CombineUnboxedTypes(val, elementType))
+            return false;
+    }
+
+    return true;
+}
+
+static size_t
+ComputePlainObjectLayout(ExclusiveContext* cx, Shape* templateShape,
+                         UnboxedLayout::PropertyVector& properties)
+{
+    // Fill in the names for all the object's properties.
+    for (Shape::Range<NoGC> r(templateShape); !r.empty(); r.popFront()) {
+        size_t slot = r.front().slot();
+        MOZ_ASSERT(!properties[slot].name);
+        properties[slot].name = JSID_TO_ATOM(r.front().propid())->asPropertyName();
+    }
+
+    // Fill in all the unboxed object's property offsets.
+    uint32_t offset = 0;
+
+    // Search for an existing unboxed layout which is a subset of this one.
+    // If there are multiple such layouts, use the largest one. If we're able
+    // to find such a layout, use the same property offsets for the shared
+    // properties, which will allow us to generate better code if the objects
+    // have a subtype/supertype relation and are accessed at common sites.
+    UnboxedLayout* bestExisting = nullptr;
+    for (UnboxedLayout* existing : cx->compartment()->unboxedLayouts) {
+        if (PropertiesAreSuperset(properties, existing)) {
+            if (!bestExisting ||
+                existing->properties().length() > bestExisting->properties().length())
+            {
+                bestExisting = existing;
+            }
+        }
+    }
+    if (bestExisting) {
+        for (size_t i = 0; i < bestExisting->properties().length(); i++) {
+            const UnboxedLayout::Property& existingProperty = bestExisting->properties()[i];
+            for (size_t j = 0; j < templateShape->slotSpan(); j++) {
+                if (existingProperty.name == properties[j].name) {
+                    MOZ_ASSERT(existingProperty.type == properties[j].type);
+                    properties[j].offset = existingProperty.offset;
+                }
+            }
+        }
+        offset = bestExisting->size();
+    }
+
+    // Order remaining properties from the largest down for the best space
+    // utilization.
+    static const size_t typeSizes[] = { 8, 4, 1 };
+
+    for (size_t i = 0; i < ArrayLength(typeSizes); i++) {
+        size_t size = typeSizes[i];
+        for (size_t j = 0; j < templateShape->slotSpan(); j++) {
+            if (properties[j].offset != UINT32_MAX)
+                continue;
+            JSValueType type = properties[j].type;
+            if (UnboxedTypeSize(type) == size) {
+                offset = JS_ROUNDUP(offset, size);
+                properties[j].offset = offset;
+                offset += size;
+            }
+        }
+    }
+
+    // The final offset is the amount of data needed by the object.
+    return offset;
+}
+
+static bool
+SetLayoutTraceList(ExclusiveContext* cx, UnboxedLayout* layout)
+{
+    // Figure out the offsets of any objects or string properties.
+    Vector<int32_t, 8, SystemAllocPolicy> objectOffsets, stringOffsets;
+    for (size_t i = 0; i < layout->properties().length(); i++) {
+        const UnboxedLayout::Property& property = layout->properties()[i];
+        MOZ_ASSERT(property.offset != UINT32_MAX);
+        if (property.type == JSVAL_TYPE_OBJECT) {
+            if (!objectOffsets.append(property.offset))
+                return false;
+        } else if (property.type == JSVAL_TYPE_STRING) {
+            if (!stringOffsets.append(property.offset))
+                return false;
+        }
+    }
+
+    // Construct the layout's trace list.
+    if (!objectOffsets.empty() || !stringOffsets.empty()) {
+        Vector<int32_t, 8, SystemAllocPolicy> entries;
+        if (!entries.appendAll(stringOffsets) ||
+            !entries.append(-1) ||
+            !entries.appendAll(objectOffsets) ||
+            !entries.append(-1) ||
+            !entries.append(-1))
+        {
+            return false;
+        }
+        int32_t* traceList = cx->zone()->pod_malloc<int32_t>(entries.length());
+        if (!traceList)
+            return false;
+        PodCopy(traceList, entries.begin(), entries.length());
+        layout->setTraceList(traceList);
+    }
+
+    return true;
+}
+
 static inline Value
 NextValue(Handle<GCVector<Value>> values, size_t* valueCursor)
 {
     return values[(*valueCursor)++];
 }
 
+static bool
+GetValuesFromPreliminaryArrayObject(ArrayObject* obj, MutableHandle<GCVector<Value>> values)
+{
+    if (!values.append(Int32Value(obj->length())))
+        return false;
+    if (!values.append(Int32Value(obj->getDenseInitializedLength())))
+        return false;
+    for (size_t i = 0; i < obj->getDenseInitializedLength(); i++) {
+        if (!values.append(obj->getDenseElement(i)))
+            return false;
+    }
+    return true;
+}
+
 void
 UnboxedArrayObject::fillAfterConvert(ExclusiveContext* cx,
                                      Handle<GCVector<Value>> values, size_t* valueCursor)
@@ -1666,6 +1881,16 @@ UnboxedArrayObject::fillAfterConvert(ExclusiveContext* cx,
         JS_ALWAYS_TRUE(initElement(cx, i, NextValue(values, valueCursor)));
 }
 
+static bool
+GetValuesFromPreliminaryPlainObject(PlainObject* obj, MutableHandle<GCVector<Value>> values)
+{
+    for (size_t i = 0; i < obj->slotSpan(); i++) {
+        if (!values.append(obj->getSlot(i)))
+            return false;
+    }
+    return true;
+}
+
 void
 UnboxedPlainObject::fillAfterConvert(ExclusiveContext* cx,
                                      Handle<GCVector<Value>> values, size_t* valueCursor)
@@ -1676,6 +1901,181 @@ UnboxedPlainObject::fillAfterConvert(ExclusiveContext* cx,
         JS_ALWAYS_TRUE(setValue(cx, layout().properties()[i], NextValue(values, valueCursor)));
 }
 
+bool
+js::TryConvertToUnboxedLayout(ExclusiveContext* cx, AutoEnterAnalysis& enter, Shape* templateShape,
+                              ObjectGroup* group, PreliminaryObjectArray* objects)
+{
+    bool isArray = !templateShape;
+
+    // Unboxed arrays are nightly only for now. The getenv() call will be
+    // removed when they are on by default. See bug 1153266.
+    if (isArray) {
+#ifdef NIGHTLY_BUILD
+        if (!getenv("JS_OPTION_USE_UNBOXED_ARRAYS")) {
+            if (!cx->options().unboxedArrays())
+                return true;
+        }
+#else
+        return true;
+#endif
+    } else {
+        if (jit::JitOptions.disableUnboxedObjects)
+            return true;
+    }
+
+    MOZ_ASSERT_IF(templateShape, !templateShape->getObjectFlags());
+
+    if (group->runtimeFromAnyThread()->isSelfHostingGlobal(cx->global()))
+        return true;
+
+    if (!isArray && templateShape->slotSpan() == 0)
+        return true;
+
+    UnboxedLayout::PropertyVector properties;
+    if (!isArray) {
+        if (!properties.appendN(UnboxedLayout::Property(), templateShape->slotSpan()))
+            return false;
+    }
+    JSValueType elementType = JSVAL_TYPE_MAGIC;
+
+    size_t objectCount = 0;
+    for (size_t i = 0; i < PreliminaryObjectArray::COUNT; i++) {
+        JSObject* obj = objects->get(i);
+        if (!obj)
+            continue;
+
+        if (obj->isSingleton() || obj->group() != group)
+            return true;
+
+        objectCount++;
+
+        if (isArray) {
+            if (!CombineArrayObjectElements(cx, &obj->as<ArrayObject>(), &elementType))
+                return true;
+        } else {
+            if (!CombinePlainObjectProperties(&obj->as<PlainObject>(), templateShape, properties))
+                return true;
+        }
+    }
+
+    size_t layoutSize = 0;
+    if (isArray) {
+        // Don't use an unboxed representation if we couldn't determine an
+        // element type for the objects.
+        if (UnboxedTypeSize(elementType) == 0)
+            return true;
+    } else {
+        if (objectCount <= 1) {
+            // If only one of the objects has been created, it is more likely
+            // to have new properties added later. This heuristic is not used
+            // for array objects, where we might want an unboxed representation
+            // even if there is only one large array.
+            return true;
+        }
+
+        for (size_t i = 0; i < templateShape->slotSpan(); i++) {
+            // We can't use an unboxed representation if e.g. all the objects have
+            // a null value for one of the properties, as we can't decide what type
+            // it is supposed to have.
+            if (UnboxedTypeSize(properties[i].type) == 0)
+                return true;
+        }
+
+        // Make sure that all properties on the template shape are property
+        // names, and not indexes.
+        for (Shape::Range<NoGC> r(templateShape); !r.empty(); r.popFront()) {
+            jsid id = r.front().propid();
+            uint32_t dummy;
+            if (!JSID_IS_ATOM(id) || JSID_TO_ATOM(id)->isIndex(&dummy))
+                return true;
+        }
+
+        layoutSize = ComputePlainObjectLayout(cx, templateShape, properties);
+
+        // The entire object must be allocatable inline.
+        if (UnboxedPlainObject::offsetOfData() + layoutSize > JSObject::MAX_BYTE_SIZE)
+            return true;
+    }
+
+    UniquePtr<UnboxedLayout>& layout = enter.unboxedLayoutToCleanUp;
+    MOZ_ASSERT(!layout);
+    layout = group->zone()->make_unique<UnboxedLayout>();
+    if (!layout)
+        return false;
+
+    if (isArray) {
+        layout->initArray(elementType);
+    } else {
+        if (!layout->initProperties(properties, layoutSize))
+            return false;
+
+        // The unboxedLayouts list only tracks layouts for plain objects.
+        cx->compartment()->unboxedLayouts.insertFront(layout.get());
+
+        if (!SetLayoutTraceList(cx, layout.get()))
+            return false;
+    }
+
+    // We've determined that all the preliminary objects can use the new layout
+    // just constructed, so convert the existing group to use the unboxed class,
+    // and update the preliminary objects to use the new layout. Do the
+    // fallible stuff first before modifying any objects.
+
+    // Get an empty shape which we can use for the preliminary objects.
+    const Class* clasp = isArray ? &UnboxedArrayObject::class_ : &UnboxedPlainObject::class_;
+    Shape* newShape = EmptyShape::getInitialShape(cx, clasp, group->proto(), 0);
+    if (!newShape) {
+        cx->recoverFromOutOfMemory();
+        return false;
+    }
+
+    // Accumulate a list of all the values in each preliminary object, and
+    // update their shapes.
+    Rooted<GCVector<Value>> values(cx, GCVector<Value>(cx));
+    for (size_t i = 0; i < PreliminaryObjectArray::COUNT; i++) {
+        JSObject* obj = objects->get(i);
+        if (!obj)
+            continue;
+
+        bool ok;
+        if (isArray)
+            ok = GetValuesFromPreliminaryArrayObject(&obj->as<ArrayObject>(), &values);
+        else
+            ok = GetValuesFromPreliminaryPlainObject(&obj->as<PlainObject>(), &values);
+
+        if (!ok) {
+            cx->recoverFromOutOfMemory();
+            return false;
+        }
+    }
+
+    if (TypeNewScript* newScript = group->newScript())
+        layout->setNewScript(newScript);
+
+    for (size_t i = 0; i < PreliminaryObjectArray::COUNT; i++) {
+        if (JSObject* obj = objects->get(i))
+            obj->as<NativeObject>().setLastPropertyMakeNonNative(newShape);
+    }
+
+    group->setClasp(clasp);
+    group->setUnboxedLayout(layout.release());
+
+    size_t valueCursor = 0;
+    for (size_t i = 0; i < PreliminaryObjectArray::COUNT; i++) {
+        JSObject* obj = objects->get(i);
+        if (!obj)
+            continue;
+
+        if (isArray)
+            obj->as<UnboxedArrayObject>().fillAfterConvert(cx, values, &valueCursor);
+        else
+            obj->as<UnboxedPlainObject>().fillAfterConvert(cx, values, &valueCursor);
+    }
+
+    MOZ_ASSERT(valueCursor == values.length());
+    return true;
+}
+
 DefineBoxedOrUnboxedFunctor6(SetOrExtendBoxedOrUnboxedDenseElements,
                              ExclusiveContext*, JSObject*, uint32_t, const Value*, uint32_t,
                              ShouldUpdateTypes);
diff --git a/js/src/vm/UnboxedObject.h b/js/src/vm/UnboxedObject.h
index 779dd14c7..ecff8be5b 100644
--- a/js/src/vm/UnboxedObject.h
+++ b/js/src/vm/UnboxedObject.h
@@ -317,6 +317,13 @@ class UnboxedPlainObject : public JSObject
     }
 };
 
+// Try to construct an UnboxedLayout for each of the preliminary objects,
+// provided they all match the template shape. If successful, converts the
+// preliminary objects and their group to the new unboxed representation.
+bool
+TryConvertToUnboxedLayout(ExclusiveContext* cx, AutoEnterAnalysis& enter, Shape* templateShape,
+                          ObjectGroup* group, PreliminaryObjectArray* objects);
+
 inline gc::AllocKind
 UnboxedLayout::getAllocKind() const
 {