Bug 1314569 - Purge ShapeTables on shrinking GCs. r=jonco
authorJan de Mooij <jdemooij@mozilla.com>
Thu, 03 Nov 2016 19:15:15 +0100
changeset 320902 b3cf01afceb6fd3da03161f077f52bdc4e351d2d
parent 320901 2cf0ccb1a85cabf6d784ec3433f584da48864eff
child 320903 18ca736c0d1daef0c1edb4e19b622d3df131f24a
push id30905
push userphilringnalda@gmail.com
push dateFri, 04 Nov 2016 02:33:06 +0000
treeherdermozilla-central@4f09d9469e73 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjonco
bugs1314569
milestone52.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1314569 - Purge ShapeTables on shrinking GCs. r=jonco
js/src/gc/Statistics.cpp
js/src/gc/Statistics.h
js/src/gc/Zone.cpp
js/src/gc/Zone.h
js/src/jsgc.cpp
js/src/vm/NativeObject.cpp
js/src/vm/NativeObject.h
js/src/vm/Shape-inl.h
js/src/vm/Shape.cpp
js/src/vm/Shape.h
--- a/js/src/gc/Statistics.cpp
+++ b/js/src/gc/Statistics.cpp
@@ -194,19 +194,21 @@ static const PhaseInfo phases[] = {
         { PHASE_UNMARK_GRAY, "Unmark gray", PHASE_BARRIER, 56 },
     { PHASE_MARK_ROOTS, "Mark Roots", PHASE_MULTI_PARENTS, 48 },
         { PHASE_BUFFER_GRAY_ROOTS, "Buffer Gray Roots", PHASE_MARK_ROOTS, 49 },
         { PHASE_MARK_CCWS, "Mark Cross Compartment Wrappers", PHASE_MARK_ROOTS, 50 },
         { PHASE_MARK_STACK, "Mark C and JS stacks", PHASE_MARK_ROOTS, 51 },
         { PHASE_MARK_RUNTIME_DATA, "Mark Runtime-wide Data", PHASE_MARK_ROOTS, 52 },
         { PHASE_MARK_EMBEDDING, "Mark Embedding", PHASE_MARK_ROOTS, 53 },
         { PHASE_MARK_COMPARTMENTS, "Mark Compartments", PHASE_MARK_ROOTS, 54 },
-    { PHASE_LIMIT, nullptr, PHASE_NO_PARENT, 59 }
+    { PHASE_PURGE_SHAPE_TABLES, "Purge ShapeTables", PHASE_NO_PARENT, 60 },
 
-    // Current number of telemetryBuckets is 59. If you insert new phases
+    { PHASE_LIMIT, nullptr, PHASE_NO_PARENT, 60 }
+
+    // Current number of telemetryBuckets is 60. If you insert new phases
     // somewhere, start at that number and count up. Do not change any existing
     // numbers.
 };
 
 static ExtraPhaseInfo phaseExtra[PHASE_LIMIT] = { { 0, 0 } };
 
 // Mapping from all nodes with a multi-parented child to a Vector of all
 // multi-parented children and their descendants. (Single-parented children will
--- a/js/src/gc/Statistics.h
+++ b/js/src/gc/Statistics.h
@@ -83,16 +83,17 @@ enum Phase : uint8_t {
     PHASE_UNMARK_GRAY,
     PHASE_MARK_ROOTS,
     PHASE_BUFFER_GRAY_ROOTS,
     PHASE_MARK_CCWS,
     PHASE_MARK_STACK,
     PHASE_MARK_RUNTIME_DATA,
     PHASE_MARK_EMBEDDING,
     PHASE_MARK_COMPARTMENTS,
+    PHASE_PURGE_SHAPE_TABLES,
 
     PHASE_LIMIT,
     PHASE_NONE = PHASE_LIMIT,
     PHASE_EXPLICIT_SUSPENSION = PHASE_LIMIT,
     PHASE_IMPLICIT_SUSPENSION,
     PHASE_MULTI_PARENTS
 };
 
@@ -139,16 +140,17 @@ struct ZoneGCStats
     {}
 };
 
 #define FOR_EACH_GC_PROFILE_TIME(_)                                           \
     _(BeginCallback, "beginCB",  PHASE_GC_BEGIN)                              \
     _(WaitBgThread,  "waitBG",   PHASE_WAIT_BACKGROUND_THREAD)                \
     _(DiscardCode,   "discard",  PHASE_MARK_DISCARD_CODE)                     \
     _(RelazifyFunc,  "relazify", PHASE_RELAZIFY_FUNCTIONS)                    \
+    _(PurgeTables,   "purgeTables", PHASE_PURGE_SHAPE_TABLES)                 \
     _(Purge,         "purge",    PHASE_PURGE)                                 \
     _(Mark,          "mark",     PHASE_MARK)                                  \
     _(Sweep,         "sweep",    PHASE_SWEEP)                                 \
     _(Compact,       "compact",  PHASE_COMPACT)                               \
     _(EndCallback,   "endCB",    PHASE_GC_END)                                \
     _(Barriers,      "barriers", PHASE_BARRIER)
 
 const char* ExplainAbortReason(gc::AbortReason reason);
--- a/js/src/gc/Zone.cpp
+++ b/js/src/gc/Zone.cpp
@@ -43,16 +43,17 @@ JS::Zone::Zone(JSRuntime* rt)
     isSystem(false),
     usedByExclusiveThread(false),
     active(false),
     jitZone_(nullptr),
     gcState_(NoGC),
     gcScheduled_(false),
     gcPreserveCode_(false),
     jitUsingBarriers_(false),
+    keepShapeTables_(false),
     listNext_(NotOnList)
 {
     /* Ensure that there are no vtables to mess us up here. */
     MOZ_ASSERT(reinterpret_cast<JS::shadow::Zone*>(this) ==
                static_cast<JS::shadow::Zone*>(this));
 
     AutoLockGC lock(rt);
     threshold.updateAfterGC(8192, GC_NORMAL, rt->gc.tunables, rt->gc.schedulingState, lock);
--- a/js/src/gc/Zone.h
+++ b/js/src/gc/Zone.h
@@ -511,23 +511,31 @@ struct Zone : public JS::shadow::Zone,
         return runtime_->contextFromMainThread();
     }
 
 #ifdef JSGC_HASH_TABLE_CHECKS
     // Assert that the UniqueId table has been redirected successfully.
     void checkUniqueIdTableAfterMovingGC();
 #endif
 
+    bool keepShapeTables() const {
+        return keepShapeTables_;
+    }
+    void setKeepShapeTables(bool b) {
+        keepShapeTables_ = b;
+    }
+
   private:
     js::jit::JitZone* jitZone_;
 
     GCState gcState_;
     bool gcScheduled_;
     bool gcPreserveCode_;
     bool jitUsingBarriers_;
+    bool keepShapeTables_;
 
     // Allow zones to be linked into a list
     friend class js::gc::ZoneList;
     static Zone * const NotOnList;
     Zone* listNext_;
     bool isOnList() const;
     Zone* nextZone() const;
 
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -3856,20 +3856,31 @@ GCRuntime::beginMarkPhase(JS::gcreason::
      * Relazify functions after discarding JIT code (we can't relazify
      * functions with JIT code) and before the actual mark phase, so that
      * the current GC can collect the JSScripts we're unlinking here.
      * We do this only when we're performing a shrinking GC, as too much
      * relazification can cause performance issues when we have to reparse
      * the same functions over and over.
      */
     if (invocationKind == GC_SHRINK) {
-        gcstats::AutoPhase ap(stats, gcstats::PHASE_RELAZIFY_FUNCTIONS);
+        {
+            gcstats::AutoPhase ap(stats, gcstats::PHASE_RELAZIFY_FUNCTIONS);
+            for (GCZonesIter zone(rt); !zone.done(); zone.next()) {
+                RelazifyFunctions(zone, AllocKind::FUNCTION);
+                RelazifyFunctions(zone, AllocKind::FUNCTION_EXTENDED);
+            }
+        }
+
+        /* Purge ShapeTables. */
+        gcstats::AutoPhase ap(stats, gcstats::PHASE_PURGE_SHAPE_TABLES);
         for (GCZonesIter zone(rt); !zone.done(); zone.next()) {
-            RelazifyFunctions(zone, AllocKind::FUNCTION);
-            RelazifyFunctions(zone, AllocKind::FUNCTION_EXTENDED);
+            if (zone->keepShapeTables())
+                continue;
+            for (auto baseShape = zone->cellIter<BaseShape>(); !baseShape.done(); baseShape.next())
+                baseShape->maybePurgeTable();
         }
     }
 
     startNumber = number;
 
     /*
      * We must purge the runtime at the beginning of an incremental GC. The
      * danger if we purge later is that the snapshot invariant of incremental
@@ -7162,19 +7173,20 @@ js::gc::CheckHashTablesAfterMovingGC(JSR
      * that have been moved.
      */
     rt->spsProfiler.checkStringsMapAfterMovingGC();
     for (ZonesIter zone(rt, SkipAtoms); !zone.done(); zone.next()) {
         zone->checkUniqueIdTableAfterMovingGC();
         zone->checkInitialShapesTableAfterMovingGC();
         zone->checkBaseShapeTableAfterMovingGC();
 
+        JS::AutoCheckCannotGC nogc;
         for (auto baseShape = zone->cellIter<BaseShape>(); !baseShape.done(); baseShape.next()) {
-            if (baseShape->hasTable())
-                baseShape->table().checkAfterMovingGC();
+            if (ShapeTable* table = baseShape->maybeTable(nogc))
+                table->checkAfterMovingGC();
         }
     }
     for (CompartmentsIter c(rt, SkipAtoms); !c.done(); c.next()) {
         c->objectGroups.checkTablesAfterMovingGC();
         c->dtoaCache.checkCacheAfterMovingGC();
         c->checkWrapperMapAfterMovingGC();
         c->checkScriptMapsAfterMovingGC();
         if (c->debugEnvs)
--- a/js/src/vm/NativeObject.cpp
+++ b/js/src/vm/NativeObject.cpp
@@ -20,16 +20,17 @@
 
 #include "gc/Nursery-inl.h"
 #include "vm/ArrayObject-inl.h"
 #include "vm/EnvironmentObject-inl.h"
 #include "vm/Shape-inl.h"
 
 using namespace js;
 
+using JS::AutoCheckCannotGC;
 using JS::GenericNaN;
 using mozilla::ArrayLength;
 using mozilla::DebugOnly;
 using mozilla::PodCopy;
 using mozilla::RoundUpPow2;
 
 static const ObjectElements emptyElementsHeader(0, 0);
 
@@ -134,52 +135,53 @@ js::NativeObject::checkShapeConsistency(
     if (throttle == 0)
         return;
 
     MOZ_ASSERT(isNative());
 
     Shape* shape = lastProperty();
     Shape* prev = nullptr;
 
+    AutoCheckCannotGC nogc;
     if (inDictionaryMode()) {
-        MOZ_ASSERT(shape->hasTable());
-
-        ShapeTable& table = shape->table();
-        for (uint32_t fslot = table.freeList();
-             fslot != SHAPE_INVALID_SLOT;
-             fslot = getSlot(fslot).toPrivateUint32())
-        {
-            MOZ_ASSERT(fslot < slotSpan());
-        }
-
-        for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
-            MOZ_ASSERT_IF(lastProperty() != shape, !shape->hasTable());
-
-            ShapeTable::Entry& entry = table.search<MaybeAdding::NotAdding>(shape->propid());
-            MOZ_ASSERT(entry.shape() == shape);
+        if (ShapeTable* table = shape->maybeTable(nogc)) {
+            for (uint32_t fslot = table->freeList();
+                 fslot != SHAPE_INVALID_SLOT;
+                 fslot = getSlot(fslot).toPrivateUint32())
+            {
+                MOZ_ASSERT(fslot < slotSpan());
+            }
+
+            for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
+                MOZ_ASSERT_IF(lastProperty() != shape, !shape->hasTable());
+
+                ShapeTable::Entry& entry = table->search<MaybeAdding::NotAdding>(shape->propid(),
+                                                                                 nogc);
+                MOZ_ASSERT(entry.shape() == shape);
+            }
         }
 
         shape = lastProperty();
         for (int n = throttle; --n >= 0 && shape; shape = shape->parent) {
             MOZ_ASSERT_IF(shape->slot() != SHAPE_INVALID_SLOT, shape->slot() < slotSpan());
             if (!prev) {
                 MOZ_ASSERT(lastProperty() == shape);
                 MOZ_ASSERT(shape->listp == &shape_);
             } else {
                 MOZ_ASSERT(shape->listp == &prev->parent);
             }
             prev = shape;
         }
     } else {
         for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
-            if (shape->hasTable()) {
-                ShapeTable& table = shape->table();
+            if (ShapeTable* table = shape->maybeTable(nogc)) {
                 MOZ_ASSERT(shape->parent);
                 for (Shape::Range<NoGC> r(shape); !r.empty(); r.popFront()) {
-                    ShapeTable::Entry& entry = table.search<MaybeAdding::NotAdding>(r.front().propid());
+                    ShapeTable::Entry& entry =
+                        table->search<MaybeAdding::NotAdding>(r.front().propid(), nogc);
                     MOZ_ASSERT(entry.shape() == &r.front());
                 }
             }
             if (prev) {
                 MOZ_ASSERT(prev->maybeSlot() >= shape->maybeSlot());
                 shape->kids.checkConsistency(prev);
             }
             prev = shape;
@@ -246,18 +248,17 @@ js::NativeObject::slotInRange(uint32_t s
     return slot < capacity;
 }
 #endif /* DEBUG */
 
 Shape*
 js::NativeObject::lookup(ExclusiveContext* cx, jsid id)
 {
     MOZ_ASSERT(isNative());
-    ShapeTable::Entry* entry;
-    return Shape::search(cx, lastProperty(), id, &entry);
+    return Shape::search(cx, lastProperty(), id);
 }
 
 Shape*
 js::NativeObject::lookupPure(jsid id)
 {
     MOZ_ASSERT(isNative());
     return Shape::searchNoHashify(lastProperty(), id);
 }
@@ -517,25 +518,30 @@ NativeObject::sparsifyDenseElement(Exclu
     MOZ_ASSERT(!value.isMagic(JS_ELEMENTS_HOLE));
 
     removeDenseElementForSparseIndex(cx, obj, index);
 
     uint32_t slot = obj->slotSpan();
 
     RootedId id(cx, INT_TO_JSID(index));
 
+    AutoKeepShapeTables keep(cx);
     ShapeTable::Entry* entry = nullptr;
-    if (obj->inDictionaryMode())
-        entry = &obj->lastProperty()->table().search<MaybeAdding::Adding>(id);
+    if (obj->inDictionaryMode()) {
+        ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
+        if (!table)
+            return false;
+        entry = &table->search<MaybeAdding::Adding>(id, keep);
+    }
 
     // NOTE: We don't use addDataProperty because we don't want the
     // extensibility check if we're, for example, sparsifying frozen objects..
     if (!addPropertyInternal(cx, obj, id, nullptr, nullptr, slot,
                              obj->getElementsHeader()->elementAttributes(),
-                             0, entry, true)) {
+                             0, entry, true, keep)) {
         obj->setDenseElementUnchecked(index, value);
         return false;
     }
 
     MOZ_ASSERT(slot == obj->slotSpan() - 1);
     obj->initSlot(slot, value);
 
     return true;
@@ -941,36 +947,38 @@ NativeObject::CopyElementsForWrite(Exclu
 }
 
 /* static */ bool
 NativeObject::allocSlot(ExclusiveContext* cx, HandleNativeObject obj, uint32_t* slotp)
 {
     uint32_t slot = obj->slotSpan();
     MOZ_ASSERT(slot >= JSSLOT_FREE(obj->getClass()));
 
-    /*
-     * If this object is in dictionary mode, try to pull a free slot from the
-     * shape table's slot-number freelist.
-     */
+    // If this object is in dictionary mode, try to pull a free slot from the
+    // shape table's slot-number free list. Shapes without a ShapeTable have an
+    // empty free list, because we only purge ShapeTables with an empty free
+    // list.
     if (obj->inDictionaryMode()) {
-        ShapeTable& table = obj->lastProperty()->table();
-        uint32_t last = table.freeList();
-        if (last != SHAPE_INVALID_SLOT) {
+        AutoCheckCannotGC nogc;
+        if (ShapeTable* table = obj->lastProperty()->maybeTable(nogc)) {
+            uint32_t last = table->freeList();
+            if (last != SHAPE_INVALID_SLOT) {
 #ifdef DEBUG
-            MOZ_ASSERT(last < slot);
-            uint32_t next = obj->getSlot(last).toPrivateUint32();
-            MOZ_ASSERT_IF(next != SHAPE_INVALID_SLOT, next < slot);
+                MOZ_ASSERT(last < slot);
+                uint32_t next = obj->getSlot(last).toPrivateUint32();
+                MOZ_ASSERT_IF(next != SHAPE_INVALID_SLOT, next < slot);
 #endif
 
-            *slotp = last;
-
-            const Value& vref = obj->getSlot(last);
-            table.setFreeList(vref.toPrivateUint32());
-            obj->setSlot(last, UndefinedValue());
-            return true;
+                *slotp = last;
+
+                const Value& vref = obj->getSlot(last);
+                table->setFreeList(vref.toPrivateUint32());
+                obj->setSlot(last, UndefinedValue());
+                return true;
+            }
         }
     }
 
     if (slot >= SHAPE_MAXIMUM_SLOT) {
         ReportOutOfMemory(cx);
         return false;
     }
 
@@ -978,36 +986,43 @@ NativeObject::allocSlot(ExclusiveContext
 
     if (obj->inDictionaryMode() && !obj->setSlotSpan(cx, slot + 1))
         return false;
 
     return true;
 }
 
 void
-NativeObject::freeSlot(uint32_t slot)
+NativeObject::freeSlot(ExclusiveContext* cx, uint32_t slot)
 {
     MOZ_ASSERT(slot < slotSpan());
 
     if (inDictionaryMode()) {
-        ShapeTable& table = lastProperty()->table();
-        uint32_t last = table.freeList();
-
-        /* Can't afford to check the whole freelist, but let's check the head. */
-        MOZ_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < slotSpan() && last != slot);
-
-        /*
-         * Place all freed slots other than reserved slots (bug 595230) on the
-         * dictionary's free list.
-         */
-        if (JSSLOT_FREE(getClass()) <= slot) {
-            MOZ_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < slotSpan());
-            setSlot(slot, PrivateUint32Value(last));
-            table.setFreeList(slot);
-            return;
+        // Ensure we have a ShapeTable as it stores the object's free list (the
+        // list of available slots in dictionary objects).
+        AutoCheckCannotGC nogc;
+        if (ShapeTable* table = lastProperty()->ensureTableForDictionary(cx, nogc)) {
+            uint32_t last = table->freeList();
+
+            // Can't afford to check the whole free list, but let's check the head.
+            MOZ_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < slotSpan() && last != slot);
+
+            // Place all freed slots other than reserved slots (bug 595230) on the
+            // dictionary's free list.
+            if (JSSLOT_FREE(getClass()) <= slot) {
+                MOZ_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < slotSpan());
+                setSlot(slot, PrivateUint32Value(last));
+                table->setFreeList(slot);
+                return;
+            }
+        } else {
+            // OOM while creating the ShapeTable holding the free list. We can
+            // recover from it - it just means we won't be able to reuse this
+            // slot later.
+            cx->recoverFromOutOfMemory();
         }
     }
     setSlot(slot, UndefinedValue());
 }
 
 Shape*
 NativeObject::addDataProperty(ExclusiveContext* cx, jsid idArg, uint32_t slot, unsigned attrs)
 {
--- a/js/src/vm/NativeObject.h
+++ b/js/src/vm/NativeObject.h
@@ -722,17 +722,17 @@ class NativeObject : public ShapedObject
     /*
      * Allocate and free an object slot.
      *
      * FIXME: bug 593129 -- slot allocation should be done by object methods
      * after calling object-parameter-free shape methods, avoiding coupling
      * logic across the object vs. shape module wall.
      */
     static bool allocSlot(ExclusiveContext* cx, HandleNativeObject obj, uint32_t* slotp);
-    void freeSlot(uint32_t slot);
+    void freeSlot(ExclusiveContext* cx, uint32_t slot);
 
   private:
     static Shape* getChildPropertyOnDictionary(ExclusiveContext* cx, HandleNativeObject obj,
                                                HandleShape parent, MutableHandle<StackShape> child);
     static Shape* getChildProperty(ExclusiveContext* cx, HandleNativeObject obj,
                                    HandleShape parent, MutableHandle<StackShape> child);
 
   public:
@@ -777,17 +777,18 @@ class NativeObject : public ShapedObject
      *
      * Notes:
      * 1. getter and setter must be normalized based on flags (see jsscope.cpp).
      * 2. Checks for non-extensibility must be done by callers.
      */
     static Shape*
     addPropertyInternal(ExclusiveContext* cx, HandleNativeObject obj, HandleId id,
                         JSGetterOp getter, JSSetterOp setter, uint32_t slot, unsigned attrs,
-                        unsigned flags, ShapeTable::Entry* entry, bool allowDictionary);
+                        unsigned flags, ShapeTable::Entry* entry, bool allowDictionary,
+                        const AutoKeepShapeTables& keep);
 
     bool fillInAfterSwap(JSContext* cx, const Vector<Value>& values, void* priv);
 
   public:
     // Return true if this object has been converted from shared-immutable
     // prototype-rooted shape storage to dictionary-shapes in a doubly-linked
     // list.
     bool inDictionaryMode() const {
--- a/js/src/vm/Shape-inl.h
+++ b/js/src/vm/Shape-inl.h
@@ -1,9 +1,8 @@
-
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef vm_Shape_inl_h
 #define vm_Shape_inl_h
@@ -19,68 +18,93 @@
 #include "vm/TypedArrayCommon.h"
 
 #include "jsatominlines.h"
 #include "jscntxtinlines.h"
 
 namespace js {
 
 inline
+AutoKeepShapeTables::AutoKeepShapeTables(ExclusiveContext* cx)
+  : cx_(cx),
+    prev_(cx->zone()->keepShapeTables())
+{
+    cx->zone()->setKeepShapeTables(true);
+}
+
+inline
+AutoKeepShapeTables::~AutoKeepShapeTables()
+{
+    cx_->zone()->setKeepShapeTables(prev_);
+}
+
+inline
 StackBaseShape::StackBaseShape(ExclusiveContext* cx, const Class* clasp, uint32_t objectFlags)
   : flags(objectFlags),
     clasp(clasp)
 {}
 
 inline Shape*
 Shape::search(ExclusiveContext* cx, jsid id)
 {
-    ShapeTable::Entry* _;
-    return search(cx, this, id, &_);
+    return search(cx, this, id);
+}
+
+MOZ_ALWAYS_INLINE bool
+Shape::maybeCreateTableForLookup(ExclusiveContext* cx)
+{
+    if (hasTable())
+        return true;
+
+    if (!inDictionary() && numLinearSearches() < LINEAR_SEARCHES_MAX) {
+        incrementNumLinearSearches();
+        return true;
+    }
+
+    if (!isBigEnoughForAShapeTable())
+        return true;
+
+    return Shape::hashify(cx, this);
+}
+
+template<MaybeAdding Adding>
+/* static */ inline bool
+Shape::search(ExclusiveContext* cx, Shape* start, jsid id, const AutoKeepShapeTables& keep,
+              Shape** pshape, ShapeTable::Entry** pentry)
+{
+    if (start->inDictionary()) {
+        ShapeTable* table = start->ensureTableForDictionary(cx, keep);
+        if (!table)
+            return false;
+        *pentry = &table->search<Adding>(id, keep);
+        *pshape = (*pentry)->shape();
+        return true;
+    }
+
+    *pentry = nullptr;
+    *pshape = Shape::search<Adding>(cx, start, id);
+    return true;
 }
 
 template<MaybeAdding Adding>
 /* static */ inline Shape*
-Shape::search(ExclusiveContext* cx, Shape* start, jsid id, ShapeTable::Entry** pentry)
+Shape::search(ExclusiveContext* cx, Shape* start, jsid id)
 {
-    if (start->inDictionary()) {
-        *pentry = &start->table().search<Adding>(id);
-        return (*pentry)->shape();
-    }
-
-    *pentry = nullptr;
-
-    if (start->hasTable()) {
-        ShapeTable::Entry& entry = start->table().search<Adding>(id);
-        return entry.shape();
+    if (start->maybeCreateTableForLookup(cx)) {
+        JS::AutoCheckCannotGC nogc;
+        if (ShapeTable* table = start->maybeTable(nogc)) {
+            ShapeTable::Entry& entry = table->search<Adding>(id, nogc);
+            return entry.shape();
+        }
+    } else {
+        // Just do a linear search.
+        cx->recoverFromOutOfMemory();
     }
 
-    if (start->numLinearSearches() == LINEAR_SEARCHES_MAX) {
-        if (start->isBigEnoughForAShapeTable()) {
-            if (Shape::hashify(cx, start)) {
-                ShapeTable::Entry& entry = start->table().search<Adding>(id);
-                return entry.shape();
-            } else {
-                cx->recoverFromOutOfMemory();
-            }
-        }
-        /*
-         * No table built -- there weren't enough entries, or OOM occurred.
-         * Don't increment numLinearSearches, to keep hasTable() false.
-         */
-        MOZ_ASSERT(!start->hasTable());
-    } else {
-        start->incrementNumLinearSearches();
-    }
-
-    for (Shape* shape = start; shape; shape = shape->parent) {
-        if (shape->propidRef() == id)
-            return shape;
-    }
-
-    return nullptr;
+    return start->searchLinear(id);
 }
 
 inline Shape*
 Shape::new_(ExclusiveContext* cx, Handle<StackShape> other, uint32_t nfixed)
 {
     Shape* shape = other.isAccessorShape()
                    ? js::Allocate<AccessorShape>(cx)
                    : js::Allocate<Shape>(cx);
--- a/js/src/vm/Shape.cpp
+++ b/js/src/vm/Shape.cpp
@@ -30,16 +30,18 @@
 using namespace js;
 using namespace js::gc;
 
 using mozilla::CeilingLog2Size;
 using mozilla::DebugOnly;
 using mozilla::PodZero;
 using mozilla::RotateLeft;
 
+using JS::AutoCheckCannotGC;
+
 Shape* const ShapeTable::Entry::SHAPE_REMOVED = (Shape*)ShapeTable::Entry::SHAPE_COLLISION;
 
 bool
 ShapeTable::init(ExclusiveContext* cx, Shape* lastProp)
 {
     uint32_t sizeLog2 = CeilingLog2Size(entryCount_);
     uint32_t size = JS_BIT(sizeLog2);
     if (entryCount_ >= size - (size >> 2))
@@ -52,17 +54,17 @@ ShapeTable::init(ExclusiveContext* cx, S
     if (!entries_)
         return false;
 
     MOZ_ASSERT(sizeLog2 <= HASH_BITS);
     hashShift_ = HASH_BITS - sizeLog2;
 
     for (Shape::Range<NoGC> r(lastProp); !r.empty(); r.popFront()) {
         Shape& shape = r.front();
-        Entry& entry = search<MaybeAdding::Adding>(shape.propid());
+        Entry& entry = searchUnchecked<MaybeAdding::Adding>(shape.propid());
 
         /*
          * Beware duplicate args and arg vs. var conflicts: the youngest shape
          * (nearest to lastProp) must win. See bug 600067.
          */
         if (!entry.shape())
             entry.setPreservingCollision(&shape);
     }
@@ -180,17 +182,17 @@ Hash1(HashNumber hash0, uint32_t shift)
 static HashNumber
 Hash2(HashNumber hash0, uint32_t log2, uint32_t shift)
 {
     return ((hash0 << log2) >> shift) | 1;
 }
 
 template<MaybeAdding Adding>
 ShapeTable::Entry&
-ShapeTable::search(jsid id)
+ShapeTable::searchUnchecked(jsid id)
 {
     MOZ_ASSERT(entries_);
     MOZ_ASSERT(!JSID_IS_EMPTY(id));
 
     /* Compute the primary hash address. */
     HashNumber hash0 = HashId(id);
     HashNumber hash1 = Hash1(hash0, hashShift_);
     Entry* entry = &getEntry(hash1);
@@ -255,18 +257,18 @@ ShapeTable::search(jsid id)
         if (!entry->isRemoved())
             collisionFlag &= entry->hadCollision();
 #endif
     }
 
     MOZ_CRASH("Shape::search failed to find an expected entry.");
 }
 
-template ShapeTable::Entry& ShapeTable::search<MaybeAdding::Adding>(jsid id);
-template ShapeTable::Entry& ShapeTable::search<MaybeAdding::NotAdding>(jsid id);
+template ShapeTable::Entry& ShapeTable::searchUnchecked<MaybeAdding::Adding>(jsid id);
+template ShapeTable::Entry& ShapeTable::searchUnchecked<MaybeAdding::NotAdding>(jsid id);
 
 bool
 ShapeTable::change(ExclusiveContext* cx, int log2Delta)
 {
     MOZ_ASSERT(entries_);
     MOZ_ASSERT(-1 <= log2Delta && log2Delta <= 1);
 
     /*
@@ -283,19 +285,20 @@ ShapeTable::change(ExclusiveContext* cx,
     /* Now that we have newTable allocated, update members. */
     MOZ_ASSERT(newLog2 <= HASH_BITS);
     hashShift_ = HASH_BITS - newLog2;
     removedCount_ = 0;
     Entry* oldTable = entries_;
     entries_ = newTable;
 
     /* Copy only live entries, leaving removed and free ones behind. */
+    AutoCheckCannotGC nogc;
     for (Entry* oldEntry = oldTable; oldSize != 0; oldEntry++) {
         if (Shape* shape = oldEntry->shape()) {
-            Entry& entry = search<MaybeAdding::Adding>(shape->propid());
+            Entry& entry = search<MaybeAdding::Adding>(shape->propid(), nogc);
             MOZ_ASSERT(entry.isFree());
             entry.setShape(shape);
         }
         oldSize--;
     }
 
     MOZ_ASSERT(capacity() == newSize);
 
@@ -528,22 +531,27 @@ NativeObject::addProperty(ExclusiveConte
     if (!IsExtensible(cx, obj, &extensible))
         return nullptr;
     if (!extensible) {
         if (cx->isJSContext())
             obj->reportNotExtensible(cx->asJSContext());
         return nullptr;
     }
 
+    AutoKeepShapeTables keep(cx);
     ShapeTable::Entry* entry = nullptr;
-    if (obj->inDictionaryMode())
-        entry = &obj->lastProperty()->table().search<MaybeAdding::Adding>(id);
+    if (obj->inDictionaryMode()) {
+        ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
+        if (!table)
+            return nullptr;
+        entry = &table->search<MaybeAdding::Adding>(id, keep);
+    }
 
     return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags, entry,
-                               allowDictionary);
+                               allowDictionary, keep);
 }
 
 static bool
 ShouldConvertToDictionary(NativeObject* obj)
 {
     /*
      * Use a lower limit if this object is likely a hashmap (SETELEM was used
      * to set properties).
@@ -554,17 +562,17 @@ ShouldConvertToDictionary(NativeObject* 
 }
 
 /* static */ Shape*
 NativeObject::addPropertyInternal(ExclusiveContext* cx,
                                   HandleNativeObject obj, HandleId id,
                                   GetterOp getter, SetterOp setter,
                                   uint32_t slot, unsigned attrs,
                                   unsigned flags, ShapeTable::Entry* entry,
-                                  bool allowDictionary)
+                                  bool allowDictionary, const AutoKeepShapeTables& keep)
 {
     MOZ_ASSERT_IF(!allowDictionary, !obj->inDictionaryMode());
     MOZ_ASSERT(getter != JS_PropertyStub);
     MOZ_ASSERT(setter != JS_StrictPropertyStub);
 
     AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
 
     /*
@@ -579,25 +587,27 @@ NativeObject::addPropertyInternal(Exclus
             obj->lastProperty()->hasMissingSlot() ||
             (slot == obj->lastProperty()->maybeSlot() + 1);
         MOZ_ASSERT_IF(!allowDictionary, stableSlot);
         if (allowDictionary &&
             (!stableSlot || ShouldConvertToDictionary(obj)))
         {
             if (!obj->toDictionaryMode(cx))
                 return nullptr;
-            table = &obj->lastProperty()->table();
-            entry = &table->search<MaybeAdding::Adding>(id);
+            table = obj->lastProperty()->maybeTable(keep);
+            entry = &table->search<MaybeAdding::Adding>(id, keep);
         }
     } else {
-        table = &obj->lastProperty()->table();
+        table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
+        if (!table)
+            return nullptr;
         if (table->needsToGrow()) {
             if (!table->grow(cx))
                 return nullptr;
-            entry = &table->search<MaybeAdding::Adding>(id);
+            entry = &table->search<MaybeAdding::Adding>(id, keep);
             MOZ_ASSERT(!entry->shape());
         }
     }
 
     MOZ_ASSERT(!!table == !!entry);
 
     /* Find or create a property tree node labeled by our arguments. */
     RootedShape shape(cx);
@@ -627,17 +637,17 @@ NativeObject::addPropertyInternal(Exclus
         MOZ_ASSERT(shape == obj->lastProperty());
 
         if (table) {
             /* Store the tree node pointer in the table entry for id. */
             entry->setPreservingCollision(shape);
             table->incEntryCount();
 
             /* Pass the table along to the new last property, namely shape. */
-            MOZ_ASSERT(&shape->parent->table() == table);
+            MOZ_ASSERT(shape->parent->maybeTable(keep) == table);
             shape->parent->handoffTableTo(shape);
         }
 
         obj->checkShapeConsistency();
         return shape;
     }
 
     obj->checkShapeConsistency();
@@ -747,18 +757,25 @@ NativeObject::putProperty(ExclusiveConte
      *
      * Note that we can only try to claim an entry in a table that is thread
      * local. An object may be thread local *without* its shape being thread
      * local. The only thread local objects that *also* have thread local
      * shapes are dictionaries that were allocated/converted thread
      * locally. Only for those objects we can try to claim an entry in its
      * shape table.
      */
+    AutoKeepShapeTables keep(cx);
     ShapeTable::Entry* entry;
-    RootedShape shape(cx, Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, &entry));
+    RootedShape shape(cx);
+    if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep,
+                                            shape.address(), &entry))
+    {
+        return nullptr;
+    }
+
     if (!shape) {
         /*
          * You can't add properties to a non-extensible object, but you can change
          * attributes of properties in such objects.
          */
         bool extensible;
 
         if (!IsExtensible(cx, obj, &extensible))
@@ -766,17 +783,17 @@ NativeObject::putProperty(ExclusiveConte
 
         if (!extensible) {
             if (cx->isJSContext())
                 obj->reportNotExtensible(cx->asJSContext());
             return nullptr;
         }
 
         return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags,
-                                   entry, true);
+                                   entry, true, keep);
     }
 
     /* Property exists: search must have returned a valid entry. */
     MOZ_ASSERT_IF(entry, !entry->isRemoved());
 
     if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
         return nullptr;
 
@@ -812,17 +829,19 @@ NativeObject::putProperty(ExclusiveConte
     /*
      * Overwriting a non-last property requires switching to dictionary mode.
      * The shape tree is shared immutable, and we can't removeProperty and then
      * addPropertyInternal because a failure under add would lose data.
      */
     if (shape != obj->lastProperty() && !obj->inDictionaryMode()) {
         if (!obj->toDictionaryMode(cx))
             return nullptr;
-        entry = &obj->lastProperty()->table().search<MaybeAdding::NotAdding>(shape->propid());
+        ShapeTable* table = obj->lastProperty()->maybeTable(keep);
+        MOZ_ASSERT(table);
+        entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
         shape = entry->shape();
     }
 
     MOZ_ASSERT_IF(shape->hasSlot() && !(attrs & JSPROP_SHARED), shape->slot() == slot);
 
     if (obj->inDictionaryMode()) {
         /*
          * Updating some property in a dictionary-mode object. Create a new
@@ -896,17 +915,17 @@ NativeObject::putProperty(ExclusiveConte
     /*
      * Can't fail now, so free the previous incarnation's slot if the new shape
      * has no slot. But we do not need to free oldSlot (and must not, as trying
      * to will botch an assertion in JSObject::freeSlot) if the new last
      * property (shape here) has a slotSpan that does not cover it.
      */
     if (hadSlot && !shape->hasSlot()) {
         if (oldSlot < obj->slotSpan())
-            obj->freeSlot(oldSlot);
+            obj->freeSlot(cx, oldSlot);
         /* Note: The optimization based on propertyRemovals is only relevant to the main thread. */
         if (cx->isJSContext())
             ++cx->asJSContext()->runtime()->propertyRemovals;
     }
 
     obj->checkShapeConsistency();
 
     return shape;
@@ -948,29 +967,35 @@ NativeObject::changeProperty(ExclusiveCo
 }
 
 bool
 NativeObject::removeProperty(ExclusiveContext* cx, jsid id_)
 {
     RootedId id(cx, id_);
     RootedNativeObject self(cx, this);
 
+    AutoKeepShapeTables keep(cx);
     ShapeTable::Entry* entry;
-    RootedShape shape(cx, Shape::search(cx, lastProperty(), id, &entry));
+    RootedShape shape(cx);
+    if (!Shape::search(cx, lastProperty(), id, keep, shape.address(), &entry))
+        return false;
+
     if (!shape)
         return true;
 
     /*
      * If shape is not the last property added, or the last property cannot
      * be removed, switch to dictionary mode.
      */
     if (!self->inDictionaryMode() && (shape != self->lastProperty() || !self->canRemoveLastProperty())) {
         if (!self->toDictionaryMode(cx))
             return false;
-        entry = &self->lastProperty()->table().search<MaybeAdding::NotAdding>(shape->propid());
+        ShapeTable* table = self->lastProperty()->maybeTable(keep);
+        MOZ_ASSERT(table);
+        entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
         shape = entry->shape();
     }
 
     /*
      * If in dictionary mode, get a new shape for the last property after the
      * removal. We need a fresh shape for all dictionary deletions, even of
      * the last property. Otherwise, a shape could replay and caches might
      * return deleted DictionaryShapes! See bug 595365. Do this before changing
@@ -996,36 +1021,37 @@ NativeObject::removeProperty(ExclusiveCo
             if (!nbase)
                 return false;
             previous->base_ = nbase;
         }
     }
 
     /* If shape has a slot, free its slot number. */
     if (shape->hasSlot()) {
-        self->freeSlot(shape->slot());
+        self->freeSlot(cx, shape->slot());
         if (cx->isJSContext())
             ++cx->asJSContext()->runtime()->propertyRemovals;
     }
 
     /*
      * A dictionary-mode object owns mutable, unique shapes on a non-circular
      * doubly linked list, hashed by lastProperty()->table. So we can edit the
      * list and hash in place.
      */
     if (self->inDictionaryMode()) {
-        ShapeTable& table = self->lastProperty()->table();
+        ShapeTable* table = self->lastProperty()->maybeTable(keep);
+        MOZ_ASSERT(table);
 
         if (entry->hadCollision()) {
             entry->setRemoved();
-            table.decEntryCount();
-            table.incRemovedCount();
+            table->decEntryCount();
+            table->incRemovedCount();
         } else {
             entry->setFree();
-            table.decEntryCount();
+            table->decEntryCount();
 
 #ifdef DEBUG
             /*
              * Check the consistency of the table but limit the number of
              * checks not to alter significantly the complexity of the
              * delete in debug builds, see bug 534493.
              */
             Shape* aprop = self->lastProperty();
@@ -1042,19 +1068,19 @@ NativeObject::removeProperty(ExclusiveCo
             /* Hand off table from the old to new last property. */
             oldLastProp->handoffTableTo(self->lastProperty());
         }
 
         /* Generate a new shape for the object, infallibly. */
         JS_ALWAYS_TRUE(self->generateOwnShape(cx, spare));
 
         /* Consider shrinking table if its load factor is <= .25. */
-        uint32_t size = table.capacity();
-        if (size > ShapeTable::MIN_SIZE && table.entryCount() <= size >> 2)
-            (void) table.change(cx, -1);
+        uint32_t size = table->capacity();
+        if (size > ShapeTable::MIN_SIZE && table->entryCount() <= size >> 2)
+            (void) table->change(cx, -1);
     } else {
         /*
          * Non-dictionary-mode shape tables are shared immutables, so all we
          * need do is retract the last property and we'll either get or else
          * lazily make via a later hashify the exact table for the new property
          * lineage.
          */
         MOZ_ASSERT(shape == self->lastProperty());
@@ -1140,20 +1166,24 @@ NativeObject::replaceWithNewEquivalentSh
                    : Allocate<Shape>(cx);
         if (!newShape)
             return nullptr;
         new (newShape) Shape(oldRoot->base()->unowned(), 0);
         self = selfRoot;
         oldShape = oldRoot;
     }
 
-    ShapeTable& table = self->lastProperty()->table();
+    AutoCheckCannotGC nogc;
+    ShapeTable* table = self->lastProperty()->ensureTableForDictionary(cx, nogc);
+    if (!table)
+        return nullptr;
+
     ShapeTable::Entry* entry = oldShape->isEmptyShape()
-                               ? nullptr
-                               : &table.search<MaybeAdding::NotAdding>(oldShape->propidRef());
+        ? nullptr
+        : &table->search<MaybeAdding::NotAdding>(oldShape->propidRef(), nogc);
 
     /*
      * Splice the new shape into the same position as the old shape, preserving
      * enumeration order (see bug 601399).
      */
     StackShape nshape(oldShape);
     newShape->initDictionaryShape(nshape, self->numFixedSlots(), oldShape->listp);
 
@@ -1278,20 +1308,18 @@ BaseShape::copyFromUnowned(BaseShape& de
 inline void
 BaseShape::adoptUnowned(UnownedBaseShape* other)
 {
     // This is a base shape owned by a dictionary object, update it to reflect the
     // unowned base shape of a new last property.
     MOZ_ASSERT(isOwned());
 
     uint32_t span = slotSpan();
-    ShapeTable* table = &this->table();
 
     BaseShape::copyFromUnowned(*this, *other);
-    setTable(table);
     setSlotSpan(span);
 
     assertConsistency();
 }
 
 /* static */ UnownedBaseShape*
 BaseShape::getUnowned(ExclusiveContext* cx, StackBaseShape& base)
 {
@@ -1345,39 +1373,42 @@ BaseShape::traceChildrenSkipShapeTable(J
         TraceEdge(trc, &unowned_, "base");
 
     assertConsistency();
 }
 
 void
 BaseShape::traceShapeTable(JSTracer* trc)
 {
-    if (hasTable())
-        table().trace(trc);
+    AutoCheckCannotGC nogc;
+    if (ShapeTable* table = maybeTable(nogc))
+        table->trace(trc);
 }
 
 #ifdef DEBUG
 bool
 BaseShape::canSkipMarkingShapeTable(Shape* lastShape)
 {
     // Check that every shape in the shape table will be marked by marking
     // |lastShape|.
 
-    if (!hasTable())
+    AutoCheckCannotGC nogc;
+    ShapeTable* table = maybeTable(nogc);
+    if (!table)
         return true;
 
     uint32_t count = 0;
     for (Shape::Range<NoGC> r(lastShape); !r.empty(); r.popFront()) {
         Shape* shape = &r.front();
-        ShapeTable::Entry& entry = table().search<MaybeAdding::NotAdding>(shape->propid());
+        ShapeTable::Entry& entry = table->search<MaybeAdding::NotAdding>(shape->propid(), nogc);
         if (entry.isLive())
             count++;
     }
 
-    return count == table().entryCount();
+    return count == table->entryCount();
 }
 #endif
 
 #ifdef JSGC_HASH_TABLE_CHECKS
 
 void
 Zone::checkBaseShapeTableAfterMovingGC()
 {
@@ -1727,18 +1758,19 @@ AutoRooterGetterSetter::Inner::trace(JST
         TraceRoot(trc, (JSObject**) psetter, "AutoRooterGetterSetter setter");
 }
 
 JS::ubi::Node::Size
 JS::ubi::Concrete<js::Shape>::size(mozilla::MallocSizeOf mallocSizeOf) const
 {
     Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
 
-    if (get().hasTable())
-        size += get().table().sizeOfIncludingThis(mallocSizeOf);
+    AutoCheckCannotGC nogc;
+    if (ShapeTable* table = get().maybeTable(nogc))
+        size += table->sizeOfIncludingThis(mallocSizeOf);
 
     if (!get().inDictionary() && get().kids.isHash())
         size += get().kids.toHash()->sizeOfIncludingThis(mallocSizeOf);
 
     return size;
 }
 
 JS::ubi::Node::Size
--- a/js/src/vm/Shape.h
+++ b/js/src/vm/Shape.h
@@ -88,16 +88,22 @@
  * Shape in the property tree exceeds LINEAR_SEARCHES_MAX and the Shape's
  * lineage has (excluding the EmptyShape) at least MIN_ENTRIES, we create an
  * auxiliary hash table -- the ShapeTable -- that allows faster lookup.
  * Furthermore, a ShapeTable is always created for dictionary mode lists,
  * and it is attached to the last Shape in the lineage. Shape tables for
  * property tree Shapes never change, but shape tables for dictionary mode
  * Shapes can grow and shrink.
  *
+ * To save memory, shape tables can be discarded on GC and recreated when
+ * needed. AutoKeepShapeTables can be used to avoid discarding shape tables
+ * for a particular zone. Methods operating on ShapeTables take either an
+ * AutoCheckCannotGC or AutoKeepShapeTables argument, to help ensure tables
+ * are not purged while we're using them.
+ *
  * There used to be a long, math-heavy comment here explaining why property
  * trees are more space-efficient than alternatives.  This was removed in bug
  * 631138; see that bug for the full details.
  *
  * For getters/setters, an AccessorShape is allocated. This is a slightly fatter
  * type with extra fields for the getter/setter data.
  *
  * Because many Shapes have similar data, there is actually a secondary type
@@ -115,16 +121,18 @@ typedef JSGetterOp GetterOp;
 typedef JSSetterOp SetterOp;
 
 /* Limit on the number of slotful properties in an object. */
 static const uint32_t SHAPE_INVALID_SLOT = JS_BIT(24) - 1;
 static const uint32_t SHAPE_MAXIMUM_SLOT = JS_BIT(24) - 2;
 
 enum class MaybeAdding { Adding = true, NotAdding = false };
 
+class AutoKeepShapeTables;
+
 /*
  * Shapes use multiplicative hashing, but specialized to
  * minimize footprint.
  */
 class ShapeTable {
   public:
     friend class NativeObject;
     friend class BaseShape;
@@ -184,16 +192,19 @@ class ShapeTable {
     uint32_t        removedCount_;      /* removed entry sentinels in table */
 
     uint32_t        freeList_;          /* SHAPE_INVALID_SLOT or head of slot
                                            freelist in owning dictionary-mode
                                            object */
 
     Entry*          entries_;          /* table of ptrs to shared tree nodes */
 
+    template<MaybeAdding Adding>
+    Entry& searchUnchecked(jsid id);
+
   public:
     explicit ShapeTable(uint32_t nentries)
       : hashShift_(HASH_BITS - MIN_SIZE_LOG2),
         entryCount_(nentries),
         removedCount_(0),
         freeList_(SHAPE_INVALID_SLOT),
         entries_(nullptr)
     {
@@ -219,17 +230,24 @@ class ShapeTable {
 
     // init() is fallible and reports OOM to the context.
     bool init(ExclusiveContext* cx, Shape* lastProp);
 
     // change() is fallible but does not report OOM.
     bool change(ExclusiveContext* cx, int log2Delta);
 
     template<MaybeAdding Adding>
-    Entry& search(jsid id);
+    MOZ_ALWAYS_INLINE Entry& search(jsid id, const AutoKeepShapeTables&) {
+        return searchUnchecked<Adding>(id);
+    }
+
+    template<MaybeAdding Adding>
+    MOZ_ALWAYS_INLINE Entry& search(jsid id, const JS::AutoCheckCannotGC&) {
+        return searchUnchecked<Adding>(id);
+    }
 
     void trace(JSTracer* trc);
 #ifdef JSGC_HASH_TABLE_CHECKS
     void checkAfterMovingGC();
 #endif
 
   private:
     Entry& getEntry(uint32_t i) const {
@@ -261,16 +279,30 @@ class ShapeTable {
     /*
      * Try to grow the table.  On failure, reports out of memory on cx
      * and returns false.  This will make any extant pointers into the
      * table invalid.  Don't call this unless needsToGrow() is true.
      */
     bool grow(ExclusiveContext* cx);
 };
 
+// Ensures no shape tables are purged in the current zone.
+class MOZ_RAII AutoKeepShapeTables
+{
+    ExclusiveContext* cx_;
+    bool prev_;
+
+    AutoKeepShapeTables(const AutoKeepShapeTables&) = delete;
+    void operator=(const AutoKeepShapeTables&) = delete;
+
+  public:
+    explicit inline AutoKeepShapeTables(ExclusiveContext* cx);
+    inline ~AutoKeepShapeTables();
+};
+
 /*
  * Use the reserved attribute bit to mean shadowability.
  */
 #define JSPROP_SHADOWABLE       JSPROP_INTERNAL_USE_BIT
 
 /*
  * Shapes encode information about both a property lineage *and* a particular
  * property. This information is split across the Shape and the BaseShape
@@ -409,19 +441,33 @@ class BaseShape : public gc::TenuredCell
     void setOwned(UnownedBaseShape* unowned) {
         flags |= OWNED_SHAPE;
         unowned_ = unowned;
     }
 
     uint32_t getObjectFlags() const { return flags & OBJECT_FLAG_MASK; }
 
     bool hasTable() const { MOZ_ASSERT_IF(table_, isOwned()); return table_ != nullptr; }
-    ShapeTable& table() const { MOZ_ASSERT(table_ && isOwned()); return *table_; }
     void setTable(ShapeTable* table) { MOZ_ASSERT(isOwned()); table_ = table; }
 
+    ShapeTable* maybeTable(const AutoKeepShapeTables&) const {
+        MOZ_ASSERT_IF(table_, isOwned());
+        return table_;
+    }
+    ShapeTable* maybeTable(const JS::AutoCheckCannotGC&) const {
+        MOZ_ASSERT_IF(table_, isOwned());
+        return table_;
+    }
+    void maybePurgeTable() {
+        if (table_ && table_->freeList() == SHAPE_INVALID_SLOT) {
+            js_delete(table_);
+            table_ = nullptr;
+        }
+    }
+
     uint32_t slotSpan() const { MOZ_ASSERT(isOwned()); return slotSpan_; }
     void setSlotSpan(uint32_t slotSpan) { MOZ_ASSERT(isOwned()); slotSpan_ = slotSpan; }
 
     /*
      * Lookup base shapes from the zone's baseShapes table, adding if not
      * already found.
      */
     static UnownedBaseShape* getUnowned(ExclusiveContext* cx, StackBaseShape& base);
@@ -575,18 +621,23 @@ class Shape : public gc::TenuredCell
                                      to many-kids data structure */
         GCPtrShape* listp;        /* dictionary list starting at shape_
                                      has a double-indirect back pointer,
                                      either to the next shape's parent if not
                                      last, else to obj->shape_ */
     };
 
     template<MaybeAdding Adding = MaybeAdding::NotAdding>
-    static inline Shape* search(ExclusiveContext* cx, Shape* start, jsid id,
-                                ShapeTable::Entry** pentry);
+    static inline Shape* search(ExclusiveContext* cx, Shape* start, jsid id);
+
+    template<MaybeAdding Adding = MaybeAdding::NotAdding>
+    static inline MOZ_MUST_USE bool search(ExclusiveContext* cx, Shape* start, jsid id,
+                                           const AutoKeepShapeTables&,
+                                           Shape** pshape, ShapeTable::Entry** pentry);
+
     static inline Shape* searchNoHashify(Shape* start, jsid id);
 
     void removeFromDictionary(NativeObject* obj);
     void insertIntoDictionary(GCPtrShape* dictp);
 
     inline void initDictionaryShape(const StackShape& child, uint32_t nfixed,
                                     GCPtrShape* dictp);
 
@@ -613,28 +664,49 @@ class Shape : public gc::TenuredCell
     bool ensureOwnBaseShape(ExclusiveContext* cx) {
         if (base()->isOwned())
             return true;
         return makeOwnBaseShape(cx);
     }
 
     bool makeOwnBaseShape(ExclusiveContext* cx);
 
+    MOZ_ALWAYS_INLINE MOZ_MUST_USE bool maybeCreateTableForLookup(ExclusiveContext* cx);
+
   public:
     bool hasTable() const { return base()->hasTable(); }
-    ShapeTable& table() const { return base()->table(); }
+
+    ShapeTable* maybeTable(const AutoKeepShapeTables& keep) const {
+        return base()->maybeTable(keep);
+    }
+    ShapeTable* maybeTable(const JS::AutoCheckCannotGC& check) const {
+        return base()->maybeTable(check);
+    }
+
+    template <typename T>
+    MOZ_MUST_USE ShapeTable* ensureTableForDictionary(ExclusiveContext* cx, const T& nogc) {
+        MOZ_ASSERT(inDictionary());
+        if (ShapeTable* table = maybeTable(nogc))
+            return table;
+        if (!hashify(cx, this))
+            return nullptr;
+        ShapeTable* table = maybeTable(nogc);
+        MOZ_ASSERT(table);
+        return table;
+    }
 
     void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
                                 JS::ShapeInfo* info) const
     {
-        if (hasTable()) {
+        JS::AutoCheckCannotGC nogc;
+        if (ShapeTable* table = maybeTable(nogc)) {
             if (inDictionary())
-                info->shapesMallocHeapDictTables += table().sizeOfIncludingThis(mallocSizeOf);
+                info->shapesMallocHeapDictTables += table->sizeOfIncludingThis(mallocSizeOf);
             else
-                info->shapesMallocHeapTreeTables += table().sizeOfIncludingThis(mallocSizeOf);
+                info->shapesMallocHeapTreeTables += table->sizeOfIncludingThis(mallocSizeOf);
         }
 
         if (!inDictionary() && kids.isHash())
             info->shapesMallocHeapTreeKids += kids.toHash()->sizeOfIncludingThis(mallocSizeOf);
     }
 
     bool isAccessorShape() const {
         MOZ_ASSERT_IF(flags & ACCESSOR_SHAPE, getAllocKind() == gc::AllocKind::ACCESSOR_SHAPE);
@@ -887,18 +959,19 @@ class Shape : public gc::TenuredCell
     }
     bool isAccessorDescriptor() const {
         return (attrs & (JSPROP_SETTER | JSPROP_GETTER)) != 0;
     }
 
     bool hasShadowable() const { return attrs & JSPROP_SHADOWABLE; }
 
     uint32_t entryCount() {
-        if (hasTable())
-            return table().entryCount();
+        JS::AutoCheckCannotGC nogc;
+        if (ShapeTable* table = maybeTable(nogc))
+            return table->entryCount();
         uint32_t count = 0;
         for (Shape::Range<NoGC> r(this); !r.empty(); r.popFront())
             ++count;
         return count;
     }
 
   private:
     bool isBigEnoughForAShapeTableSlow() {
@@ -908,17 +981,16 @@ class Shape : public gc::TenuredCell
             if (count >= ShapeTable::MIN_ENTRIES)
                 return true;
         }
         return false;
     }
 
   public:
     bool isBigEnoughForAShapeTable() {
-        MOZ_ASSERT(!inDictionary());
         MOZ_ASSERT(!hasTable());
 
         // isBigEnoughForAShapeTableSlow is pretty inefficient so we only call
         // it once and cache the result.
 
         if (flags & HAS_CACHED_BIG_ENOUGH_FOR_SHAPE_TABLE) {
             bool res = flags & CACHED_BIG_ENOUGH_FOR_SHAPE_TABLE;
             MOZ_ASSERT(res == isBigEnoughForAShapeTableSlow());
@@ -943,17 +1015,17 @@ class Shape : public gc::TenuredCell
     void finalize(FreeOp* fop);
     void removeChild(Shape* child);
 
     static const JS::TraceKind TraceKind = JS::TraceKind::Shape;
 
     void traceChildren(JSTracer* trc);
 
     inline Shape* search(ExclusiveContext* cx, jsid id);
-    inline Shape* searchLinear(jsid id);
+    MOZ_ALWAYS_INLINE Shape* searchLinear(jsid id);
 
     void fixupAfterMovingGC();
     void fixupGetterSetterForBarrier(JSTracer* trc);
     void updateBaseShapeAfterMovingGC();
 
     /* For JIT usage */
     static inline size_t offsetOfBase() { return offsetof(Shape, base_); }
     static inline size_t offsetOfSlotInfo() { return offsetof(Shape, slotInfo); }
@@ -1411,24 +1483,16 @@ Shape::initDictionaryShape(const StackSh
     this->listp = nullptr;
     if (dictp)
         insertIntoDictionary(dictp);
 }
 
 inline Shape*
 Shape::searchLinear(jsid id)
 {
-    /*
-     * Non-dictionary shapes can acquire a table at any point the main thread
-     * is operating on it, so other threads inspecting such shapes can't use
-     * their table without racing. This function can be called from any thread
-     * on any non-dictionary shape.
-     */
-    MOZ_ASSERT(!inDictionary());
-
     for (Shape* shape = this; shape; ) {
         if (shape->propidRef() == id)
             return shape;
         shape = shape->parent;
     }
 
     return nullptr;
 }
@@ -1439,18 +1503,19 @@ Shape::searchLinear(jsid id)
  */
 inline Shape*
 Shape::searchNoHashify(Shape* start, jsid id)
 {
     /*
      * If we have a table, search in the shape table, else do a linear
      * search. We never hashify into a table in parallel.
      */
-    if (start->hasTable()) {
-        ShapeTable::Entry& entry = start->table().search<MaybeAdding::NotAdding>(id);
+    JS::AutoCheckCannotGC nogc;
+    if (ShapeTable* table = start->maybeTable(nogc)) {
+        ShapeTable::Entry& entry = table->search<MaybeAdding::NotAdding>(id, nogc);
         return entry.shape();
     }
 
     return start->searchLinear(id);
 }
 
 inline bool
 Shape::matches(const StackShape& other) const