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
23namespace llvm {
24namespace 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.
33enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
34
35/// An individual sequence of instructions to be replaced with a call to
36/// an outlined function.
37struct Candidate {
38private:
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
107public:
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.
217struct OutlinedFunction {
218
219public:
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

source code of llvm/include/llvm/CodeGen/MachineOutliner.h