467 lines · cpp
1//===-- LineTable.cpp -----------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "lldb/Symbol/LineTable.h"10#include "lldb/Core/Address.h"11#include "lldb/Core/Module.h"12#include "lldb/Core/Section.h"13#include "lldb/Symbol/CompileUnit.h"14#include "lldb/Utility/Stream.h"15#include <algorithm>16 17using namespace lldb;18using namespace lldb_private;19 20// LineTable constructor21LineTable::LineTable(CompileUnit *comp_unit)22 : m_comp_unit(comp_unit), m_entries() {}23 24LineTable::LineTable(CompileUnit *comp_unit, std::vector<Sequence> &&sequences)25 : m_comp_unit(comp_unit), m_entries() {26 LessThanBinaryPredicate less_than_bp(this);27 llvm::stable_sort(sequences, less_than_bp);28 for (const Sequence &seq : sequences) {29 m_entries.insert(m_entries.end(), seq.m_entries.begin(),30 seq.m_entries.end());31 }32}33 34// Destructor35LineTable::~LineTable() = default;36 37void LineTable::InsertLineEntry(lldb::addr_t file_addr, uint32_t line,38 uint16_t column, uint16_t file_idx,39 bool is_start_of_statement,40 bool is_start_of_basic_block,41 bool is_prologue_end, bool is_epilogue_begin,42 bool is_terminal_entry) {43 Entry entry(file_addr, line, column, file_idx, is_start_of_statement,44 is_start_of_basic_block, is_prologue_end, is_epilogue_begin,45 is_terminal_entry);46 47 LessThanBinaryPredicate less_than_bp(this);48 entry_collection::iterator pos =49 llvm::upper_bound(m_entries, entry, less_than_bp);50 51 // Stream s(stdout);52 // s << "\n\nBefore:\n";53 // Dump (&s, Address::DumpStyleFileAddress);54 m_entries.insert(pos, entry);55 // s << "After:\n";56 // Dump (&s, Address::DumpStyleFileAddress);57}58 59void LineTable::AppendLineEntryToSequence(60 Sequence &sequence, lldb::addr_t file_addr, uint32_t line, uint16_t column,61 uint16_t file_idx, bool is_start_of_statement, bool is_start_of_basic_block,62 bool is_prologue_end, bool is_epilogue_begin, bool is_terminal_entry) {63 Entry entry(file_addr, line, column, file_idx, is_start_of_statement,64 is_start_of_basic_block, is_prologue_end, is_epilogue_begin,65 is_terminal_entry);66 entry_collection &entries = sequence.m_entries;67 // Replace the last entry if the address is the same, otherwise append it. If68 // we have multiple line entries at the same address, this indicates illegal69 // DWARF so this "fixes" the line table to be correct. If not fixed this can70 // cause a line entry's address that when resolved back to a symbol context,71 // could resolve to a different line entry. We really want a72 // 1 to 1 mapping73 // here to avoid these kinds of inconsistencies. We will need tor revisit74 // this if the DWARF line tables are updated to allow multiple entries at the75 // same address legally.76 if (!entries.empty() && entries.back().file_addr == file_addr) {77 // GCC don't use the is_prologue_end flag to mark the first instruction78 // after the prologue.79 // Instead of it is issuing a line table entry for the first instruction80 // of the prologue and one for the first instruction after the prologue. If81 // the size of the prologue is 0 instruction then the 2 line entry will82 // have the same file address. Removing it will remove our ability to83 // properly detect the location of the end of prologe so we set the84 // prologue_end flag to preserve this information (setting the prologue_end85 // flag for an entry what is after the prologue end don't have any effect)86 entry.is_prologue_end = entry.file_idx == entries.back().file_idx;87 entries.back() = entry;88 } else89 entries.push_back(entry);90}91 92void LineTable::InsertSequence(Sequence sequence) {93 if (sequence.m_entries.empty())94 return;95 const Entry &entry = sequence.m_entries.front();96 97 // If the first entry address in this sequence is greater than or equal to98 // the address of the last item in our entry collection, just append.99 if (m_entries.empty() ||100 !Entry::EntryAddressLessThan(entry, m_entries.back())) {101 m_entries.insert(m_entries.end(), sequence.m_entries.begin(),102 sequence.m_entries.end());103 return;104 }105 106 // Otherwise, find where this belongs in the collection107 entry_collection::iterator begin_pos = m_entries.begin();108 entry_collection::iterator end_pos = m_entries.end();109 LessThanBinaryPredicate less_than_bp(this);110 entry_collection::iterator pos =111 std::upper_bound(begin_pos, end_pos, entry, less_than_bp);112 113 // We should never insert a sequence in the middle of another sequence114 if (pos != begin_pos) {115 while (pos < end_pos && !((pos - 1)->is_terminal_entry))116 pos++;117 }118 119#ifndef NDEBUG120 // If we aren't inserting at the beginning, the previous entry should121 // terminate a sequence.122 if (pos != begin_pos) {123 entry_collection::iterator prev_pos = pos - 1;124 assert(prev_pos->is_terminal_entry);125 }126#endif127 m_entries.insert(pos, sequence.m_entries.begin(), sequence.m_entries.end());128}129 130bool LineTable::LessThanBinaryPredicate::operator()(const Entry &a,131 const Entry &b) const {132#define LT_COMPARE(a, b) \133 if (a != b) \134 return a < b135 LT_COMPARE(a.file_addr, b.file_addr);136 // b and a reversed on purpose below.137 LT_COMPARE(b.is_terminal_entry, a.is_terminal_entry);138 LT_COMPARE(a.line, b.line);139 LT_COMPARE(a.column, b.column);140 LT_COMPARE(a.is_start_of_statement, b.is_start_of_statement);141 LT_COMPARE(a.is_start_of_basic_block, b.is_start_of_basic_block);142 // b and a reversed on purpose below.143 LT_COMPARE(b.is_prologue_end, a.is_prologue_end);144 LT_COMPARE(a.is_epilogue_begin, b.is_epilogue_begin);145 LT_COMPARE(a.file_idx, b.file_idx);146 return false;147#undef LT_COMPARE148}149 150bool LineTable::LessThanBinaryPredicate::operator()(151 const Sequence &seq_a, const Sequence &seq_b) const {152 return (*this)(seq_a.m_entries.front(), seq_b.m_entries.front());153}154 155uint32_t LineTable::GetSize() const { return m_entries.size(); }156 157bool LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry) {158 if (idx < m_entries.size()) {159 ConvertEntryAtIndexToLineEntry(idx, line_entry);160 return true;161 }162 line_entry.Clear();163 return false;164}165 166uint32_t LineTable::lower_bound(const Address &so_addr) const {167 if (so_addr.GetModule() != m_comp_unit->GetModule())168 return GetSize();169 170 Entry search_entry;171 search_entry.file_addr = so_addr.GetFileAddress();172 if (search_entry.file_addr == LLDB_INVALID_ADDRESS)173 return GetSize();174 175 // This is not a typo. upper_bound returns the first entry which definitely176 // does not contain this address, which means the entry before it *might*177 // contain it -- if it is not a termination entry.178 auto pos =179 llvm::upper_bound(m_entries, search_entry, Entry::EntryAddressLessThan);180 181 if (pos != m_entries.begin() && !std::prev(pos)->is_terminal_entry)182 --pos;183 184 return std::distance(m_entries.begin(), pos);185}186 187std::pair<uint32_t, uint32_t>188LineTable::GetLineEntryIndexRange(const AddressRange &range) const {189 uint32_t first = lower_bound(range.GetBaseAddress());190 if (first >= GetSize() || range.GetByteSize() == 0)191 return {first, first};192 193 Entry search_entry;194 search_entry.file_addr =195 range.GetBaseAddress().GetFileAddress() + range.GetByteSize();196 197 // lower_bound returns the first entry which starts on or after the given198 // address, which is exactly what we want -- *except* if the entry is a199 // termination entry (in that case, we want the one after it).200 auto pos =201 std::lower_bound(std::next(m_entries.begin(), first), m_entries.end(),202 search_entry, Entry::EntryAddressLessThan);203 if (pos != m_entries.end() && pos->file_addr == search_entry.file_addr &&204 pos->is_terminal_entry)205 ++pos;206 207 return {first, std::distance(m_entries.begin(), pos)};208}209 210bool LineTable::FindLineEntryByAddress(const Address &so_addr,211 LineEntry &line_entry,212 uint32_t *index_ptr) {213 if (index_ptr != nullptr)214 *index_ptr = UINT32_MAX;215 216 uint32_t idx = lower_bound(so_addr);217 if (idx >= GetSize())218 return false;219 220 addr_t file_addr = so_addr.GetFileAddress();221 if (m_entries[idx].file_addr > file_addr)222 return false;223 224 bool success = ConvertEntryAtIndexToLineEntry(idx, line_entry);225 if (index_ptr != nullptr && success)226 *index_ptr = idx;227 return success;228}229 230bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx,231 LineEntry &line_entry) {232 if (idx >= m_entries.size())233 return false;234 235 const Entry &entry = m_entries[idx];236 ModuleSP module_sp(m_comp_unit->GetModule());237 if (!module_sp)238 return false;239 240 addr_t file_addr = entry.file_addr;241 242 // A terminal entry can point outside of a module or a section. Decrement the243 // address to ensure it resolves correctly.244 if (entry.is_terminal_entry)245 --file_addr;246 247 if (!module_sp->ResolveFileAddress(file_addr,248 line_entry.range.GetBaseAddress()))249 return false;250 251 // Now undo the decrement above.252 if (entry.is_terminal_entry)253 line_entry.range.GetBaseAddress().Slide(1);254 255 if (!entry.is_terminal_entry && idx + 1 < m_entries.size())256 line_entry.range.SetByteSize(m_entries[idx + 1].file_addr -257 entry.file_addr);258 else259 line_entry.range.SetByteSize(0);260 261 line_entry.file_sp =262 m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx);263 line_entry.original_file_sp =264 m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx);265 line_entry.line = entry.line;266 line_entry.column = entry.column;267 line_entry.is_start_of_statement = entry.is_start_of_statement;268 line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;269 line_entry.is_prologue_end = entry.is_prologue_end;270 line_entry.is_epilogue_begin = entry.is_epilogue_begin;271 line_entry.is_terminal_entry = entry.is_terminal_entry;272 return true;273}274 275uint32_t LineTable::FindLineEntryIndexByFileIndex(276 uint32_t start_idx, uint32_t file_idx,277 const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {278 auto file_idx_matcher = [](uint32_t file_index, uint16_t entry_file_idx) {279 return file_index == entry_file_idx;280 };281 return FindLineEntryIndexByFileIndexImpl<uint32_t>(282 283 start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);284}285 286uint32_t LineTable::FindLineEntryIndexByFileIndex(287 uint32_t start_idx, const std::vector<uint32_t> &file_idx,288 const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {289 auto file_idx_matcher = [](const std::vector<uint32_t> &file_indexes,290 uint16_t entry_file_idx) {291 return llvm::is_contained(file_indexes, entry_file_idx);292 };293 294 return FindLineEntryIndexByFileIndexImpl<std::vector<uint32_t>>(295 start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);296}297 298size_t LineTable::FindLineEntriesForFileIndex(uint32_t file_idx, bool append,299 SymbolContextList &sc_list) {300 301 if (!append)302 sc_list.Clear();303 304 size_t num_added = 0;305 const size_t count = m_entries.size();306 if (count > 0) {307 SymbolContext sc(m_comp_unit);308 309 for (size_t idx = 0; idx < count; ++idx) {310 // Skip line table rows that terminate the previous row311 // (is_terminal_entry is non-zero)312 if (m_entries[idx].is_terminal_entry)313 continue;314 315 if (m_entries[idx].file_idx == file_idx) {316 if (ConvertEntryAtIndexToLineEntry(idx, sc.line_entry)) {317 ++num_added;318 sc_list.Append(sc);319 }320 }321 }322 }323 return num_added;324}325 326void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style,327 Address::DumpStyle fallback_style, bool show_line_ranges) {328 const size_t count = m_entries.size();329 LineEntry line_entry;330 SupportFileNSP prev_file = std::make_shared<SupportFile>();331 for (size_t idx = 0; idx < count; ++idx) {332 ConvertEntryAtIndexToLineEntry(idx, line_entry);333 line_entry.Dump(s, target, !prev_file->Equal(*line_entry.original_file_sp),334 style, fallback_style, show_line_ranges);335 s->EOL();336 prev_file = line_entry.original_file_sp;337 }338}339 340void LineTable::GetDescription(Stream *s, Target *target,341 DescriptionLevel level) {342 const size_t count = m_entries.size();343 LineEntry line_entry;344 for (size_t idx = 0; idx < count; ++idx) {345 ConvertEntryAtIndexToLineEntry(idx, line_entry);346 line_entry.GetDescription(s, level, m_comp_unit, target, true);347 s->EOL();348 }349}350 351size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,352 bool append) {353 if (!append)354 file_ranges.Clear();355 const size_t initial_count = file_ranges.GetSize();356 357 const size_t count = m_entries.size();358 LineEntry line_entry;359 FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0);360 for (size_t idx = 0; idx < count; ++idx) {361 const Entry &entry = m_entries[idx];362 363 if (entry.is_terminal_entry) {364 if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) {365 range.SetRangeEnd(entry.file_addr);366 file_ranges.Append(range);367 range.Clear(LLDB_INVALID_ADDRESS);368 }369 } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) {370 range.SetRangeBase(entry.file_addr);371 }372 }373 return file_ranges.GetSize() - initial_count;374}375 376LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) {377 std::unique_ptr<LineTable> line_table_up(new LineTable(m_comp_unit));378 Sequence sequence;379 const size_t count = m_entries.size();380 LineEntry line_entry;381 const FileRangeMap::Entry *file_range_entry = nullptr;382 const FileRangeMap::Entry *prev_file_range_entry = nullptr;383 lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS;384 bool prev_entry_was_linked = false;385 bool range_changed = false;386 for (size_t idx = 0; idx < count; ++idx) {387 const Entry &entry = m_entries[idx];388 389 const bool end_sequence = entry.is_terminal_entry;390 const lldb::addr_t lookup_file_addr =391 entry.file_addr - (end_sequence ? 1 : 0);392 if (file_range_entry == nullptr ||393 !file_range_entry->Contains(lookup_file_addr)) {394 prev_file_range_entry = file_range_entry;395 file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr);396 range_changed = true;397 }398 399 lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS;400 lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS;401 402 bool terminate_previous_entry = false;403 if (file_range_entry) {404 entry_linked_file_addr = entry.file_addr -405 file_range_entry->GetRangeBase() +406 file_range_entry->data;407 // Determine if we need to terminate the previous entry when the previous408 // entry was not contiguous with this one after being linked.409 if (range_changed && prev_file_range_entry) {410 prev_end_entry_linked_file_addr =411 std::min<lldb::addr_t>(entry.file_addr,412 prev_file_range_entry->GetRangeEnd()) -413 prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;414 if (prev_end_entry_linked_file_addr != entry_linked_file_addr)415 terminate_previous_entry = prev_entry_was_linked;416 }417 } else if (prev_entry_was_linked) {418 // This entry doesn't have a remapping and it needs to be removed. Watch419 // out in case we need to terminate a previous entry needs to be420 // terminated now that one line entry in a sequence is not longer valid.421 if (!sequence.m_entries.empty() &&422 !sequence.m_entries.back().is_terminal_entry) {423 terminate_previous_entry = true;424 }425 }426 427 if (terminate_previous_entry && !sequence.m_entries.empty()) {428 assert(prev_file_addr != LLDB_INVALID_ADDRESS);429 UNUSED_IF_ASSERT_DISABLED(prev_file_addr);430 sequence.m_entries.push_back(sequence.m_entries.back());431 if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS)432 prev_end_entry_linked_file_addr =433 std::min<lldb::addr_t>(entry.file_addr,434 prev_file_range_entry->GetRangeEnd()) -435 prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;436 sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr;437 sequence.m_entries.back().is_terminal_entry = true;438 439 // Append the sequence since we just terminated the previous one440 line_table_up->InsertSequence(std::move(sequence));441 }442 443 // Now link the current entry444 if (file_range_entry) {445 // This entry has an address remapping and it needs to have its address446 // relinked447 sequence.m_entries.push_back(entry);448 sequence.m_entries.back().file_addr = entry_linked_file_addr;449 }450 451 // If we have items in the sequence and the last entry is a terminal entry,452 // insert this sequence into our new line table.453 if (!sequence.m_entries.empty() &&454 sequence.m_entries.back().is_terminal_entry) {455 line_table_up->InsertSequence(std::move(sequence));456 prev_entry_was_linked = false;457 } else {458 prev_entry_was_linked = file_range_entry != nullptr;459 }460 prev_file_addr = entry.file_addr;461 range_changed = false;462 }463 if (line_table_up->m_entries.empty())464 return nullptr;465 return line_table_up.release();466}467