1 //===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// Contains all data structures shared between the outliner implemented in
12 /// MachineOutliner.cpp and target implementations of the outliner.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_MACHINEOUTLINER_H
17 #define LLVM_MACHINEOUTLINER_H
19 #include "llvm/CodeGen/LiveRegUnits.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/TargetRegisterInfo.h"
22 #include "llvm/CodeGen/LivePhysRegs.h"
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.
34 enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
36 /// An individual sequence of instructions to be replaced with a call to
37 /// an outlined function.
40 /// The start index of this \p Candidate in the instruction list.
43 /// The number of instructions in this \p Candidate.
46 // The first instruction in this \p Candidate.
47 MachineBasicBlock::iterator FirstInst;
49 // The last instruction in this \p Candidate.
50 MachineBasicBlock::iterator LastInst;
52 // The basic block that contains this Candidate.
53 MachineBasicBlock *MBB;
55 /// Cost of calling an outlined function from this point as defined by the
57 unsigned CallOverhead;
60 /// The index of this \p Candidate's \p OutlinedFunction in the list of
61 /// \p OutlinedFunctions.
64 /// Identifier denoting the instructions to emit to call an outlined function
65 /// from this point. Defined by the target.
66 unsigned CallConstructionID;
68 /// Contains physical register liveness information for the MBB containing
69 /// this \p Candidate.
71 /// This is optionally used by the target to calculate more fine-grained
72 /// cost model information.
75 /// Contains the accumulated register liveness information for the
76 /// instructions in this \p Candidate.
78 /// This is optionally used by the target to determine which registers have
79 /// been used across the sequence.
80 LiveRegUnits UsedInSequence;
82 /// Target-specific flags for this Candidate's MBB.
85 /// True if initLRU has been called on this Candidate.
86 bool LRUWasSet = false;
88 /// Return the number of instructions in this Candidate.
89 unsigned getLength() const { return Len; }
91 /// Return the start index of this candidate.
92 unsigned getStartIdx() const { return StartIdx; }
94 /// Return the end index of this candidate.
95 unsigned getEndIdx() const { return StartIdx + Len - 1; }
97 /// Set the CallConstructionID and CallOverhead of this candidate to CID and
99 void setCallInfo(unsigned CID, unsigned CO) {
100 CallConstructionID = CID;
104 /// Returns the call overhead of this candidate if it is in the list.
105 unsigned getCallOverhead() const { return CallOverhead; }
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; }
112 /// The number of instructions that would be saved by outlining every
113 /// candidate of this type.
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;
121 Candidate(unsigned StartIdx, unsigned Len,
122 MachineBasicBlock::iterator &FirstInst,
123 MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
124 unsigned FunctionIdx, unsigned Flags)
125 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
126 MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
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();
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
139 void initLRU(const TargetRegisterInfo &TRI) {
140 assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
141 "Candidate's Machine Function must track liveness");
142 // Only initialize once.
147 LRU.addLiveOuts(*MBB);
149 // Compute liveness from the end of the block up to the beginning of the
150 // outlining candidate.
151 std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
152 [this](MachineInstr &MI) { LRU.stepBackward(MI); });
154 // Walk over the sequence itself and figure out which registers were used
156 UsedInSequence.init(TRI);
157 std::for_each(front(), std::next(back()),
158 [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
162 /// The information necessary to create an outlined function for some
163 /// class of candidate.
164 struct OutlinedFunction {
167 std::vector<Candidate> Candidates;
169 /// The actual outlined function created.
170 /// This is initialized after we go through and create the actual function.
171 MachineFunction *MF = nullptr;
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;
177 /// Target-defined overhead of constructing a frame for this function.
178 unsigned FrameOverhead;
180 /// Target-defined identifier for constructing a frame for this function.
181 unsigned FrameConstructionID;
183 /// Return the number of candidates for this \p OutlinedFunction.
184 unsigned getOccurrenceCount() const { return Candidates.size(); }
186 /// Return the number of bytes it would take to outline this
188 unsigned getOutliningCost() const {
189 unsigned CallOverhead = 0;
190 for (const Candidate &C : Candidates)
191 CallOverhead += C.getCallOverhead();
192 return CallOverhead + SequenceSize + FrameOverhead;
195 /// Return the size in bytes of the unoutlined sequences.
196 unsigned getNotOutlinedCost() const {
197 return getOccurrenceCount() * SequenceSize;
200 /// Return the number of instructions that would be saved by outlining
202 unsigned getBenefit() const {
203 unsigned NotOutlinedCost = getNotOutlinedCost();
204 unsigned OutlinedCost = getOutliningCost();
205 return (NotOutlinedCost < OutlinedCost) ? 0
206 : NotOutlinedCost - OutlinedCost;
209 /// Return the number of instructions in this sequence.
210 unsigned getNumInstrs() const { return Candidates[0].getLength(); }
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)
221 OutlinedFunction() {}
223 } // namespace outliner