Author: Unnar Freyr Erlendsson Date: 2020-01-20T12:50:58+01:00 New Revision: 39f1335486eae355b2259d59549382e5cee9e38f
URL: https://github.com/llvm/llvm-project/commit/39f1335486eae355b2259d59549382e5cee9e38f DIFF: https://github.com/llvm/llvm-project/commit/39f1335486eae355b2259d59549382e5cee9e38f.diff LOG: Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort Summary: Motivation: When setting breakpoints in certain projects line sequences are frequently being inserted out of order. Rather than inserting sequences one at a time into a sorted line table, store all the line sequences as we're building them up and sort and flatten afterwards. Reviewers: jdoerfert, labath Reviewed By: labath Subscribers: teemperor, labath, mgrang, JDevlieghere, lldb-commits Tags: #lldb Differential Revision: https://reviews.llvm.org/D72909 Added: Modified: lldb/include/lldb/Symbol/LineTable.h lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp lldb/source/Symbol/LineTable.cpp Removed: ################################################################################ diff --git a/lldb/include/lldb/Symbol/LineTable.h b/lldb/include/lldb/Symbol/LineTable.h index 043f3eb895cb..363966aae9f3 100644 --- a/lldb/include/lldb/Symbol/LineTable.h +++ b/lldb/include/lldb/Symbol/LineTable.h @@ -42,6 +42,12 @@ class LineTable { /// The compile unit to which this line table belongs. LineTable(CompileUnit *comp_unit); + /// Construct with entries found in \a sequences. + /// + /// \param[in] sequences + /// Unsorted list of line sequences. + LineTable(CompileUnit *comp_unit, std::vector<LineSequence *> &sequences); + /// Destructor. ~LineTable(); @@ -64,11 +70,11 @@ class LineTable { bool is_epilogue_begin, bool is_terminal_entry); // Used to instantiate the LineSequence helper class - LineSequence *CreateLineSequenceContainer(); + static LineSequence *CreateLineSequenceContainer(); // Append an entry to a caller-provided collection that will later be // inserted in this line table. - void AppendLineEntryToSequence(LineSequence *sequence, lldb::addr_t file_addr, + static void AppendLineEntryToSequence(LineSequence *sequence, lldb::addr_t file_addr, uint32_t line, uint16_t column, uint16_t file_idx, bool is_start_of_statement, bool is_start_of_basic_block, @@ -259,6 +265,7 @@ class LineTable { public: LessThanBinaryPredicate(LineTable *line_table); bool operator()(const LineTable::Entry &, const LineTable::Entry &) const; + bool operator()(const LineSequence*, const LineSequence*) const; protected: LineTable *m_line_table; diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp index 29012bdb95a9..493a3160376f 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp @@ -1007,20 +1007,22 @@ bool SymbolFileDWARF::ParseLineTable(CompileUnit &comp_unit) { // FIXME: Rather than parsing the whole line table and then copying it over // into LLDB, we should explore using a callback to populate the line table // while we parse to reduce memory usage. - std::unique_ptr<LineTable> line_table_up = - std::make_unique<LineTable>(&comp_unit); - LineSequence *sequence = line_table_up->CreateLineSequenceContainer(); + LineSequence *sequence = LineTable::CreateLineSequenceContainer(); + std::vector<LineSequence *> sequences; for (auto &row : line_table->Rows) { - line_table_up->AppendLineEntryToSequence( + LineTable::AppendLineEntryToSequence( sequence, row.Address.Address, row.Line, row.Column, row.File, row.IsStmt, row.BasicBlock, row.PrologueEnd, row.EpilogueBegin, row.EndSequence); if (row.EndSequence) { - line_table_up->InsertSequence(sequence); - sequence = line_table_up->CreateLineSequenceContainer(); + sequences.push_back(sequence); + sequence = LineTable::CreateLineSequenceContainer(); } } + std::unique_ptr<LineTable> line_table_up = + std::make_unique<LineTable>(&comp_unit, sequences); + if (SymbolFileDWARFDebugMap *debug_map_symfile = GetDebugMapSymfile()) { // We have an object file that has a line table with addresses that are not // linked. We need to link the line table and convert the addresses that diff --git a/lldb/source/Symbol/LineTable.cpp b/lldb/source/Symbol/LineTable.cpp index fecc90c409f2..21e451021cd6 100644 --- a/lldb/source/Symbol/LineTable.cpp +++ b/lldb/source/Symbol/LineTable.cpp @@ -21,6 +21,17 @@ using namespace lldb_private; LineTable::LineTable(CompileUnit *comp_unit) : m_comp_unit(comp_unit), m_entries() {} +LineTable::LineTable(CompileUnit *comp_unit, std::vector<LineSequence *> &sequences) + : m_comp_unit(comp_unit), m_entries() { + LineTable::Entry::LessThanBinaryPredicate less_than_bp(this); + std::sort(sequences.begin(), sequences.end(), less_than_bp); + for (auto *sequence : sequences) { + LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence); + m_entries.insert(m_entries.end(), seq->m_entries.begin(), + seq->m_entries.end()); + } +} + // Destructor LineTable::~LineTable() {} @@ -154,6 +165,13 @@ operator()(const LineTable::Entry &a, const LineTable::Entry &b) const { #undef LT_COMPARE } +bool LineTable::Entry::LessThanBinaryPredicate:: +operator()(const LineSequence *sequence_a, const LineSequence *sequence_b) const { + auto *seq_a = static_cast<const LineSequenceImpl *>(sequence_a); + auto *seq_b = static_cast<const LineSequenceImpl *>(sequence_b); + return (*this)(seq_a->m_entries.front(), seq_b->m_entries.front()); +} + uint32_t LineTable::GetSize() const { return m_entries.size(); } bool LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry) { _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits