1 /*========================== begin_copyright_notice ============================ 2 3 Copyright (C) 2017-2021 Intel Corporation 4 5 SPDX-License-Identifier: MIT 6 7 ============================= end_copyright_notice ===========================*/ 8 9 /*========================== begin_copyright_notice ============================ 10 11 This file is distributed under the University of Illinois Open Source License. 12 See LICENSE.TXT for details. 13 14 ============================= end_copyright_notice ===========================*/ 15 16 // Estimate the register pressure at a program point. 17 18 #pragma once 19 20 #include "common/LLVMWarningsPush.hpp" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/IR/BasicBlock.h" 23 #include "llvm/IR/Value.h" 24 #include "llvm/Pass.h" 25 #include <llvm/IR/InstVisitor.h> 26 #include "llvm/Analysis/LoopInfo.h" 27 #include <llvmWrapper/IR/DerivedTypes.h> 28 #include "common/LLVMWarningsPop.hpp" 29 #include "Compiler/IGCPassSupport.h" 30 #include "Compiler/CISACodeGen/WIAnalysis.hpp" 31 #include "Probe/Assertion.h" 32 33 namespace IGC 34 { 35 constexpr unsigned int SIMD_PRESSURE_MULTIPLIER = 8; 36 constexpr unsigned int OVERALL_PRESSURE_UPBOUND = 512; 37 38 class RegisterPressureEstimate : public llvm::FunctionPass 39 { 40 public: 41 static char ID; RegisterPressureEstimate()42 RegisterPressureEstimate() 43 : FunctionPass(ID), m_DL(nullptr), m_pFunc(nullptr), LI(nullptr), 44 WI(nullptr), m_available(false), MaxAssignedNumber(0) 45 { 46 initializeRegisterPressureEstimatePass(*llvm::PassRegistry::getPassRegistry()); 47 } 48 49 /// @brief Provides name of pass getPassName() const50 virtual llvm::StringRef getPassName() const override 51 { 52 return "RegisterPressureEstimate"; 53 } 54 55 void getAnalysisUsage(llvm::AnalysisUsage& AU) const override; 56 bool runOnFunction(llvm::Function& F) override; 57 doFinalization(llvm::Module & F)58 bool doFinalization(llvm::Module& F) override 59 { 60 for (auto Item : m_pLiveRangePool) 61 delete Item; 62 m_pLiveRangePool.clear(); 63 return false; 64 } 65 /// \brief Describe a value is live at Begin and dead right after End. 66 struct Segment 67 { 68 unsigned Begin; 69 unsigned End; SegmentIGC::RegisterPressureEstimate::Segment70 Segment() {} SegmentIGC::RegisterPressureEstimate::Segment71 Segment(unsigned Begin, unsigned End) : Begin(Begin), End(End) {} operator <IGC::RegisterPressureEstimate::Segment72 bool operator<(const Segment& Other) const 73 { 74 if (Begin != Other.Begin) 75 { 76 return Begin < Other.Begin; 77 } 78 return End < Other.End; 79 } 80 }; 81 82 /// \brief A live range consists of a list of live segments. 83 struct LiveRange 84 { 85 /// Empty live range. LiveRangeIGC::RegisterPressureEstimate::LiveRange86 LiveRange() {} 87 88 LiveRange(const LiveRange&) = delete; 89 90 /// \brief Shorten a segment. 91 void setBegin(unsigned B); 92 93 /// \brief Append a new segment. addSegmentIGC::RegisterPressureEstimate::LiveRange94 void addSegment(unsigned B, unsigned E) 95 { 96 if (B < E) 97 { 98 Segments.push_back(Segment(B, E)); 99 } 100 } 101 102 /// \brief Sort segments and merge them. 103 void sortAndMerge(); 104 105 /// \brief Check whether N is contained in this live range. containsIGC::RegisterPressureEstimate::LiveRange106 bool contains(unsigned N) const 107 { 108 // Segments are sorted. 109 for (auto& Seg : Segments) 110 { 111 if (N < Seg.Begin) 112 { 113 return false; 114 } 115 if (N < Seg.End) 116 { 117 return true; 118 } 119 } 120 // N is out of range. 121 return false; 122 } 123 124 void dump() const; 125 void print(llvm::raw_ostream& OS) const; 126 llvm::SmallVector<Segment, 8> Segments; 127 }; 128 getOrCreateLiveRange(llvm::Value * V)129 LiveRange* getOrCreateLiveRange(llvm::Value* V) 130 { 131 auto Iter = m_pLiveRanges.find(V); 132 if (Iter != m_pLiveRanges.end()) 133 { 134 return Iter->second; 135 } 136 137 auto Result = m_pLiveRanges.insert(std::make_pair(V, createLiveRange())); 138 return Result.first->second; 139 } 140 getLiveRangeOrNull(llvm::Value * V)141 LiveRange* getLiveRangeOrNull(llvm::Value* V) 142 { 143 auto Iter = m_pLiveRanges.find(V); 144 if (Iter != m_pLiveRanges.end()) 145 { 146 return Iter->second; 147 } 148 return nullptr; 149 } 150 createLiveRange(llvm::Value * V)151 void createLiveRange(llvm::Value* V) 152 { 153 IGC_ASSERT(!m_pLiveRanges.count(V)); 154 m_pLiveRanges[V] = createLiveRange(); 155 } 156 157 /// \brief Cleanup live ranges. mergeLiveRanges()158 void mergeLiveRanges() 159 { 160 for (auto& Item : m_pLiveRanges) 161 { 162 Item.second->sortAndMerge(); 163 } 164 } 165 166 /// \brief Assign a number to each instruction in a function. 167 void assignNumbers(); 168 169 /// \brief Print instruction list with numbering. 170 void printNumbering(llvm::raw_ostream& OS); 171 void dumpNumbering(); 172 173 /// \brief Used to fetch number on instructions and BB 174 unsigned getAssignedNumberForInst(llvm::Instruction*); getMaxAssignedNumberForFunction()175 unsigned getMaxAssignedNumberForFunction() { return MaxAssignedNumber; } 176 unsigned getMaxAssignedNumberForBB(llvm::BasicBlock*); 177 unsigned getMinAssignedNumberForBB(llvm::BasicBlock* pBB); 178 179 /// \brief Print live ranges. 180 void printLiveRanges(llvm::raw_ostream& OS); 181 void dumpLiveRanges(); 182 183 /// \brief Scan a function and build live ranges for all values of interest. A 184 /// live range consists of non-overlapping live intervals [i, j) where i is 185 /// the label this value starts to live and j is the label where it ends 186 /// living. This value may still be used at j but it does not interfere with 187 /// the value defined at j. Thus intervals are open on the right-hand side. 188 /// The return value of true indicates that live ranges are available for use. 189 bool buildLiveIntervals(bool RemoveLR = false); 190 191 /// \brief Return the register pressure for the whole function. 192 unsigned getMaxRegisterPressure() const; 193 194 /// \brief Return the register pressure for a basic block. 195 unsigned getMaxRegisterPressure(llvm::BasicBlock* BB) const; 196 197 void printRegisterPressureInfo(bool Detailed = false, 198 const char* msg = "") const; 199 isAvailable() const200 bool isAvailable() const { return m_available; } 201 clear(bool RemoveLR)202 void clear(bool RemoveLR) 203 { 204 for (auto& Item : m_pLiveRanges) 205 Item.second->Segments.clear(); 206 if (RemoveLR) 207 m_pLiveRanges.clear(); 208 for (auto Item : m_pLiveRangePool) 209 delete Item; 210 m_pLiveRangePool.clear(); 211 } 212 213 unsigned getRegisterPressureForInstructionFromRPMap(unsigned number) const; 214 215 void buildRPMapPerInstruction(); 216 217 private: 218 /// \brief Return the register pressure at location specified by Inst. 219 unsigned getRegisterPressure(llvm::Instruction* Inst) const; 220 getValueBytes(llvm::Value * V) const221 unsigned getValueBytes(llvm::Value* V) const 222 { 223 auto Ty = V->getType(); 224 if (Ty->isVoidTy()) 225 return 0; 226 auto VTy = llvm::dyn_cast<IGCLLVM::FixedVectorType>(Ty); 227 auto eltTy = VTy ? VTy->getElementType() : Ty; 228 uint32_t nelts = VTy ? int_cast<uint32_t>(VTy->getNumElements()) : 1; 229 uint32_t eltBits = (uint32_t)m_DL->getTypeSizeInBits(eltTy); 230 uint32_t nBytes = nelts * ((eltBits + 7) / 8); 231 unsigned int simdness = 232 (WI && WI->isUniform(V)) ? 1 : SIMD_PRESSURE_MULTIPLIER; 233 return simdness * nBytes; 234 } 235 createLiveRange()236 LiveRange* createLiveRange() 237 { 238 LiveRange* LR = new LiveRange(); 239 m_pLiveRangePool.push_back(LR); 240 return LR; 241 } 242 243 private: 244 const llvm::DataLayout* m_DL; 245 /// The function being analyzed. 246 llvm::Function* m_pFunc; 247 248 /// The loop info object. 249 llvm::LoopInfo* LI; 250 251 /// uniform analysis object 252 WIAnalysis* WI; 253 254 /// Each instruction gets an ID. 255 llvm::DenseMap<llvm::Value*, unsigned> m_pNumbers; 256 257 /// The value to live range map. 258 std::map<llvm::Value*, LiveRange*> m_pLiveRanges; 259 260 /// To check if live range info is available 261 bool m_available; 262 263 std::vector<LiveRange*> m_pLiveRangePool; 264 265 /// the max assigned number for live-range 266 unsigned int MaxAssignedNumber; 267 268 llvm::DenseMap<unsigned, unsigned> m_pRegisterPressureByInstruction; 269 }; 270 } // namespace IGC 271