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_CODEGEN_MACHINEOUTLINER_H 16 #define LLVM_CODEGEN_MACHINEOUTLINER_H 17 18 #include "llvm/CodeGen/LiveRegUnits.h" 19 #include "llvm/CodeGen/MachineFunction.h" 20 #include "llvm/CodeGen/MachineRegisterInfo.h" 21 #include <initializer_list> 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. 33 enum InstrType { Legal, LegalTerminator, Illegal, Invisible }; 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 = 0; 41 42 /// The number of instructions in this \p Candidate. 43 unsigned Len = 0; 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 = nullptr; 53 54 /// Cost of calling an outlined function from this point as defined by the 55 /// target. 56 unsigned CallOverhead = 0; 57 58 /// Liveness information for this Candidate. Tracks from the end of the 59 /// block containing this Candidate to the beginning of its sequence. 60 /// 61 /// Optional. Can be used to fine-tune the cost model, or fine-tune legality 62 /// decisions. 63 LiveRegUnits FromEndOfBlockToStartOfSeq; 64 65 /// Liveness information restricted to this Candidate's instruction sequence. 66 /// 67 /// Optional. Can be used to fine-tune the cost model, or fine-tune legality 68 /// decisions. 69 LiveRegUnits InSeq; 70 71 /// True if FromEndOfBlockToStartOfSeq has been initialized. 72 bool FromEndOfBlockToStartOfSeqWasSet = false; 73 74 /// True if InSeq has been initialized. 75 bool InSeqWasSet = false; 76 77 /// Populate FromEndOfBlockToStartOfSeq with liveness information. 78 void initFromEndOfBlockToStartOfSeq(const TargetRegisterInfo &TRI) { 79 assert(MBB->getParent()->getRegInfo().tracksLiveness() && 80 "Candidate's Machine Function must track liveness"); 81 // Only initialize once. 82 if (FromEndOfBlockToStartOfSeqWasSet) 83 return; 84 FromEndOfBlockToStartOfSeqWasSet = true; 85 FromEndOfBlockToStartOfSeq.init(TRI); 86 FromEndOfBlockToStartOfSeq.addLiveOuts(*MBB); 87 // Compute liveness from the end of the block up to the beginning of the 88 // outlining candidate. 89 for (auto &MI : make_range(MBB->rbegin(), 90 (MachineBasicBlock::reverse_iterator)begin())) 91 FromEndOfBlockToStartOfSeq.stepBackward(MI); 92 } 93 94 /// Populate InSeq with liveness information. 95 void initInSeq(const TargetRegisterInfo &TRI) { 96 assert(MBB->getParent()->getRegInfo().tracksLiveness() && 97 "Candidate's Machine Function must track liveness"); 98 // Only initialize once. 99 if (InSeqWasSet) 100 return; 101 InSeqWasSet = true; 102 InSeq.init(TRI); 103 for (auto &MI : *this) 104 InSeq.accumulate(MI); 105 } 106 107 public: 108 /// The index of this \p Candidate's \p OutlinedFunction in the list of 109 /// \p OutlinedFunctions. 110 unsigned FunctionIdx = 0; 111 112 /// Identifier denoting the instructions to emit to call an outlined function 113 /// from this point. Defined by the target. 114 unsigned CallConstructionID = 0; 115 116 /// Target-specific flags for this Candidate's MBB. 117 unsigned Flags = 0x0; 118 119 /// Return the number of instructions in this Candidate. 120 unsigned getLength() const { return Len; } 121 122 /// Return the start index of this candidate. 123 unsigned getStartIdx() const { return StartIdx; } 124 125 /// Return the end index of this candidate. 126 unsigned getEndIdx() const { return StartIdx + Len - 1; } 127 128 /// Set the CallConstructionID and CallOverhead of this candidate to CID and 129 /// CO respectively. 130 void setCallInfo(unsigned CID, unsigned CO) { 131 CallConstructionID = CID; 132 CallOverhead = CO; 133 } 134 135 /// Returns the call overhead of this candidate if it is in the list. 136 unsigned getCallOverhead() const { return CallOverhead; } 137 138 MachineBasicBlock::iterator begin() { return FirstInst; } 139 MachineBasicBlock::iterator end() { return std::next(LastInst); } 140 141 MachineInstr &front() { return *FirstInst; } 142 MachineInstr &back() { return *LastInst; } 143 MachineFunction *getMF() const { return MBB->getParent(); } 144 MachineBasicBlock *getMBB() const { return MBB; } 145 146 /// \returns True if \p Reg is available from the end of the block to the 147 /// beginning of the sequence. 148 /// 149 /// This query considers the following range: 150 /// 151 /// in_seq_1 152 /// in_seq_2 153 /// ... 154 /// in_seq_n 155 /// not_in_seq_1 156 /// ... 157 /// <end of block> 158 bool isAvailableAcrossAndOutOfSeq(Register Reg, 159 const TargetRegisterInfo &TRI) { 160 if (!FromEndOfBlockToStartOfSeqWasSet) 161 initFromEndOfBlockToStartOfSeq(TRI); 162 return FromEndOfBlockToStartOfSeq.available(Reg); 163 } 164 165 /// \returns True if `isAvailableAcrossAndOutOfSeq` fails for any register 166 /// in \p Regs. 167 bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list<Register> Regs, 168 const TargetRegisterInfo &TRI) { 169 if (!FromEndOfBlockToStartOfSeqWasSet) 170 initFromEndOfBlockToStartOfSeq(TRI); 171 return any_of(Regs, [&](Register Reg) { 172 return !FromEndOfBlockToStartOfSeq.available(Reg); 173 }); 174 } 175 176 /// \returns True if \p Reg is available within the sequence itself. 177 /// 178 /// This query considers the following range: 179 /// 180 /// in_seq_1 181 /// in_seq_2 182 /// ... 183 /// in_seq_n 184 bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI) { 185 if (!InSeqWasSet) 186 initInSeq(TRI); 187 return InSeq.available(Reg); 188 } 189 190 /// The number of instructions that would be saved by outlining every 191 /// candidate of this type. 192 /// 193 /// This is a fixed value which is not updated during the candidate pruning 194 /// process. It is only used for deciding which candidate to keep if two 195 /// candidates overlap. The true benefit is stored in the OutlinedFunction 196 /// for some given candidate. 197 unsigned Benefit = 0; 198 199 Candidate(unsigned StartIdx, unsigned Len, 200 MachineBasicBlock::iterator &FirstInst, 201 MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, 202 unsigned FunctionIdx, unsigned Flags) 203 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), 204 MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {} 205 Candidate() = delete; 206 207 /// Used to ensure that \p Candidates are outlined in an order that 208 /// preserves the start and end indices of other \p Candidates. 209 bool operator<(const Candidate &RHS) const { 210 return getStartIdx() > RHS.getStartIdx(); 211 } 212 213 }; 214 215 /// The information necessary to create an outlined function for some 216 /// class of candidate. 217 struct OutlinedFunction { 218 219 public: 220 std::vector<Candidate> Candidates; 221 222 /// The actual outlined function created. 223 /// This is initialized after we go through and create the actual function. 224 MachineFunction *MF = nullptr; 225 226 /// Represents the size of a sequence in bytes. (Some instructions vary 227 /// widely in size, so just counting the instructions isn't very useful.) 228 unsigned SequenceSize = 0; 229 230 /// Target-defined overhead of constructing a frame for this function. 231 unsigned FrameOverhead = 0; 232 233 /// Target-defined identifier for constructing a frame for this function. 234 unsigned FrameConstructionID = 0; 235 236 /// Return the number of candidates for this \p OutlinedFunction. 237 unsigned getOccurrenceCount() const { return Candidates.size(); } 238 239 /// Return the number of bytes it would take to outline this 240 /// function. 241 unsigned getOutliningCost() const { 242 unsigned CallOverhead = 0; 243 for (const Candidate &C : Candidates) 244 CallOverhead += C.getCallOverhead(); 245 return CallOverhead + SequenceSize + FrameOverhead; 246 } 247 248 /// Return the size in bytes of the unoutlined sequences. 249 unsigned getNotOutlinedCost() const { 250 return getOccurrenceCount() * SequenceSize; 251 } 252 253 /// Return the number of instructions that would be saved by outlining 254 /// this function. 255 unsigned getBenefit() const { 256 unsigned NotOutlinedCost = getNotOutlinedCost(); 257 unsigned OutlinedCost = getOutliningCost(); 258 return (NotOutlinedCost < OutlinedCost) ? 0 259 : NotOutlinedCost - OutlinedCost; 260 } 261 262 /// Return the number of instructions in this sequence. 263 unsigned getNumInstrs() const { return Candidates[0].getLength(); } 264 265 OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize, 266 unsigned FrameOverhead, unsigned FrameConstructionID) 267 : Candidates(Candidates), SequenceSize(SequenceSize), 268 FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) { 269 const unsigned B = getBenefit(); 270 for (Candidate &C : Candidates) 271 C.Benefit = B; 272 } 273 274 OutlinedFunction() = delete; 275 }; 276 } // namespace outliner 277 } // namespace llvm 278 279 #endif 280