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// ConcatOutputSections that contain code (text) require special handling to
66// support thunk insertion.
67class TextOutputSection : public ConcatOutputSection {
68public:
69 explicit TextOutputSection(StringRef name)
70 : ConcatOutputSection(name, TextKind) {}
71 void finalizeContents() override {}
72 void finalize() override;
73 bool needsThunks() const;
74 ArrayRef<ConcatInputSection *> getThunks() const { return thunks; }
75 void writeTo(uint8_t *buf) const override;
76
77 static bool classof(const OutputSection *sec) {
78 return sec->kind() == TextKind;
79 }
80
81private:
82 uint64_t estimateBranchTargetThresholdVA(size_t callIdx) const;
83
84 std::vector<ConcatInputSection *> thunks;
85};
86
87// We maintain one ThunkInfo per real function.
88//
89// The "active thunk" is represented by the sym/isec pair that
90// turns-over during finalize(): as the call-site address advances,
91// the active thunk goes out of branch-range, and we create a new
92// thunk to take its place.
93//
94// The remaining members -- bools and counters -- apply to the
95// collection of thunks associated with the real function.
96
97struct ThunkInfo {
98 // These denote the active thunk:
99 Defined *sym = nullptr; // private-extern symbol for active thunk
100 ConcatInputSection *isec = nullptr; // input section for active thunk
101
102 // The following values are cumulative across all thunks on this function
103 uint32_t callSiteCount = 0; // how many calls to the real function?
104 uint32_t callSitesUsed = 0; // how many call sites processed so-far?
105 uint32_t thunkCallCount = 0; // how many call sites went to thunk?
106 uint8_t sequence = 0; // how many thunks created so-far?
107};
108
109NamePair maybeRenameSection(NamePair key);
110
111// Output sections are added to output segments in iteration order
112// of ConcatOutputSection, so must have deterministic iteration order.
113extern llvm::MapVector<NamePair, ConcatOutputSection *> concatOutputSections;
114
115// After ICF, multiple Defined symbols may point to the same (isec, value) yet
116// remain as distinct Symbol pointers. Using bare Symbol* as thunkMap keys
117// would create redundant thunks for the same target. This DenseMapInfo
118// canonicalizes Defined symbols by (isec, value) so that ICF-folded copies
119// share a single thunkMap entry.
120struct ThunkMapKeyInfo : llvm::DenseMapInfo<Symbol *> {
121 static unsigned getHashValue(const Symbol *sym) {
122 if (const auto *d = dyn_cast<Defined>(Val: sym))
123 return llvm::hash_combine(args: d->isec(), args: d->value);
124 return llvm::DenseMapInfo<Symbol *>::getHashValue(PtrVal: sym);
125 }
126 static bool isEqual(const Symbol *lhs, const Symbol *rhs) {
127 if (lhs == rhs)
128 return true;
129 if (lhs == getEmptyKey() || lhs == getTombstoneKey() ||
130 rhs == getEmptyKey() || rhs == getTombstoneKey())
131 return false;
132 const auto *dl = dyn_cast<Defined>(Val: lhs);
133 const auto *dr = dyn_cast<Defined>(Val: rhs);
134 if (dl && dr)
135 return dl->isec() == dr->isec() && dl->value == dr->value;
136 return false;
137 }
138};
139
140extern llvm::DenseMap<Symbol *, ThunkInfo, ThunkMapKeyInfo> thunkMap;
141
142} // namespace lld::macho
143
144#endif
145