Author: Pavel Labath Date: 2022-01-27T10:05:05+01:00 New Revision: 7afd05211282c7516f0e9b3e7743b5dcc2605491
URL: https://github.com/llvm/llvm-project/commit/7afd05211282c7516f0e9b3e7743b5dcc2605491 DIFF: https://github.com/llvm/llvm-project/commit/7afd05211282c7516f0e9b3e7743b5dcc2605491.diff LOG: [lldb/DWARF] Make manual dwarf index deterministic Currently, running the test suite with LLVM_ENABLE_EXPENSIVE_CHECKS=On causes a couple of tests to fail. This happens because they expect a certain order of variables (all of them happen to use the "target variable" command, but other lookup functions should suffer from the same issues), all of which have the same name. Sort algorithms often preserve the order of equivalent elements (in this case the entries in the NameToDIE map), but that not guaranteed, and LLVM_ENABLE_EXPENSIVE_CHECKS stresses that by pre-shuffling all inputs before sorting. While this could easily be fixed by relaxing the test expectations, having a deterministic output seems like a worthwhile goal, particularly, as this could have bigger consequences than just a different print order -- in some cases we just pick the first entry that we find, whatever that is. Therefore this patch makes the sort deterministic by introducing another sort key -- UniqueCString::Sort gets a value comparator functor, which can be used to sort elements with the same name -- in the DWARF case we use DIERef::operator<, which roughly equals the order in which the entries appear in the debug info, and matches the current "accidental" order. Using a extra functor seemed preferable to using stable_sort, as the latter allocates extra O(n) of temporary memory. I observed no difference in debug info parsing speed with this patch applied. Differential Revision: https://reviews.llvm.org/D118251 Added: Modified: lldb/include/lldb/Core/UniqueCStringMap.h lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp lldb/unittests/Core/UniqueCStringMapTest.cpp Removed: ################################################################################ diff --git a/lldb/include/lldb/Core/UniqueCStringMap.h b/lldb/include/lldb/Core/UniqueCStringMap.h index e37027a0150a3..9c8b8081d374e 100644 --- a/lldb/include/lldb/Core/UniqueCStringMap.h +++ b/lldb/include/lldb/Core/UniqueCStringMap.h @@ -165,7 +165,21 @@ template <typename T> class UniqueCStringMap { // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); // } // my_map.Sort(); - void Sort() { llvm::sort(m_map.begin(), m_map.end(), Compare()); } + void Sort() { + Sort([](const T &, const T &) { return false; }); + } + + /// Sort contents of this map using the provided comparator to break ties for + /// entries with the same string value. + template <typename TCompare> void Sort(TCompare tc) { + Compare c; + llvm::sort(m_map, [&](const Entry &lhs, const Entry &rhs) -> bool { + int result = c.ThreeWay(lhs.cstring, rhs.cstring); + if (result == 0) + return tc(lhs.value, rhs.value); + return result < 0; + }); + } // Since we are using a vector to contain our items it will always double its // memory consumption as things are added to the vector, so if you intend to @@ -205,13 +219,24 @@ template <typename T> class UniqueCStringMap { return operator()(lhs, rhs.cstring); } + bool operator()(ConstString lhs, ConstString rhs) { + return ThreeWay(lhs, rhs) < 0; + } + // This is only for uniqueness, not lexicographical ordering, so we can // just compare pointers. *However*, comparing pointers from diff erent // allocations is UB, so we need compare their integral values instead. - bool operator()(ConstString lhs, ConstString rhs) { - return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString()); + int ThreeWay(ConstString lhs, ConstString rhs) { + auto lhsint = uintptr_t(lhs.GetCString()); + auto rhsint = uintptr_t(rhs.GetCString()); + if (lhsint < rhsint) + return -1; + if (lhsint > rhsint) + return 1; + return 0; } }; + collection m_map; }; diff --git a/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp b/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp index 33e2695f403a2..413920f33619e 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp @@ -21,7 +21,7 @@ using namespace lldb; using namespace lldb_private; void NameToDIE::Finalize() { - m_map.Sort(); + m_map.Sort(std::less<DIERef>()); m_map.SizeToFit(); } diff --git a/lldb/unittests/Core/UniqueCStringMapTest.cpp b/lldb/unittests/Core/UniqueCStringMapTest.cpp index 25bc28538e65f..aa1cdbadc958e 100644 --- a/lldb/unittests/Core/UniqueCStringMapTest.cpp +++ b/lldb/unittests/Core/UniqueCStringMapTest.cpp @@ -51,3 +51,18 @@ TEST(UniqueCStringMap, NoDefaultConstructor) { EXPECT_THAT(Map.GetValues(Bar, Values), 0); EXPECT_THAT(Values, testing::IsEmpty()); } + +TEST(UniqueCStringMap, ValueCompare) { + UniqueCStringMap<int> Map; + + ConstString Foo("foo"); + + Map.Append(Foo, 0); + Map.Append(Foo, 5); + Map.Append(Foo, -5); + + Map.Sort(std::less<int>()); + std::vector<int> Values; + EXPECT_THAT(Map.GetValues(Foo, Values), 3); + EXPECT_THAT(Values, testing::ElementsAre(-5, 0, 5)); +} _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
