llvm
diff --git a/‎llvm/docs/ProgrammersManual.rst‎
Lines changed: 8 additions & 6 deletions b/‎llvm/docs/ProgrammersManual.rst‎
Lines changed: 8 additions & 6 deletions
diff --git a/‎llvm/include/llvm/ADT/StringMap.h‎
Lines changed: 107 additions & 51 deletions b/‎llvm/include/llvm/ADT/StringMap.h‎
Lines changed: 107 additions & 51 deletions
@@ -2384,12 +2384,14 @@ This container guarantees the "``(char*)(&Value+1)``" points to the key string
 for a value.
 
 The ``StringMap`` is very fast for several reasons: linear probing is very cache
-efficient for lookups, the hash value of strings in buckets is not recomputed
-when looking up an element, ``StringMap`` rarely has to touch the memory for
-unrelated objects when looking up a value (even when hash collisions happen),
-hash table growth does not recompute the hash values for strings already in the
-table, and each pair in the map is store in a single allocation (the string data
-is stored in the same allocation as the Value of a pair).
+efficient for lookups, bucket occupancy is tracked in a packed 1-bit-per-bucket
+array so probing tests a dense bit rather than loading the sparse bucket pointer,
+the hash value of strings in buckets is not recomputed when looking up an
+element, ``StringMap`` rarely has to touch the memory for unrelated objects when
+looking up a value (even when hash collisions happen), hash table growth does not
+recompute the hash values for strings already in the table, and each pair in the
+map is store in a single allocation (the string data is stored in the same
+allocation as the Value of a pair).
 
 ``StringMap`` also provides query methods that take byte ranges, so it only ever
 copies a string if a value is inserted into the table.
 
@@ -15,10 +15,13 @@
 #define LLVM_ADT_STRINGMAP_H
 
 #include "llvm/ADT/StringMapEntry.h"
+#include "llvm/ADT/bit.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/Support/AllocatorBase.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
+#include <cstdint>
+#include <cstring>
 #include <initializer_list>
 #include <iterator>
 #include <type_traits>
@@ -31,15 +34,40 @@ template <typename ValueTy> class StringMapKeyIterator;
 /// StringMapImpl - This is the base class of StringMap that is shared among
 /// all of its instantiations.
 class StringMapImpl {
+public:
+  // Occupancy is tracked in a packed 1-bit-per-bucket "used" array (uint32
+  // words), like DenseMap.  Probing and iteration test a dense bit rather than
+  // loading the sparse bucket pointer.
+  using UsedT = uint32_t;
+
+  // Number of used words backing NumBuckets buckets.
+  static constexpr unsigned usedWords(unsigned N) { return (N + 31) / 32; }
+  static bool isUsed(const UsedT *U, unsigned I) {
+    return (U[I >> 5] >> (I & 31)) & 1;
+  }
+  static void setUsed(UsedT *U, unsigned I) {
+    U[I >> 5] |= UsedT(1) << (I & 31);
+  }
+  static void unsetUsed(UsedT *U, unsigned I) {
+    U[I >> 5] &= ~(UsedT(1) << (I & 31));
+  }
+
 protected:
-  // Array of NumBuckets pointers to entries, null pointers are holes.
-  // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
-  // by an array of the actual hash values as unsigned integers.
+  // One allocation holds, in order: NumBuckets entry pointers (occupied slots
+  // only; empty slots are don't-care), NumBuckets parallel hash values, and the
+  // packed used-bit array recording which slots are occupied.
   StringMapEntryBase **TheTable = nullptr;
   unsigned NumBuckets = 0;
   unsigned NumItems = 0;
   unsigned ItemSize;
 
+  unsigned *getHashArray() const {
+    return reinterpret_cast<unsigned *>(TheTable + NumBuckets);
+  }
+  UsedT *getUsed() const {
+    return reinterpret_cast<UsedT *>(getHashArray() + NumBuckets);
+  }
+
 protected:
   explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {}
   StringMapImpl(StringMapImpl &&RHS)
@@ -55,10 +83,10 @@ class StringMapImpl {
   LLVM_ABI unsigned RehashTable(unsigned BucketNo = 0);
 
   /// LookupBucketFor - Look up the bucket that the specified string should end
-  /// up in.  If it already exists as a key in the map, the Item pointer for the
-  /// specified bucket will be non-null.  Otherwise, it will be null.  In either
-  /// case, the FullHashValue field of the bucket will be set to the hash value
-  /// of the string.
+  /// up in.  If it already exists as a key in the map, the bucket's used bit
+  /// will be set.  Otherwise the bucket is empty (used bit clear) and its
+  /// FullHashValue is set to the hash value of the string so the caller can
+  /// fill it in.
   unsigned LookupBucketFor(StringRef Key) {
     return LookupBucketFor(Key, hash(Key));
   }
@@ -86,10 +114,6 @@ class StringMapImpl {
   /// setup the map as empty.
   LLVM_ABI void init(unsigned Size);
 
-  iterator_range<StringMapEntryBase **> buckets() {
-    return make_range(TheTable, TheTable + NumBuckets);
-  }
-
 public:
   [[nodiscard]] unsigned getNumBuckets() const { return NumBuckets; }
   [[nodiscard]] unsigned getNumItems() const { return NumItems; }
@@ -150,21 +174,21 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
     if (RHS.empty())
       return;
 
-    // Allocate TheTable of the same size as RHS's TheTable, and set the
-    // sentinel appropriately (and NumBuckets).
+    // Allocate TheTable of the same size as RHS's TheTable (and NumBuckets).
     init(RHS.NumBuckets);
-    unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
-             *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
+    unsigned *HashTable = getHashArray(), *RHSHashTable = RHS.getHashArray();
+    UsedT *Used = getUsed();
+    const UsedT *RHSUsed = RHS.getUsed();
 
     NumItems = RHS.NumItems;
     // Copy the bucket layout verbatim.  Because RHS was built with linear
     // probing, preserving each entry's slot keeps the probe-sequence invariant
-    // intact without re-probing.
+    // intact without re-probing.  Empty slots stay don't-care.
+    std::memcpy(Used, RHSUsed, usedWords(NumBuckets) * sizeof(UsedT));
     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
-      StringMapEntryBase *Bucket = RHS.TheTable[I];
-      if (!Bucket)
+      if (!isUsed(Used, I))
         continue;
-
+      StringMapEntryBase *Bucket = RHS.TheTable[I];
       TheTable[I] = MapEntryTy::create(
           static_cast<MapEntryTy *>(Bucket)->getKey(), getAllocator(),
           static_cast<MapEntryTy *>(Bucket)->getValue());
@@ -183,11 +207,10 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
     // to default values.  This is a copy of clear(), but avoids unnecessary
     // work not required in the destructor.
     if (!empty()) {
-      for (StringMapEntryBase *Bucket : buckets()) {
-        if (Bucket) {
-          static_cast<MapEntryTy *>(Bucket)->Destroy(getAllocator());
-        }
-      }
+      const UsedT *Used = getUsed();
+      for (unsigned I = 0, E = NumBuckets; I != E; ++I)
+        if (isUsed(Used, I))
+          static_cast<MapEntryTy *>(TheTable[I])->Destroy(getAllocator());
     }
   }
 
@@ -201,13 +224,19 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
   using const_iterator = StringMapIterBase<ValueTy, true>;
   using iterator = StringMapIterBase<ValueTy, false>;
 
-  [[nodiscard]] iterator begin() { return iterator(TheTable, NumBuckets != 0); }
-  [[nodiscard]] iterator end() { return iterator(TheTable + NumBuckets); }
+  [[nodiscard]] iterator begin() {
+    return iterator(TheTable, TheTable, getUsed(), NumBuckets, NumBuckets != 0);
+  }
+  [[nodiscard]] iterator end() {
+    return iterator(TheTable + NumBuckets, TheTable, getUsed(), NumBuckets);
+  }
   [[nodiscard]] const_iterator begin() const {
-    return const_iterator(TheTable, NumBuckets != 0);
+    return const_iterator(TheTable, TheTable, getUsed(), NumBuckets,
+                          NumBuckets != 0);
   }
   [[nodiscard]] const_iterator end() const {
-    return const_iterator(TheTable + NumBuckets);
+    return const_iterator(TheTable + NumBuckets, TheTable, getUsed(),
+                          NumBuckets);
   }
 
   [[nodiscard]] iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
@@ -221,7 +250,7 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
     int Bucket = FindKey(Key, FullHashValue);
     if (Bucket == -1)
       return end();
-    return iterator(TheTable + Bucket);
+    return iterator(TheTable + Bucket, TheTable, getUsed(), NumBuckets);
   }
 
   [[nodiscard]] const_iterator find(StringRef Key) const {
@@ -233,7 +262,7 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
     int Bucket = FindKey(Key, FullHashValue);
     if (Bucket == -1)
       return end();
-    return const_iterator(TheTable + Bucket);
+    return const_iterator(TheTable + Bucket, TheTable, getUsed(), NumBuckets);
   }
 
   /// lookup - Return the entry for the specified key, or a default
@@ -301,11 +330,12 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
   /// insert it and return true.
   bool insert(MapEntryTy *KeyValue) {
     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
-    StringMapEntryBase *&Bucket = TheTable[BucketNo];
-    if (Bucket)
+    UsedT *Used = getUsed();
+    if (isUsed(Used, BucketNo))
       return false; // Already exists in map.
 
-    Bucket = KeyValue;
+    TheTable[BucketNo] = KeyValue;
+    setUsed(Used, BucketNo);
     ++NumItems;
     assert(NumItems <= NumBuckets);
 
@@ -366,32 +396,33 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
                                                   uint32_t FullHashValue,
                                                   ArgsTy &&...Args) {
     unsigned BucketNo = LookupBucketFor(Key, FullHashValue);
-    StringMapEntryBase *&Bucket = TheTable[BucketNo];
-    if (Bucket)
-      return {iterator(TheTable + BucketNo), false}; // Already exists in map.
+    UsedT *Used = getUsed();
+    if (isUsed(Used, BucketNo)) // Already exists in map.
+      return {iterator(TheTable + BucketNo, TheTable, Used, NumBuckets), false};
 
-    Bucket =
+    TheTable[BucketNo] =
         MapEntryTy::create(Key, getAllocator(), std::forward<ArgsTy>(Args)...);
+    setUsed(Used, BucketNo);
     ++NumItems;
     assert(NumItems <= NumBuckets);
 
     BucketNo = RehashTable(BucketNo);
-    return {iterator(TheTable + BucketNo), true};
+    return {iterator(TheTable + BucketNo, TheTable, getUsed(), NumBuckets),
+            true};
   }
 
   // clear - Empties out the StringMap
   void clear() {
     if (empty())
       return;
 
-    // Zap all values, resetting the keys back to non-present, which is safe
-    // because we're removing all elements.
-    for (StringMapEntryBase *&Bucket : buckets()) {
-      if (Bucket) {
-        static_cast<MapEntryTy *>(Bucket)->Destroy(getAllocator());
-      }
-      Bucket = nullptr;
-    }
+    // Destroy all values and clear the occupancy bits, marking every bucket
+    // non-present.
+    UsedT *Used = getUsed();
+    for (unsigned I = 0, E = NumBuckets; I != E; ++I)
+      if (isUsed(Used, I))
+        static_cast<MapEntryTy *>(TheTable[I])->Destroy(getAllocator());
+    std::memset(Used, 0, usedWords(NumBuckets) * sizeof(UsedT));
 
     NumItems = 0;
   }
@@ -416,7 +447,14 @@ class LLVM_ALLOCATORHOLDER_EMPTYBASE StringMap
 };
 
 template <typename ValueTy, bool IsConst> class StringMapIterBase {
+  using UsedT = StringMapImpl::UsedT;
+
   StringMapEntryBase **Ptr = nullptr;
+  // The bucket base and the parallel used array map the current bucket back to
+  // its index so AdvancePastEmptyBuckets can consult the occupancy bits.
+  StringMapEntryBase **Buckets = nullptr;
+  const UsedT *Used = nullptr;
+  unsigned NumBuckets = 0;
 
 public:
   using iterator_category = std::forward_iterator_tag;
@@ -428,8 +466,10 @@ template <typename ValueTy, bool IsConst> class StringMapIterBase {
 
   StringMapIterBase() = default;
 
-  explicit StringMapIterBase(StringMapEntryBase **Bucket, bool Advance = false)
-      : Ptr(Bucket) {
+  explicit StringMapIterBase(StringMapEntryBase **Bucket,
+                             StringMapEntryBase **Buckets, const UsedT *Used,
+                             unsigned NumBuckets, bool Advance = false)
+      : Ptr(Bucket), Buckets(Buckets), Used(Used), NumBuckets(NumBuckets) {
     if (Advance)
       AdvancePastEmptyBuckets();
   }
@@ -456,7 +496,7 @@ template <typename ValueTy, bool IsConst> class StringMapIterBase {
   template <bool ToConst,
             typename = typename std::enable_if<!IsConst && ToConst>::type>
   operator StringMapIterBase<ValueTy, ToConst>() const {
-    return StringMapIterBase<ValueTy, ToConst>(Ptr);
+    return StringMapIterBase<ValueTy, ToConst>(Ptr, Buckets, Used, NumBuckets);
   }
 
   friend bool operator==(const StringMapIterBase &LHS,
@@ -470,9 +510,25 @@ template <typename ValueTy, bool IsConst> class StringMapIterBase {
   }
 
 private:
+  // Advance Ptr to the next occupied bucket, scanning the used array a word (32
+  // buckets) at a time, or to the end if none remain.
   void AdvancePastEmptyBuckets() {
-    while (*Ptr == nullptr)
-      ++Ptr;
+    size_t I = Ptr - Buckets;
+    if (I >= NumBuckets) {
+      Ptr = Buckets + NumBuckets;
+      return;
+    }
+    const unsigned NW = StringMapImpl::usedWords(NumBuckets);
+    unsigned W = I >> 5;
+    UsedT Bits = Used[W] & (~UsedT(0) << (I & 31));
+    while (Bits == 0) {
+      if (++W == NW) {
+        Ptr = Buckets + NumBuckets;
+        return;
+      }
+      Bits = Used[W];
+    }
+    Ptr = Buckets + ((W << 5) + llvm::countr_zero(Bits));
   }
 };