1 //===--- SPIRVUtils.h ---- SPIR-V Utility Functions -------------*- 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 // This file contains miscellaneous utility functions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_LIB_TARGET_SPIRV_SPIRVUTILS_H 14 #define LLVM_LIB_TARGET_SPIRV_SPIRVUTILS_H 15 16 #include "MCTargetDesc/SPIRVBaseInfo.h" 17 #include "llvm/Analysis/LoopInfo.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/IR/Dominators.h" 20 #include "llvm/IR/GlobalVariable.h" 21 #include "llvm/IR/IRBuilder.h" 22 #include "llvm/IR/TypedPointerType.h" 23 #include <queue> 24 #include <string> 25 #include <unordered_map> 26 #include <unordered_set> 27 28 namespace llvm { 29 class MCInst; 30 class MachineFunction; 31 class MachineInstr; 32 class MachineInstrBuilder; 33 class MachineIRBuilder; 34 class MachineRegisterInfo; 35 class Register; 36 class StringRef; 37 class SPIRVInstrInfo; 38 class SPIRVSubtarget; 39 class SPIRVGlobalRegistry; 40 41 // This class implements a partial ordering visitor, which visits a cyclic graph 42 // in natural topological-like ordering. Topological ordering is not defined for 43 // directed graphs with cycles, so this assumes cycles are a single node, and 44 // ignores back-edges. The cycle is visited from the entry in the same 45 // topological-like ordering. 46 // 47 // Note: this visitor REQUIRES a reducible graph. 48 // 49 // This means once we visit a node, we know all the possible ancestors have been 50 // visited. 51 // 52 // clang-format off 53 // 54 // Given this graph: 55 // 56 // ,-> B -\ 57 // A -+ +---> D ----> E -> F -> G -> H 58 // `-> C -/ ^ | 59 // +-----------------+ 60 // 61 // Visit order is: 62 // A, [B, C in any order], D, E, F, G, H 63 // 64 // clang-format on 65 // 66 // Changing the function CFG between the construction of the visitor and 67 // visiting is undefined. The visitor can be reused, but if the CFG is updated, 68 // the visitor must be rebuilt. 69 class PartialOrderingVisitor { 70 DomTreeBuilder::BBDomTree DT; 71 LoopInfo LI; 72 73 std::unordered_set<BasicBlock *> Queued = {}; 74 std::queue<BasicBlock *> ToVisit = {}; 75 76 struct OrderInfo { 77 size_t Rank; 78 size_t TraversalIndex; 79 }; 80 81 using BlockToOrderInfoMap = std::unordered_map<BasicBlock *, OrderInfo>; 82 BlockToOrderInfoMap BlockToOrder; 83 std::vector<BasicBlock *> Order = {}; 84 85 // Get all basic-blocks reachable from Start. 86 std::unordered_set<BasicBlock *> getReachableFrom(BasicBlock *Start); 87 88 // Internal function used to determine the partial ordering. 89 // Visits |BB| with the current rank being |Rank|. 90 size_t visit(BasicBlock *BB, size_t Rank); 91 92 bool CanBeVisited(BasicBlock *BB) const; 93 94 public: 95 size_t GetNodeRank(BasicBlock *BB) const; 96 97 // Build the visitor to operate on the function F. 98 PartialOrderingVisitor(Function &F); 99 100 // Returns true is |LHS| comes before |RHS| in the partial ordering. 101 // If |LHS| and |RHS| have the same rank, the traversal order determines the 102 // order (order is stable). 103 bool compare(const BasicBlock *LHS, const BasicBlock *RHS) const; 104 105 // Visit the function starting from the basic block |Start|, and calling |Op| 106 // on each visited BB. This traversal ignores back-edges, meaning this won't 107 // visit a node to which |Start| is not an ancestor. 108 // If Op returns |true|, the visitor continues. If |Op| returns false, the 109 // visitor will stop at that rank. This means if 2 nodes share the same rank, 110 // and Op returns false when visiting the first, the second will be visited 111 // afterwards. But none of their successors will. 112 void partialOrderVisit(BasicBlock &Start, 113 std::function<bool(BasicBlock *)> Op); 114 }; 115 116 // Add the given string as a series of integer operand, inserting null 117 // terminators and padding to make sure the operands all have 32-bit 118 // little-endian words. 119 void addStringImm(const StringRef &Str, MCInst &Inst); 120 void addStringImm(const StringRef &Str, MachineInstrBuilder &MIB); 121 void addStringImm(const StringRef &Str, IRBuilder<> &B, 122 std::vector<Value *> &Args); 123 124 // Read the series of integer operands back as a null-terminated string using 125 // the reverse of the logic in addStringImm. 126 std::string getStringImm(const MachineInstr &MI, unsigned StartIndex); 127 128 // Add the given numerical immediate to MIB. 129 void addNumImm(const APInt &Imm, MachineInstrBuilder &MIB); 130 131 // Add an OpName instruction for the given target register. 132 void buildOpName(Register Target, const StringRef &Name, 133 MachineIRBuilder &MIRBuilder); 134 void buildOpName(Register Target, const StringRef &Name, MachineInstr &I, 135 const SPIRVInstrInfo &TII); 136 137 // Add an OpDecorate instruction for the given Reg. 138 void buildOpDecorate(Register Reg, MachineIRBuilder &MIRBuilder, 139 SPIRV::Decoration::Decoration Dec, 140 const std::vector<uint32_t> &DecArgs, 141 StringRef StrImm = ""); 142 void buildOpDecorate(Register Reg, MachineInstr &I, const SPIRVInstrInfo &TII, 143 SPIRV::Decoration::Decoration Dec, 144 const std::vector<uint32_t> &DecArgs, 145 StringRef StrImm = ""); 146 147 // Add an OpDecorate instruction by "spirv.Decorations" metadata node. 148 void buildOpSpirvDecorations(Register Reg, MachineIRBuilder &MIRBuilder, 149 const MDNode *GVarMD); 150 151 // Return a valid position for the OpVariable instruction inside a function, 152 // i.e., at the beginning of the first block of the function. 153 MachineBasicBlock::iterator getOpVariableMBBIt(MachineInstr &I); 154 155 // Return a valid position for the instruction at the end of the block before 156 // terminators and debug instructions. 157 MachineBasicBlock::iterator getInsertPtValidEnd(MachineBasicBlock *MBB); 158 159 // Convert a SPIR-V storage class to the corresponding LLVM IR address space. 160 // TODO: maybe the following two functions should be handled in the subtarget 161 // to allow for different OpenCL vs Vulkan handling. 162 constexpr unsigned 163 storageClassToAddressSpace(SPIRV::StorageClass::StorageClass SC) { 164 switch (SC) { 165 case SPIRV::StorageClass::Function: 166 return 0; 167 case SPIRV::StorageClass::CrossWorkgroup: 168 return 1; 169 case SPIRV::StorageClass::UniformConstant: 170 return 2; 171 case SPIRV::StorageClass::Workgroup: 172 return 3; 173 case SPIRV::StorageClass::Generic: 174 return 4; 175 case SPIRV::StorageClass::DeviceOnlyINTEL: 176 return 5; 177 case SPIRV::StorageClass::HostOnlyINTEL: 178 return 6; 179 case SPIRV::StorageClass::Input: 180 return 7; 181 case SPIRV::StorageClass::Output: 182 return 8; 183 case SPIRV::StorageClass::CodeSectionINTEL: 184 return 9; 185 case SPIRV::StorageClass::Private: 186 return 10; 187 default: 188 report_fatal_error("Unable to get address space id"); 189 } 190 } 191 192 // Convert an LLVM IR address space to a SPIR-V storage class. 193 SPIRV::StorageClass::StorageClass 194 addressSpaceToStorageClass(unsigned AddrSpace, const SPIRVSubtarget &STI); 195 196 SPIRV::MemorySemantics::MemorySemantics 197 getMemSemanticsForStorageClass(SPIRV::StorageClass::StorageClass SC); 198 199 SPIRV::MemorySemantics::MemorySemantics getMemSemantics(AtomicOrdering Ord); 200 201 SPIRV::Scope::Scope getMemScope(LLVMContext &Ctx, SyncScope::ID Id); 202 203 // Find def instruction for the given ConstReg, walking through 204 // spv_track_constant and ASSIGN_TYPE instructions. Updates ConstReg by def 205 // of OpConstant instruction. 206 MachineInstr *getDefInstrMaybeConstant(Register &ConstReg, 207 const MachineRegisterInfo *MRI); 208 209 // Get constant integer value of the given ConstReg. 210 uint64_t getIConstVal(Register ConstReg, const MachineRegisterInfo *MRI); 211 212 // Check if MI is a SPIR-V specific intrinsic call. 213 bool isSpvIntrinsic(const MachineInstr &MI, Intrinsic::ID IntrinsicID); 214 // Check if it's a SPIR-V specific intrinsic call. 215 bool isSpvIntrinsic(const Value *Arg); 216 217 // Get type of i-th operand of the metadata node. 218 Type *getMDOperandAsType(const MDNode *N, unsigned I); 219 220 // If OpenCL or SPIR-V builtin function name is recognized, return a demangled 221 // name, otherwise return an empty string. 222 std::string getOclOrSpirvBuiltinDemangledName(StringRef Name); 223 224 // Check if a string contains a builtin prefix. 225 bool hasBuiltinTypePrefix(StringRef Name); 226 227 // Check if given LLVM type is a special opaque builtin type. 228 bool isSpecialOpaqueType(const Type *Ty); 229 230 // Check if the function is an SPIR-V entry point 231 bool isEntryPoint(const Function &F); 232 233 // Parse basic scalar type name, substring TypeName, and return LLVM type. 234 Type *parseBasicTypeName(StringRef &TypeName, LLVMContext &Ctx); 235 236 // Sort blocks in a partial ordering, so each block is after all its 237 // dominators. This should match both the SPIR-V and the MIR requirements. 238 // Returns true if the function was changed. 239 bool sortBlocks(Function &F); 240 241 inline bool hasInitializer(const GlobalVariable *GV) { 242 return GV->hasInitializer() && !isa<UndefValue>(GV->getInitializer()); 243 } 244 245 // True if this is an instance of TypedPointerType. 246 inline bool isTypedPointerTy(const Type *T) { 247 return T && T->getTypeID() == Type::TypedPointerTyID; 248 } 249 250 // True if this is an instance of PointerType. 251 inline bool isUntypedPointerTy(const Type *T) { 252 return T && T->getTypeID() == Type::PointerTyID; 253 } 254 255 // True if this is an instance of PointerType or TypedPointerType. 256 inline bool isPointerTy(const Type *T) { 257 return isUntypedPointerTy(T) || isTypedPointerTy(T); 258 } 259 260 // Get the address space of this pointer or pointer vector type for instances of 261 // PointerType or TypedPointerType. 262 inline unsigned getPointerAddressSpace(const Type *T) { 263 Type *SubT = T->getScalarType(); 264 return SubT->getTypeID() == Type::PointerTyID 265 ? cast<PointerType>(SubT)->getAddressSpace() 266 : cast<TypedPointerType>(SubT)->getAddressSpace(); 267 } 268 269 // Return true if the Argument is decorated with a pointee type 270 inline bool hasPointeeTypeAttr(Argument *Arg) { 271 return Arg->hasByValAttr() || Arg->hasByRefAttr() || Arg->hasStructRetAttr(); 272 } 273 274 // Return the pointee type of the argument or nullptr otherwise 275 inline Type *getPointeeTypeByAttr(Argument *Arg) { 276 if (Arg->hasByValAttr()) 277 return Arg->getParamByValType(); 278 if (Arg->hasStructRetAttr()) 279 return Arg->getParamStructRetType(); 280 if (Arg->hasByRefAttr()) 281 return Arg->getParamByRefType(); 282 return nullptr; 283 } 284 285 inline Type *reconstructFunctionType(Function *F) { 286 SmallVector<Type *> ArgTys; 287 for (unsigned i = 0; i < F->arg_size(); ++i) 288 ArgTys.push_back(F->getArg(i)->getType()); 289 return FunctionType::get(F->getReturnType(), ArgTys, F->isVarArg()); 290 } 291 292 #define TYPED_PTR_TARGET_EXT_NAME "spirv.$TypedPointerType" 293 inline Type *getTypedPointerWrapper(Type *ElemTy, unsigned AS) { 294 return TargetExtType::get(ElemTy->getContext(), TYPED_PTR_TARGET_EXT_NAME, 295 {ElemTy}, {AS}); 296 } 297 298 inline bool isTypedPointerWrapper(const TargetExtType *ExtTy) { 299 return ExtTy->getName() == TYPED_PTR_TARGET_EXT_NAME && 300 ExtTy->getNumIntParameters() == 1 && 301 ExtTy->getNumTypeParameters() == 1; 302 } 303 304 // True if this is an instance of PointerType or TypedPointerType. 305 inline bool isPointerTyOrWrapper(const Type *Ty) { 306 if (auto *ExtTy = dyn_cast<TargetExtType>(Ty)) 307 return isTypedPointerWrapper(ExtTy); 308 return isPointerTy(Ty); 309 } 310 311 inline Type *applyWrappers(Type *Ty) { 312 if (auto *ExtTy = dyn_cast<TargetExtType>(Ty)) { 313 if (isTypedPointerWrapper(ExtTy)) 314 return TypedPointerType::get(applyWrappers(ExtTy->getTypeParameter(0)), 315 ExtTy->getIntParameter(0)); 316 } else if (auto *VecTy = dyn_cast<VectorType>(Ty)) { 317 Type *ElemTy = VecTy->getElementType(); 318 Type *NewElemTy = ElemTy->isTargetExtTy() ? applyWrappers(ElemTy) : ElemTy; 319 if (NewElemTy != ElemTy) 320 return VectorType::get(NewElemTy, VecTy->getElementCount()); 321 } 322 return Ty; 323 } 324 325 inline Type *getPointeeType(const Type *Ty) { 326 if (Ty) { 327 if (auto PType = dyn_cast<TypedPointerType>(Ty)) 328 return PType->getElementType(); 329 else if (auto *ExtTy = dyn_cast<TargetExtType>(Ty)) 330 if (isTypedPointerWrapper(ExtTy)) 331 return ExtTy->getTypeParameter(0); 332 } 333 return nullptr; 334 } 335 336 inline bool isUntypedEquivalentToTyExt(Type *Ty1, Type *Ty2) { 337 if (!isUntypedPointerTy(Ty1) || !Ty2) 338 return false; 339 if (auto *ExtTy = dyn_cast<TargetExtType>(Ty2)) 340 if (isTypedPointerWrapper(ExtTy) && 341 ExtTy->getTypeParameter(0) == 342 IntegerType::getInt8Ty(Ty1->getContext()) && 343 ExtTy->getIntParameter(0) == cast<PointerType>(Ty1)->getAddressSpace()) 344 return true; 345 return false; 346 } 347 348 inline bool isEquivalentTypes(Type *Ty1, Type *Ty2) { 349 return isUntypedEquivalentToTyExt(Ty1, Ty2) || 350 isUntypedEquivalentToTyExt(Ty2, Ty1); 351 } 352 353 inline Type *toTypedPointer(Type *Ty) { 354 if (Type *NewTy = applyWrappers(Ty); NewTy != Ty) 355 return NewTy; 356 return isUntypedPointerTy(Ty) 357 ? TypedPointerType::get(IntegerType::getInt8Ty(Ty->getContext()), 358 getPointerAddressSpace(Ty)) 359 : Ty; 360 } 361 362 inline Type *toTypedFunPointer(FunctionType *FTy) { 363 Type *OrigRetTy = FTy->getReturnType(); 364 Type *RetTy = toTypedPointer(OrigRetTy); 365 bool IsUntypedPtr = false; 366 for (Type *PTy : FTy->params()) { 367 if (isUntypedPointerTy(PTy)) { 368 IsUntypedPtr = true; 369 break; 370 } 371 } 372 if (!IsUntypedPtr && RetTy == OrigRetTy) 373 return FTy; 374 SmallVector<Type *> ParamTys; 375 for (Type *PTy : FTy->params()) 376 ParamTys.push_back(toTypedPointer(PTy)); 377 return FunctionType::get(RetTy, ParamTys, FTy->isVarArg()); 378 } 379 380 inline const Type *unifyPtrType(const Type *Ty) { 381 if (auto FTy = dyn_cast<FunctionType>(Ty)) 382 return toTypedFunPointer(const_cast<FunctionType *>(FTy)); 383 return toTypedPointer(const_cast<Type *>(Ty)); 384 } 385 386 MachineInstr *getVRegDef(MachineRegisterInfo &MRI, Register Reg); 387 388 #define SPIRV_BACKEND_SERVICE_FUN_NAME "__spirv_backend_service_fun" 389 bool getVacantFunctionName(Module &M, std::string &Name); 390 391 void setRegClassType(Register Reg, const Type *Ty, SPIRVGlobalRegistry *GR, 392 MachineIRBuilder &MIRBuilder, bool Force = false); 393 void setRegClassType(Register Reg, const MachineInstr *SpvType, 394 SPIRVGlobalRegistry *GR, MachineRegisterInfo *MRI, 395 const MachineFunction &MF, bool Force = false); 396 Register createVirtualRegister(const MachineInstr *SpvType, 397 SPIRVGlobalRegistry *GR, 398 MachineRegisterInfo *MRI, 399 const MachineFunction &MF); 400 Register createVirtualRegister(const MachineInstr *SpvType, 401 SPIRVGlobalRegistry *GR, 402 MachineIRBuilder &MIRBuilder); 403 Register createVirtualRegister(const Type *Ty, SPIRVGlobalRegistry *GR, 404 MachineIRBuilder &MIRBuilder); 405 406 // Return true if there is an opaque pointer type nested in the argument. 407 bool isNestedPointer(const Type *Ty); 408 409 enum FPDecorationId { NONE, RTE, RTZ, RTP, RTN, SAT }; 410 411 inline FPDecorationId demangledPostfixToDecorationId(const std::string &S) { 412 static std::unordered_map<std::string, FPDecorationId> Mapping = { 413 {"rte", FPDecorationId::RTE}, 414 {"rtz", FPDecorationId::RTZ}, 415 {"rtp", FPDecorationId::RTP}, 416 {"rtn", FPDecorationId::RTN}, 417 {"sat", FPDecorationId::SAT}}; 418 auto It = Mapping.find(S); 419 return It == Mapping.end() ? FPDecorationId::NONE : It->second; 420 } 421 422 } // namespace llvm 423 #endif // LLVM_LIB_TARGET_SPIRV_SPIRVUTILS_H 424