https://github.com/jurahul updated https://github.com/llvm/llvm-project/pull/178783
>From 9ac78a2c3c78ba863945dc1d8e4c6c4ec10b8863 Mon Sep 17 00:00:00 2001 From: Rahul Joshi <[email protected]> Date: Thu, 29 Jan 2026 16:00:06 -0800 Subject: [PATCH] [LLVM][ADT] Disallow llvm::sort on pointers --- .../include-cleaner/lib/HTMLReport.cpp | 3 +-- llvm/include/llvm/ADT/STLExtras.h | 15 ++++++++++++--- .../llvm/ExecutionEngine/Orc/WaitingOnGraph.h | 2 +- llvm/include/llvm/Support/GenericLoopInfoImpl.h | 4 ++-- .../Transforms/Coroutines/SuspendCrossingInfo.h | 2 +- llvm/lib/Analysis/StackSafetyAnalysis.cpp | 3 +-- llvm/lib/IR/Verifier.cpp | 2 +- llvm/lib/Target/DirectX/DXILOpLowering.cpp | 3 +-- llvm/lib/Transforms/Scalar/GVNSink.cpp | 2 +- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | 6 +++--- .../Transforms/Scalar/RewriteStatepointsForGC.cpp | 4 +--- llvm/unittests/ADT/STLExtrasTest.cpp | 5 +++++ llvm/unittests/MIR/MachineMetadata.cpp | 4 ++-- 13 files changed, 32 insertions(+), 23 deletions(-) diff --git a/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp b/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp index 3e067f84432ac..2c5a55a92db2a 100644 --- a/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp +++ b/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp @@ -185,8 +185,7 @@ class Reporter { if (!R.Includes.empty()) R.Satisfied = true; // Include pointers are meaningfully ordered as they are backed by a vector. - llvm::sort(R.Includes); - R.Includes.erase(llvm::unique(R.Includes), R.Includes.end()); + llvm::sort_and_unique(R.Includes); if (!R.Headers.empty()) R.Insert = diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h index 23da931a63de1..55b8738015972 100644 --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -1630,8 +1630,11 @@ using sort_trivially_copyable = std::conjunction< // Provide wrappers to std::sort which shuffle the elements before sorting // to help uncover non-deterministic behavior (PR35135). -template <typename IteratorTy> +template <bool AllowPointers = false, typename IteratorTy> inline void sort(IteratorTy Start, IteratorTy End) { + using VT = typename std::iterator_traits<IteratorTy>::value_type; + static_assert(AllowPointers || !std::is_pointer_v<VT>, + "Cannot sort pointers"); if constexpr (detail::sort_trivially_copyable<IteratorTy>::value) { // Forward trivially copyable types to array_pod_sort. This avoids a large // amount of code bloat for a minor performance hit. @@ -1644,8 +1647,9 @@ inline void sort(IteratorTy Start, IteratorTy End) { } } -template <typename Container> inline void sort(Container &&C) { - llvm::sort(adl_begin(C), adl_end(C)); +template <bool AllowPointers = false, typename Container> +inline void sort(Container &&C) { + llvm::sort<AllowPointers>(adl_begin(C), adl_end(C)); } template <typename IteratorTy, typename Compare> @@ -2131,6 +2135,11 @@ template <typename Range> auto unique(Range &&R) { return std::unique(adl_begin(R), adl_end(R)); } +template <typename Container> inline void sort_and_unique(Container &&C) { + llvm::sort(C, std::less<detail::ValueOfRange<Container>>()); + C.erase(llvm::unique(C), adl_end(C)); +} + /// Wrapper function around std::equal to detect if pair-wise elements between /// two ranges are the same. template <typename L, typename R> bool equal(L &&LRange, R &&RRange) { diff --git a/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h b/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h index 93412d9d22f8c..a454d3d4041da 100644 --- a/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h +++ b/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h @@ -177,7 +177,7 @@ template <typename ContainerIdT, typename ElementIdT> class WaitingOnGraph { SortedContainers.reserve(M.size()); for (auto &[Container, Elems] : M) SortedContainers.push_back(Container); - llvm::sort(SortedContainers); + llvm::sort</*AllowPointers=*/true>(SortedContainers); hash_code Hash(0); for (auto &Container : SortedContainers) { auto &ContainerElems = M.at(Container); diff --git a/llvm/include/llvm/Support/GenericLoopInfoImpl.h b/llvm/include/llvm/Support/GenericLoopInfoImpl.h index c830f0a67a448..dac263e0e4c87 100644 --- a/llvm/include/llvm/Support/GenericLoopInfoImpl.h +++ b/llvm/include/llvm/Support/GenericLoopInfoImpl.h @@ -690,8 +690,8 @@ void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { template <typename T> bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) { - llvm::sort(BB1); - llvm::sort(BB2); + llvm::sort</*AllowPointers=*/true>(BB1); + llvm::sort</*AllowPointers=*/true>(BB2); return BB1 == BB2; } diff --git a/llvm/include/llvm/Transforms/Coroutines/SuspendCrossingInfo.h b/llvm/include/llvm/Transforms/Coroutines/SuspendCrossingInfo.h index 1e04f09ddc275..11cc84199eba8 100644 --- a/llvm/include/llvm/Transforms/Coroutines/SuspendCrossingInfo.h +++ b/llvm/include/llvm/Transforms/Coroutines/SuspendCrossingInfo.h @@ -38,7 +38,7 @@ class BlockToIndexMapping { BlockToIndexMapping(Function &F) { for (BasicBlock &BB : F) V.push_back(&BB); - llvm::sort(V); + llvm::sort</*AllowPointers=*/true>(V); } size_t blockToIndex(BasicBlock const *BB) const { diff --git a/llvm/lib/Analysis/StackSafetyAnalysis.cpp b/llvm/lib/Analysis/StackSafetyAnalysis.cpp index fbe74d21c7199..f1a98a6254732 100644 --- a/llvm/lib/Analysis/StackSafetyAnalysis.cpp +++ b/llvm/lib/Analysis/StackSafetyAnalysis.cpp @@ -687,8 +687,7 @@ void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() { for (auto &CS : KV.second.Calls) Callees.push_back(CS.first.Callee); - llvm::sort(Callees); - Callees.erase(llvm::unique(Callees), Callees.end()); + llvm::sort_and_unique(Callees); for (auto &Callee : Callees) Callers[Callee].push_back(F.first); diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp index 3d44d1317ecc7..d0fc66c059aef 100644 --- a/llvm/lib/IR/Verifier.cpp +++ b/llvm/lib/IR/Verifier.cpp @@ -3389,7 +3389,7 @@ void Verifier::visitBasicBlock(BasicBlock &BB) { if (isa<PHINode>(BB.front())) { SmallVector<BasicBlock *, 8> Preds(predecessors(&BB)); SmallVector<std::pair<BasicBlock*, Value*>, 8> Values; - llvm::sort(Preds); + llvm::sort</*AllowPointers=*/true>(Preds); for (const PHINode &PN : BB.phis()) { Check(PN.getNumIncomingValues() == Preds.size(), "PHINode should have one entry for each predecessor of its " diff --git a/llvm/lib/Target/DirectX/DXILOpLowering.cpp b/llvm/lib/Target/DirectX/DXILOpLowering.cpp index 0c0830cc92aa7..5ec8446ff910e 100644 --- a/llvm/lib/Target/DirectX/DXILOpLowering.cpp +++ b/llvm/lib/Target/DirectX/DXILOpLowering.cpp @@ -190,8 +190,7 @@ class OpLowerer { } // Deduplicate the cast functions so that we only erase each one once. - llvm::sort(CastFns); - CastFns.erase(llvm::unique(CastFns), CastFns.end()); + llvm::sort_and_unique(CastFns); for (Function *F : CastFns) F->eraseFromParent(); diff --git a/llvm/lib/Transforms/Scalar/GVNSink.cpp b/llvm/lib/Transforms/Scalar/GVNSink.cpp index 4dddb017a98ee..5c11f9224b63a 100644 --- a/llvm/lib/Transforms/Scalar/GVNSink.cpp +++ b/llvm/lib/Transforms/Scalar/GVNSink.cpp @@ -307,7 +307,7 @@ class InstructionUseExpr : public BasicExpression { for (auto &U : I->uses()) op_push_back(U.getUser()); - llvm::sort(operands()); + llvm::sort</*AllowPointers=*/true>(operands()); } void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; } diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp index e9d78baece25b..eaed5c4a53a29 100644 --- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -1689,7 +1689,7 @@ bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const { SmallVector<const SCEV *, 4> Key = F.BaseRegs; if (F.ScaledReg) Key.push_back(F.ScaledReg); // Unstable sort by host order ok, because this is only used for uniquifying. - llvm::sort(Key); + llvm::sort</*AllowPointers=*/true>(Key); return Uniquifier.count(Key); } @@ -1713,7 +1713,7 @@ bool LSRUse::InsertFormula(const Formula &F, const Loop &L) { SmallVector<const SCEV *, 4> Key = F.BaseRegs; if (F.ScaledReg) Key.push_back(F.ScaledReg); // Unstable sort by host order ok, because this is only used for uniquifying. - llvm::sort(Key); + llvm::sort</*AllowPointers=*/true>(Key); if (!Uniquifier.insert(Key).second) return false; @@ -4809,7 +4809,7 @@ void LSRInstance::FilterOutUndesirableDedicatedRegisters() { Key.push_back(F.ScaledReg); // Unstable sort by host order ok, because this is only used for // uniquifying. - llvm::sort(Key); + llvm::sort</*AllowPointers=*/true>(Key); std::pair<BestFormulaeTy::const_iterator, bool> P = BestFormulae.insert(std::make_pair(Key, FIdx)); diff --git a/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp b/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp index 230df9f971a71..a7471bffb2f6f 100644 --- a/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ b/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -2152,9 +2152,7 @@ static void relocationViaAlloca( } } - llvm::sort(Uses); - auto Last = llvm::unique(Uses); - Uses.erase(Last, Uses.end()); + llvm::sort_and_unique(Uses); for (Instruction *Use : Uses) { if (isa<PHINode>(Use)) { diff --git a/llvm/unittests/ADT/STLExtrasTest.cpp b/llvm/unittests/ADT/STLExtrasTest.cpp index fe71945e4a794..6989a548b2b5b 100644 --- a/llvm/unittests/ADT/STLExtrasTest.cpp +++ b/llvm/unittests/ADT/STLExtrasTest.cpp @@ -649,6 +649,11 @@ TEST(STLExtrasTest, PartitionAdaptor) { EXPECT_EQ(7, V[7]); } +TEST(STLExtrasTest, SortPointer) { + std::vector<int *> V = {nullptr, nullptr}; + llvm::sort</*AllowPointers=*/true>(V); +} + TEST(STLExtrasTest, EraseIf) { std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8}; diff --git a/llvm/unittests/MIR/MachineMetadata.cpp b/llvm/unittests/MIR/MachineMetadata.cpp index 8960a3a107d10..b757fcfa378fa 100644 --- a/llvm/unittests/MIR/MachineMetadata.cpp +++ b/llvm/unittests/MIR/MachineMetadata.cpp @@ -270,8 +270,8 @@ body: | for (auto &MD : MDList) Collected.push_back(MD.second); - llvm::sort(Generated); - llvm::sort(Collected); + llvm::sort</*AllowPointers=*/true>(Generated); + llvm::sort</*AllowPointers=*/true>(Collected); EXPECT_EQ(Collected, Generated); // FileCheck the output from MIR printer. _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
