https://github.com/MaskRay updated https://github.com/llvm/llvm-project/pull/221853
>From 7add1b87468fc953e2545e0697913d9a78f93129 Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Mon, 7 Sep 2026 15:29:35 -0700 Subject: [PATCH 1/9] [ADT] Give DenseMapPair its own members instead of a std::pair base. NFC Some fast paths check `std::is_trivially_copyable_v<KeyT> && std::is_trivially_copyable_v<ValueT>` instead of the bucket type, because std::pair has a non-trivial copy assignment (which costs trivial copyability). Hold the members directly, making the bucket trivially copyable. instructions:u in a stage-2 clang build decreases by 0.35%, likely due to saving std::pair instantiations (std::pair implementations have expensive `enable_if`) --- clang/lib/Sema/SemaAttr.cpp | 2 +- llvm/include/llvm/ADT/DenseMap.h | 54 +++++++++++++------ llvm/lib/CodeGen/RegisterUsageInfo.cpp | 2 +- llvm/lib/MC/StringTableBuilder.cpp | 2 +- llvm/lib/MCA/HardwareUnits/LSUnit.cpp | 2 +- .../lib/MCA/HardwareUnits/ResourceManager.cpp | 2 +- llvm/lib/Transforms/Scalar/GVNHoist.cpp | 2 +- llvm/lib/Transforms/Scalar/GVNSink.cpp | 5 +- .../Transforms/Vectorize/SLPVectorizer.cpp | 4 +- mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp | 5 +- 10 files changed, 50 insertions(+), 30 deletions(-) diff --git a/clang/lib/Sema/SemaAttr.cpp b/clang/lib/Sema/SemaAttr.cpp index 67573c9f1c72a..35d14a4444595 100644 --- a/clang/lib/Sema/SemaAttr.cpp +++ b/clang/lib/Sema/SemaAttr.cpp @@ -1074,7 +1074,7 @@ void Sema::ActOnPragmaAttributeAttribute( // variable(is_parameter). // - a sub-rule and a sibling that's negated. E.g. // variable(is_thread_local) and variable(unless(is_parameter)) - llvm::SmallDenseMap<int, std::pair<int, SourceRange>, 2> + llvm::SmallDenseMap<int, attr::ParsedSubjectMatchRuleSet::value_type, 2> RulesToFirstSpecifiedNegatedSubRule; for (const auto &Rule : Rules) { attr::SubjectMatchRule MatchRule = attr::SubjectMatchRule(Rule.first); diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index 3073ab0ec9712..5ea7ce2aeff85 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -44,17 +44,39 @@ 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)) {} + + 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 @@ -330,7 +352,7 @@ class DenseMapBase : public DebugEpochBase { /// Range insertion of pairs. template <typename InputIt> void insert(InputIt I, InputIt E) { for (; I != E; ++I) - insert(*I); + try_emplace(I->first, I->second); } /// Inserts range of 'std::pair<KeyT, ValueT>' values into the map. @@ -462,10 +484,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 +576,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/CodeGen/RegisterUsageInfo.cpp b/llvm/lib/CodeGen/RegisterUsageInfo.cpp index 38e4c30ceb634..d139bd430fb20 100644 --- a/llvm/lib/CodeGen/RegisterUsageInfo.cpp +++ b/llvm/lib/CodeGen/RegisterUsageInfo.cpp @@ -70,7 +70,7 @@ PhysicalRegisterUsageInfo::getRegUsageInfo(const Function &FP) { } void PhysicalRegisterUsageInfo::print(raw_ostream &OS, const Module *M) const { - using FuncPtrRegMaskPair = std::pair<const Function *, std::vector<uint32_t>>; + using FuncPtrRegMaskPair = decltype(RegMasks)::value_type; // Create a vector of pointer to RegMasks entries SmallVector<const FuncPtrRegMaskPair *, 64> FPRMPairVector( diff --git a/llvm/lib/MC/StringTableBuilder.cpp b/llvm/lib/MC/StringTableBuilder.cpp index eb1a62f1f6412..39d10ad128ed7 100644 --- a/llvm/lib/MC/StringTableBuilder.cpp +++ b/llvm/lib/MC/StringTableBuilder.cpp @@ -66,7 +66,7 @@ void StringTableBuilder::write(raw_ostream &OS) const { OS << Data; } -using StringPair = std::pair<CachedHashStringRef, size_t>; +using StringPair = DenseMap<CachedHashStringRef, size_t>::value_type; void StringTableBuilder::write(uint8_t *Buf) const { assert(isFinalized()); diff --git a/llvm/lib/MCA/HardwareUnits/LSUnit.cpp b/llvm/lib/MCA/HardwareUnits/LSUnit.cpp index bf0b432524881..f88f82a7f5279 100644 --- a/llvm/lib/MCA/HardwareUnits/LSUnit.cpp +++ b/llvm/lib/MCA/HardwareUnits/LSUnit.cpp @@ -42,7 +42,7 @@ LSUnitBase::LSUnitBase(const MCSchedModel &SM, unsigned LQ, unsigned SQ, LSUnitBase::~LSUnitBase() = default; void LSUnit::cycleEvent() { - for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups) + for (const auto &G : Groups) G.second->cycleEvent(); } diff --git a/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp b/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp index cdf3439e07d61..12d062ab6ff9f 100644 --- a/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp +++ b/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp @@ -473,7 +473,7 @@ void ResourceManager::fastIssueInstruction( } void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) { - for (std::pair<ResourceRef, unsigned> &BR : BusyResources) { + for (auto &BR : BusyResources) { if (BR.second) BR.second--; if (!BR.second) { diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp index 37562a024a2b0..6bb6d6772fbfb 100644 --- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp +++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp @@ -835,7 +835,7 @@ void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs, // CHIArgs now have the outgoing values, so check for anticipability and // accumulate hoistable candidates in HPL. - for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) { + for (auto &A : CHIBBs) { BasicBlock *BB = A.first; SmallVectorImpl<CHIArg> &CHIs = A.second; // Vector of PHIs contains PHIs for different instructions. 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/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index 5de71f3bf87b5..d6edb1a2cee80 100644 --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -4480,9 +4480,7 @@ class slpvectorizer::BoUpSLP { } while (It != P.first->Scalars.end()); } return all_of(PotentiallyReorderedEntriesCount, - [&](const std::pair<const TreeEntry *, unsigned> &P) { - return P.second == NumOps - 1; - }); + [&](const auto &P) { return P.second == NumOps - 1; }); } SmallVector<ScheduleCopyableData *> diff --git a/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp b/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp index 370457c85e797..1fbadcc4eff72 100644 --- a/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp +++ b/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp @@ -760,9 +760,8 @@ ParallelToGpuLaunchLowering::matchAndRewrite(ParallelOp parallelOp, // Now that we succeeded creating the launch operation, also update the // bounds. - for (auto bound : launchBounds) - launchOp.setOperand(getLaunchOpArgumentNum(std::get<0>(bound)), - std::get<1>(bound)); + for (const auto &bound : launchBounds) + launchOp.setOperand(getLaunchOpArgumentNum(bound.first), bound.second); rewriter.eraseOp(parallelOp); return success(); >From 5639a88fcd38f6717a6c6f41ada3e0e77f4fab60 Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Mon, 7 Sep 2026 19:23:06 -0700 Subject: [PATCH 2/9] explicit operator pair --- clang/lib/AST/VTableBuilder.cpp | 2 +- clang/lib/Serialization/ASTWriter.cpp | 2 +- llvm/include/llvm/ADT/DenseMap.h | 18 +++++++++++---- llvm/lib/Bitcode/Reader/MetadataLoader.cpp | 2 +- llvm/lib/Bitcode/Writer/BitcodeWriter.cpp | 2 +- llvm/lib/CodeGen/StackColoring.cpp | 2 +- llvm/lib/IR/AsmWriter.cpp | 2 +- llvm/lib/Transforms/IPO/ArgumentPromotion.cpp | 3 ++- llvm/lib/Transforms/IPO/FunctionAttrs.cpp | 3 ++- llvm/lib/Transforms/IPO/SampleProfile.cpp | 3 +-- llvm/lib/Transforms/Scalar/StructurizeCFG.cpp | 5 ++--- llvm/lib/Transforms/Utils/Local.cpp | 2 +- llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 2 +- llvm/lib/Transforms/Utils/SplitModule.cpp | 2 +- .../Transforms/Vectorize/SLPVectorizer.cpp | 4 +--- llvm/unittests/ADT/DenseMapTest.cpp | 22 +++++++++++++++++++ mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp | 2 +- mlir/lib/IR/PDL/PDLPatternMatch.cpp | 2 +- 18 files changed, 55 insertions(+), 25 deletions(-) diff --git a/clang/lib/AST/VTableBuilder.cpp b/clang/lib/AST/VTableBuilder.cpp index 3c05d4b22b03e..bef4c7d6869d6 100644 --- a/clang/lib/AST/VTableBuilder.cpp +++ b/clang/lib/AST/VTableBuilder.cpp @@ -3730,7 +3730,7 @@ void MicrosoftVTableContext::computeVTableRelatedInformation( const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); for (const auto &Loc : Builder.vtable_locations()) { - auto Insert = NewMethodLocations.insert(Loc); + auto Insert = NewMethodLocations.try_emplace(Loc.first, Loc.second); if (!Insert.second) { const MethodVFTableLocation &NewLoc = Loc.second; MethodVFTableLocation &OldLoc = Insert.first->second; diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp index de985b770cb01..d5a4ab3cfd2f2 100644 --- a/clang/lib/Serialization/ASTWriter.cpp +++ b/clang/lib/Serialization/ASTWriter.cpp @@ -3352,7 +3352,7 @@ void ASTWriter::WritePragmaDiagnosticMappings(const DiagnosticsEngine &Diag, if (!I.second.isPragma() && I.second == Diag.getDiagnosticIDs()->getDefaultMapping(I.first)) continue; - Mappings.push_back(I); + Mappings.emplace_back(I.first, I.second); } // Sort by diag::kind for deterministic output. diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index 5ea7ce2aeff85..a03dbe1564cea 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -63,8 +63,13 @@ template <typename KeyT, typename ValueT> struct DenseMapPair { DenseMapPair(std::pair<KeyT, ValueT> &&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}; } + template <typename K, typename V, + std::enable_if_t<std::is_constructible_v<K, const KeyT &> && + std::is_constructible_v<V, const ValueT &>, + int> = 0> + explicit operator std::pair<K, V>() const { + return {first, second}; + } friend bool operator==(const DenseMapPair &LHS, const DenseMapPair &RHS) { return LHS.first == RHS.first && LHS.second == RHS.second; @@ -351,8 +356,13 @@ class DenseMapBase : public DebugEpochBase { /// Range insertion of pairs. template <typename InputIt> void insert(InputIt I, InputIt E) { - for (; I != E; ++I) - try_emplace(I->first, I->second); + for (; I != E; ++I) { + // Take the members rather than converting: a move iterator's operator* + // yields an rvalue, which forwarding carries through to each member. + auto &&KV = *I; + try_emplace(std::forward<decltype(KV)>(KV).first, + std::forward<decltype(KV)>(KV).second); + } } /// Inserts range of 'std::pair<KeyT, ValueT>' values into the map. diff --git a/llvm/lib/Bitcode/Reader/MetadataLoader.cpp b/llvm/lib/Bitcode/Reader/MetadataLoader.cpp index f4ebfce24b016..0ed0817c46ec8 100644 --- a/llvm/lib/Bitcode/Reader/MetadataLoader.cpp +++ b/llvm/lib/Bitcode/Reader/MetadataLoader.cpp @@ -242,7 +242,7 @@ void BitcodeReaderMetadataList::tryToResolveCycles() { // Give up on finding a full definition for any forward decls that remain. for (const auto &Ref : OldTypeRefs.FwdDecls) - OldTypeRefs.Final.insert(Ref); + OldTypeRefs.Final.try_emplace(Ref.first, Ref.second); OldTypeRefs.FwdDecls.clear(); // Upgrade from old type ref arrays. In strange cases, this could add to diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp index 859e073b91cc5..0636b222e0441 100644 --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -580,7 +580,7 @@ class IndexBitcodeWriter : public BitcodeWriterBase { if (ModuleToSummariesForIndex) { for (auto &M : *ModuleToSummariesForIndex) for (auto &Summary : M.second) { - Callback(Summary, false); + Callback({Summary.first, Summary.second}, false); // Ensure aliasee is handled, e.g. for assigning a valueId, // even if we are not importing the aliasee directly (the // imported alias will contain a copy of aliasee). diff --git a/llvm/lib/CodeGen/StackColoring.cpp b/llvm/lib/CodeGen/StackColoring.cpp index aa42c0ee28532..0e4c1526d0d0b 100644 --- a/llvm/lib/CodeGen/StackColoring.cpp +++ b/llvm/lib/CodeGen/StackColoring.cpp @@ -927,7 +927,7 @@ void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { // Keep a list of allocas which has been affected by the remap. SmallPtrSet<const AllocaInst*, 32> MergedAllocas; - for (const std::pair<int, int> &SI : SlotRemap) { + for (const auto &SI : SlotRemap) { const AllocaInst *From = MFI->getObjectAllocation(SI.first); const AllocaInst *To = MFI->getObjectAllocation(SI.second); assert(To && From && "Invalid allocation object"); diff --git a/llvm/lib/IR/AsmWriter.cpp b/llvm/lib/IR/AsmWriter.cpp index 8e57bff1d36c9..e101c5524f5c3 100644 --- a/llvm/lib/IR/AsmWriter.cpp +++ b/llvm/lib/IR/AsmWriter.cpp @@ -5145,7 +5145,7 @@ void AssemblyWriter::writeAllAttributeGroups() { asVec.resize(Machine.as_size()); for (auto &I : llvm::make_range(Machine.as_begin(), Machine.as_end())) - asVec[I.second] = I; + asVec[I.second] = {I.first, I.second}; for (const auto &I : asVec) Out << "attributes #" << I.second << " = { " diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp index 51821dd7f23bb..9399b15eb3a75 100644 --- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -732,7 +732,8 @@ static bool findArgParts(Argument *Arg, const DataLayout &DL, AAResults &AAR, return true; // No users, this is a dead argument. // Sort parts by offset. - append_range(ArgPartsVec, ArgParts); + for (const auto &Part : ArgParts) + ArgPartsVec.emplace_back(Part.first, Part.second); sort(ArgPartsVec, llvm::less_first()); // Make sure the parts are non-overlapping. diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp index a713ead683476..708522bb61344 100644 --- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp @@ -1157,7 +1157,8 @@ static bool inferInitializes(Argument &A, Function &F) { if (UPB != UsesPerBlock.end()) { // Sort uses in this block by instruction order. SmallVector<std::pair<Instruction *, ArgumentAccessInfo>, 2> Insts; - append_range(Insts, UPB->second.Insts); + for (const auto &Inst : UPB->second.Insts) + Insts.emplace_back(Inst.first, Inst.second); sort(Insts, [](std::pair<Instruction *, ArgumentAccessInfo> &LHS, std::pair<Instruction *, ArgumentAccessInfo> &RHS) { return LHS.first->comesBefore(RHS.first); diff --git a/llvm/lib/Transforms/IPO/SampleProfile.cpp b/llvm/lib/Transforms/IPO/SampleProfile.cpp index cb11372183bc8..227a2a4ed9221 100644 --- a/llvm/lib/Transforms/IPO/SampleProfile.cpp +++ b/llvm/lib/Transforms/IPO/SampleProfile.cpp @@ -2205,8 +2205,7 @@ bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager &AM, // Account for cold calls not inlined.... if (!FunctionSamples::ProfileIsCS) - for (const std::pair<Function *, NotInlinedProfileInfo> &pair : - notInlinedCallInfo) + for (const auto &pair : notInlinedCallInfo) updateProfileCallee(pair.first, pair.second.entryCount); if (RemoveProbeAfterProfileAnnotation && diff --git a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp index 9707eee005c56..9b9889b911eee 100644 --- a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp +++ b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp @@ -1135,9 +1135,8 @@ void StructurizeCFG::setPrevNode(BasicBlock *BB) { /// Does BB dominate all the predicates of Node? bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { BBPredicates &Preds = Predicates[Node->getEntry()]; - return llvm::all_of(Preds, [&](std::pair<BasicBlock *, PredInfo> Pred) { - return DT->dominates(BB, Pred.first); - }); + return llvm::all_of( + Preds, [&](const auto &Pred) { return DT->dominates(BB, Pred.first); }); } /// Can we predict that this node will always be called? diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index b88e506ae681a..f08f1e4868091 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -2852,7 +2852,7 @@ static bool markAliveBlocks(Function &F, SmallVectorImpl<bool> &Reachable, } if (DTU) { std::vector<DominatorTree::UpdateType> Updates; - for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases) + for (const auto &I : NumPerSuccessorCases) if (I.second == 0) Updates.push_back({DominatorTree::Delete, BB, I.first}); DTU->applyUpdates(Updates); diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index cc2c769b25ce9..ca96f2e70d810 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -1053,7 +1053,7 @@ bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor( if (DTU) { std::vector<DominatorTree::UpdateType> Updates; - for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases) + for (const auto &I : NumPerSuccessorCases) if (I.second == 0) Updates.push_back({DominatorTree::Delete, PredDef, I.first}); DTU->applyUpdates(Updates); diff --git a/llvm/lib/Transforms/Utils/SplitModule.cpp b/llvm/lib/Transforms/Utils/SplitModule.cpp index 8e70902c4dac2..a73b34fab462a 100644 --- a/llvm/lib/Transforms/Utils/SplitModule.cpp +++ b/llvm/lib/Transforms/Utils/SplitModule.cpp @@ -278,7 +278,7 @@ void llvm::SplitModule( for (unsigned I = 0; I < N; ++I) { if (auto It = ModuleFunctionCount.find(I); It != ModuleFunctionCount.end()) - BalancingQueue.push(*It); + BalancingQueue.emplace(It->first, It->second); else BalancingQueue.push({I, 0}); } diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index d6edb1a2cee80..323442be1c8a7 100644 --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -11632,9 +11632,7 @@ class InstructionsCompatibilityAnalysis { ++Counters[V]; } if (Counters.size() == 2 && - any_of(Counters, [&](const std::pair<const Value *, unsigned> &C) { - return C.second == 1; - })) + any_of(Counters, [&](const auto &C) { return C.second == 1; })) return true; } // First operand not a constant or splat? Last attempt - check for diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index 1b3473fa0ec2d..65e9fdad5686a 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -16,10 +16,12 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" #include <map> +#include <memory> #include <optional> #include <set> #include <utility> #include <variant> +#include <vector> using namespace llvm; @@ -474,6 +476,14 @@ TEST(DenseMapCustomTest, EqualityComparison) { EXPECT_NE(M1, M3); } +// Converting a bucket to a std::pair copies both members, so it must not happen +// implicitly: `const std::pair<int, int> &P = *M.begin();` would bind to a +// temporary rather than the bucket. +static_assert(!std::is_convertible_v<detail::DenseMapPair<int, int>, + std::pair<int, int>>); +static_assert(std::is_constructible_v<std::pair<int, int>, + detail::DenseMapPair<int, int>>); + TEST(DenseMapCustomTest, InsertRange) { DenseMap<int, int> M; @@ -483,6 +493,18 @@ 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); } TEST(SmallDenseMapCustomTest, InsertRange) { diff --git a/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp b/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp index c38213850c6ea..9aebea1e1d72e 100644 --- a/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp +++ b/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp @@ -188,7 +188,7 @@ AffineMap mlir::makePermutationMap( for (auto *forInst : enclosingLoops) { auto it = loopToVectorDim.find(forInst); if (it != loopToVectorDim.end()) { - enclosingLoopToVectorDim.insert(*it); + enclosingLoopToVectorDim.try_emplace(it->first, it->second); } } return ::makePermutationMap(indices, enclosingLoopToVectorDim); diff --git a/mlir/lib/IR/PDL/PDLPatternMatch.cpp b/mlir/lib/IR/PDL/PDLPatternMatch.cpp index 62a71aa2c1daa..cc547d859adf4 100644 --- a/mlir/lib/IR/PDL/PDLPatternMatch.cpp +++ b/mlir/lib/IR/PDL/PDLPatternMatch.cpp @@ -83,7 +83,7 @@ void PDLPatternModule::mergeIn(PDLPatternModule &&other) { for (auto &it : other.configs) configs.emplace_back(std::move(it)); for (auto &it : other.configMap) - configMap.insert(it); + configMap.try_emplace(it.first, it.second); // Steal the other state if we have no patterns. if (!pdlModule) { >From e68ddbfc91a13efff72b6da74c61b606b381f6aa Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Mon, 7 Sep 2026 19:55:13 -0700 Subject: [PATCH 3/9] explicit operator pair --- llvm/include/llvm/ADT/DenseMap.h | 7 ++----- llvm/unittests/ADT/DenseMapTest.cpp | 26 ++++++++++++++++++++++---- 2 files changed, 24 insertions(+), 9 deletions(-) diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index a03dbe1564cea..a2ed4c00204c1 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -63,11 +63,8 @@ template <typename KeyT, typename ValueT> struct DenseMapPair { DenseMapPair(std::pair<KeyT, ValueT> &&P) : first(std::move(P.first)), second(std::move(P.second)) {} - template <typename K, typename V, - std::enable_if_t<std::is_constructible_v<K, const KeyT &> && - std::is_constructible_v<V, const ValueT &>, - int> = 0> - explicit operator std::pair<K, V>() const { + explicit operator std::pair<KeyT, ValueT>() const { return {first, second}; } + explicit operator std::pair<const KeyT, ValueT>() const { return {first, second}; } diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index 65e9fdad5686a..996ce78196013 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -476,13 +476,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>); + // Converting a bucket to a std::pair copies both members, so it must not happen // implicitly: `const std::pair<int, int> &P = *M.begin();` would bind to a // temporary rather than the bucket. -static_assert(!std::is_convertible_v<detail::DenseMapPair<int, int>, - std::pair<int, int>>); -static_assert(std::is_constructible_v<std::pair<int, int>, - detail::DenseMapPair<int, int>>); +static_assert(!std::is_convertible_v<IntBucket, std::pair<int, int>>); TEST(DenseMapCustomTest, InsertRange) { DenseMap<int, int> M; @@ -505,6 +507,16 @@ TEST(DenseMapCustomTest, InsertRange) { ASSERT_NE(It, MoveMap.end()); EXPECT_EQ(*It->second, 42); EXPECT_EQ(MoveOnly[0].second, nullptr); + + // Converting a bucket explicitly still 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))); } TEST(SmallDenseMapCustomTest, InsertRange) { @@ -1217,4 +1229,10 @@ TEST(DenseMapCustomTest, MoveAssignInvalidatesIterators) { } #endif +TEST(DenseMapCustomTest, BucketComparison) { + IntBucket A(1, 2), B(1, 2), C(1, 3); + EXPECT_EQ(A, B); + EXPECT_NE(A, C); +} + } // namespace >From 3d888b01d06f3575229d7876cad0102d5886712a Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Mon, 7 Sep 2026 20:04:02 -0700 Subject: [PATCH 4/9] adopt structured bindings --- llvm/lib/Bitcode/Reader/MetadataLoader.cpp | 4 ++-- llvm/lib/Bitcode/Writer/BitcodeWriter.cpp | 6 +++--- llvm/lib/Transforms/IPO/ArgumentPromotion.cpp | 4 ++-- llvm/lib/Transforms/IPO/FunctionAttrs.cpp | 4 ++-- llvm/lib/Transforms/IPO/SampleProfile.cpp | 4 ++-- mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp | 4 ++-- mlir/lib/IR/PDL/PDLPatternMatch.cpp | 3 +-- 7 files changed, 14 insertions(+), 15 deletions(-) diff --git a/llvm/lib/Bitcode/Reader/MetadataLoader.cpp b/llvm/lib/Bitcode/Reader/MetadataLoader.cpp index 0ed0817c46ec8..6f1fbd627edbc 100644 --- a/llvm/lib/Bitcode/Reader/MetadataLoader.cpp +++ b/llvm/lib/Bitcode/Reader/MetadataLoader.cpp @@ -241,8 +241,8 @@ void BitcodeReaderMetadataList::tryToResolveCycles() { return; // Give up on finding a full definition for any forward decls that remain. - for (const auto &Ref : OldTypeRefs.FwdDecls) - OldTypeRefs.Final.try_emplace(Ref.first, Ref.second); + for (const auto &[UUID, CT] : OldTypeRefs.FwdDecls) + OldTypeRefs.Final.try_emplace(UUID, CT); OldTypeRefs.FwdDecls.clear(); // Upgrade from old type ref arrays. In strange cases, this could add to diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp index 0636b222e0441..e33b6e0050318 100644 --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -579,12 +579,12 @@ class IndexBitcodeWriter : public BitcodeWriterBase { void forEachSummary(Functor Callback) { if (ModuleToSummariesForIndex) { for (auto &M : *ModuleToSummariesForIndex) - for (auto &Summary : M.second) { - Callback({Summary.first, Summary.second}, false); + for (auto &[GUID, GVS] : M.second) { + Callback({GUID, GVS}, false); // Ensure aliasee is handled, e.g. for assigning a valueId, // even if we are not importing the aliasee directly (the // imported alias will contain a copy of aliasee). - if (auto *AS = dyn_cast<AliasSummary>(Summary.getSecond())) + if (auto *AS = dyn_cast<AliasSummary>(GVS)) Callback({AS->getAliaseeGUID(), &AS->getAliasee()}, true); } } else { diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp index 9399b15eb3a75..a63e8245dd4b5 100644 --- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -732,8 +732,8 @@ static bool findArgParts(Argument *Arg, const DataLayout &DL, AAResults &AAR, return true; // No users, this is a dead argument. // Sort parts by offset. - for (const auto &Part : ArgParts) - ArgPartsVec.emplace_back(Part.first, Part.second); + for (const auto &[Offset, Part] : ArgParts) + ArgPartsVec.emplace_back(Offset, Part); sort(ArgPartsVec, llvm::less_first()); // Make sure the parts are non-overlapping. diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp index 708522bb61344..af393e8657fc9 100644 --- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp @@ -1157,8 +1157,8 @@ static bool inferInitializes(Argument &A, Function &F) { if (UPB != UsesPerBlock.end()) { // Sort uses in this block by instruction order. SmallVector<std::pair<Instruction *, ArgumentAccessInfo>, 2> Insts; - for (const auto &Inst : UPB->second.Insts) - Insts.emplace_back(Inst.first, Inst.second); + for (const auto &[I, Info] : UPB->second.Insts) + Insts.emplace_back(I, Info); sort(Insts, [](std::pair<Instruction *, ArgumentAccessInfo> &LHS, std::pair<Instruction *, ArgumentAccessInfo> &RHS) { return LHS.first->comesBefore(RHS.first); diff --git a/llvm/lib/Transforms/IPO/SampleProfile.cpp b/llvm/lib/Transforms/IPO/SampleProfile.cpp index 227a2a4ed9221..cd9549cd2f0cc 100644 --- a/llvm/lib/Transforms/IPO/SampleProfile.cpp +++ b/llvm/lib/Transforms/IPO/SampleProfile.cpp @@ -2205,8 +2205,8 @@ bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager &AM, // Account for cold calls not inlined.... if (!FunctionSamples::ProfileIsCS) - for (const auto &pair : notInlinedCallInfo) - updateProfileCallee(pair.first, pair.second.entryCount); + for (const auto &[Fn, Info] : notInlinedCallInfo) + updateProfileCallee(Fn, Info.entryCount); if (RemoveProbeAfterProfileAnnotation && FunctionSamples::ProfileIsProbeBased) { diff --git a/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp b/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp index 1fbadcc4eff72..796083062ac72 100644 --- a/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp +++ b/mlir/lib/Conversion/SCFToGPU/SCFToGPU.cpp @@ -760,8 +760,8 @@ ParallelToGpuLaunchLowering::matchAndRewrite(ParallelOp parallelOp, // Now that we succeeded creating the launch operation, also update the // bounds. - for (const auto &bound : launchBounds) - launchOp.setOperand(getLaunchOpArgumentNum(bound.first), bound.second); + for (const auto &[processor, bound] : launchBounds) + launchOp.setOperand(getLaunchOpArgumentNum(processor), bound); rewriter.eraseOp(parallelOp); return success(); diff --git a/mlir/lib/IR/PDL/PDLPatternMatch.cpp b/mlir/lib/IR/PDL/PDLPatternMatch.cpp index cc547d859adf4..ceaced2610b6e 100644 --- a/mlir/lib/IR/PDL/PDLPatternMatch.cpp +++ b/mlir/lib/IR/PDL/PDLPatternMatch.cpp @@ -82,8 +82,7 @@ void PDLPatternModule::mergeIn(PDLPatternModule &&other) { registerRewriteFunction(it.first(), std::move(it.second)); for (auto &it : other.configs) configs.emplace_back(std::move(it)); - for (auto &it : other.configMap) - configMap.try_emplace(it.first, it.second); + configMap.insert_range(other.configMap); // Steal the other state if we have no patterns. if (!pdlModule) { >From de1e10655a3df4626d22078fa52d5d20670060a3 Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Mon, 7 Sep 2026 22:04:52 -0700 Subject: [PATCH 5/9] Use Vec.append(x.begin(), x.end()) instead of append_range --- llvm/lib/Transforms/IPO/ArgumentPromotion.cpp | 3 +-- llvm/lib/Transforms/IPO/FunctionAttrs.cpp | 3 +-- llvm/unittests/ADT/DenseMapTest.cpp | 12 ++++++------ 3 files changed, 8 insertions(+), 10 deletions(-) diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp index a63e8245dd4b5..43eb005dfdbb3 100644 --- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -732,8 +732,7 @@ static bool findArgParts(Argument *Arg, const DataLayout &DL, AAResults &AAR, return true; // No users, this is a dead argument. // Sort parts by offset. - for (const auto &[Offset, Part] : ArgParts) - ArgPartsVec.emplace_back(Offset, Part); + ArgPartsVec.append(ArgParts.begin(), ArgParts.end()); sort(ArgPartsVec, llvm::less_first()); // Make sure the parts are non-overlapping. diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp index af393e8657fc9..e8925a6b0855e 100644 --- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp @@ -1157,8 +1157,7 @@ static bool inferInitializes(Argument &A, Function &F) { if (UPB != UsesPerBlock.end()) { // Sort uses in this block by instruction order. SmallVector<std::pair<Instruction *, ArgumentAccessInfo>, 2> Insts; - for (const auto &[I, Info] : UPB->second.Insts) - Insts.emplace_back(I, Info); + Insts.append(UPB->second.Insts.begin(), UPB->second.Insts.end()); sort(Insts, [](std::pair<Instruction *, ArgumentAccessInfo> &LHS, std::pair<Instruction *, ArgumentAccessInfo> &RHS) { return LHS.first->comesBefore(RHS.first); diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index 996ce78196013..1dc0419ebd94a 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -1183,6 +1183,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; @@ -1229,10 +1235,4 @@ TEST(DenseMapCustomTest, MoveAssignInvalidatesIterators) { } #endif -TEST(DenseMapCustomTest, BucketComparison) { - IntBucket A(1, 2), B(1, 2), C(1, 3); - EXPECT_EQ(A, B); - EXPECT_NE(A, C); -} - } // namespace >From 1cf8c44d39178367a0ba62ab8f6b9f81f43a4a9c Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Tue, 8 Sep 2026 21:11:47 -0700 Subject: [PATCH 6/9] add an insert overload; drop mlir/ adaptation --- clang/lib/AST/VTableBuilder.cpp | 2 +- llvm/include/llvm/ADT/DenseMap.h | 29 ++++++++++++++----- llvm/unittests/ADT/DenseMapTest.cpp | 7 +++++ mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp | 2 +- 4 files changed, 31 insertions(+), 9 deletions(-) diff --git a/clang/lib/AST/VTableBuilder.cpp b/clang/lib/AST/VTableBuilder.cpp index bef4c7d6869d6..3c05d4b22b03e 100644 --- a/clang/lib/AST/VTableBuilder.cpp +++ b/clang/lib/AST/VTableBuilder.cpp @@ -3730,7 +3730,7 @@ void MicrosoftVTableContext::computeVTableRelatedInformation( const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); for (const auto &Loc : Builder.vtable_locations()) { - auto Insert = NewMethodLocations.try_emplace(Loc.first, Loc.second); + auto Insert = NewMethodLocations.insert(Loc); if (!Insert.second) { const MethodVFTableLocation &NewLoc = Loc.second; MethodVFTableLocation &OldLoc = Insert.first->second; diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index a2ed4c00204c1..664eac1d8027f 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -62,6 +62,12 @@ template <typename KeyT, typename ValueT> struct DenseMapPair { : 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)) {} explicit operator std::pair<KeyT, ValueT>() const { return {first, second}; } explicit operator std::pair<const KeyT, ValueT>() const { @@ -316,6 +322,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. @@ -353,13 +373,8 @@ class DenseMapBase : public DebugEpochBase { /// Range insertion of pairs. template <typename InputIt> void insert(InputIt I, InputIt E) { - for (; I != E; ++I) { - // Take the members rather than converting: a move iterator's operator* - // yields an rvalue, which forwarding carries through to each member. - auto &&KV = *I; - try_emplace(std::forward<decltype(KV)>(KV).first, - std::forward<decltype(KV)>(KV).second); - } + for (; I != E; ++I) + insert(*I); } /// Inserts range of 'std::pair<KeyT, ValueT>' values into the map. diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index 1dc0419ebd94a..0fb270b76bdd6 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -517,6 +517,13 @@ TEST(DenseMapCustomTest, InsertRange) { 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) { diff --git a/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp b/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp index 9aebea1e1d72e..c38213850c6ea 100644 --- a/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp +++ b/mlir/lib/Dialect/Vector/Utils/VectorUtils.cpp @@ -188,7 +188,7 @@ AffineMap mlir::makePermutationMap( for (auto *forInst : enclosingLoops) { auto it = loopToVectorDim.find(forInst); if (it != loopToVectorDim.end()) { - enclosingLoopToVectorDim.try_emplace(it->first, it->second); + enclosingLoopToVectorDim.insert(*it); } } return ::makePermutationMap(indices, enclosingLoopToVectorDim); >From 6302db181e74b26a2b15d1d382073aaf68ba3300 Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Tue, 8 Sep 2026 21:23:50 -0700 Subject: [PATCH 7/9] unittest --- llvm/unittests/ADT/DenseMapTest.cpp | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index 0fb270b76bdd6..f6f96dba75747 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -508,6 +508,15 @@ TEST(DenseMapCustomTest, InsertRange) { 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); + // Converting a bucket explicitly still reaches a vector's element type, and a // std::map's, whose key is const. DenseMap<int, int> Src({{1, 10}, {2, 20}}); >From a8a3a46c7f47e28d160d9ead4252f509874a2e32 Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Tue, 8 Sep 2026 22:14:19 -0700 Subject: [PATCH 8/9] apply Kazu changes --- llvm/lib/IR/AsmWriter.cpp | 5 +++-- llvm/unittests/ADT/DenseMapTest.cpp | 2 -- 2 files changed, 3 insertions(+), 4 deletions(-) diff --git a/llvm/lib/IR/AsmWriter.cpp b/llvm/lib/IR/AsmWriter.cpp index e101c5524f5c3..96918ec35fd7b 100644 --- a/llvm/lib/IR/AsmWriter.cpp +++ b/llvm/lib/IR/AsmWriter.cpp @@ -5144,8 +5144,9 @@ void AssemblyWriter::writeAllAttributeGroups() { std::vector<std::pair<AttributeSet, unsigned>> asVec; asVec.resize(Machine.as_size()); - for (auto &I : llvm::make_range(Machine.as_begin(), Machine.as_end())) - asVec[I.second] = {I.first, I.second}; + for (const auto &[AS, ID] : + llvm::make_range(Machine.as_begin(), Machine.as_end())) + asVec[ID] = {AS, ID}; for (const auto &I : asVec) Out << "attributes #" << I.second << " = { " diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index f6f96dba75747..d3b5e97e2bf6b 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -16,12 +16,10 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" #include <map> -#include <memory> #include <optional> #include <set> #include <utility> #include <variant> -#include <vector> using namespace llvm; >From 9e42f6961b382e777de8fcc6e79788e09ccbfc9c Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Tue, 8 Sep 2026 23:21:30 -0700 Subject: [PATCH 9/9] remove explicit on operator std::pair to avoid fixing some call sites for clang-cl --- clang/lib/Serialization/ASTWriter.cpp | 2 +- llvm/include/llvm/ADT/DenseMap.h | 6 ++---- llvm/lib/IR/AsmWriter.cpp | 5 ++--- llvm/lib/Target/AMDGPU/AMDGPURewriteOutArguments.cpp | 2 +- llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp | 6 ++++-- llvm/lib/Target/AMDGPU/SIInstrInfo.cpp | 2 +- llvm/lib/Transforms/IPO/ArgumentPromotion.cpp | 2 +- llvm/lib/Transforms/IPO/FunctionAttrs.cpp | 2 +- llvm/lib/Transforms/Utils/SplitModule.cpp | 2 +- llvm/unittests/ADT/DenseMapTest.cpp | 11 +++++------ 10 files changed, 19 insertions(+), 21 deletions(-) diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp index d5a4ab3cfd2f2..de985b770cb01 100644 --- a/clang/lib/Serialization/ASTWriter.cpp +++ b/clang/lib/Serialization/ASTWriter.cpp @@ -3352,7 +3352,7 @@ void ASTWriter::WritePragmaDiagnosticMappings(const DiagnosticsEngine &Diag, if (!I.second.isPragma() && I.second == Diag.getDiagnosticIDs()->getDefaultMapping(I.first)) continue; - Mappings.emplace_back(I.first, I.second); + Mappings.push_back(I); } // Sort by diag::kind for deterministic output. diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index 664eac1d8027f..0126935ca3598 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -69,10 +69,8 @@ template <typename KeyT, typename ValueT> struct DenseMapPair { DenseMapPair(DenseMapPair<U1, U2> &&P) : first(std::move(P.first)), second(std::move(P.second)) {} - explicit operator std::pair<KeyT, ValueT>() const { return {first, second}; } - explicit operator std::pair<const KeyT, ValueT>() const { - return {first, 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; diff --git a/llvm/lib/IR/AsmWriter.cpp b/llvm/lib/IR/AsmWriter.cpp index 96918ec35fd7b..8e57bff1d36c9 100644 --- a/llvm/lib/IR/AsmWriter.cpp +++ b/llvm/lib/IR/AsmWriter.cpp @@ -5144,9 +5144,8 @@ void AssemblyWriter::writeAllAttributeGroups() { std::vector<std::pair<AttributeSet, unsigned>> asVec; asVec.resize(Machine.as_size()); - for (const auto &[AS, ID] : - llvm::make_range(Machine.as_begin(), Machine.as_end())) - asVec[ID] = {AS, ID}; + for (auto &I : llvm::make_range(Machine.as_begin(), Machine.as_end())) + asVec[I.second] = I; for (const auto &I : asVec) Out << "attributes #" << I.second << " = { " 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 49514e2cb0b48..1be2dad7d0367 100644 --- a/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp +++ b/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp @@ -2233,8 +2233,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 173c88f6c17fd..de91eca402c15 100644 --- a/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp +++ b/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp @@ -8139,7 +8139,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/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp index 43eb005dfdbb3..51821dd7f23bb 100644 --- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -732,7 +732,7 @@ static bool findArgParts(Argument *Arg, const DataLayout &DL, AAResults &AAR, return true; // No users, this is a dead argument. // Sort parts by offset. - ArgPartsVec.append(ArgParts.begin(), ArgParts.end()); + append_range(ArgPartsVec, ArgParts); sort(ArgPartsVec, llvm::less_first()); // Make sure the parts are non-overlapping. diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp index e8925a6b0855e..a713ead683476 100644 --- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp @@ -1157,7 +1157,7 @@ static bool inferInitializes(Argument &A, Function &F) { if (UPB != UsesPerBlock.end()) { // Sort uses in this block by instruction order. SmallVector<std::pair<Instruction *, ArgumentAccessInfo>, 2> Insts; - Insts.append(UPB->second.Insts.begin(), UPB->second.Insts.end()); + append_range(Insts, UPB->second.Insts); sort(Insts, [](std::pair<Instruction *, ArgumentAccessInfo> &LHS, std::pair<Instruction *, ArgumentAccessInfo> &RHS) { return LHS.first->comesBefore(RHS.first); diff --git a/llvm/lib/Transforms/Utils/SplitModule.cpp b/llvm/lib/Transforms/Utils/SplitModule.cpp index a73b34fab462a..8e70902c4dac2 100644 --- a/llvm/lib/Transforms/Utils/SplitModule.cpp +++ b/llvm/lib/Transforms/Utils/SplitModule.cpp @@ -278,7 +278,7 @@ void llvm::SplitModule( for (unsigned I = 0; I < N; ++I) { if (auto It = ModuleFunctionCount.find(I); It != ModuleFunctionCount.end()) - BalancingQueue.emplace(It->first, It->second); + BalancingQueue.push(*It); else BalancingQueue.push({I, 0}); } diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index d3b5e97e2bf6b..9ff486cbc2cff 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -479,10 +479,9 @@ using IntBucket = detail::DenseMapPair<int, int>; static_assert(std::is_trivially_copyable_v<IntBucket>); static_assert(!std::is_trivially_default_constructible_v<IntBucket>); -// Converting a bucket to a std::pair copies both members, so it must not happen -// implicitly: `const std::pair<int, int> &P = *M.begin();` would bind to a -// temporary rather than the bucket. -static_assert(!std::is_convertible_v<IntBucket, std::pair<int, int>>); +// 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; @@ -515,8 +514,8 @@ TEST(DenseMapCustomTest, InsertRange) { EXPECT_EQ(*MoveMap.find(4)->second, 7); EXPECT_EQ(MoveSrc.find(4)->second, nullptr); - // Converting a bucket explicitly still reaches a vector's element type, and a - // std::map's, whose key is const. + // 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), _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
