contrib/llvm/tools/lldb/source/Symbol/LineTable.cpp

   1 //===-- LineTable.cpp -------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "lldb/Symbol/LineTable.h"
  11 #include "lldb/Core/Address.h"
  12 #include "lldb/Core/Module.h"
  13 #include "lldb/Core/Section.h"
  14 #include "lldb/Symbol/CompileUnit.h"
  15 #include "lldb/Utility/Stream.h"
  16 #include <algorithm>
  17
  18 using namespace lldb;
  19 using namespace lldb_private;
  20
  21 //----------------------------------------------------------------------
  22 // LineTable constructor
  23 //----------------------------------------------------------------------
  24 LineTable::LineTable(CompileUnit *comp_unit)
  25     : m_comp_unit(comp_unit), m_entries() {}
  26
  27 //----------------------------------------------------------------------
  28 // Destructor
  29 //----------------------------------------------------------------------
  30 LineTable::~LineTable() {}
  31
  32 void LineTable::InsertLineEntry(lldb::addr_t file_addr, uint32_t line,
  33                                 uint16_t column, uint16_t file_idx,
  34                                 bool is_start_of_statement,
  35                                 bool is_start_of_basic_block,
  36                                 bool is_prologue_end, bool is_epilogue_begin,
  37                                 bool is_terminal_entry) {
  38   Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
  39               is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
  40               is_terminal_entry);
  41
  42   entry_collection::iterator begin_pos = m_entries.begin();
  43   entry_collection::iterator end_pos = m_entries.end();
  44   LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
  45   entry_collection::iterator pos =
  46       upper_bound(begin_pos, end_pos, entry, less_than_bp);
  47
  48   //  Stream s(stdout);
  49   //  s << "\n\nBefore:\n";
  50   //  Dump (&s, Address::DumpStyleFileAddress);
  51   m_entries.insert(pos, entry);
  52   //  s << "After:\n";
  53   //  Dump (&s, Address::DumpStyleFileAddress);
  54 }
  55
  56 LineSequence::LineSequence() {}
  57
  58 void LineTable::LineSequenceImpl::Clear() { m_entries.clear(); }
  59
  60 LineSequence *LineTable::CreateLineSequenceContainer() {
  61   return new LineTable::LineSequenceImpl();
  62 }
  63
  64 void LineTable::AppendLineEntryToSequence(
  65     LineSequence *sequence, lldb::addr_t file_addr, uint32_t line,
  66     uint16_t column, uint16_t file_idx, bool is_start_of_statement,
  67     bool is_start_of_basic_block, bool is_prologue_end, bool is_epilogue_begin,
  68     bool is_terminal_entry) {
  69   assert(sequence != nullptr);
  70   LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
  71   Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
  72               is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
  73               is_terminal_entry);
  74   entry_collection &entries = seq->m_entries;
  75   // Replace the last entry if the address is the same, otherwise append it. If
  76   // we have multiple line entries at the same address, this indicates illegal
  77   // DWARF so this "fixes" the line table to be correct. If not fixed this can
  78   // cause a line entry's address that when resolved back to a symbol context,
  79   // could resolve to a different line entry. We really want a
  80   // 1 to 1 mapping
  81   // here to avoid these kinds of inconsistencies. We will need tor revisit
  82   // this if the DWARF line tables are updated to allow multiple entries at the
  83   // same address legally.
  84   if (!entries.empty() && entries.back().file_addr == file_addr) {
  85     // GCC don't use the is_prologue_end flag to mark the first instruction
  86     // after the prologue.
  87     // Instead of it it is issuing a line table entry for the first instruction
  88     // of the prologue and one for the first instruction after the prologue. If
  89     // the size of the prologue is 0 instruction then the 2 line entry will
  90     // have the same file address. Removing it will remove our ability to
  91     // properly detect the location of the end of prologe so we set the
  92     // prologue_end flag to preserve this information (setting the prologue_end
  93     // flag for an entry what is after the prologue end don't have any effect)
  94     entry.is_prologue_end = entry.file_idx == entries.back().file_idx;
  95     entries.back() = entry;
  96   } else
  97     entries.push_back(entry);
  98 }
  99
 100 void LineTable::InsertSequence(LineSequence *sequence) {
 101   assert(sequence != nullptr);
 102   LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
 103   if (seq->m_entries.empty())
 104     return;
 105   Entry &entry = seq->m_entries.front();
 106
 107   // If the first entry address in this sequence is greater than or equal to
 108   // the address of the last item in our entry collection, just append.
 109   if (m_entries.empty() ||
 110       !Entry::EntryAddressLessThan(entry, m_entries.back())) {
 111     m_entries.insert(m_entries.end(), seq->m_entries.begin(),
 112                      seq->m_entries.end());
 113     return;
 114   }
 115
 116   // Otherwise, find where this belongs in the collection
 117   entry_collection::iterator begin_pos = m_entries.begin();
 118   entry_collection::iterator end_pos = m_entries.end();
 119   LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
 120   entry_collection::iterator pos =
 121       upper_bound(begin_pos, end_pos, entry, less_than_bp);
 122
 123   // We should never insert a sequence in the middle of another sequence
 124   if (pos != begin_pos) {
 125     while (pos < end_pos && !((pos - 1)->is_terminal_entry))
 126       pos++;
 127   }
 128
 129 #ifdef LLDB_CONFIGURATION_DEBUG
 130   // If we aren't inserting at the beginning, the previous entry should
 131   // terminate a sequence.
 132   if (pos != begin_pos) {
 133     entry_collection::iterator prev_pos = pos - 1;
 134     assert(prev_pos->is_terminal_entry);
 135   }
 136 #endif
 137   m_entries.insert(pos, seq->m_entries.begin(), seq->m_entries.end());
 138 }
 139
 140 //----------------------------------------------------------------------
 141 LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(
 142     LineTable *line_table)
 143     : m_line_table(line_table) {}
 144
 145 bool LineTable::Entry::LessThanBinaryPredicate::
 146 operator()(const LineTable::Entry &a, const LineTable::Entry &b) const {
 147 #define LT_COMPARE(a, b)                                                       \
 148   if (a != b)                                                                  \
 149   return a < b
 150   LT_COMPARE(a.file_addr, b.file_addr);
 151   // b and a reversed on purpose below.
 152   LT_COMPARE(b.is_terminal_entry, a.is_terminal_entry);
 153   LT_COMPARE(a.line, b.line);
 154   LT_COMPARE(a.column, b.column);
 155   LT_COMPARE(a.is_start_of_statement, b.is_start_of_statement);
 156   LT_COMPARE(a.is_start_of_basic_block, b.is_start_of_basic_block);
 157   // b and a reversed on purpose below.
 158   LT_COMPARE(b.is_prologue_end, a.is_prologue_end);
 159   LT_COMPARE(a.is_epilogue_begin, b.is_epilogue_begin);
 160   LT_COMPARE(a.file_idx, b.file_idx);
 161   return false;
 162 #undef LT_COMPARE
 163 }
 164
 165 uint32_t LineTable::GetSize() const { return m_entries.size(); }
 166
 167 bool LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry) {
 168   if (idx < m_entries.size()) {
 169     ConvertEntryAtIndexToLineEntry(idx, line_entry);
 170     return true;
 171   }
 172   line_entry.Clear();
 173   return false;
 174 }
 175
 176 bool LineTable::FindLineEntryByAddress(const Address &so_addr,
 177                                        LineEntry &line_entry,
 178                                        uint32_t *index_ptr) {
 179   if (index_ptr != nullptr)
 180     *index_ptr = UINT32_MAX;
 181
 182   bool success = false;
 183
 184   if (so_addr.GetModule().get() == m_comp_unit->GetModule().get()) {
 185     Entry search_entry;
 186     search_entry.file_addr = so_addr.GetFileAddress();
 187     if (search_entry.file_addr != LLDB_INVALID_ADDRESS) {
 188       entry_collection::const_iterator begin_pos = m_entries.begin();
 189       entry_collection::const_iterator end_pos = m_entries.end();
 190       entry_collection::const_iterator pos = lower_bound(
 191           begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan);
 192       if (pos != end_pos) {
 193         if (pos != begin_pos) {
 194           if (pos->file_addr != search_entry.file_addr)
 195             --pos;
 196           else if (pos->file_addr == search_entry.file_addr) {
 197             // If this is a termination entry, it shouldn't match since entries
 198             // with the "is_terminal_entry" member set to true are termination
 199             // entries that define the range for the previous entry.
 200             if (pos->is_terminal_entry) {
 201               // The matching entry is a terminal entry, so we skip ahead to
 202               // the next entry to see if there is another entry following this
 203               // one whose section/offset matches.
 204               ++pos;
 205               if (pos != end_pos) {
 206                 if (pos->file_addr != search_entry.file_addr)
 207                   pos = end_pos;
 208               }
 209             }
 210
 211             if (pos != end_pos) {
 212               // While in the same section/offset backup to find the first line
 213               // entry that matches the address in case there are multiple
 214               while (pos != begin_pos) {
 215                 entry_collection::const_iterator prev_pos = pos - 1;
 216                 if (prev_pos->file_addr == search_entry.file_addr &&
 217                     prev_pos->is_terminal_entry == false)
 218                   --pos;
 219                 else
 220                   break;
 221               }
 222             }
 223           }
 224         }
 225         else
 226         {
 227           // There might be code in the containing objfile before the first
 228           // line table entry.  Make sure that does not get considered part of
 229           // the first line table entry.
 230           if (pos->file_addr > so_addr.GetFileAddress())
 231             return false;
 232         }
 233
 234         // Make sure we have a valid match and that the match isn't a
 235         // terminating entry for a previous line...
 236         if (pos != end_pos && pos->is_terminal_entry == false) {
 237           uint32_t match_idx = std::distance(begin_pos, pos);
 238           success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry);
 239           if (index_ptr != nullptr && success)
 240             *index_ptr = match_idx;
 241         }
 242       }
 243     }
 244   }
 245   return success;
 246 }
 247
 248 bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx,
 249                                                LineEntry &line_entry) {
 250   if (idx < m_entries.size()) {
 251     const Entry &entry = m_entries[idx];
 252     ModuleSP module_sp(m_comp_unit->GetModule());
 253     if (module_sp &&
 254         module_sp->ResolveFileAddress(entry.file_addr,
 255                                       line_entry.range.GetBaseAddress())) {
 256       if (!entry.is_terminal_entry && idx + 1 < m_entries.size())
 257         line_entry.range.SetByteSize(m_entries[idx + 1].file_addr -
 258                                      entry.file_addr);
 259       else
 260         line_entry.range.SetByteSize(0);
 261
 262       line_entry.file =
 263           m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(entry.file_idx);
 264       line_entry.original_file =
 265           m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(entry.file_idx);
 266       line_entry.line = entry.line;
 267       line_entry.column = entry.column;
 268       line_entry.is_start_of_statement = entry.is_start_of_statement;
 269       line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;
 270       line_entry.is_prologue_end = entry.is_prologue_end;
 271       line_entry.is_epilogue_begin = entry.is_epilogue_begin;
 272       line_entry.is_terminal_entry = entry.is_terminal_entry;
 273       return true;
 274     }
 275   }
 276   return false;
 277 }
 278
 279 uint32_t LineTable::FindLineEntryIndexByFileIndex(
 280     uint32_t start_idx, const std::vector<uint32_t> &file_indexes,
 281     uint32_t line, bool exact, LineEntry *line_entry_ptr) {
 282
 283   const size_t count = m_entries.size();
 284   std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin();
 285   std::vector<uint32_t>::const_iterator end_pos = file_indexes.end();
 286   size_t best_match = UINT32_MAX;
 287
 288   for (size_t idx = start_idx; idx < count; ++idx) {
 289     // Skip line table rows that terminate the previous row (is_terminal_entry
 290     // is non-zero)
 291     if (m_entries[idx].is_terminal_entry)
 292       continue;
 293
 294     if (find(begin_pos, end_pos, m_entries[idx].file_idx) == end_pos)
 295       continue;
 296
 297     // Exact match always wins.  Otherwise try to find the closest line > the
 298     // desired line.
 299     // FIXME: Maybe want to find the line closest before and the line closest
 300     // after and
 301     // if they're not in the same function, don't return a match.
 302
 303     if (m_entries[idx].line < line) {
 304       continue;
 305     } else if (m_entries[idx].line == line) {
 306       if (line_entry_ptr)
 307         ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
 308       return idx;
 309     } else if (!exact) {
 310       if (best_match == UINT32_MAX)
 311         best_match = idx;
 312       else if (m_entries[idx].line < m_entries[best_match].line)
 313         best_match = idx;
 314     }
 315   }
 316
 317   if (best_match != UINT32_MAX) {
 318     if (line_entry_ptr)
 319       ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
 320     return best_match;
 321   }
 322   return UINT32_MAX;
 323 }
 324
 325 uint32_t LineTable::FindLineEntryIndexByFileIndex(uint32_t start_idx,
 326                                                   uint32_t file_idx,
 327                                                   uint32_t line, bool exact,
 328                                                   LineEntry *line_entry_ptr) {
 329   const size_t count = m_entries.size();
 330   size_t best_match = UINT32_MAX;
 331
 332   for (size_t idx = start_idx; idx < count; ++idx) {
 333     // Skip line table rows that terminate the previous row (is_terminal_entry
 334     // is non-zero)
 335     if (m_entries[idx].is_terminal_entry)
 336       continue;
 337
 338     if (m_entries[idx].file_idx != file_idx)
 339       continue;
 340
 341     // Exact match always wins.  Otherwise try to find the closest line > the
 342     // desired line.
 343     // FIXME: Maybe want to find the line closest before and the line closest
 344     // after and
 345     // if they're not in the same function, don't return a match.
 346
 347     if (m_entries[idx].line < line) {
 348       continue;
 349     } else if (m_entries[idx].line == line) {
 350       if (line_entry_ptr)
 351         ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
 352       return idx;
 353     } else if (!exact) {
 354       if (best_match == UINT32_MAX)
 355         best_match = idx;
 356       else if (m_entries[idx].line < m_entries[best_match].line)
 357         best_match = idx;
 358     }
 359   }
 360
 361   if (best_match != UINT32_MAX) {
 362     if (line_entry_ptr)
 363       ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
 364     return best_match;
 365   }
 366   return UINT32_MAX;
 367 }
 368
 369 size_t LineTable::FineLineEntriesForFileIndex(uint32_t file_idx, bool append,
 370                                               SymbolContextList &sc_list) {
 371
 372   if (!append)
 373     sc_list.Clear();
 374
 375   size_t num_added = 0;
 376   const size_t count = m_entries.size();
 377   if (count > 0) {
 378     SymbolContext sc(m_comp_unit);
 379
 380     for (size_t idx = 0; idx < count; ++idx) {
 381       // Skip line table rows that terminate the previous row
 382       // (is_terminal_entry is non-zero)
 383       if (m_entries[idx].is_terminal_entry)
 384         continue;
 385
 386       if (m_entries[idx].file_idx == file_idx) {
 387         if (ConvertEntryAtIndexToLineEntry(idx, sc.line_entry)) {
 388           ++num_added;
 389           sc_list.Append(sc);
 390         }
 391       }
 392     }
 393   }
 394   return num_added;
 395 }
 396
 397 void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style,
 398                      Address::DumpStyle fallback_style, bool show_line_ranges) {
 399   const size_t count = m_entries.size();
 400   LineEntry line_entry;
 401   FileSpec prev_file;
 402   for (size_t idx = 0; idx < count; ++idx) {
 403     ConvertEntryAtIndexToLineEntry(idx, line_entry);
 404     line_entry.Dump(s, target, prev_file != line_entry.original_file, style,
 405                     fallback_style, show_line_ranges);
 406     s->EOL();
 407     prev_file = line_entry.original_file;
 408   }
 409 }
 410
 411 void LineTable::GetDescription(Stream *s, Target *target,
 412                                DescriptionLevel level) {
 413   const size_t count = m_entries.size();
 414   LineEntry line_entry;
 415   for (size_t idx = 0; idx < count; ++idx) {
 416     ConvertEntryAtIndexToLineEntry(idx, line_entry);
 417     line_entry.GetDescription(s, level, m_comp_unit, target, true);
 418     s->EOL();
 419   }
 420 }
 421
 422 size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,
 423                                                  bool append) {
 424   if (!append)
 425     file_ranges.Clear();
 426   const size_t initial_count = file_ranges.GetSize();
 427
 428   const size_t count = m_entries.size();
 429   LineEntry line_entry;
 430   FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0);
 431   for (size_t idx = 0; idx < count; ++idx) {
 432     const Entry &entry = m_entries[idx];
 433
 434     if (entry.is_terminal_entry) {
 435       if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) {
 436         range.SetRangeEnd(entry.file_addr);
 437         file_ranges.Append(range);
 438         range.Clear(LLDB_INVALID_ADDRESS);
 439       }
 440     } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) {
 441       range.SetRangeBase(entry.file_addr);
 442     }
 443   }
 444   return file_ranges.GetSize() - initial_count;
 445 }
 446
 447 LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) {
 448   std::unique_ptr<LineTable> line_table_ap(new LineTable(m_comp_unit));
 449   LineSequenceImpl sequence;
 450   const size_t count = m_entries.size();
 451   LineEntry line_entry;
 452   const FileRangeMap::Entry *file_range_entry = nullptr;
 453   const FileRangeMap::Entry *prev_file_range_entry = nullptr;
 454   lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS;
 455   bool prev_entry_was_linked = false;
 456   bool range_changed = false;
 457   for (size_t idx = 0; idx < count; ++idx) {
 458     const Entry &entry = m_entries[idx];
 459
 460     const bool end_sequence = entry.is_terminal_entry;
 461     const lldb::addr_t lookup_file_addr =
 462         entry.file_addr - (end_sequence ? 1 : 0);
 463     if (file_range_entry == nullptr ||
 464         !file_range_entry->Contains(lookup_file_addr)) {
 465       prev_file_range_entry = file_range_entry;
 466       file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr);
 467       range_changed = true;
 468     }
 469
 470     lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS;
 471     lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS;
 472
 473     bool terminate_previous_entry = false;
 474     if (file_range_entry) {
 475       entry_linked_file_addr = entry.file_addr -
 476                                file_range_entry->GetRangeBase() +
 477                                file_range_entry->data;
 478       // Determine if we need to terminate the previous entry when the previous
 479       // entry was not contiguous with this one after being linked.
 480       if (range_changed && prev_file_range_entry) {
 481         prev_end_entry_linked_file_addr =
 482             std::min<lldb::addr_t>(entry.file_addr,
 483                                    prev_file_range_entry->GetRangeEnd()) -
 484             prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
 485         if (prev_end_entry_linked_file_addr != entry_linked_file_addr)
 486           terminate_previous_entry = prev_entry_was_linked;
 487       }
 488     } else if (prev_entry_was_linked) {
 489       // This entry doesn't have a remapping and it needs to be removed. Watch
 490       // out in case we need to terminate a previous entry needs to be
 491       // terminated now that one line entry in a sequence is not longer valid.
 492       if (!sequence.m_entries.empty() &&
 493           !sequence.m_entries.back().is_terminal_entry) {
 494         terminate_previous_entry = true;
 495       }
 496     }
 497
 498     if (terminate_previous_entry && !sequence.m_entries.empty()) {
 499       assert(prev_file_addr != LLDB_INVALID_ADDRESS);
 500       UNUSED_IF_ASSERT_DISABLED(prev_file_addr);
 501       sequence.m_entries.push_back(sequence.m_entries.back());
 502       if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS)
 503         prev_end_entry_linked_file_addr =
 504             std::min<lldb::addr_t>(entry.file_addr,
 505                                    prev_file_range_entry->GetRangeEnd()) -
 506             prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
 507       sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr;
 508       sequence.m_entries.back().is_terminal_entry = true;
 509
 510       // Append the sequence since we just terminated the previous one
 511       line_table_ap->InsertSequence(&sequence);
 512       sequence.Clear();
 513     }
 514
 515     // Now link the current entry
 516     if (file_range_entry) {
 517       // This entry has an address remapping and it needs to have its address
 518       // relinked
 519       sequence.m_entries.push_back(entry);
 520       sequence.m_entries.back().file_addr = entry_linked_file_addr;
 521     }
 522
 523     // If we have items in the sequence and the last entry is a terminal entry,
 524     // insert this sequence into our new line table.
 525     if (!sequence.m_entries.empty() &&
 526         sequence.m_entries.back().is_terminal_entry) {
 527       line_table_ap->InsertSequence(&sequence);
 528       sequence.Clear();
 529       prev_entry_was_linked = false;
 530     } else {
 531       prev_entry_was_linked = file_range_entry != nullptr;
 532     }
 533     prev_file_addr = entry.file_addr;
 534     range_changed = false;
 535   }
 536   if (line_table_ap->m_entries.empty())
 537     return nullptr;
 538   return line_table_ap.release();
 539 }