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