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: SimpleFile(StringRef path,File::Kind kind)41 SimpleFile(StringRef path, File::Kind kind) 42 : File(path, kind) {} 43 ~SimpleFile()44 ~SimpleFile() override { 45 _defined.clear(); 46 _undefined.clear(); 47 _shared.clear(); 48 _absolute.clear(); 49 } 50 addAtom(DefinedAtom & a)51 void addAtom(DefinedAtom &a) { 52 _defined.push_back(OwningAtomPtr<DefinedAtom>(&a)); 53 } addAtom(UndefinedAtom & a)54 void addAtom(UndefinedAtom &a) { 55 _undefined.push_back(OwningAtomPtr<UndefinedAtom>(&a)); 56 } addAtom(SharedLibraryAtom & a)57 void addAtom(SharedLibraryAtom &a) { 58 _shared.push_back(OwningAtomPtr<SharedLibraryAtom>(&a)); 59 } addAtom(AbsoluteAtom & a)60 void addAtom(AbsoluteAtom &a) { 61 _absolute.push_back(OwningAtomPtr<AbsoluteAtom>(&a)); 62 } 63 addAtom(const Atom & atom)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 removeDefinedAtomsIf(std::function<bool (const DefinedAtom *)> pred)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 defined()87 const AtomRange<DefinedAtom> defined() const override { return _defined; } 88 undefined()89 const AtomRange<UndefinedAtom> undefined() const override { 90 return _undefined; 91 } 92 sharedLibrary()93 const AtomRange<SharedLibraryAtom> sharedLibrary() const override { 94 return _shared; 95 } 96 absolute()97 const AtomRange<AbsoluteAtom> absolute() const override { 98 return _absolute; 99 } 100 clearAtoms()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: SimpleReference(Reference::KindNamespace ns,Reference::KindArch arch,Reference::KindValue value,uint64_t off,const Atom * t,Reference::Addend a)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 } SimpleReference()123 SimpleReference() 124 : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0), 125 _target(nullptr), _offsetInAtom(0), _addend(0) {} 126 offsetInAtom()127 uint64_t offsetInAtom() const override { return _offsetInAtom; } 128 target()129 const Atom *target() const override { 130 assert(_target); 131 return _target; 132 } 133 addend()134 Addend addend() const override { return _addend; } setAddend(Addend a)135 void setAddend(Addend a) override { _addend = a; } setTarget(const Atom * newAtom)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: SimpleDefinedAtom(const File & f)146 explicit SimpleDefinedAtom(const File &f) 147 : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {} 148 ~SimpleDefinedAtom()149 ~SimpleDefinedAtom() override { 150 _references.clearAndLeakNodesUnsafely(); 151 } 152 file()153 const File &file() const override { return _file; } 154 name()155 StringRef name() const override { return StringRef(); } 156 ordinal()157 uint64_t ordinal() const override { return _ordinal; } 158 scope()159 Scope scope() const override { return DefinedAtom::scopeLinkageUnit; } 160 interposable()161 Interposable interposable() const override { 162 return DefinedAtom::interposeNo; 163 } 164 merge()165 Merge merge() const override { return DefinedAtom::mergeNo; } 166 alignment()167 Alignment alignment() const override { return 1; } 168 sectionChoice()169 SectionChoice sectionChoice() const override { 170 return DefinedAtom::sectionBasedOnContent; 171 } 172 customSectionName()173 StringRef customSectionName() const override { return StringRef(); } deadStrip()174 DeadStripKind deadStrip() const override { 175 return DefinedAtom::deadStripNormal; 176 } 177 begin()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 end()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 derefIterator(const void * it)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 incrementIterator(const void * & it)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 addReference(Reference::KindNamespace ns,Reference::KindArch arch,Reference::KindValue kindValue,uint64_t off,const Atom * target,Reference::Addend a)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). sortReferences()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 setOrdinal(uint64_t ord)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: SimpleUndefinedAtom(const File & f,StringRef name)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 file()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. name()260 StringRef name() const override { return _name; } 261 canBeNull()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