Line data Source code
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 :
19 : #include "llvm/CodeGen/LiveRegUnits.h"
20 : #include "llvm/CodeGen/MachineFunction.h"
21 : #include "llvm/CodeGen/TargetRegisterInfo.h"
22 : #include "llvm/CodeGen/LivePhysRegs.h"
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.
34 : enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
35 :
36 : /// An individual sequence of instructions to be replaced with a call to
37 : /// an outlined function.
38 862 : 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.
47 : MachineBasicBlock::iterator FirstInst;
48 :
49 : // The last instruction in this \p Candidate.
50 : MachineBasicBlock::iterator LastInst;
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.
69 : unsigned CallConstructionID;
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.
76 : LiveRegUnits LRU;
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.
83 : LiveRegUnits UsedInSequence;
84 :
85 : /// Return the number of instructions in this Candidate.
86 : unsigned getLength() const { return Len; }
87 :
88 : /// Return the start index of this candidate.
89 0 : unsigned getStartIdx() const { return StartIdx; }
90 :
91 : /// Return the end index of this candidate.
92 0 : unsigned getEndIdx() const { return StartIdx + Len - 1; }
93 :
94 : /// Set the CallConstructionID and CallOverhead of this candidate to CID and
95 : /// CO respectively.
96 0 : void setCallInfo(unsigned CID, unsigned CO) {
97 481 : CallConstructionID = CID;
98 481 : CallOverhead = CO;
99 0 : }
100 :
101 : /// Returns the call overhead of this candidate if it is in the list.
102 0 : unsigned getCallOverhead() const {
103 0 : return InCandidateList ? CallOverhead : 0;
104 : }
105 :
106 205 : MachineBasicBlock::iterator &front() { return FirstInst; }
107 : MachineBasicBlock::iterator &back() { return LastInst; }
108 254 : MachineFunction *getMF() const { return MBB->getParent(); }
109 0 : 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,
122 : MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
123 : unsigned FunctionIdx)
124 503 : : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
125 1006 : MBB(MBB), FunctionIdx(FunctionIdx) {}
126 : Candidate() {}
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 0 : 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.
138 451 : void initLRU(const TargetRegisterInfo &TRI) {
139 : assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
140 : "Candidate's Machine Function must track liveness");
141 451 : LRU.init(TRI);
142 451 : LRU.addLiveOuts(*MBB);
143 :
144 : // Compute liveness from the end of the block up to the beginning of the
145 : // outlining candidate.
146 451 : std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
147 4723 : [this](MachineInstr &MI) { LRU.stepBackward(MI); });
148 :
149 : // Walk over the sequence itself and figure out which registers were used
150 : // in the sequence.
151 451 : UsedInSequence.init(TRI);
152 : std::for_each(front(), std::next(back()),
153 2539 : [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
154 451 : }
155 : };
156 :
157 : /// The information necessary to create an outlined function for some
158 : /// class of candidate.
159 : struct OutlinedFunction {
160 :
161 : private:
162 : /// The number of candidates for this \p OutlinedFunction.
163 : unsigned OccurrenceCount = 0;
164 :
165 : public:
166 : std::vector<std::shared_ptr<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 : /// A number assigned to this function which appears at the end of its name.
173 : unsigned Name;
174 :
175 : /// The sequence of integers corresponding to the instructions in this
176 : /// function.
177 : std::vector<unsigned> Sequence;
178 :
179 : /// Represents the size of a sequence in bytes. (Some instructions vary
180 : /// widely in size, so just counting the instructions isn't very useful.)
181 : unsigned SequenceSize;
182 :
183 : /// Target-defined overhead of constructing a frame for this function.
184 : unsigned FrameOverhead;
185 :
186 : /// Target-defined identifier for constructing a frame for this function.
187 : unsigned FrameConstructionID;
188 :
189 : /// Return the number of candidates for this \p OutlinedFunction.
190 0 : unsigned getOccurrenceCount() { return OccurrenceCount; }
191 :
192 : /// Decrement the occurrence count of this OutlinedFunction and return the
193 : /// new count.
194 0 : unsigned decrement() {
195 : assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
196 0 : OccurrenceCount--;
197 0 : return getOccurrenceCount();
198 : }
199 :
200 : /// Return the number of bytes it would take to outline this
201 : /// function.
202 : unsigned getOutliningCost() {
203 : unsigned CallOverhead = 0;
204 3213 : for (std::shared_ptr<Candidate> &C : Candidates)
205 4547 : CallOverhead += C->getCallOverhead();
206 858 : return CallOverhead + SequenceSize + FrameOverhead;
207 : }
208 :
209 : /// Return the size in bytes of the unoutlined sequences.
210 858 : unsigned getNotOutlinedCost() { return OccurrenceCount * SequenceSize; }
211 :
212 : /// Return the number of instructions that would be saved by outlining
213 : /// this function.
214 858 : unsigned getBenefit() {
215 858 : unsigned NotOutlinedCost = getNotOutlinedCost();
216 : unsigned OutlinedCost = getOutliningCost();
217 858 : return (NotOutlinedCost < OutlinedCost) ? 0
218 858 : : NotOutlinedCost - OutlinedCost;
219 : }
220 :
221 200 : OutlinedFunction(std::vector<Candidate> &Cands,
222 : unsigned SequenceSize, unsigned FrameOverhead,
223 : unsigned FrameConstructionID)
224 200 : : SequenceSize(SequenceSize), FrameOverhead(FrameOverhead),
225 400 : FrameConstructionID(FrameConstructionID) {
226 400 : OccurrenceCount = Cands.size();
227 681 : for (Candidate &C : Cands)
228 481 : Candidates.push_back(std::make_shared<outliner::Candidate>(C));
229 :
230 200 : unsigned B = getBenefit();
231 681 : for (std::shared_ptr<Candidate> &C : Candidates)
232 481 : C->Benefit = B;
233 200 : }
234 :
235 10 : OutlinedFunction() {}
236 : };
237 : } // namespace outliner
238 : } // namespace llvm
239 :
240 : #endif
|
