LLVM  13.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 
23 
24 namespace llvm {
25 namespace outliner {
26 
27 /// Represents how an instruction should be mapped by the outliner.
28 /// \p Legal instructions are those which are safe to outline.
29 /// \p LegalTerminator instructions are safe to outline, but only as the
30 /// last instruction in a sequence.
31 /// \p Illegal instructions are those which cannot be outlined.
32 /// \p Invisible instructions are instructions which can be outlined, but
33 /// shouldn't actually impact the outlining result.
35 
36 /// An individual sequence of instructions to be replaced with a call to
37 /// an outlined function.
38 struct Candidate {
39 private:
40  /// The start index of this \p Candidate in the instruction list.
41  unsigned StartIdx = 0;
42 
43  /// The number of instructions in this \p Candidate.
44  unsigned Len = 0;
45 
46  // The first instruction in this \p Candidate.
48 
49  // The last instruction in this \p Candidate.
51 
52  // The basic block that contains this Candidate.
53  MachineBasicBlock *MBB = nullptr;
54 
55  /// Cost of calling an outlined function from this point as defined by the
56  /// target.
57  unsigned CallOverhead = 0;
58 
59 public:
60  /// The index of this \p Candidate's \p OutlinedFunction in the list of
61  /// \p OutlinedFunctions.
62  unsigned FunctionIdx = 0;
63 
64  /// Identifier denoting the instructions to emit to call an outlined function
65  /// from this point. Defined by the target.
66  unsigned CallConstructionID = 0;
67 
68  /// Contains physical register liveness information for the MBB containing
69  /// this \p Candidate.
70  ///
71  /// This is optionally used by the target to calculate more fine-grained
72  /// cost model information.
74 
75  /// Contains the accumulated register liveness information for the
76  /// instructions in this \p Candidate.
77  ///
78  /// This is optionally used by the target to determine which registers have
79  /// been used across the sequence.
81 
82  /// Target-specific flags for this Candidate's MBB.
83  unsigned Flags = 0x0;
84 
85  /// True if initLRU has been called on this Candidate.
86  bool LRUWasSet = false;
87 
88  /// Return the number of instructions in this Candidate.
89  unsigned getLength() const { return Len; }
90 
91  /// Return the start index of this candidate.
92  unsigned getStartIdx() const { return StartIdx; }
93 
94  /// Return the end index of this candidate.
95  unsigned getEndIdx() const { return StartIdx + Len - 1; }
96 
97  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
98  /// CO respectively.
99  void setCallInfo(unsigned CID, unsigned CO) {
100  CallConstructionID = CID;
101  CallOverhead = CO;
102  }
103 
104  /// Returns the call overhead of this candidate if it is in the list.
105  unsigned getCallOverhead() const { return CallOverhead; }
106 
107  MachineBasicBlock::iterator &front() { return FirstInst; }
108  MachineBasicBlock::iterator &back() { return LastInst; }
109  MachineFunction *getMF() const { return MBB->getParent(); }
110  MachineBasicBlock *getMBB() const { return MBB; }
111 
112  /// The number of instructions that would be saved by outlining every
113  /// candidate of this type.
114  ///
115  /// This is a fixed value which is not updated during the candidate pruning
116  /// process. It is only used for deciding which candidate to keep if two
117  /// candidates overlap. The true benefit is stored in the OutlinedFunction
118  /// for some given candidate.
119  unsigned Benefit = 0;
120 
121  Candidate(unsigned StartIdx, unsigned Len,
122  MachineBasicBlock::iterator &FirstInst,
124  unsigned FunctionIdx, unsigned Flags)
125  : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
128 
129  /// Used to ensure that \p Candidates are outlined in an order that
130  /// preserves the start and end indices of other \p Candidates.
131  bool operator<(const Candidate &RHS) const {
132  return getStartIdx() > RHS.getStartIdx();
133  }
134 
135  /// Compute the registers that are live across this Candidate.
136  /// Used by targets that need this information for cost model calculation.
137  /// If a target does not need this information, then this should not be
138  /// called.
140  assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
141  "Candidate's Machine Function must track liveness");
142  // Only initialize once.
143  if (LRUWasSet)
144  return;
145  LRUWasSet = true;
146  LRU.init(TRI);
147  LRU.addLiveOuts(*MBB);
148 
149  // Compute liveness from the end of the block up to the beginning of the
150  // outlining candidate.
152  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
153 
154  // Walk over the sequence itself and figure out which registers were used
155  // in the sequence.
157  std::for_each(front(), std::next(back()),
158  [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
159  }
160 };
161 
162 /// The information necessary to create an outlined function for some
163 /// class of candidate.
165 
166 public:
167  std::vector<Candidate> Candidates;
168 
169  /// The actual outlined function created.
170  /// This is initialized after we go through and create the actual function.
171  MachineFunction *MF = nullptr;
172 
173  /// Represents the size of a sequence in bytes. (Some instructions vary
174  /// widely in size, so just counting the instructions isn't very useful.)
175  unsigned SequenceSize = 0;
176 
177  /// Target-defined overhead of constructing a frame for this function.
178  unsigned FrameOverhead = 0;
179 
180  /// Target-defined identifier for constructing a frame for this function.
181  unsigned FrameConstructionID = 0;
182 
183  /// Return the number of candidates for this \p OutlinedFunction.
184  unsigned getOccurrenceCount() const { return Candidates.size(); }
185 
186  /// Return the number of bytes it would take to outline this
187  /// function.
188  unsigned getOutliningCost() const {
189  unsigned CallOverhead = 0;
190  for (const Candidate &C : Candidates)
191  CallOverhead += C.getCallOverhead();
192  return CallOverhead + SequenceSize + FrameOverhead;
193  }
194 
195  /// Return the size in bytes of the unoutlined sequences.
196  unsigned getNotOutlinedCost() const {
197  return getOccurrenceCount() * SequenceSize;
198  }
199 
200  /// Return the number of instructions that would be saved by outlining
201  /// this function.
202  unsigned getBenefit() const {
203  unsigned NotOutlinedCost = getNotOutlinedCost();
204  unsigned OutlinedCost = getOutliningCost();
205  return (NotOutlinedCost < OutlinedCost) ? 0
206  : NotOutlinedCost - OutlinedCost;
207  }
208 
209  /// Return the number of instructions in this sequence.
210  unsigned getNumInstrs() const { return Candidates[0].getLength(); }
211 
212  OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
213  unsigned FrameOverhead, unsigned FrameConstructionID)
216  const unsigned B = getBenefit();
217  for (Candidate &C : Candidates)
218  C.Benefit = B;
219  }
220 
222 };
223 } // namespace outliner
224 } // namespace llvm
225 
226 #endif
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm
Definition: AllocatorList.h:23
llvm::outliner::OutlinedFunction::getOutliningCost
unsigned getOutliningCost() const
Return the number of bytes it would take to outline this function.
Definition: MachineOutliner.h:188
llvm::outliner::Candidate::FunctionIdx
unsigned FunctionIdx
The index of this Candidate's OutlinedFunction in the list of OutlinedFunctions.
Definition: MachineOutliner.h:62
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
llvm::outliner::InstrType
InstrType
Represents how an instruction should be mapped by the outliner.
Definition: MachineOutliner.h:34
llvm::outliner::OutlinedFunction
The information necessary to create an outlined function for some class of candidate.
Definition: MachineOutliner.h:164
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
MachineRegisterInfo.h
llvm::outliner::OutlinedFunction::FrameOverhead
unsigned FrameOverhead
Target-defined overhead of constructing a frame for this function.
Definition: MachineOutliner.h:178
llvm::outliner::OutlinedFunction::OutlinedFunction
OutlinedFunction()
Definition: MachineOutliner.h:221
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:66
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:99
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::outliner::Candidate::getMF
MachineFunction * getMF() const
Definition: MachineOutliner.h:109
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::outliner::Invisible
@ Invisible
Definition: MachineOutliner.h:34
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:95
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::outliner::OutlinedFunction::getOccurrenceCount
unsigned getOccurrenceCount() const
Return the number of candidates for this OutlinedFunction.
Definition: MachineOutliner.h:184
llvm::outliner::Candidate::UsedInSequence
LiveRegUnits UsedInSequence
Contains the accumulated register liveness information for the instructions in this Candidate.
Definition: MachineOutliner.h:80
llvm::LiveRegUnits::stepBackward
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
Definition: LiveRegUnits.cpp:40
llvm::outliner::Candidate::LRU
LiveRegUnits LRU
Contains physical register liveness information for the MBB containing this Candidate.
Definition: MachineOutliner.h:73
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1475
llvm::outliner::LegalTerminator
@ LegalTerminator
Definition: MachineOutliner.h:34
llvm::outliner::Candidate
An individual sequence of instructions to be replaced with a call to an outlined function.
Definition: MachineOutliner.h:38
llvm::outliner::OutlinedFunction::getNotOutlinedCost
unsigned getNotOutlinedCost() const
Return the size in bytes of the unoutlined sequences.
Definition: MachineOutliner.h:196
llvm::outliner::Candidate::front
MachineBasicBlock::iterator & front()
Definition: MachineOutliner.h:107
llvm::outliner::Candidate::LRUWasSet
bool LRUWasSet
True if initLRU has been called on this Candidate.
Definition: MachineOutliner.h:86
llvm::outliner::Candidate::back
MachineBasicBlock::iterator & back()
Definition: MachineOutliner.h:108
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:202
llvm::outliner::OutlinedFunction::SequenceSize
unsigned SequenceSize
Represents the size of a sequence in bytes.
Definition: MachineOutliner.h:175
llvm::MachineFunction
Definition: MachineFunction.h:230
LiveRegUnits.h
llvm::outliner::Candidate::Flags
unsigned Flags
Target-specific flags for this Candidate's MBB.
Definition: MachineOutliner.h:83
llvm::outliner::Candidate::Candidate
Candidate(unsigned StartIdx, unsigned Len, MachineBasicBlock::iterator &FirstInst, MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, unsigned FunctionIdx, unsigned Flags)
Definition: MachineOutliner.h:121
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::outliner::Candidate::Candidate
Candidate()
Definition: MachineOutliner.h:127
llvm::outliner::Candidate::getLength
unsigned getLength() const
Return the number of instructions in this Candidate.
Definition: MachineOutliner.h:89
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:131
llvm::outliner::Candidate::initLRU
void initLRU(const TargetRegisterInfo &TRI)
Compute the registers that are live across this Candidate.
Definition: MachineOutliner.h:139
llvm::outliner::OutlinedFunction::OutlinedFunction
OutlinedFunction(std::vector< Candidate > &Candidates, unsigned SequenceSize, unsigned FrameOverhead, unsigned FrameConstructionID)
Definition: MachineOutliner.h:212
llvm::outliner::Legal
@ Legal
Definition: MachineOutliner.h:34
llvm::outliner::Candidate::getCallOverhead
unsigned getCallOverhead() const
Returns the call overhead of this candidate if it is in the list.
Definition: MachineOutliner.h:105
llvm::outliner::Candidate::Benefit
unsigned Benefit
The number of instructions that would be saved by outlining every candidate of this type.
Definition: MachineOutliner.h:119
llvm::outliner::OutlinedFunction::MF
MachineFunction * MF
The actual outlined function created.
Definition: MachineOutliner.h:171
llvm::outliner::Candidate::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOutliner.h:110
llvm::outliner::Candidate::getStartIdx
unsigned getStartIdx() const
Return the start index of this candidate.
Definition: MachineOutliner.h:92
llvm::outliner::OutlinedFunction::getNumInstrs
unsigned getNumInstrs() const
Return the number of instructions in this sequence.
Definition: MachineOutliner.h:210
llvm::outliner::OutlinedFunction::Candidates
std::vector< Candidate > Candidates
Definition: MachineOutliner.h:167
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
TargetRegisterInfo.h
llvm::outliner::OutlinedFunction::FrameConstructionID
unsigned FrameConstructionID
Target-defined identifier for constructing a frame for this function.
Definition: MachineOutliner.h:181
llvm::outliner::Illegal
@ Illegal
Definition: MachineOutliner.h:34
LivePhysRegs.h