1//===- lib/ReaderWriter/MachO/GOTPass.cpp -----------------------*- C++ -*-===//
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/// This linker pass transforms all GOT kind references to real references.
11/// That is, in assembly you can write something like:
12///     movq foo@GOTPCREL(%rip), %rax
13/// which means you want to load a pointer to "foo" out of the GOT (global
14/// Offsets Table). In the object file, the Atom containing this instruction
15/// has a Reference whose target is an Atom named "foo" and the Reference
16/// kind is a GOT load.  The linker needs to instantiate a pointer sized
17/// GOT entry.  This is done be creating a GOT Atom to represent that pointer
18/// sized data in this pass, and altering the Atom graph so the Reference now
19/// points to the GOT Atom entry (corresponding to "foo") and changing the
20/// Reference Kind to reflect it is now pointing to a GOT entry (rather
21/// then needing a GOT entry).
22///
23/// There is one optimization the linker can do here.  If the target of the GOT
24/// is in the same linkage unit and does not need to be interposable, and
25/// the GOT use is just a load (not some other operation), this pass can
26/// transform that load into an LEA (add).  This optimizes away one memory load
27/// which at runtime that could stall the pipeline.  This optimization only
28/// works for architectures in which a (GOT) load instruction can be change to
29/// an LEA instruction that is the same size.  The method isGOTAccess() should
30/// only return true for "canBypassGOT" if this optimization is supported.
31///
32//===----------------------------------------------------------------------===//
33
34#include "ArchHandler.h"
35#include "File.h"
36#include "MachOPasses.h"
37#include "lld/Common/LLVM.h"
38#include "lld/Core/DefinedAtom.h"
39#include "lld/Core/File.h"
40#include "lld/Core/Reference.h"
41#include "lld/Core/Simple.h"
42#include "llvm/ADT/DenseMap.h"
43#include "llvm/ADT/STLExtras.h"
44
45namespace lld {
46namespace mach_o {
47
48//
49//  GOT Entry Atom created by the GOT pass.
50//
51class GOTEntryAtom : public SimpleDefinedAtom {
52public:
53  GOTEntryAtom(const File &file, bool is64, StringRef name)
54    : SimpleDefinedAtom(file), _is64(is64), _name(name) { }
55
56  ~GOTEntryAtom() override = default;
57
58  ContentType contentType() const override {
59    return DefinedAtom::typeGOT;
60  }
61
62  Alignment alignment() const override {
63    return _is64 ? 8 : 4;
64  }
65
66  uint64_t size() const override {
67    return _is64 ? 8 : 4;
68  }
69
70  ContentPermissions permissions() const override {
71    return DefinedAtom::permRW_;
72  }
73
74  ArrayRef<uint8_t> rawContent() const override {
75    static const uint8_t zeros[] =
76        { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
77    return llvm::makeArrayRef(zeros, size());
78  }
79
80  StringRef slotName() const {
81    return _name;
82  }
83
84private:
85  const bool _is64;
86  StringRef _name;
87};
88
89/// Pass for instantiating and optimizing GOT slots.
90///
91class GOTPass : public Pass {
92public:
93  GOTPass(const MachOLinkingContext &context)
94      : _ctx(context), _archHandler(_ctx.archHandler()),
95        _file(*_ctx.make_file<MachOFile>("<mach-o GOT Pass>")) {
96    _file.setOrdinal(_ctx.getNextOrdinalAndIncrement());
97  }
98
99private:
100  llvm::Error perform(SimpleFile &mergedFile) override {
101    // Scan all references in all atoms.
102    for (const DefinedAtom *atom : mergedFile.defined()) {
103      for (const Reference *ref : *atom) {
104        // Look at instructions accessing the GOT.
105        bool canBypassGOT;
106        if (!_archHandler.isGOTAccess(*ref, canBypassGOT))
107          continue;
108        const Atom *target = ref->target();
109        assert(target != nullptr);
110
111        if (!shouldReplaceTargetWithGOTAtom(target, canBypassGOT)) {
112          // Update reference kind to reflect that target is a direct access.
113          _archHandler.updateReferenceToGOT(ref, false);
114        } else {
115          // Replace the target with a reference to a GOT entry.
116          const DefinedAtom *gotEntry = makeGOTEntry(target);
117          const_cast<Reference *>(ref)->setTarget(gotEntry);
118          // Update reference kind to reflect that target is now a GOT entry.
119          _archHandler.updateReferenceToGOT(ref, true);
120        }
121      }
122    }
123
124    // Sort and add all created GOT Atoms to master file
125    std::vector<const GOTEntryAtom *> entries;
126    entries.reserve(_targetToGOT.size());
127    for (auto &it : _targetToGOT)
128      entries.push_back(it.second);
129    std::sort(entries.begin(), entries.end(),
130              [](const GOTEntryAtom *left, const GOTEntryAtom *right) {
131      return (left->slotName().compare(right->slotName()) < 0);
132    });
133    for (const GOTEntryAtom *slot : entries)
134      mergedFile.addAtom(*slot);
135
136    return llvm::Error::success();
137  }
138
139  bool shouldReplaceTargetWithGOTAtom(const Atom *target, bool canBypassGOT) {
140    // Accesses to shared library symbols must go through GOT.
141    if (isa<SharedLibraryAtom>(target))
142      return true;
143    // Accesses to interposable symbols in same linkage unit must also go
144    // through GOT.
145    const DefinedAtom *defTarget = dyn_cast<DefinedAtom>(target);
146    if (defTarget != nullptr &&
147        defTarget->interposable() != DefinedAtom::interposeNo) {
148      assert(defTarget->scope() != DefinedAtom::scopeTranslationUnit);
149      return true;
150    }
151    // Target does not require indirection.  So, if instruction allows GOT to be
152    // by-passed, do that optimization and don't create GOT entry.
153    return !canBypassGOT;
154  }
155
156  const DefinedAtom *makeGOTEntry(const Atom *target) {
157    auto pos = _targetToGOT.find(target);
158    if (pos == _targetToGOT.end()) {
159      auto *gotEntry = new (_file.allocator())
160          GOTEntryAtom(_file, _ctx.is64Bit(), target->name());
161      _targetToGOT[target] = gotEntry;
162      const ArchHandler::ReferenceInfo &nlInfo = _archHandler.stubInfo().
163                                                nonLazyPointerReferenceToBinder;
164      gotEntry->addReference(Reference::KindNamespace::mach_o, nlInfo.arch,
165                             nlInfo.kind, 0, target, 0);
166      return gotEntry;
167    }
168    return pos->second;
169  }
170
171  const MachOLinkingContext &_ctx;
172  mach_o::ArchHandler                             &_archHandler;
173  MachOFile                                       &_file;
174  llvm::DenseMap<const Atom*, const GOTEntryAtom*> _targetToGOT;
175};
176
177void addGOTPass(PassManager &pm, const MachOLinkingContext &ctx) {
178  assert(ctx.needsGOTPass());
179  pm.add(std::make_unique<GOTPass>(ctx));
180}
181
182} // end namesapce mach_o
183} // end namesapce lld
184