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
21namespace lld {
22class DefinedAtom;
23class SimpleFile;
24
25namespace 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.
32class LayoutPass : public Pass {
33public:
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
72private:
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