Bug 1314569 - Purge ShapeTables on shrinking GCs. r=jonco
authorJan de Mooij <jdemooij@mozilla.com>
Thu, 03 Nov 2016 19:15:15 +0100
changeset 351661 b3cf01afceb6fd3da03161f077f52bdc4e351d2d
parent 351660 2cf0ccb1a85cabf6d784ec3433f584da48864eff
child 351662 18ca736c0d1daef0c1edb4e19b622d3df131f24a
push id13
push userfmarier@mozilla.com
push dateFri, 11 Nov 2016 01:36:56 +0000
reviewersjonco
bugs1314569
milestone52.0a1
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