Author: jdevlieghere Date: Tue Jan 8 15:25:06 2019 New Revision: 350679 URL: http://llvm.org/viewvc/llvm-project?rev=350679&view=rev Log: Change std::sort to llvm::sort to detect non-determinism.
LLVM added wrappers to std::sort (r327219) that randomly shuffle the container before sorting. The goal is to uncover non-determinism due to undefined sorting order of objects having the same key. This can be enabled with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON. Modified: lldb/trunk/include/lldb/Core/UniqueCStringMap.h lldb/trunk/source/Breakpoint/BreakpointResolver.cpp lldb/trunk/source/Commands/CommandObjectType.cpp lldb/trunk/source/Interpreter/OptionValueArray.cpp lldb/trunk/source/Interpreter/OptionValueFileSpecLIst.cpp lldb/trunk/source/Interpreter/OptionValuePathMappings.cpp lldb/trunk/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp lldb/trunk/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp lldb/trunk/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp lldb/trunk/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp lldb/trunk/source/Plugins/Process/minidump/MinidumpParser.cpp lldb/trunk/source/Symbol/ArmUnwindInfo.cpp lldb/trunk/source/Symbol/CompileUnit.cpp lldb/trunk/source/Symbol/Function.cpp lldb/trunk/source/Symbol/Symtab.cpp lldb/trunk/source/Target/Target.cpp lldb/trunk/source/Utility/Timer.cpp Modified: lldb/trunk/include/lldb/Core/UniqueCStringMap.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Core/UniqueCStringMap.h?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/include/lldb/Core/UniqueCStringMap.h (original) +++ lldb/trunk/include/lldb/Core/UniqueCStringMap.h Tue Jan 8 15:25:06 2019 @@ -217,7 +217,7 @@ public: // } // my_map.Sort(); //------------------------------------------------------------------ - void Sort() { std::sort(m_map.begin(), m_map.end()); } + void Sort() { llvm::sort(m_map.begin(), m_map.end()); } //------------------------------------------------------------------ // Since we are using a vector to contain our items it will always double its Modified: lldb/trunk/source/Breakpoint/BreakpointResolver.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Breakpoint/BreakpointResolver.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Breakpoint/BreakpointResolver.cpp (original) +++ lldb/trunk/source/Breakpoint/BreakpointResolver.cpp Tue Jan 8 15:25:06 2019 @@ -238,10 +238,10 @@ void BreakpointResolver::SetSCMatchesByL worklist_begin, worklist_end, [&](const SymbolContext &sc) { return SourceLoc(sc) < requested; }); // Sort the remaining entries by (line, column). - std::sort(worklist_begin, worklist_end, - [](const SymbolContext &a, const SymbolContext &b) { - return SourceLoc(a) < SourceLoc(b); - }); + llvm::sort(worklist_begin, worklist_end, + [](const SymbolContext &a, const SymbolContext &b) { + return SourceLoc(a) < SourceLoc(b); + }); // Filter out all locations with a source location after the closest match. if (worklist_begin != worklist_end) @@ -261,11 +261,11 @@ void BreakpointResolver::SetSCMatchesByL } // Sort by file address. - std::sort(worklist_begin, worklist_end, - [](const SymbolContext &a, const SymbolContext &b) { - return a.line_entry.range.GetBaseAddress().GetFileAddress() < - b.line_entry.range.GetBaseAddress().GetFileAddress(); - }); + llvm::sort(worklist_begin, worklist_end, + [](const SymbolContext &a, const SymbolContext &b) { + return a.line_entry.range.GetBaseAddress().GetFileAddress() < + b.line_entry.range.GetBaseAddress().GetFileAddress(); + }); // Go through and see if there are line table entries that are // contiguous, and if so keep only the first of the contiguous range. Modified: lldb/trunk/source/Commands/CommandObjectType.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Commands/CommandObjectType.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Commands/CommandObjectType.cpp (original) +++ lldb/trunk/source/Commands/CommandObjectType.cpp Tue Jan 8 15:25:06 2019 @@ -2907,7 +2907,7 @@ public: if (StackFrame *frame = m_exe_ctx.GetFramePtr()) { guessed_language = GuessLanguage(frame); if (guessed_language != eLanguageTypeUnknown) { - std::sort( + llvm::sort( languages.begin(), languages.end(), [guessed_language](Language *lang1, Language *lang2) -> bool { if (!lang1 || !lang2) Modified: lldb/trunk/source/Interpreter/OptionValueArray.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Interpreter/OptionValueArray.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Interpreter/OptionValueArray.cpp (original) +++ lldb/trunk/source/Interpreter/OptionValueArray.cpp Tue Jan 8 15:25:06 2019 @@ -221,7 +221,7 @@ Status OptionValueArray::SetArgs(const A if (num_remove_indexes) { // Sort and then erase in reverse so indexes are always valid if (num_remove_indexes > 1) { - std::sort(remove_indexes.begin(), remove_indexes.end()); + llvm::sort(remove_indexes.begin(), remove_indexes.end()); for (std::vector<int>::const_reverse_iterator pos = remove_indexes.rbegin(), end = remove_indexes.rend(); Modified: lldb/trunk/source/Interpreter/OptionValueFileSpecLIst.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Interpreter/OptionValueFileSpecLIst.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Interpreter/OptionValueFileSpecLIst.cpp (original) +++ lldb/trunk/source/Interpreter/OptionValueFileSpecLIst.cpp Tue Jan 8 15:25:06 2019 @@ -140,7 +140,7 @@ Status OptionValueFileSpecList::SetValue size_t num_remove_indexes = remove_indexes.size(); if (num_remove_indexes) { // Sort and then erase in reverse so indexes are always valid - std::sort(remove_indexes.begin(), remove_indexes.end()); + llvm::sort(remove_indexes.begin(), remove_indexes.end()); for (size_t j = num_remove_indexes - 1; j < num_remove_indexes; ++j) { m_current_value.Remove(j); } Modified: lldb/trunk/source/Interpreter/OptionValuePathMappings.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Interpreter/OptionValuePathMappings.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Interpreter/OptionValuePathMappings.cpp (original) +++ lldb/trunk/source/Interpreter/OptionValuePathMappings.cpp Tue Jan 8 15:25:06 2019 @@ -177,7 +177,7 @@ Status OptionValuePathMappings::SetValue size_t num_remove_indexes = remove_indexes.size(); if (num_remove_indexes) { // Sort and then erase in reverse so indexes are always valid - std::sort(remove_indexes.begin(), remove_indexes.end()); + llvm::sort(remove_indexes.begin(), remove_indexes.end()); for (size_t j = num_remove_indexes - 1; j < num_remove_indexes; ++j) { m_path_mappings.Remove(j, m_notify_changes); } Modified: lldb/trunk/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp (original) +++ lldb/trunk/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp Tue Jan 8 15:25:06 2019 @@ -453,7 +453,7 @@ DynamicLoaderHexagonDYLD::GetStepThrough AddressVector::iterator start = addrs.begin(); AddressVector::iterator end = addrs.end(); - std::sort(start, end); + llvm::sort(start, end); addrs.erase(std::unique(start, end), end); thread_plan_sp.reset(new ThreadPlanRunToAddress(thread, addrs, stop)); } Modified: lldb/trunk/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp (original) +++ lldb/trunk/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp Tue Jan 8 15:25:06 2019 @@ -496,7 +496,7 @@ DynamicLoaderPOSIXDYLD::GetStepThroughTr AddressVector::iterator start = addrs.begin(); AddressVector::iterator end = addrs.end(); - std::sort(start, end); + llvm::sort(start, end); addrs.erase(std::unique(start, end), end); thread_plan_sp.reset(new ThreadPlanRunToAddress(thread, addrs, stop)); } Modified: lldb/trunk/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp (original) +++ lldb/trunk/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp Tue Jan 8 15:25:06 2019 @@ -1653,10 +1653,10 @@ static bool ImportOffsetMap(llvm::DenseM std::vector<PairType> sorted_items; sorted_items.reserve(source_map.size()); sorted_items.assign(source_map.begin(), source_map.end()); - std::sort(sorted_items.begin(), sorted_items.end(), - [](const PairType &lhs, const PairType &rhs) { - return lhs.second < rhs.second; - }); + llvm::sort(sorted_items.begin(), sorted_items.end(), + [](const PairType &lhs, const PairType &rhs) { + return lhs.second < rhs.second; + }); for (const auto &item : sorted_items) { DeclFromUser<D> user_decl(const_cast<D *>(item.first)); Modified: lldb/trunk/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp (original) +++ lldb/trunk/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp Tue Jan 8 15:25:06 2019 @@ -464,7 +464,7 @@ void DynamicRegisterInfo::Finalize(const end = m_value_regs_map.end(); pos != end; ++pos) { if (pos->second.size() > 1) { - std::sort(pos->second.begin(), pos->second.end()); + llvm::sort(pos->second.begin(), pos->second.end()); reg_num_collection::iterator unique_end = std::unique(pos->second.begin(), pos->second.end()); if (unique_end != pos->second.end()) @@ -514,7 +514,7 @@ void DynamicRegisterInfo::Finalize(const end = m_invalidate_regs_map.end(); pos != end; ++pos) { if (pos->second.size() > 1) { - std::sort(pos->second.begin(), pos->second.end()); + llvm::sort(pos->second.begin(), pos->second.end()); reg_num_collection::iterator unique_end = std::unique(pos->second.begin(), pos->second.end()); if (unique_end != pos->second.end()) Modified: lldb/trunk/source/Plugins/Process/minidump/MinidumpParser.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/Process/minidump/MinidumpParser.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Plugins/Process/minidump/MinidumpParser.cpp (original) +++ lldb/trunk/source/Plugins/Process/minidump/MinidumpParser.cpp Tue Jan 8 15:25:06 2019 @@ -559,7 +559,7 @@ const MemoryRegionInfos &MinidumpParser: if (!CreateRegionsCacheFromMemoryInfoList(*this, m_regions)) if (!CreateRegionsCacheFromMemoryList(*this, m_regions)) CreateRegionsCacheFromMemory64List(*this, m_regions); - std::sort(m_regions.begin(), m_regions.end()); + llvm::sort(m_regions.begin(), m_regions.end()); } return m_regions; } @@ -646,10 +646,10 @@ Status MinidumpParser::Initialize() { } // Sort the file map ranges by start offset - std::sort(minidump_map.begin(), minidump_map.end(), - [](const FileRange &a, const FileRange &b) { - return a.offset < b.offset; - }); + llvm::sort(minidump_map.begin(), minidump_map.end(), + [](const FileRange &a, const FileRange &b) { + return a.offset < b.offset; + }); // Check for overlapping streams/data structures for (size_t i = 1; i < minidump_map.size(); ++i) { Modified: lldb/trunk/source/Symbol/ArmUnwindInfo.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Symbol/ArmUnwindInfo.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Symbol/ArmUnwindInfo.cpp (original) +++ lldb/trunk/source/Symbol/ArmUnwindInfo.cpp Tue Jan 8 15:25:06 2019 @@ -66,7 +66,7 @@ ArmUnwindInfo::ArmUnwindInfo(ObjectFile // Sort the entries in the exidx section. The entries should be sorted inside // the section but some old compiler isn't sorted them. - std::sort(m_exidx_entries.begin(), m_exidx_entries.end()); + llvm::sort(m_exidx_entries.begin(), m_exidx_entries.end()); } ArmUnwindInfo::~ArmUnwindInfo() {} Modified: lldb/trunk/source/Symbol/CompileUnit.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Symbol/CompileUnit.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Symbol/CompileUnit.cpp (original) +++ lldb/trunk/source/Symbol/CompileUnit.cpp Tue Jan 8 15:25:06 2019 @@ -72,10 +72,10 @@ void CompileUnit::ForeachFunction( sorted_functions.reserve(m_functions_by_uid.size()); for (auto &p : m_functions_by_uid) sorted_functions.push_back(p.second); - std::sort(sorted_functions.begin(), sorted_functions.end(), - [](const lldb::FunctionSP &a, const lldb::FunctionSP &b) { - return a->GetID() < b->GetID(); - }); + llvm::sort(sorted_functions.begin(), sorted_functions.end(), + [](const lldb::FunctionSP &a, const lldb::FunctionSP &b) { + return a->GetID() < b->GetID(); + }); for (auto &f : sorted_functions) if (lambda(f)) Modified: lldb/trunk/source/Symbol/Function.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Symbol/Function.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Symbol/Function.cpp (original) +++ lldb/trunk/source/Symbol/Function.cpp Tue Jan 8 15:25:06 2019 @@ -267,11 +267,11 @@ llvm::MutableArrayRef<CallEdge> Function m_call_edges = sym_file->ParseCallEdgesInFunction(GetID()); // Sort the call edges to speed up return_pc lookups. - std::sort(m_call_edges.begin(), m_call_edges.end(), - [](const CallEdge &LHS, const CallEdge &RHS) { - return LHS.GetUnresolvedReturnPCAddress() < - RHS.GetUnresolvedReturnPCAddress(); - }); + llvm::sort(m_call_edges.begin(), m_call_edges.end(), + [](const CallEdge &LHS, const CallEdge &RHS) { + return LHS.GetUnresolvedReturnPCAddress() < + RHS.GetUnresolvedReturnPCAddress(); + }); return m_call_edges; } Modified: lldb/trunk/source/Symbol/Symtab.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Symbol/Symtab.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Symbol/Symtab.cpp (original) +++ lldb/trunk/source/Symbol/Symtab.cpp Tue Jan 8 15:25:06 2019 @@ -610,10 +610,9 @@ void Symtab::SortSymbolIndexesByValue(st return; // Sort the indexes in place using std::stable_sort. - // NOTE: The use of std::stable_sort instead of std::sort here is strictly for - // performance, - // not correctness. The indexes vector tends to be "close" to sorted, which - // the stable sort handles better. + // NOTE: The use of std::stable_sort instead of llvm::sort here is strictly + // for performance, not correctness. The indexes vector tends to be "close" + // to sorted, which the stable sort handles better. std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS); @@ -1132,7 +1131,7 @@ size_t Symtab::FindFunctionSymbols(const } if (!symbol_indexes.empty()) { - std::sort(symbol_indexes.begin(), symbol_indexes.end()); + llvm::sort(symbol_indexes.begin(), symbol_indexes.end()); symbol_indexes.erase( std::unique(symbol_indexes.begin(), symbol_indexes.end()), symbol_indexes.end()); Modified: lldb/trunk/source/Target/Target.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Target/Target.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Target/Target.cpp (original) +++ lldb/trunk/source/Target/Target.cpp Tue Jan 8 15:25:06 2019 @@ -764,7 +764,7 @@ void Target::GetBreakpointNames(std::vec for (auto bp_name : m_breakpoint_names) { names.push_back(bp_name.first.AsCString()); } - std::sort(names.begin(), names.end()); + llvm::sort(names.begin(), names.end()); } bool Target::ProcessIsValid() { Modified: lldb/trunk/source/Utility/Timer.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Utility/Timer.cpp?rev=350679&r1=350678&r2=350679&view=diff ============================================================================== --- lldb/trunk/source/Utility/Timer.cpp (original) +++ lldb/trunk/source/Utility/Timer.cpp Tue Jan 8 15:25:06 2019 @@ -125,7 +125,7 @@ void Timer::DumpCategoryTimes(Stream *s) return; // Later code will break without any elements. // Sort by time - std::sort(sorted.begin(), sorted.end(), CategoryMapIteratorSortCriterion); + llvm::sort(sorted.begin(), sorted.end(), CategoryMapIteratorSortCriterion); for (const auto &timer : sorted) s->Printf("%.9f sec for %s\n", timer.second / 1000000000., timer.first); _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits