[DenseMap] Derive the used array instead of caching a pointer

MaskRay · MaskRay · commit f4ed01d68dfa · 2026-06-03T18:19:25.000-07:00
The used array trails the bucket array in the shared allocation, so getUsed()
computes Buckets + sizeof(BucketT)*NumBuckets instead of caching a pointer,
dropping a word from every DenseMap (sizeof 24 -&gt; 16 for a pointer key/value).
The offset is aligned because NumBuckets is a power of two &gt;= 64, asserted in
allocateBuckets.

Lookups are unaffected (the derived pointer folds away); insert costs a few
extra instructions.
diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h
@@ -838,7 +838,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
   using UsedT = llvm::densemap::detail::UsedT;
 
   BucketT *Buckets = nullptr;
-  UsedT *Used = nullptr;
   unsigned NumEntries = 0;
   unsigned NumBuckets = 0;
 
@@ -891,7 +890,6 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
 private:
   void swapImpl(DenseMap &RHS) {
     std::swap(Buckets, RHS.Buckets);
-    std::swap(Used, RHS.Used);
     std::swap(NumEntries, RHS.NumEntries);
     std::swap(NumBuckets, RHS.NumBuckets);
   }
@@ -902,9 +900,14 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
 
   BucketT *getBuckets() const { return Buckets; }
 
-  typename BaseT::Rep getRep() const { return {Buckets, Used, NumBuckets}; }
+  typename BaseT::Rep getRep() const {
+    return {Buckets, getUsed(), NumBuckets};
+  }
 
-  UsedT *getUsed() const { return Used; }
+  UsedT *getUsed() const {
+    return reinterpret_cast<UsedT *>(reinterpret_cast<char *>(Buckets) +
+                                     sizeof(BucketT) * NumBuckets);
+  }
 
   unsigned getNumBuckets() const { return NumBuckets; }
 
@@ -915,23 +918,20 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                       llvm::densemap::detail::allocBytes<BucketT>(NumBuckets),
                       llvm::densemap::detail::allocAlign<BucketT>());
     Buckets = nullptr;
-    Used = nullptr;
     NumBuckets = 0;
   }
 
   bool allocateBuckets(unsigned Num) {
     NumBuckets = Num;
     if (NumBuckets == 0) {
       Buckets = nullptr;
-      Used = nullptr;
       return false;
     }
-
-    auto *Storage = static_cast<char *>(
+    assert(sizeof(BucketT) * NumBuckets % alignof(UsedT) == 0 &&
+           "used array would be misaligned");
+    Buckets = reinterpret_cast<BucketT *>(
         allocate_buffer(llvm::densemap::detail::allocBytes<BucketT>(NumBuckets),
                         llvm::densemap::detail::allocAlign<BucketT>()));
-    Buckets = reinterpret_cast<BucketT *>(Storage);
-    Used = reinterpret_cast<UsedT *>(Storage + sizeof(BucketT) * NumBuckets);
     return true;
   }
 
