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 /// 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/ADT/ilist_node.h"
  29 #include "llvm/Support/Allocator.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include <algorithm>
  33 #include <cassert>
  34 #include <cstdint>
  35 #include <functional>
  36
  37 namespace lld {
  38
  39 class SimpleFile : public File {
  40 public:
  41   SimpleFile(StringRef path, File::Kind kind)
  42     : File(path, kind) {}
  43
  44   ~SimpleFile() override {
  45     _defined.clear();
  46     _undefined.clear();
  47     _shared.clear();
  48     _absolute.clear();
  49   }
  50
  51   void addAtom(DefinedAtom &a) {
  52     _defined.push_back(OwningAtomPtr<DefinedAtom>(&a));
  53   }
  54   void addAtom(UndefinedAtom &a) {
  55     _undefined.push_back(OwningAtomPtr<UndefinedAtom>(&a));
  56   }
  57   void addAtom(SharedLibraryAtom &a) {
  58     _shared.push_back(OwningAtomPtr<SharedLibraryAtom>(&a));
  59   }
  60   void addAtom(AbsoluteAtom &a) {
  61     _absolute.push_back(OwningAtomPtr<AbsoluteAtom>(&a));
  62   }
  63
  64   void addAtom(const Atom &atom) {
  65     if (auto *p = dyn_cast<DefinedAtom>(&atom)) {
  66       addAtom(const_cast<DefinedAtom &>(*p));
  67     } else if (auto *p = dyn_cast<UndefinedAtom>(&atom)) {
  68       addAtom(const_cast<UndefinedAtom &>(*p));
  69     } else if (auto *p = dyn_cast<SharedLibraryAtom>(&atom)) {
  70       addAtom(const_cast<SharedLibraryAtom &>(*p));
  71     } else if (auto *p = dyn_cast<AbsoluteAtom>(&atom)) {
  72       addAtom(const_cast<AbsoluteAtom &>(*p));
  73     } else {
  74       llvm_unreachable("atom has unknown definition kind");
  75     }
  76   }
  77
  78   void removeDefinedAtomsIf(std::function<bool(const DefinedAtom *)> pred) {
  79     auto &atoms = _defined;
  80     auto newEnd = std::remove_if(atoms.begin(), atoms.end(),
  81                                  [&pred](OwningAtomPtr<DefinedAtom> &p) {
  82                                    return pred(p.get());
  83                                  });
  84     atoms.erase(newEnd, atoms.end());
  85   }
  86
  87   const AtomRange<DefinedAtom> defined() const override { return _defined; }
  88
  89   const AtomRange<UndefinedAtom> undefined() const override {
  90     return _undefined;
  91   }
  92
  93   const AtomRange<SharedLibraryAtom> sharedLibrary() const override {
  94     return _shared;
  95   }
  96
  97   const AtomRange<AbsoluteAtom> absolute() const override {
  98     return _absolute;
  99   }
 100
 101   void clearAtoms() override {
 102     _defined.clear();
 103     _undefined.clear();
 104     _shared.clear();
 105     _absolute.clear();
 106   }
 107
 108 private:
 109   AtomVector<DefinedAtom> _defined;
 110   AtomVector<UndefinedAtom> _undefined;
 111   AtomVector<SharedLibraryAtom> _shared;
 112   AtomVector<AbsoluteAtom> _absolute;
 113 };
 114
 115 class SimpleReference : public Reference,
 116                         public llvm::ilist_node<SimpleReference> {
 117 public:
 118   SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch,
 119                   Reference::KindValue value, uint64_t off, const Atom *t,
 120                   Reference::Addend a)
 121       : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a) {
 122   }
 123   SimpleReference()
 124       : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0),
 125         _target(nullptr), _offsetInAtom(0), _addend(0) {}
 126
 127   uint64_t offsetInAtom() const override { return _offsetInAtom; }
 128
 129   const Atom *target() const override {
 130     assert(_target);
 131     return _target;
 132   }
 133
 134   Addend addend() const override { return _addend; }
 135   void setAddend(Addend a) override { _addend = a; }
 136   void setTarget(const Atom *newAtom) override { _target = newAtom; }
 137
 138 private:
 139   const Atom *_target;
 140   uint64_t _offsetInAtom;
 141   Addend _addend;
 142 };
 143
 144 class SimpleDefinedAtom : public DefinedAtom {
 145 public:
 146   explicit SimpleDefinedAtom(const File &f)
 147       : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {}
 148
 149   ~SimpleDefinedAtom() override {
 150     _references.clearAndLeakNodesUnsafely();
 151   }
 152
 153   const File &file() const override { return _file; }
 154
 155   StringRef name() const override { return StringRef(); }
 156
 157   uint64_t ordinal() const override { return _ordinal; }
 158
 159   Scope scope() const override { return DefinedAtom::scopeLinkageUnit; }
 160
 161   Interposable interposable() const override {
 162     return DefinedAtom::interposeNo;
 163   }
 164
 165   Merge merge() const override { return DefinedAtom::mergeNo; }
 166
 167   Alignment alignment() const override { return 1; }
 168
 169   SectionChoice sectionChoice() const override {
 170     return DefinedAtom::sectionBasedOnContent;
 171   }
 172
 173   StringRef customSectionName() const override { return StringRef(); }
 174   DeadStripKind deadStrip() const override {
 175     return DefinedAtom::deadStripNormal;
 176   }
 177
 178   DefinedAtom::reference_iterator begin() const override {
 179     const void *it =
 180         reinterpret_cast<const void *>(_references.begin().getNodePtr());
 181     return reference_iterator(*this, it);
 182   }
 183
 184   DefinedAtom::reference_iterator end() const override {
 185     const void *it =
 186         reinterpret_cast<const void *>(_references.end().getNodePtr());
 187     return reference_iterator(*this, it);
 188   }
 189
 190   const Reference *derefIterator(const void *it) const override {
 191     return &*RefList::const_iterator(
 192         *reinterpret_cast<const llvm::ilist_node<SimpleReference> *>(it));
 193   }
 194
 195   void incrementIterator(const void *&it) const override {
 196     RefList::const_iterator ref(
 197         *reinterpret_cast<const llvm::ilist_node<SimpleReference> *>(it));
 198     it = reinterpret_cast<const void *>(std::next(ref).getNodePtr());
 199   }
 200
 201   void addReference(Reference::KindNamespace ns,
 202                     Reference::KindArch arch,
 203                     Reference::KindValue kindValue, uint64_t off,
 204                     const Atom *target, Reference::Addend a) override {
 205     assert(target && "trying to create reference to nothing");
 206     auto node = new (_file.allocator())
 207         SimpleReference(ns, arch, kindValue, off, target, a);
 208     _references.push_back(node);
 209   }
 210
 211   /// Sort references in a canonical order (by offset, then by kind).
 212   void sortReferences() const {
 213     // Cannot sort a linked  list, so move elements into a temporary vector,
 214     // sort the vector, then reconstruct the list.
 215     llvm::SmallVector<SimpleReference *, 16> elements;
 216     for (SimpleReference &node : _references) {
 217       elements.push_back(&node);
 218     }
 219     std::sort(elements.begin(), elements.end(),
 220         [] (const SimpleReference *lhs, const SimpleReference *rhs) -> bool {
 221           uint64_t lhsOffset = lhs->offsetInAtom();
 222           uint64_t rhsOffset = rhs->offsetInAtom();
 223           if (rhsOffset != lhsOffset)
 224             return (lhsOffset < rhsOffset);
 225           if (rhs->kindNamespace() != lhs->kindNamespace())
 226             return (lhs->kindNamespace() < rhs->kindNamespace());
 227           if (rhs->kindArch() != lhs->kindArch())
 228             return (lhs->kindArch() < rhs->kindArch());
 229           return (lhs->kindValue() < rhs->kindValue());
 230         });
 231     _references.clearAndLeakNodesUnsafely();
 232     for (SimpleReference *node : elements) {
 233       _references.push_back(node);
 234     }
 235   }
 236
 237   void setOrdinal(uint64_t ord) { _ordinal = ord; }
 238
 239 private:
 240   typedef llvm::ilist<SimpleReference> RefList;
 241
 242   const File &_file;
 243   uint64_t _ordinal;
 244   mutable RefList _references;
 245 };
 246
 247 class SimpleUndefinedAtom : public UndefinedAtom {
 248 public:
 249   SimpleUndefinedAtom(const File &f, StringRef name) : _file(f), _name(name) {
 250     assert(!name.empty() && "UndefinedAtoms must have a name");
 251   }
 252
 253   ~SimpleUndefinedAtom() override = default;
 254
 255   /// file - returns the File that produced/owns this Atom
 256   const File &file() const override { return _file; }
 257
 258   /// name - The name of the atom. For a function atom, it is the (mangled)
 259   /// name of the function.
 260   StringRef name() const override { return _name; }
 261
 262   CanBeNull canBeNull() const override { return UndefinedAtom::canBeNullNever; }
 263
 264 private:
 265   const File &_file;
 266   StringRef _name;
 267 };
 268
 269 } // end namespace lld
 270
 271 #endif // LLD_CORE_SIMPLE_H