diff --git a/llvm/include/llvm/ADT/ConcurrentHashtable.h b/llvm/include/llvm/ADT/ConcurrentHashtable.h
new file mode 100644
--- /dev/null
+++ b/llvm/include/llvm/ADT/ConcurrentHashtable.h
@@ -0,0 +1,879 @@
+//===- ConcurrentHashtable.h ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_CONCURRENTHASHTABLE_H
+#define LLVM_ADT_CONCURRENTHASHTABLE_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Parallel.h"
+#include "llvm/Support/WithColor.h"
+#include <atomic>
+#include <cstddef>
+#include <iomanip>
+#include <mutex>
+#include <sstream>
+#include <type_traits>
+
+namespace llvm {
+
+/// ConcurrentHashTable - is a resizeable concurrent hashtable.
+/// The range of resizings without noticable performance degradations
+/// is up to x100000. The hashtable allows only concurrent insertions.
+
+/// Data structure:
+///
+/// Value -> [------- 64-bit Hash value --------]
+///          [ ** ][ ChainIndex ][ Bucket Index ]
+///            |         |             |
+///         possibly   points to     points to
+///         unused     the bucket    the bucket.
+///                    chains.
+///
+/// After initialization, all buckets consist of one chain(not inititalized
+/// at start). During insertions, buckets might be extended to contain more
+/// chains. The number of chains kept by bucket is called bucket width. The
+/// maximal bucket width is 32768. Each bucket can be independently resized
+/// and rehashed(no need to lock the whole table).
+///
+/// HashTables keeps chains of all buckets: HashTables[ChainIdx][BucketIdx]
+///
+/// Each chain keeps a list of array of entries:
+///
+/// ChainHead->[ entry1    ] keeps entry data
+///            [ entry2    ]
+///            [ ...       ]
+///            [ last entry]
+///            [ next chain item] -> points to the next chain item
+///
+/// Pointer to the first bucket chain also keeps the width of the bucket.
+/// i.e. HashTables[0][BucketIdx] keeps both: pointer to the first chain
+/// and the width of the bucket BucketIdx.
+///
+/// ConcurrentHashTable: each entry keeps KeyDataTy in place or null.
+///
+/// ConcurrentHashTableExternalAlloc: each entry keeps a pair: hash value
+/// and the pointer to the KeyDataTy or null.
+
+template <typename KeyDataTy> struct HashedEntry {
+  uint64_t Hash;
+  KeyDataTy *Data = nullptr;
+};
+
+template <typename KeyDataTy, bool KeepDataInsideTable>
+class ConcurrentHashTableConstants {
+public:
+  static size_t constexpr MaxBucketWidthNum = 32768;
+  static size_t constexpr GrowthRate = 1;
+  static size_t constexpr ChainItemSize =
+      128 * sizeof(typename std::conditional<KeepDataInsideTable, uint8_t,
+                                             uint32_t>::type);
+  static size_t constexpr MapEntrySize =
+      sizeof(typename std::conditional<KeepDataInsideTable, KeyDataTy,
+                                       HashedEntry<KeyDataTy>>::type);
+  static size_t constexpr EntriesPerChainItem =
+      (ChainItemSize - sizeof(uintptr_t)) / MapEntrySize;
+  static size_t constexpr MutexesInitialSize = 256;
+};
+
+template <typename KeyTy, typename KeyDataTy, typename AllocatorTy,
+          bool KeepDataInsideTable, typename Info,
+          typename Constants =
+              ConcurrentHashTableConstants<KeyDataTy, KeepDataInsideTable>>
+class ConcurrentHashTableBase {
+public:
+  static_assert((Constants::MaxBucketWidthNum >= 1) &
+                    !(Constants::MaxBucketWidthNum &
+                      (Constants::MaxBucketWidthNum - 1)),
+                "MaxBucketWidthNum must be a power of two.");
+  static_assert((Constants::MaxBucketWidthNum <= 32768),
+                "MaxBucketWidthNum must not be greater than 32768.");
+  static_assert((Constants::GrowthRate > 0),
+                "GrowthRate must be greater than 0.");
+  static_assert((Constants::GrowthRate < 16),
+                "GrowthRate must not be greater than 16.");
+  static_assert((Constants::MutexesInitialSize > 0),
+                "MutexesInitialSize must be greater than 0.");
+
+  using MapEntryTy = typename std::conditional<KeepDataInsideTable, KeyDataTy,
+                                               HashedEntry<KeyDataTy>>::type;
+  using InsertionTy =
+      typename std::conditional<KeepDataInsideTable, KeyDataTy, KeyTy>::type;
+
+  using InsertionResultTy =
+      typename std::conditional<KeepDataInsideTable, KeyDataTy,
+                                KeyDataTy *>::type;
+
+  ConcurrentHashTableBase(
+      size_t EstimatedSize, AllocatorTy &Allocator,
+      size_t ThreadsNum = parallel::strategy.compute_thread_count())
+      : Allocator(Allocator) {
+    assert(ThreadsNum > 0);
+
+    // Calculate hashtable size.
+    HashTableSize = EstimatedSize / Constants::EntriesPerChainItem;
+    HashTableSize = NextPowerOf2(HashTableSize);
+    HashTableSize = std::max(HashTableSize, (size_t)2);
+    NumberOfHashTables = 0;
+
+    // Allocate first hashtable.
+    memset(&HashTables, 0, sizeof(HashTables));
+    allocateNewHashTables(1);
+
+    // Calculate number of mutexes.
+    BucketMutexesNum = NextPowerOf2(Constants::MutexesInitialSize * ThreadsNum);
+    BucketMutexesNum = std::min(BucketMutexesNum, HashTableSize);
+
+    // Allocate mutexes.
+    BucketMutexes = Allocator.template Allocate<std::mutex>(BucketMutexesNum);
+    for (size_t Idx = 0; Idx < BucketMutexesNum; Idx++)
+      new (&BucketMutexes[Idx]) std::mutex();
+
+    // Calculate masks.
+    size_t LeadingZerosNumber = countLeadingZeros(getHashMask());
+    HashBitsNum = sizeof(hash_code) * UINT8_WIDTH - LeadingZerosNumber;
+    MaxBucketWidth = std::min(Constants::MaxBucketWidthNum,
+                              (size_t)(1 << LeadingZerosNumber));
+
+    ExtHashMask = ((HashTableSize * MaxBucketWidth) - 1) & ~getHashMask();
+  }
+
+  /// Insert new value \p NewValue or return already existing entry.
+  ///
+  /// \returns entry and "true" if an entry is just inserted or
+  /// "false" if an entry already exists.
+  std::pair<InsertionResultTy, bool> insert(const InsertionTy &NewValue,
+                                            AllocatorTy &ThreadLocalAllocator) {
+    // Calculate bucket index.
+    hash_code Hash = getHashCode(NewValue);
+    size_t BucketIdx = Hash & getHashMask();
+    size_t ExtHashBits = getExtHashBits(Hash);
+    MapEntryTy DataToInsert;
+
+    ValueInserter<InsertionResultTy> Handler(NewValue, ThreadLocalAllocator,
+                                             getBucketMutex(BucketIdx), Hash);
+    HashTableEntry &ZeroEntryRef = HashTables[0][BucketIdx];
+
+    // Lock bucket.
+    Handler.BucketMutex.lock();
+
+    while (true) {
+      // Get chain head.
+      ChainItem *ChainHead = ZeroEntryRef;
+      ExtBitsEntry ExtEntry = ExtBitsEntry::getFromOpaqueValue(ChainHead);
+      uint8_t BucketWidthValue = getBucketWidthValue(ExtEntry);
+      size_t BucketWidth = getBucketWidthFromValue(BucketWidthValue);
+      size_t ChainIdx = ExtHashBits & (BucketWidth - 1);
+      if (ChainIdx == 0) {
+        ChainHead = ExtEntry.getPointer();
+        if (ChainHead == nullptr) {
+          ChainHead = allocateItem(ThreadLocalAllocator);
+          ExtEntry.setPointer(ChainHead);
+          ZeroEntryRef = static_cast<ChainItem *>(ExtEntry.getOpaqueValue());
+        }
+      } else {
+        HashTableEntry &EntryRef = HashTables[ChainIdx][BucketIdx];
+        ChainHead = EntryRef;
+
+        if (ChainHead == nullptr) {
+          ChainHead = allocateItem(ThreadLocalAllocator);
+          EntryRef = ChainHead;
+        }
+      }
+
+      // For each chain entry...
+      if (forEachChainEntry<CreateNewChainItems,
+                            ValueInserter<InsertionResultTy>>(
+              BucketIdx, BucketWidth, ChainHead, Handler, ThreadLocalAllocator))
+        break;
+    }
+
+    return Handler.Result;
+  }
+
+  /// Print information about current state of hash table structures.
+  void printStatistic(raw_ostream &OS) {
+    OS << "\n--- HashTable statistic:\n";
+    OS << "\nTable Size = " << HashTableSize;
+    OS << "\nNumber of tables = " << NumberOfHashTables;
+    OS << "\nEntries per chain item = " << (int)Constants::EntriesPerChainItem;
+    OS << "\nNumber of mutexes = " << (int)BucketMutexesNum;
+
+    uint64_t NumberOfBuckets = 0;
+    uint64_t LongestChainLength = 0;
+    uint64_t NumberOfEntries = 0;
+    uint64_t NumberOfEntriesPlusEmpty = 0;
+    uint64_t OverallSize =
+        sizeof(*this) + HashTableSize * NumberOfHashTables * sizeof(MapEntryTy);
+
+    class ChainLengthCounter {
+    public:
+      IterationStatus handleEntry(MapEntryTy &EntryData) {
+        if (!ConcurrentHashTableBase::isNull(EntryData))
+          ChainLength++;
+
+        return IterationStatus::Next;
+      }
+      uint64_t ChainLength = 0;
+    };
+    DenseMap<size_t, size_t> BucketWidthsMap;
+
+    // For each bucket...
+    for (uint64_t CurBucketIdx = 0; CurBucketIdx < HashTableSize;
+         CurBucketIdx++) {
+
+      NumberOfEntriesPlusEmpty +=
+          Constants::EntriesPerChainItem * NumberOfHashTables;
+
+      if (isEmptyBucket(CurBucketIdx))
+        continue;
+
+      NumberOfBuckets++;
+
+      size_t BucketWidth =
+          getBucketWidthFromValue(getBucketWidthValue(CurBucketIdx));
+      BucketWidthsMap[BucketWidth] = BucketWidthsMap.lookup(BucketWidth) + 1;
+
+      // For each chain...
+      for (size_t CurChainIdx = 0; CurChainIdx < BucketWidth; CurChainIdx++) {
+
+        ChainItem *ChainHead =
+            getChainHead<DoNotCreateChainHead>(CurBucketIdx, CurChainIdx);
+        if (ChainHead == nullptr)
+          continue;
+
+        ChainLengthCounter Handler;
+
+        // For each chain entry...
+        [[maybe_unused]] bool ForEachSuccessful =
+            forEachChainEntry<DoNotCreateNewChainItems, ChainLengthCounter>(
+                CurBucketIdx, BucketWidth, ChainHead, Handler);
+        assert(ForEachSuccessful);
+
+        LongestChainLength = std::max(LongestChainLength, Handler.ChainLength);
+        NumberOfEntries += Handler.ChainLength;
+
+        size_t ItemsInChain =
+            (Handler.ChainLength / Constants::EntriesPerChainItem) +
+            ((Handler.ChainLength % Constants::EntriesPerChainItem) > 0 ? 1
+                                                                        : 0);
+        assert(ItemsInChain > 0);
+
+        NumberOfEntriesPlusEmpty +=
+            Constants::EntriesPerChainItem * (ItemsInChain - 1);
+        OverallSize += sizeof(ChainItem) * ItemsInChain;
+        if constexpr (std::is_pointer<MapEntryTy>::value)
+          OverallSize += sizeof(KeyDataTy);
+      }
+    }
+
+    OS << "\nOverall number of entries = " << NumberOfEntries;
+    OS << "\nOverall number of buckets = " << NumberOfBuckets;
+    for (auto &Width : BucketWidthsMap)
+      OS << "\n Number of buckets with width " << Width.first << ": "
+         << Width.second;
+    OS << "\nLongest chain length = " << LongestChainLength;
+
+    std::stringstream stream;
+    stream << std::fixed << std::setprecision(2)
+           << ((float)NumberOfEntries / (float)NumberOfEntriesPlusEmpty);
+    std::string str = stream.str();
+
+    OS << "\nLoad factor = " << str;
+    OS << "\nOverall allocated size = " << OverallSize;
+  }
+
+protected:
+  enum IterationStatus : uint8_t { Stop, Next };
+
+  struct alignas(16) ChainItem {
+    ChainItem() = delete;
+    ChainItem(const ChainItem &) = delete;
+    ChainItem &operator=(const ChainItem &) = delete;
+
+    MapEntryTy Entries[Constants::EntriesPerChainItem];
+    ChainItem *Next;
+  };
+
+  static constexpr bool CreateChainHead = true;
+  static constexpr bool DoNotCreateChainHead = false;
+
+  static constexpr bool CreateNewChainItems = true;
+  static constexpr bool DoNotCreateNewChainItems = false;
+
+  using HashTableEntry = ChainItem *;
+  using HashTablePtr = HashTableEntry *;
+  using ExtBitsEntry = PointerIntPair<ChainItem *, 4, uint8_t>;
+
+  bool isEmptyBucket(size_t BucketIdx) {
+    return ExtBitsEntry::getFromOpaqueValue(HashTables[0][BucketIdx])
+               .getPointer() == nullptr;
+  }
+
+  uint8_t getBucketWidthValue(size_t BucketIdx) {
+    return ExtBitsEntry::getFromOpaqueValue(HashTables[0][BucketIdx]).getInt();
+  }
+
+  uint8_t getBucketWidthValue(ChainItem *Head) {
+    return getBucketWidthValue(ExtBitsEntry::getFromOpaqueValue(Head));
+  }
+
+  uint8_t getBucketWidthValue(ExtBitsEntry ExtEntry) {
+    return ExtEntry.getInt();
+  }
+
+  size_t getBucketWidthFromValue(uint8_t BucketWidthValue) {
+    return 1 << (BucketWidthValue);
+  }
+
+  void setBucketWidth(size_t BucketIdx, size_t NewBucketWidth) {
+    assert((NewBucketWidth >= 1) & !(NewBucketWidth & (NewBucketWidth - 1)));
+    assert(getBucketWidthFromValue(getBucketWidthValue(BucketIdx)) <
+           NewBucketWidth);
+
+    HashTableEntry &ExtEntryRef = HashTables[0][BucketIdx];
+    ExtBitsEntry ExtEntry = ExtBitsEntry::getFromOpaqueValue(ExtEntryRef);
+    ExtEntry.setInt(static_cast<uint8_t>(countTrailingZeros(NewBucketWidth)));
+
+    ExtEntryRef = static_cast<ChainItem *>(ExtEntry.getOpaqueValue());
+  }
+
+  size_t getExtHashBits(hash_code Hash) {
+    return (Hash & ExtHashMask) >> HashBitsNum;
+  }
+
+  size_t getChainIdx(hash_code Hash, size_t BucketWidth) {
+    assert(BucketWidth > 0);
+
+    return getExtHashBits(Hash) & (BucketWidth - 1);
+  }
+
+  // Return number of entries inside specified bucket.
+  size_t getNumberOfEntries(size_t BucketIdx, size_t BucketWidth) {
+    class EntriesCounter {
+    public:
+      IterationStatus handleEntry(MapEntryTy &EntryData) {
+        if (ConcurrentHashTableBase::isNull(EntryData))
+          return IterationStatus::Next;
+
+        EntriesNumber++;
+        return IterationStatus::Next;
+      }
+      size_t EntriesNumber = 0;
+    } Handler;
+
+    for (size_t CurChainIdx = 0; CurChainIdx < BucketWidth; CurChainIdx++) {
+      ChainItem *ChainHead =
+          getChainHead<DoNotCreateChainHead>(BucketIdx, CurChainIdx);
+      if (ChainHead == nullptr)
+        continue;
+
+      [[maybe_unused]] bool ForEachSuccessful =
+          forEachChainEntry<DoNotCreateNewChainItems, EntriesCounter>(
+              BucketIdx, BucketWidth, ChainHead, Handler);
+      assert(ForEachSuccessful);
+    }
+
+    return Handler.EntriesNumber;
+  }
+
+  // Allocate new chain intem.
+  ChainItem *allocateItem(AllocatorTy &ThreadLocalAllocator) {
+    ChainItem *ResultItem = ThreadLocalAllocator.template Allocate<ChainItem>();
+
+    assert(ResultItem != nullptr);
+    memset(ResultItem, 0x0, sizeof(ChainItem));
+
+    return ResultItem;
+  }
+
+  // Return chain head. Create new head if CreateChainHead is true.
+  template <bool CreateChainHead, typename... Types>
+  ChainItem *getChainHead(size_t BucketIdx, hash_code Hash, size_t BucketWidth,
+                          Types &... ThreadLocalAllocator) {
+    size_t ChainIdx = getChainIdx(Hash, BucketWidth);
+    return getChainHead<CreateChainHead>(BucketIdx, ChainIdx,
+                                         ThreadLocalAllocator...);
+  }
+
+  // Return chain head. Create new head if CreateChainHead is true.
+  template <bool CreateChainHead, typename... Types>
+  ChainItem *getChainHead(size_t BucketIdx, size_t ChainIdx,
+                          Types &... ThreadLocalAllocator) {
+    ChainItem *ChainHead = HashTables[ChainIdx][BucketIdx];
+
+    if (ChainIdx == 0) {
+      ExtBitsEntry ExtEntry = ExtBitsEntry::getFromOpaqueValue(ChainHead);
+      ChainHead = ExtEntry.getPointer();
+
+      if constexpr (CreateChainHead) {
+        if (ChainHead == nullptr) {
+          ChainHead = allocateItem(ThreadLocalAllocator...);
+          ExtEntry.setPointer(ChainHead);
+          HashTables[ChainIdx][BucketIdx] =
+              static_cast<ChainItem *>(ExtEntry.getOpaqueValue());
+        }
+      }
+
+      return ChainHead;
+    }
+
+    if constexpr (CreateChainHead) {
+      if (ChainHead == nullptr) {
+        ChainHead = allocateItem(ThreadLocalAllocator...);
+        HashTables[ChainIdx][BucketIdx] = ChainHead;
+      }
+    }
+
+    return ChainHead;
+  }
+
+  // Return next chain item. Create new item if necessary.
+  template <bool CreateNewChainItems = true, typename... Types,
+            typename std::enable_if<CreateNewChainItems>::type * = nullptr>
+  ChainItem *getNextChainItem(ChainItem *Item,
+                              Types &... ThreadLocalAllocator) {
+    ChainItem *NextItem = Item->Next;
+
+    if (NextItem == nullptr) {
+      ChainItem *NewEntry = allocateItem(ThreadLocalAllocator...);
+
+      Item->Next = NewEntry;
+      return NewEntry;
+    }
+
+    return NextItem;
+  }
+
+  // Return next chain item.
+  template <bool CreateNewChainItems = false, typename... Types,
+            typename std::enable_if<!CreateNewChainItems>::type * = nullptr>
+  ChainItem *getNextChainItem(ChainItem *Item, Types &...) {
+    return Item->Next;
+  }
+
+  // Extend HashTables and rehash specified bucket.
+  template <bool AllowResizings = true, typename... Types,
+            typename std::enable_if<AllowResizings>::type * = nullptr>
+  bool extendTable(size_t BucketIdx, size_t BucketWidth,
+                   Types &... ThreadLocalAllocator) {
+    assert(BucketWidth ==
+           getBucketWidthFromValue(getBucketWidthValue(BucketIdx)));
+    if (BucketWidth >= MaxBucketWidth)
+      return false;
+
+    ExtendAndRehashBucket(BucketIdx, BucketWidth, ThreadLocalAllocator...);
+    return true;
+  }
+
+  // Do nothing.
+  template <bool AllowResizings = false, typename... Types,
+            typename std::enable_if<!AllowResizings>::type * = nullptr>
+  constexpr bool extendTable(size_t, size_t, Types &...) {
+    return false;
+  }
+
+  // Enumerate all entries for the specified bucket and bucket`s chain.
+  template <bool CreateNewChainItems, typename EntryHandler, typename... Types>
+  inline __attribute__((always_inline)) bool
+  forEachChainEntry(size_t BucketIdx, size_t BucketWidth, ChainItem *ChainHead,
+                    EntryHandler &Handler, Types &... ThreadLocalAllocator) {
+    assert(ChainHead != nullptr);
+
+    for (ChainItem *CurItem = ChainHead; CurItem != nullptr;
+         CurItem = getNextChainItem<CreateNewChainItems>(
+             CurItem, ThreadLocalAllocator...)) {
+      MapEntryTy *Entries = CurItem->Entries;
+      for (size_t EntryIdx = 0; EntryIdx < Constants::EntriesPerChainItem;) {
+        switch (Handler.handleEntry(Entries[EntryIdx])) {
+        case Stop:
+          return true;
+        case Next:
+          EntryIdx++;
+        }
+      }
+
+      if (extendTable<CreateNewChainItems>(BucketIdx, BucketWidth,
+                                           ThreadLocalAllocator...))
+        return false;
+    }
+
+    return true;
+  }
+
+  // Insert data into the chain item.
+  template <typename ReturnDataTy> class ValueInserter {
+  public:
+    ValueInserter(const InsertionTy &InsertionData,
+                  AllocatorTy &ThreadLocalAllocator, std::mutex &BucketMutex,
+                  hash_code Hash)
+        : InsertionData(InsertionData),
+          ThreadLocalAllocator(ThreadLocalAllocator), BucketMutex(BucketMutex),
+          Hash(Hash) {}
+
+    IterationStatus handleEntry(MapEntryTy &EntryData) {
+      MapEntryTy Value = EntryData;
+      if (ConcurrentHashTableBase::isNull(Value)) {
+        // Insert new value into the empty slot.
+        if constexpr (KeepDataInsideTable) {
+          Result.first = InsertionData;
+          EntryData = Result.first;
+        } else {
+          Result.first = Info::create(InsertionData, ThreadLocalAllocator);
+          EntryData = {Hash, Result.first};
+        }
+        assert(!(isNull(Result.first)));
+        BucketMutex.unlock();
+
+        Result.second = true;
+        return IterationStatus::Stop;
+      }
+
+      if constexpr (KeepDataInsideTable) {
+        if (ConcurrentHashTableBase::isEqual(Value, InsertionData)) {
+          // Already existed entry matched with inserted data
+          // is found.
+          BucketMutex.unlock();
+          Result.first = Value;
+          Result.second = false;
+          return IterationStatus::Stop;
+        }
+      } else {
+        if (ConcurrentHashTableBase::isEqual(Value, InsertionData, Hash)) {
+          // Already existed entry matched with inserted data
+          // is found.
+          BucketMutex.unlock();
+          Result.first = Value.Data;
+          Result.second = false;
+          return IterationStatus::Stop;
+        }
+      }
+
+      return IterationStatus::Next;
+    }
+    std::pair<ReturnDataTy, bool> Result;
+    const InsertionTy &InsertionData;
+    AllocatorTy &ThreadLocalAllocator;
+    std::mutex &BucketMutex;
+    hash_code Hash;
+  };
+
+  using CollectedValuesVector = SmallVector<MapEntryTy>;
+
+  // This function adds new chains to the bucket and rehash existing
+  // values to place them into the new chains.
+  void ExtendAndRehashBucket(size_t BucketIdx, size_t BucketWidth,
+                             AllocatorTy &ThreadLocalAllocator) {
+    assert(BucketWidth < MaxBucketWidth);
+
+    assert(BucketWidth > 0);
+    size_t NewBucketsWidth =
+        std::min(static_cast<size_t>(BucketWidth << Constants::GrowthRate),
+                 MaxBucketWidth);
+
+    // Check whether we need to create new hashtables.
+    if (NewBucketsWidth > NumberOfHashTables) {
+      std::unique_lock<std::mutex> Guard(HashTableMutex);
+
+      if (NewBucketsWidth > NumberOfHashTables)
+        allocateNewHashTables(NewBucketsWidth);
+    }
+
+    // Collect bucket values.
+    CollectedValuesVector Values;
+    collectValuesLocked(BucketIdx, BucketWidth, Values);
+
+    assert(getNumberOfEntries(BucketIdx, BucketWidth) == 0);
+
+    // Insert values into extended bucket.
+    insertValuesLocked(Values, BucketIdx, NewBucketsWidth,
+                       ThreadLocalAllocator);
+
+    // Update bucket width.
+    setBucketWidth(BucketIdx, NewBucketsWidth);
+  }
+
+  // Collect all data into the specified vector Values.
+  // Erase data from all bucket's chains.
+  void collectValuesLocked(size_t BucketIdx, size_t BucketWidth,
+                           CollectedValuesVector &Values) {
+    class ValueCollector {
+    public:
+      ValueCollector(CollectedValuesVector &Values) : Values(Values) {}
+
+      IterationStatus handleEntry(MapEntryTy &EntryData) {
+        MapEntryTy Value = EntryData;
+
+        if (ConcurrentHashTableBase::isNull(Value))
+          return IterationStatus::Stop;
+
+        Values.emplace_back(Value);
+        setToNull(&EntryData);
+
+        return IterationStatus::Next;
+      }
+
+      CollectedValuesVector &Values;
+    } Handler(Values);
+
+    // Collect bucket values.
+    for (size_t CurChainIdx = 0; CurChainIdx < BucketWidth; CurChainIdx++) {
+      ChainItem *ChainHead =
+          getChainHead<DoNotCreateChainHead>(BucketIdx, CurChainIdx);
+      if (ChainHead == nullptr)
+        continue;
+
+      [[maybe_unused]] bool ForEachSuccessful =
+          forEachChainEntry<DoNotCreateNewChainItems, ValueCollector>(
+              BucketIdx, BucketWidth, ChainHead, Handler);
+      assert(ForEachSuccessful);
+    }
+  }
+
+  // Insert data into the locked bucket.
+  void insertValuesLocked(CollectedValuesVector &Values, size_t BucketIdx,
+                          size_t BucketWidth,
+                          AllocatorTy &ThreadLocalAllocator) {
+    for (MapEntryTy &NewValue : Values) {
+      assert(!(ConcurrentHashTableBase::isNull(NewValue)));
+
+      hash_code Hash = ConcurrentHashTableBase::getHashCode(NewValue);
+      ChainItem *ChainHead = getChainHead<CreateChainHead>(
+          BucketIdx, Hash, BucketWidth, ThreadLocalAllocator);
+
+      class InsertEntry {
+      public:
+        InsertEntry(MapEntryTy NewValue) : NewValue(NewValue) {}
+
+        IterationStatus handleEntry(MapEntryTy &EntryData) {
+          if (ConcurrentHashTableBase::isNull(EntryData)) {
+            EntryData = NewValue;
+            return IterationStatus::Stop;
+          }
+
+          return IterationStatus::Next;
+        }
+
+        MapEntryTy NewValue;
+      } Handler(NewValue);
+
+      [[maybe_unused]] bool ForEachSuccessful =
+          forEachChainEntry<DoNotCreateNewChainItems, InsertEntry>(
+              BucketIdx, BucketWidth, ChainHead, Handler, ThreadLocalAllocator);
+
+      assert(ForEachSuccessful);
+    }
+  }
+
+  // Allocate new hashtables for specified NewBucketsWidth.
+  void allocateNewHashTables(size_t NewBucketsWidth) {
+    assert((NewBucketsWidth >= 1) & !(NewBucketsWidth & (NewBucketsWidth - 1)));
+    assert(NumberOfHashTables < NewBucketsWidth);
+
+    size_t Start = NumberOfHashTables;
+    size_t Stop = NewBucketsWidth;
+
+    // Allocate and initialize new tables.
+    for (size_t Idx = Start; Idx < Stop; Idx++) {
+      HashTablePtr NewTable =
+          Allocator.template Allocate<HashTableEntry>(HashTableSize);
+      memset(NewTable, 0, sizeof(HashTableEntry) * HashTableSize);
+      HashTables[Idx] = NewTable;
+    }
+
+    NumberOfHashTables = NewBucketsWidth;
+  }
+
+  // Return mutex for the specified BucketIdx.
+  std::mutex &getBucketMutex(size_t BucketIdx) {
+    return BucketMutexes[BucketIdx & (BucketMutexesNum - 1)];
+  }
+
+  template <typename MapEntryTy,
+            typename std::enable_if<
+                (std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value),
+                bool>::type = true>
+  static inline bool isNull(MapEntryTy Data) {
+    const uint64_t *DataPtr = reinterpret_cast<const uint64_t *>(&Data);
+    return *DataPtr == 0 && DataPtr[1] == 0;
+  }
+
+  template <typename MapEntryTy,
+            typename std::enable_if<
+                (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+                 sizeof(MapEntryTy) == sizeof(uint8_t)),
+                bool>::type = true>
+  static inline bool isNull(const MapEntryTy &Data) {
+    return *reinterpret_cast<const uint8_t *>(&Data) == static_cast<uint8_t>(0);
+  }
+
+  template <typename MapEntryTy,
+            typename std::enable_if<
+                (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+                 sizeof(MapEntryTy) == sizeof(uint16_t)),
+                bool>::type = true>
+  static inline bool isNull(const MapEntryTy &Data) {
+    return *reinterpret_cast<const uint16_t *>(&Data) ==
+           static_cast<uint16_t>(0);
+  }
+
+  template <typename MapEntryTy,
+            typename std::enable_if<
+                (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+                 sizeof(MapEntryTy) == sizeof(uint32_t)),
+                bool>::type = true>
+  static inline bool isNull(const MapEntryTy &Data) {
+    return *reinterpret_cast<const uint32_t *>(&Data) ==
+           static_cast<uint32_t>(0);
+  }
+
+  template <typename MapEntryTy,
+            typename std::enable_if<
+                (!std::is_same<MapEntryTy, HashedEntry<KeyDataTy>>::value &&
+                 sizeof(MapEntryTy) == sizeof(uint64_t)),
+                bool>::type = true>
+  static inline bool isNull(const MapEntryTy &Data) {
+    return *reinterpret_cast<const uint64_t *>(&Data) ==
+           static_cast<uint64_t>(0);
+  }
+
+  static inline bool setToNull(MapEntryTy *Data) {
+    return memset(Data, 0, sizeof(MapEntryTy));
+  }
+
+  static inline bool isEqual(MapEntryTy LHS, const InsertionTy &RHS,
+                             uint64_t Hash) {
+    return (LHS.Hash == Hash) && Info::isEqual(LHS.Data->key(), RHS);
+  }
+
+  static inline bool isEqual(const MapEntryTy &LHS, const InsertionTy &RHS) {
+    return Info::isEqual(LHS.key(), RHS.key());
+  }
+
+  static inline hash_code getHashCode(const KeyTy &Data) {
+    return Info::getHashValue(Data);
+  }
+
+  static inline hash_code getHashCode(const KeyDataTy &Data) {
+    return Info::getHashValue(Data.key());
+  }
+
+  static inline hash_code getHashCode(const HashedEntry<KeyDataTy> &Data) {
+    return Data.Hash;
+  }
+
+  size_t getHashMask() { return HashTableSize - 1; }
+
+  // Number of bits in hash mask.
+  uint64_t HashBitsNum = 0;
+
+  // Hash mask for the extended hash bits.
+  uint64_t ExtHashMask = 0;
+
+  // Array of mutexes.
+  std::mutex *BucketMutexes = nullptr;
+
+  // Number of used mutexes.
+  size_t BucketMutexesNum = 2;
+
+  // The maximal bucket width.
+  size_t MaxBucketWidth = 0;
+
+  // The size of single hashtable.
+  size_t HashTableSize = 0;
+
+  // The guard for HashTables array.
+  std::mutex HashTableMutex;
+
+  // The current number of HashTables.
+  std::atomic<size_t> NumberOfHashTables;
+
+  // HashTables keeping buckets chains.
+  HashTablePtr HashTables[Constants::MaxBucketWidthNum];
+
+  // This allocator is used to allocate space for the hash tables.
+  // The data are not explicitly deallocated by ConcurrentHashTableBase.
+  AllocatorTy &Allocator;
+};
+
+/// ConcurrentHashTable: keeps a KeyDataTy(which is a key-value pair).
+/// The state when all data bits of KeyDataTy are zero is reserved as
+/// a hashtable tombstone value.
+///
+
+template <typename KeyTy, typename KeyDataTy> class ConcurrentHashTableInfo {
+public:
+  /// \returns Hash value for the specified \p Key.
+  static inline hash_code getHashValue(const KeyTy &Key) {
+    return std::hash<KeyTy>()(Key);
+  }
+
+  /// \returns true if both \p LHS and \p RHS are equal.
+  static inline bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
+    return LHS == RHS;
+  }
+};
+
+template <typename KeyTy, typename KeyDataTy,
+          typename AllocatorTy = BumpPtrAllocator,
+          typename Info = ConcurrentHashTableInfo<KeyTy, KeyDataTy>,
+          typename Constants = ConcurrentHashTableConstants<KeyDataTy, true>>
+class ConcurrentHashTable
+    : public ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, true, Info,
+                                     Constants> {
+public:
+  ConcurrentHashTable(size_t InitialSize, AllocatorTy &Allocator)
+      : ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, true, Info,
+                                Constants>(InitialSize, Allocator) {}
+};
+
+/// ConcurrentHashTableExternalAlloc: keeps a pointer to the KeyDataTy class
+/// (which is a key-value pair), whose data are allocated and kept by the
+/// external allocator.
+
+template <typename KeyTy, typename KeyDataTy, typename AllocatorTy>
+class ConcurrentHashTableInfoExternalAlloc {
+public:
+  /// \returns Hash value for the specified \p Key.
+  static inline hash_code getHashValue(const KeyTy &Key) {
+    return std::hash<KeyTy>()(Key);
+  }
+
+  /// \returns true if both \p LHS and \p RHS are equal.
+  static inline bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
+    return LHS == RHS;
+  }
+
+  /// \returns newly created object of KeyDataTy type.
+  static inline KeyDataTy *create(const KeyTy &Key, AllocatorTy &Allocator) {
+    return KeyDataTy::create(Key, Allocator);
+  }
+};
+
+template <
+    typename KeyTy, typename KeyDataTy, typename AllocatorTy = BumpPtrAllocator,
+    typename Info =
+        ConcurrentHashTableInfoExternalAlloc<KeyTy, KeyDataTy, AllocatorTy>,
+    typename Constants = ConcurrentHashTableConstants<KeyDataTy, false>>
+class ConcurrentHashTableExternalAlloc
+    : public ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, false, Info,
+                                     Constants> {
+public:
+  ConcurrentHashTableExternalAlloc(size_t InitialSize, AllocatorTy &Allocator)
+      : ConcurrentHashTableBase<KeyTy, KeyDataTy, AllocatorTy, false, Info,
+                                Constants>(InitialSize, Allocator) {}
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_CONCURRENTHASHTABLE_H
diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -16,6 +16,7 @@
   BumpPtrListTest.cpp
   CoalescingBitVectorTest.cpp
   CombinationGeneratorTest.cpp
+  ConcurrentHashtableTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
diff --git a/llvm/unittests/ADT/ConcurrentHashtableTest.cpp b/llvm/unittests/ADT/ConcurrentHashtableTest.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/unittests/ADT/ConcurrentHashtableTest.cpp
@@ -0,0 +1,401 @@
+//===- ConcurrentHashtableTest.cpp ----------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/ConcurrentHashtable.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/Parallel.h"
+#include "gtest/gtest.h"
+#include <experimental/random>
+#include <limits>
+#include <vector>
+using namespace llvm;
+
+namespace {
+class Int {
+public:
+  Int() : Data(0x0) {}
+  uint32_t key() const { return Data & 0x7FFFFFFF; }
+
+  friend bool operator==(const Int &LHS, const Int &RHS) {
+    return LHS.Data == RHS.Data;
+  }
+
+  static Int create(uint32_t Data) { return Int(Data | 0x80000000); }
+
+protected:
+  Int(uint32_t Data) : Data(Data) {}
+
+  uint32_t Data;
+};
+
+TEST(ConcurrentHashTableTest, AddIntEntries) {
+  BumpPtrAllocator Allocator;
+  ConcurrentHashTable<uint32_t, Int> HashTable(10, Allocator);
+
+  std::pair<Int, bool> res1 = HashTable.insert(Int::create(1), Allocator);
+  // Check entry is inserted.
+  EXPECT_TRUE(res1.first.key() == 1);
+  EXPECT_TRUE(res1.second);
+
+  res1 = HashTable.insert(Int::create(1), Allocator);
+  // Check entry is inserted.
+  EXPECT_TRUE(res1.first.key() == 1);
+  EXPECT_FALSE(res1.second);
+
+  std::pair<Int, bool> res2 = HashTable.insert(Int::create(2), Allocator);
+  // Check old entry is still valid.
+  EXPECT_TRUE(res1.first.key() == 1);
+  // Check new entry is inserted.
+  EXPECT_TRUE(res2.first.key() == 2);
+  EXPECT_TRUE(res2.second);
+  // Check new and old entries are not the equal.
+  EXPECT_FALSE(res1.first == res2.first);
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 2") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesWithResizing) {
+  BumpPtrAllocator Allocator;
+  ConcurrentHashTable<uint32_t, Int> HashTable(10, Allocator);
+
+  for (size_t Idx = 0; Idx < 10000; Idx++) {
+    std::pair<Int, bool> res1 = HashTable.insert(Int::create(Idx), Allocator);
+    // Check entry is inserted.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_TRUE(res1.second);
+
+    res1 = HashTable.insert(Int::create(Idx), Allocator);
+    // Check entry is found.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  }
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+
+  for (size_t Idx = 0; Idx < 10000; Idx++) {
+    std::pair<Int, bool> res1 = HashTable.insert(Int::create(Idx), Allocator);
+    // Check entry is found.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  }
+
+  StatisticString.erase();
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesParralel) {
+  static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+  ConcurrentHashTable<uint32_t, Int> HashTable(1000000, DataAllocator);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 =
+        HashTable.insert(Int::create(Idx), DataAllocator);
+    // Check entry is inserted.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_TRUE(res1.second);
+
+    res1 = HashTable.insert(Int::create(Idx), DataAllocator);
+    // Check entry is found.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  });
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 =
+        HashTable.insert(Int::create(Idx), DataAllocator);
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  });
+
+  StatisticString.erase();
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesWithResizingParralel1) {
+  static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+  ConcurrentHashTable<uint32_t, Int> HashTable(1000, DataAllocator);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 =
+        HashTable.insert(Int::create(Idx), DataAllocator);
+    // Check entry is inserted.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_TRUE(res1.second);
+
+    res1 = HashTable.insert(Int::create(Idx), DataAllocator);
+    // Check entry is found.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  });
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 =
+        HashTable.insert(Int::create(Idx), DataAllocator);
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  });
+
+  StatisticString.erase();
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddEntriesWithResizingParralel2) {
+  static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+  ConcurrentHashTable<uint32_t, Int> HashTable(10, DataAllocator);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 =
+        HashTable.insert(Int::create(Idx), DataAllocator);
+    // Check entry is inserted.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_TRUE(res1.second);
+
+    res1 = HashTable.insert(Int::create(Idx), DataAllocator);
+    // Check entry is found.
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  });
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 =
+        HashTable.insert(Int::create(Idx), DataAllocator);
+    EXPECT_TRUE(res1.first.key() == Idx);
+    EXPECT_FALSE(res1.second);
+  });
+
+  StatisticString.erase();
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddRandomEntriesParralel) {
+
+  std::vector<Int> Data;
+  std::set<size_t> UniqData;
+  std::srand(
+      std::time(nullptr)); // use current time as seed for random generator
+  for (size_t Idx = 0; Idx < 10000; Idx++) {
+    size_t RndNum = std::experimental::randint(0, 100);
+    Data.push_back(Int::create(RndNum));
+    UniqData.insert(RndNum);
+  }
+
+  static LLVM_THREAD_LOCAL BumpPtrAllocator DataAllocator;
+  ConcurrentHashTable<uint32_t, Int> HashTable(10, DataAllocator);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 = HashTable.insert(Data[Idx], DataAllocator);
+    //// Check entry is inserted.
+    EXPECT_TRUE(res1.first.key() == Data[Idx].key());
+
+    res1 = HashTable.insert(Data[Idx], DataAllocator);
+    //// Check entry is inserted.
+    EXPECT_TRUE(res1.first.key() == Data[Idx].key());
+    EXPECT_FALSE(res1.second);
+  });
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = " +
+                                   itostr(UniqData.size())) !=
+              std::string::npos);
+
+  parallelFor(0, 10000, [&](size_t Idx) {
+    std::pair<Int, bool> res1 = HashTable.insert(Data[Idx], DataAllocator);
+    EXPECT_TRUE(res1.first.key() == Data[Idx].key());
+    EXPECT_FALSE(res1.second);
+  });
+
+  StatisticString.erase();
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = " +
+                                   itostr(UniqData.size())) !=
+              std::string::npos);
+}
+
+using ExtraDataTy = std::array<char, 0x20>;
+
+class String {
+public:
+  String() {}
+  const std::string &key() const { return Data; }
+
+  static String *create(const std::string &Num, BumpPtrAllocator &Allocator) {
+    String *Result = Allocator.Allocate<String>();
+    new (Result) String(Num);
+    return Result;
+  }
+
+protected:
+  String(const std::string &Num) { Data += Num; }
+
+  std::string Data;
+  ExtraDataTy ExtraData;
+};
+
+TEST(ConcurrentHashTableTest, AddStringEntries) {
+  BumpPtrAllocator Allocator;
+  ConcurrentHashTableExternalAlloc<std::string, String> HashTable(10,
+                                                                  Allocator);
+
+  std::pair<String *, bool> res1 = HashTable.insert("1", Allocator);
+  // Check entry is inserted.
+  EXPECT_TRUE(res1.first->key() == "1");
+  EXPECT_TRUE(res1.second);
+
+  std::pair<String *, bool> res2 = HashTable.insert("2", Allocator);
+  // Check old entry is still valid.
+  EXPECT_TRUE(res1.first->key() == "1");
+  // Check new entry is inserted.
+  EXPECT_TRUE(res2.first->key() == "2");
+  EXPECT_TRUE(res2.second);
+  // Check new and old entries use different memory.
+  EXPECT_TRUE(res1.first != res2.first);
+
+  std::pair<String *, bool> res3 = HashTable.insert("3", Allocator);
+  // Check one more entry is inserted.
+  EXPECT_TRUE(res3.first->key() == "3");
+  EXPECT_TRUE(res3.second);
+
+  std::pair<String *, bool> res4 = HashTable.insert("1", Allocator);
+  // Check duplicated entry is inserted.
+  EXPECT_TRUE(res4.first->key() == "1");
+  EXPECT_FALSE(res4.second);
+  // Check duplicated entry matches with the first one.
+  EXPECT_TRUE(res1.first == res4.first);
+
+  // Check first entry is still valid.
+  EXPECT_TRUE(res1.first->key() == "1");
+
+  // Check data was allocated by allocator.
+  EXPECT_TRUE(Allocator.getBytesAllocated() > 0);
+
+  // Check statistic.
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 3") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddStringEntriesParallel) {
+  // Number of elements exceeds original size, thus hashtable
+  // should be resized.
+  const size_t NumElements = 10000;
+  static LLVM_THREAD_LOCAL BumpPtrAllocator Allocator;
+  ConcurrentHashTableExternalAlloc<std::string, String, BumpPtrAllocator>
+      HashTable(NumElements, Allocator);
+
+  // Check parallel insertion.
+  parallelFor(0, NumElements, [&](size_t I) {
+    std::string StringForElement = formatv("{0}", I);
+    std::pair<String *, bool> Entry =
+        HashTable.insert(StringForElement, Allocator);
+    EXPECT_TRUE(Entry.second);
+    EXPECT_TRUE(Entry.first->key() == StringForElement);
+    EXPECT_TRUE(Allocator.getBytesAllocated() > 0);
+  });
+
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+
+  // Check parallel insertion of duplicates.
+  parallelFor(0, NumElements, [&](size_t I) {
+    size_t BytesAllocated = Allocator.getBytesAllocated();
+    std::string StringForElement = formatv("{0}", I);
+    std::pair<String *, bool> Entry =
+        HashTable.insert(StringForElement, Allocator);
+    EXPECT_FALSE(Entry.second);
+    EXPECT_TRUE(Entry.first->key() == StringForElement);
+    // Check no additional bytes were allocated for duplicate.
+    EXPECT_TRUE(Allocator.getBytesAllocated() == BytesAllocated);
+  });
+
+  // Check statistic.
+  // Verifying that the table contains exactly the number of elements we
+  // inserted.
+  EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000") !=
+              std::string::npos);
+}
+
+} // namespace