LLD: Use std::vector to store SimpleReferences instead of linked list.

[ruiu]

Summary

Previously, SimpleReferences has two pointers to previous and next references,
making them elements of linked lists. I don't know how this design choice was
made, but it looks like we can just use plain std::vector instead of std::ilist.
Performance-wise this patch is neutral.

[Jean-Daniel]

SimpleReference was implemented using a vector not so long ago, but that design choice was made because std::vector is not bumpPtrAllocator friendly.
Mach-O implementation (at least) uses a bumpPtrAllocator to allocate the SimpleReferences. So SimpleReference destructor is never call, and so are members destructor.
If you use a std::vector, it means you will leak the vector storage memory. As all ilist nodes are allocated using the bumpPtr allocator, we don’t have that issue.

[ruiu]

Where is the code? Looks like SimpleReference is used only by PE/COFF port.

[yaron.keren]

This may mean we need teach SmallVector to accept allocator like other ADT.

[ruiu]

I think SmallVector guarantees the array it contains is contiguous in
memory. That data structure does not work well with BumpPtrAllocator
because garbage after extending the array is not reclaimed until the whole
buffer is discarded. That makes memory consumption of a small vector from
O(n) to O(n^2).

That being said, that behavior might be acceptable if we rarely extend
SmallVectors. So, maybe it's not a bad idea, but I don't know if it's good
enough to add an additional parameter to SmallVector's constructor.

include/lld/Core/Simple.h

 #ifndef LLD_CORE_SIMPLE_H
 #define LLD_CORE_SIMPLE_H
 
 #include "lld/Core/DefinedAtom.h"
 #include "lld/Core/File.h"
 #include "lld/Core/LinkingContext.h"
 #include "lld/Core/Reference.h"
 #include "lld/Core/UndefinedAtom.h"
-#include "llvm/ADT/ilist.h"
-#include "llvm/ADT/ilist_node.h"
 
 namespace lld {
 
 class SimpleFile : public MutableFile {
 public:
   SimpleFile(StringRef path) : MutableFile(path) {}
 
   void addAtom(const Atom &atom) override {
private:
   atom_collection_vector<UndefinedAtom>      _undefinedAtoms;
   atom_collection_vector<SharedLibraryAtom>  _sharedLibraryAtoms;
   atom_collection_vector<AbsoluteAtom>       _absoluteAtoms;
 };
 
 class SimpleReference : public Reference {
 public:
   SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch,
-                  Reference::KindValue value, uint64_t off, const Atom *t,
+                  Reference::KindValue val, uint64_t off, const Atom *t,
                   Reference::Addend a)
-      : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a),
-        _next(nullptr), _prev(nullptr) {
-  }
+      : Reference(ns, arch, val), _target(t), _offsetInAtom(off), _addend(a) {}
+
   SimpleReference()
       : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0),
-        _target(nullptr), _offsetInAtom(0), _addend(0), _next(nullptr),
-        _prev(nullptr) {
-  }
+        _target(nullptr), _offsetInAtom(0), _addend(0) {}
 
   uint64_t offsetInAtom() const override { return _offsetInAtom; }
 
   const Atom *target() const override {
     assert(_target);
     return _target;
   }
 
   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<lld::SimpleReference> {
-
-  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<lld::SimpleReference>::setNext(head, nullptr);
-      return head;
-    }
-    return ilist_traits<lld::SimpleReference>::getPrev(head);
-  }
-
-  void noteHead(lld::SimpleReference *newHead,
-                lld::SimpleReference *sentinel) const {
-    ilist_traits<lld::SimpleReference>::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; }
 
   StringRef name() const override { return StringRef(); }
 
   uint64_t ordinal() const override { return _ordinal; }
 
public:
   }
 
   StringRef customSectionName() const override { return StringRef(); }
   DeadStripKind deadStrip() const override {
     return DefinedAtom::deadStripNormal;
   }
 
   DefinedAtom::reference_iterator begin() const override {
-    const void *it = reinterpret_cast<const void *>(&*_references.begin());
+    const void *it = reinterpret_cast<void *>(0);
     return reference_iterator(*this, it);
   }
 
   DefinedAtom::reference_iterator end() const override {
-    const void *it = reinterpret_cast<const void *>(&*_references.end());
+    const void *it = reinterpret_cast<void *>(_references.size());
     return reference_iterator(*this, it);
   }
 
   const Reference *derefIterator(const void *it) const override {
-    return reinterpret_cast<const Reference*>(it);
+    return _references[reinterpret_cast<uintptr_t>(it)];
   }
 
   void incrementIterator(const void *&it) const override {
-    const SimpleReference* node = reinterpret_cast<const SimpleReference*>(it);
-    const SimpleReference* next = node->getNext();
-    it = reinterpret_cast<const void*>(next);
+    uintptr_t i = reinterpret_cast<uintptr_t>(it);
+    it = reinterpret_cast<const void*>(i + 1);
   }
 
   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");
     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 {
-    // Cannot sort a linked  list, so move elements into a temporary vector,
-    // sort the vector, then reconstruct the list.
-    llvm::SmallVector<SimpleReference *, 16> elements;
-    for (SimpleReference &node : _references) {
-      elements.push_back(&node);
-    }
-    std::sort(elements.begin(), elements.end(),
+    std::sort(_references.begin(), _references.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());
         });
-    _references.clearAndLeakNodesUnsafely();
-    for (SimpleReference *node : elements) {
-      _references.push_back(node);
-    }
   }
   void setOrdinal(uint64_t ord) { _ordinal = ord; }
 
 private:
-  typedef llvm::ilist<SimpleReference> RefList;
-
   const File &_file;
   uint64_t _ordinal;
-  mutable RefList _references;
+  mutable std::vector<SimpleReference *> _references;
 };
 
 class SimpleUndefinedAtom : public UndefinedAtom {
 public:
   SimpleUndefinedAtom(const File &f, StringRef name) : _file(f), _name(name) {
     assert(!name.empty() && "UndefinedAtoms must have a name");
   }