1 //===- lld/Core/Simple.h - Simple implementations of Atom and File --------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// Provide simple implementations for Atoms and File. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLD_CORE_SIMPLE_H 15 #define LLD_CORE_SIMPLE_H 16 17 #include "lld/Core/AbsoluteAtom.h" 18 #include "lld/Core/Atom.h" 19 #include "lld/Core/DefinedAtom.h" 20 #include "lld/Core/File.h" 21 #include "lld/Core/Reference.h" 22 #include "lld/Core/SharedLibraryAtom.h" 23 #include "lld/Core/UndefinedAtom.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include "llvm/ADT/StringRef.h" 26 #include "llvm/ADT/ilist.h" 27 #include "llvm/ADT/ilist_node.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: SimpleFile(StringRef path,File::Kind kind)40 SimpleFile(StringRef path, File::Kind kind) 41 : File(path, kind) {} 42 ~SimpleFile()43 ~SimpleFile() override { 44 _defined.clear(); 45 _undefined.clear(); 46 _shared.clear(); 47 _absolute.clear(); 48 } 49 addAtom(DefinedAtom & a)50 void addAtom(DefinedAtom &a) { 51 _defined.push_back(OwningAtomPtr<DefinedAtom>(&a)); 52 } addAtom(UndefinedAtom & a)53 void addAtom(UndefinedAtom &a) { 54 _undefined.push_back(OwningAtomPtr<UndefinedAtom>(&a)); 55 } addAtom(SharedLibraryAtom & a)56 void addAtom(SharedLibraryAtom &a) { 57 _shared.push_back(OwningAtomPtr<SharedLibraryAtom>(&a)); 58 } addAtom(AbsoluteAtom & a)59 void addAtom(AbsoluteAtom &a) { 60 _absolute.push_back(OwningAtomPtr<AbsoluteAtom>(&a)); 61 } 62 addAtom(const Atom & atom)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 removeDefinedAtomsIf(std::function<bool (const DefinedAtom *)> pred)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 defined()86 const AtomRange<DefinedAtom> defined() const override { return _defined; } 87 undefined()88 const AtomRange<UndefinedAtom> undefined() const override { 89 return _undefined; 90 } 91 sharedLibrary()92 const AtomRange<SharedLibraryAtom> sharedLibrary() const override { 93 return _shared; 94 } 95 absolute()96 const AtomRange<AbsoluteAtom> absolute() const override { 97 return _absolute; 98 } 99 clearAtoms()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 llvm::ilist_node<SimpleReference> { 116 public: SimpleReference(Reference::KindNamespace ns,Reference::KindArch arch,Reference::KindValue value,uint64_t off,const Atom * t,Reference::Addend a)117 SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch, 118 Reference::KindValue value, uint64_t off, const Atom *t, 119 Reference::Addend a) 120 : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a) { 121 } SimpleReference()122 SimpleReference() 123 : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0), 124 _target(nullptr), _offsetInAtom(0), _addend(0) {} 125 offsetInAtom()126 uint64_t offsetInAtom() const override { return _offsetInAtom; } 127 target()128 const Atom *target() const override { 129 assert(_target); 130 return _target; 131 } 132 addend()133 Addend addend() const override { return _addend; } setAddend(Addend a)134 void setAddend(Addend a) override { _addend = a; } setTarget(const Atom * newAtom)135 void setTarget(const Atom *newAtom) override { _target = newAtom; } 136 137 private: 138 const Atom *_target; 139 uint64_t _offsetInAtom; 140 Addend _addend; 141 }; 142 143 class SimpleDefinedAtom : public DefinedAtom { 144 public: SimpleDefinedAtom(const File & f)145 explicit SimpleDefinedAtom(const File &f) 146 : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {} 147 ~SimpleDefinedAtom()148 ~SimpleDefinedAtom() override { 149 _references.clearAndLeakNodesUnsafely(); 150 } 151 file()152 const File &file() const override { return _file; } 153 name()154 StringRef name() const override { return StringRef(); } 155 ordinal()156 uint64_t ordinal() const override { return _ordinal; } 157 scope()158 Scope scope() const override { return DefinedAtom::scopeLinkageUnit; } 159 interposable()160 Interposable interposable() const override { 161 return DefinedAtom::interposeNo; 162 } 163 merge()164 Merge merge() const override { return DefinedAtom::mergeNo; } 165 alignment()166 Alignment alignment() const override { return 1; } 167 sectionChoice()168 SectionChoice sectionChoice() const override { 169 return DefinedAtom::sectionBasedOnContent; 170 } 171 customSectionName()172 StringRef customSectionName() const override { return StringRef(); } deadStrip()173 DeadStripKind deadStrip() const override { 174 return DefinedAtom::deadStripNormal; 175 } 176 begin()177 DefinedAtom::reference_iterator begin() const override { 178 const void *it = 179 reinterpret_cast<const void *>(_references.begin().getNodePtr()); 180 return reference_iterator(*this, it); 181 } 182 end()183 DefinedAtom::reference_iterator end() const override { 184 const void *it = 185 reinterpret_cast<const void *>(_references.end().getNodePtr()); 186 return reference_iterator(*this, it); 187 } 188 derefIterator(const void * it)189 const Reference *derefIterator(const void *it) const override { 190 return &*RefList::const_iterator( 191 *reinterpret_cast<const llvm::ilist_node<SimpleReference> *>(it)); 192 } 193 incrementIterator(const void * & it)194 void incrementIterator(const void *&it) const override { 195 RefList::const_iterator ref( 196 *reinterpret_cast<const llvm::ilist_node<SimpleReference> *>(it)); 197 it = reinterpret_cast<const void *>(std::next(ref).getNodePtr()); 198 } 199 addReference(Reference::KindNamespace ns,Reference::KindArch arch,Reference::KindValue kindValue,uint64_t off,const Atom * target,Reference::Addend a)200 void addReference(Reference::KindNamespace ns, 201 Reference::KindArch arch, 202 Reference::KindValue kindValue, uint64_t off, 203 const Atom *target, Reference::Addend a) override { 204 assert(target && "trying to create reference to nothing"); 205 auto node = new (_file.allocator()) 206 SimpleReference(ns, arch, kindValue, off, target, a); 207 _references.push_back(node); 208 } 209 210 /// Sort references in a canonical order (by offset, then by kind). sortReferences()211 void sortReferences() const { 212 // Cannot sort a linked list, so move elements into a temporary vector, 213 // sort the vector, then reconstruct the list. 214 llvm::SmallVector<SimpleReference *, 16> elements; 215 for (SimpleReference &node : _references) { 216 elements.push_back(&node); 217 } 218 std::sort(elements.begin(), elements.end(), 219 [] (const SimpleReference *lhs, const SimpleReference *rhs) -> bool { 220 uint64_t lhsOffset = lhs->offsetInAtom(); 221 uint64_t rhsOffset = rhs->offsetInAtom(); 222 if (rhsOffset != lhsOffset) 223 return (lhsOffset < rhsOffset); 224 if (rhs->kindNamespace() != lhs->kindNamespace()) 225 return (lhs->kindNamespace() < rhs->kindNamespace()); 226 if (rhs->kindArch() != lhs->kindArch()) 227 return (lhs->kindArch() < rhs->kindArch()); 228 return (lhs->kindValue() < rhs->kindValue()); 229 }); 230 _references.clearAndLeakNodesUnsafely(); 231 for (SimpleReference *node : elements) { 232 _references.push_back(node); 233 } 234 } 235 setOrdinal(uint64_t ord)236 void setOrdinal(uint64_t ord) { _ordinal = ord; } 237 238 private: 239 typedef llvm::ilist<SimpleReference> RefList; 240 241 const File &_file; 242 uint64_t _ordinal; 243 mutable RefList _references; 244 }; 245 246 class SimpleUndefinedAtom : public UndefinedAtom { 247 public: SimpleUndefinedAtom(const File & f,StringRef name)248 SimpleUndefinedAtom(const File &f, StringRef name) : _file(f), _name(name) { 249 assert(!name.empty() && "UndefinedAtoms must have a name"); 250 } 251 252 ~SimpleUndefinedAtom() override = default; 253 254 /// file - returns the File that produced/owns this Atom file()255 const File &file() const override { return _file; } 256 257 /// name - The name of the atom. For a function atom, it is the (mangled) 258 /// name of the function. name()259 StringRef name() const override { return _name; } 260 canBeNull()261 CanBeNull canBeNull() const override { return UndefinedAtom::canBeNullNever; } 262 263 private: 264 const File &_file; 265 StringRef _name; 266 }; 267 268 } // end namespace lld 269 270 #endif // LLD_CORE_SIMPLE_H 271