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 { SortKeySortKey35 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. SortKeySortKey44 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 ®istry, 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 119