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_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 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 public: 59 /// The index of this \p Candidate's \p OutlinedFunction in the list of 60 /// \p OutlinedFunctions. 61 unsigned FunctionIdx = 0; 62 63 /// Identifier denoting the instructions to emit to call an outlined function 64 /// from this point. Defined by the target. 65 unsigned CallConstructionID = 0; 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 81 /// 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 87 /// Return the number of instructions in this Candidate. getLengthCandidate88 unsigned getLength() const { return Len; } 89 90 /// Return the start index of this candidate. getStartIdxCandidate91 unsigned getStartIdx() const { return StartIdx; } 92 93 /// Return the end index of this candidate. getEndIdxCandidate94 unsigned getEndIdx() const { return StartIdx + Len - 1; } 95 96 /// Set the CallConstructionID and CallOverhead of this candidate to CID and 97 /// CO respectively. setCallInfoCandidate98 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. getCallOverheadCandidate104 unsigned getCallOverhead() const { return CallOverhead; } 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, unsigned Flags) 124 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), 125 MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {} 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 // Only initialize once. 142 if (LRUWasSet) 143 return; 144 LRUWasSet = true; 145 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. 163 struct OutlinedFunction { 164 165 public: 166 std::vector<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 /// 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 = 0; 175 176 /// Target-defined overhead of constructing a frame for this function. 177 unsigned FrameOverhead = 0; 178 179 /// Target-defined identifier for constructing a frame for this function. 180 unsigned FrameConstructionID = 0; 181 182 /// Return the number of candidates for this \p OutlinedFunction. getOccurrenceCountOutlinedFunction183 unsigned getOccurrenceCount() const { return Candidates.size(); } 184 185 /// Return the number of bytes it would take to outline this 186 /// function. getOutliningCostOutlinedFunction187 unsigned getOutliningCost() const { 188 unsigned CallOverhead = 0; 189 for (const Candidate &C : Candidates) 190 CallOverhead += C.getCallOverhead(); 191 return CallOverhead + SequenceSize + FrameOverhead; 192 } 193 194 /// Return the size in bytes of the unoutlined sequences. getNotOutlinedCostOutlinedFunction195 unsigned getNotOutlinedCost() const { 196 return getOccurrenceCount() * SequenceSize; 197 } 198 199 /// Return the number of instructions that would be saved by outlining 200 /// this function. getBenefitOutlinedFunction201 unsigned getBenefit() const { 202 unsigned NotOutlinedCost = getNotOutlinedCost(); 203 unsigned OutlinedCost = getOutliningCost(); 204 return (NotOutlinedCost < OutlinedCost) ? 0 205 : NotOutlinedCost - OutlinedCost; 206 } 207 208 /// Return the number of instructions in this sequence. getNumInstrsOutlinedFunction209 unsigned getNumInstrs() const { return Candidates[0].getLength(); } 210 OutlinedFunctionOutlinedFunction211 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; 218 } 219 OutlinedFunctionOutlinedFunction220 OutlinedFunction() {} 221 }; 222 } // namespace outliner 223 } // namespace llvm 224 225 #endif 226