lib/ReaderWriter/MachO/GOTPass.cpp

   1 //===- lib/ReaderWriter/MachO/GOTPass.cpp ---------------------------------===//
   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 /// This linker pass transforms all GOT kind references to real references.
  12 /// That is, in assembly you can write something like:
  13 ///     movq foo@GOTPCREL(%rip), %rax
  14 /// which means you want to load a pointer to "foo" out of the GOT (global
  15 /// Offsets Table). In the object file, the Atom containing this instruction
  16 /// has a Reference whose target is an Atom named "foo" and the Reference
  17 /// kind is a GOT load.  The linker needs to instantiate a pointer sized
  18 /// GOT entry.  This is done be creating a GOT Atom to represent that pointer
  19 /// sized data in this pass, and altering the Atom graph so the Reference now
  20 /// points to the GOT Atom entry (corresponding to "foo") and changing the
  21 /// Reference Kind to reflect it is now pointing to a GOT entry (rather
  22 /// then needing a GOT entry).
  23 ///
  24 /// There is one optimization the linker can do here.  If the target of the GOT
  25 /// is in the same linkage unit and does not need to be interposable, and
  26 /// the GOT use is just a load (not some other operation), this pass can
  27 /// transform that load into an LEA (add).  This optimizes away one memory load
  28 /// which at runtime that could stall the pipeline.  This optimization only
  29 /// works for architectures in which a (GOT) load instruction can be change to
  30 /// an LEA instruction that is the same size.  The method isGOTAccess() should
  31 /// only return true for "canBypassGOT" if this optimization is supported.
  32 ///
  33 //===----------------------------------------------------------------------===//
  34
  35 #include "ArchHandler.h"
  36 #include "File.h"
  37 #include "MachOPasses.h"
  38 #include "lld/Core/DefinedAtom.h"
  39 #include "lld/Core/File.h"
  40 #include "lld/Core/LLVM.h"
  41 #include "lld/Core/Reference.h"
  42 #include "lld/Core/Simple.h"
  43 #include "llvm/ADT/DenseMap.h"
  44 #include "llvm/ADT/STLExtras.h"
  45
  46 namespace lld {
  47 namespace mach_o {
  48
  49
  50 //
  51 //  GOT Entry Atom created by the GOT pass.
  52 //
  53 class GOTEntryAtom : public SimpleDefinedAtom {
  54 public:
  55   GOTEntryAtom(const File &file, bool is64, StringRef name)
  56     : SimpleDefinedAtom(file), _is64(is64), _name(name) { }
  57
  58   ContentType contentType() const override {
  59     return DefinedAtom::typeGOT;
  60   }
  61
  62   Alignment alignment() const override {
  63     return Alignment(_is64 ? 3 : 2);
  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
  84 private:
  85   const bool _is64;
  86   StringRef _name;
  87 };
  88
  89
  90 /// Pass for instantiating and optimizing GOT slots.
  91 ///
  92 class GOTPass : public Pass {
  93 public:
  94   GOTPass(const MachOLinkingContext &context)
  95     : _context(context), _archHandler(_context.archHandler()),
  96       _file("<mach-o GOT Pass>") { }
  97
  98 private:
  99
 100   void perform(std::unique_ptr<MutableFile> &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 accesss.
 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
 137   bool shouldReplaceTargetWithGOTAtom(const Atom *target, bool canBypassGOT) {
 138     // Accesses to shared library symbols must go through GOT.
 139     if (isa<SharedLibraryAtom>(target))
 140       return true;
 141     // Accesses to interposable symbols in same linkage unit must also go
 142     // through GOT.
 143     const DefinedAtom *defTarget = dyn_cast<DefinedAtom>(target);
 144     if (defTarget != nullptr &&
 145         defTarget->interposable() != DefinedAtom::interposeNo) {
 146       assert(defTarget->scope() != DefinedAtom::scopeTranslationUnit);
 147       return true;
 148     }
 149     // Target does not require indirection.  So, if instruction allows GOT to be
 150     // by-passed, do that optimization and don't create GOT entry.
 151     return !canBypassGOT;
 152   }
 153
 154   const DefinedAtom *makeGOTEntry(const Atom *target) {
 155     auto pos = _targetToGOT.find(target);
 156     if (pos == _targetToGOT.end()) {
 157       GOTEntryAtom *gotEntry = new (_file.allocator())
 158           GOTEntryAtom(_file, _context.is64Bit(), target->name());
 159       _targetToGOT[target] = gotEntry;
 160       const ArchHandler::ReferenceInfo &nlInfo = _archHandler.stubInfo().
 161                                                 nonLazyPointerReferenceToBinder;
 162       gotEntry->addReference(Reference::KindNamespace::mach_o, nlInfo.arch,
 163                              nlInfo.kind, 0, target, 0);
 164       return gotEntry;
 165     }
 166     return pos->second;
 167   }
 168
 169
 170   const MachOLinkingContext                       &_context;
 171   mach_o::ArchHandler                             &_archHandler;
 172   MachOFile                                        _file;
 173   llvm::DenseMap<const Atom*, const GOTEntryAtom*> _targetToGOT;
 174 };
 175
 176
 177
 178 void addGOTPass(PassManager &pm, const MachOLinkingContext &ctx) {
 179   assert(ctx.needsGOTPass());
 180   pm.add(llvm::make_unique<GOTPass>(ctx));
 181 }
 182
 183
 184 } // end namesapce mach_o
 185 } // end namesapce lld