contrib/llvm/tools/lld/lib/ReaderWriter/MachO/LayoutPass.h

   1 //===------ lib/ReaderWriter/MachO/LayoutPass.h - Handles Layout of atoms -===//
   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 #ifndef LLD_READER_WRITER_MACHO_LAYOUT_PASS_H
  10 #define LLD_READER_WRITER_MACHO_LAYOUT_PASS_H
  11
  12 #include "lld/Core/File.h"
  13 #include "lld/Core/Pass.h"
  14 #include "lld/Core/Reader.h"
  15 #include "lld/Core/Simple.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include <map>
  18 #include <string>
  19 #include <vector>
  20
  21 namespace lld {
  22 class DefinedAtom;
  23 class SimpleFile;
  24
  25 namespace mach_o {
  26
  27 /// This linker pass does the layout of the atoms. The pass is done after the
  28 /// order their .o files were found on the command line, then by order of the
  29 /// atoms (address) in the .o file.  But some atoms have a preferred location
  30 /// in their section (such as pinned to the start or end of the section), so
  31 /// the sort must take that into account too.
  32 class LayoutPass : public Pass {
  33 public:
  34   struct SortKey {
  35     SortKey(OwningAtomPtr<DefinedAtom> &&atom,
  36             const DefinedAtom *root, uint64_t override)
  37     : _atom(std::move(atom)), _root(root), _override(override) {}
  38     OwningAtomPtr<DefinedAtom> _atom;
  39     const DefinedAtom *_root;
  40     uint64_t _override;
  41
  42     // Note, these are only here to appease MSVC bots which didn't like
  43     // the same methods being implemented/deleted in OwningAtomPtr.
  44     SortKey(SortKey &&key) : _atom(std::move(key._atom)), _root(key._root),
  45                              _override(key._override) {
  46       key._root = nullptr;
  47     }
  48
  49     SortKey &operator=(SortKey &&key) {
  50       _atom = std::move(key._atom);
  51       _root = key._root;
  52       key._root = nullptr;
  53       _override = key._override;
  54       return *this;
  55     }
  56
  57   private:
  58     SortKey(const SortKey &) = delete;
  59     void operator=(const SortKey&) = delete;
  60   };
  61
  62   typedef std::function<bool (const DefinedAtom *left, const DefinedAtom *right,
  63                               bool &leftBeforeRight)> SortOverride;
  64
  65   LayoutPass(const Registry &registry, SortOverride sorter);
  66
  67   /// Sorts atoms in mergedFile by content type then by command line order.
  68   llvm::Error perform(SimpleFile &mergedFile) override;
  69
  70   ~LayoutPass() override = default;
  71
  72 private:
  73   // Build the followOn atoms chain as specified by the kindLayoutAfter
  74   // reference type
  75   void buildFollowOnTable(const File::AtomRange<DefinedAtom> &range);
  76
  77   // Build a map of Atoms to ordinals for sorting the atoms
  78   void buildOrdinalOverrideMap(const File::AtomRange<DefinedAtom> &range);
  79
  80   const Registry &_registry;
  81   SortOverride _customSorter;
  82
  83   typedef llvm::DenseMap<const DefinedAtom *, const DefinedAtom *> AtomToAtomT;
  84   typedef llvm::DenseMap<const DefinedAtom *, uint64_t> AtomToOrdinalT;
  85
  86   // A map to be used to sort atoms. It represents the order of atoms in the
  87   // result; if Atom X is mapped to atom Y in this map, X will be located
  88   // immediately before Y in the output file. Y might be mapped to another
  89   // atom, constructing a follow-on chain. An atom cannot be mapped to more
  90   // than one atom unless all but one atom are of size zero.
  91   AtomToAtomT _followOnNexts;
  92
  93   // A map to be used to sort atoms. It's a map from an atom to its root of
  94   // follow-on chain. A root atom is mapped to itself. If an atom is not in
  95   // _followOnNexts, the atom is not in this map, and vice versa.
  96   AtomToAtomT _followOnRoots;
  97
  98   AtomToOrdinalT _ordinalOverrideMap;
  99
 100   // Helper methods for buildFollowOnTable().
 101   const DefinedAtom *findAtomFollowedBy(const DefinedAtom *targetAtom);
 102   bool checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom);
 103
 104   void setChainRoot(const DefinedAtom *targetAtom, const DefinedAtom *root);
 105
 106   std::vector<SortKey> decorate(File::AtomRange<DefinedAtom> &atomRange) const;
 107
 108   void undecorate(File::AtomRange<DefinedAtom> &atomRange,
 109                   std::vector<SortKey> &keys) const;
 110
 111   // Check if the follow-on graph is a correct structure. For debugging only.
 112   void checkFollowonChain(const File::AtomRange<DefinedAtom> &range);
 113 };
 114
 115 } // namespace mach_o
 116 } // namespace lld
 117
 118 #endif // LLD_READER_WRITER_MACHO_LAYOUT_PASS_H