[Bug 21683 relative] - Refactor of SimpleDefinedAtom::sortReferences()

[grimar]

Summary

I spent some time on investigating https://llvm.org/bugs/show_bug.cgi?id=21683
It looks already fixed in r223528 which switched SimpleDefinedAtom to allocate its SimpleReferences using the BumpPtrAllocator.

The only thing that does not look good for me is that SimpleDefinedAtom::sortReferences()
method uses temp SmallVector for copying into and sorting the ilist content and after that recreates the list again.
Since r247978 introduced ilist::sort I suggest the patch to use it.

Anyways I believe bug 21683 can be closed with this patch or without as fixed.

[ruiu]

Is the indentation correct?

[denis-protivensky]

Simple.h

188

Next time, please, provide the context.

This is a specialization of ilist_sentinel_traits template, and by changing the signature you made the default method play instead of this one. It may be a luck that sorting below worked for you, but it most likely hurt the correctness.

[grimar]

Fixed:
Indentations (sorry used tabs instead of spaces before)
No more possible leak of the sentinel if allocator was assigned after creation of it without allocator.

[grimar]

Simple.h

188

No, I dont think so. llvm::ilist inherits from ilist_sentinel_traits so we are free to declare destroySentinel static or not depending on our needs. That is widely used in another llvm code. I removed static modifier because we have non-static member variable here.

[lhames]

I would expect the cost of a linked-list sort to quickly exceed the cost of copying to/from the vector and sorting there. If that's the case this tidy-up may not be worth the performance hit?

Simple.h

private:
   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
+// ilist will lazily create a sentinel (so end() can return a node past the
+// end of the list). We need this trait so that the sentinel 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 {
+    // absence of allocator generally is not an issue. That might be useful for
+    // ilists of SimpleReferences created as temporatily local objects.
+    // They dont need to be allocated via BumpPtrAllocator
+    if (!_allocator) {
+      return new lld::SimpleReference();
     }
 
-  lld::SimpleReference *createSentinel() const {
     return new (*_allocator) lld::SimpleReference();
   }
 
-  static void destroySentinel(lld::SimpleReference*) {}
+  void destroySentinel(lld::SimpleReference *sentinel) {
+    // the same situation as described above in createSentinel()
+    // there is no BumpPtrAllocator allocator sometimes and its fine.
+    if (!_allocator) {
+      delete sentinel;
+    }
+  }
 
   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);
   }
 
+protected:
+  void setAllocator(llvm::BumpPtrAllocator *alloc) {
+    _allocator = alloc;
+  }
+
 private:
   mutable llvm::BumpPtrAllocator *_allocator;
 };
 }
 
 namespace lld {
 
+class SimpleReferencesList : public llvm::ilist<SimpleReference> {
+public:
+  SimpleReferencesList(llvm::BumpPtrAllocator *alloc) {
+    // SimpleReferencesList which is a part of SimpleDefinedAtom should
+    // always be created with BumpPtrAllocator
+    assert(alloc);
+    setAllocator(alloc);
+  }
+};
+
 class SimpleDefinedAtom : public DefinedAtom {
 public:
   explicit SimpleDefinedAtom(const File &f)
-    : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {
-    _references.setAllocator(&f.allocator());
+    : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()), _references(&f.allocator()) {
   }
 
   const File &file() const override { return _file; }
 
   StringRef name() const override { return StringRef(); }
 
   uint64_t ordinal() const override { return _ordinal; }
 
void addReference(Reference::KindNamespace ns, Reference::KindArch arch,
     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(),
-        [] (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);
-    }
+    _references.sort([](const SimpleReference &lhs, const SimpleReference &rhs) -> bool {
+      uint64_t lhsOffset = lhs.offsetInAtom();
+      uint64_t rhsOffset = rhs.offsetInAtom();
+      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());
   }
   void setOrdinal(uint64_t ord) { _ordinal = ord; }
 
 private:
-  typedef llvm::ilist<SimpleReference> RefList;
+  typedef SimpleReferencesList RefList;
 
   const File &_file;
   uint64_t _ordinal;
   mutable RefList _references;
 };
 
 class SimpleUndefinedAtom : public UndefinedAtom {
 public: