From 8db564e0333f56f1306ad61373567565ee020b1e Mon Sep 17 00:00:00 2001 From: Mandeep Singh Grang Date: Sun, 1 Apr 2018 21:24:53 +0000 Subject: [PATCH] [tools] Change std::sort to llvm::sort in response to r327219 Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches. Reviewers: JDevlieghere, zturner, echristo, dberris, friss Reviewed By: echristo Subscribers: gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D45141 llvm-svn: 328943 --- llvm/tools/dsymutil/DebugMap.cpp | 7 +- llvm/tools/dsymutil/DwarfLinker.cpp | 4 +- llvm/tools/dsymutil/NonRelocatableStringpool.cpp | 2 +- llvm/tools/llvm-config/llvm-config.cpp | 2 +- llvm/tools/llvm-mca/InstrBuilder.cpp | 20 ++-- llvm/tools/llvm-nm/llvm-nm.cpp | 2 +- llvm/tools/llvm-objdump/COFFDump.cpp | 2 +- llvm/tools/llvm-objdump/MachODump.cpp | 2 +- llvm/tools/llvm-objdump/llvm-objdump.cpp | 6 +- llvm/tools/llvm-pdbutil/DumpOutputStyle.cpp | 2 +- llvm/tools/llvm-pdbutil/PrettyTypeDumper.cpp | 2 +- llvm/tools/llvm-pdbutil/llvm-pdbutil.cpp | 8 +- llvm/tools/llvm-readobj/COFFDumper.cpp | 4 +- llvm/tools/llvm-xray/xray-account.cc | 134 +++++++++++------------ llvm/tools/yaml2obj/yaml2macho.cpp | 8 +- 15 files changed, 103 insertions(+), 102 deletions(-) diff --git a/llvm/tools/dsymutil/DebugMap.cpp b/llvm/tools/dsymutil/DebugMap.cpp index 341f93e..5ad2530 100644 --- a/llvm/tools/dsymutil/DebugMap.cpp +++ b/llvm/tools/dsymutil/DebugMap.cpp @@ -63,9 +63,10 @@ void DebugMapObject::print(raw_ostream &OS) const { Entries.reserve(Symbols.getNumItems()); for (const auto &Sym : make_range(Symbols.begin(), Symbols.end())) Entries.push_back(std::make_pair(Sym.getKey(), Sym.getValue())); - std::sort( - Entries.begin(), Entries.end(), - [](const Entry &LHS, const Entry &RHS) { return LHS.first < RHS.first; }); + llvm::sort(Entries.begin(), Entries.end(), + [](const Entry &LHS, const Entry &RHS) { + return LHS.first < RHS.first; + }); for (const auto &Sym : Entries) { if (Sym.second.ObjectAddress) OS << format("\t%016" PRIx64, uint64_t(*Sym.second.ObjectAddress)); diff --git a/llvm/tools/dsymutil/DwarfLinker.cpp b/llvm/tools/dsymutil/DwarfLinker.cpp index 0b1af5c..41f52e7 100644 --- a/llvm/tools/dsymutil/DwarfLinker.cpp +++ b/llvm/tools/dsymutil/DwarfLinker.cpp @@ -1069,7 +1069,7 @@ void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit, // The object addresses where sorted, but again, the linked // addresses might end up in a different order. - std::sort(Ranges.begin(), Ranges.end()); + llvm::sort(Ranges.begin(), Ranges.end()); if (!Ranges.empty()) { MS->SwitchSection(MC->getObjectFileInfo()->getDwarfARangesSection()); @@ -2407,7 +2407,7 @@ bool DwarfLinker::RelocationManager::findValidRelocs( // the file, this allows us to just keep an index in the relocation // array that we advance during our walk, rather than resorting to // some associative container. See DwarfLinker::NextValidReloc. - std::sort(ValidRelocs.begin(), ValidRelocs.end()); + llvm::sort(ValidRelocs.begin(), ValidRelocs.end()); return true; } diff --git a/llvm/tools/dsymutil/NonRelocatableStringpool.cpp b/llvm/tools/dsymutil/NonRelocatableStringpool.cpp index d943b79..f1e5f59 100644 --- a/llvm/tools/dsymutil/NonRelocatableStringpool.cpp +++ b/llvm/tools/dsymutil/NonRelocatableStringpool.cpp @@ -39,7 +39,7 @@ NonRelocatableStringpool::getEntries() const { Result.reserve(Strings.size()); for (const auto &E : Strings) Result.emplace_back(E); - std::sort( + llvm::sort( Result.begin(), Result.end(), [](const DwarfStringPoolEntryRef A, const DwarfStringPoolEntryRef B) { return A.getIndex() < B.getIndex(); diff --git a/llvm/tools/llvm-config/llvm-config.cpp b/llvm/tools/llvm-config/llvm-config.cpp index 08b096a..bb395a0 100644 --- a/llvm/tools/llvm-config/llvm-config.cpp +++ b/llvm/tools/llvm-config/llvm-config.cpp @@ -522,7 +522,7 @@ int main(int argc, char **argv) { if (DyLibExists && !sys::fs::exists(path)) { Components = GetAllDyLibComponents(IsInDevelopmentTree, true, DirSep); - std::sort(Components.begin(), Components.end()); + llvm::sort(Components.begin(), Components.end()); break; } } diff --git a/llvm/tools/llvm-mca/InstrBuilder.cpp b/llvm/tools/llvm-mca/InstrBuilder.cpp index 0305e155..2b0be92 100644 --- a/llvm/tools/llvm-mca/InstrBuilder.cpp +++ b/llvm/tools/llvm-mca/InstrBuilder.cpp @@ -44,16 +44,16 @@ static void initializeUsedResources(InstrDesc &ID, // Sort elements by mask popcount, so that we prioritize resource units over // resource groups, and smaller groups over larger groups. - std::sort(Worklist.begin(), Worklist.end(), - [](const ResourcePlusCycles &A, const ResourcePlusCycles &B) { - unsigned popcntA = countPopulation(A.first); - unsigned popcntB = countPopulation(B.first); - if (popcntA < popcntB) - return true; - if (popcntA > popcntB) - return false; - return A.first < B.first; - }); + llvm::sort(Worklist.begin(), Worklist.end(), + [](const ResourcePlusCycles &A, const ResourcePlusCycles &B) { + unsigned popcntA = countPopulation(A.first); + unsigned popcntB = countPopulation(B.first); + if (popcntA < popcntB) + return true; + if (popcntA > popcntB) + return false; + return A.first < B.first; + }); uint64_t UsedResourceUnits = 0; diff --git a/llvm/tools/llvm-nm/llvm-nm.cpp b/llvm/tools/llvm-nm/llvm-nm.cpp index 6a4f997..6d0e613 100644 --- a/llvm/tools/llvm-nm/llvm-nm.cpp +++ b/llvm/tools/llvm-nm/llvm-nm.cpp @@ -705,7 +705,7 @@ static void sortAndPrintSymbolList(SymbolicFile &Obj, bool printName, if (ReverseSort) Cmp = [=](const NMSymbol &A, const NMSymbol &B) { return Cmp(B, A); }; - std::sort(SymbolList.begin(), SymbolList.end(), Cmp); + llvm::sort(SymbolList.begin(), SymbolList.end(), Cmp); } if (!PrintFileName) { diff --git a/llvm/tools/llvm-objdump/COFFDump.cpp b/llvm/tools/llvm-objdump/COFFDump.cpp index 780d1e9..d84f768 100644 --- a/llvm/tools/llvm-objdump/COFFDump.cpp +++ b/llvm/tools/llvm-objdump/COFFDump.cpp @@ -453,7 +453,7 @@ static bool getPDataSection(const COFFObjectFile *Obj, Rels.push_back(Reloc); // Sort relocations by address. - std::sort(Rels.begin(), Rels.end(), RelocAddressLess); + llvm::sort(Rels.begin(), Rels.end(), RelocAddressLess); ArrayRef Contents; error(Obj->getSectionContents(Pdata, Contents)); diff --git a/llvm/tools/llvm-objdump/MachODump.cpp b/llvm/tools/llvm-objdump/MachODump.cpp index 69e95b4..42df15d 100644 --- a/llvm/tools/llvm-objdump/MachODump.cpp +++ b/llvm/tools/llvm-objdump/MachODump.cpp @@ -6909,7 +6909,7 @@ static void DisassembleMachO(StringRef Filename, MachOObjectFile *MachOOF, BaseSegmentAddress); // Sort the symbols by address, just in case they didn't come in that way. - std::sort(Symbols.begin(), Symbols.end(), SymbolSorter()); + llvm::sort(Symbols.begin(), Symbols.end(), SymbolSorter()); // Build a data in code table that is sorted on by the address of each entry. uint64_t BaseAddress = 0; diff --git a/llvm/tools/llvm-objdump/llvm-objdump.cpp b/llvm/tools/llvm-objdump/llvm-objdump.cpp index 53b720e..99e8a39 100644 --- a/llvm/tools/llvm-objdump/llvm-objdump.cpp +++ b/llvm/tools/llvm-objdump/llvm-objdump.cpp @@ -1381,8 +1381,8 @@ static void DisassembleObject(const ObjectFile *Obj, bool InlineRelocs) { } } - std::sort(DataMappingSymsAddr.begin(), DataMappingSymsAddr.end()); - std::sort(TextMappingSymsAddr.begin(), TextMappingSymsAddr.end()); + llvm::sort(DataMappingSymsAddr.begin(), DataMappingSymsAddr.end()); + llvm::sort(TextMappingSymsAddr.begin(), TextMappingSymsAddr.end()); if (Obj->isELF() && Obj->getArch() == Triple::amdgcn) { // AMDGPU disassembler uses symbolizer for printing labels @@ -1407,7 +1407,7 @@ static void DisassembleObject(const ObjectFile *Obj, bool InlineRelocs) { } // Sort relocations by address. - std::sort(Rels.begin(), Rels.end(), RelocAddressLess); + llvm::sort(Rels.begin(), Rels.end(), RelocAddressLess); StringRef SegmentName = ""; if (const MachOObjectFile *MachO = dyn_cast(Obj)) { diff --git a/llvm/tools/llvm-pdbutil/DumpOutputStyle.cpp b/llvm/tools/llvm-pdbutil/DumpOutputStyle.cpp index 6694a21..111dcfb 100644 --- a/llvm/tools/llvm-pdbutil/DumpOutputStyle.cpp +++ b/llvm/tools/llvm-pdbutil/DumpOutputStyle.cpp @@ -876,7 +876,7 @@ Error DumpOutputStyle::dumpStringTableFromPdb() { std::vector SortedIDs(IS->name_ids().begin(), IS->name_ids().end()); - std::sort(SortedIDs.begin(), SortedIDs.end()); + llvm::sort(SortedIDs.begin(), SortedIDs.end()); for (uint32_t I : SortedIDs) { auto ES = IS->getStringForID(I); llvm::SmallString<32> Str; diff --git a/llvm/tools/llvm-pdbutil/PrettyTypeDumper.cpp b/llvm/tools/llvm-pdbutil/PrettyTypeDumper.cpp index 5c4c82b..663a608 100644 --- a/llvm/tools/llvm-pdbutil/PrettyTypeDumper.cpp +++ b/llvm/tools/llvm-pdbutil/PrettyTypeDumper.cpp @@ -128,7 +128,7 @@ filterAndSortClassDefs(LinePrinter &Printer, Enumerator &E, } if (Comp) - std::sort(Filtered.begin(), Filtered.end(), Comp); + llvm::sort(Filtered.begin(), Filtered.end(), Comp); return Filtered; } diff --git a/llvm/tools/llvm-pdbutil/llvm-pdbutil.cpp b/llvm/tools/llvm-pdbutil/llvm-pdbutil.cpp index c96761f..3cb0237 100644 --- a/llvm/tools/llvm-pdbutil/llvm-pdbutil.cpp +++ b/llvm/tools/llvm-pdbutil/llvm-pdbutil.cpp @@ -977,8 +977,8 @@ static void dumpPretty(StringRef Path) { std::vector> Funcs; while (auto Func = Functions->getNext()) Funcs.push_back(std::move(Func)); - std::sort(Funcs.begin(), Funcs.end(), - opts::pretty::compareFunctionSymbols); + llvm::sort(Funcs.begin(), Funcs.end(), + opts::pretty::compareFunctionSymbols); for (const auto &Func : Funcs) { Printer.NewLine(); Dumper.start(*Func, FunctionDumper::PointerType::None); @@ -996,8 +996,8 @@ static void dumpPretty(StringRef Path) { std::vector> Datas; while (auto Var = Vars->getNext()) Datas.push_back(std::move(Var)); - std::sort(Datas.begin(), Datas.end(), - opts::pretty::compareDataSymbols); + llvm::sort(Datas.begin(), Datas.end(), + opts::pretty::compareDataSymbols); for (const auto &Var : Datas) Dumper.start(*Var); } diff --git a/llvm/tools/llvm-readobj/COFFDumper.cpp b/llvm/tools/llvm-readobj/COFFDumper.cpp index f40e0d9..5d6bcc6 100644 --- a/llvm/tools/llvm-readobj/COFFDumper.cpp +++ b/llvm/tools/llvm-readobj/COFFDumper.cpp @@ -607,8 +607,8 @@ void COFFDumper::cacheRelocations() { RelocMap[Section].push_back(Reloc); // Sort relocations by address. - std::sort(RelocMap[Section].begin(), RelocMap[Section].end(), - relocAddressLess); + llvm::sort(RelocMap[Section].begin(), RelocMap[Section].end(), + relocAddressLess); } } diff --git a/llvm/tools/llvm-xray/xray-account.cc b/llvm/tools/llvm-xray/xray-account.cc index 542da54..5afb48d 100644 --- a/llvm/tools/llvm-xray/xray-account.cc +++ b/llvm/tools/llvm-xray/xray-account.cc @@ -282,79 +282,79 @@ void LatencyAccountant::exportStats(const XRayFileHeader &Header, F Fn) const { // Sort the data according to user-provided flags. switch (AccountSortOutput) { case SortField::FUNCID: - std::sort(Results.begin(), Results.end(), - [](const TupleType &L, const TupleType &R) { - if (AccountSortOrder == SortDirection::ASCENDING) - return std::get<0>(L) < std::get<0>(R); - if (AccountSortOrder == SortDirection::DESCENDING) - return std::get<0>(L) > std::get<0>(R); - llvm_unreachable("Unknown sort direction"); - }); + llvm::sort(Results.begin(), Results.end(), + [](const TupleType &L, const TupleType &R) { + if (AccountSortOrder == SortDirection::ASCENDING) + return std::get<0>(L) < std::get<0>(R); + if (AccountSortOrder == SortDirection::DESCENDING) + return std::get<0>(L) > std::get<0>(R); + llvm_unreachable("Unknown sort direction"); + }); break; case SortField::COUNT: - std::sort(Results.begin(), Results.end(), - [](const TupleType &L, const TupleType &R) { - if (AccountSortOrder == SortDirection::ASCENDING) - return std::get<1>(L) < std::get<1>(R); - if (AccountSortOrder == SortDirection::DESCENDING) - return std::get<1>(L) > std::get<1>(R); - llvm_unreachable("Unknown sort direction"); - }); + llvm::sort(Results.begin(), Results.end(), + [](const TupleType &L, const TupleType &R) { + if (AccountSortOrder == SortDirection::ASCENDING) + return std::get<1>(L) < std::get<1>(R); + if (AccountSortOrder == SortDirection::DESCENDING) + return std::get<1>(L) > std::get<1>(R); + llvm_unreachable("Unknown sort direction"); + }); break; default: // Here we need to look into the ResultRow for the rest of the data that // we want to sort by. - std::sort(Results.begin(), Results.end(), - [&](const TupleType &L, const TupleType &R) { - auto &LR = std::get<2>(L); - auto &RR = std::get<2>(R); - switch (AccountSortOutput) { - case SortField::COUNT: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Count < RR.Count; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Count > RR.Count; - llvm_unreachable("Unknown sort direction"); - case SortField::MIN: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Min < RR.Min; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Min > RR.Min; - llvm_unreachable("Unknown sort direction"); - case SortField::MED: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Median < RR.Median; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Median > RR.Median; - llvm_unreachable("Unknown sort direction"); - case SortField::PCT90: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Pct90 < RR.Pct90; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Pct90 > RR.Pct90; - llvm_unreachable("Unknown sort direction"); - case SortField::PCT99: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Pct99 < RR.Pct99; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Pct99 > RR.Pct99; - llvm_unreachable("Unknown sort direction"); - case SortField::MAX: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Max < RR.Max; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Max > RR.Max; - llvm_unreachable("Unknown sort direction"); - case SortField::SUM: - if (AccountSortOrder == SortDirection::ASCENDING) - return LR.Sum < RR.Sum; - if (AccountSortOrder == SortDirection::DESCENDING) - return LR.Sum > RR.Sum; - llvm_unreachable("Unknown sort direction"); - default: - llvm_unreachable("Unsupported sort order"); - } - }); + llvm::sort(Results.begin(), Results.end(), + [&](const TupleType &L, const TupleType &R) { + auto &LR = std::get<2>(L); + auto &RR = std::get<2>(R); + switch (AccountSortOutput) { + case SortField::COUNT: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Count < RR.Count; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Count > RR.Count; + llvm_unreachable("Unknown sort direction"); + case SortField::MIN: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Min < RR.Min; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Min > RR.Min; + llvm_unreachable("Unknown sort direction"); + case SortField::MED: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Median < RR.Median; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Median > RR.Median; + llvm_unreachable("Unknown sort direction"); + case SortField::PCT90: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Pct90 < RR.Pct90; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Pct90 > RR.Pct90; + llvm_unreachable("Unknown sort direction"); + case SortField::PCT99: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Pct99 < RR.Pct99; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Pct99 > RR.Pct99; + llvm_unreachable("Unknown sort direction"); + case SortField::MAX: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Max < RR.Max; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Max > RR.Max; + llvm_unreachable("Unknown sort direction"); + case SortField::SUM: + if (AccountSortOrder == SortDirection::ASCENDING) + return LR.Sum < RR.Sum; + if (AccountSortOrder == SortDirection::DESCENDING) + return LR.Sum > RR.Sum; + llvm_unreachable("Unknown sort direction"); + default: + llvm_unreachable("Unsupported sort order"); + } + }); break; } diff --git a/llvm/tools/yaml2obj/yaml2macho.cpp b/llvm/tools/yaml2obj/yaml2macho.cpp index 34b6ac2..1bb50a9 100644 --- a/llvm/tools/yaml2obj/yaml2macho.cpp +++ b/llvm/tools/yaml2obj/yaml2macho.cpp @@ -417,10 +417,10 @@ Error MachOWriter::writeLinkEditData(raw_ostream &OS) { } } - std::sort(WriteQueue.begin(), WriteQueue.end(), - [](const writeOperation &a, const writeOperation &b) { - return a.first < b.first; - }); + llvm::sort(WriteQueue.begin(), WriteQueue.end(), + [](const writeOperation &a, const writeOperation &b) { + return a.first < b.first; + }); for (auto writeOp : WriteQueue) { ZeroToOffset(OS, writeOp.first); -- 2.7.4