contrib/llvm/tools/lld/include/lld/Core/Simple.h

   1 //===- lld/Core/Simple.h - Simple implementations of Atom and File --------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// \brief Provide simple implementations for Atoms and File.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLD_CORE_SIMPLE_H
  16 #define LLD_CORE_SIMPLE_H
  17
  18 #include "lld/Core/AbsoluteAtom.h"
  19 #include "lld/Core/Atom.h"
  20 #include "lld/Core/DefinedAtom.h"
  21 #include "lld/Core/File.h"
  22 #include "lld/Core/Reference.h"
  23 #include "lld/Core/SharedLibraryAtom.h"
  24 #include "lld/Core/UndefinedAtom.h"
  25 #include "llvm/ADT/SmallVector.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/ilist.h"
  28 #include "llvm/Support/Allocator.h"
  29 #include "llvm/Support/Casting.h"
  30 #include "llvm/Support/ErrorHandling.h"
  31 #include <algorithm>
  32 #include <cassert>
  33 #include <cstdint>
  34 #include <functional>
  35
  36 namespace lld {
  37
  38 class SimpleFile : public File {
  39 public:
  40   SimpleFile(StringRef path, File::Kind kind)
  41     : File(path, kind) {}
  42
  43   ~SimpleFile() override {
  44     _defined.clear();
  45     _undefined.clear();
  46     _shared.clear();
  47     _absolute.clear();
  48   }
  49
  50   void addAtom(DefinedAtom &a) {
  51     _defined.push_back(OwningAtomPtr<DefinedAtom>(&a));
  52   }
  53   void addAtom(UndefinedAtom &a) {
  54     _undefined.push_back(OwningAtomPtr<UndefinedAtom>(&a));
  55   }
  56   void addAtom(SharedLibraryAtom &a) {
  57     _shared.push_back(OwningAtomPtr<SharedLibraryAtom>(&a));
  58   }
  59   void addAtom(AbsoluteAtom &a) {
  60     _absolute.push_back(OwningAtomPtr<AbsoluteAtom>(&a));
  61   }
  62
  63   void addAtom(const Atom &atom) {
  64     if (auto *p = dyn_cast<DefinedAtom>(&atom)) {
  65       addAtom(const_cast<DefinedAtom &>(*p));
  66     } else if (auto *p = dyn_cast<UndefinedAtom>(&atom)) {
  67       addAtom(const_cast<UndefinedAtom &>(*p));
  68     } else if (auto *p = dyn_cast<SharedLibraryAtom>(&atom)) {
  69       addAtom(const_cast<SharedLibraryAtom &>(*p));
  70     } else if (auto *p = dyn_cast<AbsoluteAtom>(&atom)) {
  71       addAtom(const_cast<AbsoluteAtom &>(*p));
  72     } else {
  73       llvm_unreachable("atom has unknown definition kind");
  74     }
  75   }
  76
  77   void removeDefinedAtomsIf(std::function<bool(const DefinedAtom *)> pred) {
  78     auto &atoms = _defined;
  79     auto newEnd = std::remove_if(atoms.begin(), atoms.end(),
  80                                  [&pred](OwningAtomPtr<DefinedAtom> &p) {
  81                                    return pred(p.get());
  82                                  });
  83     atoms.erase(newEnd, atoms.end());
  84   }
  85
  86   const AtomRange<DefinedAtom> defined() const override { return _defined; }
  87
  88   const AtomRange<UndefinedAtom> undefined() const override {
  89     return _undefined;
  90   }
  91
  92   const AtomRange<SharedLibraryAtom> sharedLibrary() const override {
  93     return _shared;
  94   }
  95
  96   const AtomRange<AbsoluteAtom> absolute() const override {
  97     return _absolute;
  98   }
  99
 100   void clearAtoms() override {
 101     _defined.clear();
 102     _undefined.clear();
 103     _shared.clear();
 104     _absolute.clear();
 105   }
 106
 107 private:
 108   AtomVector<DefinedAtom> _defined;
 109   AtomVector<UndefinedAtom> _undefined;
 110   AtomVector<SharedLibraryAtom> _shared;
 111   AtomVector<AbsoluteAtom> _absolute;
 112 };
 113
 114 class SimpleReference : public Reference {
 115 public:
 116   SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch,
 117                   Reference::KindValue value, uint64_t off, const Atom *t,
 118                   Reference::Addend a)
 119       : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a),
 120         _next(nullptr), _prev(nullptr) {
 121   }
 122   SimpleReference()
 123       : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0),
 124         _target(nullptr), _offsetInAtom(0), _addend(0), _next(nullptr),
 125         _prev(nullptr) {
 126   }
 127
 128   uint64_t offsetInAtom() const override { return _offsetInAtom; }
 129
 130   const Atom *target() const override {
 131     assert(_target);
 132     return _target;
 133   }
 134
 135   Addend addend() const override { return _addend; }
 136   void setAddend(Addend a) override { _addend = a; }
 137   void setTarget(const Atom *newAtom) override { _target = newAtom; }
 138   SimpleReference *getNext() const { return _next; }
 139   SimpleReference *getPrev() const { return _prev; }
 140   void setNext(SimpleReference *n) { _next = n; }
 141   void setPrev(SimpleReference *p) { _prev = p; }
 142
 143 private:
 144   const Atom *_target;
 145   uint64_t _offsetInAtom;
 146   Addend _addend;
 147   SimpleReference *_next;
 148   SimpleReference *_prev;
 149 };
 150
 151 } // end namespace lld
 152
 153 // ilist will lazily create a sentinal (so end() can return a node past the
 154 // end of the list). We need this trait so that the sentinal is allocated
 155 // via the BumpPtrAllocator.
 156 namespace llvm {
 157
 158 template<>
 159 struct ilist_sentinel_traits<lld::SimpleReference> {
 160
 161   ilist_sentinel_traits() : _allocator(nullptr) { }
 162
 163   void setAllocator(llvm::BumpPtrAllocator *alloc) {
 164     _allocator = alloc;
 165   }
 166
 167   lld::SimpleReference *createSentinel() const {
 168     return new (*_allocator) lld::SimpleReference();
 169   }
 170
 171   static void destroySentinel(lld::SimpleReference*) {}
 172
 173   static lld::SimpleReference *provideInitialHead() { return nullptr; }
 174
 175   lld::SimpleReference *ensureHead(lld::SimpleReference *&head) const {
 176     if (!head) {
 177       head = createSentinel();
 178       noteHead(head, head);
 179       ilist_traits<lld::SimpleReference>::setNext(head, nullptr);
 180       return head;
 181     }
 182     return ilist_traits<lld::SimpleReference>::getPrev(head);
 183   }
 184
 185   void noteHead(lld::SimpleReference *newHead,
 186                 lld::SimpleReference *sentinel) const {
 187     ilist_traits<lld::SimpleReference>::setPrev(newHead, sentinel);
 188   }
 189
 190 private:
 191   mutable llvm::BumpPtrAllocator *_allocator;
 192 };
 193
 194 } // end namespace llvm
 195
 196 namespace lld {
 197
 198 class SimpleDefinedAtom : public DefinedAtom {
 199 public:
 200   explicit SimpleDefinedAtom(const File &f)
 201     : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {
 202     _references.setAllocator(&f.allocator());
 203   }
 204
 205   ~SimpleDefinedAtom() override {
 206     _references.clearAndLeakNodesUnsafely();
 207   }
 208
 209   const File &file() const override { return _file; }
 210
 211   StringRef name() const override { return StringRef(); }
 212
 213   uint64_t ordinal() const override { return _ordinal; }
 214
 215   Scope scope() const override { return DefinedAtom::scopeLinkageUnit; }
 216
 217   Interposable interposable() const override {
 218     return DefinedAtom::interposeNo;
 219   }
 220
 221   Merge merge() const override { return DefinedAtom::mergeNo; }
 222
 223   Alignment alignment() const override { return 1; }
 224
 225   SectionChoice sectionChoice() const override {
 226     return DefinedAtom::sectionBasedOnContent;
 227   }
 228
 229   StringRef customSectionName() const override { return StringRef(); }
 230   DeadStripKind deadStrip() const override {
 231     return DefinedAtom::deadStripNormal;
 232   }
 233
 234   DefinedAtom::reference_iterator begin() const override {
 235     const void *it = reinterpret_cast<const void *>(&*_references.begin());
 236     return reference_iterator(*this, it);
 237   }
 238
 239   DefinedAtom::reference_iterator end() const override {
 240     const void *it = reinterpret_cast<const void *>(&*_references.end());
 241     return reference_iterator(*this, it);
 242   }
 243
 244   const Reference *derefIterator(const void *it) const override {
 245     return reinterpret_cast<const Reference*>(it);
 246   }
 247
 248   void incrementIterator(const void *&it) const override {
 249     const SimpleReference* node = reinterpret_cast<const SimpleReference*>(it);
 250     const SimpleReference* next = node->getNext();
 251     it = reinterpret_cast<const void*>(next);
 252   }
 253
 254   void addReference(Reference::KindNamespace ns,
 255                     Reference::KindArch arch,
 256                     Reference::KindValue kindValue, uint64_t off,
 257                     const Atom *target, Reference::Addend a) override {
 258     assert(target && "trying to create reference to nothing");
 259     auto node = new (_file.allocator())
 260         SimpleReference(ns, arch, kindValue, off, target, a);
 261     _references.push_back(node);
 262   }
 263
 264   /// Sort references in a canonical order (by offset, then by kind).
 265   void sortReferences() const {
 266     // Cannot sort a linked  list, so move elements into a temporary vector,
 267     // sort the vector, then reconstruct the list.
 268     llvm::SmallVector<SimpleReference *, 16> elements;
 269     for (SimpleReference &node : _references) {
 270       elements.push_back(&node);
 271     }
 272     std::sort(elements.begin(), elements.end(),
 273         [] (const SimpleReference *lhs, const SimpleReference *rhs) -> bool {
 274           uint64_t lhsOffset = lhs->offsetInAtom();
 275           uint64_t rhsOffset = rhs->offsetInAtom();
 276           if (rhsOffset != lhsOffset)
 277             return (lhsOffset < rhsOffset);
 278           if (rhs->kindNamespace() != lhs->kindNamespace())
 279             return (lhs->kindNamespace() < rhs->kindNamespace());
 280           if (rhs->kindArch() != lhs->kindArch())
 281             return (lhs->kindArch() < rhs->kindArch());
 282           return (lhs->kindValue() < rhs->kindValue());
 283         });
 284     _references.clearAndLeakNodesUnsafely();
 285     for (SimpleReference *node : elements) {
 286       _references.push_back(node);
 287     }
 288   }
 289
 290   void setOrdinal(uint64_t ord) { _ordinal = ord; }
 291
 292 private:
 293   typedef llvm::ilist<SimpleReference> RefList;
 294
 295   const File &_file;
 296   uint64_t _ordinal;
 297   mutable RefList _references;
 298 };
 299
 300 class SimpleUndefinedAtom : public UndefinedAtom {
 301 public:
 302   SimpleUndefinedAtom(const File &f, StringRef name) : _file(f), _name(name) {
 303     assert(!name.empty() && "UndefinedAtoms must have a name");
 304   }
 305
 306   ~SimpleUndefinedAtom() override = default;
 307
 308   /// file - returns the File that produced/owns this Atom
 309   const File &file() const override { return _file; }
 310
 311   /// name - The name of the atom. For a function atom, it is the (mangled)
 312   /// name of the function.
 313   StringRef name() const override { return _name; }
 314
 315   CanBeNull canBeNull() const override { return UndefinedAtom::canBeNullNever; }
 316
 317 private:
 318   const File &_file;
 319   StringRef _name;
 320 };
 321
 322 } // end namespace lld
 323
 324 #endif // LLD_CORE_SIMPLE_H