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 11 #include "common/LLVMWarningsPush.hpp" 12 #include <llvm/Pass.h> 13 #include <llvm/IR/Type.h> 14 #include <llvm/IR/Instructions.h> 15 #include <llvm/ADT/DenseMap.h> 16 #include "llvm/ADT/MapVector.h" 17 #include <llvm/ADT/ilist.h> 18 #include <llvm/ADT/SetVector.h> 19 #include <llvm/ADT/SmallPtrSet.h> 20 #include <llvm/Support/Debug.h> 21 #include <llvm/IR/InstIterator.h> 22 #include <llvm/Support/raw_ostream.h> 23 #include <llvm/IR/Constants.h> 24 #include <llvm/IR/DataLayout.h> 25 #include "common/LLVMWarningsPop.hpp" 26 #include <llvm/ADT/DenseSet.h> 27 28 #include <string> 29 #include <sstream> 30 #include <set> 31 #include <map> 32 33 namespace IGC 34 { 35 36 // Maximum width supported as input 37 #define MAX_INPUT_VECTOR_WIDTH 16 38 39 // Define estimated amount of instructions in function 40 #define ESTIMATED_INST_NUM 128 41 42 /// @brief Scalarization pass used for converting code in functions 43 /// which operate on vector types, to work on scalar types (by breaking 44 /// data elements to scalars, and breaking each vector operation 45 /// to several scalar operations). 46 /// Functions are also replaced (similar to instructions), according 47 /// to data received from RuntimeServices. 48 49 class ScalarizeFunction : public llvm::FunctionPass 50 { 51 public: 52 static char ID; // Pass identification, replacement for typeid 53 54 ScalarizeFunction(bool selectiveScalarization = false); 55 56 ~ScalarizeFunction(); 57 58 /// @brief Provides name of pass getPassName()59 virtual llvm::StringRef getPassName() const override 60 { 61 return "ScalarizeFunction"; 62 } 63 getAnalysisUsage(llvm::AnalysisUsage & AU)64 virtual void getAnalysisUsage(llvm::AnalysisUsage& AU) const override 65 { 66 AU.setPreservesCFG(); 67 } 68 69 virtual bool runOnFunction(llvm::Function& F) override; 70 71 private: 72 73 /// @brief select an exclusive set that would not be scalarized 74 void buildExclusiveSet(); 75 /// @brief main Method for dispatching instructions (according to inst type) for scalarization 76 /// @param I instruction to dispatch 77 void dispatchInstructionToScalarize(llvm::Instruction* I); 78 79 /// @brief Instructions which cannot be Scalarized reach this function. 80 /// They may have a vector value, so create empty SCM entries for them if needed, 81 /// and also re-create any vector input which may have been scalarized 82 /// @param Inst instruction to work on 83 void recoverNonScalarizableInst(llvm::Instruction* Inst); 84 85 /*! \name Scalarizarion Functions 86 * \{ */ 87 /// @brief Scalarize an instruction 88 /// @param I Instruction to scalarize 89 void scalarizeInstruction(llvm::BinaryOperator* BI); 90 void scalarizeInstruction(llvm::CmpInst* CI); 91 void scalarizeInstruction(llvm::CastInst* CI); 92 void scalarizeInstruction(llvm::PHINode* CI); 93 void scalarizeInstruction(llvm::SelectInst* SI); 94 void scalarizeInstruction(llvm::ExtractElementInst* SI); 95 void scalarizeInstruction(llvm::InsertElementInst* II); 96 void scalarizeInstruction(llvm::ShuffleVectorInst* SI); 97 void scalarizeInstruction(llvm::CallInst* CI); 98 void scalarizeInstruction(llvm::AllocaInst* CI); 99 void scalarizeInstruction(llvm::GetElementPtrInst* CI); 100 101 /*! \name Scalarizarion Utility Functions 102 * \{ */ 103 104 /// @brief Takes a vector value, and returns the scalarized "breakdown" of that value 105 /// @param retValues Array for returning scalar elements in 106 /// @param retIsConstant Return (by reference) if the given value is a constant 107 /// @param origValue Vector value to obtain elements from 108 /// @param origInst Instruction for which service is requested (may be used as insertion point) 109 void obtainScalarizedValues(llvm::SmallVectorImpl<llvm::Value*>& retValues, bool* retIsConstant, 110 llvm::Value* origValue, llvm::Instruction* origInst, int dstIdx = -1); 111 112 113 /// @brief a set contains vector from original kernel that need to be used after sclarization 114 llvm::SmallSetVector<llvm::Value*, ESTIMATED_INST_NUM> m_usedVectors; 115 116 /// @brief update museVectors set with the vectori value to be obtained at when scalarization finish 117 /// @param vectorVal Vector being added to set 118 void obtainVectorValueWhichMightBeScalarized(llvm::Value* vectorVal); 119 120 /// @brief Given a vector value, check if still exists, or rebuild from scalar elements 121 /// this funciton assumes the SCM map is updated and thus should be run after sclarization is finished 122 /// @param vectorVal Vector being checked 123 void obtainVectorValueWhichMightBeScalarizedImpl(llvm::Value* vectorVal); 124 125 /// @brief obtaining vector values that are needed after scalarizaion by invoking 126 /// obtainVectorValueWhichMightBeScalarizedImpl over m_usedVectors 127 void resolveVectorValues(); 128 129 /// @brief Resolve deferred insts (Values which were scalarized with dummies) 130 void resolveDeferredInstructions(); 131 132 /*! \} */ 133 134 /// @brief Pointer to current function's context 135 llvm::LLVMContext* m_moduleContext; 136 /// @brief Accessor to current function's context context()137 llvm::LLVMContext& context() { return *m_moduleContext; } 138 /// @brief Pointer to current function 139 llvm::Function* m_currFunc; 140 141 /// @brief Set containing all the removed instructions in the function. 142 llvm::SmallDenseSet<llvm::Instruction*, ESTIMATED_INST_NUM> m_removedInsts; 143 /// @brief Counters for "transpose" statistics 144 int m_transposeCtr[llvm::Instruction::OtherOpsEnd]; 145 146 /// <summary> 147 /// @brief The instructions we do not want to scalarize 148 /// </summary> 149 std::set<llvm::Value*> m_Excludes; 150 151 /// @brief The SCM (scalar conversions map). Per each value - map of its scalar elements 152 struct SCMEntry 153 { 154 llvm::SmallVector<llvm::Value*, MAX_INPUT_VECTOR_WIDTH>scalarValues; 155 bool isOriginalVectorRemoved; 156 }; 157 llvm::DenseMap<llvm::Value*, SCMEntry*> m_SCM; 158 159 /// @brief called to create a new SCM entry. If entry already exists - return it instead 160 /// @param origValue Value pointer to search in SCM 161 /// @return pointer to found or created SCM entry 162 SCMEntry* getSCMEntry(llvm::Value* origValue); 163 164 /// @brief called to update values in SCM entry 165 /// @param entry SCM entry to update 166 /// @param scalarValues array of values to place in SCMEntry 167 /// @param origValue Value which is the key of the SCMEntry 168 /// @param isOrigValueRemoved True if original (vector) value was erased during scalarization 169 /// @param matchDbgLoc True if we want to match debug loc of the scalar value to orig Value. 170 void updateSCMEntryWithValues(SCMEntry* entry, llvm::Value* scalarValues[], 171 const llvm::Value* origValue, bool isOrigValueRemoved, 172 bool matchDbgLoc = true); 173 174 /// @brief returns an SCM entry if it exists. otherwise return NULL. 175 /// @param origValue Value used as key in SCM 176 /// @return SCMEntry if found, NULL otherwise 177 SCMEntry* getScalarizedValues(llvm::Value* origValue); 178 179 /// @brief release all allocations of SCM entries 180 void releaseAllSCMEntries(); 181 182 /// @brief create the dummy function which is called to signify a dummy value getOrCreateDummyFunc(llvm::Type * dummyType,llvm::Module * module)183 inline llvm::Function* getOrCreateDummyFunc(llvm::Type* dummyType, llvm::Module* module) { 184 if (createdDummyFunctions.find(dummyType) == createdDummyFunctions.end()) { 185 llvm::FunctionType* funcType = llvm::FunctionType::get(dummyType, false); 186 llvm::Function* function = llvm::Function::Create(funcType, llvm::Function::InternalLinkage, "", module); 187 createdDummyFunctions[dummyType] = function; 188 return function; 189 } 190 else 191 return createdDummyFunctions[dummyType]; 192 } 193 194 /// @brief deletes the memory associated with all the created dynamic Function objects in the map destroyDummyFunc()195 inline void destroyDummyFunc() { 196 for (auto& function : createdDummyFunctions) { 197 if (function.second) { 198 function.second->eraseFromParent(); 199 function.second = nullptr; 200 } 201 } 202 } 203 204 /// @brief An array of available SCMEntry's 205 SCMEntry* m_SCMAllocationArray; 206 207 /// @brief Index, in "SCMAllocationArray", of next free SCMEntry 208 unsigned m_SCMArrayLocation; 209 210 /// @brief Vector containing all the "SCMAllocationArray" arrays which were allocated 211 llvm::SmallVector<SCMEntry*, 4> m_SCMArrays; 212 213 /// @brief The DRL (Deferred resolution list). 214 typedef struct DRLEntry 215 { 216 llvm::Value* unresolvedInst; 217 llvm::SmallVector<llvm::Value*, MAX_INPUT_VECTOR_WIDTH>dummyVals; 218 } DRLEntry; 219 llvm::SmallVector<DRLEntry, 4> m_DRL; 220 221 /*! \name Pre-Scalarization function arguments scan 222 * \{ */ 223 224 /// @brief Data structure for holding "real" inputs/output of function call 225 // first - arguments of function 226 // second - retuns of function. There may be more than one return value, e.g. sincos 227 typedef std::pair< llvm::SmallVector<llvm::Value*, 4>, llvm::SmallVector<llvm::Value*, 4> > funcRootsVect; 228 /// @brief Some getters which access funcRootsVect and make the code more readable getReturns(funcRootsVect & FRV)229 static llvm::SmallVectorImpl<llvm::Value*>& getReturns(funcRootsVect& FRV) { return FRV.second; } getReturns(const funcRootsVect & FRV)230 static const llvm::SmallVectorImpl<llvm::Value*>& getReturns(const funcRootsVect& FRV) { return FRV.second; } getArgs(funcRootsVect & FRV)231 static llvm::SmallVectorImpl<llvm::Value*>& getArgs(funcRootsVect& FRV) { return FRV.first; } getArgs(const funcRootsVect & FRV)232 static const llvm::SmallVectorImpl<llvm::Value*>& getArgs(const funcRootsVect& FRV) { return FRV.first; } 233 234 /// @brief flag for selective scalarization 235 bool m_SelectiveScalarization; 236 237 /// @brief This holds DataLayout of processed module 238 const llvm::DataLayout* m_pDL; 239 240 /// @brief This holds all the created dummy functions throughout the lifetime of the pass, and manages their memory 241 llvm::MapVector<llvm::Type*, llvm::Function*> createdDummyFunctions; 242 }; 243 244 } // namespace IGC 245 246 /// By default (no argument given to this function), vector load/store are kept as is. 247 extern "C" llvm::FunctionPass* createScalarizerPass(bool selectiveScalarization = false); 248