//===-- LineTable.cpp -----------------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #include "lldb/Symbol/LineTable.h" #include "lldb/Core/Address.h" #include "lldb/Core/Module.h" #include "lldb/Core/Section.h" #include "lldb/Symbol/CompileUnit.h" #include "lldb/Utility/Stream.h" #include using namespace lldb; using namespace lldb_private; // LineTable constructor LineTable::LineTable(CompileUnit *comp_unit) : m_comp_unit(comp_unit), m_entries() {} LineTable::LineTable(CompileUnit *comp_unit, std::vector &&sequences) : m_comp_unit(comp_unit), m_entries() { LessThanBinaryPredicate less_than_bp(this); llvm::stable_sort(sequences, less_than_bp); for (const Sequence &seq : sequences) { m_entries.insert(m_entries.end(), seq.m_entries.begin(), seq.m_entries.end()); } } // Destructor LineTable::~LineTable() = default; void LineTable::InsertLineEntry(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, bool is_prologue_end, bool is_epilogue_begin, bool is_terminal_entry) { Entry entry(file_addr, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry); LessThanBinaryPredicate less_than_bp(this); entry_collection::iterator pos = llvm::upper_bound(m_entries, entry, less_than_bp); // Stream s(stdout); // s << "\n\nBefore:\n"; // Dump (&s, Address::DumpStyleFileAddress); m_entries.insert(pos, entry); // s << "After:\n"; // Dump (&s, Address::DumpStyleFileAddress); } void LineTable::AppendLineEntryToSequence( Sequence &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, bool is_prologue_end, bool is_epilogue_begin, bool is_terminal_entry) { Entry entry(file_addr, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry); entry_collection &entries = sequence.m_entries; // Replace the last entry if the address is the same, otherwise append it. If // we have multiple line entries at the same address, this indicates illegal // DWARF so this "fixes" the line table to be correct. If not fixed this can // cause a line entry's address that when resolved back to a symbol context, // could resolve to a different line entry. We really want a // 1 to 1 mapping // here to avoid these kinds of inconsistencies. We will need tor revisit // this if the DWARF line tables are updated to allow multiple entries at the // same address legally. if (!entries.empty() && entries.back().file_addr == file_addr) { // GCC don't use the is_prologue_end flag to mark the first instruction // after the prologue. // Instead of it is issuing a line table entry for the first instruction // of the prologue and one for the first instruction after the prologue. If // the size of the prologue is 0 instruction then the 2 line entry will // have the same file address. Removing it will remove our ability to // properly detect the location of the end of prologe so we set the // prologue_end flag to preserve this information (setting the prologue_end // flag for an entry what is after the prologue end don't have any effect) entry.is_prologue_end = entry.file_idx == entries.back().file_idx; entries.back() = entry; } else entries.push_back(entry); } void LineTable::InsertSequence(Sequence sequence) { if (sequence.m_entries.empty()) return; const Entry &entry = sequence.m_entries.front(); // If the first entry address in this sequence is greater than or equal to // the address of the last item in our entry collection, just append. if (m_entries.empty() || !Entry::EntryAddressLessThan(entry, m_entries.back())) { m_entries.insert(m_entries.end(), sequence.m_entries.begin(), sequence.m_entries.end()); return; } // Otherwise, find where this belongs in the collection entry_collection::iterator begin_pos = m_entries.begin(); entry_collection::iterator end_pos = m_entries.end(); LessThanBinaryPredicate less_than_bp(this); entry_collection::iterator pos = std::upper_bound(begin_pos, end_pos, entry, less_than_bp); // We should never insert a sequence in the middle of another sequence if (pos != begin_pos) { while (pos < end_pos && !((pos - 1)->is_terminal_entry)) pos++; } #ifndef NDEBUG // If we aren't inserting at the beginning, the previous entry should // terminate a sequence. if (pos != begin_pos) { entry_collection::iterator prev_pos = pos - 1; assert(prev_pos->is_terminal_entry); } #endif m_entries.insert(pos, sequence.m_entries.begin(), sequence.m_entries.end()); } bool LineTable::LessThanBinaryPredicate::operator()(const Entry &a, const Entry &b) const { #define LT_COMPARE(a, b) \ if (a != b) \ return a < b LT_COMPARE(a.file_addr, b.file_addr); // b and a reversed on purpose below. LT_COMPARE(b.is_terminal_entry, a.is_terminal_entry); LT_COMPARE(a.line, b.line); LT_COMPARE(a.column, b.column); LT_COMPARE(a.is_start_of_statement, b.is_start_of_statement); LT_COMPARE(a.is_start_of_basic_block, b.is_start_of_basic_block); // b and a reversed on purpose below. LT_COMPARE(b.is_prologue_end, a.is_prologue_end); LT_COMPARE(a.is_epilogue_begin, b.is_epilogue_begin); LT_COMPARE(a.file_idx, b.file_idx); return false; #undef LT_COMPARE } bool LineTable::LessThanBinaryPredicate::operator()( const Sequence &seq_a, const Sequence &seq_b) const { 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) { if (idx < m_entries.size()) { ConvertEntryAtIndexToLineEntry(idx, line_entry); return true; } line_entry.Clear(); return false; } uint32_t LineTable::lower_bound(const Address &so_addr) const { if (so_addr.GetModule() != m_comp_unit->GetModule()) return GetSize(); Entry search_entry; search_entry.file_addr = so_addr.GetFileAddress(); if (search_entry.file_addr == LLDB_INVALID_ADDRESS) return GetSize(); // This is not a typo. upper_bound returns the first entry which definitely // does not contain this address, which means the entry before it *might* // contain it -- if it is not a termination entry. auto pos = llvm::upper_bound(m_entries, search_entry, Entry::EntryAddressLessThan); if (pos != m_entries.begin() && !std::prev(pos)->is_terminal_entry) --pos; return std::distance(m_entries.begin(), pos); } std::pair LineTable::GetLineEntryIndexRange(const AddressRange &range) const { uint32_t first = lower_bound(range.GetBaseAddress()); if (first >= GetSize() || range.GetByteSize() == 0) return {first, first}; Entry search_entry; search_entry.file_addr = range.GetBaseAddress().GetFileAddress() + range.GetByteSize(); // lower_bound returns the first entry which starts on or after the given // address, which is exactly what we want -- *except* if the entry is a // termination entry (in that case, we want the one after it). auto pos = std::lower_bound(std::next(m_entries.begin(), first), m_entries.end(), search_entry, Entry::EntryAddressLessThan); if (pos != m_entries.end() && pos->file_addr == search_entry.file_addr && pos->is_terminal_entry) ++pos; return {first, std::distance(m_entries.begin(), pos)}; } bool LineTable::FindLineEntryByAddress(const Address &so_addr, LineEntry &line_entry, uint32_t *index_ptr) { if (index_ptr != nullptr) *index_ptr = UINT32_MAX; uint32_t idx = lower_bound(so_addr); if (idx >= GetSize()) return false; addr_t file_addr = so_addr.GetFileAddress(); if (m_entries[idx].file_addr > file_addr) return false; bool success = ConvertEntryAtIndexToLineEntry(idx, line_entry); if (index_ptr != nullptr && success) *index_ptr = idx; return success; } bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx, LineEntry &line_entry) { if (idx >= m_entries.size()) return false; const Entry &entry = m_entries[idx]; ModuleSP module_sp(m_comp_unit->GetModule()); if (!module_sp) return false; addr_t file_addr = entry.file_addr; // A terminal entry can point outside of a module or a section. Decrement the // address to ensure it resolves correctly. if (entry.is_terminal_entry) --file_addr; if (!module_sp->ResolveFileAddress(file_addr, line_entry.range.GetBaseAddress())) return false; // Now undo the decrement above. if (entry.is_terminal_entry) line_entry.range.GetBaseAddress().Slide(1); if (!entry.is_terminal_entry && idx + 1 < m_entries.size()) line_entry.range.SetByteSize(m_entries[idx + 1].file_addr - entry.file_addr); else line_entry.range.SetByteSize(0); line_entry.file_sp = m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx); line_entry.original_file_sp = m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx); line_entry.line = entry.line; line_entry.column = entry.column; line_entry.is_start_of_statement = entry.is_start_of_statement; line_entry.is_start_of_basic_block = entry.is_start_of_basic_block; line_entry.is_prologue_end = entry.is_prologue_end; line_entry.is_epilogue_begin = entry.is_epilogue_begin; line_entry.is_terminal_entry = entry.is_terminal_entry; return true; } uint32_t LineTable::FindLineEntryIndexByFileIndex( uint32_t start_idx, uint32_t file_idx, const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) { auto file_idx_matcher = [](uint32_t file_index, uint16_t entry_file_idx) { return file_index == entry_file_idx; }; return FindLineEntryIndexByFileIndexImpl( start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher); } uint32_t LineTable::FindLineEntryIndexByFileIndex( uint32_t start_idx, const std::vector &file_idx, const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) { auto file_idx_matcher = [](const std::vector &file_indexes, uint16_t entry_file_idx) { return llvm::is_contained(file_indexes, entry_file_idx); }; return FindLineEntryIndexByFileIndexImpl>( start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher); } size_t LineTable::FindLineEntriesForFileIndex(uint32_t file_idx, bool append, SymbolContextList &sc_list) { if (!append) sc_list.Clear(); size_t num_added = 0; const size_t count = m_entries.size(); if (count > 0) { SymbolContext sc(m_comp_unit); for (size_t idx = 0; idx < count; ++idx) { // Skip line table rows that terminate the previous row // (is_terminal_entry is non-zero) if (m_entries[idx].is_terminal_entry) continue; if (m_entries[idx].file_idx == file_idx) { if (ConvertEntryAtIndexToLineEntry(idx, sc.line_entry)) { ++num_added; sc_list.Append(sc); } } } } return num_added; } void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style, Address::DumpStyle fallback_style, bool show_line_ranges) { const size_t count = m_entries.size(); LineEntry line_entry; SupportFileSP prev_file; for (size_t idx = 0; idx < count; ++idx) { ConvertEntryAtIndexToLineEntry(idx, line_entry); line_entry.Dump(s, target, !prev_file->Equal(*line_entry.original_file_sp), style, fallback_style, show_line_ranges); s->EOL(); prev_file = line_entry.original_file_sp; } } void LineTable::GetDescription(Stream *s, Target *target, DescriptionLevel level) { const size_t count = m_entries.size(); LineEntry line_entry; for (size_t idx = 0; idx < count; ++idx) { ConvertEntryAtIndexToLineEntry(idx, line_entry); line_entry.GetDescription(s, level, m_comp_unit, target, true); s->EOL(); } } size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges, bool append) { if (!append) file_ranges.Clear(); const size_t initial_count = file_ranges.GetSize(); const size_t count = m_entries.size(); LineEntry line_entry; FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0); for (size_t idx = 0; idx < count; ++idx) { const Entry &entry = m_entries[idx]; if (entry.is_terminal_entry) { if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) { range.SetRangeEnd(entry.file_addr); file_ranges.Append(range); range.Clear(LLDB_INVALID_ADDRESS); } } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) { range.SetRangeBase(entry.file_addr); } } return file_ranges.GetSize() - initial_count; } LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) { std::unique_ptr line_table_up(new LineTable(m_comp_unit)); Sequence sequence; const size_t count = m_entries.size(); LineEntry line_entry; const FileRangeMap::Entry *file_range_entry = nullptr; const FileRangeMap::Entry *prev_file_range_entry = nullptr; lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS; bool prev_entry_was_linked = false; bool range_changed = false; for (size_t idx = 0; idx < count; ++idx) { const Entry &entry = m_entries[idx]; const bool end_sequence = entry.is_terminal_entry; const lldb::addr_t lookup_file_addr = entry.file_addr - (end_sequence ? 1 : 0); if (file_range_entry == nullptr || !file_range_entry->Contains(lookup_file_addr)) { prev_file_range_entry = file_range_entry; file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr); range_changed = true; } lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS; lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS; bool terminate_previous_entry = false; if (file_range_entry) { entry_linked_file_addr = entry.file_addr - file_range_entry->GetRangeBase() + file_range_entry->data; // Determine if we need to terminate the previous entry when the previous // entry was not contiguous with this one after being linked. if (range_changed && prev_file_range_entry) { prev_end_entry_linked_file_addr = std::min(entry.file_addr, prev_file_range_entry->GetRangeEnd()) - prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data; if (prev_end_entry_linked_file_addr != entry_linked_file_addr) terminate_previous_entry = prev_entry_was_linked; } } else if (prev_entry_was_linked) { // This entry doesn't have a remapping and it needs to be removed. Watch // out in case we need to terminate a previous entry needs to be // terminated now that one line entry in a sequence is not longer valid. if (!sequence.m_entries.empty() && !sequence.m_entries.back().is_terminal_entry) { terminate_previous_entry = true; } } if (terminate_previous_entry && !sequence.m_entries.empty()) { assert(prev_file_addr != LLDB_INVALID_ADDRESS); UNUSED_IF_ASSERT_DISABLED(prev_file_addr); sequence.m_entries.push_back(sequence.m_entries.back()); if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS) prev_end_entry_linked_file_addr = std::min(entry.file_addr, prev_file_range_entry->GetRangeEnd()) - prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data; sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr; sequence.m_entries.back().is_terminal_entry = true; // Append the sequence since we just terminated the previous one line_table_up->InsertSequence(std::move(sequence)); } // Now link the current entry if (file_range_entry) { // This entry has an address remapping and it needs to have its address // relinked sequence.m_entries.push_back(entry); sequence.m_entries.back().file_addr = entry_linked_file_addr; } // If we have items in the sequence and the last entry is a terminal entry, // insert this sequence into our new line table. if (!sequence.m_entries.empty() && sequence.m_entries.back().is_terminal_entry) { line_table_up->InsertSequence(std::move(sequence)); prev_entry_was_linked = false; } else { prev_entry_was_linked = file_range_entry != nullptr; } prev_file_addr = entry.file_addr; range_changed = false; } if (line_table_up->m_entries.empty()) return nullptr; return line_table_up.release(); }