1 | //===---- MachineOutliner.h - Outliner data structures ------*- 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 | /// \file |
10 | /// Contains all data structures shared between the outliner implemented in |
11 | /// MachineOutliner.cpp and target implementations of the outliner. |
12 | /// |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_CODEGEN_MACHINEOUTLINER_H |
16 | #define LLVM_CODEGEN_MACHINEOUTLINER_H |
17 | |
18 | #include "llvm/CodeGen/LiveRegUnits.h" |
19 | #include "llvm/CodeGen/MachineFunction.h" |
20 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
21 | #include <initializer_list> |
22 | |
23 | namespace llvm { |
24 | namespace outliner { |
25 | |
26 | /// Represents how an instruction should be mapped by the outliner. |
27 | /// \p Legal instructions are those which are safe to outline. |
28 | /// \p LegalTerminator instructions are safe to outline, but only as the |
29 | /// last instruction in a sequence. |
30 | /// \p Illegal instructions are those which cannot be outlined. |
31 | /// \p Invisible instructions are instructions which can be outlined, but |
32 | /// shouldn't actually impact the outlining result. |
33 | enum InstrType { Legal, LegalTerminator, Illegal, Invisible }; |
34 | |
35 | /// An individual sequence of instructions to be replaced with a call to |
36 | /// an outlined function. |
37 | struct Candidate { |
38 | private: |
39 | /// The start index of this \p Candidate in the instruction list. |
40 | unsigned StartIdx = 0; |
41 | |
42 | /// The number of instructions in this \p Candidate. |
43 | unsigned Len = 0; |
44 | |
45 | // The first instruction in this \p Candidate. |
46 | MachineBasicBlock::iterator FirstInst; |
47 | |
48 | // The last instruction in this \p Candidate. |
49 | MachineBasicBlock::iterator LastInst; |
50 | |
51 | // The basic block that contains this Candidate. |
52 | MachineBasicBlock *MBB = nullptr; |
53 | |
54 | /// Cost of calling an outlined function from this point as defined by the |
55 | /// target. |
56 | unsigned CallOverhead = 0; |
57 | |
58 | /// Liveness information for this Candidate. Tracks from the end of the |
59 | /// block containing this Candidate to the beginning of its sequence. |
60 | /// |
61 | /// Optional. Can be used to fine-tune the cost model, or fine-tune legality |
62 | /// decisions. |
63 | LiveRegUnits FromEndOfBlockToStartOfSeq; |
64 | |
65 | /// Liveness information restricted to this Candidate's instruction sequence. |
66 | /// |
67 | /// Optional. Can be used to fine-tune the cost model, or fine-tune legality |
68 | /// decisions. |
69 | LiveRegUnits InSeq; |
70 | |
71 | /// True if FromEndOfBlockToStartOfSeq has been initialized. |
72 | bool FromEndOfBlockToStartOfSeqWasSet = false; |
73 | |
74 | /// True if InSeq has been initialized. |
75 | bool InSeqWasSet = false; |
76 | |
77 | /// Populate FromEndOfBlockToStartOfSeq with liveness information. |
78 | void initFromEndOfBlockToStartOfSeq(const TargetRegisterInfo &TRI) { |
79 | assert(MBB->getParent()->getRegInfo().tracksLiveness() && |
80 | "Candidate's Machine Function must track liveness" ); |
81 | // Only initialize once. |
82 | if (FromEndOfBlockToStartOfSeqWasSet) |
83 | return; |
84 | FromEndOfBlockToStartOfSeqWasSet = true; |
85 | FromEndOfBlockToStartOfSeq.init(TRI); |
86 | FromEndOfBlockToStartOfSeq.addLiveOuts(MBB: *MBB); |
87 | // Compute liveness from the end of the block up to the beginning of the |
88 | // outlining candidate. |
89 | for (auto &MI : make_range(x: MBB->rbegin(), |
90 | y: (MachineBasicBlock::reverse_iterator)begin())) |
91 | FromEndOfBlockToStartOfSeq.stepBackward(MI); |
92 | } |
93 | |
94 | /// Populate InSeq with liveness information. |
95 | void initInSeq(const TargetRegisterInfo &TRI) { |
96 | assert(MBB->getParent()->getRegInfo().tracksLiveness() && |
97 | "Candidate's Machine Function must track liveness" ); |
98 | // Only initialize once. |
99 | if (InSeqWasSet) |
100 | return; |
101 | InSeqWasSet = true; |
102 | InSeq.init(TRI); |
103 | for (auto &MI : *this) |
104 | InSeq.accumulate(MI); |
105 | } |
106 | |
107 | public: |
108 | /// The index of this \p Candidate's \p OutlinedFunction in the list of |
109 | /// \p OutlinedFunctions. |
110 | unsigned FunctionIdx = 0; |
111 | |
112 | /// Identifier denoting the instructions to emit to call an outlined function |
113 | /// from this point. Defined by the target. |
114 | unsigned CallConstructionID = 0; |
115 | |
116 | /// Target-specific flags for this Candidate's MBB. |
117 | unsigned Flags = 0x0; |
118 | |
119 | /// Return the number of instructions in this Candidate. |
120 | unsigned getLength() const { return Len; } |
121 | |
122 | /// Return the start index of this candidate. |
123 | unsigned getStartIdx() const { return StartIdx; } |
124 | |
125 | /// Return the end index of this candidate. |
126 | unsigned getEndIdx() const { return StartIdx + Len - 1; } |
127 | |
128 | /// Set the CallConstructionID and CallOverhead of this candidate to CID and |
129 | /// CO respectively. |
130 | void setCallInfo(unsigned CID, unsigned CO) { |
131 | CallConstructionID = CID; |
132 | CallOverhead = CO; |
133 | } |
134 | |
135 | /// Returns the call overhead of this candidate if it is in the list. |
136 | unsigned getCallOverhead() const { return CallOverhead; } |
137 | |
138 | MachineBasicBlock::iterator begin() { return FirstInst; } |
139 | MachineBasicBlock::iterator end() { return std::next(x: LastInst); } |
140 | |
141 | MachineInstr &front() { return *FirstInst; } |
142 | MachineInstr &back() { return *LastInst; } |
143 | MachineFunction *getMF() const { return MBB->getParent(); } |
144 | MachineBasicBlock *getMBB() const { return MBB; } |
145 | |
146 | /// \returns True if \p Reg is available from the end of the block to the |
147 | /// beginning of the sequence. |
148 | /// |
149 | /// This query considers the following range: |
150 | /// |
151 | /// in_seq_1 |
152 | /// in_seq_2 |
153 | /// ... |
154 | /// in_seq_n |
155 | /// not_in_seq_1 |
156 | /// ... |
157 | /// <end of block> |
158 | bool isAvailableAcrossAndOutOfSeq(Register Reg, |
159 | const TargetRegisterInfo &TRI) { |
160 | if (!FromEndOfBlockToStartOfSeqWasSet) |
161 | initFromEndOfBlockToStartOfSeq(TRI); |
162 | return FromEndOfBlockToStartOfSeq.available(Reg); |
163 | } |
164 | |
165 | /// \returns True if `isAvailableAcrossAndOutOfSeq` fails for any register |
166 | /// in \p Regs. |
167 | bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list<Register> Regs, |
168 | const TargetRegisterInfo &TRI) { |
169 | if (!FromEndOfBlockToStartOfSeqWasSet) |
170 | initFromEndOfBlockToStartOfSeq(TRI); |
171 | return any_of(Range&: Regs, P: [&](Register Reg) { |
172 | return !FromEndOfBlockToStartOfSeq.available(Reg); |
173 | }); |
174 | } |
175 | |
176 | /// \returns True if \p Reg is available within the sequence itself. |
177 | /// |
178 | /// This query considers the following range: |
179 | /// |
180 | /// in_seq_1 |
181 | /// in_seq_2 |
182 | /// ... |
183 | /// in_seq_n |
184 | bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI) { |
185 | if (!InSeqWasSet) |
186 | initInSeq(TRI); |
187 | return InSeq.available(Reg); |
188 | } |
189 | |
190 | /// The number of instructions that would be saved by outlining every |
191 | /// candidate of this type. |
192 | /// |
193 | /// This is a fixed value which is not updated during the candidate pruning |
194 | /// process. It is only used for deciding which candidate to keep if two |
195 | /// candidates overlap. The true benefit is stored in the OutlinedFunction |
196 | /// for some given candidate. |
197 | unsigned Benefit = 0; |
198 | |
199 | Candidate(unsigned StartIdx, unsigned Len, |
200 | MachineBasicBlock::iterator &FirstInst, |
201 | MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, |
202 | unsigned FunctionIdx, unsigned Flags) |
203 | : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), |
204 | MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {} |
205 | Candidate() = delete; |
206 | |
207 | /// Used to ensure that \p Candidates are outlined in an order that |
208 | /// preserves the start and end indices of other \p Candidates. |
209 | bool operator<(const Candidate &RHS) const { |
210 | return getStartIdx() > RHS.getStartIdx(); |
211 | } |
212 | |
213 | }; |
214 | |
215 | /// The information necessary to create an outlined function for some |
216 | /// class of candidate. |
217 | struct OutlinedFunction { |
218 | |
219 | public: |
220 | std::vector<Candidate> Candidates; |
221 | |
222 | /// The actual outlined function created. |
223 | /// This is initialized after we go through and create the actual function. |
224 | MachineFunction *MF = nullptr; |
225 | |
226 | /// Represents the size of a sequence in bytes. (Some instructions vary |
227 | /// widely in size, so just counting the instructions isn't very useful.) |
228 | unsigned SequenceSize = 0; |
229 | |
230 | /// Target-defined overhead of constructing a frame for this function. |
231 | unsigned FrameOverhead = 0; |
232 | |
233 | /// Target-defined identifier for constructing a frame for this function. |
234 | unsigned FrameConstructionID = 0; |
235 | |
236 | /// Return the number of candidates for this \p OutlinedFunction. |
237 | unsigned getOccurrenceCount() const { return Candidates.size(); } |
238 | |
239 | /// Return the number of bytes it would take to outline this |
240 | /// function. |
241 | unsigned getOutliningCost() const { |
242 | unsigned CallOverhead = 0; |
243 | for (const Candidate &C : Candidates) |
244 | CallOverhead += C.getCallOverhead(); |
245 | return CallOverhead + SequenceSize + FrameOverhead; |
246 | } |
247 | |
248 | /// Return the size in bytes of the unoutlined sequences. |
249 | unsigned getNotOutlinedCost() const { |
250 | return getOccurrenceCount() * SequenceSize; |
251 | } |
252 | |
253 | /// Return the number of instructions that would be saved by outlining |
254 | /// this function. |
255 | unsigned getBenefit() const { |
256 | unsigned NotOutlinedCost = getNotOutlinedCost(); |
257 | unsigned OutlinedCost = getOutliningCost(); |
258 | return (NotOutlinedCost < OutlinedCost) ? 0 |
259 | : NotOutlinedCost - OutlinedCost; |
260 | } |
261 | |
262 | /// Return the number of instructions in this sequence. |
263 | unsigned getNumInstrs() const { return Candidates[0].getLength(); } |
264 | |
265 | OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize, |
266 | unsigned FrameOverhead, unsigned FrameConstructionID) |
267 | : Candidates(Candidates), SequenceSize(SequenceSize), |
268 | FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) { |
269 | const unsigned B = getBenefit(); |
270 | for (Candidate &C : Candidates) |
271 | C.Benefit = B; |
272 | } |
273 | |
274 | OutlinedFunction() = delete; |
275 | }; |
276 | } // namespace outliner |
277 | } // namespace llvm |
278 | |
279 | #endif |
280 | |