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  /// Identifier denoting the instructions to emit to call an outlined function
65  /// from this point. Defined by the target.
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),
126  MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
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.
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.
156  UsedInSequence.init(TRI);
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;
176 
177  /// Target-defined overhead of constructing a frame for this function.
178  unsigned FrameOverhead;
179 
180  /// Target-defined identifier for constructing a frame for this function.
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)
214  : Candidates(Candidates), SequenceSize(SequenceSize),
215  FrameOverhead(FrameOverhead), FrameConstructionID(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
uint64_t CallInst * C
This class represents lattice values for constants.
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 getStartIdx() const
Return the start index of this candidate.
LiveRegUnits LRU
Contains physical register liveness information for the MBB containing this Candidate.
unsigned const TargetRegisterInfo * TRI
An individual sequence of instructions to be replaced with a call to an outlined function.
std::vector< Candidate > Candidates
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.
unsigned getOccurrenceCount() const
Return the number of candidates for this OutlinedFunction.
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
unsigned getEndIdx() const
Return the end index of this candidate.
unsigned getLength() const
Return the number of instructions in this Candidate.
reverse_iterator rbegin()
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.
OutlinedFunction(std::vector< Candidate > &Candidates, unsigned SequenceSize, unsigned FrameOverhead, unsigned FrameConstructionID)
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...
unsigned getNotOutlinedCost() const
Return the size in bytes of the unoutlined sequences.
void accumulate(const MachineInstr &MI)
Adds all register units used, defined or clobbered in MI.
unsigned getNumInstrs() const
Return the number of instructions in this sequence.
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())
unsigned getOutliningCost() const
Return the number of bytes it would take to outline this function.
unsigned getBenefit() const
Return the number of instructions that would be saved by outlining this function. ...
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:1179
MachineFunction * getMF() const
MachineBasicBlock * getMBB() const