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