LLVM  15.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 
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.
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.
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 : make_range(front(), std::next(back())))
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 &front() { return FirstInst; }
139  MachineBasicBlock::iterator &back() { return LastInst; }
140  MachineFunction *getMF() const { return MBB->getParent(); }
141  MachineBasicBlock *getMBB() const { return MBB; }
142 
143  /// \returns True if \p Reg is available from the end of the block to the
144  /// beginning of the sequence.
145  ///
146  /// This query considers the following range:
147  ///
148  /// in_seq_1
149  /// in_seq_2
150  /// ...
151  /// in_seq_n
152  /// not_in_seq_1
153  /// ...
154  /// <end of block>
156  const TargetRegisterInfo &TRI) {
157  if (!FromEndOfBlockToStartOfSeqWasSet)
158  initFromEndOfBlockToStartOfSeq(TRI);
159  return FromEndOfBlockToStartOfSeq.available(Reg);
160  }
161 
162  /// \returns True if `isAvailableAcrossAndOutOfSeq` fails for any register
163  /// in \p Regs.
164  bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list<Register> Regs,
165  const TargetRegisterInfo &TRI) {
166  if (!FromEndOfBlockToStartOfSeqWasSet)
167  initFromEndOfBlockToStartOfSeq(TRI);
168  return any_of(Regs, [&](Register Reg) {
169  return !FromEndOfBlockToStartOfSeq.available(Reg);
170  });
171  }
172 
173  /// \returns True if \p Reg is available within the sequence itself.
174  ///
175  /// This query considers the following range:
176  ///
177  /// in_seq_1
178  /// in_seq_2
179  /// ...
180  /// in_seq_n
182  if (!InSeqWasSet)
183  initInSeq(TRI);
184  return InSeq.available(Reg);
185  }
186 
187  /// The number of instructions that would be saved by outlining every
188  /// candidate of this type.
189  ///
190  /// This is a fixed value which is not updated during the candidate pruning
191  /// process. It is only used for deciding which candidate to keep if two
192  /// candidates overlap. The true benefit is stored in the OutlinedFunction
193  /// for some given candidate.
194  unsigned Benefit = 0;
195 
196  Candidate(unsigned StartIdx, unsigned Len,
197  MachineBasicBlock::iterator &FirstInst,
199  unsigned FunctionIdx, unsigned Flags)
200  : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
202  Candidate() = default;
203 
204  /// Used to ensure that \p Candidates are outlined in an order that
205  /// preserves the start and end indices of other \p Candidates.
206  bool operator<(const Candidate &RHS) const {
207  return getStartIdx() > RHS.getStartIdx();
208  }
209 
210 };
211 
212 /// The information necessary to create an outlined function for some
213 /// class of candidate.
215 
216 public:
217  std::vector<Candidate> Candidates;
218 
219  /// The actual outlined function created.
220  /// This is initialized after we go through and create the actual function.
221  MachineFunction *MF = nullptr;
222 
223  /// Represents the size of a sequence in bytes. (Some instructions vary
224  /// widely in size, so just counting the instructions isn't very useful.)
225  unsigned SequenceSize = 0;
226 
227  /// Target-defined overhead of constructing a frame for this function.
228  unsigned FrameOverhead = 0;
229 
230  /// Target-defined identifier for constructing a frame for this function.
231  unsigned FrameConstructionID = 0;
232 
233  /// Return the number of candidates for this \p OutlinedFunction.
234  unsigned getOccurrenceCount() const { return Candidates.size(); }
235 
236  /// Return the number of bytes it would take to outline this
237  /// function.
238  unsigned getOutliningCost() const {
239  unsigned CallOverhead = 0;
240  for (const Candidate &C : Candidates)
241  CallOverhead += C.getCallOverhead();
242  return CallOverhead + SequenceSize + FrameOverhead;
243  }
244 
245  /// Return the size in bytes of the unoutlined sequences.
246  unsigned getNotOutlinedCost() const {
247  return getOccurrenceCount() * SequenceSize;
248  }
249 
250  /// Return the number of instructions that would be saved by outlining
251  /// this function.
252  unsigned getBenefit() const {
253  unsigned NotOutlinedCost = getNotOutlinedCost();
254  unsigned OutlinedCost = getOutliningCost();
255  return (NotOutlinedCost < OutlinedCost) ? 0
256  : NotOutlinedCost - OutlinedCost;
257  }
258 
259  /// Return the number of instructions in this sequence.
260  unsigned getNumInstrs() const { return Candidates[0].getLength(); }
261 
262  OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
263  unsigned FrameOverhead, unsigned FrameConstructionID)
266  const unsigned B = getBenefit();
267  for (Candidate &C : Candidates)
268  C.Benefit = B;
269  }
270 
271  OutlinedFunction() = default;
272 };
273 } // namespace outliner
274 } // namespace llvm
275 
276 #endif
llvm::outliner::OutlinedFunction::OutlinedFunction
OutlinedFunction()=default
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::outliner::OutlinedFunction::getOutliningCost
unsigned getOutliningCost() const
Return the number of bytes it would take to outline this function.
Definition: MachineOutliner.h:238
llvm::outliner::Candidate::isAnyUnavailableAcrossOrOutOfSeq
bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list< Register > Regs, const TargetRegisterInfo &TRI)
Definition: MachineOutliner.h:164
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::outliner::Candidate::FunctionIdx
unsigned FunctionIdx
The index of this Candidate's OutlinedFunction in the list of OutlinedFunctions.
Definition: MachineOutliner.h:110
llvm::LiveRegUnits::available
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::outliner::InstrType
InstrType
Represents how an instruction should be mapped by the outliner.
Definition: MachineOutliner.h:33
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::outliner::OutlinedFunction
The information necessary to create an outlined function for some class of candidate.
Definition: MachineOutliner.h:214
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1618
MachineRegisterInfo.h
llvm::outliner::OutlinedFunction::FrameOverhead
unsigned FrameOverhead
Target-defined overhead of constructing a frame for this function.
Definition: MachineOutliner.h:228
llvm::LiveRegUnits::addLiveOuts
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
Definition: LiveRegUnits.cpp:124
llvm::outliner::Candidate::CallConstructionID
unsigned CallConstructionID
Identifier denoting the instructions to emit to call an outlined function from this point.
Definition: MachineOutliner.h:114
llvm::LiveRegUnits::accumulate
void accumulate(const MachineInstr &MI)
Adds all register units used, defined or clobbered in MI.
Definition: LiveRegUnits.cpp:60
llvm::outliner::Candidate::setCallInfo
void setCallInfo(unsigned CID, unsigned CO)
Set the CallConstructionID and CallOverhead of this candidate to CID and CO respectively.
Definition: MachineOutliner.h:130
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::outliner::Candidate::getMF
MachineFunction * getMF() const
Definition: MachineOutliner.h:140
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::outliner::Invisible
@ Invisible
Definition: MachineOutliner.h:33
llvm::LiveRegUnits
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
llvm::outliner::Candidate::getEndIdx
unsigned getEndIdx() const
Return the end index of this candidate.
Definition: MachineOutliner.h:126
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::outliner::Candidate::isAvailableAcrossAndOutOfSeq
bool isAvailableAcrossAndOutOfSeq(Register Reg, const TargetRegisterInfo &TRI)
Definition: MachineOutliner.h:155
llvm::outliner::OutlinedFunction::getOccurrenceCount
unsigned getOccurrenceCount() const
Return the number of candidates for this OutlinedFunction.
Definition: MachineOutliner.h:234
llvm::LiveRegUnits::stepBackward
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
Definition: LiveRegUnits.cpp:40
llvm::outliner::LegalTerminator
@ LegalTerminator
Definition: MachineOutliner.h:33
llvm::outliner::Candidate
An individual sequence of instructions to be replaced with a call to an outlined function.
Definition: MachineOutliner.h:37
llvm::outliner::OutlinedFunction::getNotOutlinedCost
unsigned getNotOutlinedCost() const
Return the size in bytes of the unoutlined sequences.
Definition: MachineOutliner.h:246
llvm::outliner::Candidate::front
MachineBasicBlock::iterator & front()
Definition: MachineOutliner.h:138
llvm::outliner::Candidate::back
MachineBasicBlock::iterator & back()
Definition: MachineOutliner.h:139
llvm::LiveRegUnits::init
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
Definition: LiveRegUnits.h:73
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::outliner::OutlinedFunction::getBenefit
unsigned getBenefit() const
Return the number of instructions that would be saved by outlining this function.
Definition: MachineOutliner.h:252
llvm::outliner::OutlinedFunction::SequenceSize
unsigned SequenceSize
Represents the size of a sequence in bytes.
Definition: MachineOutliner.h:225
llvm::outliner::Candidate::Candidate
Candidate()=default
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::any_of
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:1614
LiveRegUnits.h
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::outliner::Candidate::Flags
unsigned Flags
Target-specific flags for this Candidate's MBB.
Definition: MachineOutliner.h:117
llvm::outliner::Candidate::Candidate
Candidate(unsigned StartIdx, unsigned Len, MachineBasicBlock::iterator &FirstInst, MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, unsigned FunctionIdx, unsigned Flags)
Definition: MachineOutliner.h:196
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::outliner::Candidate::getLength
unsigned getLength() const
Return the number of instructions in this Candidate.
Definition: MachineOutliner.h:120
llvm::outliner::Candidate::operator<
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...
Definition: MachineOutliner.h:206
llvm::outliner::OutlinedFunction::OutlinedFunction
OutlinedFunction(std::vector< Candidate > &Candidates, unsigned SequenceSize, unsigned FrameOverhead, unsigned FrameConstructionID)
Definition: MachineOutliner.h:262
llvm::outliner::Candidate::isAvailableInsideSeq
bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI)
Definition: MachineOutliner.h:181
llvm::outliner::Legal
@ Legal
Definition: MachineOutliner.h:33
llvm::outliner::Candidate::getCallOverhead
unsigned getCallOverhead() const
Returns the call overhead of this candidate if it is in the list.
Definition: MachineOutliner.h:136
llvm::outliner::Candidate::Benefit
unsigned Benefit
The number of instructions that would be saved by outlining every candidate of this type.
Definition: MachineOutliner.h:194
llvm::outliner::OutlinedFunction::MF
MachineFunction * MF
The actual outlined function created.
Definition: MachineOutliner.h:221
llvm::outliner::Candidate::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOutliner.h:141
llvm::outliner::Candidate::getStartIdx
unsigned getStartIdx() const
Return the start index of this candidate.
Definition: MachineOutliner.h:123
llvm::outliner::OutlinedFunction::getNumInstrs
unsigned getNumInstrs() const
Return the number of instructions in this sequence.
Definition: MachineOutliner.h:260
llvm::outliner::OutlinedFunction::Candidates
std::vector< Candidate > Candidates
Definition: MachineOutliner.h:217
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::outliner::OutlinedFunction::FrameConstructionID
unsigned FrameConstructionID
Target-defined identifier for constructing a frame for this function.
Definition: MachineOutliner.h:231
llvm::outliner::Illegal
@ Illegal
Definition: MachineOutliner.h:33