Home | History | Annotate | Download | only in Core 
      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/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
    272