blob: 377df4e18a2a0063bb45d0195031d205111b8614 [file] [log] [blame]
Andrew Scullcdfcccc2018-10-05 20:58:37 +01001//===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
2//
Andrew Walbran16937d02019-10-22 13:54:20 +01003// 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
Andrew Scullcdfcccc2018-10-05 20:58:37 +01006//
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
18#include "llvm/CodeGen/LiveRegUnits.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/TargetRegisterInfo.h"
21#include "llvm/CodeGen/LivePhysRegs.h"
22
23namespace llvm {
24namespace 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.
33enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
34
35/// An individual sequence of instructions to be replaced with a call to
36/// an outlined function.
37struct Candidate {
38private:
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.
46 MachineBasicBlock::iterator FirstInst;
47
48 // The last instruction in this \p Candidate.
49 MachineBasicBlock::iterator LastInst;
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
58public:
59 /// The index of this \p Candidate's \p OutlinedFunction in the list of
60 /// \p OutlinedFunctions.
61 unsigned FunctionIdx;
62
Andrew Scullcdfcccc2018-10-05 20:58:37 +010063 /// Identifier denoting the instructions to emit to call an outlined function
64 /// from this point. Defined by the target.
65 unsigned CallConstructionID;
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.
72 LiveRegUnits LRU;
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.
79 LiveRegUnits UsedInSequence;
80
Andrew Walbran16937d02019-10-22 13:54:20 +010081 /// 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
Andrew Scullcdfcccc2018-10-05 20:58:37 +010087 /// 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.
Andrew Walbran16937d02019-10-22 13:54:20 +0100104 unsigned getCallOverhead() const { return CallOverhead; }
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100105
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,
122 MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
Andrew Walbran16937d02019-10-22 13:54:20 +0100123 unsigned FunctionIdx, unsigned Flags)
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100124 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
Andrew Walbran16937d02019-10-22 13:54:20 +0100125 MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100126 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 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 void initLRU(const TargetRegisterInfo &TRI) {
139 assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
140 "Candidate's Machine Function must track liveness");
Andrew Walbran16937d02019-10-22 13:54:20 +0100141 // Only initialize once.
142 if (LRUWasSet)
143 return;
144 LRUWasSet = true;
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100145 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.
150 std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
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.
163struct OutlinedFunction {
164
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100165public:
Andrew Walbran16937d02019-10-22 13:54:20 +0100166 std::vector<Candidate> Candidates;
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100167
168 /// The actual outlined function created.
169 /// This is initialized after we go through and create the actual function.
170 MachineFunction *MF = nullptr;
171
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100172 /// 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.
180 unsigned FrameConstructionID;
181
182 /// Return the number of candidates for this \p OutlinedFunction.
Andrew Walbran16937d02019-10-22 13:54:20 +0100183 unsigned getOccurrenceCount() const { return Candidates.size(); }
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100184
185 /// Return the number of bytes it would take to outline this
186 /// function.
Andrew Walbran16937d02019-10-22 13:54:20 +0100187 unsigned getOutliningCost() const {
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100188 unsigned CallOverhead = 0;
Andrew Walbran16937d02019-10-22 13:54:20 +0100189 for (const Candidate &C : Candidates)
190 CallOverhead += C.getCallOverhead();
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100191 return CallOverhead + SequenceSize + FrameOverhead;
192 }
193
194 /// Return the size in bytes of the unoutlined sequences.
Andrew Walbran16937d02019-10-22 13:54:20 +0100195 unsigned getNotOutlinedCost() const {
196 return getOccurrenceCount() * SequenceSize;
197 }
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100198
199 /// Return the number of instructions that would be saved by outlining
200 /// this function.
Andrew Walbran16937d02019-10-22 13:54:20 +0100201 unsigned getBenefit() const {
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100202 unsigned NotOutlinedCost = getNotOutlinedCost();
203 unsigned OutlinedCost = getOutliningCost();
204 return (NotOutlinedCost < OutlinedCost) ? 0
205 : NotOutlinedCost - OutlinedCost;
206 }
207
Andrew Walbran16937d02019-10-22 13:54:20 +0100208 /// Return the number of instructions in this sequence.
209 unsigned getNumInstrs() const { return Candidates[0].getLength(); }
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100210
Andrew Walbran16937d02019-10-22 13:54:20 +0100211 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;
Andrew Scullcdfcccc2018-10-05 20:58:37 +0100218 }
219
220 OutlinedFunction() {}
221};
222} // namespace outliner
223} // namespace llvm
224
225#endif