582 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains miscellaneous utility functions.10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_LIB_TARGET_SPIRV_SPIRVUTILS_H14#define LLVM_LIB_TARGET_SPIRV_SPIRVUTILS_H15 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 28namespace llvm {29class MCInst;30class MachineFunction;31class MachineInstr;32class MachineInstrBuilder;33class MachineIRBuilder;34class MachineRegisterInfo;35class Register;36class StringRef;37class SPIRVInstrInfo;38class SPIRVSubtarget;39class SPIRVGlobalRegistry;40 41// This class implements a partial ordering visitor, which visits a cyclic graph42// in natural topological-like ordering. Topological ordering is not defined for43// directed graphs with cycles, so this assumes cycles are a single node, and44// ignores back-edges. The cycle is visited from the entry in the same45// 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 been50// visited.51//52// clang-format off53//54// Given this graph:55//56// ,-> B -\57// A -+ +---> D ----> E -> F -> G -> H58// `-> C -/ ^ |59// +-----------------+60//61// Visit order is:62// A, [B, C in any order], D, E, F, G, H63//64// clang-format on65//66// Changing the function CFG between the construction of the visitor and67// visiting is undefined. The visitor can be reused, but if the CFG is updated,68// the visitor must be rebuilt.69class 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 94public: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 the102 // 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't107 // visit a node to which |Start| is not an ancestor.108 // If Op returns |true|, the visitor continues. If |Op| returns false, the109 // 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 visited111 // afterwards. But none of their successors will.112 void partialOrderVisit(BasicBlock &Start,113 std::function<bool(BasicBlock *)> Op);114};115 116namespace SPIRV {117struct FPFastMathDefaultInfo {118 const Type *Ty = nullptr;119 unsigned FastMathFlags = 0;120 // When SPV_KHR_float_controls2 ContractionOff and SignzeroInfNanPreserve are121 // deprecated, and we replace them with FPFastMathDefault appropriate flags122 // instead. However, we have no guarantee about the order in which we will123 // process execution modes. Therefore it could happen that we first process124 // ContractionOff, setting AllowContraction bit to 0, and then we process125 // FPFastMathDefault enabling AllowContraction bit, effectively invalidating126 // ContractionOff. Because of that, it's best to keep separate bits for the127 // different execution modes, and we will try and combine them later when we128 // emit OpExecutionMode instructions.129 bool ContractionOff = false;130 bool SignedZeroInfNanPreserve = false;131 bool FPFastMathDefault = false;132 133 FPFastMathDefaultInfo() = default;134 FPFastMathDefaultInfo(const Type *Ty, unsigned FastMathFlags)135 : Ty(Ty), FastMathFlags(FastMathFlags) {}136 bool operator==(const FPFastMathDefaultInfo &Other) const {137 return Ty == Other.Ty && FastMathFlags == Other.FastMathFlags &&138 ContractionOff == Other.ContractionOff &&139 SignedZeroInfNanPreserve == Other.SignedZeroInfNanPreserve &&140 FPFastMathDefault == Other.FPFastMathDefault;141 }142};143 144struct FPFastMathDefaultInfoVector145 : public SmallVector<SPIRV::FPFastMathDefaultInfo, 3> {146 static size_t computeFPFastMathDefaultInfoVecIndex(size_t BitWidth) {147 switch (BitWidth) {148 case 16: // half149 return 0;150 case 32: // float151 return 1;152 case 64: // double153 return 2;154 default:155 report_fatal_error("Expected BitWidth to be 16, 32, 64", false);156 }157 llvm_unreachable(158 "Unreachable code in computeFPFastMathDefaultInfoVecIndex");159 }160};161 162} // namespace SPIRV163 164// Add the given string as a series of integer operand, inserting null165// terminators and padding to make sure the operands all have 32-bit166// little-endian words.167void addStringImm(const StringRef &Str, MCInst &Inst);168void addStringImm(const StringRef &Str, MachineInstrBuilder &MIB);169void addStringImm(const StringRef &Str, IRBuilder<> &B,170 std::vector<Value *> &Args);171 172// Read the series of integer operands back as a null-terminated string using173// the reverse of the logic in addStringImm.174std::string getStringImm(const MachineInstr &MI, unsigned StartIndex);175 176// Returns the string constant that the register refers to. It is assumed that177// Reg is a global value that contains a string.178std::string getStringValueFromReg(Register Reg, MachineRegisterInfo &MRI);179 180// Add the given numerical immediate to MIB.181void addNumImm(const APInt &Imm, MachineInstrBuilder &MIB);182 183// Add an OpName instruction for the given target register.184void buildOpName(Register Target, const StringRef &Name,185 MachineIRBuilder &MIRBuilder);186void buildOpName(Register Target, const StringRef &Name, MachineInstr &I,187 const SPIRVInstrInfo &TII);188 189// Add an OpDecorate instruction for the given Reg.190void buildOpDecorate(Register Reg, MachineIRBuilder &MIRBuilder,191 SPIRV::Decoration::Decoration Dec,192 const std::vector<uint32_t> &DecArgs,193 StringRef StrImm = "");194void buildOpDecorate(Register Reg, MachineInstr &I, const SPIRVInstrInfo &TII,195 SPIRV::Decoration::Decoration Dec,196 const std::vector<uint32_t> &DecArgs,197 StringRef StrImm = "");198 199// Add an OpDecorate instruction for the given Reg.200void buildOpMemberDecorate(Register Reg, MachineIRBuilder &MIRBuilder,201 SPIRV::Decoration::Decoration Dec, uint32_t Member,202 const std::vector<uint32_t> &DecArgs,203 StringRef StrImm = "");204void buildOpMemberDecorate(Register Reg, MachineInstr &I,205 const SPIRVInstrInfo &TII,206 SPIRV::Decoration::Decoration Dec, uint32_t Member,207 const std::vector<uint32_t> &DecArgs,208 StringRef StrImm = "");209 210// Add an OpDecorate instruction by "spirv.Decorations" metadata node.211void buildOpSpirvDecorations(Register Reg, MachineIRBuilder &MIRBuilder,212 const MDNode *GVarMD, const SPIRVSubtarget &ST);213 214// Return a valid position for the OpVariable instruction inside a function,215// i.e., at the beginning of the first block of the function.216MachineBasicBlock::iterator getOpVariableMBBIt(MachineInstr &I);217 218// Return a valid position for the instruction at the end of the block before219// terminators and debug instructions.220MachineBasicBlock::iterator getInsertPtValidEnd(MachineBasicBlock *MBB);221 222// Returns true if a pointer to the storage class can be casted to/from a223// pointer to the Generic storage class.224constexpr bool isGenericCastablePtr(SPIRV::StorageClass::StorageClass SC) {225 switch (SC) {226 case SPIRV::StorageClass::Workgroup:227 case SPIRV::StorageClass::CrossWorkgroup:228 case SPIRV::StorageClass::Function:229 return true;230 default:231 return false;232 }233}234 235// Convert a SPIR-V storage class to the corresponding LLVM IR address space.236// TODO: maybe the following two functions should be handled in the subtarget237// to allow for different OpenCL vs Vulkan handling.238constexpr unsigned239storageClassToAddressSpace(SPIRV::StorageClass::StorageClass SC) {240 switch (SC) {241 case SPIRV::StorageClass::Function:242 return 0;243 case SPIRV::StorageClass::CrossWorkgroup:244 return 1;245 case SPIRV::StorageClass::UniformConstant:246 return 2;247 case SPIRV::StorageClass::Workgroup:248 return 3;249 case SPIRV::StorageClass::Generic:250 return 4;251 case SPIRV::StorageClass::DeviceOnlyINTEL:252 return 5;253 case SPIRV::StorageClass::HostOnlyINTEL:254 return 6;255 case SPIRV::StorageClass::Input:256 return 7;257 case SPIRV::StorageClass::Output:258 return 8;259 case SPIRV::StorageClass::CodeSectionINTEL:260 return 9;261 case SPIRV::StorageClass::Private:262 return 10;263 case SPIRV::StorageClass::StorageBuffer:264 return 11;265 case SPIRV::StorageClass::Uniform:266 return 12;267 default:268 report_fatal_error("Unable to get address space id");269 }270}271 272// Convert an LLVM IR address space to a SPIR-V storage class.273SPIRV::StorageClass::StorageClass274addressSpaceToStorageClass(unsigned AddrSpace, const SPIRVSubtarget &STI);275 276SPIRV::MemorySemantics::MemorySemantics277getMemSemanticsForStorageClass(SPIRV::StorageClass::StorageClass SC);278 279SPIRV::MemorySemantics::MemorySemantics getMemSemantics(AtomicOrdering Ord);280 281SPIRV::Scope::Scope getMemScope(LLVMContext &Ctx, SyncScope::ID Id);282 283// Find def instruction for the given ConstReg, walking through284// spv_track_constant and ASSIGN_TYPE instructions. Updates ConstReg by def285// of OpConstant instruction.286MachineInstr *getDefInstrMaybeConstant(Register &ConstReg,287 const MachineRegisterInfo *MRI);288 289// Get constant integer value of the given ConstReg.290uint64_t getIConstVal(Register ConstReg, const MachineRegisterInfo *MRI);291 292// Get constant integer value of the given ConstReg, sign-extended.293int64_t getIConstValSext(Register ConstReg, const MachineRegisterInfo *MRI);294 295// Check if MI is a SPIR-V specific intrinsic call.296bool isSpvIntrinsic(const MachineInstr &MI, Intrinsic::ID IntrinsicID);297// Check if it's a SPIR-V specific intrinsic call.298bool isSpvIntrinsic(const Value *Arg);299 300// Get type of i-th operand of the metadata node.301Type *getMDOperandAsType(const MDNode *N, unsigned I);302 303// If OpenCL or SPIR-V builtin function name is recognized, return a demangled304// name, otherwise return an empty string.305std::string getOclOrSpirvBuiltinDemangledName(StringRef Name);306 307// Check if a string contains a builtin prefix.308bool hasBuiltinTypePrefix(StringRef Name);309 310// Check if given LLVM type is a special opaque builtin type.311bool isSpecialOpaqueType(const Type *Ty);312 313// Check if the function is an SPIR-V entry point314bool isEntryPoint(const Function &F);315 316// Parse basic scalar type name, substring TypeName, and return LLVM type.317Type *parseBasicTypeName(StringRef &TypeName, LLVMContext &Ctx);318 319// Sort blocks in a partial ordering, so each block is after all its320// dominators. This should match both the SPIR-V and the MIR requirements.321// Returns true if the function was changed.322bool sortBlocks(Function &F);323 324// Check for peeled array structs and recursively reconstitute them. In HLSL325// CBuffers, arrays may have padding between the elements, but not after the326// last element. To represent this in LLVM IR an array [N x T] will be327// represented as {[N-1 x {T, spirv.Padding}], T}. The function328// matchPeeledArrayPattern recognizes this pattern retrieving the type {T,329// spirv.Padding}, and the size N.330bool matchPeeledArrayPattern(const StructType *Ty, Type *&OriginalElementType,331 uint64_t &TotalSize);332 333// This function will turn the type {[N-1 x {T, spirv.Padding}], T} back into334// [N x {T, spirv.Padding}]. So it can be translated into SPIR-V. The offset335// decorations will be such that there will be no padding after the array when336// relevant.337Type *reconstitutePeeledArrayType(Type *Ty);338 339inline bool hasInitializer(const GlobalVariable *GV) {340 return GV->hasInitializer() && !isa<UndefValue>(GV->getInitializer());341}342 343// True if this is an instance of TypedPointerType.344inline bool isTypedPointerTy(const Type *T) {345 return T && T->getTypeID() == Type::TypedPointerTyID;346}347 348// True if this is an instance of PointerType.349inline bool isUntypedPointerTy(const Type *T) {350 return T && T->getTypeID() == Type::PointerTyID;351}352 353// True if this is an instance of PointerType or TypedPointerType.354inline bool isPointerTy(const Type *T) {355 return isUntypedPointerTy(T) || isTypedPointerTy(T);356}357 358// Get the address space of this pointer or pointer vector type for instances of359// PointerType or TypedPointerType.360inline unsigned getPointerAddressSpace(const Type *T) {361 Type *SubT = T->getScalarType();362 return SubT->getTypeID() == Type::PointerTyID363 ? cast<PointerType>(SubT)->getAddressSpace()364 : cast<TypedPointerType>(SubT)->getAddressSpace();365}366 367// Return true if the Argument is decorated with a pointee type368inline bool hasPointeeTypeAttr(Argument *Arg) {369 return Arg->hasByValAttr() || Arg->hasByRefAttr() || Arg->hasStructRetAttr();370}371 372// Return the pointee type of the argument or nullptr otherwise373inline Type *getPointeeTypeByAttr(Argument *Arg) {374 if (Arg->hasByValAttr())375 return Arg->getParamByValType();376 if (Arg->hasStructRetAttr())377 return Arg->getParamStructRetType();378 if (Arg->hasByRefAttr())379 return Arg->getParamByRefType();380 return nullptr;381}382 383inline Type *reconstructFunctionType(Function *F) {384 SmallVector<Type *> ArgTys;385 for (unsigned i = 0; i < F->arg_size(); ++i)386 ArgTys.push_back(F->getArg(i)->getType());387 return FunctionType::get(F->getReturnType(), ArgTys, F->isVarArg());388}389 390#define TYPED_PTR_TARGET_EXT_NAME "spirv.$TypedPointerType"391inline Type *getTypedPointerWrapper(Type *ElemTy, unsigned AS) {392 return TargetExtType::get(ElemTy->getContext(), TYPED_PTR_TARGET_EXT_NAME,393 {ElemTy}, {AS});394}395 396inline bool isTypedPointerWrapper(const TargetExtType *ExtTy) {397 return ExtTy->getName() == TYPED_PTR_TARGET_EXT_NAME &&398 ExtTy->getNumIntParameters() == 1 &&399 ExtTy->getNumTypeParameters() == 1;400}401 402// True if this is an instance of PointerType or TypedPointerType.403inline bool isPointerTyOrWrapper(const Type *Ty) {404 if (auto *ExtTy = dyn_cast<TargetExtType>(Ty))405 return isTypedPointerWrapper(ExtTy);406 return isPointerTy(Ty);407}408 409inline Type *applyWrappers(Type *Ty) {410 if (auto *ExtTy = dyn_cast<TargetExtType>(Ty)) {411 if (isTypedPointerWrapper(ExtTy))412 return TypedPointerType::get(applyWrappers(ExtTy->getTypeParameter(0)),413 ExtTy->getIntParameter(0));414 } else if (auto *VecTy = dyn_cast<VectorType>(Ty)) {415 Type *ElemTy = VecTy->getElementType();416 Type *NewElemTy = ElemTy->isTargetExtTy() ? applyWrappers(ElemTy) : ElemTy;417 if (NewElemTy != ElemTy)418 return VectorType::get(NewElemTy, VecTy->getElementCount());419 }420 return Ty;421}422 423inline Type *getPointeeType(const Type *Ty) {424 if (Ty) {425 if (auto PType = dyn_cast<TypedPointerType>(Ty))426 return PType->getElementType();427 else if (auto *ExtTy = dyn_cast<TargetExtType>(Ty))428 if (isTypedPointerWrapper(ExtTy))429 return ExtTy->getTypeParameter(0);430 }431 return nullptr;432}433 434inline bool isUntypedEquivalentToTyExt(Type *Ty1, Type *Ty2) {435 if (!isUntypedPointerTy(Ty1) || !Ty2)436 return false;437 if (auto *ExtTy = dyn_cast<TargetExtType>(Ty2))438 if (isTypedPointerWrapper(ExtTy) &&439 ExtTy->getTypeParameter(0) ==440 IntegerType::getInt8Ty(Ty1->getContext()) &&441 ExtTy->getIntParameter(0) == cast<PointerType>(Ty1)->getAddressSpace())442 return true;443 return false;444}445 446inline bool isEquivalentTypes(Type *Ty1, Type *Ty2) {447 return isUntypedEquivalentToTyExt(Ty1, Ty2) ||448 isUntypedEquivalentToTyExt(Ty2, Ty1);449}450 451inline Type *toTypedPointer(Type *Ty) {452 if (Type *NewTy = applyWrappers(Ty); NewTy != Ty)453 return NewTy;454 return isUntypedPointerTy(Ty)455 ? TypedPointerType::get(IntegerType::getInt8Ty(Ty->getContext()),456 getPointerAddressSpace(Ty))457 : Ty;458}459 460inline Type *toTypedFunPointer(FunctionType *FTy) {461 Type *OrigRetTy = FTy->getReturnType();462 Type *RetTy = toTypedPointer(OrigRetTy);463 bool IsUntypedPtr = false;464 for (Type *PTy : FTy->params()) {465 if (isUntypedPointerTy(PTy)) {466 IsUntypedPtr = true;467 break;468 }469 }470 if (!IsUntypedPtr && RetTy == OrigRetTy)471 return FTy;472 SmallVector<Type *> ParamTys;473 for (Type *PTy : FTy->params())474 ParamTys.push_back(toTypedPointer(PTy));475 return FunctionType::get(RetTy, ParamTys, FTy->isVarArg());476}477 478inline const Type *unifyPtrType(const Type *Ty) {479 if (auto FTy = dyn_cast<FunctionType>(Ty))480 return toTypedFunPointer(const_cast<FunctionType *>(FTy));481 return toTypedPointer(const_cast<Type *>(Ty));482}483 484inline bool isVector1(Type *Ty) {485 auto *FVTy = dyn_cast<FixedVectorType>(Ty);486 return FVTy && FVTy->getNumElements() == 1;487}488 489// Modify an LLVM type to conform with future transformations in IRTranslator.490// At the moment use cases comprise only a <1 x Type> vector. To extend when/if491// needed.492inline Type *normalizeType(Type *Ty) {493 auto *FVTy = dyn_cast<FixedVectorType>(Ty);494 if (!FVTy || FVTy->getNumElements() != 1)495 return Ty;496 // If it's a <1 x Type> vector type, replace it by the element type, because497 // it's not a legal vector type in LLT and IRTranslator will represent it as498 // the scalar eventually.499 return normalizeType(FVTy->getElementType());500}501 502inline PoisonValue *getNormalizedPoisonValue(Type *Ty) {503 return PoisonValue::get(normalizeType(Ty));504}505 506inline MetadataAsValue *buildMD(Value *Arg) {507 LLVMContext &Ctx = Arg->getContext();508 return MetadataAsValue::get(509 Ctx, MDNode::get(Ctx, ValueAsMetadata::getConstant(Arg)));510}511 512CallInst *buildIntrWithMD(Intrinsic::ID IntrID, ArrayRef<Type *> Types,513 Value *Arg, Value *Arg2, ArrayRef<Constant *> Imms,514 IRBuilder<> &B);515 516MachineInstr *getVRegDef(MachineRegisterInfo &MRI, Register Reg);517 518#define SPIRV_BACKEND_SERVICE_FUN_NAME "__spirv_backend_service_fun"519bool getVacantFunctionName(Module &M, std::string &Name);520 521void setRegClassType(Register Reg, const Type *Ty, SPIRVGlobalRegistry *GR,522 MachineIRBuilder &MIRBuilder,523 SPIRV::AccessQualifier::AccessQualifier AccessQual,524 bool EmitIR, bool Force = false);525void setRegClassType(Register Reg, const MachineInstr *SpvType,526 SPIRVGlobalRegistry *GR, MachineRegisterInfo *MRI,527 const MachineFunction &MF, bool Force = false);528Register createVirtualRegister(const MachineInstr *SpvType,529 SPIRVGlobalRegistry *GR,530 MachineRegisterInfo *MRI,531 const MachineFunction &MF);532Register createVirtualRegister(const MachineInstr *SpvType,533 SPIRVGlobalRegistry *GR,534 MachineIRBuilder &MIRBuilder);535Register createVirtualRegister(536 const Type *Ty, SPIRVGlobalRegistry *GR, MachineIRBuilder &MIRBuilder,537 SPIRV::AccessQualifier::AccessQualifier AccessQual, bool EmitIR);538 539// Return true if there is an opaque pointer type nested in the argument.540bool isNestedPointer(const Type *Ty);541 542enum FPDecorationId { NONE, RTE, RTZ, RTP, RTN, SAT };543 544inline FPDecorationId demangledPostfixToDecorationId(const std::string &S) {545 static std::unordered_map<std::string, FPDecorationId> Mapping = {546 {"rte", FPDecorationId::RTE},547 {"rtz", FPDecorationId::RTZ},548 {"rtp", FPDecorationId::RTP},549 {"rtn", FPDecorationId::RTN},550 {"sat", FPDecorationId::SAT}};551 auto It = Mapping.find(S);552 return It == Mapping.end() ? FPDecorationId::NONE : It->second;553}554 555SmallVector<MachineInstr *, 4>556createContinuedInstructions(MachineIRBuilder &MIRBuilder, unsigned Opcode,557 unsigned MinWC, unsigned ContinuedOpcode,558 ArrayRef<Register> Args, Register ReturnRegister,559 Register TypeID);560 561// Instruction selection directed by type folding.562const std::set<unsigned> &getTypeFoldingSupportedOpcodes();563bool isTypeFoldingSupported(unsigned Opcode);564 565// Get loop controls from llvm.loop. metadata.566SmallVector<unsigned, 1> getSpirvLoopControlOperandsFromLoopMetadata(Loop *L);567 568// Traversing [g]MIR accounting for pseudo-instructions.569MachineInstr *passCopy(MachineInstr *Def, const MachineRegisterInfo *MRI);570MachineInstr *getDef(const MachineOperand &MO, const MachineRegisterInfo *MRI);571MachineInstr *getImm(const MachineOperand &MO, const MachineRegisterInfo *MRI);572int64_t foldImm(const MachineOperand &MO, const MachineRegisterInfo *MRI);573unsigned getArrayComponentCount(const MachineRegisterInfo *MRI,574 const MachineInstr *ResType);575MachineBasicBlock::iterator576getFirstValidInstructionInsertPoint(MachineBasicBlock &BB);577 578std::optional<SPIRV::LinkageType::LinkageType>579getSpirvLinkageTypeFor(const SPIRVSubtarget &ST, const GlobalValue &GV);580} // namespace llvm581#endif // LLVM_LIB_TARGET_SPIRV_SPIRVUTILS_H582