LLVM  9.0.0svn
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_MACHINEOUTLINER_H
16 #define LLVM_MACHINEOUTLINER_H
17 
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;
41 
42  /// The number of instructions in this \p Candidate.
43  unsigned Len;
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;
53 
54  /// Cost of calling an outlined function from this point as defined by the
55  /// target.
56  unsigned CallOverhead;
57 
58 public:
59  /// The index of this \p Candidate's \p OutlinedFunction in the list of
60  /// \p OutlinedFunctions.
61  unsigned FunctionIdx;
62 
63  /// Identifier denoting the instructions to emit to call an outlined function
64  /// from this point. Defined by the target.
66 
67  /// Contains physical register liveness information for the MBB containing
68  /// this \p Candidate.
69  ///
70  /// This is optionally used by the target to calculate more fine-grained
71  /// cost model information.
73 
74  /// Contains the accumulated register liveness information for the
75  /// instructions in this \p Candidate.
76  ///
77  /// This is optionally used by the target to determine which registers have
78  /// been used across the sequence.
80 
81  /// Target-specific flags for this Candidate's MBB.
82  unsigned Flags = 0x0;
83 
84  /// True if initLRU has been called on this Candidate.
85  bool LRUWasSet = false;
86 
87  /// Return the number of instructions in this Candidate.
88  unsigned getLength() const { return Len; }
89 
90  /// Return the start index of this candidate.
91  unsigned getStartIdx() const { return StartIdx; }
92 
93  /// Return the end index of this candidate.
94  unsigned getEndIdx() const { return StartIdx + Len - 1; }
95 
96  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
97  /// CO respectively.
98  void setCallInfo(unsigned CID, unsigned CO) {
99  CallConstructionID = CID;
100  CallOverhead = CO;
101  }
102 
103  /// Returns the call overhead of this candidate if it is in the list.
104  unsigned getCallOverhead() const { return CallOverhead; }
105 
106  MachineBasicBlock::iterator &front() { return FirstInst; }
107  MachineBasicBlock::iterator &back() { return LastInst; }
108  MachineFunction *getMF() const { return MBB->getParent(); }
109  MachineBasicBlock *getMBB() const { return MBB; }
110 
111  /// The number of instructions that would be saved by outlining every
112  /// candidate of this type.
113  ///
114  /// This is a fixed value which is not updated during the candidate pruning
115  /// process. It is only used for deciding which candidate to keep if two
116  /// candidates overlap. The true benefit is stored in the OutlinedFunction
117  /// for some given candidate.
118  unsigned Benefit = 0;
119 
120  Candidate(unsigned StartIdx, unsigned Len,
121  MachineBasicBlock::iterator &FirstInst,
123  unsigned FunctionIdx, unsigned Flags)
124  : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
125  MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
127 
128  /// Used to ensure that \p Candidates are outlined in an order that
129  /// preserves the start and end indices of other \p Candidates.
130  bool operator<(const Candidate &RHS) const {
131  return getStartIdx() > RHS.getStartIdx();
132  }
133 
134  /// Compute the registers that are live across this Candidate.
135  /// Used by targets that need this information for cost model calculation.
136  /// If a target does not need this information, then this should not be
137  /// called.
140  "Candidate's Machine Function must track liveness");
141  // Only initialize once.
142  if (LRUWasSet)
143  return;
144  LRUWasSet = true;
145  LRU.init(TRI);
146  LRU.addLiveOuts(*MBB);
147 
148  // Compute liveness from the end of the block up to the beginning of the
149  // outlining candidate.
151  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
152 
153  // Walk over the sequence itself and figure out which registers were used
154  // in the sequence.
155  UsedInSequence.init(TRI);
156  std::for_each(front(), std::next(back()),
157  [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
158  }
159 };
160 
161 /// The information necessary to create an outlined function for some
162 /// class of candidate.
164 
165 public:
166  std::vector<Candidate> Candidates;
167 
168  /// The actual outlined function created.
169  /// This is initialized after we go through and create the actual function.
170  MachineFunction *MF = nullptr;
171 
172  /// Represents the size of a sequence in bytes. (Some instructions vary
173  /// widely in size, so just counting the instructions isn't very useful.)
174  unsigned SequenceSize;
175 
176  /// Target-defined overhead of constructing a frame for this function.
177  unsigned FrameOverhead;
178 
179  /// Target-defined identifier for constructing a frame for this function.
181 
182  /// Return the number of candidates for this \p OutlinedFunction.
183  unsigned getOccurrenceCount() const { return Candidates.size(); }
184 
185  /// Return the number of bytes it would take to outline this
186  /// function.
187  unsigned getOutliningCost() const {
188  unsigned CallOverhead = 0;
189  for (const Candidate &C : Candidates)
190  CallOverhead += C.getCallOverhead();
191  return CallOverhead + SequenceSize + FrameOverhead;
192  }
193 
194  /// Return the size in bytes of the unoutlined sequences.
195  unsigned getNotOutlinedCost() const {
196  return getOccurrenceCount() * SequenceSize;
197  }
198 
199  /// Return the number of instructions that would be saved by outlining
200  /// this function.
201  unsigned getBenefit() const {
202  unsigned NotOutlinedCost = getNotOutlinedCost();
203  unsigned OutlinedCost = getOutliningCost();
204  return (NotOutlinedCost < OutlinedCost) ? 0
205  : NotOutlinedCost - OutlinedCost;
206  }
207 
208  /// Return the number of instructions in this sequence.
209  unsigned getNumInstrs() const { return Candidates[0].getLength(); }
210 
211  OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
212  unsigned FrameOverhead, unsigned FrameConstructionID)
213  : Candidates(Candidates), SequenceSize(SequenceSize),
214  FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) {
215  const unsigned B = getBenefit();
216  for (Candidate &C : Candidates)
217  C.Benefit = B;
218  }
219 
221 };
222 } // namespace outliner
223 } // namespace llvm
224 
225 #endif
uint64_t CallInst * C
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:74
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:63
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:30
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:1178
MachineFunction * getMF() const
MachineBasicBlock * getMBB() const