Bug 1543159 - TypeHashSet should use a non-reserved bit for marking elements to be moved. r=jandem
authorNicolas B. Pierron <nicolas.b.pierron@nbp.name>
Tue, 16 Apr 2019 18:45:45 +0000
changeset 469858 6b754628d15922d6f564ea222fbb0d90135e25a9
parent 469857 a0eb669e2d77cd005c0da54375f8994f9e353c91
child 469859 bc25508285184d50fb58523c0c83a6fdf9b96ad7
push id35883
push userbtara@mozilla.com
push dateWed, 17 Apr 2019 21:47:29 +0000
treeherdermozilla-central@02b89c29412b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs1543159
milestone68.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 1543159 - TypeHashSet should use a non-reserved bit for marking elements to be moved. r=jandem Differential Revision: https://phabricator.services.mozilla.com/D26961
js/src/vm/TypeInference-inl.h
js/src/vm/TypeSet.h
--- a/js/src/vm/TypeInference-inl.h
+++ b/js/src/vm/TypeInference-inl.h
@@ -988,81 +988,86 @@ struct TypeHashSet {
   template <class T, class U, class Key, typename Fun>
   static void MapEntries(U**& values, unsigned count, Fun f) {
     // No element.
     if (count == 0) {
       MOZ_RELEASE_ASSERT(!values);
       return;
     }
 
+    // Simple functions to read and mutate the mark bit of pointers.
+    auto markBit = [](U* elem) -> bool {
+      return bool(reinterpret_cast<uintptr_t>(elem) & U::TypeHashSetMarkBit);
+    };
+    auto toggleMarkBit = [](U* elem) -> U* {
+      return reinterpret_cast<U*>(
+          reinterpret_cast<uintptr_t>(elem) ^ U::TypeHashSetMarkBit);
+    };
+
     // When we have a single element it is stored in-place of the function
     // array pointer.
     if (count == 1) {
-      values = reinterpret_cast<U**>(f(reinterpret_cast<U*>(values)));
+      U* elem = f(reinterpret_cast<U*>(values));
+      MOZ_ASSERT(!markBit(elem));
+      values = reinterpret_cast<U**>(elem);
       return;
     }
 
     // When we have SET_ARRAY_SIZE or fewer elements, the values is an
     // unorderred array.
     if (count <= SET_ARRAY_SIZE) {
       for (unsigned i = 0; i < count; i++) {
-        values[i] = f(values[i]);
+        U* elem = f(values[i]);
+        MOZ_ASSERT(!markBit(elem));
+        values[i] = elem;
       }
       return;
     }
 
-    // Simple functions to read and mutate the lowest bit of pointers.
-    auto lowBit = [](U* elem) -> bool {
-      return bool(reinterpret_cast<uintptr_t>(elem) & 1);
-    };
-    auto toggleLowBit = [](U* elem) -> U* {
-      return reinterpret_cast<U*>(reinterpret_cast<uintptr_t>(elem) ^ 1);
-    };
-
     // This code applies the function f and relocates the values based on
     // the new pointers.
     //
     // To avoid allocations, we reuse the same structure but distinguish the
     // elements to be rellocated from the rellocated elements with the
-    // lowest bit.
+    // mark bit.
     unsigned capacity = Capacity(count);
     MOZ_RELEASE_ASSERT(uintptr_t(values[-1]) == capacity);
     unsigned found = 0;
     for (unsigned i = 0; i < capacity; i++) {
       if (!values[i]) {
         continue;
       }
       MOZ_ASSERT(found <= count);
       U* elem = f(values[i]);
       values[i] = nullptr;
-      MOZ_ASSERT(!lowBit(elem));
-      values[found++] = toggleLowBit(elem);
+      MOZ_ASSERT(!markBit(elem));
+      values[found++] = toggleMarkBit(elem);
     }
     MOZ_ASSERT(found == count);
 
-    // Follow the same rule as InsertTry, except that for each cell we
-    // identify empty cell content with:
+    // Follow the same rule as InsertTry, except that for each cell we identify
+    // empty cell content with either a nullptr or the value of the mark bit:
     //
     //   nullptr    empty cell.
-    //   0b....0    inserted element.
-    //   0b....1    empty cell - element to be inserted.
+    //   0b...0.    inserted element.
+    //   0b...1.    empty cell - element to be inserted.
     unsigned mask = capacity - 1;
     for (unsigned i = 0; i < count; i++) {
       U* elem = values[i];
-      if (!lowBit(elem)) {
+      if (!markBit(elem)) {
         // If this is a newly inserted element, this implies that one of
         // the previous objects was moved to this position.
         continue;
       }
       values[i] = nullptr;
       while (elem) {
-        MOZ_ASSERT(lowBit(elem));
-        elem = toggleLowBit(elem);
+        MOZ_ASSERT(markBit(elem));
+        elem = toggleMarkBit(elem);
         unsigned pos = HashKey<T, Key>(Key::getKey(elem)) & mask;
-        while (values[pos] != nullptr && !lowBit(values[pos])) {
+        while (values[pos] != nullptr && !markBit(values[pos])) {
           pos = (pos + 1) & mask;
         }
         // The replaced element is either a nullptr, which stops this
         // loop, or an element to be inserted, which would be inserted
         // by this loop.
         std::swap(values[pos], elem);
       }
     }
--- a/js/src/vm/TypeSet.h
+++ b/js/src/vm/TypeSet.h
@@ -284,16 +284,17 @@ class TypeSet {
     static intptr_t keyBits(ObjectKey* obj) { return (intptr_t)obj; }
     static ObjectKey* getKey(ObjectKey* obj) { return obj; }
 
     static inline ObjectKey* get(JSObject* obj);
     static inline ObjectKey* get(ObjectGroup* group);
 
     bool isGroup() { return (uintptr_t(this) & 1) == 0; }
     bool isSingleton() { return (uintptr_t(this) & 1) != 0; }
+    static constexpr uintptr_t TypeHashSetMarkBit = 1 << 1;
 
     inline ObjectGroup* group();
     inline JSObject* singleton();
 
     inline ObjectGroup* groupNoBarrier();
     inline JSObject* singletonNoBarrier();
 
     const Class* clasp();