Author: Fangrui Song Date: 2026-09-09T08:28:20Z New Revision: c4cd7b73e27839103badad11e4eff9baf3d53d84
URL: https://github.com/llvm/llvm-project/commit/c4cd7b73e27839103badad11e4eff9baf3d53d84 DIFF: https://github.com/llvm/llvm-project/commit/c4cd7b73e27839103badad11e4eff9baf3d53d84.diff LOG: [ADT] Give DenseMapPair its own members instead of a std::pair base. NFC (#221853) std::pair declares a copy assignment operator, so it is not trivially copyable. destroyAll and copyFrom therefore ask about KeyT and ValueT separately. Hold first and second directly. Conversion to std::pair is explicit; insert also takes a bucket, and a converting constructor keeps range insert working across pair types. Co-authored-by: Kazu Hirata <[email protected]> Added: Modified: lldb/source/Plugins/ExpressionParser/Clang/ClangASTImporter.cpp llvm/include/llvm/ADT/DenseMap.h llvm/lib/MCA/InstrBuilder.cpp llvm/lib/Target/AMDGPU/AMDGPURewriteOutArguments.cpp llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp llvm/lib/Target/AMDGPU/SIInstrInfo.cpp llvm/lib/Transforms/Scalar/GVNSink.cpp llvm/unittests/ADT/DenseMapTest.cpp llvm/utils/lldbDataFormatters.py third-party/unittest/googletest/include/gtest/internal/custom/gtest-printers.h Removed: ################################################################################ diff --git a/lldb/source/Plugins/ExpressionParser/Clang/ClangASTImporter.cpp b/lldb/source/Plugins/ExpressionParser/Clang/ClangASTImporter.cpp index 95664eec647ed..9d6dd2617a945 100644 --- a/lldb/source/Plugins/ExpressionParser/Clang/ClangASTImporter.cpp +++ b/lldb/source/Plugins/ExpressionParser/Clang/ClangASTImporter.cpp @@ -209,7 +209,7 @@ class DeclContextOverride { } ~DeclContextOverride() { - for (const std::pair<clang::Decl *, Backup> &backup : m_backups) { + for (const auto &backup : m_backups) { backup.first->setDeclContext(backup.second.decl_context); backup.first->setLexicalDeclContext(backup.second.lexical_decl_context); } @@ -541,8 +541,7 @@ static bool ImportOffsetMap(clang::ASTContext *dest_ctx, // DenseMap with a pointer as the key type, this means we cannot simply // iterate over the map, as the order will be non-deterministic. Instead we // have to sort by the offset and then insert in sorted order. - typedef llvm::DenseMap<const D *, O> MapType; - typedef typename MapType::value_type PairType; + typedef std::pair<const D *, O> PairType; std::vector<PairType> sorted_items; sorted_items.reserve(source_map.size()); sorted_items.assign(source_map.begin(), source_map.end()); diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index 3073ab0ec9712..0126935ca3598 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -44,17 +44,45 @@ namespace llvm { namespace detail { +// A bucket holds a key and a value. Don't use std::pair, which has a +// non-trivial copy assignment, which costs is_trivially_copyable. +template <typename KeyT, typename ValueT> struct DenseMapPair { + using first_type = KeyT; + using second_type = ValueT; + + KeyT first; + ValueT second; + + DenseMapPair() : first(), second() {} + DenseMapPair(const KeyT &Key, const ValueT &Value) + : first(Key), second(Value) {} + DenseMapPair(KeyT &&Key, ValueT &&Value) + : first(std::move(Key)), second(std::move(Value)) {} + DenseMapPair(const std::pair<KeyT, ValueT> &P) + : first(P.first), second(P.second) {} + DenseMapPair(std::pair<KeyT, ValueT> &&P) + : first(std::move(P.first)), second(std::move(P.second)) {} + template <typename U1, typename U2> + DenseMapPair(const DenseMapPair<U1, U2> &P) + : first(P.first), second(P.second) {} + template <typename U1, typename U2> + DenseMapPair(DenseMapPair<U1, U2> &&P) + : first(std::move(P.first)), second(std::move(P.second)) {} + + operator std::pair<KeyT, ValueT>() const { return {first, second}; } + operator std::pair<const KeyT, ValueT>() const { return {first, second}; } + + friend bool operator==(const DenseMapPair &LHS, const DenseMapPair &RHS) { + return LHS.first == RHS.first && LHS.second == RHS.second; + } + friend bool operator!=(const DenseMapPair &LHS, const DenseMapPair &RHS) { + return !(LHS == RHS); + } -// 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 : 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; } + KeyT &getFirst() { return first; } + const KeyT &getFirst() const { return first; } + ValueT &getSecond() { return second; } + const ValueT &getSecond() const { return second; } }; } // end namespace detail @@ -292,6 +320,20 @@ class DenseMapBase : public DebugEpochBase { return try_emplace_impl(std::move(KV.first), std::move(KV.second)); } + template < + typename B = BucketT, + typename = std::enable_if_t<!std::is_same_v<B, std::pair<KeyT, ValueT>>>> + std::pair<iterator, bool> insert(const BucketT &KV) { + return try_emplace_impl(KV.first, KV.second); + } + + template < + typename B = BucketT, + typename = std::enable_if_t<!std::is_same_v<B, std::pair<KeyT, ValueT>>>> + std::pair<iterator, bool> insert(BucketT &&KV) { + return try_emplace_impl(std::move(KV.first), std::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. @@ -462,10 +504,9 @@ class DenseMapBase : public DebugEpochBase { } void destroyAll() { - // No need to iterate through the buckets if both KeyT and ValueT are - // trivially destructible. - if constexpr (std::is_trivially_destructible_v<KeyT> && - std::is_trivially_destructible_v<ValueT>) + // No need to iterate through the buckets if the bucket is trivially + // destructible. + if constexpr (std::is_trivially_destructible_v<BucketT>) return; if (getNumBuckets() == 0) // Nothing to do. @@ -555,8 +596,7 @@ class DenseMapBase : public DebugEpochBase { const UsedT *OtherU = other.getUsed(); std::memcpy(U, OtherU, llvm::densemap::detail::usedWords(NumBuckets) * sizeof(UsedT)); - if constexpr (std::is_trivially_copyable_v<KeyT> && - std::is_trivially_copyable_v<ValueT>) { + if constexpr (std::is_trivially_copyable_v<BucketT>) { memcpy(reinterpret_cast<void *>(Buckets), OtherBuckets, NumBuckets * sizeof(BucketT)); } else { diff --git a/llvm/lib/MCA/InstrBuilder.cpp b/llvm/lib/MCA/InstrBuilder.cpp index b7819daca5a66..c5169b908b7e8 100644 --- a/llvm/lib/MCA/InstrBuilder.cpp +++ b/llvm/lib/MCA/InstrBuilder.cpp @@ -185,7 +185,7 @@ static void initializeUsedResources(InstrDesc &ID, } // Identify extra buffers that are consumed through super resources. - for (const std::pair<uint64_t, unsigned> &SR : SuperResources) { + for (const auto &SR : SuperResources) { for (unsigned I = 1, E = NumProcResources; I < E; ++I) { if (SM.getResourceBufferSize(I) == -1) continue; diff --git a/llvm/lib/Target/AMDGPU/AMDGPURewriteOutArguments.cpp b/llvm/lib/Target/AMDGPU/AMDGPURewriteOutArguments.cpp index 30431cb54249c..2ed66dc09dbb6 100644 --- a/llvm/lib/Target/AMDGPU/AMDGPURewriteOutArguments.cpp +++ b/llvm/lib/Target/AMDGPU/AMDGPURewriteOutArguments.cpp @@ -378,7 +378,7 @@ bool AMDGPURewriteOutArguments::runOnFunction(Function &F) { // this function with a stub. NewFunc->splice(NewFunc->begin(), &F); - for (std::pair<ReturnInst *, ReplacementVec> &Replacement : Replacements) { + for (auto &Replacement : Replacements) { ReturnInst *RI = Replacement.first; IRBuilder<> B(RI); B.SetCurrentDebugLocation(RI->getDebugLoc()); diff --git a/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp b/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp index 9597fccb89494..11e7e2f1edc97 100644 --- a/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp +++ b/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp @@ -2232,8 +2232,10 @@ bool GCNHazardRecognizer::fixVALUPartialForwardingHazard(MachineInstr *MI) { int VALUs = 0; static unsigned getHashValue(const StateType &State) { - return hash_combine(State.ExecPos, State.VALUs, - hash_combine_range(State.DefPos)); + hash_code H = hash_combine(State.ExecPos, State.VALUs); + for (const auto &[Reg, Pos] : State.DefPos) + H = hash_combine(H, Reg, Pos); + return H; } static bool isEqual(const StateType &LHS, const StateType &RHS) { return LHS.DefPos == RHS.DefPos && LHS.ExecPos == RHS.ExecPos && diff --git a/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp b/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp index a456b2193403c..f2f2a1b7d2eaa 100644 --- a/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp +++ b/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp @@ -8173,7 +8173,7 @@ void SIInstrInfo::moveToVALU(SIInstrWorklist &Worklist, "Deferred MachineInstr are not supposed to re-populate worklist"); } - for (std::pair<MachineInstr *, V2PhysSCopyInfo> &Entry : WaterFalls) { + for (auto &Entry : WaterFalls) { if (Entry.first->getOpcode() == AMDGPU::SI_CALL_ISEL) createWaterFallForSiCall(Entry.first, MDT, Entry.second.MOs, Entry.second.SGPRs); diff --git a/llvm/lib/Transforms/Scalar/GVNSink.cpp b/llvm/lib/Transforms/Scalar/GVNSink.cpp index 67196ef9715f1..eb7a9c68b5b61 100644 --- a/llvm/lib/Transforms/Scalar/GVNSink.cpp +++ b/llvm/lib/Transforms/Scalar/GVNSink.cpp @@ -606,7 +606,10 @@ GVNSink::analyzeInstructionForSinking(LockstepReverseIterator<false> &LRI, return std::nullopt; VNums[N]++; } - unsigned VNumToSink = llvm::max_element(VNums, llvm::less_second())->first; + unsigned VNumToSink = + llvm::max_element(VNums, [](const auto &L, const auto &R) { + return L.second < R.second; + })->first; if (VNums[VNumToSink] == 1) // Can't sink anything! diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index 1b3473fa0ec2d..9ff486cbc2cff 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -474,6 +474,15 @@ TEST(DenseMapCustomTest, EqualityComparison) { EXPECT_NE(M1, M3); } +using IntBucket = detail::DenseMapPair<int, int>; + +static_assert(std::is_trivially_copyable_v<IntBucket>); +static_assert(!std::is_trivially_default_constructible_v<IntBucket>); + +// A bucket converts to a std::pair, so code naming the pair type keeps working. +static_assert(std::is_convertible_v<IntBucket, std::pair<int, int>>); +static_assert(std::is_convertible_v<IntBucket, std::pair<const int, int>>); + TEST(DenseMapCustomTest, InsertRange) { DenseMap<int, int> M; @@ -483,6 +492,44 @@ TEST(DenseMapCustomTest, InsertRange) { EXPECT_EQ(M.size(), 2u); EXPECT_THAT(M, testing::UnorderedElementsAre(testing::Pair(0, 0), testing::Pair(1, 2))); + + // A move iterator yields an rvalue from operator*, which the range insert + // must forward to the members for a move-only value to survive. + std::vector<std::pair<int, std::unique_ptr<int>>> MoveOnly; + MoveOnly.emplace_back(3, std::make_unique<int>(42)); + DenseMap<int, std::unique_ptr<int>> MoveMap; + MoveMap.insert(std::make_move_iterator(MoveOnly.begin()), + std::make_move_iterator(MoveOnly.end())); + auto It = MoveMap.find(3); + ASSERT_NE(It, MoveMap.end()); + EXPECT_EQ(*It->second, 42); + EXPECT_EQ(MoveOnly[0].second, nullptr); + + // A move iterator over a map yields bucket rvalues instead, which must reach + // insert(BucketT &&) rather than be copied. + DenseMap<int, std::unique_ptr<int>> MoveSrc; + MoveSrc.try_emplace(4, std::make_unique<int>(7)); + MoveMap.insert(std::make_move_iterator(MoveSrc.begin()), + std::make_move_iterator(MoveSrc.end())); + EXPECT_EQ(*MoveMap.find(4)->second, 7); + EXPECT_EQ(MoveSrc.find(4)->second, nullptr); + + // The conversion reaches a vector's element type, and a std::map's, whose key + // is const. + DenseMap<int, int> Src({{1, 10}, {2, 20}}); + SmallVector<std::pair<int, int>> Vec(Src.begin(), Src.end()); + EXPECT_THAT(Vec, testing::UnorderedElementsAre(testing::Pair(1, 10), + testing::Pair(2, 20))); + std::map<int, int> Sorted(Src.begin(), Src.end()); + EXPECT_THAT(Sorted, + testing::ElementsAre(testing::Pair(1, 10), testing::Pair(2, 20))); + + // As polly inserts a DenseMap<BasicBlock *, BasicBlock *> into a + // DenseMap<AssertingVH<Value>, AssertingVH<Value>>, insert from a map whose + // key and value types only convert to this one's. + DenseMap<CtorTester, CtorTester, CtorTesterMapInfo> Convertible; + Convertible.insert_range(DenseMap<uint32_t, uint32_t>({{1, 10}})); + EXPECT_EQ(CtorTester(10), Convertible.lookup(CtorTester(1))); } TEST(SmallDenseMapCustomTest, InsertRange) { @@ -1149,6 +1196,12 @@ TEST(DenseMapCustomTest, RemoveIfValueDtor) { EXPECT_EQ(0u, CtorTester::getNumConstructed()); } +TEST(DenseMapCustomTest, BucketComparison) { + IntBucket A(1, 2), B(1, 2), C(1, 3); + EXPECT_EQ(A, B); + EXPECT_NE(A, C); +} + #if LLVM_ENABLE_ABI_BREAKING_CHECKS TEST(DenseMapCustomTest, EraseInvalidatesIterators) { DenseMap<int, int> M; diff --git a/llvm/utils/lldbDataFormatters.py b/llvm/utils/lldbDataFormatters.py index 1899f3acbe21b..d1765f87b52f4 100644 --- a/llvm/utils/lldbDataFormatters.py +++ b/llvm/utils/lldbDataFormatters.py @@ -465,16 +465,6 @@ def num_children(self) -> int: def get_child_at_index(self, child_index: int) -> lldb.SBValue: bucket_index = self.child_buckets[child_index] entry = self.valobj.GetValueForExpressionPath(f".Buckets[{bucket_index}]") - - # By default, DenseMap instances use DenseMapPair to hold key-value - # entries. When the entry is a DenseMapPair, unwrap it to expose the - # children as simple std::pair values. - # - # This entry type is customizable (a template parameter). For other - # types, expose the entry type as is. - if entry.type.name.startswith("llvm::detail::DenseMapPair<"): - entry = entry.GetChildAtIndex(0) - return entry.Clone(f"[{child_index}]") def update(self): diff --git a/third-party/unittest/googletest/include/gtest/internal/custom/gtest-printers.h b/third-party/unittest/googletest/include/gtest/internal/custom/gtest-printers.h index 06f85f89a5cb5..8a9ce020de20d 100644 --- a/third-party/unittest/googletest/include/gtest/internal/custom/gtest-printers.h +++ b/third-party/unittest/googletest/include/gtest/internal/custom/gtest-printers.h @@ -65,13 +65,14 @@ inline void PrintTo(const SmallVectorImpl<char> &S, std::ostream *OS) { *OS << ::testing::PrintToString(std::string(S.data(), S.size())); } -// DenseMap's entries inherit from std::pair, and should act like pairs. -// However gTest's provided `PrintTo(pair<K,V>)` template won't deduce K and V -// because of the needed derived-to-base conversion. +// gTest's provided `PrintTo(pair<K,V>)` template won't deduce K and V from a +// DenseMap entry. Print the members rather than converting, which would copy +// them and so require both to be copyable. namespace detail { template <typename K, typename V> inline void PrintTo(const DenseMapPair<K, V> &Pair, std::ostream *OS) { - *OS << ::testing::PrintToString(static_cast<const std::pair<K, V> &>(Pair)); + *OS << "(" << ::testing::PrintToString(Pair.first) << ", " + << ::testing::PrintToString(Pair.second) << ")"; } } // namespace detail _______________________________________________ lldb-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
