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
36namespace lld {
37
38class SimpleFile : public File {
39public:
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
107private:
108  AtomVector<DefinedAtom> _defined;
109  AtomVector<UndefinedAtom> _undefined;
110  AtomVector<SharedLibraryAtom> _shared;
111  AtomVector<AbsoluteAtom> _absolute;
112};
113
114class SimpleReference : public Reference,
115                        public llvm::ilist_node<SimpleReference> {
116public:
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  }
122  SimpleReference()
123      : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0),
124        _target(nullptr), _offsetInAtom(0), _addend(0) {}
125
126  uint64_t offsetInAtom() const override { return _offsetInAtom; }
127
128  const Atom *target() const override {
129    assert(_target);
130    return _target;
131  }
132
133  Addend addend() const override { return _addend; }
134  void setAddend(Addend a) override { _addend = a; }
135  void setTarget(const Atom *newAtom) override { _target = newAtom; }
136
137private:
138  const Atom *_target;
139  uint64_t _offsetInAtom;
140  Addend _addend;
141};
142
143class SimpleDefinedAtom : public DefinedAtom {
144public:
145  explicit SimpleDefinedAtom(const File &f)
146      : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {}
147
148  ~SimpleDefinedAtom() override {
149    _references.clearAndLeakNodesUnsafely();
150  }
151
152  const File &file() const override { return _file; }
153
154  StringRef name() const override { return StringRef(); }
155
156  uint64_t ordinal() const override { return _ordinal; }
157
158  Scope scope() const override { return DefinedAtom::scopeLinkageUnit; }
159
160  Interposable interposable() const override {
161    return DefinedAtom::interposeNo;
162  }
163
164  Merge merge() const override { return DefinedAtom::mergeNo; }
165
166  Alignment alignment() const override { return 1; }
167
168  SectionChoice sectionChoice() const override {
169    return DefinedAtom::sectionBasedOnContent;
170  }
171
172  StringRef customSectionName() const override { return StringRef(); }
173  DeadStripKind deadStrip() const override {
174    return DefinedAtom::deadStripNormal;
175  }
176
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
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
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
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
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).
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
236  void setOrdinal(uint64_t ord) { _ordinal = ord; }
237
238private:
239  typedef llvm::ilist<SimpleReference> RefList;
240
241  const File &_file;
242  uint64_t _ordinal;
243  mutable RefList _references;
244};
245
246class SimpleUndefinedAtom : public UndefinedAtom {
247public:
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
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.
259  StringRef name() const override { return _name; }
260
261  CanBeNull canBeNull() const override { return UndefinedAtom::canBeNullNever; }
262
263private:
264  const File &_file;
265  StringRef _name;
266};
267
268} // end namespace lld
269
270#endif // LLD_CORE_SIMPLE_H
271