LLVM  8.0.0svn
MachineOutliner.h
Go to the documentation of this file.
1 //===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// Contains all data structures shared between the outliner implemented in
12 /// MachineOutliner.cpp and target implementations of the outliner.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_MACHINEOUTLINER_H
17 #define LLVM_MACHINEOUTLINER_H
18 
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;
42 
43  /// The number of instructions in this \p Candidate.
44  unsigned Len;
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;
54 
55  /// Cost of calling an outlined function from this point as defined by the
56  /// target.
57  unsigned CallOverhead;
58 
59 public:
60  /// The index of this \p Candidate's \p OutlinedFunction in the list of
61  /// \p OutlinedFunctions.
62  unsigned FunctionIdx;
63 
64  /// Set to false if the candidate overlapped with another candidate.
65  bool InCandidateList = true;
66 
67  /// Identifier denoting the instructions to emit to call an outlined function
68  /// from this point. Defined by the target.
70 
71  /// Contains physical register liveness information for the MBB containing
72  /// this \p Candidate.
73  ///
74  /// This is optionally used by the target to calculate more fine-grained
75  /// cost model information.
77 
78  /// Contains the accumulated register liveness information for the
79  /// instructions in this \p Candidate.
80  ///
81  /// This is optionally used by the target to determine which registers have
82  /// been used across the sequence.
84 
85  /// Target-specific flags for this Candidate's MBB.
86  unsigned Flags = 0x0;
87 
88  /// True if initLRU has been called on this Candidate.
89  bool LRUWasSet = false;
90 
91  /// Return the number of instructions in this Candidate.
92  unsigned getLength() const { return Len; }
93 
94  /// Return the start index of this candidate.
95  unsigned getStartIdx() const { return StartIdx; }
96 
97  /// Return the end index of this candidate.
98  unsigned getEndIdx() const { return StartIdx + Len - 1; }
99 
100  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
101  /// CO respectively.
102  void setCallInfo(unsigned CID, unsigned CO) {
103  CallConstructionID = CID;
104  CallOverhead = CO;
105  }
106 
107  /// Returns the call overhead of this candidate if it is in the list.
108  unsigned getCallOverhead() const {
109  return InCandidateList ? CallOverhead : 0;
110  }
111 
112  MachineBasicBlock::iterator &front() { return FirstInst; }
113  MachineBasicBlock::iterator &back() { return LastInst; }
114  MachineFunction *getMF() const { return MBB->getParent(); }
115  MachineBasicBlock *getMBB() const { return MBB; }
116 
117  /// The number of instructions that would be saved by outlining every
118  /// candidate of this type.
119  ///
120  /// This is a fixed value which is not updated during the candidate pruning
121  /// process. It is only used for deciding which candidate to keep if two
122  /// candidates overlap. The true benefit is stored in the OutlinedFunction
123  /// for some given candidate.
124  unsigned Benefit = 0;
125 
126  Candidate(unsigned StartIdx, unsigned Len,
127  MachineBasicBlock::iterator &FirstInst,
129  unsigned FunctionIdx, unsigned Flags)
130  : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
131  MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
133 
134  /// Used to ensure that \p Candidates are outlined in an order that
135  /// preserves the start and end indices of other \p Candidates.
136  bool operator<(const Candidate &RHS) const {
137  return getStartIdx() > RHS.getStartIdx();
138  }
139 
140  /// Compute the registers that are live across this Candidate.
141  /// Used by targets that need this information for cost model calculation.
142  /// If a target does not need this information, then this should not be
143  /// called.
146  "Candidate's Machine Function must track liveness");
147  // Only initialize once.
148  if (LRUWasSet)
149  return;
150  LRUWasSet = true;
151  LRU.init(TRI);
152  LRU.addLiveOuts(*MBB);
153 
154  // Compute liveness from the end of the block up to the beginning of the
155  // outlining candidate.
157  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
158 
159  // Walk over the sequence itself and figure out which registers were used
160  // in the sequence.
161  UsedInSequence.init(TRI);
162  std::for_each(front(), std::next(back()),
163  [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
164  }
165 };
166 
167 /// The information necessary to create an outlined function for some
168 /// class of candidate.
170 
171 private:
172  /// The number of candidates for this \p OutlinedFunction.
173  unsigned OccurrenceCount = 0;
174 
175 public:
176  std::vector<std::shared_ptr<Candidate>> Candidates;
177 
178  /// The actual outlined function created.
179  /// This is initialized after we go through and create the actual function.
180  MachineFunction *MF = nullptr;
181 
182  /// The sequence of integers corresponding to the instructions in this
183  /// function.
184  std::vector<unsigned> Sequence;
185 
186  /// Represents the size of a sequence in bytes. (Some instructions vary
187  /// widely in size, so just counting the instructions isn't very useful.)
188  unsigned SequenceSize;
189 
190  /// Target-defined overhead of constructing a frame for this function.
191  unsigned FrameOverhead;
192 
193  /// Target-defined identifier for constructing a frame for this function.
195 
196  /// Return the number of candidates for this \p OutlinedFunction.
197  unsigned getOccurrenceCount() { return OccurrenceCount; }
198 
199  /// Decrement the occurrence count of this OutlinedFunction and return the
200  /// new count.
201  unsigned decrement() {
202  assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
203  OccurrenceCount--;
204  return getOccurrenceCount();
205  }
206 
207  /// Return the number of bytes it would take to outline this
208  /// function.
209  unsigned getOutliningCost() {
210  unsigned CallOverhead = 0;
211  for (std::shared_ptr<Candidate> &C : Candidates)
212  CallOverhead += C->getCallOverhead();
213  return CallOverhead + SequenceSize + FrameOverhead;
214  }
215 
216  /// Return the size in bytes of the unoutlined sequences.
217  unsigned getNotOutlinedCost() { return OccurrenceCount * SequenceSize; }
218 
219  /// Return the number of instructions that would be saved by outlining
220  /// this function.
221  unsigned getBenefit() {
222  unsigned NotOutlinedCost = getNotOutlinedCost();
223  unsigned OutlinedCost = getOutliningCost();
224  return (NotOutlinedCost < OutlinedCost) ? 0
225  : NotOutlinedCost - OutlinedCost;
226  }
227 
228  OutlinedFunction(std::vector<Candidate> &Cands,
229  unsigned SequenceSize, unsigned FrameOverhead,
230  unsigned FrameConstructionID)
231  : SequenceSize(SequenceSize), FrameOverhead(FrameOverhead),
232  FrameConstructionID(FrameConstructionID) {
233  OccurrenceCount = Cands.size();
234  for (Candidate &C : Cands)
235  Candidates.push_back(std::make_shared<outliner::Candidate>(C));
236 
237  unsigned B = getBenefit();
238  for (std::shared_ptr<Candidate> &C : Candidates)
239  C->Benefit = B;
240  }
241 
243 };
244 } // namespace outliner
245 } // namespace llvm
246 
247 #endif
std::vector< unsigned > Sequence
The sequence of integers corresponding to the instructions in this function.
uint64_t CallInst * C
unsigned getNotOutlinedCost()
Return the size in bytes of the unoutlined sequences.
unsigned getOutliningCost()
Return the number of bytes it would take to outline this function.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Candidate(unsigned StartIdx, unsigned Len, MachineBasicBlock::iterator &FirstInst, MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, unsigned FunctionIdx, unsigned Flags)
void initLRU(const TargetRegisterInfo &TRI)
Compute the registers that are live across this Candidate.
unsigned FrameOverhead
Target-defined overhead of constructing a frame for this function.
unsigned decrement()
Decrement the occurrence count of this OutlinedFunction and return the new count. ...
unsigned getStartIdx() const
Return the start index of this candidate.
LiveRegUnits LRU
Contains physical register liveness information for the MBB containing this Candidate.
unsigned getBenefit()
Return the number of instructions that would be saved by outlining this function. ...
unsigned const TargetRegisterInfo * TRI
An individual sequence of instructions to be replaced with a call to an outlined function.
bool InCandidateList
Set to false if the candidate overlapped with another candidate.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
unsigned SequenceSize
Represents the size of a sequence in bytes.
unsigned FrameConstructionID
Target-defined identifier for constructing a frame for this function.
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
unsigned getEndIdx() const
Return the end index of this candidate.
unsigned getOccurrenceCount()
Return the number of candidates for this OutlinedFunction.
unsigned getLength() const
Return the number of instructions in this Candidate.
reverse_iterator rbegin()
std::vector< std::shared_ptr< Candidate > > Candidates
MachineBasicBlock::iterator & back()
unsigned Flags
Target-specific flags for this Candidate&#39;s MBB.
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
Definition: LiveRegUnits.h:75
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool LRUWasSet
True if initLRU has been called on this Candidate.
InstrType
Represents how an instruction should be mapped by the outliner.
LiveRegUnits UsedInSequence
Contains the accumulated register liveness information for the instructions in this Candidate...
unsigned CallConstructionID
Identifier denoting the instructions to emit to call an outlined function from this point...
The information necessary to create an outlined function for some class of candidate.
void setCallInfo(unsigned CID, unsigned CO)
Set the CallConstructionID and CallOverhead of this candidate to CID and CO respectively.
unsigned getCallOverhead() const
Returns the call overhead of this candidate if it is in the list.
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
A set of register units.
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...
MachineBasicBlock::iterator & front()
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
unsigned Benefit
The number of instructions that would be saved by outlining every candidate of this type...
void accumulate(const MachineInstr &MI)
Adds all register units used, defined or clobbered in MI.
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
unsigned FunctionIdx
The index of this Candidate&#39;s OutlinedFunction in the list of OutlinedFunctions.
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:31
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutlinedFunction(std::vector< Candidate > &Cands, unsigned SequenceSize, unsigned FrameOverhead, unsigned FrameConstructionID)
IRTranslator LLVM IR MI
UnaryPredicate for_each(R &&Range, UnaryPredicate P)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1041
MachineFunction * getMF() const
MachineBasicBlock * getMBB() const