Bug 1236523 part 3 - Templatize Shape::search and ShapeTable::search. r=bhackett
authorJan de Mooij <jdemooij@mozilla.com>
Thu, 07 Jan 2016 10:18:06 +0100
changeset 278871 cb2aea4df00597cc86ea1bc998f3f52c155879f5
parent 278870 f8817ab2f74500c71ec2f51eb38a315af871e6c6
child 278872 4c8dd8987cf49a928f61be9514434c0298e6990b
push id69919
push userjandemooij@gmail.com
push dateThu, 07 Jan 2016 09:20:07 +0000
treeherdermozilla-inbound@cb2aea4df005 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs1236523
milestone46.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 1236523 part 3 - Templatize Shape::search and ShapeTable::search. r=bhackett
js/src/vm/NativeObject.cpp
js/src/vm/ScopeObject.cpp
js/src/vm/Shape-inl.h
js/src/vm/Shape.cpp
js/src/vm/Shape.h
--- a/js/src/vm/NativeObject.cpp
+++ b/js/src/vm/NativeObject.cpp
@@ -129,17 +129,17 @@ js::NativeObject::checkShapeConsistency(
              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(shape->propid(), false);
+            ShapeTable::Entry& entry = table.search<MaybeAdding::NotAdding>(shape->propid());
             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);
@@ -150,17 +150,17 @@ js::NativeObject::checkShapeConsistency(
             prev = shape;
         }
     } else {
         for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
             if (shape->hasTable()) {
                 ShapeTable& table = shape->table();
                 MOZ_ASSERT(shape->parent);
                 for (Shape::Range<NoGC> r(shape); !r.empty(); r.popFront()) {
-                    ShapeTable::Entry& entry = table.search(r.front().propid(), false);
+                    ShapeTable::Entry& entry = table.search<MaybeAdding::NotAdding>(r.front().propid());
                     MOZ_ASSERT(entry.shape() == &r.front());
                 }
             }
             if (prev) {
                 MOZ_ASSERT(prev->maybeSlot() >= shape->maybeSlot());
                 shape->kids.checkConsistency(prev);
             }
             prev = shape;
--- a/js/src/vm/ScopeObject.cpp
+++ b/js/src/vm/ScopeObject.cpp
@@ -1002,17 +1002,17 @@ StaticBlockObject::addVar(ExclusiveConte
 {
     MOZ_ASSERT(JSID_IS_ATOM(id));
     MOZ_ASSERT(index < LOCAL_INDEX_LIMIT);
 
     *redeclared = false;
 
     /* Inline NativeObject::addProperty in order to trap the redefinition case. */
     ShapeTable::Entry* entry;
-    if (Shape::search(cx, block->lastProperty(), id, &entry, true)) {
+    if (Shape::search<MaybeAdding::Adding>(cx, block->lastProperty(), id, &entry)) {
         *redeclared = true;
         return nullptr;
     }
 
     /*
      * Don't convert this object to dictionary mode so that we can clone the
      * block's shape later.
      */
--- a/js/src/vm/Shape-inl.h
+++ b/js/src/vm/Shape-inl.h
@@ -32,35 +32,36 @@ StackBaseShape::StackBaseShape(Exclusive
 
 inline Shape*
 Shape::search(ExclusiveContext* cx, jsid id)
 {
     ShapeTable::Entry* _;
     return search(cx, this, id, &_);
 }
 
+template<MaybeAdding Adding>
 /* static */ inline Shape*
-Shape::search(ExclusiveContext* cx, Shape* start, jsid id, ShapeTable::Entry** pentry, bool adding)
+Shape::search(ExclusiveContext* cx, Shape* start, jsid id, ShapeTable::Entry** pentry)
 {
     if (start->inDictionary()) {
-        *pentry = &start->table().search(id, adding);
+        *pentry = &start->table().search<Adding>(id);
         return (*pentry)->shape();
     }
 
     *pentry = nullptr;
 
     if (start->hasTable()) {
-        ShapeTable::Entry& entry = start->table().search(id, adding);
+        ShapeTable::Entry& entry = start->table().search<Adding>(id);
         return entry.shape();
     }
 
     if (start->numLinearSearches() == LINEAR_SEARCHES_MAX) {
         if (start->isBigEnoughForAShapeTable()) {
             if (Shape::hashify(cx, start)) {
-                ShapeTable::Entry& entry = start->table().search(id, adding);
+                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.
--- a/js/src/vm/Shape.cpp
+++ b/js/src/vm/Shape.cpp
@@ -55,17 +55,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(shape.propid(), true);
+        Entry& entry = search<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);
     }
@@ -181,18 +181,19 @@ 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, bool adding)
+ShapeTable::search(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);
@@ -206,62 +207,70 @@ ShapeTable::search(jsid id, bool adding)
     if (shape && shape->propidRaw() == id)
         return *entry;
 
     /* Collision: double hash. */
     uint32_t sizeLog2 = HASH_BITS - hashShift_;
     HashNumber hash2 = Hash2(hash0, sizeLog2, hashShift_);
     uint32_t sizeMask = JS_BITMASK(sizeLog2);
 
-#ifdef DEBUG
-    bool collisionFlag = true;
-#endif
-
     /* Save the first removed entry pointer so we can recycle it if adding. */
     Entry* firstRemoved;
-    if (entry->isRemoved()) {
-        firstRemoved = entry;
-    } else {
-        firstRemoved = nullptr;
-        if (adding && !entry->hadCollision())
-            entry->flagCollision();
+    if (Adding == MaybeAdding::Adding) {
+        if (entry->isRemoved()) {
+            firstRemoved = entry;
+        } else {
+            firstRemoved = nullptr;
+            if (!entry->hadCollision())
+                entry->flagCollision();
+        }
+    }
+
 #ifdef DEBUG
-        collisionFlag &= entry->hadCollision();
+    bool collisionFlag = true;
+    if (!entry->isRemoved())
+        collisionFlag = entry->hadCollision();
 #endif
-    }
 
     while (true) {
         hash1 -= hash2;
         hash1 &= sizeMask;
         entry = &getEntry(hash1);
 
         if (entry->isFree())
-            return (adding && firstRemoved) ? *firstRemoved : *entry;
+            return (Adding == MaybeAdding::Adding && firstRemoved) ? *firstRemoved : *entry;
 
         shape = entry->shape();
         if (shape && shape->propidRaw() == id) {
             MOZ_ASSERT(collisionFlag);
             return *entry;
         }
 
-        if (entry->isRemoved()) {
-            if (!firstRemoved)
-                firstRemoved = entry;
-        } else {
-            if (adding && !entry->hadCollision())
-                entry->flagCollision();
+        if (Adding == MaybeAdding::Adding) {
+            if (entry->isRemoved()) {
+                if (!firstRemoved)
+                    firstRemoved = entry;
+            } else {
+                if (!entry->hadCollision())
+                    entry->flagCollision();
+            }
+        }
+
 #ifdef DEBUG
+        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);
+
 bool
 ShapeTable::change(int log2Delta, ExclusiveContext* cx)
 {
     MOZ_ASSERT(entries_);
     MOZ_ASSERT(-1 <= log2Delta && log2Delta <= 1);
 
     /*
      * Grow, shrink, or compress by changing this->entries_.
@@ -279,17 +288,17 @@ ShapeTable::change(int log2Delta, Exclus
     hashShift_ = HASH_BITS - newLog2;
     removedCount_ = 0;
     Entry* oldTable = entries_;
     entries_ = newTable;
 
     /* Copy only live entries, leaving removed and free ones behind. */
     for (Entry* oldEntry = oldTable; oldSize != 0; oldEntry++) {
         if (Shape* shape = oldEntry->shape()) {
-            Entry& entry = search(shape->propid(), true);
+            Entry& entry = search<MaybeAdding::Adding>(shape->propid());
             MOZ_ASSERT(entry.isFree());
             entry.setShape(shape);
         }
         oldSize--;
     }
 
     MOZ_ASSERT(capacity() == newSize);
 
@@ -488,17 +497,17 @@ NativeObject::addProperty(ExclusiveConte
     if (!extensible) {
         if (cx->isJSContext())
             obj->reportNotExtensible(cx->asJSContext());
         return nullptr;
     }
 
     ShapeTable::Entry* entry = nullptr;
     if (obj->inDictionaryMode())
-        entry = &obj->lastProperty()->table().search(id, true);
+        entry = &obj->lastProperty()->table().search<MaybeAdding::Adding>(id);
 
     return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags, entry,
                                allowDictionary);
 }
 
 static bool
 ShouldConvertToDictionary(NativeObject* obj)
 {
@@ -538,24 +547,24 @@ NativeObject::addPropertyInternal(Exclus
             (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(id, true);
+            entry = &table->search<MaybeAdding::Adding>(id);
         }
     } else {
         table = &obj->lastProperty()->table();
         if (table->needsToGrow()) {
             if (!table->grow(cx))
                 return nullptr;
-            entry = &table->search(id, true);
+            entry = &table->search<MaybeAdding::Adding>(id);
             MOZ_ASSERT(!entry->shape());
         }
     }
 
     MOZ_ASSERT(!!table == !!entry);
 
     /* Find or create a property tree node labeled by our arguments. */
     RootedShape shape(cx);
@@ -706,17 +715,17 @@ 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.
      */
     ShapeTable::Entry* entry;
-    RootedShape shape(cx, Shape::search(cx, obj->lastProperty(), id, &entry, true));
+    RootedShape shape(cx, Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, &entry));
     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))
@@ -770,17 +779,17 @@ 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(shape->propid(), false);
+        entry = &obj->lastProperty()->table().search<MaybeAdding::NotAdding>(shape->propid());
         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
@@ -918,17 +927,17 @@ NativeObject::removeProperty(ExclusiveCo
 
     /*
      * 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(shape->propid(), false);
+        entry = &self->lastProperty()->table().search<MaybeAdding::NotAdding>(shape->propid());
         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
@@ -1101,17 +1110,17 @@ NativeObject::replaceWithNewEquivalentSh
         new (newShape) Shape(oldRoot->base()->unowned(), 0);
         self = selfRoot;
         oldShape = oldRoot;
     }
 
     ShapeTable& table = self->lastProperty()->table();
     ShapeTable::Entry* entry = oldShape->isEmptyShape()
                                ? nullptr
-                               : &table.search(oldShape->propidRef(), false);
+                               : &table.search<MaybeAdding::NotAdding>(oldShape->propidRef());
 
     /*
      * 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);
 
--- a/js/src/vm/Shape.h
+++ b/js/src/vm/Shape.h
@@ -116,16 +116,18 @@ class TenuringTracer;
 typedef JSGetterOp GetterOp;
 typedef JSSetterOp SetterOp;
 typedef JSPropertyDescriptor PropertyDescriptor;
 
 /* 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 };
+
 /*
  * Shapes use multiplicative hashing, but specialized to
  * minimize footprint.
  */
 class ShapeTable {
   public:
     friend class NativeObject;
     static const uint32_t MIN_ENTRIES   = 11;
@@ -218,17 +220,19 @@ class ShapeTable {
 
     /*
      * NB: init and change are fallible but do not report OOM, so callers can
      * cope or ignore. They do however use the context's calloc method in
      * order to update the malloc counter on success.
      */
     bool init(ExclusiveContext* cx, Shape* lastProp);
     bool change(int log2Delta, ExclusiveContext* cx);
-    Entry& search(jsid id, bool adding);
+
+    template<MaybeAdding Adding>
+    Entry& search(jsid id);
 
   private:
     Entry& getEntry(uint32_t i) const {
         MOZ_ASSERT(i < capacity());
         return entries_[i];
     }
     void decEntryCount() {
         MOZ_ASSERT(entryCount_ > 0);
@@ -575,18 +579,19 @@ class Shape : public gc::TenuredCell
         KidsPointer kids;       /* null, single child, or a tagged ptr
                                    to many-kids data structure */
         HeapPtrShape* 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, bool adding = false);
+                                ShapeTable::Entry** pentry);
     static inline Shape* searchNoHashify(Shape* start, jsid id);
 
     void removeFromDictionary(NativeObject* obj);
     void insertIntoDictionary(HeapPtrShape* dictp);
 
     inline void initDictionaryShape(const StackShape& child, uint32_t nfixed, HeapPtrShape* dictp);
 
     /* Replace the base shape of the last shape in a non-dictionary lineage with base. */
@@ -1376,17 +1381,17 @@ 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(id, false);
+        ShapeTable::Entry& entry = start->table().search<MaybeAdding::NotAdding>(id);
         return entry.shape();
     }
 
     return start->searchLinear(id);
 }
 
 inline bool
 Shape::matches(const StackShape& other) const