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 #pragma once 10 #include "Compiler/MetaDataApi/MetaDataApi.h" 11 #include "common/LLVMWarningsPush.hpp" 12 #include "llvm/IR/ValueHandle.h" 13 #include "llvm/Pass.h" 14 #include "llvm/Analysis/CallGraph.h" 15 #include "common/LLVMWarningsPop.hpp" 16 #include "Probe/Assertion.h" 17 18 namespace IGC { 19 class GenXFunctionGroupAnalysis; 20 21 /// \brief A module pass to initialize GenXFunctionGroupAnalysis and sort function 22 /// list in a module properly. 23 /// 24 /// The module pass's results have two parts: 25 /// 26 /// (1) GenXFunctionGroupAnalysis object, which stores information needed for vISA 27 /// emission. E.g, each non-empty function belongs to a uniquely defined 28 /// function group with a kernel function as the head. 29 /// 30 /// (2) The module itself. All functions reachable from different function 31 /// groups will be cloned if necessary; they will be ordered such that each 32 /// callee will be after the caller in the module function list. When clone 33 /// happens, this module pass returns true, otherwise it returns false. 34 /// Currently, we assume no kernel functions will be called. This 35 /// requirement could be enforced before this pass by inlining kernels. 36 /// 37 class GenXCodeGenModule : public llvm::ModulePass { 38 public: 39 static char ID; 40 GenXCodeGenModule(); 41 ~GenXCodeGenModule(); getPassName()42 virtual llvm::StringRef getPassName() const override { return "GenX CodeGen module"; } 43 void getAnalysisUsage(llvm::AnalysisUsage& AU) const override; 44 bool runOnModule(llvm::Module& M) override; 45 private: 46 void processFunction(llvm::Function& F); 47 void processSCC(std::vector<llvm::CallGraphNode*>* SCCNodes); 48 void setFuncProperties(llvm::CallGraph& CG); 49 void copyFuncProperties(llvm::Function* To, llvm::Function* From); 50 llvm::Function* cloneFunc(llvm::Function* F); 51 GenXFunctionGroupAnalysis* FGA; 52 IGC::IGCMD::MetaDataUtils* pMdUtils; 53 bool Modified; 54 }; 55 56 /// \brief A collection of functions that are reachable from a kernel. 57 class FunctionGroup { 58 public: 59 friend class GenXFunctionGroupAnalysis; 60 /// \brief use 2-d vector of Functions to represent FunctionGroup. 61 /// Each sub-vector is a subgroup led by a kernel or a stack-call function. 62 /// Element [0][0] is the group head. Element[i][0] is the sub-group head. 63 typedef llvm::SmallVector<llvm::AssertingVH<llvm::Function>, 8> SubGroupContainer; 64 typedef llvm::SmallVector<SubGroupContainer*, 4> FunctionGroupContainer; 65 FunctionGroupContainer Functions; 66 67 class iterator 68 { 69 public: 70 enum POS { BEGIN, END }; iterator(FunctionGroupContainer & FC,POS pos)71 iterator(FunctionGroupContainer &FC, POS pos) 72 { 73 if (pos == BEGIN) 74 { 75 major = FC.begin(); 76 majorEnd = FC.end(); 77 minor = (*major)->begin(); 78 } 79 else if (pos == END) 80 { 81 major = FC.end(); 82 majorEnd = FC.end(); 83 minor = FC.back()->end(); 84 } 85 } 86 iterator& operator++() 87 { 88 minor++; 89 if (minor == (*major)->end()) 90 { 91 major++; 92 if (major != majorEnd) 93 minor = (*major)->begin(); 94 } 95 return *this; 96 } 97 llvm::Function* operator*() 98 { 99 return *minor; 100 } 101 bool operator==(const iterator& rhs) 102 { 103 return (major == rhs.major && minor == rhs.minor); 104 } 105 bool operator!=(const iterator& rhs) 106 { 107 return !(*this == rhs); 108 } 109 private: 110 FunctionGroupContainer::iterator major; 111 FunctionGroupContainer::iterator majorEnd; 112 SubGroupContainer::iterator minor; 113 }; 114 begin()115 iterator begin() { return iterator(Functions, iterator::BEGIN); } end()116 iterator end() { return iterator(Functions, iterator::END); } 117 ~FunctionGroup()118 ~FunctionGroup() { 119 for (auto I = Functions.begin(), E = Functions.end(); I != E; I++) { 120 delete (*I); 121 } 122 } 123 124 /// \brief The entry kernel function of group. getHead()125 llvm::Function* getHead() { 126 return Functions.front()->front(); 127 } 128 /// \brief The tail function of a group. back()129 llvm::Function* back() { 130 return Functions.back()->back(); 131 } 132 /// \brief Only one function in this group isSingle()133 bool isSingle() { 134 return (Functions.size() == 1 && Functions.front()->size() == 1); 135 } 136 /// \brief Function group has a stack call (including indirect calls) hasStackCall()137 bool hasStackCall() { 138 return m_hasStackCall; 139 } hasInlineAsm()140 bool hasInlineAsm() { 141 return m_hasInlineAsm; 142 } 143 /// \brief Function group has a variable length alloca hasVariableLengthAlloca()144 bool hasVariableLengthAlloca() { 145 return m_hasVaribleLengthAlloca; 146 } 147 /// \brief Function group has indirect calls hasIndirectCall()148 bool hasIndirectCall() { 149 return m_hasIndirectCall; 150 } 151 /// \brief Function group has recursion hasRecursion()152 bool hasRecursion() { 153 return m_hasRecursion; 154 } 155 /// Set and Get the max private memory used by FG give then call depth 156 /// This is calculated in PrivateMemoryResolution.cpp setMaxPrivateMemOnStack(unsigned size)157 void setMaxPrivateMemOnStack(unsigned size) { 158 m_MaxPrivateMemOnStack = size; 159 } getMaxPrivateMemOnStack()160 unsigned getMaxPrivateMemOnStack() { 161 return m_MaxPrivateMemOnStack; 162 } 163 replaceGroupHead(llvm::Function * OH,llvm::Function * NH)164 void replaceGroupHead(llvm::Function* OH, llvm::Function* NH) { 165 auto headSG = Functions[0]; 166 llvm::AssertingVH<llvm::Function>& HVH = (*headSG)[0]; 167 IGC_ASSERT_MESSAGE(&(*HVH) == OH, "Group's head isn't set up correctly!"); 168 HVH = NH; 169 } 170 171 private: 172 bool m_hasStackCall = false; 173 bool m_hasInlineAsm = false; 174 bool m_hasVaribleLengthAlloca = false; 175 bool m_hasIndirectCall = false; 176 bool m_hasRecursion = false; 177 unsigned m_MaxPrivateMemOnStack = 0; 178 }; 179 180 class GenXFunctionGroupAnalysis : public llvm::ImmutablePass { 181 enum class FuncPropertyInfo : uint32_t { 182 FPI_LEAF = 0x1 // bit 0: 1 (leaf function) 183 }; 184 185 /// \brief The module being analyzed. 186 llvm::Module* M; 187 188 /// \brief Function groups constructed in this module. 189 llvm::SmallVector<FunctionGroup*, 8> Groups; 190 191 /// \brief Each function belongs to a uniquely defined function group. 192 llvm::DenseMap<const llvm::Function*, FunctionGroup*> GroupMap; 193 194 /// \brief Each function also belongs to a uniquely defined sub-group of a stack-call entry 195 llvm::DenseMap<const llvm::Function*, llvm::Function*> SubGroupMap; 196 197 /// \brief Properties for each function 198 llvm::DenseMap<const llvm::Function*, uint32_t> FuncProperties; 199 200 /// \brief Special group that contains indirect call functions and the dummy kernel 201 FunctionGroup* IndirectCallGroup = nullptr; 202 203 public: 204 static char ID; 205 explicit GenXFunctionGroupAnalysis(); ~GenXFunctionGroupAnalysis()206 ~GenXFunctionGroupAnalysis() { clear(); } 207 getPassName()208 virtual llvm::StringRef getPassName() const override { return "FunctionGroup analysis"; } 209 210 /// This function returns nullptr if no analysis is not available. getModule()211 llvm::Module* getModule() { return M; } setModule(llvm::Module * Mod)212 void setModule(llvm::Module* Mod) { M = Mod; } 213 void clear(); 214 215 /// \brief This function rebuilds function groups with the assumption that 216 /// no function will be directly or undirectly called from more than one 217 /// kernel, and functions in the module are well-ordered. It returns false if 218 /// fails to rebuild and returns true otherwise. 219 /// 220 bool rebuild(llvm::Module* Mod); 221 222 // Attach all indirectly called functions to a single kernel group 223 void addIndirectFuncsToKernelGroup(llvm::Module* pModule); 224 225 // Replace OF with NF in Groups and GroupMap 226 void replaceEntryFunc(llvm::Function* OF, llvm::Function* NF); 227 228 /// \brief Verify if this analysis result is valid. 229 bool verify(); 230 231 void getAnalysisUsage(llvm::AnalysisUsage& AU) const override; 232 233 /// \brief Get the FunctionGroup containing Function F, else nullptr. 234 FunctionGroup* getGroup(const llvm::Function* F); 235 236 /// \brief Get the FunctionGroup for which Function F is the head, else 237 /// nullptr. 238 FunctionGroup* getGroupForHead(const llvm::Function* F); 239 240 /// \brief Get the group head for the group to which F belongs. getGroupHead(const llvm::Function * F)241 llvm::Function* getGroupHead(const llvm::Function* F) { 242 auto FG = getGroup(F); 243 IGC_ASSERT(nullptr != FG); 244 return FG->getHead(); 245 } 246 /// \brief Get the subgroup head for the subgroup to which F belongs getSubGroupMap(llvm::Function * F)247 llvm::Function* getSubGroupMap(llvm::Function* F) { 248 auto I = SubGroupMap.find(F); 249 if (I == SubGroupMap.end()) 250 return nullptr; 251 return I->second; 252 } 253 setSubGroupMap(llvm::Function * F,llvm::Function * SubGroupHead)254 void setSubGroupMap(llvm::Function* F, llvm::Function* SubGroupHead) { 255 SubGroupMap[F] = SubGroupHead; 256 } 257 isIndirectCallGroup(const llvm::Function * F)258 bool isIndirectCallGroup(const llvm::Function* F) { 259 FunctionGroup* FG = getGroup(F); 260 return FG != nullptr && FG == IndirectCallGroup; 261 } 262 getIndirectCallGroup()263 FunctionGroup* getIndirectCallGroup() { 264 return IndirectCallGroup; 265 } 266 267 /// \brief Check whether this is a group header. isGroupHead(const llvm::Function * F)268 bool isGroupHead(const llvm::Function* F) { 269 return getGroupForHead(F) != nullptr; 270 } 271 272 /// \brief Check whether this is the last function in a function group. This 273 /// order is also reflected in the module function list. isGroupTail(const llvm::Function * F)274 bool isGroupTail(const llvm::Function* F) { 275 FunctionGroup* FG = getGroup(F); 276 IGC_ASSERT_MESSAGE(nullptr != FG, "not in function group"); 277 return F == FG->back(); 278 } 279 isLeafFunc(const llvm::Function * F)280 bool isLeafFunc(const llvm::Function* F) { 281 auto FI = FuncProperties.find(F); 282 if (FI != FuncProperties.end()) { 283 return (FI->second & (uint32_t)FuncPropertyInfo::FPI_LEAF); 284 } 285 return false; 286 } setLeafFunc(const llvm::Function * F)287 void setLeafFunc(const llvm::Function* F) { 288 auto II = FuncProperties.find(F); 289 uint32_t P = (II != FuncProperties.end()) ? II->second : 0; 290 FuncProperties[F] = (P | (uint32_t)FuncPropertyInfo::FPI_LEAF); 291 } copyFuncProperties(const llvm::Function * To,const llvm::Function * From)292 void copyFuncProperties(const llvm::Function* To, const llvm::Function* From) { 293 auto II = FuncProperties.find(From); 294 if (II != FuncProperties.end()) { 295 FuncProperties[To] = II->second; 296 } 297 } 298 299 /// check if function is stack-called 300 bool useStackCall(llvm::Function* F); 301 302 /// sets function group attribute flags 303 void setGroupAttributes(); 304 305 typedef llvm::SmallVectorImpl<FunctionGroup*>::iterator iterator; begin()306 iterator begin() { return iterator(Groups.begin()); } end()307 iterator end() { return iterator(Groups.end()); } 308 309 /// \brief Returns the number of groups, aka. kernels. size()310 size_t size() { return Groups.size(); } 311 312 /// \brife add Function F to FunctionGroup FG. 313 void addToFunctionGroup(llvm::Function* F, FunctionGroup* FG, llvm::Function* SubGrpH); 314 315 /// \brief Create a new FunctionGroup with head F. 316 FunctionGroup* createFunctionGroup(llvm::Function* F); 317 318 void print(llvm::raw_ostream& os); 319 320 #if defined(_DEBUG) 321 void dump(); 322 #endif 323 }; 324 325 llvm::ModulePass* createGenXCodeGenModulePass(); 326 llvm::ImmutablePass* createGenXFunctionGroupAnalysisPass(); 327 llvm::Pass* createSubroutineInlinerPass(); 328 329 } // namespace IGC 330