https://github.com/kazutakahirata created
https://github.com/llvm/llvm-project/pull/136543
None
>From 2022f8dee6651e99f5c1af1cbb8b89e22dc16916 Mon Sep 17 00:00:00 2001
From: Kazu Hirata <k...@google.com>
Date: Sat, 19 Apr 2025 22:42:07 -0700
Subject: [PATCH] DO NOT MERGE: Identify places that need reserve.
---
clang/lib/Analysis/CFG.cpp | 2 +
llvm/include/llvm/ADT/STLExtras.h | 51 +++++++++++++++++++
llvm/lib/CodeGen/SplitKit.cpp | 1 +
llvm/lib/IR/Verifier.cpp | 5 +-
llvm/lib/Transforms/IPO/ArgumentPromotion.cpp | 2 +
llvm/lib/Transforms/IPO/FunctionAttrs.cpp | 1 +
llvm/lib/Transforms/IPO/GlobalOpt.cpp | 6 ++-
llvm/lib/Transforms/Utils/LoopSimplify.cpp | 4 +-
llvm/lib/Transforms/Utils/SSAUpdater.cpp | 6 ++-
.../Transforms/Vectorize/LoopVectorize.cpp | 1 +
.../TableGen/Common/CodeGenRegisters.cpp | 1 +
llvm/utils/TableGen/GlobalISelEmitter.cpp | 1 +
12 files changed, 75 insertions(+), 6 deletions(-)
diff --git a/clang/lib/Analysis/CFG.cpp b/clang/lib/Analysis/CFG.cpp
index d03a0a544b016..6ff485049c28e 100644
--- a/clang/lib/Analysis/CFG.cpp
+++ b/clang/lib/Analysis/CFG.cpp
@@ -484,6 +484,8 @@ reverse_children::reverse_children(Stmt *S, ASTContext
&Ctx) {
}
// Default case for all other statements.
+ auto R = S->children();
+ childrenBuf.reserve(childrenBuf.size() + std::distance(R.begin(), R.end()));
llvm::append_range(childrenBuf, S->children());
// This needs to be done *after* childrenBuf has been populated.
diff --git a/llvm/include/llvm/ADT/STLExtras.h
b/llvm/include/llvm/ADT/STLExtras.h
index dc0443c9244be..ec662594232e2 100644
--- a/llvm/include/llvm/ADT/STLExtras.h
+++ b/llvm/include/llvm/ADT/STLExtras.h
@@ -2113,12 +2113,63 @@ void erase(Container &C, ValueType V) {
C.erase(std::remove(C.begin(), C.end(), V), C.end());
}
+namespace detail {
+template <typename Range>
+using check_has_member_iterator_category_t =
+ typename decltype(std::declval<Range &>().begin())::iterator_category;
+
+template <typename Range>
+static constexpr bool HasMemberIteratorCategory =
+ is_detected<check_has_member_iterator_category_t, Range>::value;
+
+template <typename Container>
+using check_has_member_capacity_t =
+ decltype(std::declval<Container &>().capacity());
+
+template <typename Container>
+static constexpr bool HasMemberCapacity =
+ is_detected<check_has_member_capacity_t, Container>::value;
+
+template <typename Container>
+using check_has_member_reserve_t =
+ decltype(std::declval<Container &>().reserve(1U));
+
+template <typename Container>
+static constexpr bool HasMemberReserve =
+ is_detected<check_has_member_reserve_t, Container>::value;
+} // namespace detail
+
/// Wrapper function to append range `R` to container `C`.
///
/// C.insert(C.end(), R.begin(), R.end());
template <typename Container, typename Range>
void append_range(Container &C, Range &&R) {
+ size_t Before = 0;
+ size_t After = 0;
+
+ if constexpr (detail::HasMemberReserve<Container>) {
+ using IteratorType = decltype(adl_begin(R));
+ if constexpr (std::is_pointer<IteratorType>::value) {
+ C.reserve(C.size() + std::distance(adl_begin(R), adl_end(R)));
+ } else if constexpr (detail::HasMemberIteratorCategory<Range>) {
+ if constexpr (std::is_convertible<
+ typename IteratorType::iterator_category,
+ std::random_access_iterator_tag>::value) {
+ C.reserve(C.size() + std::distance(adl_begin(R), adl_end(R)));
+ }
+ }
+ }
+
+ if constexpr (detail::HasMemberCapacity<Container>)
+ Before = C.capacity();
+
C.insert(C.end(), adl_begin(R), adl_end(R));
+
+ if constexpr (detail::HasMemberCapacity<Container>)
+ After = C.capacity();
+
+ if (Before != After)
+ llvm_unreachable("capacity changed");
}
/// Appends all `Values` to container `C`.
diff --git a/llvm/lib/CodeGen/SplitKit.cpp b/llvm/lib/CodeGen/SplitKit.cpp
index e55dfaebd028e..416dc0fdac2f2 100644
--- a/llvm/lib/CodeGen/SplitKit.cpp
+++ b/llvm/lib/CodeGen/SplitKit.cpp
@@ -1035,6 +1035,7 @@ void SplitEditor::computeRedundantBackCopies(
}
if (!DominatedVNIs.empty()) {
forceRecompute(0, *ParentVNI);
+ BackCopies.reserve(BackCopies.size() + DominatedVNIs.size());
append_range(BackCopies, DominatedVNIs);
DominatedVNIs.clear();
}
diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp
index 8afe360d088bc..5a3bac7f26a75 100644
--- a/llvm/lib/IR/Verifier.cpp
+++ b/llvm/lib/IR/Verifier.cpp
@@ -725,8 +725,11 @@ static void forEachUser(const Value *User,
const Value *Cur = WorkList.pop_back_val();
if (!Visited.insert(Cur).second)
continue;
- if (Callback(Cur))
+ if (Callback(Cur)) {
+ auto R = Cur->materialized_users();
+ WorkList.reserve(WorkList.size() + std::distance(R.begin(), R.end()));
append_range(WorkList, Cur->materialized_users());
+ }
}
}
diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
index 0ec5202b8cfe7..a3ef9c4836f31 100644
--- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
+++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
@@ -388,6 +388,8 @@ doPromotion(Function *F, FunctionAnalysisManager &FAM,
Value *V = Worklist.pop_back_val();
if (isa<GetElementPtrInst>(V)) {
DeadInsts.push_back(cast<Instruction>(V));
+ auto R = V->users();
+ Worklist.reserve(Worklist.size() + std::distance(R.begin(), R.end()));
append_range(Worklist, V->users());
continue;
}
diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
index bbfed2ac2c090..7fac2aa98ffe6 100644
--- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -1144,6 +1144,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.reserve(UPB->second.Insts.size());
append_range(Insts, UPB->second.Insts);
sort(Insts, [](std::pair<Instruction *, ArgumentAccessInfo> &LHS,
std::pair<Instruction *, ArgumentAccessInfo> &RHS) {
diff --git a/llvm/lib/Transforms/IPO/GlobalOpt.cpp
b/llvm/lib/Transforms/IPO/GlobalOpt.cpp
index 83cc1e5f04f3d..44f68113f97c1 100644
--- a/llvm/lib/Transforms/IPO/GlobalOpt.cpp
+++ b/llvm/lib/Transforms/IPO/GlobalOpt.cpp
@@ -299,9 +299,11 @@ static bool CleanupConstantGlobalUsers(GlobalVariable *GV,
append_range(WorkList, BO->users());
if (auto *ASC = dyn_cast<AddrSpaceCastOperator>(U))
append_range(WorkList, ASC->users());
- else if (auto *GEP = dyn_cast<GEPOperator>(U))
+ else if (auto *GEP = dyn_cast<GEPOperator>(U)) {
+ auto R = GEP->users();
+ WorkList.reserve(WorkList.size() + std::distance(R.begin(), R.end()));
append_range(WorkList, GEP->users());
- else if (auto *LI = dyn_cast<LoadInst>(U)) {
+ } else if (auto *LI = dyn_cast<LoadInst>(U)) {
// A load from a uniform value is always the same, regardless of any
// applied offset.
Type *Ty = LI->getType();
diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp
b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
index 61ffb49a8c010..3b4ca1203151c 100644
--- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
@@ -158,10 +158,12 @@ static void addBlockAndPredsToSet(BasicBlock *InputBB,
BasicBlock *StopBlock,
Worklist.push_back(InputBB);
do {
BasicBlock *BB = Worklist.pop_back_val();
- if (Blocks.insert(BB).second && BB != StopBlock)
+ if (Blocks.insert(BB).second && BB != StopBlock) {
// If BB is not already processed and it is not a stop block then
// insert its predecessor in the work list
+ Worklist.reserve(Worklist.size() + pred_size(BB));
append_range(Worklist, predecessors(BB));
+ }
} while (!Worklist.empty());
}
diff --git a/llvm/lib/Transforms/Utils/SSAUpdater.cpp
b/llvm/lib/Transforms/Utils/SSAUpdater.cpp
index 48d9528f0c3df..8bad2286c090f 100644
--- a/llvm/lib/Transforms/Utils/SSAUpdater.cpp
+++ b/llvm/lib/Transforms/Utils/SSAUpdater.cpp
@@ -300,10 +300,12 @@ class SSAUpdaterTraits<SSAUpdater> {
// We can get our predecessor info by walking the pred_iterator list,
// but it is relatively slow. If we already have PHI nodes in this
// block, walk one of them to get the predecessor list instead.
- if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin()))
+ if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
append_range(*Preds, SomePhi->blocks());
- else
+ } else {
+ Preds->reserve(pred_size(BB));
append_range(*Preds, predecessors(BB));
+ }
}
/// GetPoisonVal - Get a poison value of the same type as the value
diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
index 137f32ded7248..0cc90e3bfa54a 100644
--- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -6433,6 +6433,7 @@ void
LoopVectorizationCostModel::setCostBasedWideningDecision(ElementCount VF) {
// Add all instructions used to generate the addresses.
SmallVector<Instruction *, 4> Worklist;
+ Worklist.reserve(AddrDefs.size());
append_range(Worklist, AddrDefs);
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
diff --git a/llvm/utils/TableGen/Common/CodeGenRegisters.cpp
b/llvm/utils/TableGen/Common/CodeGenRegisters.cpp
index 3479cad10b66c..69d1f5dd44723 100644
--- a/llvm/utils/TableGen/Common/CodeGenRegisters.cpp
+++ b/llvm/utils/TableGen/Common/CodeGenRegisters.cpp
@@ -1185,6 +1185,7 @@ void
CodeGenRegisterClass::extendSuperRegClasses(CodeGenSubRegIndex *SubIdx) {
return;
SmallVector<CodeGenRegisterClass *> MidRCs;
+ MidRCs.reserve(It->second.size());
llvm::append_range(MidRCs, It->second);
for (CodeGenRegisterClass *MidRC : MidRCs) {
diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp
b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index ccc4c00fca047..cf07640ac9f84 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -2451,6 +2451,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
// Create a table containing the LLT objects needed by the matcher and an
enum
// for the matcher to reference them with.
std::vector<LLTCodeGen> TypeObjects;
+ TypeObjects.reserve(KnownTypes.size());
append_range(TypeObjects, KnownTypes);
llvm::sort(TypeObjects);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
