1 //===-- DWARFDebugLine.cpp ------------------------------------------------===// 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 "DWARFDebugLine.h" 11 #include "llvm/Support/Dwarf.h" 12 #include "llvm/Support/Format.h" 13 #include "llvm/Support/raw_ostream.h" 14 #include <algorithm> 15 using namespace llvm; 16 using namespace dwarf; 17 18 void DWARFDebugLine::Prologue::dump(raw_ostream &OS) const { 19 OS << "Line table prologue:\n" 20 << format(" total_length: 0x%8.8x\n", TotalLength) 21 << format(" version: %u\n", Version) 22 << format("prologue_length: 0x%8.8x\n", PrologueLength) 23 << format("min_inst_length: %u\n", MinInstLength) 24 << format("default_is_stmt: %u\n", DefaultIsStmt) 25 << format(" line_base: %i\n", LineBase) 26 << format(" line_range: %u\n", LineRange) 27 << format(" opcode_base: %u\n", OpcodeBase); 28 29 for (uint32_t i = 0; i < StandardOpcodeLengths.size(); ++i) 30 OS << format("standard_opcode_lengths[%s] = %u\n", LNStandardString(i+1), 31 StandardOpcodeLengths[i]); 32 33 if (!IncludeDirectories.empty()) 34 for (uint32_t i = 0; i < IncludeDirectories.size(); ++i) 35 OS << format("include_directories[%3u] = '", i+1) 36 << IncludeDirectories[i] << "'\n"; 37 38 if (!FileNames.empty()) { 39 OS << " Dir Mod Time File Len File Name\n" 40 << " ---- ---------- ---------- -----------" 41 "----------------\n"; 42 for (uint32_t i = 0; i < FileNames.size(); ++i) { 43 const FileNameEntry& fileEntry = FileNames[i]; 44 OS << format("file_names[%3u] %4" PRIu64 " ", i+1, fileEntry.DirIdx) 45 << format("0x%8.8" PRIx64 " 0x%8.8" PRIx64 " ", 46 fileEntry.ModTime, fileEntry.Length) 47 << fileEntry.Name << '\n'; 48 } 49 } 50 } 51 52 void DWARFDebugLine::Row::postAppend() { 53 BasicBlock = false; 54 PrologueEnd = false; 55 EpilogueBegin = false; 56 } 57 58 void DWARFDebugLine::Row::reset(bool default_is_stmt) { 59 Address = 0; 60 Line = 1; 61 Column = 0; 62 File = 1; 63 Isa = 0; 64 IsStmt = default_is_stmt; 65 BasicBlock = false; 66 EndSequence = false; 67 PrologueEnd = false; 68 EpilogueBegin = false; 69 } 70 71 void DWARFDebugLine::Row::dump(raw_ostream &OS) const { 72 OS << format("0x%16.16" PRIx64 " %6u %6u", Address, Line, Column) 73 << format(" %6u %3u ", File, Isa) 74 << (IsStmt ? " is_stmt" : "") 75 << (BasicBlock ? " basic_block" : "") 76 << (PrologueEnd ? " prologue_end" : "") 77 << (EpilogueBegin ? " epilogue_begin" : "") 78 << (EndSequence ? " end_sequence" : "") 79 << '\n'; 80 } 81 82 void DWARFDebugLine::LineTable::dump(raw_ostream &OS) const { 83 Prologue.dump(OS); 84 OS << '\n'; 85 86 if (!Rows.empty()) { 87 OS << "Address Line Column File ISA Flags\n" 88 << "------------------ ------ ------ ------ --- -------------\n"; 89 for (std::vector<Row>::const_iterator pos = Rows.begin(), 90 end = Rows.end(); pos != end; ++pos) 91 pos->dump(OS); 92 } 93 } 94 95 DWARFDebugLine::State::~State() {} 96 97 void DWARFDebugLine::State::appendRowToMatrix(uint32_t offset) { 98 ++row; // Increase the row number. 99 LineTable::appendRow(*this); 100 Row::postAppend(); 101 } 102 103 DWARFDebugLine::DumpingState::~DumpingState() {} 104 105 void DWARFDebugLine::DumpingState::finalize(uint32_t offset) { 106 LineTable::dump(OS); 107 } 108 109 const DWARFDebugLine::LineTable * 110 DWARFDebugLine::getLineTable(uint32_t offset) const { 111 LineTableConstIter pos = LineTableMap.find(offset); 112 if (pos != LineTableMap.end()) 113 return &pos->second; 114 return 0; 115 } 116 117 const DWARFDebugLine::LineTable * 118 DWARFDebugLine::getOrParseLineTable(DataExtractor debug_line_data, 119 uint32_t offset) { 120 std::pair<LineTableIter, bool> pos = 121 LineTableMap.insert(LineTableMapTy::value_type(offset, LineTable())); 122 if (pos.second) { 123 // Parse and cache the line table for at this offset. 124 State state; 125 if (!parseStatementTable(debug_line_data, &offset, state)) 126 return 0; 127 pos.first->second = state; 128 } 129 return &pos.first->second; 130 } 131 132 bool 133 DWARFDebugLine::parsePrologue(DataExtractor debug_line_data, 134 uint32_t *offset_ptr, Prologue *prologue) { 135 const uint32_t prologue_offset = *offset_ptr; 136 137 prologue->clear(); 138 prologue->TotalLength = debug_line_data.getU32(offset_ptr); 139 prologue->Version = debug_line_data.getU16(offset_ptr); 140 if (prologue->Version != 2) 141 return false; 142 143 prologue->PrologueLength = debug_line_data.getU32(offset_ptr); 144 const uint32_t end_prologue_offset = prologue->PrologueLength + *offset_ptr; 145 prologue->MinInstLength = debug_line_data.getU8(offset_ptr); 146 prologue->DefaultIsStmt = debug_line_data.getU8(offset_ptr); 147 prologue->LineBase = debug_line_data.getU8(offset_ptr); 148 prologue->LineRange = debug_line_data.getU8(offset_ptr); 149 prologue->OpcodeBase = debug_line_data.getU8(offset_ptr); 150 151 prologue->StandardOpcodeLengths.reserve(prologue->OpcodeBase-1); 152 for (uint32_t i = 1; i < prologue->OpcodeBase; ++i) { 153 uint8_t op_len = debug_line_data.getU8(offset_ptr); 154 prologue->StandardOpcodeLengths.push_back(op_len); 155 } 156 157 while (*offset_ptr < end_prologue_offset) { 158 const char *s = debug_line_data.getCStr(offset_ptr); 159 if (s && s[0]) 160 prologue->IncludeDirectories.push_back(s); 161 else 162 break; 163 } 164 165 while (*offset_ptr < end_prologue_offset) { 166 const char *name = debug_line_data.getCStr(offset_ptr); 167 if (name && name[0]) { 168 FileNameEntry fileEntry; 169 fileEntry.Name = name; 170 fileEntry.DirIdx = debug_line_data.getULEB128(offset_ptr); 171 fileEntry.ModTime = debug_line_data.getULEB128(offset_ptr); 172 fileEntry.Length = debug_line_data.getULEB128(offset_ptr); 173 prologue->FileNames.push_back(fileEntry); 174 } else { 175 break; 176 } 177 } 178 179 if (*offset_ptr != end_prologue_offset) { 180 fprintf(stderr, "warning: parsing line table prologue at 0x%8.8x should" 181 " have ended at 0x%8.8x but it ended ad 0x%8.8x\n", 182 prologue_offset, end_prologue_offset, *offset_ptr); 183 } 184 return end_prologue_offset; 185 } 186 187 bool 188 DWARFDebugLine::parseStatementTable(DataExtractor debug_line_data, 189 uint32_t *offset_ptr, State &state) { 190 const uint32_t debug_line_offset = *offset_ptr; 191 192 Prologue *prologue = &state.Prologue; 193 194 if (!parsePrologue(debug_line_data, offset_ptr, prologue)) { 195 // Restore our offset and return false to indicate failure! 196 *offset_ptr = debug_line_offset; 197 return false; 198 } 199 200 const uint32_t end_offset = debug_line_offset + prologue->TotalLength + 201 sizeof(prologue->TotalLength); 202 203 state.reset(); 204 205 while (*offset_ptr < end_offset) { 206 uint8_t opcode = debug_line_data.getU8(offset_ptr); 207 208 if (opcode == 0) { 209 // Extended Opcodes always start with a zero opcode followed by 210 // a uleb128 length so you can skip ones you don't know about 211 uint32_t ext_offset = *offset_ptr; 212 uint64_t len = debug_line_data.getULEB128(offset_ptr); 213 uint32_t arg_size = len - (*offset_ptr - ext_offset); 214 215 uint8_t sub_opcode = debug_line_data.getU8(offset_ptr); 216 switch (sub_opcode) { 217 case DW_LNE_end_sequence: 218 // Set the end_sequence register of the state machine to true and 219 // append a row to the matrix using the current values of the 220 // state-machine registers. Then reset the registers to the initial 221 // values specified above. Every statement program sequence must end 222 // with a DW_LNE_end_sequence instruction which creates a row whose 223 // address is that of the byte after the last target machine instruction 224 // of the sequence. 225 state.EndSequence = true; 226 state.appendRowToMatrix(*offset_ptr); 227 state.reset(); 228 break; 229 230 case DW_LNE_set_address: 231 // Takes a single relocatable address as an operand. The size of the 232 // operand is the size appropriate to hold an address on the target 233 // machine. Set the address register to the value given by the 234 // relocatable address. All of the other statement program opcodes 235 // that affect the address register add a delta to it. This instruction 236 // stores a relocatable value into it instead. 237 state.Address = debug_line_data.getAddress(offset_ptr); 238 break; 239 240 case DW_LNE_define_file: 241 // Takes 4 arguments. The first is a null terminated string containing 242 // a source file name. The second is an unsigned LEB128 number 243 // representing the directory index of the directory in which the file 244 // was found. The third is an unsigned LEB128 number representing the 245 // time of last modification of the file. The fourth is an unsigned 246 // LEB128 number representing the length in bytes of the file. The time 247 // and length fields may contain LEB128(0) if the information is not 248 // available. 249 // 250 // The directory index represents an entry in the include_directories 251 // section of the statement program prologue. The index is LEB128(0) 252 // if the file was found in the current directory of the compilation, 253 // LEB128(1) if it was found in the first directory in the 254 // include_directories section, and so on. The directory index is 255 // ignored for file names that represent full path names. 256 // 257 // The files are numbered, starting at 1, in the order in which they 258 // appear; the names in the prologue come before names defined by 259 // the DW_LNE_define_file instruction. These numbers are used in the 260 // the file register of the state machine. 261 { 262 FileNameEntry fileEntry; 263 fileEntry.Name = debug_line_data.getCStr(offset_ptr); 264 fileEntry.DirIdx = debug_line_data.getULEB128(offset_ptr); 265 fileEntry.ModTime = debug_line_data.getULEB128(offset_ptr); 266 fileEntry.Length = debug_line_data.getULEB128(offset_ptr); 267 prologue->FileNames.push_back(fileEntry); 268 } 269 break; 270 271 default: 272 // Length doesn't include the zero opcode byte or the length itself, but 273 // it does include the sub_opcode, so we have to adjust for that below 274 (*offset_ptr) += arg_size; 275 break; 276 } 277 } else if (opcode < prologue->OpcodeBase) { 278 switch (opcode) { 279 // Standard Opcodes 280 case DW_LNS_copy: 281 // Takes no arguments. Append a row to the matrix using the 282 // current values of the state-machine registers. Then set 283 // the basic_block register to false. 284 state.appendRowToMatrix(*offset_ptr); 285 break; 286 287 case DW_LNS_advance_pc: 288 // Takes a single unsigned LEB128 operand, multiplies it by the 289 // min_inst_length field of the prologue, and adds the 290 // result to the address register of the state machine. 291 state.Address += debug_line_data.getULEB128(offset_ptr) * 292 prologue->MinInstLength; 293 break; 294 295 case DW_LNS_advance_line: 296 // Takes a single signed LEB128 operand and adds that value to 297 // the line register of the state machine. 298 state.Line += debug_line_data.getSLEB128(offset_ptr); 299 break; 300 301 case DW_LNS_set_file: 302 // Takes a single unsigned LEB128 operand and stores it in the file 303 // register of the state machine. 304 state.File = debug_line_data.getULEB128(offset_ptr); 305 break; 306 307 case DW_LNS_set_column: 308 // Takes a single unsigned LEB128 operand and stores it in the 309 // column register of the state machine. 310 state.Column = debug_line_data.getULEB128(offset_ptr); 311 break; 312 313 case DW_LNS_negate_stmt: 314 // Takes no arguments. Set the is_stmt register of the state 315 // machine to the logical negation of its current value. 316 state.IsStmt = !state.IsStmt; 317 break; 318 319 case DW_LNS_set_basic_block: 320 // Takes no arguments. Set the basic_block register of the 321 // state machine to true 322 state.BasicBlock = true; 323 break; 324 325 case DW_LNS_const_add_pc: 326 // Takes no arguments. Add to the address register of the state 327 // machine the address increment value corresponding to special 328 // opcode 255. The motivation for DW_LNS_const_add_pc is this: 329 // when the statement program needs to advance the address by a 330 // small amount, it can use a single special opcode, which occupies 331 // a single byte. When it needs to advance the address by up to 332 // twice the range of the last special opcode, it can use 333 // DW_LNS_const_add_pc followed by a special opcode, for a total 334 // of two bytes. Only if it needs to advance the address by more 335 // than twice that range will it need to use both DW_LNS_advance_pc 336 // and a special opcode, requiring three or more bytes. 337 { 338 uint8_t adjust_opcode = 255 - prologue->OpcodeBase; 339 uint64_t addr_offset = (adjust_opcode / prologue->LineRange) * 340 prologue->MinInstLength; 341 state.Address += addr_offset; 342 } 343 break; 344 345 case DW_LNS_fixed_advance_pc: 346 // Takes a single uhalf operand. Add to the address register of 347 // the state machine the value of the (unencoded) operand. This 348 // is the only extended opcode that takes an argument that is not 349 // a variable length number. The motivation for DW_LNS_fixed_advance_pc 350 // is this: existing assemblers cannot emit DW_LNS_advance_pc or 351 // special opcodes because they cannot encode LEB128 numbers or 352 // judge when the computation of a special opcode overflows and 353 // requires the use of DW_LNS_advance_pc. Such assemblers, however, 354 // can use DW_LNS_fixed_advance_pc instead, sacrificing compression. 355 state.Address += debug_line_data.getU16(offset_ptr); 356 break; 357 358 case DW_LNS_set_prologue_end: 359 // Takes no arguments. Set the prologue_end register of the 360 // state machine to true 361 state.PrologueEnd = true; 362 break; 363 364 case DW_LNS_set_epilogue_begin: 365 // Takes no arguments. Set the basic_block register of the 366 // state machine to true 367 state.EpilogueBegin = true; 368 break; 369 370 case DW_LNS_set_isa: 371 // Takes a single unsigned LEB128 operand and stores it in the 372 // column register of the state machine. 373 state.Isa = debug_line_data.getULEB128(offset_ptr); 374 break; 375 376 default: 377 // Handle any unknown standard opcodes here. We know the lengths 378 // of such opcodes because they are specified in the prologue 379 // as a multiple of LEB128 operands for each opcode. 380 { 381 assert(opcode - 1U < prologue->StandardOpcodeLengths.size()); 382 uint8_t opcode_length = prologue->StandardOpcodeLengths[opcode - 1]; 383 for (uint8_t i=0; i<opcode_length; ++i) 384 debug_line_data.getULEB128(offset_ptr); 385 } 386 break; 387 } 388 } else { 389 // Special Opcodes 390 391 // A special opcode value is chosen based on the amount that needs 392 // to be added to the line and address registers. The maximum line 393 // increment for a special opcode is the value of the line_base 394 // field in the header, plus the value of the line_range field, 395 // minus 1 (line base + line range - 1). If the desired line 396 // increment is greater than the maximum line increment, a standard 397 // opcode must be used instead of a special opcode. The "address 398 // advance" is calculated by dividing the desired address increment 399 // by the minimum_instruction_length field from the header. The 400 // special opcode is then calculated using the following formula: 401 // 402 // opcode = (desired line increment - line_base) + 403 // (line_range * address advance) + opcode_base 404 // 405 // If the resulting opcode is greater than 255, a standard opcode 406 // must be used instead. 407 // 408 // To decode a special opcode, subtract the opcode_base from the 409 // opcode itself to give the adjusted opcode. The amount to 410 // increment the address register is the result of the adjusted 411 // opcode divided by the line_range multiplied by the 412 // minimum_instruction_length field from the header. That is: 413 // 414 // address increment = (adjusted opcode / line_range) * 415 // minimum_instruction_length 416 // 417 // The amount to increment the line register is the line_base plus 418 // the result of the adjusted opcode modulo the line_range. That is: 419 // 420 // line increment = line_base + (adjusted opcode % line_range) 421 422 uint8_t adjust_opcode = opcode - prologue->OpcodeBase; 423 uint64_t addr_offset = (adjust_opcode / prologue->LineRange) * 424 prologue->MinInstLength; 425 int32_t line_offset = prologue->LineBase + 426 (adjust_opcode % prologue->LineRange); 427 state.Line += line_offset; 428 state.Address += addr_offset; 429 state.appendRowToMatrix(*offset_ptr); 430 } 431 } 432 433 state.finalize(*offset_ptr); 434 435 return end_offset; 436 } 437 438 static bool findMatchingAddress(const DWARFDebugLine::Row& row1, 439 const DWARFDebugLine::Row& row2) { 440 return row1.Address < row2.Address; 441 } 442 443 uint32_t 444 DWARFDebugLine::LineTable::lookupAddress(uint64_t address, 445 uint64_t cu_high_pc) const { 446 uint32_t index = UINT32_MAX; 447 if (!Rows.empty()) { 448 // Use the lower_bound algorithm to perform a binary search since we know 449 // that our line table data is ordered by address. 450 DWARFDebugLine::Row row; 451 row.Address = address; 452 typedef std::vector<Row>::const_iterator iterator; 453 iterator begin_pos = Rows.begin(); 454 iterator end_pos = Rows.end(); 455 iterator pos = std::lower_bound(begin_pos, end_pos, row, 456 findMatchingAddress); 457 if (pos == end_pos) { 458 if (address < cu_high_pc) 459 return Rows.size()-1; 460 } else { 461 // Rely on fact that we are using a std::vector and we can do 462 // pointer arithmetic to find the row index (which will be one less 463 // that what we found since it will find the first position after 464 // the current address) since std::vector iterators are just 465 // pointers to the container type. 466 index = pos - begin_pos; 467 if (pos->Address > address) { 468 if (index > 0) 469 --index; 470 else 471 index = UINT32_MAX; 472 } 473 } 474 } 475 return index; // Failed to find address. 476 } 477