X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FDIE.h;h=2e6d4aa6d196891717e280dee1e0769a782202fd;hb=dd94739f022b97d4108b22260cc6408cfb9696e4;hp=7d98b4e14830898d54d8e5cc19fbe672d291f184;hpb=a0b5a74966533bd7df09fedd4e8726eaa118196d;p=oota-llvm.git diff --git a/include/llvm/CodeGen/DIE.h b/include/llvm/CodeGen/DIE.h index 7d98b4e1483..2e6d4aa6d19 100644 --- a/include/llvm/CodeGen/DIE.h +++ b/include/llvm/CodeGen/DIE.h @@ -15,6 +15,8 @@ #define LLVM_LIB_CODEGEN_ASMPRINTER_DIE_H #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/DwarfStringPoolEntry.h" #include "llvm/Support/Dwarf.h" @@ -448,11 +450,186 @@ public: #endif }; +struct IntrusiveBackListNode { + PointerIntPair Next; + IntrusiveBackListNode() : Next(this, true) {} + + IntrusiveBackListNode *getNext() const { + return Next.getInt() ? nullptr : Next.getPointer(); + } +}; + +struct IntrusiveBackListBase { + typedef IntrusiveBackListNode Node; + Node *Last = nullptr; + + bool empty() const { return !Last; } + void push_back(Node &N) { + assert(N.Next.getPointer() == &N && "Expected unlinked node"); + assert(N.Next.getInt() == true && "Expected unlinked node"); + + if (Last) { + N.Next = Last->Next; + Last->Next.setPointerAndInt(&N, false); + } + Last = &N; + } +}; + +template class IntrusiveBackList : IntrusiveBackListBase { +public: + using IntrusiveBackListBase::empty; + void push_back(T &N) { IntrusiveBackListBase::push_back(N); } + T &back() { return *static_cast(Last); } + const T &back() const { return *static_cast(Last); } + + class const_iterator; + class iterator + : public iterator_facade_base { + friend class const_iterator; + Node *N = nullptr; + + public: + iterator() = default; + explicit iterator(T *N) : N(N) {} + + iterator &operator++() { + N = N->getNext(); + return *this; + } + + explicit operator bool() const { return N; } + T &operator*() const { return *static_cast(N); } + + bool operator==(const iterator &X) const { return N == X.N; } + bool operator!=(const iterator &X) const { return N != X.N; } + }; + + class const_iterator + : public iterator_facade_base { + const Node *N = nullptr; + + public: + const_iterator() = default; + // Placate MSVC by explicitly scoping 'iterator'. + const_iterator(typename IntrusiveBackList::iterator X) : N(X.N) {} + explicit const_iterator(const T *N) : N(N) {} + + const_iterator &operator++() { + N = N->getNext(); + return *this; + } + + explicit operator bool() const { return N; } + const T &operator*() const { return *static_cast(N); } + + bool operator==(const const_iterator &X) const { return N == X.N; } + bool operator!=(const const_iterator &X) const { return N != X.N; } + }; + + iterator begin() { + return Last ? iterator(static_cast(Last->Next.getPointer())) : end(); + } + const_iterator begin() const { + return const_cast(this)->begin(); + } + iterator end() { return iterator(); } + const_iterator end() const { return const_iterator(); } + + static iterator toIterator(T &N) { return iterator(&N); } + static const_iterator toIterator(const T &N) { return const_iterator(&N); } +}; + +/// A list of DIE values. +/// +/// This is a singly-linked list, but instead of reversing the order of +/// insertion, we keep a pointer to the back of the list so we can push in +/// order. +/// +/// There are two main reasons to choose a linked list over a customized +/// vector-like data structure. +/// +/// 1. For teardown efficiency, we want DIEs to be BumpPtrAllocated. Using a +/// linked list here makes this way easier to accomplish. +/// 2. Carrying an extra pointer per \a DIEValue isn't expensive. 45% of DIEs +/// have 2 or fewer values, and 90% have 5 or fewer. A vector would be +/// over-allocated by 50% on average anyway, the same cost as the +/// linked-list node. +class DIEValueList { + struct Node : IntrusiveBackListNode { + DIEValue V; + explicit Node(DIEValue V) : V(V) {} + }; + + typedef IntrusiveBackList ListTy; + ListTy List; + +public: + class const_value_iterator; + class value_iterator + : public iterator_adaptor_base { + friend class const_value_iterator; + typedef iterator_adaptor_base iterator_adaptor; + + public: + value_iterator() = default; + explicit value_iterator(ListTy::iterator X) : iterator_adaptor(X) {} + + explicit operator bool() const { return bool(wrapped()); } + DIEValue &operator*() const { return wrapped()->V; } + }; + + class const_value_iterator : public iterator_adaptor_base< + const_value_iterator, ListTy::const_iterator, + std::forward_iterator_tag, const DIEValue> { + typedef iterator_adaptor_base iterator_adaptor; + + public: + const_value_iterator() = default; + const_value_iterator(DIEValueList::value_iterator X) + : iterator_adaptor(X.wrapped()) {} + explicit const_value_iterator(ListTy::const_iterator X) + : iterator_adaptor(X) {} + + explicit operator bool() const { return bool(wrapped()); } + const DIEValue &operator*() const { return wrapped()->V; } + }; + + typedef iterator_range value_range; + typedef iterator_range const_value_range; + + value_iterator addValue(BumpPtrAllocator &Alloc, DIEValue V) { + List.push_back(*new (Alloc) Node(V)); + return value_iterator(ListTy::toIterator(List.back())); + } + template + value_iterator addValue(BumpPtrAllocator &Alloc, dwarf::Attribute Attribute, + dwarf::Form Form, T &&Value) { + return addValue(Alloc, DIEValue(Attribute, Form, std::forward(Value))); + } + + value_range values() { + return llvm::make_range(value_iterator(List.begin()), + value_iterator(List.end())); + } + const_value_range values() const { + return llvm::make_range(const_value_iterator(List.begin()), + const_value_iterator(List.end())); + } +}; + //===--------------------------------------------------------------------===// /// DIE - A structured debug information entry. Has an abbreviation which /// describes its organization. -class DIE { -protected: +class DIE : IntrusiveBackListNode, public DIEValueList { + friend class IntrusiveBackList; + /// Offset - Offset in debug info section. /// unsigned Offset; @@ -468,27 +645,17 @@ protected: dwarf::Tag Tag = (dwarf::Tag)0; /// Children DIEs. - /// - // This can't be a vector because pointer validity is requirent for the - // Parent pointer and DIEEntry. - // It can't be a list because some clients need pointer validity before - // the object has been added to any child list - // (eg: DwarfUnit::constructVariableDIE). These aren't insurmountable, but may - // be more convoluted than beneficial. - std::vector> Children; - - DIE *Parent; + IntrusiveBackList Children; - /// Attribute values. - /// - SmallVector Values; + DIE *Parent = nullptr; -protected: - DIE() : Offset(0), Size(0), Parent(nullptr) {} + DIE() = delete; + explicit DIE(dwarf::Tag Tag) : Offset(0), Size(0), Tag(Tag) {} public: - explicit DIE(dwarf::Tag Tag) - : Offset(0), Size(0), Tag(Tag), Parent(nullptr) {} + static DIE *get(BumpPtrAllocator &Alloc, dwarf::Tag Tag) { + return new (Alloc) DIE(Tag); + } // Accessors. unsigned getAbbrevNumber() const { return AbbrevNumber; } @@ -497,26 +664,18 @@ public: unsigned getSize() const { return Size; } bool hasChildren() const { return !Children.empty(); } - typedef std::vector>::const_iterator child_iterator; + typedef IntrusiveBackList::iterator child_iterator; + typedef IntrusiveBackList::const_iterator const_child_iterator; typedef iterator_range child_range; + typedef iterator_range const_child_range; - child_range children() const { + child_range children() { return llvm::make_range(Children.begin(), Children.end()); } - - typedef SmallVectorImpl::const_iterator value_iterator; - typedef iterator_range value_range; - - value_iterator values_begin() const { return Values.begin(); } - value_iterator values_end() const { return Values.end(); } - value_range values() const { - return llvm::make_range(values_begin(), values_end()); + const_child_range children() const { + return llvm::make_range(Children.begin(), Children.end()); } - void setValue(unsigned I, DIEValue New) { - assert(I < Values.size()); - Values[I] = New; - } DIE *getParent() const { return Parent; } /// Generate the abbreviation for this DIE. @@ -537,21 +696,12 @@ public: void setOffset(unsigned O) { Offset = O; } void setSize(unsigned S) { Size = S; } - /// addValue - Add a value and attributes to a DIE. - /// - void addValue(DIEValue Value) { Values.push_back(Value); } - template - void addValue(dwarf::Attribute Attribute, dwarf::Form Form, T &&Value) { - Values.emplace_back(Attribute, Form, std::forward(Value)); - } - - /// addChild - Add a child to the DIE. - /// - DIE &addChild(std::unique_ptr Child) { - assert(!Child->getParent()); + /// Add a child to the DIE. + DIE &addChild(DIE *Child) { + assert(!Child->getParent() && "Child should be orphaned"); Child->Parent = this; - Children.push_back(std::move(Child)); - return *Children.back(); + Children.push_back(*Child); + return Children.back(); } /// Find a value in the DIE with the attribute given. @@ -569,7 +719,7 @@ public: //===--------------------------------------------------------------------===// /// DIELoc - Represents an expression location. // -class DIELoc : public DIE { +class DIELoc : public DIEValueList { mutable unsigned Size; // Size in bytes excluding size header. public: @@ -605,7 +755,7 @@ public: //===--------------------------------------------------------------------===// /// DIEBlock - Represents a block of values. // -class DIEBlock : public DIE { +class DIEBlock : public DIEValueList { mutable unsigned Size; // Size in bytes excluding size header. public: