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/LivePhysRegs.h" 19 #include "llvm/CodeGen/LiveRegUnits.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineRegisterInfo.h" 22 #include "llvm/CodeGen/TargetRegisterInfo.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 = 0; 42 43 /// The number of instructions in this \p Candidate. 44 unsigned Len = 0; 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 = nullptr; 54 55 /// Cost of calling an outlined function from this point as defined by the 56 /// target. 57 unsigned CallOverhead = 0; 58 59 public: 60 /// The index of this \p Candidate's \p OutlinedFunction in the list of 61 /// \p OutlinedFunctions. 62 unsigned FunctionIdx = 0; 63 64 /// Identifier denoting the instructions to emit to call an outlined function 65 /// from this point. Defined by the target. 66 unsigned CallConstructionID = 0; 67 68 /// Contains physical register liveness information for the MBB containing 69 /// this \p Candidate. 70 /// 71 /// This is optionally used by the target to calculate more fine-grained 72 /// cost model information. 73 LiveRegUnits LRU; 74 75 /// Contains the accumulated register liveness information for the 76 /// instructions in this \p Candidate. 77 /// 78 /// This is optionally used by the target to determine which registers have 79 /// been used across the sequence. 80 LiveRegUnits UsedInSequence; 81 82 /// Target-specific flags for this Candidate's MBB. 83 unsigned Flags = 0x0; 84 85 /// True if initLRU has been called on this Candidate. 86 bool LRUWasSet = false; 87 88 /// Return the number of instructions in this Candidate. getLengthCandidate89 unsigned getLength() const { return Len; } 90 91 /// Return the start index of this candidate. getStartIdxCandidate92 unsigned getStartIdx() const { return StartIdx; } 93 94 /// Return the end index of this candidate. getEndIdxCandidate95 unsigned getEndIdx() const { return StartIdx + Len - 1; } 96 97 /// Set the CallConstructionID and CallOverhead of this candidate to CID and 98 /// CO respectively. setCallInfoCandidate99 void setCallInfo(unsigned CID, unsigned CO) { 100 CallConstructionID = CID; 101 CallOverhead = CO; 102 } 103 104 /// Returns the call overhead of this candidate if it is in the list. getCallOverheadCandidate105 unsigned getCallOverhead() const { return CallOverhead; } 106 frontCandidate107 MachineBasicBlock::iterator &front() { return FirstInst; } backCandidate108 MachineBasicBlock::iterator &back() { return LastInst; } getMFCandidate109 MachineFunction *getMF() const { return MBB->getParent(); } getMBBCandidate110 MachineBasicBlock *getMBB() const { return MBB; } 111 112 /// The number of instructions that would be saved by outlining every 113 /// candidate of this type. 114 /// 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; 120 CandidateCandidate121 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) {} CandidateCandidate127 Candidate() {} 128 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(); 133 } 134 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 138 /// called. initLRUCandidate139 void initLRU(const TargetRegisterInfo &TRI) { 140 assert(MBB->getParent()->getRegInfo().tracksLiveness() && 141 "Candidate's Machine Function must track liveness"); 142 // Only initialize once. 143 if (LRUWasSet) 144 return; 145 LRUWasSet = true; 146 LRU.init(TRI); 147 LRU.addLiveOuts(*MBB); 148 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); }); 153 154 // Walk over the sequence itself and figure out which registers were used 155 // in the sequence. 156 UsedInSequence.init(TRI); 157 std::for_each(front(), std::next(back()), 158 [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); }); 159 } 160 }; 161 162 /// The information necessary to create an outlined function for some 163 /// class of candidate. 164 struct OutlinedFunction { 165 166 public: 167 std::vector<Candidate> Candidates; 168 169 /// The actual outlined function created. 170 /// This is initialized after we go through and create the actual function. 171 MachineFunction *MF = nullptr; 172 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 = 0; 176 177 /// Target-defined overhead of constructing a frame for this function. 178 unsigned FrameOverhead = 0; 179 180 /// Target-defined identifier for constructing a frame for this function. 181 unsigned FrameConstructionID = 0; 182 183 /// Return the number of candidates for this \p OutlinedFunction. getOccurrenceCountOutlinedFunction184 unsigned getOccurrenceCount() const { return Candidates.size(); } 185 186 /// Return the number of bytes it would take to outline this 187 /// function. getOutliningCostOutlinedFunction188 unsigned getOutliningCost() const { 189 unsigned CallOverhead = 0; 190 for (const Candidate &C : Candidates) 191 CallOverhead += C.getCallOverhead(); 192 return CallOverhead + SequenceSize + FrameOverhead; 193 } 194 195 /// Return the size in bytes of the unoutlined sequences. getNotOutlinedCostOutlinedFunction196 unsigned getNotOutlinedCost() const { 197 return getOccurrenceCount() * SequenceSize; 198 } 199 200 /// Return the number of instructions that would be saved by outlining 201 /// this function. getBenefitOutlinedFunction202 unsigned getBenefit() const { 203 unsigned NotOutlinedCost = getNotOutlinedCost(); 204 unsigned OutlinedCost = getOutliningCost(); 205 return (NotOutlinedCost < OutlinedCost) ? 0 206 : NotOutlinedCost - OutlinedCost; 207 } 208 209 /// Return the number of instructions in this sequence. getNumInstrsOutlinedFunction210 unsigned getNumInstrs() const { return Candidates[0].getLength(); } 211 OutlinedFunctionOutlinedFunction212 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) 218 C.Benefit = B; 219 } 220 OutlinedFunctionOutlinedFunction221 OutlinedFunction() {} 222 }; 223 } // namespace outliner 224 } // namespace llvm 225 226 #endif 227