[sanitizer] Fix DenseMap for compiler-rt

Depends on D114047.

Differential Revision: https://reviews.llvm.org/D114048

6 files changed, 254 insertions, 260 deletions

diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
index 9320a834ef7a..4c7ca62ad0c9 100644
--- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
@@ -131,6 +131,8 @@ set(SANITIZER_IMPL_HEADERS
   sanitizer_dbghelp.h
   sanitizer_deadlock_detector.h
   sanitizer_deadlock_detector_interface.h
+  sanitizer_dense_map.h
+  sanitizer_dense_map_info.h
   sanitizer_errno.h
   sanitizer_errno_codes.h
   sanitizer_file.h
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
index 08f0f6b94ea0..3fa6af76ce29 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
@@ -6,7 +6,10 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This is fork of llvm/ADT/DenseMap.h class.
+// This is fork of llvm/ADT/DenseMap.h class with the following changes:
+//  * Use mmap to allocate.
+//  * No iterators.
+//  * Does not shrink.
 //
 //===----------------------------------------------------------------------===//
 
@@ -16,68 +19,36 @@
 #include "sanitizer_common.h"
 #include "sanitizer_dense_map_info.h"
 #include "sanitizer_internal_defs.h"
+#include "sanitizer_type_traits.h"
 
 namespace __sanitizer {
-namespace detail {
-
-// We extend a pair to allow users to override the bucket type with their own
-// implementation without requiring two members.
-template <typename KeyT, typename ValueT>
-struct DenseMapPair : public std::pair<KeyT, ValueT> {
-  using std::pair<KeyT, ValueT>::pair;
-
-  KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
-  const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
-  ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
-  const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
-};
-
-}  // end namespace detail
-
-template <typename KeyT, typename ValueT,
-          typename KeyInfoT = DenseMapInfo<KeyT>,
-          typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
-          bool IsConst = false>
-class DenseMapIterator;
 
 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
           typename BucketT>
-class DenseMapBase : public DebugEpochBase {
-  template <typename T>
-  using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
-
+class DenseMapBase {
  public:
   using size_type = unsigned;
   using key_type = KeyT;
   using mapped_type = ValueT;
   using value_type = BucketT;
 
-  LLVM_NODISCARD bool empty() const { return getNumEntries() == 0; }
+  WARN_UNUSED_RESULT bool empty() const { return getNumEntries() == 0; }
   unsigned size() const { return getNumEntries(); }
 
   /// Grow the densemap so that it can contain at least \p NumEntries items
   /// before resizing again.
   void reserve(size_type NumEntries) {
     auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
-    incrementEpoch();
     if (NumBuckets > getNumBuckets())
       grow(NumBuckets);
   }
 
   void clear() {
-    incrementEpoch();
     if (getNumEntries() == 0 && getNumTombstones() == 0)
       return;
 
-    // If the capacity of the array is huge, and the # elements used is small,
-    // shrink the array.
-    if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
-      shrink_and_clear();
-      return;
-    }
-
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
-    if (std::is_trivially_destructible<ValueT>::value) {
+    if (__sanitizer::is_trivially_destructible<ValueT>::value) {
       // Use a simpler loop when values don't need destruction.
       for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
         P->getFirst() = EmptyKey;
@@ -92,35 +63,29 @@ class DenseMapBase : public DebugEpochBase {
           P->getFirst() = EmptyKey;
         }
       }
-      assert(NumEntries == 0 && "Node count imbalance!");
+      CHECK_EQ(NumEntries, 0);
     }
     setNumEntries(0);
     setNumTombstones(0);
   }
 
   /// Return 1 if the specified key is in the map, 0 otherwise.
-  size_type count(const_arg_type_t<KeyT> Val) const {
+  size_type count(const KeyT &Key) const {
     const BucketT *TheBucket;
-    return LookupBucketFor(Val, TheBucket) ? 1 : 0;
+    return LookupBucketFor(Key, TheBucket) ? 1 : 0;
   }
 
-  iterator find(const_arg_type_t<KeyT> Val) {
+  value_type *find(const KeyT &Key) {
     BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
-  const_iterator find(const_arg_type_t<KeyT> Val) const {
+  const value_type *find(const KeyT &Key) const {
     const BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeConstIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
 
   /// Alternate version of find() which allows a different, and possibly
@@ -129,31 +94,25 @@ class DenseMapBase : public DebugEpochBase {
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
   /// type used.
   template <class LookupKeyT>
-  iterator find_as(const LookupKeyT &Val) {
+  value_type *find_as(const LookupKeyT &Key) {
     BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
   template <class LookupKeyT>
-  const_iterator find_as(const LookupKeyT &Val) const {
+  const value_type *find_as(const LookupKeyT &Key) const {
     const BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
-      return makeConstIterator(
-          TheBucket,
-          shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(), *this,
-          true);
-    return end();
+    if (LookupBucketFor(Key, TheBucket))
+      return TheBucket;
+    return nullptr;
   }
 
   /// lookup - Return the entry for the specified key, or a default
   /// constructed value if no such entry exists.
-  ValueT lookup(const_arg_type_t<KeyT> Val) const {
+  ValueT lookup(const KeyT &Key) const {
     const BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
+    if (LookupBucketFor(Key, TheBucket))
       return TheBucket->getSecond();
     return ValueT();
   }
@@ -161,64 +120,48 @@ class DenseMapBase : public DebugEpochBase {
   // Inserts key,value pair into the map if the key isn't already in the map.
   // If the key is already in the map, it returns false and doesn't update the
   // value.
-  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
+  detail::DenseMapPair<value_type *, bool> insert(const value_type &KV) {
     return try_emplace(KV.first, KV.second);
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // If the key is already in the map, it returns false and doesn't update the
   // value.
-  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
-    return try_emplace(std::move(KV.first), std::move(KV.second));
+  detail::DenseMapPair<value_type *, bool> insert(value_type &&KV) {
+    return try_emplace(__sanitizer::move(KV.first),
+                       __sanitizer::move(KV.second));
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // The value is constructed in-place if the key is not in the map, otherwise
   // it is not moved.
   template <typename... Ts>
-  std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&...Args) {
+  detail::DenseMapPair<value_type *, bool> try_emplace(KeyT &&Key,
+                                                       Ts &&...Args) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
-      return std::make_pair(
-          makeIterator(
-              TheBucket,
-              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-              *this, true),
-          false);  // Already in map.
+      return {TheBucket, false};  // Already in map.
 
     // Otherwise, insert the new element.
-    TheBucket =
-        InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
-    return std::make_pair(
-        makeIterator(
-            TheBucket,
-            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-            *this, true),
-        true);
+    TheBucket = InsertIntoBucket(TheBucket, __sanitizer::move(Key),
+                                 __sanitizer::forward<Ts>(Args)...);
+    return {TheBucket, true};
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // The value is constructed in-place if the key is not in the map, otherwise
   // it is not moved.
   template <typename... Ts>
-  std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&...Args) {
+  detail::DenseMapPair<value_type *, bool> try_emplace(const KeyT &Key,
+                                                       Ts &&...Args) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
-      return std::make_pair(
-          makeIterator(
-              TheBucket,
-              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-              *this, true),
-          false);  // Already in map.
+      return {TheBucket, false};  // Already in map.
 
     // Otherwise, insert the new element.
-    TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
-    return std::make_pair(
-        makeIterator(
-            TheBucket,
-            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-            *this, true),
-        true);
+    TheBucket =
+        InsertIntoBucket(TheBucket, Key, __sanitizer::forward<Ts>(Args)...);
+    return {TheBucket, true};
   }
 
   /// Alternate version of insert() which allows a different, and possibly
@@ -227,32 +170,17 @@ class DenseMapBase : public DebugEpochBase {
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
   /// type used.
   template <typename LookupKeyT>
-  std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
-                                      const LookupKeyT &Val) {
+  detail::DenseMapPair<value_type *, bool> insert_as(value_type &&KV,
+                                                     const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return std::make_pair(
-          makeIterator(
-              TheBucket,
-              shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-              *this, true),
-          false);  // Already in map.
+      return {TheBucket, false};  // Already in map.
 
     // Otherwise, insert the new element.
-    TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
-                                           std::move(KV.second), Val);
-    return std::make_pair(
-        makeIterator(
-            TheBucket,
-            shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),
-            *this, true),
-        true);
-  }
-
-  /// insert - Range insertion of pairs.
-  template <typename InputIt>
-  void insert(InputIt I, InputIt E) {
-    for (; I != E; ++I) insert(*I);
+    TheBucket =
+        InsertIntoBucketWithLookup(TheBucket, __sanitizer::move(KV.first),
+                                   __sanitizer::move(KV.second), Val);
+    return {TheBucket, true};
   }
 
   bool erase(const KeyT &Val) {
@@ -266,7 +194,9 @@ class DenseMapBase : public DebugEpochBase {
     incrementNumTombstones();
     return true;
   }
-  void erase(iterator I) {
+
+  void erase(value_type *I) {
+    CHECK_NE(I, nullptr);
     BucketT *TheBucket = &*I;
     TheBucket->getSecond().~ValueT();
     TheBucket->getFirst() = getTombstoneKey();
@@ -289,11 +219,35 @@ class DenseMapBase : public DebugEpochBase {
     if (LookupBucketFor(Key, TheBucket))
       return *TheBucket;
 
-    return *InsertIntoBucket(TheBucket, std::move(Key));
+    return *InsertIntoBucket(TheBucket, __sanitizer::move(Key));
   }
 
   ValueT &operator[](KeyT &&Key) {
-    return FindAndConstruct(std::move(Key)).second;
+    return FindAndConstruct(__sanitizer::move(Key)).second;
+  }
+
+  /// Equality comparison for DenseMap.
+  ///
+  /// Iterates over elements of LHS confirming that each (key, value) pair in
+  /// LHS is also in RHS, and that no additional pairs are in RHS. Equivalent to
+  /// N calls to RHS.find and N value comparisons. Amortized complexity is
+  /// linear, worst case is O(N^2) (if every hash collides).
+  bool operator==(const DenseMapBase &RHS) const {
+    if (size() != RHS.size())
+      return false;
+
+    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+    for (auto *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
+      const KeyT K = P->getFirst();
+      if (!KeyInfoT::isEqual(K, EmptyKey) &&
+          !KeyInfoT::isEqual(K, TombstoneKey)) {
+        const auto *I = RHS.find(K);
+        if (!I || P->getSecond() != I->getSecond())
+          return false;
+      }
+    }
+
+    return true;
   }
 
  protected:
@@ -316,8 +270,7 @@ class DenseMapBase : public DebugEpochBase {
     setNumEntries(0);
     setNumTombstones(0);
 
-    assert((getNumBuckets() & (getNumBuckets() - 1)) == 0 &&
-           "# initial buckets must be a power of two!");
+    CHECK_EQ((getNumBuckets() & (getNumBuckets() - 1)), 0);
     const KeyT EmptyKey = getEmptyKey();
     for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
       ::new (&B->getFirst()) KeyT(EmptyKey);
@@ -331,7 +284,7 @@ class DenseMapBase : public DebugEpochBase {
       return 0;
     // +1 is required because of the strict equality.
     // For example if NumEntries is 48, we need to return 401.
-    return NextPowerOf2(NumEntries * 4 / 3 + 1);
+    return RoundUpToPowerOfTwo((NumEntries * 4 / 3 + 1) + /* NextPowerOf2 */ 1);
   }
 
   void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
@@ -347,9 +300,10 @@ class DenseMapBase : public DebugEpochBase {
         BucketT *DestBucket;
         bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
         (void)FoundVal;  // silence warning.
-        assert(!FoundVal && "Key already in new map?");
-        DestBucket->getFirst() = std::move(B->getFirst());
-        ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
+        CHECK(!FoundVal);
+        DestBucket->getFirst() = __sanitizer::move(B->getFirst());
+        ::new (&DestBucket->getSecond())
+            ValueT(__sanitizer::move(B->getSecond()));
         incrementNumEntries();
 
         // Free the value.
@@ -362,18 +316,18 @@ class DenseMapBase : public DebugEpochBase {
   template <typename OtherBaseT>
   void copyFrom(
       const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
-    assert(&other != this);
-    assert(getNumBuckets() == other.getNumBuckets());
+    CHECK_NE(&other, this);
+    CHECK_EQ(getNumBuckets(), other.getNumBuckets());
 
     setNumEntries(other.getNumEntries());
     setNumTombstones(other.getNumTombstones());
 
-    if (std::is_trivially_copyable<KeyT>::value &&
-        std::is_trivially_copyable<ValueT>::value)
-      memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
-             getNumBuckets() * sizeof(BucketT));
+    if (__sanitizer::is_trivially_copyable<KeyT>::value &&
+        __sanitizer::is_trivially_copyable<ValueT>::value)
+      internal_memcpy(reinterpret_cast<void *>(getBuckets()),
+                      other.getBuckets(), getNumBuckets() * sizeof(BucketT));
     else
-      for (size_t i = 0; i < getNumBuckets(); ++i) {
+      for (uptr i = 0; i < getNumBuckets(); ++i) {
         ::new (&getBuckets()[i].getFirst())
             KeyT(other.getBuckets()[i].getFirst());
         if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
@@ -392,11 +346,7 @@ class DenseMapBase : public DebugEpochBase {
     return KeyInfoT::getHashValue(Val);
   }
 
-  static const KeyT getEmptyKey() {
-    static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
-                  "Must pass the derived type to this template!");
-    return KeyInfoT::getEmptyKey();
-  }
+  static const KeyT getEmptyKey() { return KeyInfoT::getEmptyKey(); }
 
   static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); }
 
@@ -448,8 +398,9 @@ class DenseMapBase : public DebugEpochBase {
                             ValueArgs &&...Values) {
     TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
 
-    TheBucket->getFirst() = std::forward<KeyArg>(Key);
-    ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
+    TheBucket->getFirst() = __sanitizer::forward<KeyArg>(Key);
+    ::new (&TheBucket->getSecond())
+        ValueT(__sanitizer::forward<ValueArgs>(Values)...);
     return TheBucket;
   }
 
@@ -458,8 +409,8 @@ class DenseMapBase : public DebugEpochBase {
                                       ValueT &&Value, LookupKeyT &Lookup) {
     TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
 
-    TheBucket->getFirst() = std::move(Key);
-    ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
+    TheBucket->getFirst() = __sanitizer::move(Key);
+    ::new (&TheBucket->getSecond()) ValueT(__sanitizer::move(Value));
     return TheBucket;
   }
 
@@ -477,17 +428,16 @@ class DenseMapBase : public DebugEpochBase {
     // causing infinite loops in lookup.
     unsigned NewNumEntries = getNumEntries() + 1;
     unsigned NumBuckets = getNumBuckets();
-    if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
+    if (UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
       this->grow(NumBuckets * 2);
       LookupBucketFor(Lookup, TheBucket);
       NumBuckets = getNumBuckets();
-    } else if (LLVM_UNLIKELY(NumBuckets -
-                                 (NewNumEntries + getNumTombstones()) <=
-                             NumBuckets / 8)) {
+    } else if (UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <=
+                        NumBuckets / 8)) {
       this->grow(NumBuckets);
       LookupBucketFor(Lookup, TheBucket);
     }
-    assert(TheBucket);
+    CHECK(TheBucket);
 
     // Only update the state after we've grown our bucket space appropriately
     // so that when growing buckets we have self-consistent entry count.
@@ -520,23 +470,22 @@ class DenseMapBase : public DebugEpochBase {
     const BucketT *FoundTombstone = nullptr;
     const KeyT EmptyKey = getEmptyKey();
     const KeyT TombstoneKey = getTombstoneKey();
-    assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
-           !KeyInfoT::isEqual(Val, TombstoneKey) &&
-           "Empty/Tombstone value shouldn't be inserted into map!");
+    CHECK(!KeyInfoT::isEqual(Val, EmptyKey));
+    CHECK(!KeyInfoT::isEqual(Val, TombstoneKey));
 
     unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1);
     unsigned ProbeAmt = 1;
     while (true) {
       const BucketT *ThisBucket = BucketsPtr + BucketNo;
       // Found Val's bucket?  If so, return it.
-      if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
+      if (LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
         FoundBucket = ThisBucket;
         return true;
       }
 
       // If we found an empty bucket, the key doesn't exist in the set.
       // Insert it and return the default value.
-      if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
+      if (LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
         // If we've already seen a tombstone while probing, fill it in instead
         // of the empty bucket we eventually probed to.
         FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
@@ -570,7 +519,9 @@ class DenseMapBase : public DebugEpochBase {
   /// This is just the raw memory used by DenseMap.
   /// If entries are pointers to objects, the size of the referenced objects
   /// are not included.
-  size_t getMemorySize() const { return getNumBuckets() * sizeof(BucketT); }
+  uptr getMemorySize() const {
+    return RoundUpTo(getNumBuckets() * sizeof(BucketT), GetPageSizeCached());
+  }
 };
 
 /// Inequality comparison for DenseMap.
@@ -586,7 +537,7 @@ bool operator!=(
 
 template <typename KeyT, typename ValueT,
           typename KeyInfoT = DenseMapInfo<KeyT>,
-          typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
+          typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
 class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                                      KeyT, ValueT, KeyInfoT, BucketT> {
   friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
@@ -595,15 +546,16 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
   // simplicity of referring to them.
   using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
 
-  BucketT *Buckets;
-  unsigned NumEntries;
-  unsigned NumTombstones;
-  unsigned NumBuckets;
+  BucketT *Buckets = nullptr;
+  unsigned NumEntries = 0;
+  unsigned NumTombstones = 0;
+  unsigned NumBuckets = 0;
 
  public:
   /// Create a DenseMap with an optional \p InitialReserve that guarantee that
   /// this number of elements can be inserted in the map without grow()
-  explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
+  explicit DenseMap(unsigned InitialReserve) { init(InitialReserve); }
+  constexpr DenseMap() = default;
 
   DenseMap(const DenseMap &other) : BaseT() {
     init(0);
@@ -615,29 +567,16 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
     swap(other);
   }
 
-  template <typename InputIt>
-  DenseMap(const InputIt &I, const InputIt &E) {
-    init(std::distance(I, E));
-    this->insert(I, E);
-  }
-
-  DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
-    init(Vals.size());
-    this->insert(Vals.begin(), Vals.end());
-  }
-
   ~DenseMap() {
     this->destroyAll();
-    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
+    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
   }
 
   void swap(DenseMap &RHS) {
-    this->incrementEpoch();
-    RHS.incrementEpoch();
-    std::swap(Buckets, RHS.Buckets);
-    std::swap(NumEntries, RHS.NumEntries);
-    std::swap(NumTombstones, RHS.NumTombstones);
-    std::swap(NumBuckets, RHS.NumBuckets);
+    Swap(Buckets, RHS.Buckets);
+    Swap(NumEntries, RHS.NumEntries);
+    Swap(NumTombstones, RHS.NumTombstones);
+    Swap(NumBuckets, RHS.NumBuckets);
   }
 
   DenseMap &operator=(const DenseMap &other) {
@@ -656,7 +595,7 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
 
   void copyFrom(const DenseMap &other) {
     this->destroyAll();
-    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
+    deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
     if (allocateBuckets(other.NumBuckets)) {
       this->BaseT::copyFrom(other);
     } else {
@@ -679,9 +618,8 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
     unsigned OldNumBuckets = NumBuckets;
     BucketT *OldBuckets = Buckets;
 
-    allocateBuckets(std::max<unsigned>(
-        64, static_cast<unsigned>(NextPowerOf2(AtLeast - 1))));
-    assert(Buckets);
+    allocateBuckets(RoundUpToPowerOfTwo(Max<unsigned>(64, AtLeast)));
+    CHECK(Buckets);
     if (!OldBuckets) {
       this->BaseT::initEmpty();
       return;
@@ -690,8 +628,7 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
     this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets);
 
     // Free the old table.
-    deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets,
-                      alignof(BucketT));
+    deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets);
   }
 
  private:
@@ -714,10 +651,26 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
       return false;
     }
 
-    Buckets = static_cast<BucketT *>(
-        allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT)));
+    uptr Size = sizeof(BucketT) * NumBuckets;
+    if (Size * 2 <= GetPageSizeCached()) {
+      // We always allocate at least a page, so use entire space.
+      unsigned Log2 = MostSignificantSetBitIndex(GetPageSizeCached() / Size);
+      Size <<= Log2;
+      NumBuckets <<= Log2;
+      CHECK_EQ(Size, sizeof(BucketT) * NumBuckets);
+      CHECK_GT(Size * 2, GetPageSizeCached());
+    }
+    Buckets = static_cast<BucketT *>(allocate_buffer(Size));
     return true;
   }
+
+  static void *allocate_buffer(uptr Size) {
+    return MmapOrDie(RoundUpTo(Size, GetPageSizeCached()), "DenseMap");
+  }
+
+  static void deallocate_buffer(void *Ptr, uptr Size) {
+    UnmapOrDie(Ptr, RoundUpTo(Size, GetPageSizeCached()));
+  }
 };
 
 }  // namespace __sanitizer
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h
index 7e525d038519..85c6427906c1 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h
@@ -9,7 +9,9 @@
 #ifndef SANITIZER_DENSE_MAP_INFO_H
 #define SANITIZER_DENSE_MAP_INFO_H
 
+#include "sanitizer_common.h"
 #include "sanitizer_internal_defs.h"
+#include "sanitizer_type_traits.h"
 
 namespace __sanitizer {
 
@@ -17,7 +19,7 @@ namespace detail {
 
 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
 static inline unsigned combineHashValue(unsigned a, unsigned b) {
-  uint64_t key = (uint64_t)a << 32 | (uint64_t)b;
+  u64 key = (u64)a << 32 | (u64)b;
   key += ~(key << 32);
   key ^= (key >> 22);
   key += ~(key << 13);
@@ -29,6 +31,31 @@ static inline unsigned combineHashValue(unsigned a, unsigned b) {
   return (unsigned)key;
 }
 
+// We extend a pair to allow users to override the bucket type with their own
+// implementation without requiring two members.
+template <typename KeyT, typename ValueT>
+struct DenseMapPair {
+  KeyT first = {};
+  ValueT second = {};
+  DenseMapPair() = default;
+  DenseMapPair(const KeyT &f, const ValueT &s) : first(f), second(s) {}
+
+  template <typename KeyT2, typename ValueT2>
+  DenseMapPair(KeyT2 &&f, ValueT2 &&s)
+      : first(__sanitizer::forward<KeyT2>(f)),
+        second(__sanitizer::forward<ValueT2>(s)) {}
+
+  DenseMapPair(const DenseMapPair &other) = default;
+  DenseMapPair &operator=(const DenseMapPair &other) = default;
+  DenseMapPair(DenseMapPair &&other) = default;
+  DenseMapPair &operator=(DenseMapPair &&other) = default;
+
+  KeyT &getFirst() { return first; }
+  const KeyT &getFirst() const { return first; }
+  ValueT &getSecond() { return second; }
+  const ValueT &getSecond() const { return second; }
+};
+
 }  // end namespace detail
 
 template <typename T>
@@ -50,23 +77,22 @@ struct DenseMapInfo<T *> {
   // static_assert(alignof(T) <= (1 << Log2MaxAlign),
   //               "DenseMap does not support pointer keys requiring more than "
   //               "Log2MaxAlign bits of alignment");
-  static constexpr uintptr_t Log2MaxAlign = 12;
+  static constexpr uptr Log2MaxAlign = 12;
 
   static inline T *getEmptyKey() {
-    uintptr_t Val = static_cast<uintptr_t>(-1);
+    uptr Val = static_cast<uptr>(-1);
     Val <<= Log2MaxAlign;
     return reinterpret_cast<T *>(Val);
   }
 
   static inline T *getTombstoneKey() {
-    uintptr_t Val = static_cast<uintptr_t>(-2);
+    uptr Val = static_cast<uptr>(-2);
     Val <<= Log2MaxAlign;
     return reinterpret_cast<T *>(Val);
   }
 
   static unsigned getHashValue(const T *PtrVal) {
-    return (unsigned((uintptr_t)PtrVal) >> 4) ^
-           (unsigned((uintptr_t)PtrVal) >> 9);
+    return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9);
   }
 
   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
@@ -203,18 +229,19 @@ struct DenseMapInfo<long long> {
 
 // Provide DenseMapInfo for all pairs whose members have info.
 template <typename T, typename U>
-struct DenseMapInfo<std::pair<T, U>> {
-  using Pair = std::pair<T, U>;
+struct DenseMapInfo<detail::DenseMapPair<T, U>> {
+  using Pair = detail::DenseMapPair<T, U>;
   using FirstInfo = DenseMapInfo<T>;
   using SecondInfo = DenseMapInfo<U>;
 
   static inline Pair getEmptyKey() {
-    return std::make_pair(FirstInfo::getEmptyKey(), SecondInfo::getEmptyKey());
+    return detail::DenseMapPair<T, U>(FirstInfo::getEmptyKey(),
+                                      SecondInfo::getEmptyKey());
   }
 
   static inline Pair getTombstoneKey() {
-    return std::make_pair(FirstInfo::getTombstoneKey(),
-                          SecondInfo::getTombstoneKey());
+    return detail::DenseMapPair<T, U>(FirstInfo::getTombstoneKey(),
+                                      SecondInfo::getTombstoneKey());
   }
 
   static unsigned getHashValue(const Pair &PairVal) {
diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
index d689d60d06f2..570da2670b53 100644
--- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
@@ -17,6 +17,7 @@ set(SANITIZER_UNITTESTS
   sanitizer_chained_origin_depot_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
+  sanitizer_dense_map_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_flat_map_test.cpp
   sanitizer_format_interceptor_test.cpp
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp
index 7dc79f5d6b5b..c4cf746f35bf 100644
--- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp
@@ -18,6 +18,29 @@ using namespace __sanitizer;
 
 namespace {
 
+// Helps to keep some tests.
+template <typename KeyT, typename ValueT,
+          typename KeyInfoT = DenseMapInfo<KeyT>>
+class TestDenseMap : public DenseMap<KeyT, ValueT, KeyInfoT> {
+  using BaseT = DenseMap<KeyT, ValueT, KeyInfoT>;
+
+ public:
+  using BaseT::BaseT;
+
+  TestDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
+      : BaseT(Vals.size()) {
+    for (const auto &V : Vals) this->BaseT::insert(V);
+  }
+
+  template <typename I>
+  TestDenseMap(I B, I E) : BaseT(std::distance(B, E)) {
+    for (; B != E; ++B) this->BaseT::insert(*B);
+  }
+};
+
+template <typename... T>
+using DenseMap = TestDenseMap<T...>;
+
 uint32_t getTestKey(int i, uint32_t *) { return i; }
 uint32_t getTestValue(int i, uint32_t *) { return 42 + i; }
 
@@ -98,11 +121,9 @@ template <typename T>
 typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr;
 
 // Register these types for testing.
-typedef ::testing::Types<
-    DenseMap<uint32_t, uint32_t>, DenseMap<uint32_t *, uint32_t *>,
-    DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>,
-    SmallDenseMap<uint32_t, uint32_t>, SmallDenseMap<uint32_t *, uint32_t *>,
-    SmallDenseMap<CtorTester, CtorTester, 4, CtorTesterMapInfo>>
+typedef ::testing::Types<DenseMap<uint32_t, uint32_t>,
+                         DenseMap<uint32_t *, uint32_t *>,
+                         DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>>
     DenseMapTestTypes;
 TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, );
 
@@ -112,12 +133,9 @@ TYPED_TEST(DenseMapTest, EmptyIntMapTest) {
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
 
-  // Iterator tests
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
-
   // Lookup tests
   EXPECT_FALSE(this->Map.count(this->getKey()));
-  EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end());
+  EXPECT_EQ(nullptr, this->Map.find(this->getKey()));
   EXPECT_EQ(typename TypeParam::mapped_type(),
             this->Map.lookup(this->getKey()));
 }
@@ -127,7 +145,6 @@ TYPED_TEST(DenseMapTest, ConstEmptyMapTest) {
   const TypeParam &ConstMap = this->Map;
   EXPECT_EQ(0u, ConstMap.size());
   EXPECT_TRUE(ConstMap.empty());
-  EXPECT_TRUE(ConstMap.begin() == ConstMap.end());
 }
 
 // A map with a single entry
@@ -136,19 +153,11 @@ TYPED_TEST(DenseMapTest, SingleEntryMapTest) {
 
   // Size tests
   EXPECT_EQ(1u, this->Map.size());
-  EXPECT_FALSE(this->Map.begin() == this->Map.end());
   EXPECT_FALSE(this->Map.empty());
 
-  // Iterator tests
-  typename TypeParam::iterator it = this->Map.begin();
-  EXPECT_EQ(this->getKey(), it->first);
-  EXPECT_EQ(this->getValue(), it->second);
-  ++it;
-  EXPECT_TRUE(it == this->Map.end());
-
   // Lookup tests
   EXPECT_TRUE(this->Map.count(this->getKey()));
-  EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin());
+  EXPECT_NE(nullptr, this->Map.find(this->getKey()));
   EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey()));
   EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);
 }
@@ -160,17 +169,15 @@ TYPED_TEST(DenseMapTest, ClearTest) {
 
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
 }
 
 // Test erase(iterator) method
 TYPED_TEST(DenseMapTest, EraseTest) {
   this->Map[this->getKey()] = this->getValue();
-  this->Map.erase(this->Map.begin());
+  this->Map.erase(this->Map.find(this->getKey()));
 
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
 }
 
 // Test erase(value) method
@@ -180,12 +187,12 @@ TYPED_TEST(DenseMapTest, EraseTest2) {
 
   EXPECT_EQ(0u, this->Map.size());
   EXPECT_TRUE(this->Map.empty());
-  EXPECT_TRUE(this->Map.begin() == this->Map.end());
 }
 
 // Test insert() method
 TYPED_TEST(DenseMapTest, InsertTest) {
-  this->Map.insert(std::make_pair(this->getKey(), this->getValue()));
+  this->Map.insert(
+      typename TypeParam::value_type(this->getKey(), this->getValue()));
   EXPECT_EQ(1u, this->Map.size());
   EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);
 }
@@ -339,7 +346,7 @@ TEST(DenseMapCustomTest, EqualityComparison) {
 TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {
   // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and
   // ReserveTest as well!
-  const int ExpectedInitialBucketCount = 64;
+  const int ExpectedInitialBucketCount = 512;
   // Formula from DenseMap::getMinBucketToReserveForEntries()
   const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1;
 
@@ -349,10 +356,11 @@ TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {
   unsigned MemorySize = Map.getMemorySize();
   CountCopyAndMove::Copy = 0;
   CountCopyAndMove::Move = 0;
-  for (int i = 0; i < ExpectedMaxInitialEntries; ++i)
-    Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,
-                                                std::forward_as_tuple(i),
-                                                std::forward_as_tuple()));
+  for (int i = 0; i < ExpectedMaxInitialEntries; ++i) {
+    detail::DenseMapPair<int, CountCopyAndMove> KV;
+    KV.first = i;
+    Map.insert(move(KV));
+  }
   // Check that we didn't grow
   EXPECT_EQ(MemorySize, Map.getMemorySize());
   // Check that move was called the expected number of times
@@ -361,10 +369,9 @@ TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {
   EXPECT_EQ(0, CountCopyAndMove::Copy);
 
   // Adding one extra element should grow the map
-  Map.insert(std::pair<int, CountCopyAndMove>(
-      std::piecewise_construct,
-      std::forward_as_tuple(ExpectedMaxInitialEntries),
-      std::forward_as_tuple()));
+  detail::DenseMapPair<int, CountCopyAndMove> KV;
+  KV.first = ExpectedMaxInitialEntries;
+  Map.insert(move(KV));
   // Check that we grew
   EXPECT_NE(MemorySize, Map.getMemorySize());
   // Check that move was called the expected number of times
@@ -377,20 +384,21 @@ TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {
 // Make sure creating the map with an initial size of N actually gives us enough
 // buckets to insert N items without increasing allocation size.
 TEST(DenseMapCustomTest, InitialSizeTest) {
-  // Test a few different sizes, 48 is *not* a random choice: we need a value
+  // Test a few different size, 341 is *not* a random choice: we need a value
   // that is 2/3 of a power of two to stress the grow() condition, and the power
-  // of two has to be at least 64 because of minimum size allocation in the
-  // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the
-  // 64 default init.
-  for (auto Size : {1, 2, 48, 66}) {
+  // of two has to be at least 512 because of minimum size allocation in the
+  // DenseMap (see DefaultMinReservedSizeTest). 513 is a value just above the
+  // 512 default init.
+  for (auto Size : {1, 2, 48, 66, 341, 513}) {
     DenseMap<int, CountCopyAndMove> Map(Size);
     unsigned MemorySize = Map.getMemorySize();
     CountCopyAndMove::Copy = 0;
     CountCopyAndMove::Move = 0;
-    for (int i = 0; i < Size; ++i)
-      Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,
-                                                  std::forward_as_tuple(i),
-                                                  std::forward_as_tuple()));
+    for (int i = 0; i < Size; ++i) {
+      detail::DenseMapPair<int, CountCopyAndMove> KV;
+      KV.first = i;
+      Map.insert(move(KV));
+    }
     // Check that we didn't grow
     EXPECT_EQ(MemorySize, Map.getMemorySize());
     // Check that move was called the expected number of times
@@ -402,7 +410,7 @@ TEST(DenseMapCustomTest, InitialSizeTest) {
 
 // Make sure creating the map with a iterator range does not trigger grow()
 TEST(DenseMapCustomTest, InitFromIterator) {
-  std::vector<std::pair<int, CountCopyAndMove>> Values;
+  std::vector<detail::DenseMapPair<int, CountCopyAndMove>> Values;
   // The size is a random value greater than 64 (hardcoded DenseMap min init)
   const int Count = 65;
   for (int i = 0; i < Count; i++) Values.emplace_back(i, CountCopyAndMove());
@@ -419,21 +427,22 @@ TEST(DenseMapCustomTest, InitFromIterator) {
 // Make sure reserve actually gives us enough buckets to insert N items
 // without increasing allocation size.
 TEST(DenseMapCustomTest, ReserveTest) {
-  // Test a few different size, 48 is *not* a random choice: we need a value
+  // Test a few different size, 341 is *not* a random choice: we need a value
   // that is 2/3 of a power of two to stress the grow() condition, and the power
-  // of two has to be at least 64 because of minimum size allocation in the
-  // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the
-  // 64 default init.
-  for (auto Size : {1, 2, 48, 66}) {
+  // of two has to be at least 512 because of minimum size allocation in the
+  // DenseMap (see DefaultMinReservedSizeTest). 513 is a value just above the
+  // 512 default init.
+  for (auto Size : {1, 2, 48, 66, 341, 513}) {
     DenseMap<int, CountCopyAndMove> Map;
     Map.reserve(Size);
     unsigned MemorySize = Map.getMemorySize();
     CountCopyAndMove::Copy = 0;
     CountCopyAndMove::Move = 0;
-    for (int i = 0; i < Size; ++i)
-      Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,
-                                                  std::forward_as_tuple(i),
-                                                  std::forward_as_tuple()));
+    for (int i = 0; i < Size; ++i) {
+      detail::DenseMapPair<int, CountCopyAndMove> KV;
+      KV.first = i;
+      Map.insert(move(KV));
+    }
     // Check that we didn't grow
     EXPECT_EQ(MemorySize, Map.getMemorySize());
     // Check that move was called the expected number of times
@@ -475,13 +484,13 @@ TEST(DenseMapCustomTest, FindAsTest) {
   EXPECT_EQ(1u, map.find(0)->second);
   EXPECT_EQ(2u, map.find(1)->second);
   EXPECT_EQ(3u, map.find(2)->second);
-  EXPECT_TRUE(map.find(3) == map.end());
+  EXPECT_EQ(nullptr, map.find(3));
 
   // find_as() tests
   EXPECT_EQ(1u, map.find_as("a")->second);
   EXPECT_EQ(2u, map.find_as("b")->second);
   EXPECT_EQ(3u, map.find_as("c")->second);
-  EXPECT_TRUE(map.find_as("d") == map.end());
+  EXPECT_EQ(nullptr, map.find_as("d"));
 }
 
 TEST(DenseMapCustomTest, TryEmplaceTest) {
@@ -514,8 +523,8 @@ TEST(DenseMapCustomTest, OpaquePointerKey) {
   EXPECT_EQ(Map[K2], 2);
   EXPECT_EQ(Map[K3], 3);
   Map.clear();
-  EXPECT_EQ(Map.find(K1), Map.end());
-  EXPECT_EQ(Map.find(K2), Map.end());
-  EXPECT_EQ(Map.find(K3), Map.end());
+  EXPECT_EQ(nullptr, Map.find(K1));
+  EXPECT_EQ(nullptr, Map.find(K2));
+  EXPECT_EQ(nullptr, Map.find(K3));
 }
 }  // namespace
diff --git a/llvm/utils/gn/secondary/compiler-rt/lib/sanitizer_common/BUILD.gn b/llvm/utils/gn/secondary/compiler-rt/lib/sanitizer_common/BUILD.gn
index 8f5315e48661..6d1b48132ebe 100644
--- a/llvm/utils/gn/secondary/compiler-rt/lib/sanitizer_common/BUILD.gn
+++ b/llvm/utils/gn/secondary/compiler-rt/lib/sanitizer_common/BUILD.gn
@@ -51,6 +51,8 @@ source_set("sources") {
     "sanitizer_deadlock_detector1.cpp",
     "sanitizer_deadlock_detector2.cpp",
     "sanitizer_deadlock_detector_interface.h",
+    "sanitizer_dense_map.h",
+    "sanitizer_dense_map_info.h",
     "sanitizer_errno.cpp",
     "sanitizer_errno.h",
     "sanitizer_errno_codes.h",