1 //===- lib/CodeGen/DIE.h - DWARF Info Entries -------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Data structures for DWARF info entries. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DIE_H 14 #define LLVM_LIB_CODEGEN_ASMPRINTER_DIE_H 15 16 #include "llvm/ADT/FoldingSet.h" 17 #include "llvm/ADT/PointerIntPair.h" 18 #include "llvm/ADT/PointerUnion.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/StringRef.h" 21 #include "llvm/ADT/iterator.h" 22 #include "llvm/ADT/iterator_range.h" 23 #include "llvm/BinaryFormat/Dwarf.h" 24 #include "llvm/CodeGen/DwarfStringPoolEntry.h" 25 #include "llvm/Support/AlignOf.h" 26 #include "llvm/Support/Allocator.h" 27 #include <cassert> 28 #include <cstddef> 29 #include <cstdint> 30 #include <iterator> 31 #include <new> 32 #include <type_traits> 33 #include <utility> 34 #include <vector> 35 36 namespace llvm { 37 38 class AsmPrinter; 39 class DIE; 40 class DIEUnit; 41 class DwarfCompileUnit; 42 class MCExpr; 43 class MCSection; 44 class MCSymbol; 45 class raw_ostream; 46 47 //===--------------------------------------------------------------------===// 48 /// Dwarf abbreviation data, describes one attribute of a Dwarf abbreviation. 49 class DIEAbbrevData { 50 /// Dwarf attribute code. 51 dwarf::Attribute Attribute; 52 53 /// Dwarf form code. 54 dwarf::Form Form; 55 56 /// Dwarf attribute value for DW_FORM_implicit_const 57 int64_t Value = 0; 58 59 public: DIEAbbrevData(dwarf::Attribute A,dwarf::Form F)60 DIEAbbrevData(dwarf::Attribute A, dwarf::Form F) 61 : Attribute(A), Form(F) {} DIEAbbrevData(dwarf::Attribute A,int64_t V)62 DIEAbbrevData(dwarf::Attribute A, int64_t V) 63 : Attribute(A), Form(dwarf::DW_FORM_implicit_const), Value(V) {} 64 65 /// Accessors. 66 /// @{ getAttribute()67 dwarf::Attribute getAttribute() const { return Attribute; } getForm()68 dwarf::Form getForm() const { return Form; } getValue()69 int64_t getValue() const { return Value; } 70 /// @} 71 72 /// Used to gather unique data for the abbreviation folding set. 73 void Profile(FoldingSetNodeID &ID) const; 74 }; 75 76 //===--------------------------------------------------------------------===// 77 /// Dwarf abbreviation, describes the organization of a debug information 78 /// object. 79 class DIEAbbrev : public FoldingSetNode { 80 /// Unique number for node. 81 unsigned Number = 0; 82 83 /// Dwarf tag code. 84 dwarf::Tag Tag; 85 86 /// Whether or not this node has children. 87 /// 88 /// This cheats a bit in all of the uses since the values in the standard 89 /// are 0 and 1 for no children and children respectively. 90 bool Children; 91 92 /// Raw data bytes for abbreviation. 93 SmallVector<DIEAbbrevData, 12> Data; 94 95 public: DIEAbbrev(dwarf::Tag T,bool C)96 DIEAbbrev(dwarf::Tag T, bool C) : Tag(T), Children(C) {} 97 98 /// Accessors. 99 /// @{ getTag()100 dwarf::Tag getTag() const { return Tag; } getNumber()101 unsigned getNumber() const { return Number; } hasChildren()102 bool hasChildren() const { return Children; } getData()103 const SmallVectorImpl<DIEAbbrevData> &getData() const { return Data; } setChildrenFlag(bool hasChild)104 void setChildrenFlag(bool hasChild) { Children = hasChild; } setNumber(unsigned N)105 void setNumber(unsigned N) { Number = N; } 106 /// @} 107 108 /// Adds another set of attribute information to the abbreviation. AddAttribute(dwarf::Attribute Attribute,dwarf::Form Form)109 void AddAttribute(dwarf::Attribute Attribute, dwarf::Form Form) { 110 Data.push_back(DIEAbbrevData(Attribute, Form)); 111 } 112 113 /// Adds attribute with DW_FORM_implicit_const value AddImplicitConstAttribute(dwarf::Attribute Attribute,int64_t Value)114 void AddImplicitConstAttribute(dwarf::Attribute Attribute, int64_t Value) { 115 Data.push_back(DIEAbbrevData(Attribute, Value)); 116 } 117 118 /// Used to gather unique data for the abbreviation folding set. 119 void Profile(FoldingSetNodeID &ID) const; 120 121 /// Print the abbreviation using the specified asm printer. 122 void Emit(const AsmPrinter *AP) const; 123 124 void print(raw_ostream &O) const; 125 void dump() const; 126 }; 127 128 //===--------------------------------------------------------------------===// 129 /// Helps unique DIEAbbrev objects and assigns abbreviation numbers. 130 /// 131 /// This class will unique the DIE abbreviations for a llvm::DIE object and 132 /// assign a unique abbreviation number to each unique DIEAbbrev object it 133 /// finds. The resulting collection of DIEAbbrev objects can then be emitted 134 /// into the .debug_abbrev section. 135 class DIEAbbrevSet { 136 /// The bump allocator to use when creating DIEAbbrev objects in the uniqued 137 /// storage container. 138 BumpPtrAllocator &Alloc; 139 /// FoldingSet that uniques the abbreviations. 140 FoldingSet<DIEAbbrev> AbbreviationsSet; 141 /// A list of all the unique abbreviations in use. 142 std::vector<DIEAbbrev *> Abbreviations; 143 144 public: DIEAbbrevSet(BumpPtrAllocator & A)145 DIEAbbrevSet(BumpPtrAllocator &A) : Alloc(A) {} 146 ~DIEAbbrevSet(); 147 148 /// Generate the abbreviation declaration for a DIE and return a pointer to 149 /// the generated abbreviation. 150 /// 151 /// \param Die the debug info entry to generate the abbreviation for. 152 /// \returns A reference to the uniqued abbreviation declaration that is 153 /// owned by this class. 154 DIEAbbrev &uniqueAbbreviation(DIE &Die); 155 156 /// Print all abbreviations using the specified asm printer. 157 void Emit(const AsmPrinter *AP, MCSection *Section) const; 158 }; 159 160 //===--------------------------------------------------------------------===// 161 /// An integer value DIE. 162 /// 163 class DIEInteger { 164 uint64_t Integer; 165 166 public: DIEInteger(uint64_t I)167 explicit DIEInteger(uint64_t I) : Integer(I) {} 168 169 /// Choose the best form for integer. BestForm(bool IsSigned,uint64_t Int)170 static dwarf::Form BestForm(bool IsSigned, uint64_t Int) { 171 if (IsSigned) { 172 const int64_t SignedInt = Int; 173 if ((char)Int == SignedInt) 174 return dwarf::DW_FORM_data1; 175 if ((short)Int == SignedInt) 176 return dwarf::DW_FORM_data2; 177 if ((int)Int == SignedInt) 178 return dwarf::DW_FORM_data4; 179 } else { 180 if ((unsigned char)Int == Int) 181 return dwarf::DW_FORM_data1; 182 if ((unsigned short)Int == Int) 183 return dwarf::DW_FORM_data2; 184 if ((unsigned int)Int == Int) 185 return dwarf::DW_FORM_data4; 186 } 187 return dwarf::DW_FORM_data8; 188 } 189 getValue()190 uint64_t getValue() const { return Integer; } setValue(uint64_t Val)191 void setValue(uint64_t Val) { Integer = Val; } 192 193 void emitValue(const AsmPrinter *Asm, dwarf::Form Form) const; 194 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 195 196 void print(raw_ostream &O) const; 197 }; 198 199 //===--------------------------------------------------------------------===// 200 /// An expression DIE. 201 class DIEExpr { 202 const MCExpr *Expr; 203 204 public: DIEExpr(const MCExpr * E)205 explicit DIEExpr(const MCExpr *E) : Expr(E) {} 206 207 /// Get MCExpr. getValue()208 const MCExpr *getValue() const { return Expr; } 209 210 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 211 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 212 213 void print(raw_ostream &O) const; 214 }; 215 216 //===--------------------------------------------------------------------===// 217 /// A label DIE. 218 class DIELabel { 219 const MCSymbol *Label; 220 221 public: DIELabel(const MCSymbol * L)222 explicit DIELabel(const MCSymbol *L) : Label(L) {} 223 224 /// Get MCSymbol. getValue()225 const MCSymbol *getValue() const { return Label; } 226 227 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 228 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 229 230 void print(raw_ostream &O) const; 231 }; 232 233 //===--------------------------------------------------------------------===// 234 /// A BaseTypeRef DIE. 235 class DIEBaseTypeRef { 236 const DwarfCompileUnit *CU; 237 const uint64_t Index; 238 static constexpr unsigned ULEB128PadSize = 4; 239 240 public: DIEBaseTypeRef(const DwarfCompileUnit * TheCU,uint64_t Idx)241 explicit DIEBaseTypeRef(const DwarfCompileUnit *TheCU, uint64_t Idx) 242 : CU(TheCU), Index(Idx) {} 243 244 /// EmitValue - Emit base type reference. 245 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 246 /// SizeOf - Determine size of the base type reference in bytes. 247 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 248 249 void print(raw_ostream &O) const; getIndex()250 uint64_t getIndex() const { return Index; } 251 }; 252 253 //===--------------------------------------------------------------------===// 254 /// A simple label difference DIE. 255 /// 256 class DIEDelta { 257 const MCSymbol *LabelHi; 258 const MCSymbol *LabelLo; 259 260 public: DIEDelta(const MCSymbol * Hi,const MCSymbol * Lo)261 DIEDelta(const MCSymbol *Hi, const MCSymbol *Lo) : LabelHi(Hi), LabelLo(Lo) {} 262 263 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 264 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 265 266 void print(raw_ostream &O) const; 267 }; 268 269 //===--------------------------------------------------------------------===// 270 /// A container for string pool string values. 271 /// 272 /// This class is used with the DW_FORM_strp and DW_FORM_GNU_str_index forms. 273 class DIEString { 274 DwarfStringPoolEntryRef S; 275 276 public: DIEString(DwarfStringPoolEntryRef S)277 DIEString(DwarfStringPoolEntryRef S) : S(S) {} 278 279 /// Grab the string out of the object. getString()280 StringRef getString() const { return S.getString(); } 281 282 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 283 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 284 285 void print(raw_ostream &O) const; 286 }; 287 288 //===--------------------------------------------------------------------===// 289 /// A container for inline string values. 290 /// 291 /// This class is used with the DW_FORM_string form. 292 class DIEInlineString { 293 StringRef S; 294 295 public: 296 template <typename Allocator> DIEInlineString(StringRef Str,Allocator & A)297 explicit DIEInlineString(StringRef Str, Allocator &A) : S(Str.copy(A)) {} 298 299 ~DIEInlineString() = default; 300 301 /// Grab the string out of the object. getString()302 StringRef getString() const { return S; } 303 304 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 305 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 306 307 void print(raw_ostream &O) const; 308 }; 309 310 //===--------------------------------------------------------------------===// 311 /// A pointer to another debug information entry. An instance of this class can 312 /// also be used as a proxy for a debug information entry not yet defined 313 /// (ie. types.) 314 class DIEEntry { 315 DIE *Entry; 316 317 public: 318 DIEEntry() = delete; DIEEntry(DIE & E)319 explicit DIEEntry(DIE &E) : Entry(&E) {} 320 getEntry()321 DIE &getEntry() const { return *Entry; } 322 323 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 324 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 325 326 void print(raw_ostream &O) const; 327 }; 328 329 //===--------------------------------------------------------------------===// 330 /// Represents a pointer to a location list in the debug_loc 331 /// section. 332 class DIELocList { 333 /// Index into the .debug_loc vector. 334 size_t Index; 335 336 public: DIELocList(size_t I)337 DIELocList(size_t I) : Index(I) {} 338 339 /// Grab the current index out. getValue()340 size_t getValue() const { return Index; } 341 342 void emitValue(const AsmPrinter *AP, dwarf::Form Form) const; 343 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 344 345 void print(raw_ostream &O) const; 346 }; 347 348 //===--------------------------------------------------------------------===// 349 /// A debug information entry value. Some of these roughly correlate 350 /// to DWARF attribute classes. 351 class DIEBlock; 352 class DIELoc; 353 class DIEValue { 354 public: 355 enum Type { 356 isNone, 357 #define HANDLE_DIEVALUE(T) is##T, 358 #include "llvm/CodeGen/DIEValue.def" 359 }; 360 361 private: 362 /// Type of data stored in the value. 363 Type Ty = isNone; 364 dwarf::Attribute Attribute = (dwarf::Attribute)0; 365 dwarf::Form Form = (dwarf::Form)0; 366 367 /// Storage for the value. 368 /// 369 /// All values that aren't standard layout (or are larger than 8 bytes) 370 /// should be stored by reference instead of by value. 371 using ValTy = AlignedCharArrayUnion<DIEInteger, DIEString, DIEExpr, DIELabel, 372 DIEDelta *, DIEEntry, DIEBlock *, 373 DIELoc *, DIELocList, DIEBaseTypeRef *>; 374 375 static_assert(sizeof(ValTy) <= sizeof(uint64_t) || 376 sizeof(ValTy) <= sizeof(void *), 377 "Expected all large types to be stored via pointer"); 378 379 /// Underlying stored value. 380 ValTy Val; 381 construct(T V)382 template <class T> void construct(T V) { 383 static_assert(std::is_standard_layout<T>::value || 384 std::is_pointer<T>::value, 385 "Expected standard layout or pointer"); 386 new (reinterpret_cast<void *>(&Val)) T(V); 387 } 388 get()389 template <class T> T *get() { return reinterpret_cast<T *>(&Val); } get()390 template <class T> const T *get() const { 391 return reinterpret_cast<const T *>(&Val); 392 } destruct()393 template <class T> void destruct() { get<T>()->~T(); } 394 395 /// Destroy the underlying value. 396 /// 397 /// This should get optimized down to a no-op. We could skip it if we could 398 /// add a static assert on \a std::is_trivially_copyable(), but we currently 399 /// support versions of GCC that don't understand that. destroyVal()400 void destroyVal() { 401 switch (Ty) { 402 case isNone: 403 return; 404 #define HANDLE_DIEVALUE_SMALL(T) \ 405 case is##T: \ 406 destruct<DIE##T>(); \ 407 return; 408 #define HANDLE_DIEVALUE_LARGE(T) \ 409 case is##T: \ 410 destruct<const DIE##T *>(); \ 411 return; 412 #include "llvm/CodeGen/DIEValue.def" 413 } 414 } 415 416 /// Copy the underlying value. 417 /// 418 /// This should get optimized down to a simple copy. We need to actually 419 /// construct the value, rather than calling memcpy, to satisfy strict 420 /// aliasing rules. copyVal(const DIEValue & X)421 void copyVal(const DIEValue &X) { 422 switch (Ty) { 423 case isNone: 424 return; 425 #define HANDLE_DIEVALUE_SMALL(T) \ 426 case is##T: \ 427 construct<DIE##T>(*X.get<DIE##T>()); \ 428 return; 429 #define HANDLE_DIEVALUE_LARGE(T) \ 430 case is##T: \ 431 construct<const DIE##T *>(*X.get<const DIE##T *>()); \ 432 return; 433 #include "llvm/CodeGen/DIEValue.def" 434 } 435 } 436 437 public: 438 DIEValue() = default; 439 DIEValue(const DIEValue & X)440 DIEValue(const DIEValue &X) : Ty(X.Ty), Attribute(X.Attribute), Form(X.Form) { 441 copyVal(X); 442 } 443 444 DIEValue &operator=(const DIEValue &X) { 445 destroyVal(); 446 Ty = X.Ty; 447 Attribute = X.Attribute; 448 Form = X.Form; 449 copyVal(X); 450 return *this; 451 } 452 ~DIEValue()453 ~DIEValue() { destroyVal(); } 454 455 #define HANDLE_DIEVALUE_SMALL(T) \ 456 DIEValue(dwarf::Attribute Attribute, dwarf::Form Form, const DIE##T &V) \ 457 : Ty(is##T), Attribute(Attribute), Form(Form) { \ 458 construct<DIE##T>(V); \ 459 } 460 #define HANDLE_DIEVALUE_LARGE(T) \ 461 DIEValue(dwarf::Attribute Attribute, dwarf::Form Form, const DIE##T *V) \ 462 : Ty(is##T), Attribute(Attribute), Form(Form) { \ 463 assert(V && "Expected valid value"); \ 464 construct<const DIE##T *>(V); \ 465 } 466 #include "llvm/CodeGen/DIEValue.def" 467 468 /// Accessors. 469 /// @{ getType()470 Type getType() const { return Ty; } getAttribute()471 dwarf::Attribute getAttribute() const { return Attribute; } getForm()472 dwarf::Form getForm() const { return Form; } 473 explicit operator bool() const { return Ty; } 474 /// @} 475 476 #define HANDLE_DIEVALUE_SMALL(T) \ 477 const DIE##T &getDIE##T() const { \ 478 assert(getType() == is##T && "Expected " #T); \ 479 return *get<DIE##T>(); \ 480 } 481 #define HANDLE_DIEVALUE_LARGE(T) \ 482 const DIE##T &getDIE##T() const { \ 483 assert(getType() == is##T && "Expected " #T); \ 484 return **get<const DIE##T *>(); \ 485 } 486 #include "llvm/CodeGen/DIEValue.def" 487 488 /// Emit value via the Dwarf writer. 489 void emitValue(const AsmPrinter *AP) const; 490 491 /// Return the size of a value in bytes. 492 unsigned SizeOf(const AsmPrinter *AP) const; 493 494 void print(raw_ostream &O) const; 495 void dump() const; 496 }; 497 498 struct IntrusiveBackListNode { 499 PointerIntPair<IntrusiveBackListNode *, 1> Next; 500 IntrusiveBackListNodeIntrusiveBackListNode501 IntrusiveBackListNode() : Next(this, true) {} 502 getNextIntrusiveBackListNode503 IntrusiveBackListNode *getNext() const { 504 return Next.getInt() ? nullptr : Next.getPointer(); 505 } 506 }; 507 508 struct IntrusiveBackListBase { 509 using Node = IntrusiveBackListNode; 510 511 Node *Last = nullptr; 512 emptyIntrusiveBackListBase513 bool empty() const { return !Last; } 514 push_backIntrusiveBackListBase515 void push_back(Node &N) { 516 assert(N.Next.getPointer() == &N && "Expected unlinked node"); 517 assert(N.Next.getInt() == true && "Expected unlinked node"); 518 519 if (Last) { 520 N.Next = Last->Next; 521 Last->Next.setPointerAndInt(&N, false); 522 } 523 Last = &N; 524 } 525 push_frontIntrusiveBackListBase526 void push_front(Node &N) { 527 assert(N.Next.getPointer() == &N && "Expected unlinked node"); 528 assert(N.Next.getInt() == true && "Expected unlinked node"); 529 530 if (Last) { 531 N.Next.setPointerAndInt(Last->Next.getPointer(), false); 532 Last->Next.setPointerAndInt(&N, true); 533 } else { 534 Last = &N; 535 } 536 } 537 }; 538 539 template <class T> class IntrusiveBackList : IntrusiveBackListBase { 540 public: 541 using IntrusiveBackListBase::empty; 542 push_back(T & N)543 void push_back(T &N) { IntrusiveBackListBase::push_back(N); } push_front(T & N)544 void push_front(T &N) { IntrusiveBackListBase::push_front(N); } back()545 T &back() { return *static_cast<T *>(Last); } back()546 const T &back() const { return *static_cast<T *>(Last); } front()547 T &front() { 548 return *static_cast<T *>(Last ? Last->Next.getPointer() : nullptr); 549 } front()550 const T &front() const { 551 return *static_cast<T *>(Last ? Last->Next.getPointer() : nullptr); 552 } 553 takeNodes(IntrusiveBackList<T> & Other)554 void takeNodes(IntrusiveBackList<T> &Other) { 555 if (Other.empty()) 556 return; 557 558 T *FirstNode = static_cast<T *>(Other.Last->Next.getPointer()); 559 T *IterNode = FirstNode; 560 do { 561 // Keep a pointer to the node and increment the iterator. 562 T *TmpNode = IterNode; 563 IterNode = static_cast<T *>(IterNode->Next.getPointer()); 564 565 // Unlink the node and push it back to this list. 566 TmpNode->Next.setPointerAndInt(TmpNode, true); 567 push_back(*TmpNode); 568 } while (IterNode != FirstNode); 569 570 Other.Last = nullptr; 571 } 572 573 class const_iterator; 574 class iterator 575 : public iterator_facade_base<iterator, std::forward_iterator_tag, T> { 576 friend class const_iterator; 577 578 Node *N = nullptr; 579 580 public: 581 iterator() = default; iterator(T * N)582 explicit iterator(T *N) : N(N) {} 583 584 iterator &operator++() { 585 N = N->getNext(); 586 return *this; 587 } 588 589 explicit operator bool() const { return N; } 590 T &operator*() const { return *static_cast<T *>(N); } 591 592 bool operator==(const iterator &X) const { return N == X.N; } 593 }; 594 595 class const_iterator 596 : public iterator_facade_base<const_iterator, std::forward_iterator_tag, 597 const T> { 598 const Node *N = nullptr; 599 600 public: 601 const_iterator() = default; 602 // Placate MSVC by explicitly scoping 'iterator'. const_iterator(typename IntrusiveBackList<T>::iterator X)603 const_iterator(typename IntrusiveBackList<T>::iterator X) : N(X.N) {} const_iterator(const T * N)604 explicit const_iterator(const T *N) : N(N) {} 605 606 const_iterator &operator++() { 607 N = N->getNext(); 608 return *this; 609 } 610 611 explicit operator bool() const { return N; } 612 const T &operator*() const { return *static_cast<const T *>(N); } 613 614 bool operator==(const const_iterator &X) const { return N == X.N; } 615 }; 616 begin()617 iterator begin() { 618 return Last ? iterator(static_cast<T *>(Last->Next.getPointer())) : end(); 619 } begin()620 const_iterator begin() const { 621 return const_cast<IntrusiveBackList *>(this)->begin(); 622 } end()623 iterator end() { return iterator(); } end()624 const_iterator end() const { return const_iterator(); } 625 toIterator(T & N)626 static iterator toIterator(T &N) { return iterator(&N); } toIterator(const T & N)627 static const_iterator toIterator(const T &N) { return const_iterator(&N); } 628 }; 629 630 /// A list of DIE values. 631 /// 632 /// This is a singly-linked list, but instead of reversing the order of 633 /// insertion, we keep a pointer to the back of the list so we can push in 634 /// order. 635 /// 636 /// There are two main reasons to choose a linked list over a customized 637 /// vector-like data structure. 638 /// 639 /// 1. For teardown efficiency, we want DIEs to be BumpPtrAllocated. Using a 640 /// linked list here makes this way easier to accomplish. 641 /// 2. Carrying an extra pointer per \a DIEValue isn't expensive. 45% of DIEs 642 /// have 2 or fewer values, and 90% have 5 or fewer. A vector would be 643 /// over-allocated by 50% on average anyway, the same cost as the 644 /// linked-list node. 645 class DIEValueList { 646 struct Node : IntrusiveBackListNode { 647 DIEValue V; 648 NodeNode649 explicit Node(DIEValue V) : V(V) {} 650 }; 651 652 using ListTy = IntrusiveBackList<Node>; 653 654 ListTy List; 655 656 public: 657 class const_value_iterator; 658 class value_iterator 659 : public iterator_adaptor_base<value_iterator, ListTy::iterator, 660 std::forward_iterator_tag, DIEValue> { 661 friend class const_value_iterator; 662 663 using iterator_adaptor = 664 iterator_adaptor_base<value_iterator, ListTy::iterator, 665 std::forward_iterator_tag, DIEValue>; 666 667 public: 668 value_iterator() = default; value_iterator(ListTy::iterator X)669 explicit value_iterator(ListTy::iterator X) : iterator_adaptor(X) {} 670 671 explicit operator bool() const { return bool(wrapped()); } 672 DIEValue &operator*() const { return wrapped()->V; } 673 }; 674 675 class const_value_iterator : public iterator_adaptor_base< 676 const_value_iterator, ListTy::const_iterator, 677 std::forward_iterator_tag, const DIEValue> { 678 using iterator_adaptor = 679 iterator_adaptor_base<const_value_iterator, ListTy::const_iterator, 680 std::forward_iterator_tag, const DIEValue>; 681 682 public: 683 const_value_iterator() = default; const_value_iterator(DIEValueList::value_iterator X)684 const_value_iterator(DIEValueList::value_iterator X) 685 : iterator_adaptor(X.wrapped()) {} const_value_iterator(ListTy::const_iterator X)686 explicit const_value_iterator(ListTy::const_iterator X) 687 : iterator_adaptor(X) {} 688 689 explicit operator bool() const { return bool(wrapped()); } 690 const DIEValue &operator*() const { return wrapped()->V; } 691 }; 692 693 using value_range = iterator_range<value_iterator>; 694 using const_value_range = iterator_range<const_value_iterator>; 695 addValue(BumpPtrAllocator & Alloc,const DIEValue & V)696 value_iterator addValue(BumpPtrAllocator &Alloc, const DIEValue &V) { 697 List.push_back(*new (Alloc) Node(V)); 698 return value_iterator(ListTy::toIterator(List.back())); 699 } 700 template <class T> addValue(BumpPtrAllocator & Alloc,dwarf::Attribute Attribute,dwarf::Form Form,T && Value)701 value_iterator addValue(BumpPtrAllocator &Alloc, dwarf::Attribute Attribute, 702 dwarf::Form Form, T &&Value) { 703 return addValue(Alloc, DIEValue(Attribute, Form, std::forward<T>(Value))); 704 } 705 706 /// Take ownership of the nodes in \p Other, and append them to the back of 707 /// the list. takeValues(DIEValueList & Other)708 void takeValues(DIEValueList &Other) { List.takeNodes(Other.List); } 709 values()710 value_range values() { 711 return make_range(value_iterator(List.begin()), value_iterator(List.end())); 712 } values()713 const_value_range values() const { 714 return make_range(const_value_iterator(List.begin()), 715 const_value_iterator(List.end())); 716 } 717 }; 718 719 //===--------------------------------------------------------------------===// 720 /// A structured debug information entry. Has an abbreviation which 721 /// describes its organization. 722 class DIE : IntrusiveBackListNode, public DIEValueList { 723 friend class IntrusiveBackList<DIE>; 724 friend class DIEUnit; 725 726 /// Dwarf unit relative offset. 727 unsigned Offset = 0; 728 /// Size of instance + children. 729 unsigned Size = 0; 730 unsigned AbbrevNumber = ~0u; 731 /// Dwarf tag code. 732 dwarf::Tag Tag = (dwarf::Tag)0; 733 /// Set to true to force a DIE to emit an abbreviation that says it has 734 /// children even when it doesn't. This is used for unit testing purposes. 735 bool ForceChildren = false; 736 /// Children DIEs. 737 IntrusiveBackList<DIE> Children; 738 739 /// The owner is either the parent DIE for children of other DIEs, or a 740 /// DIEUnit which contains this DIE as its unit DIE. 741 PointerUnion<DIE *, DIEUnit *> Owner; 742 DIE(dwarf::Tag Tag)743 explicit DIE(dwarf::Tag Tag) : Tag(Tag) {} 744 745 public: 746 DIE() = delete; 747 DIE(const DIE &RHS) = delete; 748 DIE(DIE &&RHS) = delete; 749 DIE &operator=(const DIE &RHS) = delete; 750 DIE &operator=(const DIE &&RHS) = delete; 751 get(BumpPtrAllocator & Alloc,dwarf::Tag Tag)752 static DIE *get(BumpPtrAllocator &Alloc, dwarf::Tag Tag) { 753 return new (Alloc) DIE(Tag); 754 } 755 756 // Accessors. getAbbrevNumber()757 unsigned getAbbrevNumber() const { return AbbrevNumber; } getTag()758 dwarf::Tag getTag() const { return Tag; } 759 /// Get the compile/type unit relative offset of this DIE. getOffset()760 unsigned getOffset() const { return Offset; } getSize()761 unsigned getSize() const { return Size; } hasChildren()762 bool hasChildren() const { return ForceChildren || !Children.empty(); } setForceChildren(bool B)763 void setForceChildren(bool B) { ForceChildren = B; } 764 765 using child_iterator = IntrusiveBackList<DIE>::iterator; 766 using const_child_iterator = IntrusiveBackList<DIE>::const_iterator; 767 using child_range = iterator_range<child_iterator>; 768 using const_child_range = iterator_range<const_child_iterator>; 769 children()770 child_range children() { 771 return make_range(Children.begin(), Children.end()); 772 } children()773 const_child_range children() const { 774 return make_range(Children.begin(), Children.end()); 775 } 776 777 DIE *getParent() const; 778 779 /// Generate the abbreviation for this DIE. 780 /// 781 /// Calculate the abbreviation for this, which should be uniqued and 782 /// eventually used to call \a setAbbrevNumber(). 783 DIEAbbrev generateAbbrev() const; 784 785 /// Set the abbreviation number for this DIE. setAbbrevNumber(unsigned I)786 void setAbbrevNumber(unsigned I) { AbbrevNumber = I; } 787 788 /// Get the absolute offset within the .debug_info or .debug_types section 789 /// for this DIE. 790 uint64_t getDebugSectionOffset() const; 791 792 /// Compute the offset of this DIE and all its children. 793 /// 794 /// This function gets called just before we are going to generate the debug 795 /// information and gives each DIE a chance to figure out its CU relative DIE 796 /// offset, unique its abbreviation and fill in the abbreviation code, and 797 /// return the unit offset that points to where the next DIE will be emitted 798 /// within the debug unit section. After this function has been called for all 799 /// DIE objects, the DWARF can be generated since all DIEs will be able to 800 /// properly refer to other DIE objects since all DIEs have calculated their 801 /// offsets. 802 /// 803 /// \param AP AsmPrinter to use when calculating sizes. 804 /// \param AbbrevSet the abbreviation used to unique DIE abbreviations. 805 /// \param CUOffset the compile/type unit relative offset in bytes. 806 /// \returns the offset for the DIE that follows this DIE within the 807 /// current compile/type unit. 808 unsigned computeOffsetsAndAbbrevs(const AsmPrinter *AP, 809 DIEAbbrevSet &AbbrevSet, unsigned CUOffset); 810 811 /// Climb up the parent chain to get the compile unit or type unit DIE that 812 /// this DIE belongs to. 813 /// 814 /// \returns the compile or type unit DIE that owns this DIE, or NULL if 815 /// this DIE hasn't been added to a unit DIE. 816 const DIE *getUnitDie() const; 817 818 /// Climb up the parent chain to get the compile unit or type unit that this 819 /// DIE belongs to. 820 /// 821 /// \returns the DIEUnit that represents the compile or type unit that owns 822 /// this DIE, or NULL if this DIE hasn't been added to a unit DIE. 823 DIEUnit *getUnit() const; 824 setOffset(unsigned O)825 void setOffset(unsigned O) { Offset = O; } setSize(unsigned S)826 void setSize(unsigned S) { Size = S; } 827 828 /// Add a child to the DIE. addChild(DIE * Child)829 DIE &addChild(DIE *Child) { 830 assert(!Child->getParent() && "Child should be orphaned"); 831 Child->Owner = this; 832 Children.push_back(*Child); 833 return Children.back(); 834 } 835 addChildFront(DIE * Child)836 DIE &addChildFront(DIE *Child) { 837 assert(!Child->getParent() && "Child should be orphaned"); 838 Child->Owner = this; 839 Children.push_front(*Child); 840 return Children.front(); 841 } 842 843 /// Find a value in the DIE with the attribute given. 844 /// 845 /// Returns a default-constructed DIEValue (where \a DIEValue::getType() 846 /// gives \a DIEValue::isNone) if no such attribute exists. 847 DIEValue findAttribute(dwarf::Attribute Attribute) const; 848 849 void print(raw_ostream &O, unsigned IndentCount = 0) const; 850 void dump() const; 851 }; 852 853 //===--------------------------------------------------------------------===// 854 /// Represents a compile or type unit. 855 class DIEUnit { 856 /// The compile unit or type unit DIE. This variable must be an instance of 857 /// DIE so that we can calculate the DIEUnit from any DIE by traversing the 858 /// parent backchain and getting the Unit DIE, and then casting itself to a 859 /// DIEUnit. This allows us to be able to find the DIEUnit for any DIE without 860 /// having to store a pointer to the DIEUnit in each DIE instance. 861 DIE Die; 862 /// The section this unit will be emitted in. This may or may not be set to 863 /// a valid section depending on the client that is emitting DWARF. 864 MCSection *Section; 865 uint64_t Offset; /// .debug_info or .debug_types absolute section offset. 866 protected: 867 virtual ~DIEUnit() = default; 868 869 public: 870 explicit DIEUnit(dwarf::Tag UnitTag); 871 DIEUnit(const DIEUnit &RHS) = delete; 872 DIEUnit(DIEUnit &&RHS) = delete; 873 void operator=(const DIEUnit &RHS) = delete; 874 void operator=(const DIEUnit &&RHS) = delete; 875 /// Set the section that this DIEUnit will be emitted into. 876 /// 877 /// This function is used by some clients to set the section. Not all clients 878 /// that emit DWARF use this section variable. setSection(MCSection * Section)879 void setSection(MCSection *Section) { 880 assert(!this->Section); 881 this->Section = Section; 882 } 883 getCrossSectionRelativeBaseAddress()884 virtual const MCSymbol *getCrossSectionRelativeBaseAddress() const { 885 return nullptr; 886 } 887 888 /// Return the section that this DIEUnit will be emitted into. 889 /// 890 /// \returns Section pointer which can be NULL. getSection()891 MCSection *getSection() const { return Section; } setDebugSectionOffset(uint64_t O)892 void setDebugSectionOffset(uint64_t O) { Offset = O; } getDebugSectionOffset()893 uint64_t getDebugSectionOffset() const { return Offset; } getUnitDie()894 DIE &getUnitDie() { return Die; } getUnitDie()895 const DIE &getUnitDie() const { return Die; } 896 }; 897 898 struct BasicDIEUnit final : DIEUnit { BasicDIEUnitfinal899 explicit BasicDIEUnit(dwarf::Tag UnitTag) : DIEUnit(UnitTag) {} 900 }; 901 902 //===--------------------------------------------------------------------===// 903 /// DIELoc - Represents an expression location. 904 // 905 class DIELoc : public DIEValueList { 906 mutable unsigned Size = 0; // Size in bytes excluding size header. 907 908 public: 909 DIELoc() = default; 910 911 /// ComputeSize - Calculate the size of the location expression. 912 /// 913 unsigned ComputeSize(const AsmPrinter *AP) const; 914 915 // TODO: move setSize() and Size to DIEValueList. setSize(unsigned size)916 void setSize(unsigned size) { Size = size; } 917 918 /// BestForm - Choose the best form for data. 919 /// BestForm(unsigned DwarfVersion)920 dwarf::Form BestForm(unsigned DwarfVersion) const { 921 if (DwarfVersion > 3) 922 return dwarf::DW_FORM_exprloc; 923 // Pre-DWARF4 location expressions were blocks and not exprloc. 924 if ((unsigned char)Size == Size) 925 return dwarf::DW_FORM_block1; 926 if ((unsigned short)Size == Size) 927 return dwarf::DW_FORM_block2; 928 if ((unsigned int)Size == Size) 929 return dwarf::DW_FORM_block4; 930 return dwarf::DW_FORM_block; 931 } 932 933 void emitValue(const AsmPrinter *Asm, dwarf::Form Form) const; 934 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 935 936 void print(raw_ostream &O) const; 937 }; 938 939 //===--------------------------------------------------------------------===// 940 /// DIEBlock - Represents a block of values. 941 // 942 class DIEBlock : public DIEValueList { 943 mutable unsigned Size = 0; // Size in bytes excluding size header. 944 945 public: 946 DIEBlock() = default; 947 948 /// ComputeSize - Calculate the size of the location expression. 949 /// 950 unsigned ComputeSize(const AsmPrinter *AP) const; 951 952 // TODO: move setSize() and Size to DIEValueList. setSize(unsigned size)953 void setSize(unsigned size) { Size = size; } 954 955 /// BestForm - Choose the best form for data. 956 /// BestForm()957 dwarf::Form BestForm() const { 958 if ((unsigned char)Size == Size) 959 return dwarf::DW_FORM_block1; 960 if ((unsigned short)Size == Size) 961 return dwarf::DW_FORM_block2; 962 if ((unsigned int)Size == Size) 963 return dwarf::DW_FORM_block4; 964 return dwarf::DW_FORM_block; 965 } 966 967 void emitValue(const AsmPrinter *Asm, dwarf::Form Form) const; 968 unsigned SizeOf(const AsmPrinter *AP, dwarf::Form Form) const; 969 970 void print(raw_ostream &O) const; 971 }; 972 973 } // end namespace llvm 974 975 #endif // LLVM_LIB_CODEGEN_ASMPRINTER_DIE_H 976