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/Section.h" 12 #include "lldb/Core/Stream.h" 13 #include "lldb/Symbol/CompileUnit.h" 14 #include "lldb/Symbol/LineTable.h" 15 #include <algorithm> 16 17 using namespace lldb; 18 using namespace lldb_private; 19 20 //---------------------------------------------------------------------- 21 // LineTable constructor 22 //---------------------------------------------------------------------- 23 LineTable::LineTable(CompileUnit* comp_unit) : 24 m_comp_unit(comp_unit), 25 m_section_list(), 26 m_entries() 27 { 28 } 29 30 //---------------------------------------------------------------------- 31 // Destructor 32 //---------------------------------------------------------------------- 33 LineTable::~LineTable() 34 { 35 } 36 37 //void 38 //LineTable::AddLineEntry(const LineEntry& entry) 39 //{ 40 // // Do a binary search for the correct entry and insert it 41 // m_line_entries.insert(std::upper_bound(m_line_entries.begin(), m_line_entries.end(), entry), entry); 42 //} 43 44 void 45 LineTable::AppendLineEntry 46 ( 47 SectionSP& section_sp, 48 lldb::addr_t section_offset, 49 uint32_t line, 50 uint16_t column, 51 uint16_t file_idx, 52 bool is_start_of_statement, 53 bool is_start_of_basic_block, 54 bool is_prologue_end, 55 bool is_epilogue_begin, 56 bool is_terminal_entry 57 ) 58 { 59 uint32_t sect_idx = m_section_list.AddUniqueSection (section_sp); 60 // Make sure we don't user more than 256 sections as that is all we have 61 // room for in the LineTable::Entry::m_sect_idx. If this assert fires, 62 // we will need to m_sect_idx have more bits... 63 assert((section_offset & 0xffffffffff000000ull) == 0); 64 Entry entry(sect_idx, section_offset, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry); 65 m_entries.push_back (entry); 66 } 67 68 69 void 70 LineTable::InsertLineEntry 71 ( 72 SectionSP& section_sp, 73 lldb::addr_t section_offset, 74 uint32_t line, 75 uint16_t column, 76 uint16_t file_idx, 77 bool is_start_of_statement, 78 bool is_start_of_basic_block, 79 bool is_prologue_end, 80 bool is_epilogue_begin, 81 bool is_terminal_entry 82 ) 83 { 84 SectionSP line_section_sp(section_sp); 85 const Section *linked_section = line_section_sp->GetLinkedSection(); 86 if (linked_section) 87 { 88 section_offset += line_section_sp->GetLinkedOffset(); 89 line_section_sp = linked_section->GetSharedPointer(); 90 assert(line_section_sp.get()); 91 } 92 93 uint32_t sect_idx = m_section_list.AddUniqueSection (line_section_sp); 94 // Make sure we don't user more than 256 sections as that is all we have 95 // room for in the LineTable::Entry::m_sect_idx. If this assert fires, 96 // we will need to m_sect_idx have more bits... 97 assert((section_offset & 0xffffffffff000000ull) == 0); 98 Entry entry(sect_idx, section_offset, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry); 99 100 entry_collection::iterator begin_pos = m_entries.begin(); 101 entry_collection::iterator end_pos = m_entries.end(); 102 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this); 103 entry_collection::iterator pos = upper_bound(begin_pos, end_pos, entry, less_than_bp); 104 105 // Stream s(stdout); 106 // s << "\n\nBefore:\n"; 107 // Dump (&s, Address::DumpStyleFileAddress); 108 m_entries.insert(pos, entry); 109 // s << "After:\n"; 110 // Dump (&s, Address::DumpStyleFileAddress); 111 } 112 113 //---------------------------------------------------------------------- 114 LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(LineTable *line_table) : 115 m_line_table (line_table) 116 { 117 } 118 119 bool 120 LineTable::Entry::LessThanBinaryPredicate::operator() (const LineTable::Entry& a, const LineTable::Entry& b) const 121 { 122 if (a.sect_idx == b.sect_idx) 123 { 124 #define LT_COMPARE(a,b) if (a != b) return a < b 125 LT_COMPARE (a.sect_offset, b.sect_offset); 126 LT_COMPARE (a.line, b.line); 127 LT_COMPARE (a.column, b.column); 128 LT_COMPARE (a.is_start_of_statement, b.is_start_of_statement); 129 LT_COMPARE (a.is_start_of_basic_block, b.is_start_of_basic_block); 130 // b and a reversed on purpose below. 131 LT_COMPARE (b.is_prologue_end, a.is_prologue_end); 132 LT_COMPARE (a.is_epilogue_begin, b.is_epilogue_begin); 133 // b and a reversed on purpose below. 134 LT_COMPARE (b.is_terminal_entry, a.is_terminal_entry); 135 LT_COMPARE (a.file_idx, b.file_idx); 136 return false; 137 #undef LT_COMPARE 138 } 139 140 const Section *a_section = m_line_table->GetSectionForEntryIndex (a.sect_idx); 141 const Section *b_section = m_line_table->GetSectionForEntryIndex (b.sect_idx); 142 return Section::Compare(*a_section, *b_section) < 0; 143 } 144 145 146 Section * 147 LineTable::GetSectionForEntryIndex (uint32_t idx) 148 { 149 if (idx < m_section_list.GetSize()) 150 return m_section_list.GetSectionAtIndex(idx).get(); 151 return NULL; 152 } 153 154 uint32_t 155 LineTable::GetSize() const 156 { 157 return m_entries.size(); 158 } 159 160 bool 161 LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry& line_entry) 162 { 163 if (idx < m_entries.size()) 164 { 165 ConvertEntryAtIndexToLineEntry (idx, line_entry); 166 return true; 167 } 168 line_entry.Clear(); 169 return false; 170 } 171 172 bool 173 LineTable::FindLineEntryByAddress (const Address &so_addr, LineEntry& line_entry, uint32_t *index_ptr) 174 { 175 if (index_ptr != NULL ) 176 *index_ptr = UINT32_MAX; 177 178 bool success = false; 179 uint32_t sect_idx = m_section_list.FindSectionIndex (so_addr.GetSection()); 180 if (sect_idx != UINT32_MAX) 181 { 182 Entry search_entry; 183 search_entry.sect_idx = sect_idx; 184 search_entry.sect_offset = so_addr.GetOffset(); 185 186 entry_collection::const_iterator begin_pos = m_entries.begin(); 187 entry_collection::const_iterator end_pos = m_entries.end(); 188 entry_collection::const_iterator pos = lower_bound(begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan); 189 if (pos != end_pos) 190 { 191 if (pos != begin_pos) 192 { 193 if (pos->sect_offset != search_entry.sect_offset) 194 --pos; 195 else if (pos->sect_offset == search_entry.sect_offset) 196 { 197 // If this is a termination entry, it should't match since 198 // entries with the "is_terminal_entry" member set to true 199 // are termination entries that define the range for the 200 // previous entry. 201 if (pos->is_terminal_entry) 202 { 203 // The matching entry is a terminal entry, so we skip 204 // ahead to the next entry to see if there is another 205 // entry following this one whose section/offset matches. 206 ++pos; 207 if (pos != end_pos) 208 { 209 if (pos->sect_offset != search_entry.sect_offset) 210 pos = end_pos; 211 } 212 } 213 214 if (pos != end_pos) 215 { 216 // While in the same section/offset backup to find the first 217 // line entry that matches the address in case there are 218 // multiple 219 while (pos != begin_pos) 220 { 221 entry_collection::const_iterator prev_pos = pos - 1; 222 if (prev_pos->sect_idx == search_entry.sect_idx && 223 prev_pos->sect_offset == search_entry.sect_offset && 224 prev_pos->is_terminal_entry == false) 225 --pos; 226 else 227 break; 228 } 229 } 230 } 231 232 } 233 234 if (pos != end_pos) 235 { 236 uint32_t match_idx = std::distance (begin_pos, pos); 237 success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry); 238 if (index_ptr != NULL && success) 239 *index_ptr = match_idx; 240 } 241 } 242 } 243 return success; 244 } 245 246 247 bool 248 LineTable::ConvertEntryAtIndexToLineEntry (uint32_t idx, LineEntry &line_entry) 249 { 250 if (idx < m_entries.size()) 251 { 252 const Entry& entry = m_entries[idx]; 253 line_entry.range.GetBaseAddress().SetSection(m_section_list.GetSectionAtIndex (entry.sect_idx).get()); 254 line_entry.range.GetBaseAddress().SetOffset(entry.sect_offset); 255 if (!entry.is_terminal_entry && idx + 1 < m_entries.size()) 256 { 257 const Entry& next_entry = m_entries[idx+1]; 258 if (next_entry.sect_idx == entry.sect_idx) 259 { 260 line_entry.range.SetByteSize(next_entry.sect_offset - entry.sect_offset); 261 } 262 else 263 { 264 Address next_line_addr(m_section_list.GetSectionAtIndex (next_entry.sect_idx).get(), next_entry.sect_offset); 265 line_entry.range.SetByteSize(next_line_addr.GetFileAddress() - line_entry.range.GetBaseAddress().GetFileAddress()); 266 } 267 } 268 else 269 line_entry.range.SetByteSize(0); 270 line_entry.file = m_comp_unit->GetSupportFiles().GetFileSpecAtIndex (entry.file_idx); 271 line_entry.line = entry.line; 272 line_entry.column = entry.column; 273 line_entry.is_start_of_statement = entry.is_start_of_statement; 274 line_entry.is_start_of_basic_block = entry.is_start_of_basic_block; 275 line_entry.is_prologue_end = entry.is_prologue_end; 276 line_entry.is_epilogue_begin = entry.is_epilogue_begin; 277 line_entry.is_terminal_entry = entry.is_terminal_entry; 278 return true; 279 } 280 return false; 281 } 282 283 uint32_t 284 LineTable::FindLineEntryIndexByFileIndex 285 ( 286 uint32_t start_idx, 287 const std::vector<uint32_t> &file_indexes, 288 uint32_t line, 289 bool exact, 290 LineEntry* line_entry_ptr 291 ) 292 { 293 294 const size_t count = m_entries.size(); 295 std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin(); 296 std::vector<uint32_t>::const_iterator end_pos = file_indexes.end(); 297 size_t best_match = UINT32_MAX; 298 299 for (size_t idx = start_idx; idx < count; ++idx) 300 { 301 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 302 if (m_entries[idx].is_terminal_entry) 303 continue; 304 305 if (find (begin_pos, end_pos, m_entries[idx].file_idx) == end_pos) 306 continue; 307 308 // Exact match always wins. Otherwise try to find the closest line > the desired 309 // line. 310 // FIXME: Maybe want to find the line closest before and the line closest after and 311 // if they're not in the same function, don't return a match. 312 313 if (m_entries[idx].line < line) 314 { 315 continue; 316 } 317 else if (m_entries[idx].line == line) 318 { 319 if (line_entry_ptr) 320 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 321 return idx; 322 } 323 else if (!exact) 324 { 325 if (best_match == UINT32_MAX) 326 best_match = idx; 327 else if (m_entries[idx].line < m_entries[best_match].line) 328 best_match = idx; 329 } 330 } 331 332 if (best_match != UINT32_MAX) 333 { 334 if (line_entry_ptr) 335 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 336 return best_match; 337 } 338 return UINT32_MAX; 339 } 340 341 uint32_t 342 LineTable::FindLineEntryIndexByFileIndex (uint32_t start_idx, uint32_t file_idx, uint32_t line, bool exact, LineEntry* line_entry_ptr) 343 { 344 const size_t count = m_entries.size(); 345 size_t best_match = UINT32_MAX; 346 347 for (size_t idx = start_idx; idx < count; ++idx) 348 { 349 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 350 if (m_entries[idx].is_terminal_entry) 351 continue; 352 353 if (m_entries[idx].file_idx != file_idx) 354 continue; 355 356 // Exact match always wins. Otherwise try to find the closest line > the desired 357 // line. 358 // FIXME: Maybe want to find the line closest before and the line closest after and 359 // if they're not in the same function, don't return a match. 360 361 if (m_entries[idx].line < line) 362 { 363 continue; 364 } 365 else if (m_entries[idx].line == line) 366 { 367 if (line_entry_ptr) 368 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 369 return idx; 370 } 371 else if (!exact) 372 { 373 if (best_match == UINT32_MAX) 374 best_match = idx; 375 else if (m_entries[idx].line < m_entries[best_match].line) 376 best_match = idx; 377 } 378 } 379 380 if (best_match != UINT32_MAX) 381 { 382 if (line_entry_ptr) 383 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 384 return best_match; 385 } 386 return UINT32_MAX; 387 } 388 389 void 390 LineTable::Dump (Stream *s, Target *target, Address::DumpStyle style, Address::DumpStyle fallback_style, bool show_line_ranges) 391 { 392 const size_t count = m_entries.size(); 393 LineEntry line_entry; 394 FileSpec prev_file; 395 for (size_t idx = 0; idx < count; ++idx) 396 { 397 ConvertEntryAtIndexToLineEntry (idx, line_entry); 398 line_entry.Dump (s, target, prev_file != line_entry.file, style, fallback_style, show_line_ranges); 399 s->EOL(); 400 prev_file = line_entry.file; 401 } 402 } 403 404 405 void 406 LineTable::GetDescription (Stream *s, Target *target, DescriptionLevel level) 407 { 408 const size_t count = m_entries.size(); 409 LineEntry line_entry; 410 for (size_t idx = 0; idx < count; ++idx) 411 { 412 ConvertEntryAtIndexToLineEntry (idx, line_entry); 413 line_entry.GetDescription (s, level, m_comp_unit, target, true); 414 s->EOL(); 415 } 416 } 417 418 419 420