From 868654e5495c632e56c5601212e49feca1029df8 Mon Sep 17 00:00:00 2001 From: Alexey Lapshin Date: Wed, 29 Mar 2023 12:58:21 +0200 Subject: [PATCH] [DWARFLinkerParallel] Add StringPool class. This patch is extracted from D96035. It adds StringPool class. StringPool allows to store strings in parallel. It also allows to have string data associated with the concrete string. Reviewed By: JDevlieghere Differential Revision: https://reviews.llvm.org/D140841 --- llvm/include/llvm/DWARFLinkerParallel/StringPool.h | 85 ++++++++++++++++++++++ llvm/lib/DWARFLinkerParallel/CMakeLists.txt | 1 + llvm/lib/DWARFLinkerParallel/StringPool.cpp | 12 +++ llvm/unittests/DWARFLinkerParallel/CMakeLists.txt | 1 + .../DWARFLinkerParallel/StringPoolTest.cpp | 62 ++++++++++++++++ 5 files changed, 161 insertions(+) create mode 100644 llvm/include/llvm/DWARFLinkerParallel/StringPool.h create mode 100644 llvm/lib/DWARFLinkerParallel/StringPool.cpp create mode 100644 llvm/unittests/DWARFLinkerParallel/StringPoolTest.cpp diff --git a/llvm/include/llvm/DWARFLinkerParallel/StringPool.h b/llvm/include/llvm/DWARFLinkerParallel/StringPool.h new file mode 100644 index 0000000..52fb64c --- /dev/null +++ b/llvm/include/llvm/DWARFLinkerParallel/StringPool.h @@ -0,0 +1,85 @@ +//===- StringPool.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_DWARFLINKERPARALLEL_STRINGPOOL_H +#define LLVM_DWARFLINKERPARALLEL_STRINGPOOL_H + +#include "llvm/ADT/ConcurrentHashtable.h" +#include "llvm/CodeGen/DwarfStringPoolEntry.h" +#include "llvm/Support/Allocator.h" +#include +#include + +namespace llvm { +namespace dwarflinker_parallel { + +/// StringEntry keeps data of the string: the length, external offset +/// and a string body which is placed right after StringEntry. +using StringEntry = StringMapEntry; + +class PerThreadStringAllocator + : public AllocatorBase { +public: + inline LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size, + size_t Alignment) { + return ThreadLocalAllocator.Allocate(Size, Align(Alignment)); + } + + // Pull in base class overloads. + using AllocatorBase::Allocate; + +private: + static thread_local BumpPtrAllocator ThreadLocalAllocator; +}; + +class StringPoolEntryInfo { +public: + /// \returns Hash value for the specified \p Key. + static inline uint64_t getHashValue(const StringRef &Key) { + return xxHash64(Key); + } + + /// \returns true if both \p LHS and \p RHS are equal. + static inline bool isEqual(const StringRef &LHS, const StringRef &RHS) { + return LHS == RHS; + } + + /// \returns key for the specified \p KeyData. + static inline StringRef getKey(const StringEntry &KeyData) { + return KeyData.getKey(); + } + + /// \returns newly created object of KeyDataTy type. + static inline StringEntry *create(const StringRef &Key, + PerThreadStringAllocator &Allocator) { + return StringEntry::create(Key, Allocator); + } +}; + +class StringPool : public ConcurrentHashTableByPtr { +public: + StringPool() + : ConcurrentHashTableByPtr( + Allocator) {} + + StringPool(size_t InitialSize) + : ConcurrentHashTableByPtr( + Allocator, InitialSize) {} + +private: + PerThreadStringAllocator Allocator; +}; + +} // end of namespace dwarflinker_parallel +} // end namespace llvm + +#endif // LLVM_DWARFLINKERPARALLEL_STRINGPOOL_H diff --git a/llvm/lib/DWARFLinkerParallel/CMakeLists.txt b/llvm/lib/DWARFLinkerParallel/CMakeLists.txt index 298fb98..a9bad6c 100644 --- a/llvm/lib/DWARFLinkerParallel/CMakeLists.txt +++ b/llvm/lib/DWARFLinkerParallel/CMakeLists.txt @@ -1,5 +1,6 @@ add_llvm_component_library(LLVMDWARFLinkerParallel DWARFLinker.cpp + StringPool.cpp ADDITIONAL_HEADER_DIRS ${LLVM_MAIN_INCLUDE_DIR}/llvm/DWARFLinkerParallel diff --git a/llvm/lib/DWARFLinkerParallel/StringPool.cpp b/llvm/lib/DWARFLinkerParallel/StringPool.cpp new file mode 100644 index 0000000..aa8bc61 --- /dev/null +++ b/llvm/lib/DWARFLinkerParallel/StringPool.cpp @@ -0,0 +1,12 @@ +//=== StringPool.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/DWARFLinkerParallel/StringPool.h" + +thread_local llvm::BumpPtrAllocator + llvm::dwarflinker_parallel::PerThreadStringAllocator::ThreadLocalAllocator; diff --git a/llvm/unittests/DWARFLinkerParallel/CMakeLists.txt b/llvm/unittests/DWARFLinkerParallel/CMakeLists.txt index e81e09c..ca2cb47 100644 --- a/llvm/unittests/DWARFLinkerParallel/CMakeLists.txt +++ b/llvm/unittests/DWARFLinkerParallel/CMakeLists.txt @@ -5,6 +5,7 @@ set(LLVM_LINK_COMPONENTS add_llvm_unittest(DWARFLinkerParallelTests DWARFLinkerTest.cpp + StringPoolTest.cpp ) target_link_libraries(DWARFLinkerParallelTests PRIVATE LLVMTestingSupport) diff --git a/llvm/unittests/DWARFLinkerParallel/StringPoolTest.cpp b/llvm/unittests/DWARFLinkerParallel/StringPoolTest.cpp new file mode 100644 index 0000000..2e36cde --- /dev/null +++ b/llvm/unittests/DWARFLinkerParallel/StringPoolTest.cpp @@ -0,0 +1,62 @@ +//===- llvm/unittest/DWARFLinkerParallel/StringPoolTest.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/DWARFLinkerParallel/StringPool.h" +#include "llvm/Support/Parallel.h" +#include "gtest/gtest.h" +#include + +using namespace llvm; +using namespace dwarflinker_parallel; + +namespace { + +TEST(StringPoolTest, TestStringPool) { + StringPool Strings; + + std::pair Entry = Strings.insert("test"); + EXPECT_TRUE(Entry.second); + EXPECT_TRUE(Entry.first->getKey() == "test"); + EXPECT_TRUE(Entry.first->second == nullptr); + + StringEntry *EntryPtr = Entry.first; + + Entry = Strings.insert("test"); + EXPECT_FALSE(Entry.second); + EXPECT_TRUE(Entry.first->getKey() == "test"); + EXPECT_TRUE(Entry.first->second == nullptr); + EXPECT_TRUE(EntryPtr == Entry.first); + + Entry = Strings.insert("test2"); + EXPECT_TRUE(Entry.second); + EXPECT_TRUE(Entry.first->getKey() == "test2"); + EXPECT_TRUE(Entry.first->second == nullptr); + EXPECT_TRUE(EntryPtr != Entry.first); +} + +TEST(StringPoolTest, TestStringPoolParallel) { + StringPool Strings; + + // Add data. + parallelFor(0, 1000, [&](size_t Idx) { + std::pair Entry = Strings.insert(std::to_string(Idx)); + EXPECT_TRUE(Entry.second); + EXPECT_TRUE(Entry.first->getKey() == std::to_string(Idx)); + EXPECT_TRUE(Entry.first->second == nullptr); + }); + + // Check data. + parallelFor(0, 1000, [&](size_t Idx) { + std::pair Entry = Strings.insert(std::to_string(Idx)); + EXPECT_FALSE(Entry.second); + EXPECT_TRUE(Entry.first->getKey() == std::to_string(Idx)); + EXPECT_TRUE(Entry.first->second == nullptr); + }); +} + +} // anonymous namespace -- 2.7.4