LLVM 20.0.0git
MachineOutliner.h
Go to the documentation of this file.
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
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.
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.
47
48 // The last instruction in this \p Candidate.
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);
87 // Compute liveness from the end of the block up to the beginning of the
88 // outlining candidate.
89 for (auto &MI : make_range(MBB->rbegin(),
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(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>
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(Regs, [&](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
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,
202 unsigned FunctionIdx, unsigned Flags)
203 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
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.
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.
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 {
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)
269 const unsigned B = getBenefit();
270 for (Candidate &C : Candidates)
271 C.Benefit = B;
272 }
273
275};
276} // namespace outliner
277} // namespace llvm
278
279#endif
MachineBasicBlock & MBB
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
IRTranslator LLVM IR MI
A set of register units.
unsigned const TargetRegisterInfo * TRI
unsigned Reg
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
Definition: LiveRegUnits.h:73
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
void accumulate(const MachineInstr &MI)
Adds all register units used, defined or clobbered in MI.
Representation of each machine instruction.
Definition: MachineInstr.h:69
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
InstrType
Represents how an instruction should be mapped by the outliner.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
An individual sequence of instructions to be replaced with a call to an outlined function.
unsigned Flags
Target-specific flags for this Candidate's MBB.
bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list< Register > Regs, const TargetRegisterInfo &TRI)
unsigned getCallOverhead() const
Returns the call overhead of this candidate if it is in the list.
void setCallInfo(unsigned CID, unsigned CO)
Set the CallConstructionID and CallOverhead of this candidate to CID and CO respectively.
unsigned Benefit
The number of instructions that would be saved by outlining every candidate of this type.
MachineBasicBlock * getMBB() const
MachineFunction * getMF() const
MachineBasicBlock::iterator begin()
bool operator<(const Candidate &RHS) const
Used to ensure that Candidates are outlined in an order that preserves the start and end indices of o...
unsigned getEndIdx() const
Return the end index of this candidate.
Candidate(unsigned StartIdx, unsigned Len, MachineBasicBlock::iterator &FirstInst, MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, unsigned FunctionIdx, unsigned Flags)
unsigned CallConstructionID
Identifier denoting the instructions to emit to call an outlined function from this point.
bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI)
unsigned getStartIdx() const
Return the start index of this candidate.
MachineBasicBlock::iterator end()
bool isAvailableAcrossAndOutOfSeq(Register Reg, const TargetRegisterInfo &TRI)
unsigned getLength() const
Return the number of instructions in this Candidate.
unsigned FunctionIdx
The index of this Candidate's OutlinedFunction in the list of OutlinedFunctions.
The information necessary to create an outlined function for some class of candidate.
unsigned getBenefit() const
Return the number of instructions that would be saved by outlining this function.
unsigned getNotOutlinedCost() const
Return the size in bytes of the unoutlined sequences.
unsigned getOutliningCost() const
Return the number of bytes it would take to outline this function.
MachineFunction * MF
The actual outlined function created.
unsigned FrameConstructionID
Target-defined identifier for constructing a frame for this function.
unsigned getNumInstrs() const
Return the number of instructions in this sequence.
OutlinedFunction(std::vector< Candidate > &Candidates, unsigned SequenceSize, unsigned FrameOverhead, unsigned FrameConstructionID)
unsigned FrameOverhead
Target-defined overhead of constructing a frame for this function.
unsigned SequenceSize
Represents the size of a sequence in bytes.
unsigned getOccurrenceCount() const
Return the number of candidates for this OutlinedFunction.
std::vector< Candidate > Candidates