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 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. getLengthCandidate86 unsigned getLength() const { return Len; } 87 88 /// Return the start index of this candidate. getStartIdxCandidate89 unsigned getStartIdx() const { return StartIdx; } 90 91 /// Return the end index of this candidate. getEndIdxCandidate92 unsigned getEndIdx() const { return StartIdx + Len - 1; } 93 94 /// Set the CallConstructionID and CallOverhead of this candidate to CID and 95 /// CO respectively. setCallInfoCandidate96 void setCallInfo(unsigned CID, unsigned CO) { 97 CallConstructionID = CID; 98 CallOverhead = CO; 99 } 100 101 /// Returns the call overhead of this candidate if it is in the list. getCallOverheadCandidate102 unsigned getCallOverhead() const { 103 return InCandidateList ? CallOverhead : 0; 104 } 105 frontCandidate106 MachineBasicBlock::iterator &front() { return FirstInst; } backCandidate107 MachineBasicBlock::iterator &back() { return LastInst; } getMFCandidate108 MachineFunction *getMF() const { return MBB->getParent(); } getMBBCandidate109 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 CandidateCandidate120 Candidate(unsigned StartIdx, unsigned Len, 121 MachineBasicBlock::iterator &FirstInst, 122 MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB, 123 unsigned FunctionIdx) 124 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), 125 MBB(MBB), FunctionIdx(FunctionIdx) {} CandidateCandidate126 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. initLRUCandidate138 void initLRU(const TargetRegisterInfo &TRI) { 139 assert(MBB->getParent()->getRegInfo().tracksLiveness() && 140 "Candidate's Machine Function must track liveness"); 141 LRU.init(TRI); 142 LRU.addLiveOuts(*MBB); 143 144 // Compute liveness from the end of the block up to the beginning of the 145 // outlining candidate. 146 std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(), 147 [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 UsedInSequence.init(TRI); 152 std::for_each(front(), std::next(back()), 153 [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); }); 154 } 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. getOccurrenceCountOutlinedFunction190 unsigned getOccurrenceCount() { return OccurrenceCount; } 191 192 /// Decrement the occurrence count of this OutlinedFunction and return the 193 /// new count. decrementOutlinedFunction194 unsigned decrement() { 195 assert(OccurrenceCount > 0 && "Can't decrement an empty function!"); 196 OccurrenceCount--; 197 return getOccurrenceCount(); 198 } 199 200 /// Return the number of bytes it would take to outline this 201 /// function. getOutliningCostOutlinedFunction202 unsigned getOutliningCost() { 203 unsigned CallOverhead = 0; 204 for (std::shared_ptr<Candidate> &C : Candidates) 205 CallOverhead += C->getCallOverhead(); 206 return CallOverhead + SequenceSize + FrameOverhead; 207 } 208 209 /// Return the size in bytes of the unoutlined sequences. getNotOutlinedCostOutlinedFunction210 unsigned getNotOutlinedCost() { return OccurrenceCount * SequenceSize; } 211 212 /// Return the number of instructions that would be saved by outlining 213 /// this function. getBenefitOutlinedFunction214 unsigned getBenefit() { 215 unsigned NotOutlinedCost = getNotOutlinedCost(); 216 unsigned OutlinedCost = getOutliningCost(); 217 return (NotOutlinedCost < OutlinedCost) ? 0 218 : NotOutlinedCost - OutlinedCost; 219 } 220 OutlinedFunctionOutlinedFunction221 OutlinedFunction(std::vector<Candidate> &Cands, 222 unsigned SequenceSize, unsigned FrameOverhead, 223 unsigned FrameConstructionID) 224 : SequenceSize(SequenceSize), FrameOverhead(FrameOverhead), 225 FrameConstructionID(FrameConstructionID) { 226 OccurrenceCount = Cands.size(); 227 for (Candidate &C : Cands) 228 Candidates.push_back(std::make_shared<outliner::Candidate>(C)); 229 230 unsigned B = getBenefit(); 231 for (std::shared_ptr<Candidate> &C : Candidates) 232 C->Benefit = B; 233 } 234 OutlinedFunctionOutlinedFunction235 OutlinedFunction() {} 236 }; 237 } // namespace outliner 238 } // namespace llvm 239 240 #endif 241