1130 lines · cpp
1//===--- SPIRVUtils.cpp ---- 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#include "SPIRVUtils.h"14#include "MCTargetDesc/SPIRVBaseInfo.h"15#include "SPIRV.h"16#include "SPIRVGlobalRegistry.h"17#include "SPIRVInstrInfo.h"18#include "SPIRVSubtarget.h"19#include "llvm/ADT/StringRef.h"20#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"21#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"22#include "llvm/CodeGen/MachineInstr.h"23#include "llvm/CodeGen/MachineInstrBuilder.h"24#include "llvm/Demangle/Demangle.h"25#include "llvm/IR/IntrinsicInst.h"26#include "llvm/IR/IntrinsicsSPIRV.h"27#include <queue>28#include <vector>29 30namespace llvm {31 32// The following functions are used to add these string literals as a series of33// 32-bit integer operands with the correct format, and unpack them if necessary34// when making string comparisons in compiler passes.35// SPIR-V requires null-terminated UTF-8 strings padded to 32-bit alignment.36static uint32_t convertCharsToWord(const StringRef &Str, unsigned i) {37 uint32_t Word = 0u; // Build up this 32-bit word from 4 8-bit chars.38 for (unsigned WordIndex = 0; WordIndex < 4; ++WordIndex) {39 unsigned StrIndex = i + WordIndex;40 uint8_t CharToAdd = 0; // Initilize char as padding/null.41 if (StrIndex < Str.size()) { // If it's within the string, get a real char.42 CharToAdd = Str[StrIndex];43 }44 Word |= (CharToAdd << (WordIndex * 8));45 }46 return Word;47}48 49// Get length including padding and null terminator.50static size_t getPaddedLen(const StringRef &Str) {51 return (Str.size() + 4) & ~3;52}53 54void addStringImm(const StringRef &Str, MCInst &Inst) {55 const size_t PaddedLen = getPaddedLen(Str);56 for (unsigned i = 0; i < PaddedLen; i += 4) {57 // Add an operand for the 32-bits of chars or padding.58 Inst.addOperand(MCOperand::createImm(convertCharsToWord(Str, i)));59 }60}61 62void addStringImm(const StringRef &Str, MachineInstrBuilder &MIB) {63 const size_t PaddedLen = getPaddedLen(Str);64 for (unsigned i = 0; i < PaddedLen; i += 4) {65 // Add an operand for the 32-bits of chars or padding.66 MIB.addImm(convertCharsToWord(Str, i));67 }68}69 70void addStringImm(const StringRef &Str, IRBuilder<> &B,71 std::vector<Value *> &Args) {72 const size_t PaddedLen = getPaddedLen(Str);73 for (unsigned i = 0; i < PaddedLen; i += 4) {74 // Add a vector element for the 32-bits of chars or padding.75 Args.push_back(B.getInt32(convertCharsToWord(Str, i)));76 }77}78 79std::string getStringImm(const MachineInstr &MI, unsigned StartIndex) {80 return getSPIRVStringOperand(MI, StartIndex);81}82 83std::string getStringValueFromReg(Register Reg, MachineRegisterInfo &MRI) {84 MachineInstr *Def = getVRegDef(MRI, Reg);85 assert(Def && Def->getOpcode() == TargetOpcode::G_GLOBAL_VALUE &&86 "Expected G_GLOBAL_VALUE");87 const GlobalValue *GV = Def->getOperand(1).getGlobal();88 Value *V = GV->getOperand(0);89 const ConstantDataArray *CDA = cast<ConstantDataArray>(V);90 return CDA->getAsCString().str();91}92 93void addNumImm(const APInt &Imm, MachineInstrBuilder &MIB) {94 const auto Bitwidth = Imm.getBitWidth();95 if (Bitwidth == 1)96 return; // Already handled97 else if (Bitwidth <= 32) {98 MIB.addImm(Imm.getZExtValue());99 // Asm Printer needs this info to print floating-type correctly100 if (Bitwidth == 16)101 MIB.getInstr()->setAsmPrinterFlag(SPIRV::ASM_PRINTER_WIDTH16);102 return;103 } else if (Bitwidth <= 64) {104 uint64_t FullImm = Imm.getZExtValue();105 uint32_t LowBits = FullImm & 0xffffffff;106 uint32_t HighBits = (FullImm >> 32) & 0xffffffff;107 MIB.addImm(LowBits).addImm(HighBits);108 // Asm Printer needs this info to print 64-bit operands correctly109 MIB.getInstr()->setAsmPrinterFlag(SPIRV::ASM_PRINTER_WIDTH64);110 return;111 }112 report_fatal_error("Unsupported constant bitwidth");113}114 115void buildOpName(Register Target, const StringRef &Name,116 MachineIRBuilder &MIRBuilder) {117 if (!Name.empty()) {118 auto MIB = MIRBuilder.buildInstr(SPIRV::OpName).addUse(Target);119 addStringImm(Name, MIB);120 }121}122 123void buildOpName(Register Target, const StringRef &Name, MachineInstr &I,124 const SPIRVInstrInfo &TII) {125 if (!Name.empty()) {126 auto MIB =127 BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(SPIRV::OpName))128 .addUse(Target);129 addStringImm(Name, MIB);130 }131}132 133static void finishBuildOpDecorate(MachineInstrBuilder &MIB,134 const std::vector<uint32_t> &DecArgs,135 StringRef StrImm) {136 if (!StrImm.empty())137 addStringImm(StrImm, MIB);138 for (const auto &DecArg : DecArgs)139 MIB.addImm(DecArg);140}141 142void buildOpDecorate(Register Reg, MachineIRBuilder &MIRBuilder,143 SPIRV::Decoration::Decoration Dec,144 const std::vector<uint32_t> &DecArgs, StringRef StrImm) {145 auto MIB = MIRBuilder.buildInstr(SPIRV::OpDecorate)146 .addUse(Reg)147 .addImm(static_cast<uint32_t>(Dec));148 finishBuildOpDecorate(MIB, DecArgs, StrImm);149}150 151void buildOpDecorate(Register Reg, MachineInstr &I, const SPIRVInstrInfo &TII,152 SPIRV::Decoration::Decoration Dec,153 const std::vector<uint32_t> &DecArgs, StringRef StrImm) {154 MachineBasicBlock &MBB = *I.getParent();155 auto MIB = BuildMI(MBB, I, I.getDebugLoc(), TII.get(SPIRV::OpDecorate))156 .addUse(Reg)157 .addImm(static_cast<uint32_t>(Dec));158 finishBuildOpDecorate(MIB, DecArgs, StrImm);159}160 161void buildOpMemberDecorate(Register Reg, MachineIRBuilder &MIRBuilder,162 SPIRV::Decoration::Decoration Dec, uint32_t Member,163 const std::vector<uint32_t> &DecArgs,164 StringRef StrImm) {165 auto MIB = MIRBuilder.buildInstr(SPIRV::OpMemberDecorate)166 .addUse(Reg)167 .addImm(Member)168 .addImm(static_cast<uint32_t>(Dec));169 finishBuildOpDecorate(MIB, DecArgs, StrImm);170}171 172void buildOpMemberDecorate(Register Reg, MachineInstr &I,173 const SPIRVInstrInfo &TII,174 SPIRV::Decoration::Decoration Dec, uint32_t Member,175 const std::vector<uint32_t> &DecArgs,176 StringRef StrImm) {177 MachineBasicBlock &MBB = *I.getParent();178 auto MIB = BuildMI(MBB, I, I.getDebugLoc(), TII.get(SPIRV::OpMemberDecorate))179 .addUse(Reg)180 .addImm(Member)181 .addImm(static_cast<uint32_t>(Dec));182 finishBuildOpDecorate(MIB, DecArgs, StrImm);183}184 185void buildOpSpirvDecorations(Register Reg, MachineIRBuilder &MIRBuilder,186 const MDNode *GVarMD, const SPIRVSubtarget &ST) {187 for (unsigned I = 0, E = GVarMD->getNumOperands(); I != E; ++I) {188 auto *OpMD = dyn_cast<MDNode>(GVarMD->getOperand(I));189 if (!OpMD)190 report_fatal_error("Invalid decoration");191 if (OpMD->getNumOperands() == 0)192 report_fatal_error("Expect operand(s) of the decoration");193 ConstantInt *DecorationId =194 mdconst::dyn_extract<ConstantInt>(OpMD->getOperand(0));195 if (!DecorationId)196 report_fatal_error("Expect SPIR-V <Decoration> operand to be the first "197 "element of the decoration");198 199 // The goal of `spirv.Decorations` metadata is to provide a way to200 // represent SPIR-V entities that do not map to LLVM in an obvious way.201 // FP flags do have obvious matches between LLVM IR and SPIR-V.202 // Additionally, we have no guarantee at this point that the flags passed203 // through the decoration are not violated already in the optimizer passes.204 // Therefore, we simply ignore FP flags, including NoContraction, and205 // FPFastMathMode.206 if (DecorationId->getZExtValue() ==207 static_cast<uint32_t>(SPIRV::Decoration::NoContraction) ||208 DecorationId->getZExtValue() ==209 static_cast<uint32_t>(SPIRV::Decoration::FPFastMathMode)) {210 continue; // Ignored.211 }212 auto MIB = MIRBuilder.buildInstr(SPIRV::OpDecorate)213 .addUse(Reg)214 .addImm(static_cast<uint32_t>(DecorationId->getZExtValue()));215 for (unsigned OpI = 1, OpE = OpMD->getNumOperands(); OpI != OpE; ++OpI) {216 if (ConstantInt *OpV =217 mdconst::dyn_extract<ConstantInt>(OpMD->getOperand(OpI)))218 MIB.addImm(static_cast<uint32_t>(OpV->getZExtValue()));219 else if (MDString *OpV = dyn_cast<MDString>(OpMD->getOperand(OpI)))220 addStringImm(OpV->getString(), MIB);221 else222 report_fatal_error("Unexpected operand of the decoration");223 }224 }225}226 227MachineBasicBlock::iterator getOpVariableMBBIt(MachineInstr &I) {228 MachineFunction *MF = I.getParent()->getParent();229 MachineBasicBlock *MBB = &MF->front();230 MachineBasicBlock::iterator It = MBB->SkipPHIsAndLabels(MBB->begin()),231 E = MBB->end();232 bool IsHeader = false;233 unsigned Opcode;234 for (; It != E && It != I; ++It) {235 Opcode = It->getOpcode();236 if (Opcode == SPIRV::OpFunction || Opcode == SPIRV::OpFunctionParameter) {237 IsHeader = true;238 } else if (IsHeader &&239 !(Opcode == SPIRV::ASSIGN_TYPE || Opcode == SPIRV::OpLabel)) {240 ++It;241 break;242 }243 }244 return It;245}246 247MachineBasicBlock::iterator getInsertPtValidEnd(MachineBasicBlock *MBB) {248 MachineBasicBlock::iterator I = MBB->end();249 if (I == MBB->begin())250 return I;251 --I;252 while (I->isTerminator() || I->isDebugValue()) {253 if (I == MBB->begin())254 break;255 --I;256 }257 return I;258}259 260SPIRV::StorageClass::StorageClass261addressSpaceToStorageClass(unsigned AddrSpace, const SPIRVSubtarget &STI) {262 switch (AddrSpace) {263 case 0:264 return SPIRV::StorageClass::Function;265 case 1:266 return SPIRV::StorageClass::CrossWorkgroup;267 case 2:268 return SPIRV::StorageClass::UniformConstant;269 case 3:270 return SPIRV::StorageClass::Workgroup;271 case 4:272 return SPIRV::StorageClass::Generic;273 case 5:274 return STI.canUseExtension(SPIRV::Extension::SPV_INTEL_usm_storage_classes)275 ? SPIRV::StorageClass::DeviceOnlyINTEL276 : SPIRV::StorageClass::CrossWorkgroup;277 case 6:278 return STI.canUseExtension(SPIRV::Extension::SPV_INTEL_usm_storage_classes)279 ? SPIRV::StorageClass::HostOnlyINTEL280 : SPIRV::StorageClass::CrossWorkgroup;281 case 7:282 return SPIRV::StorageClass::Input;283 case 8:284 return SPIRV::StorageClass::Output;285 case 9:286 return SPIRV::StorageClass::CodeSectionINTEL;287 case 10:288 return SPIRV::StorageClass::Private;289 case 11:290 return SPIRV::StorageClass::StorageBuffer;291 case 12:292 return SPIRV::StorageClass::Uniform;293 default:294 report_fatal_error("Unknown address space");295 }296}297 298SPIRV::MemorySemantics::MemorySemantics299getMemSemanticsForStorageClass(SPIRV::StorageClass::StorageClass SC) {300 switch (SC) {301 case SPIRV::StorageClass::StorageBuffer:302 case SPIRV::StorageClass::Uniform:303 return SPIRV::MemorySemantics::UniformMemory;304 case SPIRV::StorageClass::Workgroup:305 return SPIRV::MemorySemantics::WorkgroupMemory;306 case SPIRV::StorageClass::CrossWorkgroup:307 return SPIRV::MemorySemantics::CrossWorkgroupMemory;308 case SPIRV::StorageClass::AtomicCounter:309 return SPIRV::MemorySemantics::AtomicCounterMemory;310 case SPIRV::StorageClass::Image:311 return SPIRV::MemorySemantics::ImageMemory;312 default:313 return SPIRV::MemorySemantics::None;314 }315}316 317SPIRV::MemorySemantics::MemorySemantics getMemSemantics(AtomicOrdering Ord) {318 switch (Ord) {319 case AtomicOrdering::Acquire:320 return SPIRV::MemorySemantics::Acquire;321 case AtomicOrdering::Release:322 return SPIRV::MemorySemantics::Release;323 case AtomicOrdering::AcquireRelease:324 return SPIRV::MemorySemantics::AcquireRelease;325 case AtomicOrdering::SequentiallyConsistent:326 return SPIRV::MemorySemantics::SequentiallyConsistent;327 case AtomicOrdering::Unordered:328 case AtomicOrdering::Monotonic:329 case AtomicOrdering::NotAtomic:330 return SPIRV::MemorySemantics::None;331 }332 llvm_unreachable(nullptr);333}334 335SPIRV::Scope::Scope getMemScope(LLVMContext &Ctx, SyncScope::ID Id) {336 // Named by337 // https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.html#_scope_id.338 // We don't need aliases for Invocation and CrossDevice, as we already have339 // them covered by "singlethread" and "" strings respectively (see340 // implementation of LLVMContext::LLVMContext()).341 static const llvm::SyncScope::ID SubGroup =342 Ctx.getOrInsertSyncScopeID("subgroup");343 static const llvm::SyncScope::ID WorkGroup =344 Ctx.getOrInsertSyncScopeID("workgroup");345 static const llvm::SyncScope::ID Device =346 Ctx.getOrInsertSyncScopeID("device");347 348 if (Id == llvm::SyncScope::SingleThread)349 return SPIRV::Scope::Invocation;350 else if (Id == llvm::SyncScope::System)351 return SPIRV::Scope::CrossDevice;352 else if (Id == SubGroup)353 return SPIRV::Scope::Subgroup;354 else if (Id == WorkGroup)355 return SPIRV::Scope::Workgroup;356 else if (Id == Device)357 return SPIRV::Scope::Device;358 return SPIRV::Scope::CrossDevice;359}360 361MachineInstr *getDefInstrMaybeConstant(Register &ConstReg,362 const MachineRegisterInfo *MRI) {363 MachineInstr *MI = MRI->getVRegDef(ConstReg);364 MachineInstr *ConstInstr =365 MI->getOpcode() == SPIRV::G_TRUNC || MI->getOpcode() == SPIRV::G_ZEXT366 ? MRI->getVRegDef(MI->getOperand(1).getReg())367 : MI;368 if (auto *GI = dyn_cast<GIntrinsic>(ConstInstr)) {369 if (GI->is(Intrinsic::spv_track_constant)) {370 ConstReg = ConstInstr->getOperand(2).getReg();371 return MRI->getVRegDef(ConstReg);372 }373 } else if (ConstInstr->getOpcode() == SPIRV::ASSIGN_TYPE) {374 ConstReg = ConstInstr->getOperand(1).getReg();375 return MRI->getVRegDef(ConstReg);376 } else if (ConstInstr->getOpcode() == TargetOpcode::G_CONSTANT ||377 ConstInstr->getOpcode() == TargetOpcode::G_FCONSTANT) {378 ConstReg = ConstInstr->getOperand(0).getReg();379 return ConstInstr;380 }381 return MRI->getVRegDef(ConstReg);382}383 384uint64_t getIConstVal(Register ConstReg, const MachineRegisterInfo *MRI) {385 const MachineInstr *MI = getDefInstrMaybeConstant(ConstReg, MRI);386 assert(MI && MI->getOpcode() == TargetOpcode::G_CONSTANT);387 return MI->getOperand(1).getCImm()->getValue().getZExtValue();388}389 390int64_t getIConstValSext(Register ConstReg, const MachineRegisterInfo *MRI) {391 const MachineInstr *MI = getDefInstrMaybeConstant(ConstReg, MRI);392 assert(MI && MI->getOpcode() == TargetOpcode::G_CONSTANT);393 return MI->getOperand(1).getCImm()->getSExtValue();394}395 396bool isSpvIntrinsic(const MachineInstr &MI, Intrinsic::ID IntrinsicID) {397 if (const auto *GI = dyn_cast<GIntrinsic>(&MI))398 return GI->is(IntrinsicID);399 return false;400}401 402Type *getMDOperandAsType(const MDNode *N, unsigned I) {403 Type *ElementTy = cast<ValueAsMetadata>(N->getOperand(I))->getType();404 return toTypedPointer(ElementTy);405}406 407// The set of names is borrowed from the SPIR-V translator.408// TODO: may be implemented in SPIRVBuiltins.td.409static bool isPipeOrAddressSpaceCastBI(const StringRef MangledName) {410 return MangledName == "write_pipe_2" || MangledName == "read_pipe_2" ||411 MangledName == "write_pipe_2_bl" || MangledName == "read_pipe_2_bl" ||412 MangledName == "write_pipe_4" || MangledName == "read_pipe_4" ||413 MangledName == "reserve_write_pipe" ||414 MangledName == "reserve_read_pipe" ||415 MangledName == "commit_write_pipe" ||416 MangledName == "commit_read_pipe" ||417 MangledName == "work_group_reserve_write_pipe" ||418 MangledName == "work_group_reserve_read_pipe" ||419 MangledName == "work_group_commit_write_pipe" ||420 MangledName == "work_group_commit_read_pipe" ||421 MangledName == "get_pipe_num_packets_ro" ||422 MangledName == "get_pipe_max_packets_ro" ||423 MangledName == "get_pipe_num_packets_wo" ||424 MangledName == "get_pipe_max_packets_wo" ||425 MangledName == "sub_group_reserve_write_pipe" ||426 MangledName == "sub_group_reserve_read_pipe" ||427 MangledName == "sub_group_commit_write_pipe" ||428 MangledName == "sub_group_commit_read_pipe" ||429 MangledName == "to_global" || MangledName == "to_local" ||430 MangledName == "to_private";431}432 433static bool isEnqueueKernelBI(const StringRef MangledName) {434 return MangledName == "__enqueue_kernel_basic" ||435 MangledName == "__enqueue_kernel_basic_events" ||436 MangledName == "__enqueue_kernel_varargs" ||437 MangledName == "__enqueue_kernel_events_varargs";438}439 440static bool isKernelQueryBI(const StringRef MangledName) {441 return MangledName == "__get_kernel_work_group_size_impl" ||442 MangledName == "__get_kernel_sub_group_count_for_ndrange_impl" ||443 MangledName == "__get_kernel_max_sub_group_size_for_ndrange_impl" ||444 MangledName == "__get_kernel_preferred_work_group_size_multiple_impl";445}446 447static bool isNonMangledOCLBuiltin(StringRef Name) {448 if (!Name.starts_with("__"))449 return false;450 451 return isEnqueueKernelBI(Name) || isKernelQueryBI(Name) ||452 isPipeOrAddressSpaceCastBI(Name.drop_front(2)) ||453 Name == "__translate_sampler_initializer";454}455 456std::string getOclOrSpirvBuiltinDemangledName(StringRef Name) {457 bool IsNonMangledOCL = isNonMangledOCLBuiltin(Name);458 bool IsNonMangledSPIRV = Name.starts_with("__spirv_");459 bool IsNonMangledHLSL = Name.starts_with("__hlsl_");460 bool IsMangled = Name.starts_with("_Z");461 462 // Otherwise use simple demangling to return the function name.463 if (IsNonMangledOCL || IsNonMangledSPIRV || IsNonMangledHLSL || !IsMangled)464 return Name.str();465 466 // Try to use the itanium demangler.467 if (char *DemangledName = itaniumDemangle(Name.data())) {468 std::string Result = DemangledName;469 free(DemangledName);470 return Result;471 }472 473 // Autocheck C++, maybe need to do explicit check of the source language.474 // OpenCL C++ built-ins are declared in cl namespace.475 // TODO: consider using 'St' abbriviation for cl namespace mangling.476 // Similar to ::std:: in C++.477 size_t Start, Len = 0;478 size_t DemangledNameLenStart = 2;479 if (Name.starts_with("_ZN")) {480 // Skip CV and ref qualifiers.481 size_t NameSpaceStart = Name.find_first_not_of("rVKRO", 3);482 // All built-ins are in the ::cl:: namespace.483 if (Name.substr(NameSpaceStart, 11) != "2cl7__spirv")484 return std::string();485 DemangledNameLenStart = NameSpaceStart + 11;486 }487 Start = Name.find_first_not_of("0123456789", DemangledNameLenStart);488 [[maybe_unused]] bool Error =489 Name.substr(DemangledNameLenStart, Start - DemangledNameLenStart)490 .getAsInteger(10, Len);491 assert(!Error && "Failed to parse demangled name length");492 return Name.substr(Start, Len).str();493}494 495bool hasBuiltinTypePrefix(StringRef Name) {496 if (Name.starts_with("opencl.") || Name.starts_with("ocl_") ||497 Name.starts_with("spirv."))498 return true;499 return false;500}501 502bool isSpecialOpaqueType(const Type *Ty) {503 if (const TargetExtType *ExtTy = dyn_cast<TargetExtType>(Ty))504 return isTypedPointerWrapper(ExtTy)505 ? false506 : hasBuiltinTypePrefix(ExtTy->getName());507 508 return false;509}510 511bool isEntryPoint(const Function &F) {512 // OpenCL handling: any function with the SPIR_KERNEL513 // calling convention will be a potential entry point.514 if (F.getCallingConv() == CallingConv::SPIR_KERNEL)515 return true;516 517 // HLSL handling: special attribute are emitted from the518 // front-end.519 if (F.getFnAttribute("hlsl.shader").isValid())520 return true;521 522 return false;523}524 525Type *parseBasicTypeName(StringRef &TypeName, LLVMContext &Ctx) {526 TypeName.consume_front("atomic_");527 if (TypeName.consume_front("void"))528 return Type::getVoidTy(Ctx);529 else if (TypeName.consume_front("bool") || TypeName.consume_front("_Bool"))530 return Type::getIntNTy(Ctx, 1);531 else if (TypeName.consume_front("char") ||532 TypeName.consume_front("signed char") ||533 TypeName.consume_front("unsigned char") ||534 TypeName.consume_front("uchar"))535 return Type::getInt8Ty(Ctx);536 else if (TypeName.consume_front("short") ||537 TypeName.consume_front("signed short") ||538 TypeName.consume_front("unsigned short") ||539 TypeName.consume_front("ushort"))540 return Type::getInt16Ty(Ctx);541 else if (TypeName.consume_front("int") ||542 TypeName.consume_front("signed int") ||543 TypeName.consume_front("unsigned int") ||544 TypeName.consume_front("uint"))545 return Type::getInt32Ty(Ctx);546 else if (TypeName.consume_front("long") ||547 TypeName.consume_front("signed long") ||548 TypeName.consume_front("unsigned long") ||549 TypeName.consume_front("ulong"))550 return Type::getInt64Ty(Ctx);551 else if (TypeName.consume_front("half") ||552 TypeName.consume_front("_Float16") ||553 TypeName.consume_front("__fp16"))554 return Type::getHalfTy(Ctx);555 else if (TypeName.consume_front("float"))556 return Type::getFloatTy(Ctx);557 else if (TypeName.consume_front("double"))558 return Type::getDoubleTy(Ctx);559 560 // Unable to recognize SPIRV type name561 return nullptr;562}563 564std::unordered_set<BasicBlock *>565PartialOrderingVisitor::getReachableFrom(BasicBlock *Start) {566 std::queue<BasicBlock *> ToVisit;567 ToVisit.push(Start);568 569 std::unordered_set<BasicBlock *> Output;570 while (ToVisit.size() != 0) {571 BasicBlock *BB = ToVisit.front();572 ToVisit.pop();573 574 if (Output.count(BB) != 0)575 continue;576 Output.insert(BB);577 578 for (BasicBlock *Successor : successors(BB)) {579 if (DT.dominates(Successor, BB))580 continue;581 ToVisit.push(Successor);582 }583 }584 585 return Output;586}587 588bool PartialOrderingVisitor::CanBeVisited(BasicBlock *BB) const {589 for (BasicBlock *P : predecessors(BB)) {590 // Ignore back-edges.591 if (DT.dominates(BB, P))592 continue;593 594 // One of the predecessor hasn't been visited. Not ready yet.595 if (BlockToOrder.count(P) == 0)596 return false;597 598 // If the block is a loop exit, the loop must be finished before599 // we can continue.600 Loop *L = LI.getLoopFor(P);601 if (L == nullptr || L->contains(BB))602 continue;603 604 // SPIR-V requires a single back-edge. And the backend first605 // step transforms loops into the simplified format. If we have606 // more than 1 back-edge, something is wrong.607 assert(L->getNumBackEdges() <= 1);608 609 // If the loop has no latch, loop's rank won't matter, so we can610 // proceed.611 BasicBlock *Latch = L->getLoopLatch();612 assert(Latch);613 if (Latch == nullptr)614 continue;615 616 // The latch is not ready yet, let's wait.617 if (BlockToOrder.count(Latch) == 0)618 return false;619 }620 621 return true;622}623 624size_t PartialOrderingVisitor::GetNodeRank(BasicBlock *BB) const {625 auto It = BlockToOrder.find(BB);626 if (It != BlockToOrder.end())627 return It->second.Rank;628 629 size_t result = 0;630 for (BasicBlock *P : predecessors(BB)) {631 // Ignore back-edges.632 if (DT.dominates(BB, P))633 continue;634 635 auto Iterator = BlockToOrder.end();636 Loop *L = LI.getLoopFor(P);637 BasicBlock *Latch = L ? L->getLoopLatch() : nullptr;638 639 // If the predecessor is either outside a loop, or part of640 // the same loop, simply take its rank + 1.641 if (L == nullptr || L->contains(BB) || Latch == nullptr) {642 Iterator = BlockToOrder.find(P);643 } else {644 // Otherwise, take the loop's rank (highest rank in the loop) as base.645 // Since loops have a single latch, highest rank is easy to find.646 // If the loop has no latch, then it doesn't matter.647 Iterator = BlockToOrder.find(Latch);648 }649 650 assert(Iterator != BlockToOrder.end());651 result = std::max(result, Iterator->second.Rank + 1);652 }653 654 return result;655}656 657size_t PartialOrderingVisitor::visit(BasicBlock *BB, size_t Unused) {658 ToVisit.push(BB);659 Queued.insert(BB);660 661 size_t QueueIndex = 0;662 while (ToVisit.size() != 0) {663 BasicBlock *BB = ToVisit.front();664 ToVisit.pop();665 666 if (!CanBeVisited(BB)) {667 ToVisit.push(BB);668 if (QueueIndex >= ToVisit.size())669 llvm::report_fatal_error(670 "No valid candidate in the queue. Is the graph reducible?");671 QueueIndex++;672 continue;673 }674 675 QueueIndex = 0;676 size_t Rank = GetNodeRank(BB);677 OrderInfo Info = {Rank, BlockToOrder.size()};678 BlockToOrder.emplace(BB, Info);679 680 for (BasicBlock *S : successors(BB)) {681 if (Queued.count(S) != 0)682 continue;683 ToVisit.push(S);684 Queued.insert(S);685 }686 }687 688 return 0;689}690 691PartialOrderingVisitor::PartialOrderingVisitor(Function &F) {692 DT.recalculate(F);693 LI = LoopInfo(DT);694 695 visit(&*F.begin(), 0);696 697 Order.reserve(F.size());698 for (auto &[BB, Info] : BlockToOrder)699 Order.emplace_back(BB);700 701 std::sort(Order.begin(), Order.end(), [&](const auto &LHS, const auto &RHS) {702 return compare(LHS, RHS);703 });704}705 706bool PartialOrderingVisitor::compare(const BasicBlock *LHS,707 const BasicBlock *RHS) const {708 const OrderInfo &InfoLHS = BlockToOrder.at(const_cast<BasicBlock *>(LHS));709 const OrderInfo &InfoRHS = BlockToOrder.at(const_cast<BasicBlock *>(RHS));710 if (InfoLHS.Rank != InfoRHS.Rank)711 return InfoLHS.Rank < InfoRHS.Rank;712 return InfoLHS.TraversalIndex < InfoRHS.TraversalIndex;713}714 715void PartialOrderingVisitor::partialOrderVisit(716 BasicBlock &Start, std::function<bool(BasicBlock *)> Op) {717 std::unordered_set<BasicBlock *> Reachable = getReachableFrom(&Start);718 assert(BlockToOrder.count(&Start) != 0);719 720 // Skipping blocks with a rank inferior to |Start|'s rank.721 auto It = Order.begin();722 while (It != Order.end() && *It != &Start)723 ++It;724 725 // This is unexpected. Worst case |Start| is the last block,726 // so It should point to the last block, not past-end.727 assert(It != Order.end());728 729 // By default, there is no rank limit. Setting it to the maximum value.730 std::optional<size_t> EndRank = std::nullopt;731 for (; It != Order.end(); ++It) {732 if (EndRank.has_value() && BlockToOrder[*It].Rank > *EndRank)733 break;734 735 if (Reachable.count(*It) == 0) {736 continue;737 }738 739 if (!Op(*It)) {740 EndRank = BlockToOrder[*It].Rank;741 }742 }743}744 745bool sortBlocks(Function &F) {746 if (F.size() == 0)747 return false;748 749 bool Modified = false;750 std::vector<BasicBlock *> Order;751 Order.reserve(F.size());752 753 ReversePostOrderTraversal<Function *> RPOT(&F);754 llvm::append_range(Order, RPOT);755 756 assert(&*F.begin() == Order[0]);757 BasicBlock *LastBlock = &*F.begin();758 for (BasicBlock *BB : Order) {759 if (BB != LastBlock && &*LastBlock->getNextNode() != BB) {760 Modified = true;761 BB->moveAfter(LastBlock);762 }763 LastBlock = BB;764 }765 766 return Modified;767}768 769MachineInstr *getVRegDef(MachineRegisterInfo &MRI, Register Reg) {770 MachineInstr *MaybeDef = MRI.getVRegDef(Reg);771 if (MaybeDef && MaybeDef->getOpcode() == SPIRV::ASSIGN_TYPE)772 MaybeDef = MRI.getVRegDef(MaybeDef->getOperand(1).getReg());773 return MaybeDef;774}775 776bool getVacantFunctionName(Module &M, std::string &Name) {777 // It's a bit of paranoia, but still we don't want to have even a chance that778 // the loop will work for too long.779 constexpr unsigned MaxIters = 1024;780 for (unsigned I = 0; I < MaxIters; ++I) {781 std::string OrdName = Name + Twine(I).str();782 if (!M.getFunction(OrdName)) {783 Name = std::move(OrdName);784 return true;785 }786 }787 return false;788}789 790// Assign SPIR-V type to the register. If the register has no valid assigned791// class, set register LLT type and class according to the SPIR-V type.792void setRegClassType(Register Reg, SPIRVType *SpvType, SPIRVGlobalRegistry *GR,793 MachineRegisterInfo *MRI, const MachineFunction &MF,794 bool Force) {795 GR->assignSPIRVTypeToVReg(SpvType, Reg, MF);796 if (!MRI->getRegClassOrNull(Reg) || Force) {797 MRI->setRegClass(Reg, GR->getRegClass(SpvType));798 MRI->setType(Reg, GR->getRegType(SpvType));799 }800}801 802// Create a SPIR-V type, assign SPIR-V type to the register. If the register has803// no valid assigned class, set register LLT type and class according to the804// SPIR-V type.805void setRegClassType(Register Reg, const Type *Ty, SPIRVGlobalRegistry *GR,806 MachineIRBuilder &MIRBuilder,807 SPIRV::AccessQualifier::AccessQualifier AccessQual,808 bool EmitIR, bool Force) {809 setRegClassType(Reg,810 GR->getOrCreateSPIRVType(Ty, MIRBuilder, AccessQual, EmitIR),811 GR, MIRBuilder.getMRI(), MIRBuilder.getMF(), Force);812}813 814// Create a virtual register and assign SPIR-V type to the register. Set815// register LLT type and class according to the SPIR-V type.816Register createVirtualRegister(SPIRVType *SpvType, SPIRVGlobalRegistry *GR,817 MachineRegisterInfo *MRI,818 const MachineFunction &MF) {819 Register Reg = MRI->createVirtualRegister(GR->getRegClass(SpvType));820 MRI->setType(Reg, GR->getRegType(SpvType));821 GR->assignSPIRVTypeToVReg(SpvType, Reg, MF);822 return Reg;823}824 825// Create a virtual register and assign SPIR-V type to the register. Set826// register LLT type and class according to the SPIR-V type.827Register createVirtualRegister(SPIRVType *SpvType, SPIRVGlobalRegistry *GR,828 MachineIRBuilder &MIRBuilder) {829 return createVirtualRegister(SpvType, GR, MIRBuilder.getMRI(),830 MIRBuilder.getMF());831}832 833// Create a SPIR-V type, virtual register and assign SPIR-V type to the834// register. Set register LLT type and class according to the SPIR-V type.835Register createVirtualRegister(836 const Type *Ty, SPIRVGlobalRegistry *GR, MachineIRBuilder &MIRBuilder,837 SPIRV::AccessQualifier::AccessQualifier AccessQual, bool EmitIR) {838 return createVirtualRegister(839 GR->getOrCreateSPIRVType(Ty, MIRBuilder, AccessQual, EmitIR), GR,840 MIRBuilder);841}842 843CallInst *buildIntrWithMD(Intrinsic::ID IntrID, ArrayRef<Type *> Types,844 Value *Arg, Value *Arg2, ArrayRef<Constant *> Imms,845 IRBuilder<> &B) {846 SmallVector<Value *, 4> Args;847 Args.push_back(Arg2);848 Args.push_back(buildMD(Arg));849 llvm::append_range(Args, Imms);850 return B.CreateIntrinsic(IntrID, {Types}, Args);851}852 853// Return true if there is an opaque pointer type nested in the argument.854bool isNestedPointer(const Type *Ty) {855 if (Ty->isPtrOrPtrVectorTy())856 return true;857 if (const FunctionType *RefTy = dyn_cast<FunctionType>(Ty)) {858 if (isNestedPointer(RefTy->getReturnType()))859 return true;860 for (const Type *ArgTy : RefTy->params())861 if (isNestedPointer(ArgTy))862 return true;863 return false;864 }865 if (const ArrayType *RefTy = dyn_cast<ArrayType>(Ty))866 return isNestedPointer(RefTy->getElementType());867 return false;868}869 870bool isSpvIntrinsic(const Value *Arg) {871 if (const auto *II = dyn_cast<IntrinsicInst>(Arg))872 if (Function *F = II->getCalledFunction())873 if (F->getName().starts_with("llvm.spv."))874 return true;875 return false;876}877 878// Function to create continued instructions for SPV_INTEL_long_composites879// extension880SmallVector<MachineInstr *, 4>881createContinuedInstructions(MachineIRBuilder &MIRBuilder, unsigned Opcode,882 unsigned MinWC, unsigned ContinuedOpcode,883 ArrayRef<Register> Args, Register ReturnRegister,884 Register TypeID) {885 886 SmallVector<MachineInstr *, 4> Instructions;887 constexpr unsigned MaxWordCount = UINT16_MAX;888 const size_t NumElements = Args.size();889 size_t MaxNumElements = MaxWordCount - MinWC;890 size_t SPIRVStructNumElements = NumElements;891 892 if (NumElements > MaxNumElements) {893 // Do adjustments for continued instructions which always had only one894 // minumum word count.895 SPIRVStructNumElements = MaxNumElements;896 MaxNumElements = MaxWordCount - 1;897 }898 899 auto MIB =900 MIRBuilder.buildInstr(Opcode).addDef(ReturnRegister).addUse(TypeID);901 902 for (size_t I = 0; I < SPIRVStructNumElements; ++I)903 MIB.addUse(Args[I]);904 905 Instructions.push_back(MIB.getInstr());906 907 for (size_t I = SPIRVStructNumElements; I < NumElements;908 I += MaxNumElements) {909 auto MIB = MIRBuilder.buildInstr(ContinuedOpcode);910 for (size_t J = I; J < std::min(I + MaxNumElements, NumElements); ++J)911 MIB.addUse(Args[J]);912 Instructions.push_back(MIB.getInstr());913 }914 return Instructions;915}916 917SmallVector<unsigned, 1> getSpirvLoopControlOperandsFromLoopMetadata(Loop *L) {918 unsigned LC = SPIRV::LoopControl::None;919 // Currently used only to store PartialCount value. Later when other920 // LoopControls are added - this map should be sorted before making921 // them loop_merge operands to satisfy 3.23. Loop Control requirements.922 std::vector<std::pair<unsigned, unsigned>> MaskToValueMap;923 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable")) {924 LC |= SPIRV::LoopControl::DontUnroll;925 } else {926 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable") ||927 getBooleanLoopAttribute(L, "llvm.loop.unroll.full")) {928 LC |= SPIRV::LoopControl::Unroll;929 }930 std::optional<int> Count =931 getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");932 if (Count && Count != 1) {933 LC |= SPIRV::LoopControl::PartialCount;934 MaskToValueMap.emplace_back(935 std::make_pair(SPIRV::LoopControl::PartialCount, *Count));936 }937 }938 SmallVector<unsigned, 1> Result = {LC};939 for (auto &[Mask, Val] : MaskToValueMap)940 Result.push_back(Val);941 return Result;942}943 944const std::set<unsigned> &getTypeFoldingSupportedOpcodes() {945 // clang-format off946 static const std::set<unsigned> TypeFoldingSupportingOpcs = {947 TargetOpcode::G_ADD,948 TargetOpcode::G_FADD,949 TargetOpcode::G_STRICT_FADD,950 TargetOpcode::G_SUB,951 TargetOpcode::G_FSUB,952 TargetOpcode::G_STRICT_FSUB,953 TargetOpcode::G_MUL,954 TargetOpcode::G_FMUL,955 TargetOpcode::G_STRICT_FMUL,956 TargetOpcode::G_SDIV,957 TargetOpcode::G_UDIV,958 TargetOpcode::G_FDIV,959 TargetOpcode::G_STRICT_FDIV,960 TargetOpcode::G_SREM,961 TargetOpcode::G_UREM,962 TargetOpcode::G_FREM,963 TargetOpcode::G_STRICT_FREM,964 TargetOpcode::G_FNEG,965 TargetOpcode::G_CONSTANT,966 TargetOpcode::G_FCONSTANT,967 TargetOpcode::G_AND,968 TargetOpcode::G_OR,969 TargetOpcode::G_XOR,970 TargetOpcode::G_SHL,971 TargetOpcode::G_ASHR,972 TargetOpcode::G_LSHR,973 TargetOpcode::G_SELECT,974 TargetOpcode::G_EXTRACT_VECTOR_ELT,975 };976 // clang-format on977 return TypeFoldingSupportingOpcs;978}979 980bool isTypeFoldingSupported(unsigned Opcode) {981 return getTypeFoldingSupportedOpcodes().count(Opcode) > 0;982}983 984// Traversing [g]MIR accounting for pseudo-instructions.985MachineInstr *passCopy(MachineInstr *Def, const MachineRegisterInfo *MRI) {986 return (Def->getOpcode() == SPIRV::ASSIGN_TYPE ||987 Def->getOpcode() == TargetOpcode::COPY)988 ? MRI->getVRegDef(Def->getOperand(1).getReg())989 : Def;990}991 992MachineInstr *getDef(const MachineOperand &MO, const MachineRegisterInfo *MRI) {993 if (MachineInstr *Def = MRI->getVRegDef(MO.getReg()))994 return passCopy(Def, MRI);995 return nullptr;996}997 998MachineInstr *getImm(const MachineOperand &MO, const MachineRegisterInfo *MRI) {999 if (MachineInstr *Def = getDef(MO, MRI)) {1000 if (Def->getOpcode() == TargetOpcode::G_CONSTANT ||1001 Def->getOpcode() == SPIRV::OpConstantI)1002 return Def;1003 }1004 return nullptr;1005}1006 1007int64_t foldImm(const MachineOperand &MO, const MachineRegisterInfo *MRI) {1008 if (MachineInstr *Def = getImm(MO, MRI)) {1009 if (Def->getOpcode() == SPIRV::OpConstantI)1010 return Def->getOperand(2).getImm();1011 if (Def->getOpcode() == TargetOpcode::G_CONSTANT)1012 return Def->getOperand(1).getCImm()->getZExtValue();1013 }1014 llvm_unreachable("Unexpected integer constant pattern");1015}1016 1017unsigned getArrayComponentCount(const MachineRegisterInfo *MRI,1018 const MachineInstr *ResType) {1019 return foldImm(ResType->getOperand(2), MRI);1020}1021 1022MachineBasicBlock::iterator1023getFirstValidInstructionInsertPoint(MachineBasicBlock &BB) {1024 // Find the position to insert the OpVariable instruction.1025 // We will insert it after the last OpFunctionParameter, if any, or1026 // after OpFunction otherwise.1027 MachineBasicBlock::iterator VarPos = BB.begin();1028 while (VarPos != BB.end() && VarPos->getOpcode() != SPIRV::OpFunction) {1029 ++VarPos;1030 }1031 // Advance VarPos to the next instruction after OpFunction, it will either1032 // be an OpFunctionParameter, so that we can start the next loop, or the1033 // position to insert the OpVariable instruction.1034 ++VarPos;1035 while (VarPos != BB.end() &&1036 VarPos->getOpcode() == SPIRV::OpFunctionParameter) {1037 ++VarPos;1038 }1039 // VarPos is now pointing at after the last OpFunctionParameter, if any,1040 // or after OpFunction, if no parameters.1041 return VarPos != BB.end() && VarPos->getOpcode() == SPIRV::OpLabel ? ++VarPos1042 : VarPos;1043}1044 1045bool matchPeeledArrayPattern(const StructType *Ty, Type *&OriginalElementType,1046 uint64_t &TotalSize) {1047 // An array of N padded structs is represented as {[N-1 x <{T, pad}>], T}.1048 if (Ty->getStructNumElements() != 2)1049 return false;1050 1051 Type *FirstElement = Ty->getStructElementType(0);1052 Type *SecondElement = Ty->getStructElementType(1);1053 1054 if (!FirstElement->isArrayTy())1055 return false;1056 1057 Type *ArrayElementType = FirstElement->getArrayElementType();1058 if (!ArrayElementType->isStructTy() ||1059 ArrayElementType->getStructNumElements() != 2)1060 return false;1061 1062 Type *T_in_struct = ArrayElementType->getStructElementType(0);1063 if (T_in_struct != SecondElement)1064 return false;1065 1066 auto *Padding_in_struct =1067 dyn_cast<TargetExtType>(ArrayElementType->getStructElementType(1));1068 if (!Padding_in_struct || Padding_in_struct->getName() != "spirv.Padding")1069 return false;1070 1071 const uint64_t ArraySize = FirstElement->getArrayNumElements();1072 TotalSize = ArraySize + 1;1073 OriginalElementType = ArrayElementType;1074 return true;1075}1076 1077Type *reconstitutePeeledArrayType(Type *Ty) {1078 if (!Ty->isStructTy())1079 return Ty;1080 1081 auto *STy = cast<StructType>(Ty);1082 Type *OriginalElementType = nullptr;1083 uint64_t TotalSize = 0;1084 if (matchPeeledArrayPattern(STy, OriginalElementType, TotalSize)) {1085 Type *ResultTy = ArrayType::get(1086 reconstitutePeeledArrayType(OriginalElementType), TotalSize);1087 return ResultTy;1088 }1089 1090 SmallVector<Type *, 4> NewElementTypes;1091 bool Changed = false;1092 for (Type *ElementTy : STy->elements()) {1093 Type *NewElementTy = reconstitutePeeledArrayType(ElementTy);1094 if (NewElementTy != ElementTy)1095 Changed = true;1096 NewElementTypes.push_back(NewElementTy);1097 }1098 1099 if (!Changed)1100 return Ty;1101 1102 Type *ResultTy;1103 if (STy->isLiteral())1104 ResultTy =1105 StructType::get(STy->getContext(), NewElementTypes, STy->isPacked());1106 else {1107 auto *NewTy = StructType::create(STy->getContext(), STy->getName());1108 NewTy->setBody(NewElementTypes, STy->isPacked());1109 ResultTy = NewTy;1110 }1111 return ResultTy;1112}1113 1114std::optional<SPIRV::LinkageType::LinkageType>1115getSpirvLinkageTypeFor(const SPIRVSubtarget &ST, const GlobalValue &GV) {1116 if (GV.hasLocalLinkage() || GV.hasHiddenVisibility())1117 return std::nullopt;1118 1119 if (GV.isDeclarationForLinker())1120 return SPIRV::LinkageType::Import;1121 1122 if (GV.hasLinkOnceODRLinkage() &&1123 ST.canUseExtension(SPIRV::Extension::SPV_KHR_linkonce_odr))1124 return SPIRV::LinkageType::LinkOnceODR;1125 1126 return SPIRV::LinkageType::Export;1127}1128 1129} // namespace llvm1130