MachineOutliner.h revision 360784
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 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 = 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 58public: 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. 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. 104 unsigned getCallOverhead() const { return CallOverhead; } 105 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, 123 unsigned FunctionIdx, unsigned Flags) 124 : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst), 125 MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {} 126 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"); 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. 163struct OutlinedFunction { 164 165public: 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. 183 unsigned getOccurrenceCount() const { return Candidates.size(); } 184 185 /// Return the number of bytes it would take to outline this 186 /// function. 187 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. 195 unsigned getNotOutlinedCost() const { 196 return getOccurrenceCount() * SequenceSize; 197 } 198 199 /// Return the number of instructions that would be saved by outlining 200 /// this function. 201 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. 209 unsigned getNumInstrs() const { return Candidates[0].getLength(); } 210 211 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 220 OutlinedFunction() {} 221}; 222} // namespace outliner 223} // namespace llvm 224 225#endif 226