From de9563d31b6cc8b0d72aa4d6933ddbb917adb1be Mon Sep 17 00:00:00 2001 From: Nick Kledzik Date: Fri, 5 Dec 2014 22:03:23 +0000 Subject: [PATCH] Add BumpPtrAllocator to lld::File. Switch SimpleDefinedAtom to allocate its SimpleRefernces using the BumpPtrAllocator. llvm-svn: 223528 --- lld/include/lld/Core/File.h | 6 +++ lld/include/lld/Core/Simple.h | 113 ++++++++++++++++++++++++++++++++++-------- 2 files changed, 97 insertions(+), 22 deletions(-) diff --git a/lld/include/lld/Core/File.h b/lld/include/lld/Core/File.h index 8ab4452..9fedd69 100644 --- a/lld/include/lld/Core/File.h +++ b/lld/include/lld/Core/File.h @@ -72,6 +72,11 @@ public: template class atom_iterator; // forward reference + /// For allocating any objects owned by this File. + llvm::BumpPtrAllocator &allocator() const { + return _allocator; + } + /// \brief For use interating over DefinedAtoms in this File. typedef atom_iterator defined_iterator; @@ -206,6 +211,7 @@ protected: static atom_collection_empty _noUndefinedAtoms; static atom_collection_empty _noSharedLibraryAtoms; static atom_collection_empty _noAbsoluteAtoms; + mutable llvm::BumpPtrAllocator _allocator; private: StringRef _path; diff --git a/lld/include/lld/Core/Simple.h b/lld/include/lld/Core/Simple.h index 1d901f8..905f462 100644 --- a/lld/include/lld/Core/Simple.h +++ b/lld/include/lld/Core/Simple.h @@ -15,6 +15,8 @@ #ifndef LLD_CORE_SIMPLE_H #define LLD_CORE_SIMPLE_H +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include "lld/Core/DefinedAtom.h" #include "lld/Core/File.h" #include "lld/Core/Reference.h" @@ -94,7 +96,13 @@ public: SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch, Reference::KindValue value, uint64_t off, const Atom *t, Reference::Addend a) - : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a) { + : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a), + _next(nullptr), _prev(nullptr) { + } + SimpleReference() + : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0), + _target(nullptr), _offsetInAtom(0), _addend(0), _next(nullptr), + _prev(nullptr) { } uint64_t offsetInAtom() const override { return _offsetInAtom; } @@ -107,18 +115,70 @@ public: Addend addend() const override { return _addend; } void setAddend(Addend a) override { _addend = a; } void setTarget(const Atom *newAtom) override { _target = newAtom; } + SimpleReference *getNext() const { return _next; } + SimpleReference *getPrev() const { return _prev; } + void setNext(SimpleReference *n) { _next = n; } + void setPrev(SimpleReference *p) { _prev = p; } private: const Atom *_target; uint64_t _offsetInAtom; Addend _addend; + SimpleReference *_next; + SimpleReference *_prev; }; +} + +// ilist will lazily create a sentinal (so end() can return a node past the +// end of the list). We need this trait so that the sentinal is allocated +// via the BumpPtrAllocator. +namespace llvm { +template<> +struct ilist_sentinel_traits { + + ilist_sentinel_traits() : _allocator(nullptr) { } + + void setAllocator(llvm::BumpPtrAllocator *alloc) { + _allocator = alloc; + } + + lld::SimpleReference *createSentinel() const { + return new (*_allocator) lld::SimpleReference(); + } + + static void destroySentinel(lld::SimpleReference*) {} + + static lld::SimpleReference *provideInitialHead() { return nullptr; } + + lld::SimpleReference *ensureHead(lld::SimpleReference *&head) const { + if (!head) { + head = createSentinel(); + noteHead(head, head); + ilist_traits::setNext(head, nullptr); + return head; + } + return ilist_traits::getPrev(head); + } + + void noteHead(lld::SimpleReference *newHead, + lld::SimpleReference *sentinel) const { + ilist_traits::setPrev(newHead, sentinel); + } + +private: + mutable llvm::BumpPtrAllocator *_allocator; +}; +} + +namespace lld { + class SimpleDefinedAtom : public DefinedAtom { public: explicit SimpleDefinedAtom(const File &f) : _file(f) { static uint32_t lastOrdinal = 0; _ordinal = lastOrdinal++; + _references.setAllocator(&f.allocator()); } const File &file() const override { return _file; } @@ -149,57 +209,66 @@ public: } DefinedAtom::reference_iterator begin() const override { - uintptr_t index = 0; - const void *it = reinterpret_cast(index); + const void *it = reinterpret_cast(&*_references.begin()); return reference_iterator(*this, it); } DefinedAtom::reference_iterator end() const override { - uintptr_t index = _references.size(); - const void *it = reinterpret_cast(index); + const void *it = reinterpret_cast(&*_references.end()); return reference_iterator(*this, it); } const Reference *derefIterator(const void *it) const override { - uintptr_t index = reinterpret_cast(it); - assert(index < _references.size()); - return &_references[index]; + return reinterpret_cast(it); } void incrementIterator(const void *&it) const override { - uintptr_t index = reinterpret_cast(it); - ++index; - it = reinterpret_cast(index); + const SimpleReference* node = reinterpret_cast(it); + const SimpleReference* next = node->getNext(); + it = reinterpret_cast(next); } void addReference(Reference::KindNamespace ns, Reference::KindArch arch, Reference::KindValue kindValue, uint64_t off, const Atom *target, Reference::Addend a) { assert(target && "trying to create reference to nothing"); - _references.push_back(SimpleReference(ns, arch, kindValue, off, target, a)); + auto node = new (_file.allocator()) SimpleReference(ns, arch, kindValue, off, target, a); + _references.push_back(node); } /// Sort references in a canonical order (by offset, then by kind). void sortReferences() const { - std::sort(_references.begin(), _references.end(), - [] (const SimpleReference &lhs, const SimpleReference &rhs) -> bool { - uint64_t lhsOffset = lhs.offsetInAtom(); - uint64_t rhsOffset = rhs.offsetInAtom(); + // Cannot sort a linked list, so move elements into a temporary vector, + // sort the vector, then reconstruct the list. + llvm::SmallVector elements; + for (SimpleReference &node : _references) { + elements.push_back(&node); + } + std::sort(elements.begin(), elements.end(), + [] (const SimpleReference *lhs, const SimpleReference *rhs) -> bool { + uint64_t lhsOffset = lhs->offsetInAtom(); + uint64_t rhsOffset = rhs->offsetInAtom(); if (rhsOffset != lhsOffset) return (lhsOffset < rhsOffset); - if (rhs.kindNamespace() != lhs.kindNamespace()) - return (lhs.kindNamespace() < rhs.kindNamespace()); - if (rhs.kindArch() != lhs.kindArch()) - return (lhs.kindArch() < rhs.kindArch()); - return (lhs.kindValue() < rhs.kindValue()); + if (rhs->kindNamespace() != lhs->kindNamespace()) + return (lhs->kindNamespace() < rhs->kindNamespace()); + if (rhs->kindArch() != lhs->kindArch()) + return (lhs->kindArch() < rhs->kindArch()); + return (lhs->kindValue() < rhs->kindValue()); }); + _references.clearAndLeakNodesUnsafely(); + for (SimpleReference *node : elements) { + _references.push_back(node); + } } void setOrdinal(uint64_t ord) { _ordinal = ord; } private: + typedef llvm::ilist RefList; + const File &_file; uint64_t _ordinal; - mutable std::vector _references; + mutable RefList _references; }; class SimpleUndefinedAtom : public UndefinedAtom { -- 2.7.4