mirror of
https://github.com/llvm/llvm-project.git
synced 2025-04-18 09:06:43 +00:00
036f5c0f58
I *think* this should be equivalent to the original implementation for all line tables occurring in practice. One difference I'm aware of is that the original implementation tried to return the first line entry out of multiple ones for the same address. However, this is not possible (anymore?) because of the check in LineTable::AppendLineEntryToSequence.
467 lines
18 KiB
C++
467 lines
18 KiB
C++
//===-- 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 <algorithm>
|
||
|
||
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<Sequence> &&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<uint32_t, uint32_t>
|
||
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<uint32_t>(
|
||
|
||
start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
|
||
}
|
||
|
||
uint32_t LineTable::FindLineEntryIndexByFileIndex(
|
||
uint32_t start_idx, const std::vector<uint32_t> &file_idx,
|
||
const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
|
||
auto file_idx_matcher = [](const std::vector<uint32_t> &file_indexes,
|
||
uint16_t entry_file_idx) {
|
||
return llvm::is_contained(file_indexes, entry_file_idx);
|
||
};
|
||
|
||
return FindLineEntryIndexByFileIndexImpl<std::vector<uint32_t>>(
|
||
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<LineTable> 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<lldb::addr_t>(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<lldb::addr_t>(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();
|
||
}
|