commit ad8bec08c3bfc48c78203d44b8f4cc07d4e6ae80
parent 76504589695a5c6d65d581795076a0cd4977e34c
Author: Iain Ireland <iireland@mozilla.com>
Date: Thu, 27 Nov 2025 21:39:55 +0000
Bug 2000328: Implement MacroAssembler::lookupMFBT r=jandem
Differential Revision: https://phabricator.services.mozilla.com/D273671
Diffstat:
5 files changed, 175 insertions(+), 0 deletions(-)
diff --git a/js/src/gc/WeakMap.h b/js/src/gc/WeakMap.h
@@ -435,6 +435,9 @@ class WeakMap : public WeakMapBase {
static size_t offsetOfHashShift() {
return offsetof(WeakMap, map_) + UnbarrieredMap::offsetOfHashShift();
}
+ static size_t offsetOfTable() {
+ return offsetof(WeakMap, map_) + UnbarrieredMap::offsetOfTable();
+ }
protected:
inline void assertMapIsSameZoneWithValue(const BarrieredValue& v);
diff --git a/js/src/jit/MacroAssembler-inl.h b/js/src/jit/MacroAssembler-inl.h
@@ -1024,6 +1024,40 @@ void MacroAssembler::loadStringLength(Register str, Register dest) {
load32(Address(str, JSString::offsetOfLength()), dest);
}
+template <typename Table, typename Match>
+void MacroAssembler::lookupMFBT(Register hashTable, Register hashCode,
+ Register scratch, Register scratch2,
+ Register scratch3, Register scratch4,
+ Register scratch5, Label* missing,
+ Match match) {
+ // Inline implementation of |lookup| for mozilla::detail::HashTable
+
+ // Compute the primary hash address:
+ // HashNumber h1 = hash1(aKeyHash);
+ Register hash1 = scratch5;
+ computeHash1MFBT<Table>(hashTable, hashCode, hash1, scratch);
+
+ Label primaryCollision;
+ checkForMatchMFBT<Table>(hashTable, hash1, hashCode, scratch, scratch2,
+ missing, &primaryCollision);
+ match();
+ bind(&primaryCollision);
+
+ // Otherwise, we've had a collision. Double-hash.
+ Register hash2 = scratch4;
+ Register sizeMask = scratch3;
+ computeHash2MFBT<Table>(hashTable, hashCode, hash2, sizeMask, scratch);
+
+ Label loop;
+ bind(&loop);
+
+ applyDoubleHashMFBT(hash1, hash2, sizeMask);
+ checkForMatchMFBT<Table>(hashTable, hash1, hashCode, scratch, scratch2,
+ missing, &loop);
+ match();
+ jump(&loop);
+}
+
void MacroAssembler::assertStackAlignment(uint32_t alignment,
int32_t offset /* = 0 */) {
#ifdef DEBUG
diff --git a/js/src/jit/MacroAssembler.cpp b/js/src/jit/MacroAssembler.cpp
@@ -10561,6 +10561,109 @@ void MacroAssembler::applyDoubleHashMFBT(Register hash1, Register hash2,
and32(sizeMask, hash1);
}
+template <typename Table>
+void MacroAssembler::checkForMatchMFBT(Register hashTable, Register hashIndex,
+ Register hashCode, Register scratch,
+ Register scratch2, Label* missing,
+ Label* collision) {
+ // Helper for inline implementation of |mozilla::detail::HashTable::lookup|
+ // The following code is used twice in |lookup|:
+ //
+ // Slot slot = slotForIndex(h1);
+ // if (slot.isFree()) {
+ // <not found>
+ // }
+ // if (slot.matchHash(aKeyHash) && match(slot.get(), aLookup)) {
+ // <found>
+ // }
+ //
+ // To reduce register pressure, we do some inlining and reorder some
+ // intermediate computation. We inline the following functions:
+ //
+ // Slot slotForIndex(HashNumber aIndex) const {
+ // auto hashes = reinterpret_cast<HashNumber*>(mTable);
+ // auto entries = reinterpret_cast<Entry*>(&hashes[capacity()]);
+ // return Slot(&entries[aIndex], &hashes[aIndex]);
+ // }
+ //
+ // uint32_t rawCapacity() { return 1u << (kHashNumberBits - hashShift()); }
+ //
+ // bool isFree() const { return *mKeyHash == Entry::sFreeKey; }
+ //
+ // bool matchHash(HashNumber hn) {
+ // return (*mKeyHash & ~Entry::sCollisionBit) == hn;
+ // }
+ //
+ // Reordered, we implement:
+ //
+ // auto hashes = reinterpret_cast<HashNumber*>(mTable);
+ // HashNumber hashInTable = hashes[hashIndex];
+ // if (hashInTable == Entry::sFreeKey) {
+ // <jump to missing label>
+ // }
+ // if (hashInTable & ~CollisionBit != hashCode) {
+ // <jump to collision label>
+ // }
+ // auto entries = hashes[capacity()];
+ // Entry* entry = entries[hashIndex]
+ // <fall through to entry-specific match code>
+ const mozilla::HashNumber FreeKey = mozilla::detail::kHashTableFreeKey;
+ const mozilla::HashNumber CollisionBit =
+ mozilla::detail::kHashTableCollisionBit;
+
+ Address tableAddr(hashTable, Table::offsetOfTable());
+ Address hashShiftAddr(hashTable, Table::offsetOfHashShift());
+
+ // auto hashes = reinterpret_cast<HashNumber*>(mTable);
+ Register hashes = scratch;
+ loadPtr(tableAddr, scratch);
+
+ // HashNumber hashInTable = hashes[hashIndex];
+ Register hashInTable = scratch2;
+ static_assert(sizeof(HashNumber) == 4);
+ load32(BaseIndex(hashes, hashIndex, Scale::TimesFour), hashInTable);
+
+ // if (hashInTable == Entry::sFreeKey) {
+ // <jump to missing label>
+ // }
+ branch32(Assembler::Equal, hashInTable, Imm32(FreeKey), missing);
+
+ // if (hashInTable & ~CollisionBit != hashCode) {
+ // <jump to collision label>
+ // }
+ and32(Imm32(~CollisionBit), hashInTable);
+ branch32(Assembler::NotEqual, hashInTable, hashCode, collision);
+
+ // entries = hashes[capacity()]
+ // = hashes[1 << (kHashNumberBits - hashShift()]
+ // = &hashes + (1 << (kHashNumberBits - hashShift())) * sizeof(HashNumber)
+ // = &hashes + sizeof(HashNumber) << (kHashNumberBits - hashShift())
+ // = &hashes + sizeof(HashNumber) << (kHashNumberBits + -hashShift())
+ Register capacityOffset = scratch;
+ load8ZeroExtend(hashShiftAddr, scratch2);
+ neg32(scratch2);
+ add32(Imm32(kHashNumberBits), scratch2);
+ move32(Imm32(sizeof(mozilla::HashNumber)), capacityOffset);
+ flexibleLshift32(scratch2, capacityOffset);
+ Register entries = scratch2;
+ loadPtr(tableAddr, entries);
+ addPtr(capacityOffset, entries);
+
+ // Load entries[hashIndex] into |scratch|
+ // TODO: support non-power-of-2 entry sizes
+ constexpr size_t EntrySize = sizeof(typename Table::Entry);
+ static_assert(mozilla::IsPowerOfTwo(EntrySize));
+ uint32_t shift = mozilla::FloorLog2(EntrySize);
+ lshiftPtr(Imm32(shift), hashIndex, scratch);
+
+ computeEffectiveAddress(BaseIndex(entries, scratch, Scale::TimesOne),
+ scratch);
+}
+
+template void MacroAssembler::checkForMatchMFBT<WeakMapObject::Map>(
+ Register hashTable, Register hashIndex, Register hashCode, Register scratch,
+ Register scratch2, Label* missing, Label* collision);
+
// Can't push large frames blindly on windows, so we must touch frame memory
// incrementally, with no more than 4096 - 1 bytes between touches.
//
diff --git a/js/src/jit/MacroAssembler.h b/js/src/jit/MacroAssembler.h
@@ -5454,6 +5454,34 @@ class MacroAssembler : public MacroAssemblerSpecific {
void computeHash2MFBT(Register hashTable, Register hashCode, Register hash2,
Register sizeMask, Register scratch);
void applyDoubleHashMFBT(Register hash1, Register hash2, Register sizeMask);
+ template <typename Table>
+ void checkForMatchMFBT(Register hashTable, Register hashIndex,
+ Register hashCode, Register scratch, Register scratch2,
+ Label* missing, Label* collision);
+
+ public:
+ // This generates an inlined version of mozilla::detail::HashTable::lookup
+ // (ForNonAdd).
+ // Inputs/requirements:
+ // - hashTable: A register containing a pointer to a Table. The Table type
+ // must define:
+ // - Table::Entry
+ // - Table::offsetOfHashShift()
+ // - Table::offsetOfTable()
+ // - hashCode: The 32-bit hash of the key to look up. This should already
+ // have been scrambled using prepareHashMFBT.
+ // - match: A lambda to generate code to compare keys. The code that it
+ // generates can assume that `scratch` contains the address of
+ // a Table::Entry with a matching hash value. `scratch2` can be
+ // safely used without clobbering anything. If the keys don't
+ // match, the generated code should fall through. If the keys
+ // match, the generated code is responsible for jumping to the
+ // correct continuation.
+ // - missing: A label to jump to if the key does not exist in the table.
+ template <typename Table, typename Match>
+ void lookupMFBT(Register hashTable, Register hashCode, Register scratch,
+ Register scratch2, Register scratch3, Register scratch4,
+ Register scratch5, Label* missing, Match match);
private:
enum class IsBigInt { No, Yes, Maybe };
diff --git a/mfbt/HashTable.h b/mfbt/HashTable.h
@@ -429,6 +429,9 @@ class MOZ_STANDALONE_DEBUG HashMap {
static size_t offsetOfHashShift() {
return offsetof(HashMap, mImpl) + Impl::offsetOfHashShift();
}
+ static size_t offsetOfTable() {
+ return offsetof(HashMap, mImpl) + Impl::offsetOfTable();
+ }
};
//---------------------------------------------------------------------------
@@ -980,6 +983,9 @@ class HashMapEntry {
const Value& value() const { return value_; }
Value& value() { return value_; }
+ static size_t offsetOfKey() { return offsetof(HashMapEntry, key_); }
+ static size_t offsetOfValue() { return offsetof(HashMapEntry, value_); }
+
private:
HashMapEntry(const HashMapEntry&) = delete;
void operator=(const HashMapEntry&) = delete;
@@ -2352,6 +2358,7 @@ class MOZ_STANDALONE_DEBUG HashTable : private AllocPolicy {
return offsetof(HashTable, mGenAndHashShift);
#endif
}
+ static size_t offsetOfTable() { return offsetof(HashTable, mTable); }
};
} // namespace detail
