1//===- ConcatOutputSection.h ------------------------------------*- 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#ifndef LLD_MACHO_CONCAT_OUTPUT_SECTION_H
10#define LLD_MACHO_CONCAT_OUTPUT_SECTION_H
11
12#include "InputSection.h"
13#include "OutputSection.h"
14#include "Symbols.h"
15#include "lld/Common/LLVM.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/MapVector.h"
18
19namespace lld::macho {
20
21// Linking multiple files will inevitably mean resolving sections in different
22// files that are labeled with the same segment and section name. This class
23// contains all such sections and writes the data from each section sequentially
24// in the final binary.
25class ConcatOutputSection : public OutputSection {
26public:
27 explicit ConcatOutputSection(StringRef name,
28 OutputSection::Kind kind = ConcatKind)
29 : OutputSection(kind, name) {}
30
31 const ConcatInputSection *firstSection() const { return inputs.front(); }
32 const ConcatInputSection *lastSection() const { return inputs.back(); }
33 bool isNeeded() const override { return !inputs.empty(); }
34
35 // These accessors will only be valid after finalizing the section
36 uint64_t getSize() const override { return size; }
37 uint64_t getFileSize() const override { return fileSize; }
38
39 // Assign values to InputSection::outSecOff. In contrast to TextOutputSection,
40 // which does this in its implementation of `finalize()`, we can do this
41 // without `finalize()`'s sequential guarantees detailed in the block comment
42 // of `OutputSection::finalize()`.
43 virtual void finalizeContents();
44
45 void addInput(ConcatInputSection *input);
46 void writeTo(uint8_t *buf) const override;
47
48 static bool classof(const OutputSection *sec) {
49 return sec->kind() == ConcatKind || sec->kind() == TextKind;
50 }
51
52 static ConcatOutputSection *getOrCreateForInput(const InputSection *);
53
54 std::vector<ConcatInputSection *> inputs;
55
56protected:
57 size_t size = 0;
58 uint64_t fileSize = 0;
59 void finalizeOne(ConcatInputSection *);
60
61private:
62 void finalizeFlags(InputSection *input);
63};
64
65// We maintain one ThunkInfo per real function.
66//
67// The "active thunk" is represented by the sym/isec pair that
68// turns-over during finalize(): as the call-site address advances,
69// the active thunk goes out of branch-range, and we create a new
70// thunk to take its place.
71//
72// The remaining members -- bools and counters -- apply to the
73// collection of thunks associated with the real function.
74
75struct ThunkInfo {
76 // These denote the active thunk:
77 Defined *sym = nullptr; // private-extern symbol for active thunk
78 ConcatInputSection *isec = nullptr; // input section for active thunk
79
80 // The following value is cumulative across all thunks on this function
81 uint8_t sequence = 0; // how many thunks created so-far?
82};
83
84// ConcatOutputSections that contain code (text) require special handling to
85// support thunk insertion.
86class TextOutputSection : public ConcatOutputSection {
87public:
88 explicit TextOutputSection(StringRef name)
89 : ConcatOutputSection(name, TextKind) {}
90 void finalizeContents() override {}
91 void finalize() override;
92 bool needsThunks() const;
93 ArrayRef<ConcatInputSection *> getThunks() const { return thunks; }
94 void writeTo(uint8_t *buf) const override;
95
96 static bool classof(const OutputSection *sec) {
97 return sec->kind() == TextKind;
98 }
99
100private:
101 std::vector<ConcatInputSection *> thunks;
102 /// \return true if the target in \p r is in range from the location in \p
103 /// isec. If the target isec is not finalized, \return false.
104 bool isTargetKnownInRange(const ConcatInputSection &isec,
105 const Relocation &r) const;
106 /// If there exists a thunk in range of the target in \p r, \return that
107 /// thunk.
108 Defined *getThunkInRange(const ConcatInputSection &isec, const Relocation &r,
109 const ThunkInfo &thunkInfo) const;
110 /// Update \p r to target \p thunk which is guaranteed to be in range.
111 void updateBranchTargetToThunk(Relocation &r, Defined *thunk);
112 /// Create a new thunk and update \p r to target the new thunk.
113 void createThunk(const ConcatInputSection &isec, Relocation &r,
114 ThunkInfo &thunkInfo);
115 /// \return the largest possible stub section end VA or \p std::nullopt if we
116 /// can't estimate this yet. Used to determine if stub symbol targets are in
117 /// range.
118 std::optional<uint64_t> estimateStubsEndVA(unsigned numPotentialThunks) const;
119 /// \return true if the target in \p r is in __stubs or __objc_stubs and in
120 /// range from the location in \p isec. \p estimatedStubsEnd is the estimated
121 /// VA of the end of the last stubs section.
122 bool isTargetStubsAndInRange(const ConcatInputSection &isec,
123 const Relocation &r,
124 std::optional<uint64_t> estimatedStubsEnd) const;
125 /// The number of relocations updated to point to thunks.
126 size_t thunkCallCount = 0;
127};
128
129NamePair maybeRenameSection(NamePair key);
130
131// Output sections are added to output segments in iteration order
132// of ConcatOutputSection, so must have deterministic iteration order.
133extern llvm::MapVector<NamePair, ConcatOutputSection *> concatOutputSections;
134
135// Branch-extension thunks are keyed by both the target referent and the
136// branch relocation's addend. Two call sites that branch to the same
137// symbol with different addends (e.g. `bl _func` and `bl _func+8`) target
138// distinct addresses and therefore need distinct thunks.
139//
140// After ICF, multiple Defined symbols may point to the same (isec, value)
141// yet remain as distinct Symbol pointers. The equality predicate below
142// canonicalizes Defined symbols by (isec, value) so that ICF-folded copies
143// still share a single thunkMap entry when their addends match.
144struct ThunkKey {
145 Symbol *sym;
146 int64_t addend;
147
148 ThunkKey(Symbol *sym, int64_t addend) : sym(sym), addend(addend) {}
149 ThunkKey(Relocation &r) : ThunkKey(cast<Symbol *>(Val&: r.referent), r.addend) {}
150
151 bool operator==(const ThunkKey &other) const {
152 if (addend != other.addend)
153 return false;
154 if (sym == other.sym)
155 return true;
156 const auto *dl = dyn_cast<Defined>(Val: sym);
157 const auto *dr = dyn_cast<Defined>(Val: other.sym);
158 if (dl && dr)
159 return dl->isec() == dr->isec() && dl->value == dr->value;
160 return false;
161 }
162};
163
164struct ThunkMapKeyInfo {
165 static unsigned getHashValue(const ThunkKey &k) {
166 if (const auto *d = dyn_cast<Defined>(Val: k.sym))
167 return llvm::hash_combine(args: d->isec(), args: d->value, args: k.addend);
168 return llvm::hash_combine(args: k.sym, args: k.addend);
169 }
170 static bool isEqual(const ThunkKey &lhs, const ThunkKey &rhs) {
171 return lhs == rhs;
172 }
173};
174
175extern llvm::DenseMap<ThunkKey, ThunkInfo, ThunkMapKeyInfo> thunkMap;
176
177} // namespace lld::macho
178
179#endif
180