brintos / llvm-project-archived public Read only

1//===-- SPIRVEmitIntrinsics.cpp - emit SPIRV intrinsics ---------*- 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// The pass emits SPIRV intrinsics keeping essential high-level information for10// the translation of LLVM IR to SPIR-V.11//12//===----------------------------------------------------------------------===//13 14#include "SPIRV.h"15#include "SPIRVBuiltins.h"16#include "SPIRVSubtarget.h"17#include "SPIRVTargetMachine.h"18#include "SPIRVUtils.h"19#include "llvm/ADT/DenseSet.h"20#include "llvm/ADT/StringSet.h"21#include "llvm/IR/IRBuilder.h"22#include "llvm/IR/InstIterator.h"23#include "llvm/IR/InstVisitor.h"24#include "llvm/IR/IntrinsicsSPIRV.h"25#include "llvm/IR/PatternMatch.h"26#include "llvm/IR/TypedPointerType.h"27#include "llvm/Transforms/Utils/Local.h"28 29#include <cassert>30#include <queue>31#include <unordered_set>32 33// This pass performs the following transformation on LLVM IR level required34// for the following translation to SPIR-V:35// - replaces direct usages of aggregate constants with target-specific36//   intrinsics;37// - replaces aggregates-related instructions (extract/insert, ld/st, etc)38//   with a target-specific intrinsics;39// - emits intrinsics for the global variable initializers since IRTranslator40//   doesn't handle them and it's not very convenient to translate them41//   ourselves;42// - emits intrinsics to keep track of the string names assigned to the values;43// - emits intrinsics to keep track of constants (this is necessary to have an44//   LLVM IR constant after the IRTranslation is completed) for their further45//   deduplication;46// - emits intrinsics to keep track of original LLVM types of the values47//   to be able to emit proper SPIR-V types eventually.48//49// TODO: consider removing spv.track.constant in favor of spv.assign.type.50 51using namespace llvm;52 53namespace llvm::SPIRV {54#define GET_BuiltinGroup_DECL55#include "SPIRVGenTables.inc"56} // namespace llvm::SPIRV57 58namespace {59 60class SPIRVEmitIntrinsics61    : public ModulePass,62      public InstVisitor<SPIRVEmitIntrinsics, Instruction *> {63  SPIRVTargetMachine *TM = nullptr;64  SPIRVGlobalRegistry *GR = nullptr;65  Function *CurrF = nullptr;66  bool TrackConstants = true;67  bool HaveFunPtrs = false;68  DenseMap<Instruction *, Constant *> AggrConsts;69  DenseMap<Instruction *, Type *> AggrConstTypes;70  DenseSet<Instruction *> AggrStores;71  std::unordered_set<Value *> Named;72 73  // map of function declarations to <pointer arg index => element type>74  DenseMap<Function *, SmallVector<std::pair<unsigned, Type *>>> FDeclPtrTys;75 76  // a register of Instructions that don't have a complete type definition77  bool CanTodoType = true;78  unsigned TodoTypeSz = 0;79  DenseMap<Value *, bool> TodoType;80  void insertTodoType(Value *Op) {81    // TODO: add isa<CallInst>(Op) to no-insert82    if (CanTodoType && !isa<GetElementPtrInst>(Op)) {83      auto It = TodoType.try_emplace(Op, true);84      if (It.second)85        ++TodoTypeSz;86    }87  }88  void eraseTodoType(Value *Op) {89    auto It = TodoType.find(Op);90    if (It != TodoType.end() && It->second) {91      It->second = false;92      --TodoTypeSz;93    }94  }95  bool isTodoType(Value *Op) {96    if (isa<GetElementPtrInst>(Op))97      return false;98    auto It = TodoType.find(Op);99    return It != TodoType.end() && It->second;100  }101  // a register of Instructions that were visited by deduceOperandElementType()102  // to validate operand types with an instruction103  std::unordered_set<Instruction *> TypeValidated;104 105  // well known result types of builtins106  enum WellKnownTypes { Event };107 108  // deduce element type of untyped pointers109  Type *deduceElementType(Value *I, bool UnknownElemTypeI8);110  Type *deduceElementTypeHelper(Value *I, bool UnknownElemTypeI8);111  Type *deduceElementTypeHelper(Value *I, std::unordered_set<Value *> &Visited,112                                bool UnknownElemTypeI8,113                                bool IgnoreKnownType = false);114  Type *deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,115                                     bool UnknownElemTypeI8);116  Type *deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,117                                     std::unordered_set<Value *> &Visited,118                                     bool UnknownElemTypeI8);119  Type *deduceElementTypeByUsersDeep(Value *Op,120                                     std::unordered_set<Value *> &Visited,121                                     bool UnknownElemTypeI8);122  void maybeAssignPtrType(Type *&Ty, Value *I, Type *RefTy,123                          bool UnknownElemTypeI8);124 125  // deduce nested types of composites126  Type *deduceNestedTypeHelper(User *U, bool UnknownElemTypeI8);127  Type *deduceNestedTypeHelper(User *U, Type *Ty,128                               std::unordered_set<Value *> &Visited,129                               bool UnknownElemTypeI8);130 131  // deduce Types of operands of the Instruction if possible132  void deduceOperandElementType(Instruction *I,133                                SmallPtrSet<Instruction *, 4> *IncompleteRets,134                                const SmallPtrSet<Value *, 4> *AskOps = nullptr,135                                bool IsPostprocessing = false);136 137  void preprocessCompositeConstants(IRBuilder<> &B);138  void preprocessUndefs(IRBuilder<> &B);139 140  Type *reconstructType(Value *Op, bool UnknownElemTypeI8,141                        bool IsPostprocessing);142 143  void replaceMemInstrUses(Instruction *Old, Instruction *New, IRBuilder<> &B);144  void processInstrAfterVisit(Instruction *I, IRBuilder<> &B);145  bool insertAssignPtrTypeIntrs(Instruction *I, IRBuilder<> &B,146                                bool UnknownElemTypeI8);147  void insertAssignTypeIntrs(Instruction *I, IRBuilder<> &B);148  void insertAssignPtrTypeTargetExt(TargetExtType *AssignedType, Value *V,149                                    IRBuilder<> &B);150  void replacePointerOperandWithPtrCast(Instruction *I, Value *Pointer,151                                        Type *ExpectedElementType,152                                        unsigned OperandToReplace,153                                        IRBuilder<> &B);154  void insertPtrCastOrAssignTypeInstr(Instruction *I, IRBuilder<> &B);155  bool shouldTryToAddMemAliasingDecoration(Instruction *Inst);156  void insertSpirvDecorations(Instruction *I, IRBuilder<> &B);157  void insertConstantsForFPFastMathDefault(Module &M);158  void processGlobalValue(GlobalVariable &GV, IRBuilder<> &B);159  void processParamTypes(Function *F, IRBuilder<> &B);160  void processParamTypesByFunHeader(Function *F, IRBuilder<> &B);161  Type *deduceFunParamElementType(Function *F, unsigned OpIdx);162  Type *deduceFunParamElementType(Function *F, unsigned OpIdx,163                                  std::unordered_set<Function *> &FVisited);164 165  bool deduceOperandElementTypeCalledFunction(166      CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,167      Type *&KnownElemTy, bool &Incomplete);168  void deduceOperandElementTypeFunctionPointer(169      CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,170      Type *&KnownElemTy, bool IsPostprocessing);171  bool deduceOperandElementTypeFunctionRet(172      Instruction *I, SmallPtrSet<Instruction *, 4> *IncompleteRets,173      const SmallPtrSet<Value *, 4> *AskOps, bool IsPostprocessing,174      Type *&KnownElemTy, Value *Op, Function *F);175 176  CallInst *buildSpvPtrcast(Function *F, Value *Op, Type *ElemTy);177  void replaceUsesOfWithSpvPtrcast(Value *Op, Type *ElemTy, Instruction *I,178                                   DenseMap<Function *, CallInst *> Ptrcasts);179  void propagateElemType(Value *Op, Type *ElemTy,180                         DenseSet<std::pair<Value *, Value *>> &VisitedSubst);181  void182  propagateElemTypeRec(Value *Op, Type *PtrElemTy, Type *CastElemTy,183                       DenseSet<std::pair<Value *, Value *>> &VisitedSubst);184  void propagateElemTypeRec(Value *Op, Type *PtrElemTy, Type *CastElemTy,185                            DenseSet<std::pair<Value *, Value *>> &VisitedSubst,186                            std::unordered_set<Value *> &Visited,187                            DenseMap<Function *, CallInst *> Ptrcasts);188 189  void replaceAllUsesWith(Value *Src, Value *Dest, bool DeleteOld = true);190  void replaceAllUsesWithAndErase(IRBuilder<> &B, Instruction *Src,191                                  Instruction *Dest, bool DeleteOld = true);192 193  void applyDemangledPtrArgTypes(IRBuilder<> &B);194 195  GetElementPtrInst *simplifyZeroLengthArrayGepInst(GetElementPtrInst *GEP);196 197  bool runOnFunction(Function &F);198  bool postprocessTypes(Module &M);199  bool processFunctionPointers(Module &M);200  void parseFunDeclarations(Module &M);201 202  void useRoundingMode(ConstrainedFPIntrinsic *FPI, IRBuilder<> &B);203 204  // Tries to walk the type accessed by the given GEP instruction.205  // For each nested type access, one of the 2 callbacks is called:206  //  - OnLiteralIndexing when the index is a known constant value.207  //    Parameters:208  //      PointedType: the pointed type resulting of this indexing.209  //        If the parent type is an array, this is the index in the array.210  //        If the parent type is a struct, this is the field index.211  //      Index: index of the element in the parent type.212  //  - OnDynamnicIndexing when the index is a non-constant value.213  //    This callback is only called when indexing into an array.214  //    Parameters:215  //      ElementType: the type of the elements stored in the parent array.216  //      Offset: the Value* containing the byte offset into the array.217  // Return true if an error occured during the walk, false otherwise.218  bool walkLogicalAccessChain(219      GetElementPtrInst &GEP,220      const std::function<void(Type *PointedType, uint64_t Index)>221          &OnLiteralIndexing,222      const std::function<void(Type *ElementType, Value *Offset)>223          &OnDynamicIndexing);224 225  // Returns the type accessed using the given GEP instruction by relying226  // on the GEP type.227  // FIXME: GEP types are not supposed to be used to retrieve the pointed228  // type. This must be fixed.229  Type *getGEPType(GetElementPtrInst *GEP);230 231  // Returns the type accessed using the given GEP instruction by walking232  // the source type using the GEP indices.233  // FIXME: without help from the frontend, this method cannot reliably retrieve234  // the stored type, nor can robustly determine the depth of the type235  // we are accessing.236  Type *getGEPTypeLogical(GetElementPtrInst *GEP);237 238  Instruction *buildLogicalAccessChainFromGEP(GetElementPtrInst &GEP);239 240public:241  static char ID;242  SPIRVEmitIntrinsics(SPIRVTargetMachine *TM = nullptr)243      : ModulePass(ID), TM(TM) {}244  Instruction *visitInstruction(Instruction &I) { return &I; }245  Instruction *visitSwitchInst(SwitchInst &I);246  Instruction *visitGetElementPtrInst(GetElementPtrInst &I);247  Instruction *visitBitCastInst(BitCastInst &I);248  Instruction *visitInsertElementInst(InsertElementInst &I);249  Instruction *visitExtractElementInst(ExtractElementInst &I);250  Instruction *visitInsertValueInst(InsertValueInst &I);251  Instruction *visitExtractValueInst(ExtractValueInst &I);252  Instruction *visitLoadInst(LoadInst &I);253  Instruction *visitStoreInst(StoreInst &I);254  Instruction *visitAllocaInst(AllocaInst &I);255  Instruction *visitAtomicCmpXchgInst(AtomicCmpXchgInst &I);256  Instruction *visitUnreachableInst(UnreachableInst &I);257  Instruction *visitCallInst(CallInst &I);258 259  StringRef getPassName() const override { return "SPIRV emit intrinsics"; }260 261  bool runOnModule(Module &M) override;262 263  void getAnalysisUsage(AnalysisUsage &AU) const override {264    ModulePass::getAnalysisUsage(AU);265  }266};267 268bool isConvergenceIntrinsic(const Instruction *I) {269  const auto *II = dyn_cast<IntrinsicInst>(I);270  if (!II)271    return false;272 273  return II->getIntrinsicID() == Intrinsic::experimental_convergence_entry ||274         II->getIntrinsicID() == Intrinsic::experimental_convergence_loop ||275         II->getIntrinsicID() == Intrinsic::experimental_convergence_anchor;276}277 278bool expectIgnoredInIRTranslation(const Instruction *I) {279  const auto *II = dyn_cast<IntrinsicInst>(I);280  if (!II)281    return false;282  switch (II->getIntrinsicID()) {283  case Intrinsic::invariant_start:284  case Intrinsic::spv_resource_handlefrombinding:285  case Intrinsic::spv_resource_getpointer:286    return true;287  default:288    return false;289  }290}291 292// Returns the source pointer from `I` ignoring intermediate ptrcast.293Value *getPointerRoot(Value *I) {294  if (auto *II = dyn_cast<IntrinsicInst>(I)) {295    if (II->getIntrinsicID() == Intrinsic::spv_ptrcast) {296      Value *V = II->getArgOperand(0);297      return getPointerRoot(V);298    }299  }300  return I;301}302 303} // namespace304 305char SPIRVEmitIntrinsics::ID = 0;306 307INITIALIZE_PASS(SPIRVEmitIntrinsics, "emit-intrinsics", "SPIRV emit intrinsics",308                false, false)309 310static inline bool isAssignTypeInstr(const Instruction *I) {311  return isa<IntrinsicInst>(I) &&312         cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::spv_assign_type;313}314 315static bool isMemInstrToReplace(Instruction *I) {316  return isa<StoreInst>(I) || isa<LoadInst>(I) || isa<InsertValueInst>(I) ||317         isa<ExtractValueInst>(I) || isa<AtomicCmpXchgInst>(I);318}319 320static bool isAggrConstForceInt32(const Value *V) {321  return isa<ConstantArray>(V) || isa<ConstantStruct>(V) ||322         isa<ConstantDataArray>(V) ||323         (isa<ConstantAggregateZero>(V) && !V->getType()->isVectorTy());324}325 326static void setInsertPointSkippingPhis(IRBuilder<> &B, Instruction *I) {327  if (isa<PHINode>(I))328    B.SetInsertPoint(I->getParent()->getFirstNonPHIOrDbgOrAlloca());329  else330    B.SetInsertPoint(I);331}332 333static void setInsertPointAfterDef(IRBuilder<> &B, Instruction *I) {334  B.SetCurrentDebugLocation(I->getDebugLoc());335  if (I->getType()->isVoidTy())336    B.SetInsertPoint(I->getNextNode());337  else338    B.SetInsertPoint(*I->getInsertionPointAfterDef());339}340 341static bool requireAssignType(Instruction *I) {342  if (const auto *Intr = dyn_cast<IntrinsicInst>(I)) {343    switch (Intr->getIntrinsicID()) {344    case Intrinsic::invariant_start:345    case Intrinsic::invariant_end:346      return false;347    }348  }349  return true;350}351 352static inline void reportFatalOnTokenType(const Instruction *I) {353  if (I->getType()->isTokenTy())354    report_fatal_error("A token is encountered but SPIR-V without extensions "355                       "does not support token type",356                       false);357}358 359static void emitAssignName(Instruction *I, IRBuilder<> &B) {360  if (!I->hasName() || I->getType()->isAggregateType() ||361      expectIgnoredInIRTranslation(I))362    return;363  reportFatalOnTokenType(I);364  setInsertPointAfterDef(B, I);365  LLVMContext &Ctx = I->getContext();366  std::vector<Value *> Args = {367      I, MetadataAsValue::get(368             Ctx, MDNode::get(Ctx, MDString::get(Ctx, I->getName())))};369  B.CreateIntrinsic(Intrinsic::spv_assign_name, {I->getType()}, Args);370}371 372void SPIRVEmitIntrinsics::replaceAllUsesWith(Value *Src, Value *Dest,373                                             bool DeleteOld) {374  GR->replaceAllUsesWith(Src, Dest, DeleteOld);375  // Update uncomplete type records if any376  if (isTodoType(Src)) {377    if (DeleteOld)378      eraseTodoType(Src);379    insertTodoType(Dest);380  }381}382 383void SPIRVEmitIntrinsics::replaceAllUsesWithAndErase(IRBuilder<> &B,384                                                     Instruction *Src,385                                                     Instruction *Dest,386                                                     bool DeleteOld) {387  replaceAllUsesWith(Src, Dest, DeleteOld);388  std::string Name = Src->hasName() ? Src->getName().str() : "";389  Src->eraseFromParent();390  if (!Name.empty()) {391    Dest->setName(Name);392    if (Named.insert(Dest).second)393      emitAssignName(Dest, B);394  }395}396 397static bool IsKernelArgInt8(Function *F, StoreInst *SI) {398  return SI && F->getCallingConv() == CallingConv::SPIR_KERNEL &&399         isPointerTy(SI->getValueOperand()->getType()) &&400         isa<Argument>(SI->getValueOperand());401}402 403// Maybe restore original function return type.404static inline Type *restoreMutatedType(SPIRVGlobalRegistry *GR, Instruction *I,405                                       Type *Ty) {406  CallInst *CI = dyn_cast<CallInst>(I);407  if (!CI || CI->isIndirectCall() || CI->isInlineAsm() ||408      !CI->getCalledFunction() || CI->getCalledFunction()->isIntrinsic())409    return Ty;410  if (Type *OriginalTy = GR->findMutated(CI->getCalledFunction()))411    return OriginalTy;412  return Ty;413}414 415// Reconstruct type with nested element types according to deduced type info.416// Return nullptr if no detailed type info is available.417Type *SPIRVEmitIntrinsics::reconstructType(Value *Op, bool UnknownElemTypeI8,418                                           bool IsPostprocessing) {419  Type *Ty = Op->getType();420  if (auto *OpI = dyn_cast<Instruction>(Op))421    Ty = restoreMutatedType(GR, OpI, Ty);422  if (!isUntypedPointerTy(Ty))423    return Ty;424  // try to find the pointee type425  if (Type *NestedTy = GR->findDeducedElementType(Op))426    return getTypedPointerWrapper(NestedTy, getPointerAddressSpace(Ty));427  // not a pointer according to the type info (e.g., Event object)428  CallInst *CI = GR->findAssignPtrTypeInstr(Op);429  if (CI) {430    MetadataAsValue *MD = cast<MetadataAsValue>(CI->getArgOperand(1));431    return cast<ConstantAsMetadata>(MD->getMetadata())->getType();432  }433  if (UnknownElemTypeI8) {434    if (!IsPostprocessing)435      insertTodoType(Op);436    return getTypedPointerWrapper(IntegerType::getInt8Ty(Op->getContext()),437                                  getPointerAddressSpace(Ty));438  }439  return nullptr;440}441 442CallInst *SPIRVEmitIntrinsics::buildSpvPtrcast(Function *F, Value *Op,443                                               Type *ElemTy) {444  IRBuilder<> B(Op->getContext());445  if (auto *OpI = dyn_cast<Instruction>(Op)) {446    // spv_ptrcast's argument Op denotes an instruction that generates447    // a value, and we may use getInsertionPointAfterDef()448    setInsertPointAfterDef(B, OpI);449  } else if (auto *OpA = dyn_cast<Argument>(Op)) {450    B.SetInsertPointPastAllocas(OpA->getParent());451    B.SetCurrentDebugLocation(DebugLoc());452  } else {453    B.SetInsertPoint(F->getEntryBlock().getFirstNonPHIOrDbgOrAlloca());454  }455  Type *OpTy = Op->getType();456  SmallVector<Type *, 2> Types = {OpTy, OpTy};457  SmallVector<Value *, 2> Args = {Op, buildMD(getNormalizedPoisonValue(ElemTy)),458                                  B.getInt32(getPointerAddressSpace(OpTy))};459  CallInst *PtrCasted =460      B.CreateIntrinsic(Intrinsic::spv_ptrcast, {Types}, Args);461  GR->buildAssignPtr(B, ElemTy, PtrCasted);462  return PtrCasted;463}464 465void SPIRVEmitIntrinsics::replaceUsesOfWithSpvPtrcast(466    Value *Op, Type *ElemTy, Instruction *I,467    DenseMap<Function *, CallInst *> Ptrcasts) {468  Function *F = I->getParent()->getParent();469  CallInst *PtrCastedI = nullptr;470  auto It = Ptrcasts.find(F);471  if (It == Ptrcasts.end()) {472    PtrCastedI = buildSpvPtrcast(F, Op, ElemTy);473    Ptrcasts[F] = PtrCastedI;474  } else {475    PtrCastedI = It->second;476  }477  I->replaceUsesOfWith(Op, PtrCastedI);478}479 480void SPIRVEmitIntrinsics::propagateElemType(481    Value *Op, Type *ElemTy,482    DenseSet<std::pair<Value *, Value *>> &VisitedSubst) {483  DenseMap<Function *, CallInst *> Ptrcasts;484  SmallVector<User *> Users(Op->users());485  for (auto *U : Users) {486    if (!isa<Instruction>(U) || isSpvIntrinsic(U))487      continue;488    if (!VisitedSubst.insert(std::make_pair(U, Op)).second)489      continue;490    Instruction *UI = dyn_cast<Instruction>(U);491    // If the instruction was validated already, we need to keep it valid by492    // keeping current Op type.493    if (isa<GetElementPtrInst>(UI) ||494        TypeValidated.find(UI) != TypeValidated.end())495      replaceUsesOfWithSpvPtrcast(Op, ElemTy, UI, Ptrcasts);496  }497}498 499void SPIRVEmitIntrinsics::propagateElemTypeRec(500    Value *Op, Type *PtrElemTy, Type *CastElemTy,501    DenseSet<std::pair<Value *, Value *>> &VisitedSubst) {502  std::unordered_set<Value *> Visited;503  DenseMap<Function *, CallInst *> Ptrcasts;504  propagateElemTypeRec(Op, PtrElemTy, CastElemTy, VisitedSubst, Visited,505                       std::move(Ptrcasts));506}507 508void SPIRVEmitIntrinsics::propagateElemTypeRec(509    Value *Op, Type *PtrElemTy, Type *CastElemTy,510    DenseSet<std::pair<Value *, Value *>> &VisitedSubst,511    std::unordered_set<Value *> &Visited,512    DenseMap<Function *, CallInst *> Ptrcasts) {513  if (!Visited.insert(Op).second)514    return;515  SmallVector<User *> Users(Op->users());516  for (auto *U : Users) {517    if (!isa<Instruction>(U) || isSpvIntrinsic(U))518      continue;519    if (!VisitedSubst.insert(std::make_pair(U, Op)).second)520      continue;521    Instruction *UI = dyn_cast<Instruction>(U);522    // If the instruction was validated already, we need to keep it valid by523    // keeping current Op type.524    if (isa<GetElementPtrInst>(UI) ||525        TypeValidated.find(UI) != TypeValidated.end())526      replaceUsesOfWithSpvPtrcast(Op, CastElemTy, UI, Ptrcasts);527  }528}529 530// Set element pointer type to the given value of ValueTy and tries to531// specify this type further (recursively) by Operand value, if needed.532 533Type *534SPIRVEmitIntrinsics::deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,535                                                  bool UnknownElemTypeI8) {536  std::unordered_set<Value *> Visited;537  return deduceElementTypeByValueDeep(ValueTy, Operand, Visited,538                                      UnknownElemTypeI8);539}540 541Type *SPIRVEmitIntrinsics::deduceElementTypeByValueDeep(542    Type *ValueTy, Value *Operand, std::unordered_set<Value *> &Visited,543    bool UnknownElemTypeI8) {544  Type *Ty = ValueTy;545  if (Operand) {546    if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {547      if (Type *NestedTy =548              deduceElementTypeHelper(Operand, Visited, UnknownElemTypeI8))549        Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());550    } else {551      Ty = deduceNestedTypeHelper(dyn_cast<User>(Operand), Ty, Visited,552                                  UnknownElemTypeI8);553    }554  }555  return Ty;556}557 558// Traverse User instructions to deduce an element pointer type of the operand.559Type *SPIRVEmitIntrinsics::deduceElementTypeByUsersDeep(560    Value *Op, std::unordered_set<Value *> &Visited, bool UnknownElemTypeI8) {561  if (!Op || !isPointerTy(Op->getType()) || isa<ConstantPointerNull>(Op) ||562      isa<UndefValue>(Op))563    return nullptr;564 565  if (auto ElemTy = getPointeeType(Op->getType()))566    return ElemTy;567 568  // maybe we already know operand's element type569  if (Type *KnownTy = GR->findDeducedElementType(Op))570    return KnownTy;571 572  for (User *OpU : Op->users()) {573    if (Instruction *Inst = dyn_cast<Instruction>(OpU)) {574      if (Type *Ty = deduceElementTypeHelper(Inst, Visited, UnknownElemTypeI8))575        return Ty;576    }577  }578  return nullptr;579}580 581// Implements what we know in advance about intrinsics and builtin calls582// TODO: consider feasibility of this particular case to be generalized by583// encoding knowledge about intrinsics and builtin calls by corresponding584// specification rules585static Type *getPointeeTypeByCallInst(StringRef DemangledName,586                                      Function *CalledF, unsigned OpIdx) {587  if ((DemangledName.starts_with("__spirv_ocl_printf(") ||588       DemangledName.starts_with("printf(")) &&589      OpIdx == 0)590    return IntegerType::getInt8Ty(CalledF->getContext());591  return nullptr;592}593 594// Deduce and return a successfully deduced Type of the Instruction,595// or nullptr otherwise.596Type *SPIRVEmitIntrinsics::deduceElementTypeHelper(Value *I,597                                                   bool UnknownElemTypeI8) {598  std::unordered_set<Value *> Visited;599  return deduceElementTypeHelper(I, Visited, UnknownElemTypeI8);600}601 602void SPIRVEmitIntrinsics::maybeAssignPtrType(Type *&Ty, Value *Op, Type *RefTy,603                                             bool UnknownElemTypeI8) {604  if (isUntypedPointerTy(RefTy)) {605    if (!UnknownElemTypeI8)606      return;607    insertTodoType(Op);608  }609  Ty = RefTy;610}611 612bool SPIRVEmitIntrinsics::walkLogicalAccessChain(613    GetElementPtrInst &GEP,614    const std::function<void(Type *, uint64_t)> &OnLiteralIndexing,615    const std::function<void(Type *, Value *)> &OnDynamicIndexing) {616  // We only rewrite i8* GEP. Other should be left as-is.617  // Valid i8* GEP must always have a single index.618  assert(GEP.getSourceElementType() ==619         IntegerType::getInt8Ty(CurrF->getContext()));620  assert(GEP.getNumIndices() == 1);621 622  auto &DL = CurrF->getDataLayout();623  Value *Src = getPointerRoot(GEP.getPointerOperand());624  Type *CurType = deduceElementType(Src, true);625 626  Value *Operand = *GEP.idx_begin();627  ConstantInt *CI = dyn_cast<ConstantInt>(Operand);628  if (!CI) {629    ArrayType *AT = dyn_cast<ArrayType>(CurType);630    // Operand is not constant. Either we have an array and accept it, or we631    // give up.632    if (AT)633      OnDynamicIndexing(AT->getElementType(), Operand);634    return AT == nullptr;635  }636 637  assert(CI);638  uint64_t Offset = CI->getZExtValue();639 640  do {641    if (ArrayType *AT = dyn_cast<ArrayType>(CurType)) {642      uint32_t EltTypeSize = DL.getTypeSizeInBits(AT->getElementType()) / 8;643      assert(Offset < AT->getNumElements() * EltTypeSize);644      uint64_t Index = Offset / EltTypeSize;645      Offset = Offset - (Index * EltTypeSize);646      CurType = AT->getElementType();647      OnLiteralIndexing(CurType, Index);648    } else if (StructType *ST = dyn_cast<StructType>(CurType)) {649      uint32_t StructSize = DL.getTypeSizeInBits(ST) / 8;650      assert(Offset < StructSize);651      (void)StructSize;652      const auto &STL = DL.getStructLayout(ST);653      unsigned Element = STL->getElementContainingOffset(Offset);654      Offset -= STL->getElementOffset(Element);655      CurType = ST->getElementType(Element);656      OnLiteralIndexing(CurType, Element);657    } else {658      // Vector type indexing should not use GEP.659      // So if we have an index left, something is wrong. Giving up.660      return true;661    }662  } while (Offset > 0);663 664  return false;665}666 667Instruction *668SPIRVEmitIntrinsics::buildLogicalAccessChainFromGEP(GetElementPtrInst &GEP) {669  auto &DL = CurrF->getDataLayout();670  IRBuilder<> B(GEP.getParent());671  B.SetInsertPoint(&GEP);672 673  std::vector<Value *> Indices;674  Indices.push_back(ConstantInt::get(675      IntegerType::getInt32Ty(CurrF->getContext()), 0, /* Signed= */ false));676  walkLogicalAccessChain(677      GEP,678      [&Indices, &B](Type *EltType, uint64_t Index) {679        Indices.push_back(680            ConstantInt::get(B.getInt64Ty(), Index, /* Signed= */ false));681      },682      [&Indices, &B, &DL](Type *EltType, Value *Offset) {683        uint32_t EltTypeSize = DL.getTypeSizeInBits(EltType) / 8;684        Value *Index = B.CreateUDiv(685            Offset, ConstantInt::get(Offset->getType(), EltTypeSize,686                                     /* Signed= */ false));687        Indices.push_back(Index);688      });689 690  SmallVector<Type *, 2> Types = {GEP.getType(), GEP.getOperand(0)->getType()};691  SmallVector<Value *, 4> Args;692  Args.push_back(B.getInt1(GEP.isInBounds()));693  Args.push_back(GEP.getOperand(0));694  llvm::append_range(Args, Indices);695  auto *NewI = B.CreateIntrinsic(Intrinsic::spv_gep, {Types}, {Args});696  replaceAllUsesWithAndErase(B, &GEP, NewI);697  return NewI;698}699 700Type *SPIRVEmitIntrinsics::getGEPTypeLogical(GetElementPtrInst *GEP) {701 702  Type *CurType = GEP->getResultElementType();703 704  bool Interrupted = walkLogicalAccessChain(705      *GEP, [&CurType](Type *EltType, uint64_t Index) { CurType = EltType; },706      [&CurType](Type *EltType, Value *Index) { CurType = EltType; });707 708  return Interrupted ? GEP->getResultElementType() : CurType;709}710 711Type *SPIRVEmitIntrinsics::getGEPType(GetElementPtrInst *Ref) {712  if (Ref->getSourceElementType() ==713          IntegerType::getInt8Ty(CurrF->getContext()) &&714      TM->getSubtargetImpl()->isLogicalSPIRV()) {715    return getGEPTypeLogical(Ref);716  }717 718  Type *Ty = nullptr;719  // TODO: not sure if GetElementPtrInst::getTypeAtIndex() does anything720  // useful here721  if (isNestedPointer(Ref->getSourceElementType())) {722    Ty = Ref->getSourceElementType();723    for (Use &U : drop_begin(Ref->indices()))724      Ty = GetElementPtrInst::getTypeAtIndex(Ty, U.get());725  } else {726    Ty = Ref->getResultElementType();727  }728  return Ty;729}730 731Type *SPIRVEmitIntrinsics::deduceElementTypeHelper(732    Value *I, std::unordered_set<Value *> &Visited, bool UnknownElemTypeI8,733    bool IgnoreKnownType) {734  // allow to pass nullptr as an argument735  if (!I)736    return nullptr;737 738  // maybe already known739  if (!IgnoreKnownType)740    if (Type *KnownTy = GR->findDeducedElementType(I))741      return KnownTy;742 743  // maybe a cycle744  if (!Visited.insert(I).second)745    return nullptr;746 747  // fallback value in case when we fail to deduce a type748  Type *Ty = nullptr;749  // look for known basic patterns of type inference750  if (auto *Ref = dyn_cast<AllocaInst>(I)) {751    maybeAssignPtrType(Ty, I, Ref->getAllocatedType(), UnknownElemTypeI8);752  } else if (auto *Ref = dyn_cast<GetElementPtrInst>(I)) {753    Ty = getGEPType(Ref);754  } else if (auto *Ref = dyn_cast<LoadInst>(I)) {755    Value *Op = Ref->getPointerOperand();756    Type *KnownTy = GR->findDeducedElementType(Op);757    if (!KnownTy)758      KnownTy = Op->getType();759    if (Type *ElemTy = getPointeeType(KnownTy))760      maybeAssignPtrType(Ty, I, ElemTy, UnknownElemTypeI8);761  } else if (auto *Ref = dyn_cast<GlobalValue>(I)) {762    Ty = deduceElementTypeByValueDeep(763        Ref->getValueType(),764        Ref->getNumOperands() > 0 ? Ref->getOperand(0) : nullptr, Visited,765        UnknownElemTypeI8);766  } else if (auto *Ref = dyn_cast<AddrSpaceCastInst>(I)) {767    Type *RefTy = deduceElementTypeHelper(Ref->getPointerOperand(), Visited,768                                          UnknownElemTypeI8);769    maybeAssignPtrType(Ty, I, RefTy, UnknownElemTypeI8);770  } else if (auto *Ref = dyn_cast<IntToPtrInst>(I)) {771    maybeAssignPtrType(Ty, I, Ref->getDestTy(), UnknownElemTypeI8);772  } else if (auto *Ref = dyn_cast<BitCastInst>(I)) {773    if (Type *Src = Ref->getSrcTy(), *Dest = Ref->getDestTy();774        isPointerTy(Src) && isPointerTy(Dest))775      Ty = deduceElementTypeHelper(Ref->getOperand(0), Visited,776                                   UnknownElemTypeI8);777  } else if (auto *Ref = dyn_cast<AtomicCmpXchgInst>(I)) {778    Value *Op = Ref->getNewValOperand();779    if (isPointerTy(Op->getType()))780      Ty = deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8);781  } else if (auto *Ref = dyn_cast<AtomicRMWInst>(I)) {782    Value *Op = Ref->getValOperand();783    if (isPointerTy(Op->getType()))784      Ty = deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8);785  } else if (auto *Ref = dyn_cast<PHINode>(I)) {786    Type *BestTy = nullptr;787    unsigned MaxN = 1;788    DenseMap<Type *, unsigned> PhiTys;789    for (int i = Ref->getNumIncomingValues() - 1; i >= 0; --i) {790      Ty = deduceElementTypeByUsersDeep(Ref->getIncomingValue(i), Visited,791                                        UnknownElemTypeI8);792      if (!Ty)793        continue;794      auto It = PhiTys.try_emplace(Ty, 1);795      if (!It.second) {796        ++It.first->second;797        if (It.first->second > MaxN) {798          MaxN = It.first->second;799          BestTy = Ty;800        }801      }802    }803    if (BestTy)804      Ty = BestTy;805  } else if (auto *Ref = dyn_cast<SelectInst>(I)) {806    for (Value *Op : {Ref->getTrueValue(), Ref->getFalseValue()}) {807      Ty = deduceElementTypeByUsersDeep(Op, Visited, UnknownElemTypeI8);808      if (Ty)809        break;810    }811  } else if (auto *CI = dyn_cast<CallInst>(I)) {812    static StringMap<unsigned> ResTypeByArg = {813        {"to_global", 0},814        {"to_local", 0},815        {"to_private", 0},816        {"__spirv_GenericCastToPtr_ToGlobal", 0},817        {"__spirv_GenericCastToPtr_ToLocal", 0},818        {"__spirv_GenericCastToPtr_ToPrivate", 0},819        {"__spirv_GenericCastToPtrExplicit_ToGlobal", 0},820        {"__spirv_GenericCastToPtrExplicit_ToLocal", 0},821        {"__spirv_GenericCastToPtrExplicit_ToPrivate", 0}};822    // TODO: maybe improve performance by caching demangled names823 824    auto *II = dyn_cast<IntrinsicInst>(I);825    if (II && II->getIntrinsicID() == Intrinsic::spv_resource_getpointer) {826      auto *HandleType = cast<TargetExtType>(II->getOperand(0)->getType());827      if (HandleType->getTargetExtName() == "spirv.Image" ||828          HandleType->getTargetExtName() == "spirv.SignedImage") {829        for (User *U : II->users()) {830          Ty = cast<Instruction>(U)->getAccessType();831          if (Ty)832            break;833        }834      } else if (HandleType->getTargetExtName() == "spirv.VulkanBuffer") {835        // This call is supposed to index into an array836        Ty = HandleType->getTypeParameter(0);837        if (Ty->isArrayTy())838          Ty = Ty->getArrayElementType();839        else {840          assert(Ty && Ty->isStructTy());841          uint32_t Index = cast<ConstantInt>(II->getOperand(1))->getZExtValue();842          Ty = cast<StructType>(Ty)->getElementType(Index);843        }844        Ty = reconstitutePeeledArrayType(Ty);845      } else {846        llvm_unreachable("Unknown handle type for spv_resource_getpointer.");847      }848    } else if (II && II->getIntrinsicID() ==849                         Intrinsic::spv_generic_cast_to_ptr_explicit) {850      Ty = deduceElementTypeHelper(CI->getArgOperand(0), Visited,851                                   UnknownElemTypeI8);852    } else if (Function *CalledF = CI->getCalledFunction()) {853      std::string DemangledName =854          getOclOrSpirvBuiltinDemangledName(CalledF->getName());855      if (DemangledName.length() > 0)856        DemangledName = SPIRV::lookupBuiltinNameHelper(DemangledName);857      auto AsArgIt = ResTypeByArg.find(DemangledName);858      if (AsArgIt != ResTypeByArg.end())859        Ty = deduceElementTypeHelper(CI->getArgOperand(AsArgIt->second),860                                     Visited, UnknownElemTypeI8);861      else if (Type *KnownRetTy = GR->findDeducedElementType(CalledF))862        Ty = KnownRetTy;863    }864  }865 866  // remember the found relationship867  if (Ty && !IgnoreKnownType) {868    // specify nested types if needed, otherwise return unchanged869    GR->addDeducedElementType(I, normalizeType(Ty));870  }871 872  return Ty;873}874 875// Re-create a type of the value if it has untyped pointer fields, also nested.876// Return the original value type if no corrections of untyped pointer877// information is found or needed.878Type *SPIRVEmitIntrinsics::deduceNestedTypeHelper(User *U,879                                                  bool UnknownElemTypeI8) {880  std::unordered_set<Value *> Visited;881  return deduceNestedTypeHelper(U, U->getType(), Visited, UnknownElemTypeI8);882}883 884Type *SPIRVEmitIntrinsics::deduceNestedTypeHelper(885    User *U, Type *OrigTy, std::unordered_set<Value *> &Visited,886    bool UnknownElemTypeI8) {887  if (!U)888    return OrigTy;889 890  // maybe already known891  if (Type *KnownTy = GR->findDeducedCompositeType(U))892    return KnownTy;893 894  // maybe a cycle895  if (!Visited.insert(U).second)896    return OrigTy;897 898  if (isa<StructType>(OrigTy)) {899    SmallVector<Type *> Tys;900    bool Change = false;901    for (unsigned i = 0; i < U->getNumOperands(); ++i) {902      Value *Op = U->getOperand(i);903      assert(Op && "Operands should not be null.");904      Type *OpTy = Op->getType();905      Type *Ty = OpTy;906      if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {907        if (Type *NestedTy =908                deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))909          Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());910      } else {911        Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,912                                    UnknownElemTypeI8);913      }914      Tys.push_back(Ty);915      Change |= Ty != OpTy;916    }917    if (Change) {918      Type *NewTy = StructType::create(Tys);919      GR->addDeducedCompositeType(U, NewTy);920      return NewTy;921    }922  } else if (auto *ArrTy = dyn_cast<ArrayType>(OrigTy)) {923    if (Value *Op = U->getNumOperands() > 0 ? U->getOperand(0) : nullptr) {924      Type *OpTy = ArrTy->getElementType();925      Type *Ty = OpTy;926      if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {927        if (Type *NestedTy =928                deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))929          Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());930      } else {931        Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,932                                    UnknownElemTypeI8);933      }934      if (Ty != OpTy) {935        Type *NewTy = ArrayType::get(Ty, ArrTy->getNumElements());936        GR->addDeducedCompositeType(U, NewTy);937        return NewTy;938      }939    }940  } else if (auto *VecTy = dyn_cast<VectorType>(OrigTy)) {941    if (Value *Op = U->getNumOperands() > 0 ? U->getOperand(0) : nullptr) {942      Type *OpTy = VecTy->getElementType();943      Type *Ty = OpTy;944      if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {945        if (Type *NestedTy =946                deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))947          Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());948      } else {949        Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,950                                    UnknownElemTypeI8);951      }952      if (Ty != OpTy) {953        Type *NewTy = VectorType::get(Ty, VecTy->getElementCount());954        GR->addDeducedCompositeType(U, normalizeType(NewTy));955        return NewTy;956      }957    }958  }959 960  return OrigTy;961}962 963Type *SPIRVEmitIntrinsics::deduceElementType(Value *I, bool UnknownElemTypeI8) {964  if (Type *Ty = deduceElementTypeHelper(I, UnknownElemTypeI8))965    return Ty;966  if (!UnknownElemTypeI8)967    return nullptr;968  insertTodoType(I);969  return IntegerType::getInt8Ty(I->getContext());970}971 972static inline Type *getAtomicElemTy(SPIRVGlobalRegistry *GR, Instruction *I,973                                    Value *PointerOperand) {974  Type *PointeeTy = GR->findDeducedElementType(PointerOperand);975  if (PointeeTy && !isUntypedPointerTy(PointeeTy))976    return nullptr;977  auto *PtrTy = dyn_cast<PointerType>(I->getType());978  if (!PtrTy)979    return I->getType();980  if (Type *NestedTy = GR->findDeducedElementType(I))981    return getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());982  return nullptr;983}984 985// Try to deduce element type for a call base. Returns false if this is an986// indirect function invocation, and true otherwise.987bool SPIRVEmitIntrinsics::deduceOperandElementTypeCalledFunction(988    CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,989    Type *&KnownElemTy, bool &Incomplete) {990  Function *CalledF = CI->getCalledFunction();991  if (!CalledF)992    return false;993  std::string DemangledName =994      getOclOrSpirvBuiltinDemangledName(CalledF->getName());995  if (DemangledName.length() > 0 &&996      !StringRef(DemangledName).starts_with("llvm.")) {997    const SPIRVSubtarget &ST = TM->getSubtarget<SPIRVSubtarget>(*CalledF);998    auto [Grp, Opcode, ExtNo] = SPIRV::mapBuiltinToOpcode(999        DemangledName, ST.getPreferredInstructionSet());1000    if (Opcode == SPIRV::OpGroupAsyncCopy) {1001      for (unsigned i = 0, PtrCnt = 0; i < CI->arg_size() && PtrCnt < 2; ++i) {1002        Value *Op = CI->getArgOperand(i);1003        if (!isPointerTy(Op->getType()))1004          continue;1005        ++PtrCnt;1006        if (Type *ElemTy = GR->findDeducedElementType(Op))1007          KnownElemTy = ElemTy; // src will rewrite dest if both are defined1008        Ops.push_back(std::make_pair(Op, i));1009      }1010    } else if (Grp == SPIRV::Atomic || Grp == SPIRV::AtomicFloating) {1011      if (CI->arg_size() == 0)1012        return true;1013      Value *Op = CI->getArgOperand(0);1014      if (!isPointerTy(Op->getType()))1015        return true;1016      switch (Opcode) {1017      case SPIRV::OpAtomicFAddEXT:1018      case SPIRV::OpAtomicFMinEXT:1019      case SPIRV::OpAtomicFMaxEXT:1020      case SPIRV::OpAtomicLoad:1021      case SPIRV::OpAtomicCompareExchangeWeak:1022      case SPIRV::OpAtomicCompareExchange:1023      case SPIRV::OpAtomicExchange:1024      case SPIRV::OpAtomicIAdd:1025      case SPIRV::OpAtomicISub:1026      case SPIRV::OpAtomicOr:1027      case SPIRV::OpAtomicXor:1028      case SPIRV::OpAtomicAnd:1029      case SPIRV::OpAtomicUMin:1030      case SPIRV::OpAtomicUMax:1031      case SPIRV::OpAtomicSMin:1032      case SPIRV::OpAtomicSMax: {1033        KnownElemTy = isPointerTy(CI->getType()) ? getAtomicElemTy(GR, CI, Op)1034                                                 : CI->getType();1035        if (!KnownElemTy)1036          return true;1037        Incomplete = isTodoType(Op);1038        Ops.push_back(std::make_pair(Op, 0));1039      } break;1040      case SPIRV::OpAtomicStore: {1041        if (CI->arg_size() < 4)1042          return true;1043        Value *ValOp = CI->getArgOperand(3);1044        KnownElemTy = isPointerTy(ValOp->getType())1045                          ? getAtomicElemTy(GR, CI, Op)1046                          : ValOp->getType();1047        if (!KnownElemTy)1048          return true;1049        Incomplete = isTodoType(Op);1050        Ops.push_back(std::make_pair(Op, 0));1051      } break;1052      }1053    }1054  }1055  return true;1056}1057 1058// Try to deduce element type for a function pointer.1059void SPIRVEmitIntrinsics::deduceOperandElementTypeFunctionPointer(1060    CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,1061    Type *&KnownElemTy, bool IsPostprocessing) {1062  Value *Op = CI->getCalledOperand();1063  if (!Op || !isPointerTy(Op->getType()))1064    return;1065  Ops.push_back(std::make_pair(Op, std::numeric_limits<unsigned>::max()));1066  FunctionType *FTy = CI->getFunctionType();1067  bool IsNewFTy = false, IsIncomplete = false;1068  SmallVector<Type *, 4> ArgTys;1069  for (Value *Arg : CI->args()) {1070    Type *ArgTy = Arg->getType();1071    if (ArgTy->isPointerTy()) {1072      if (Type *ElemTy = GR->findDeducedElementType(Arg)) {1073        IsNewFTy = true;1074        ArgTy = getTypedPointerWrapper(ElemTy, getPointerAddressSpace(ArgTy));1075        if (isTodoType(Arg))1076          IsIncomplete = true;1077      } else {1078        IsIncomplete = true;1079      }1080    }1081    ArgTys.push_back(ArgTy);1082  }1083  Type *RetTy = FTy->getReturnType();1084  if (CI->getType()->isPointerTy()) {1085    if (Type *ElemTy = GR->findDeducedElementType(CI)) {1086      IsNewFTy = true;1087      RetTy =1088          getTypedPointerWrapper(ElemTy, getPointerAddressSpace(CI->getType()));1089      if (isTodoType(CI))1090        IsIncomplete = true;1091    } else {1092      IsIncomplete = true;1093    }1094  }1095  if (!IsPostprocessing && IsIncomplete)1096    insertTodoType(Op);1097  KnownElemTy =1098      IsNewFTy ? FunctionType::get(RetTy, ArgTys, FTy->isVarArg()) : FTy;1099}1100 1101bool SPIRVEmitIntrinsics::deduceOperandElementTypeFunctionRet(1102    Instruction *I, SmallPtrSet<Instruction *, 4> *IncompleteRets,1103    const SmallPtrSet<Value *, 4> *AskOps, bool IsPostprocessing,1104    Type *&KnownElemTy, Value *Op, Function *F) {1105  KnownElemTy = GR->findDeducedElementType(F);1106  if (KnownElemTy)1107    return false;1108  if (Type *OpElemTy = GR->findDeducedElementType(Op)) {1109    OpElemTy = normalizeType(OpElemTy);1110    GR->addDeducedElementType(F, OpElemTy);1111    GR->addReturnType(1112        F, TypedPointerType::get(OpElemTy,1113                                 getPointerAddressSpace(F->getReturnType())));1114    // non-recursive update of types in function uses1115    DenseSet<std::pair<Value *, Value *>> VisitedSubst{std::make_pair(I, Op)};1116    for (User *U : F->users()) {1117      CallInst *CI = dyn_cast<CallInst>(U);1118      if (!CI || CI->getCalledFunction() != F)1119        continue;1120      if (CallInst *AssignCI = GR->findAssignPtrTypeInstr(CI)) {1121        if (Type *PrevElemTy = GR->findDeducedElementType(CI)) {1122          GR->updateAssignType(AssignCI, CI,1123                               getNormalizedPoisonValue(OpElemTy));1124          propagateElemType(CI, PrevElemTy, VisitedSubst);1125        }1126      }1127    }1128    // Non-recursive update of types in the function uncomplete returns.1129    // This may happen just once per a function, the latch is a pair of1130    // findDeducedElementType(F) / addDeducedElementType(F, ...).1131    // With or without the latch it is a non-recursive call due to1132    // IncompleteRets set to nullptr in this call.1133    if (IncompleteRets)1134      for (Instruction *IncompleteRetI : *IncompleteRets)1135        deduceOperandElementType(IncompleteRetI, nullptr, AskOps,1136                                 IsPostprocessing);1137  } else if (IncompleteRets) {1138    IncompleteRets->insert(I);1139  }1140  TypeValidated.insert(I);1141  return true;1142}1143 1144// If the Instruction has Pointer operands with unresolved types, this function1145// tries to deduce them. If the Instruction has Pointer operands with known1146// types which differ from expected, this function tries to insert a bitcast to1147// resolve the issue.1148void SPIRVEmitIntrinsics::deduceOperandElementType(1149    Instruction *I, SmallPtrSet<Instruction *, 4> *IncompleteRets,1150    const SmallPtrSet<Value *, 4> *AskOps, bool IsPostprocessing) {1151  SmallVector<std::pair<Value *, unsigned>> Ops;1152  Type *KnownElemTy = nullptr;1153  bool Incomplete = false;1154  // look for known basic patterns of type inference1155  if (auto *Ref = dyn_cast<PHINode>(I)) {1156    if (!isPointerTy(I->getType()) ||1157        !(KnownElemTy = GR->findDeducedElementType(I)))1158      return;1159    Incomplete = isTodoType(I);1160    for (unsigned i = 0; i < Ref->getNumIncomingValues(); i++) {1161      Value *Op = Ref->getIncomingValue(i);1162      if (isPointerTy(Op->getType()))1163        Ops.push_back(std::make_pair(Op, i));1164    }1165  } else if (auto *Ref = dyn_cast<AddrSpaceCastInst>(I)) {1166    KnownElemTy = GR->findDeducedElementType(I);1167    if (!KnownElemTy)1168      return;1169    Incomplete = isTodoType(I);1170    Ops.push_back(std::make_pair(Ref->getPointerOperand(), 0));1171  } else if (auto *Ref = dyn_cast<BitCastInst>(I)) {1172    if (!isPointerTy(I->getType()))1173      return;1174    KnownElemTy = GR->findDeducedElementType(I);1175    if (!KnownElemTy)1176      return;1177    Incomplete = isTodoType(I);1178    Ops.push_back(std::make_pair(Ref->getOperand(0), 0));1179  } else if (auto *Ref = dyn_cast<GetElementPtrInst>(I)) {1180    if (GR->findDeducedElementType(Ref->getPointerOperand()))1181      return;1182    KnownElemTy = Ref->getSourceElementType();1183    Ops.push_back(std::make_pair(Ref->getPointerOperand(),1184                                 GetElementPtrInst::getPointerOperandIndex()));1185  } else if (auto *Ref = dyn_cast<LoadInst>(I)) {1186    KnownElemTy = I->getType();1187    if (isUntypedPointerTy(KnownElemTy))1188      return;1189    Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());1190    if (PointeeTy && !isUntypedPointerTy(PointeeTy))1191      return;1192    Ops.push_back(std::make_pair(Ref->getPointerOperand(),1193                                 LoadInst::getPointerOperandIndex()));1194  } else if (auto *Ref = dyn_cast<StoreInst>(I)) {1195    if (!(KnownElemTy =1196              reconstructType(Ref->getValueOperand(), false, IsPostprocessing)))1197      return;1198    Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());1199    if (PointeeTy && !isUntypedPointerTy(PointeeTy))1200      return;1201    Ops.push_back(std::make_pair(Ref->getPointerOperand(),1202                                 StoreInst::getPointerOperandIndex()));1203  } else if (auto *Ref = dyn_cast<AtomicCmpXchgInst>(I)) {1204    KnownElemTy = isPointerTy(I->getType())1205                      ? getAtomicElemTy(GR, I, Ref->getPointerOperand())1206                      : I->getType();1207    if (!KnownElemTy)1208      return;1209    Incomplete = isTodoType(Ref->getPointerOperand());1210    Ops.push_back(std::make_pair(Ref->getPointerOperand(),1211                                 AtomicCmpXchgInst::getPointerOperandIndex()));1212  } else if (auto *Ref = dyn_cast<AtomicRMWInst>(I)) {1213    KnownElemTy = isPointerTy(I->getType())1214                      ? getAtomicElemTy(GR, I, Ref->getPointerOperand())1215                      : I->getType();1216    if (!KnownElemTy)1217      return;1218    Incomplete = isTodoType(Ref->getPointerOperand());1219    Ops.push_back(std::make_pair(Ref->getPointerOperand(),1220                                 AtomicRMWInst::getPointerOperandIndex()));1221  } else if (auto *Ref = dyn_cast<SelectInst>(I)) {1222    if (!isPointerTy(I->getType()) ||1223        !(KnownElemTy = GR->findDeducedElementType(I)))1224      return;1225    Incomplete = isTodoType(I);1226    for (unsigned i = 0; i < Ref->getNumOperands(); i++) {1227      Value *Op = Ref->getOperand(i);1228      if (isPointerTy(Op->getType()))1229        Ops.push_back(std::make_pair(Op, i));1230    }1231  } else if (auto *Ref = dyn_cast<ReturnInst>(I)) {1232    if (!isPointerTy(CurrF->getReturnType()))1233      return;1234    Value *Op = Ref->getReturnValue();1235    if (!Op)1236      return;1237    if (deduceOperandElementTypeFunctionRet(I, IncompleteRets, AskOps,1238                                            IsPostprocessing, KnownElemTy, Op,1239                                            CurrF))1240      return;1241    Incomplete = isTodoType(CurrF);1242    Ops.push_back(std::make_pair(Op, 0));1243  } else if (auto *Ref = dyn_cast<ICmpInst>(I)) {1244    if (!isPointerTy(Ref->getOperand(0)->getType()))1245      return;1246    Value *Op0 = Ref->getOperand(0);1247    Value *Op1 = Ref->getOperand(1);1248    bool Incomplete0 = isTodoType(Op0);1249    bool Incomplete1 = isTodoType(Op1);1250    Type *ElemTy1 = GR->findDeducedElementType(Op1);1251    Type *ElemTy0 = (Incomplete0 && !Incomplete1 && ElemTy1)1252                        ? nullptr1253                        : GR->findDeducedElementType(Op0);1254    if (ElemTy0) {1255      KnownElemTy = ElemTy0;1256      Incomplete = Incomplete0;1257      Ops.push_back(std::make_pair(Op1, 1));1258    } else if (ElemTy1) {1259      KnownElemTy = ElemTy1;1260      Incomplete = Incomplete1;1261      Ops.push_back(std::make_pair(Op0, 0));1262    }1263  } else if (CallInst *CI = dyn_cast<CallInst>(I)) {1264    if (!CI->isIndirectCall())1265      deduceOperandElementTypeCalledFunction(CI, Ops, KnownElemTy, Incomplete);1266    else if (HaveFunPtrs)1267      deduceOperandElementTypeFunctionPointer(CI, Ops, KnownElemTy,1268                                              IsPostprocessing);1269  }1270 1271  // There is no enough info to deduce types or all is valid.1272  if (!KnownElemTy || Ops.size() == 0)1273    return;1274 1275  LLVMContext &Ctx = CurrF->getContext();1276  IRBuilder<> B(Ctx);1277  for (auto &OpIt : Ops) {1278    Value *Op = OpIt.first;1279    if (AskOps && !AskOps->contains(Op))1280      continue;1281    Type *AskTy = nullptr;1282    CallInst *AskCI = nullptr;1283    if (IsPostprocessing && AskOps) {1284      AskTy = GR->findDeducedElementType(Op);1285      AskCI = GR->findAssignPtrTypeInstr(Op);1286      assert(AskTy && AskCI);1287    }1288    Type *Ty = AskTy ? AskTy : GR->findDeducedElementType(Op);1289    if (Ty == KnownElemTy)1290      continue;1291    Value *OpTyVal = getNormalizedPoisonValue(KnownElemTy);1292    Type *OpTy = Op->getType();1293    if (Op->hasUseList() &&1294        (!Ty || AskTy || isUntypedPointerTy(Ty) || isTodoType(Op))) {1295      Type *PrevElemTy = GR->findDeducedElementType(Op);1296      GR->addDeducedElementType(Op, normalizeType(KnownElemTy));1297      // check if KnownElemTy is complete1298      if (!Incomplete)1299        eraseTodoType(Op);1300      else if (!IsPostprocessing)1301        insertTodoType(Op);1302      // check if there is existing Intrinsic::spv_assign_ptr_type instruction1303      CallInst *AssignCI = AskCI ? AskCI : GR->findAssignPtrTypeInstr(Op);1304      if (AssignCI == nullptr) {1305        Instruction *User = dyn_cast<Instruction>(Op->use_begin()->get());1306        setInsertPointSkippingPhis(B, User ? User->getNextNode() : I);1307        CallInst *CI =1308            buildIntrWithMD(Intrinsic::spv_assign_ptr_type, {OpTy}, OpTyVal, Op,1309                            {B.getInt32(getPointerAddressSpace(OpTy))}, B);1310        GR->addAssignPtrTypeInstr(Op, CI);1311      } else {1312        GR->updateAssignType(AssignCI, Op, OpTyVal);1313        DenseSet<std::pair<Value *, Value *>> VisitedSubst{1314            std::make_pair(I, Op)};1315        propagateElemTypeRec(Op, KnownElemTy, PrevElemTy, VisitedSubst);1316      }1317    } else {1318      eraseTodoType(Op);1319      CallInst *PtrCastI =1320          buildSpvPtrcast(I->getParent()->getParent(), Op, KnownElemTy);1321      if (OpIt.second == std::numeric_limits<unsigned>::max())1322        dyn_cast<CallInst>(I)->setCalledOperand(PtrCastI);1323      else1324        I->setOperand(OpIt.second, PtrCastI);1325    }1326  }1327  TypeValidated.insert(I);1328}1329 1330void SPIRVEmitIntrinsics::replaceMemInstrUses(Instruction *Old,1331                                              Instruction *New,1332                                              IRBuilder<> &B) {1333  while (!Old->user_empty()) {1334    auto *U = Old->user_back();1335    if (isAssignTypeInstr(U)) {1336      B.SetInsertPoint(U);1337      SmallVector<Value *, 2> Args = {New, U->getOperand(1)};1338      CallInst *AssignCI =1339          B.CreateIntrinsic(Intrinsic::spv_assign_type, {New->getType()}, Args);1340      GR->addAssignPtrTypeInstr(New, AssignCI);1341      U->eraseFromParent();1342    } else if (isMemInstrToReplace(U) || isa<ReturnInst>(U) ||1343               isa<CallInst>(U)) {1344      U->replaceUsesOfWith(Old, New);1345    } else {1346      llvm_unreachable("illegal aggregate intrinsic user");1347    }1348  }1349  New->copyMetadata(*Old);1350  Old->eraseFromParent();1351}1352 1353void SPIRVEmitIntrinsics::preprocessUndefs(IRBuilder<> &B) {1354  std::queue<Instruction *> Worklist;1355  for (auto &I : instructions(CurrF))1356    Worklist.push(&I);1357 1358  while (!Worklist.empty()) {1359    Instruction *I = Worklist.front();1360    bool BPrepared = false;1361    Worklist.pop();1362 1363    for (auto &Op : I->operands()) {1364      auto *AggrUndef = dyn_cast<UndefValue>(Op);1365      if (!AggrUndef || !Op->getType()->isAggregateType())1366        continue;1367 1368      if (!BPrepared) {1369        setInsertPointSkippingPhis(B, I);1370        BPrepared = true;1371      }1372      auto *IntrUndef = B.CreateIntrinsic(Intrinsic::spv_undef, {});1373      Worklist.push(IntrUndef);1374      I->replaceUsesOfWith(Op, IntrUndef);1375      AggrConsts[IntrUndef] = AggrUndef;1376      AggrConstTypes[IntrUndef] = AggrUndef->getType();1377    }1378  }1379}1380 1381void SPIRVEmitIntrinsics::preprocessCompositeConstants(IRBuilder<> &B) {1382  std::queue<Instruction *> Worklist;1383  for (auto &I : instructions(CurrF))1384    Worklist.push(&I);1385 1386  while (!Worklist.empty()) {1387    auto *I = Worklist.front();1388    bool IsPhi = isa<PHINode>(I), BPrepared = false;1389    assert(I);1390    bool KeepInst = false;1391    for (const auto &Op : I->operands()) {1392      Constant *AggrConst = nullptr;1393      Type *ResTy = nullptr;1394      if (auto *COp = dyn_cast<ConstantVector>(Op)) {1395        AggrConst = COp;1396        ResTy = COp->getType();1397      } else if (auto *COp = dyn_cast<ConstantArray>(Op)) {1398        AggrConst = COp;1399        ResTy = B.getInt32Ty();1400      } else if (auto *COp = dyn_cast<ConstantStruct>(Op)) {1401        AggrConst = COp;1402        ResTy = B.getInt32Ty();1403      } else if (auto *COp = dyn_cast<ConstantDataArray>(Op)) {1404        AggrConst = COp;1405        ResTy = B.getInt32Ty();1406      } else if (auto *COp = dyn_cast<ConstantAggregateZero>(Op)) {1407        AggrConst = COp;1408        ResTy = Op->getType()->isVectorTy() ? COp->getType() : B.getInt32Ty();1409      }1410      if (AggrConst) {1411        SmallVector<Value *> Args;1412        if (auto *COp = dyn_cast<ConstantDataSequential>(Op))1413          for (unsigned i = 0; i < COp->getNumElements(); ++i)1414            Args.push_back(COp->getElementAsConstant(i));1415        else1416          llvm::append_range(Args, AggrConst->operands());1417        if (!BPrepared) {1418          IsPhi ? B.SetInsertPointPastAllocas(I->getParent()->getParent())1419                : B.SetInsertPoint(I);1420          BPrepared = true;1421        }1422        auto *CI =1423            B.CreateIntrinsic(Intrinsic::spv_const_composite, {ResTy}, {Args});1424        Worklist.push(CI);1425        I->replaceUsesOfWith(Op, CI);1426        KeepInst = true;1427        AggrConsts[CI] = AggrConst;1428        AggrConstTypes[CI] = deduceNestedTypeHelper(AggrConst, false);1429      }1430    }1431    if (!KeepInst)1432      Worklist.pop();1433  }1434}1435 1436static void createDecorationIntrinsic(Instruction *I, MDNode *Node,1437                                      IRBuilder<> &B) {1438  LLVMContext &Ctx = I->getContext();1439  setInsertPointAfterDef(B, I);1440  B.CreateIntrinsic(Intrinsic::spv_assign_decoration, {I->getType()},1441                    {I, MetadataAsValue::get(Ctx, MDNode::get(Ctx, {Node}))});1442}1443 1444static void createRoundingModeDecoration(Instruction *I,1445                                         unsigned RoundingModeDeco,1446                                         IRBuilder<> &B) {1447  LLVMContext &Ctx = I->getContext();1448  Type *Int32Ty = Type::getInt32Ty(Ctx);1449  MDNode *RoundingModeNode = MDNode::get(1450      Ctx,1451      {ConstantAsMetadata::get(1452           ConstantInt::get(Int32Ty, SPIRV::Decoration::FPRoundingMode)),1453       ConstantAsMetadata::get(ConstantInt::get(Int32Ty, RoundingModeDeco))});1454  createDecorationIntrinsic(I, RoundingModeNode, B);1455}1456 1457static void createSaturatedConversionDecoration(Instruction *I,1458                                                IRBuilder<> &B) {1459  LLVMContext &Ctx = I->getContext();1460  Type *Int32Ty = Type::getInt32Ty(Ctx);1461  MDNode *SaturatedConversionNode =1462      MDNode::get(Ctx, {ConstantAsMetadata::get(ConstantInt::get(1463                           Int32Ty, SPIRV::Decoration::SaturatedConversion))});1464  createDecorationIntrinsic(I, SaturatedConversionNode, B);1465}1466 1467static void addSaturatedDecorationToIntrinsic(Instruction *I, IRBuilder<> &B) {1468  if (auto *CI = dyn_cast<CallInst>(I)) {1469    if (Function *Fu = CI->getCalledFunction()) {1470      if (Fu->isIntrinsic()) {1471        unsigned const int IntrinsicId = Fu->getIntrinsicID();1472        switch (IntrinsicId) {1473        case Intrinsic::fptosi_sat:1474        case Intrinsic::fptoui_sat:1475          createSaturatedConversionDecoration(I, B);1476          break;1477        default:1478          break;1479        }1480      }1481    }1482  }1483}1484 1485Instruction *SPIRVEmitIntrinsics::visitCallInst(CallInst &Call) {1486  if (!Call.isInlineAsm())1487    return &Call;1488 1489  const InlineAsm *IA = cast<InlineAsm>(Call.getCalledOperand());1490  LLVMContext &Ctx = CurrF->getContext();1491 1492  Constant *TyC = UndefValue::get(IA->getFunctionType());1493  MDString *ConstraintString = MDString::get(Ctx, IA->getConstraintString());1494  SmallVector<Value *> Args = {1495      buildMD(TyC),1496      MetadataAsValue::get(Ctx, MDNode::get(Ctx, ConstraintString))};1497  for (unsigned OpIdx = 0; OpIdx < Call.arg_size(); OpIdx++)1498    Args.push_back(Call.getArgOperand(OpIdx));1499 1500  IRBuilder<> B(Call.getParent());1501  B.SetInsertPoint(&Call);1502  B.CreateIntrinsic(Intrinsic::spv_inline_asm, {Args});1503  return &Call;1504}1505 1506// Use a tip about rounding mode to create a decoration.1507void SPIRVEmitIntrinsics::useRoundingMode(ConstrainedFPIntrinsic *FPI,1508                                          IRBuilder<> &B) {1509  std::optional<RoundingMode> RM = FPI->getRoundingMode();1510  if (!RM.has_value())1511    return;1512  unsigned RoundingModeDeco = std::numeric_limits<unsigned>::max();1513  switch (RM.value()) {1514  default:1515    // ignore unknown rounding modes1516    break;1517  case RoundingMode::NearestTiesToEven:1518    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTE;1519    break;1520  case RoundingMode::TowardNegative:1521    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTN;1522    break;1523  case RoundingMode::TowardPositive:1524    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTP;1525    break;1526  case RoundingMode::TowardZero:1527    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTZ;1528    break;1529  case RoundingMode::Dynamic:1530  case RoundingMode::NearestTiesToAway:1531    // TODO: check if supported1532    break;1533  }1534  if (RoundingModeDeco == std::numeric_limits<unsigned>::max())1535    return;1536  // Convert the tip about rounding mode into a decoration record.1537  createRoundingModeDecoration(FPI, RoundingModeDeco, B);1538}1539 1540Instruction *SPIRVEmitIntrinsics::visitSwitchInst(SwitchInst &I) {1541  BasicBlock *ParentBB = I.getParent();1542  IRBuilder<> B(ParentBB);1543  B.SetInsertPoint(&I);1544  SmallVector<Value *, 4> Args;1545  SmallVector<BasicBlock *> BBCases;1546  for (auto &Op : I.operands()) {1547    if (Op.get()->getType()->isSized()) {1548      Args.push_back(Op);1549    } else if (BasicBlock *BB = dyn_cast<BasicBlock>(Op.get())) {1550      BBCases.push_back(BB);1551      Args.push_back(BlockAddress::get(BB->getParent(), BB));1552    } else {1553      report_fatal_error("Unexpected switch operand");1554    }1555  }1556  CallInst *NewI = B.CreateIntrinsic(Intrinsic::spv_switch,1557                                     {I.getOperand(0)->getType()}, {Args});1558  // remove switch to avoid its unneeded and undesirable unwrap into branches1559  // and conditions1560  replaceAllUsesWith(&I, NewI);1561  I.eraseFromParent();1562  // insert artificial and temporary instruction to preserve valid CFG,1563  // it will be removed after IR translation pass1564  B.SetInsertPoint(ParentBB);1565  IndirectBrInst *BrI = B.CreateIndirectBr(1566      Constant::getNullValue(PointerType::getUnqual(ParentBB->getContext())),1567      BBCases.size());1568  for (BasicBlock *BBCase : BBCases)1569    BrI->addDestination(BBCase);1570  return BrI;1571}1572 1573static bool isFirstIndexZero(const GetElementPtrInst *GEP) {1574  if (GEP->getNumIndices() == 0)1575    return false;1576  if (const auto *CI = dyn_cast<ConstantInt>(GEP->getOperand(1))) {1577    return CI->getZExtValue() == 0;1578  }1579  return false;1580}1581 1582Instruction *SPIRVEmitIntrinsics::visitGetElementPtrInst(GetElementPtrInst &I) {1583  IRBuilder<> B(I.getParent());1584  B.SetInsertPoint(&I);1585 1586  if (TM->getSubtargetImpl()->isLogicalSPIRV() && !isFirstIndexZero(&I)) {1587    // Logical SPIR-V cannot use the OpPtrAccessChain instruction. If the first1588    // index of the GEP is not 0, then we need to try to adjust it.1589    //1590    // If the GEP is doing byte addressing, try to rebuild the full access chain1591    // from the type of the pointer.1592    if (I.getSourceElementType() ==1593        IntegerType::getInt8Ty(CurrF->getContext())) {1594      return buildLogicalAccessChainFromGEP(I);1595    }1596 1597    // Look for the array-to-pointer decay. If this is the pattern1598    // we can adjust the types, and prepend a 0 to the indices.1599    Value *PtrOp = I.getPointerOperand();1600    Type *SrcElemTy = I.getSourceElementType();1601    Type *DeducedPointeeTy = deduceElementType(PtrOp, true);1602 1603    if (auto *ArrTy = dyn_cast<ArrayType>(DeducedPointeeTy)) {1604      if (ArrTy->getElementType() == SrcElemTy) {1605        SmallVector<Value *> NewIndices;1606        Type *FirstIdxType = I.getOperand(1)->getType();1607        NewIndices.push_back(ConstantInt::get(FirstIdxType, 0));1608        for (Value *Idx : I.indices())1609          NewIndices.push_back(Idx);1610 1611        SmallVector<Type *, 2> Types = {I.getType(), I.getPointerOperandType()};1612        SmallVector<Value *, 4> Args;1613        Args.push_back(B.getInt1(I.isInBounds()));1614        Args.push_back(I.getPointerOperand());1615        Args.append(NewIndices.begin(), NewIndices.end());1616 1617        auto *NewI = B.CreateIntrinsic(Intrinsic::spv_gep, {Types}, {Args});1618        replaceAllUsesWithAndErase(B, &I, NewI);1619        return NewI;1620      }1621    }1622  }1623 1624  SmallVector<Type *, 2> Types = {I.getType(), I.getOperand(0)->getType()};1625  SmallVector<Value *, 4> Args;1626  Args.push_back(B.getInt1(I.isInBounds()));1627  llvm::append_range(Args, I.operands());1628  auto *NewI = B.CreateIntrinsic(Intrinsic::spv_gep, {Types}, {Args});1629  replaceAllUsesWithAndErase(B, &I, NewI);1630  return NewI;1631}1632 1633Instruction *SPIRVEmitIntrinsics::visitBitCastInst(BitCastInst &I) {1634  IRBuilder<> B(I.getParent());1635  B.SetInsertPoint(&I);1636  Value *Source = I.getOperand(0);1637 1638  // SPIR-V, contrary to LLVM 17+ IR, supports bitcasts between pointers of1639  // varying element types. In case of IR coming from older versions of LLVM1640  // such bitcasts do not provide sufficient information, should be just skipped1641  // here, and handled in insertPtrCastOrAssignTypeInstr.1642  if (isPointerTy(I.getType())) {1643    replaceAllUsesWith(&I, Source);1644    I.eraseFromParent();1645    return nullptr;1646  }1647 1648  SmallVector<Type *, 2> Types = {I.getType(), Source->getType()};1649  SmallVector<Value *> Args(I.op_begin(), I.op_end());1650  auto *NewI = B.CreateIntrinsic(Intrinsic::spv_bitcast, {Types}, {Args});1651  replaceAllUsesWithAndErase(B, &I, NewI);1652  return NewI;1653}1654 1655void SPIRVEmitIntrinsics::insertAssignPtrTypeTargetExt(1656    TargetExtType *AssignedType, Value *V, IRBuilder<> &B) {1657  Type *VTy = V->getType();1658 1659  // A couple of sanity checks.1660  assert((isPointerTy(VTy)) && "Expect a pointer type!");1661  if (Type *ElemTy = getPointeeType(VTy))1662    if (ElemTy != AssignedType)1663      report_fatal_error("Unexpected pointer element type!");1664 1665  CallInst *AssignCI = GR->findAssignPtrTypeInstr(V);1666  if (!AssignCI) {1667    GR->buildAssignType(B, AssignedType, V);1668    return;1669  }1670 1671  Type *CurrentType =1672      dyn_cast<ConstantAsMetadata>(1673          cast<MetadataAsValue>(AssignCI->getOperand(1))->getMetadata())1674          ->getType();1675  if (CurrentType == AssignedType)1676    return;1677 1678  // Builtin types cannot be redeclared or casted.1679  if (CurrentType->isTargetExtTy())1680    report_fatal_error("Type mismatch " + CurrentType->getTargetExtName() +1681                           "/" + AssignedType->getTargetExtName() +1682                           " for value " + V->getName(),1683                       false);1684 1685  // Our previous guess about the type seems to be wrong, let's update1686  // inferred type according to a new, more precise type information.1687  GR->updateAssignType(AssignCI, V, getNormalizedPoisonValue(AssignedType));1688}1689 1690void SPIRVEmitIntrinsics::replacePointerOperandWithPtrCast(1691    Instruction *I, Value *Pointer, Type *ExpectedElementType,1692    unsigned OperandToReplace, IRBuilder<> &B) {1693  TypeValidated.insert(I);1694 1695  // Do not emit spv_ptrcast if Pointer's element type is ExpectedElementType1696  Type *PointerElemTy = deduceElementTypeHelper(Pointer, false);1697  if (PointerElemTy == ExpectedElementType ||1698      isEquivalentTypes(PointerElemTy, ExpectedElementType))1699    return;1700 1701  setInsertPointSkippingPhis(B, I);1702  Value *ExpectedElementVal = getNormalizedPoisonValue(ExpectedElementType);1703  MetadataAsValue *VMD = buildMD(ExpectedElementVal);1704  unsigned AddressSpace = getPointerAddressSpace(Pointer->getType());1705  bool FirstPtrCastOrAssignPtrType = true;1706 1707  // Do not emit new spv_ptrcast if equivalent one already exists or when1708  // spv_assign_ptr_type already targets this pointer with the same element1709  // type.1710  if (Pointer->hasUseList()) {1711    for (auto User : Pointer->users()) {1712      auto *II = dyn_cast<IntrinsicInst>(User);1713      if (!II ||1714          (II->getIntrinsicID() != Intrinsic::spv_assign_ptr_type &&1715           II->getIntrinsicID() != Intrinsic::spv_ptrcast) ||1716          II->getOperand(0) != Pointer)1717        continue;1718 1719      // There is some spv_ptrcast/spv_assign_ptr_type already targeting this1720      // pointer.1721      FirstPtrCastOrAssignPtrType = false;1722      if (II->getOperand(1) != VMD ||1723          dyn_cast<ConstantInt>(II->getOperand(2))->getSExtValue() !=1724              AddressSpace)1725        continue;1726 1727      // The spv_ptrcast/spv_assign_ptr_type targeting this pointer is of the1728      // same element type and address space.1729      if (II->getIntrinsicID() != Intrinsic::spv_ptrcast)1730        return;1731 1732      // This must be a spv_ptrcast, do not emit new if this one has the same BB1733      // as I. Otherwise, search for other spv_ptrcast/spv_assign_ptr_type.1734      if (II->getParent() != I->getParent())1735        continue;1736 1737      I->setOperand(OperandToReplace, II);1738      return;1739    }1740  }1741 1742  if (isa<Instruction>(Pointer) || isa<Argument>(Pointer)) {1743    if (FirstPtrCastOrAssignPtrType) {1744      // If this would be the first spv_ptrcast, do not emit spv_ptrcast and1745      // emit spv_assign_ptr_type instead.1746      GR->buildAssignPtr(B, ExpectedElementType, Pointer);1747      return;1748    } else if (isTodoType(Pointer)) {1749      eraseTodoType(Pointer);1750      if (!isa<CallInst>(Pointer) && !isa<GetElementPtrInst>(Pointer)) {1751        //  If this wouldn't be the first spv_ptrcast but existing type info is1752        //  uncomplete, update spv_assign_ptr_type arguments.1753        if (CallInst *AssignCI = GR->findAssignPtrTypeInstr(Pointer)) {1754          Type *PrevElemTy = GR->findDeducedElementType(Pointer);1755          assert(PrevElemTy);1756          DenseSet<std::pair<Value *, Value *>> VisitedSubst{1757              std::make_pair(I, Pointer)};1758          GR->updateAssignType(AssignCI, Pointer, ExpectedElementVal);1759          propagateElemType(Pointer, PrevElemTy, VisitedSubst);1760        } else {1761          GR->buildAssignPtr(B, ExpectedElementType, Pointer);1762        }1763        return;1764      }1765    }1766  }1767 1768  // Emit spv_ptrcast1769  SmallVector<Type *, 2> Types = {Pointer->getType(), Pointer->getType()};1770  SmallVector<Value *, 2> Args = {Pointer, VMD, B.getInt32(AddressSpace)};1771  auto *PtrCastI = B.CreateIntrinsic(Intrinsic::spv_ptrcast, {Types}, Args);1772  I->setOperand(OperandToReplace, PtrCastI);1773  // We need to set up a pointee type for the newly created spv_ptrcast.1774  GR->buildAssignPtr(B, ExpectedElementType, PtrCastI);1775}1776 1777void SPIRVEmitIntrinsics::insertPtrCastOrAssignTypeInstr(Instruction *I,1778                                                         IRBuilder<> &B) {1779  // Handle basic instructions:1780  StoreInst *SI = dyn_cast<StoreInst>(I);1781  if (IsKernelArgInt8(CurrF, SI)) {1782    replacePointerOperandWithPtrCast(1783        I, SI->getValueOperand(), IntegerType::getInt8Ty(CurrF->getContext()),1784        0, B);1785  }1786  if (SI) {1787    Value *Op = SI->getValueOperand();1788    Value *Pointer = SI->getPointerOperand();1789    Type *OpTy = Op->getType();1790    if (auto *OpI = dyn_cast<Instruction>(Op))1791      OpTy = restoreMutatedType(GR, OpI, OpTy);1792    if (OpTy == Op->getType())1793      OpTy = deduceElementTypeByValueDeep(OpTy, Op, false);1794    replacePointerOperandWithPtrCast(I, Pointer, OpTy, 1, B);1795    return;1796  }1797  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {1798    Value *Pointer = LI->getPointerOperand();1799    Type *OpTy = LI->getType();1800    if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {1801      if (Type *ElemTy = GR->findDeducedElementType(LI)) {1802        OpTy = getTypedPointerWrapper(ElemTy, PtrTy->getAddressSpace());1803      } else {1804        Type *NewOpTy = OpTy;1805        OpTy = deduceElementTypeByValueDeep(OpTy, LI, false);1806        if (OpTy == NewOpTy)1807          insertTodoType(Pointer);1808      }1809    }1810    replacePointerOperandWithPtrCast(I, Pointer, OpTy, 0, B);1811    return;1812  }1813  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {1814    Value *Pointer = GEPI->getPointerOperand();1815    Type *OpTy = nullptr;1816 1817    // Logical SPIR-V is not allowed to use Op*PtrAccessChain instructions. If1818    // the first index is 0, then we can trivially lower to OpAccessChain. If1819    // not we need to try to rewrite the GEP. We avoid adding a pointer cast at1820    // this time, and will rewrite the GEP when visiting it.1821    if (TM->getSubtargetImpl()->isLogicalSPIRV() && !isFirstIndexZero(GEPI)) {1822      return;1823    }1824 1825    // In all cases, fall back to the GEP type if type scavenging failed.1826    if (!OpTy)1827      OpTy = GEPI->getSourceElementType();1828 1829    replacePointerOperandWithPtrCast(I, Pointer, OpTy, 0, B);1830    if (isNestedPointer(OpTy))1831      insertTodoType(Pointer);1832    return;1833  }1834 1835  // TODO: review and merge with existing logics:1836  // Handle calls to builtins (non-intrinsics):1837  CallInst *CI = dyn_cast<CallInst>(I);1838  if (!CI || CI->isIndirectCall() || CI->isInlineAsm() ||1839      !CI->getCalledFunction() || CI->getCalledFunction()->isIntrinsic())1840    return;1841 1842  // collect information about formal parameter types1843  std::string DemangledName =1844      getOclOrSpirvBuiltinDemangledName(CI->getCalledFunction()->getName());1845  Function *CalledF = CI->getCalledFunction();1846  SmallVector<Type *, 4> CalledArgTys;1847  bool HaveTypes = false;1848  for (unsigned OpIdx = 0; OpIdx < CalledF->arg_size(); ++OpIdx) {1849    Argument *CalledArg = CalledF->getArg(OpIdx);1850    Type *ArgType = CalledArg->getType();1851    if (!isPointerTy(ArgType)) {1852      CalledArgTys.push_back(nullptr);1853    } else if (Type *ArgTypeElem = getPointeeType(ArgType)) {1854      CalledArgTys.push_back(ArgTypeElem);1855      HaveTypes = true;1856    } else {1857      Type *ElemTy = GR->findDeducedElementType(CalledArg);1858      if (!ElemTy && hasPointeeTypeAttr(CalledArg))1859        ElemTy = getPointeeTypeByAttr(CalledArg);1860      if (!ElemTy) {1861        ElemTy = getPointeeTypeByCallInst(DemangledName, CalledF, OpIdx);1862        if (ElemTy) {1863          GR->addDeducedElementType(CalledArg, normalizeType(ElemTy));1864        } else {1865          for (User *U : CalledArg->users()) {1866            if (Instruction *Inst = dyn_cast<Instruction>(U)) {1867              if ((ElemTy = deduceElementTypeHelper(Inst, false)) != nullptr)1868                break;1869            }1870          }1871        }1872      }1873      HaveTypes |= ElemTy != nullptr;1874      CalledArgTys.push_back(ElemTy);1875    }1876  }1877 1878  if (DemangledName.empty() && !HaveTypes)1879    return;1880 1881  for (unsigned OpIdx = 0; OpIdx < CI->arg_size(); OpIdx++) {1882    Value *ArgOperand = CI->getArgOperand(OpIdx);1883    if (!isPointerTy(ArgOperand->getType()))1884      continue;1885 1886    // Constants (nulls/undefs) are handled in insertAssignPtrTypeIntrs()1887    if (!isa<Instruction>(ArgOperand) && !isa<Argument>(ArgOperand)) {1888      // However, we may have assumptions about the formal argument's type and1889      // may have a need to insert a ptr cast for the actual parameter of this1890      // call.1891      Argument *CalledArg = CalledF->getArg(OpIdx);1892      if (!GR->findDeducedElementType(CalledArg))1893        continue;1894    }1895 1896    Type *ExpectedType =1897        OpIdx < CalledArgTys.size() ? CalledArgTys[OpIdx] : nullptr;1898    if (!ExpectedType && !DemangledName.empty())1899      ExpectedType = SPIRV::parseBuiltinCallArgumentBaseType(1900          DemangledName, OpIdx, I->getContext());1901    if (!ExpectedType || ExpectedType->isVoidTy())1902      continue;1903 1904    if (ExpectedType->isTargetExtTy() &&1905        !isTypedPointerWrapper(cast<TargetExtType>(ExpectedType)))1906      insertAssignPtrTypeTargetExt(cast<TargetExtType>(ExpectedType),1907                                   ArgOperand, B);1908    else1909      replacePointerOperandWithPtrCast(CI, ArgOperand, ExpectedType, OpIdx, B);1910  }1911}1912 1913Instruction *SPIRVEmitIntrinsics::visitInsertElementInst(InsertElementInst &I) {1914  // If it's a <1 x Type> vector type, don't modify it. It's not a legal vector1915  // type in LLT and IRTranslator will replace it by the scalar.1916  if (isVector1(I.getType()))1917    return &I;1918 1919  SmallVector<Type *, 4> Types = {I.getType(), I.getOperand(0)->getType(),1920                                  I.getOperand(1)->getType(),1921                                  I.getOperand(2)->getType()};1922  IRBuilder<> B(I.getParent());1923  B.SetInsertPoint(&I);1924  SmallVector<Value *> Args(I.op_begin(), I.op_end());1925  auto *NewI = B.CreateIntrinsic(Intrinsic::spv_insertelt, {Types}, {Args});1926  replaceAllUsesWithAndErase(B, &I, NewI);1927  return NewI;1928}1929 1930Instruction *1931SPIRVEmitIntrinsics::visitExtractElementInst(ExtractElementInst &I) {1932  // If it's a <1 x Type> vector type, don't modify it. It's not a legal vector1933  // type in LLT and IRTranslator will replace it by the scalar.1934  if (isVector1(I.getVectorOperandType()))1935    return &I;1936 1937  IRBuilder<> B(I.getParent());1938  B.SetInsertPoint(&I);1939  SmallVector<Type *, 3> Types = {I.getType(), I.getVectorOperandType(),1940                                  I.getIndexOperand()->getType()};1941  SmallVector<Value *, 2> Args = {I.getVectorOperand(), I.getIndexOperand()};1942  auto *NewI = B.CreateIntrinsic(Intrinsic::spv_extractelt, {Types}, {Args});1943  replaceAllUsesWithAndErase(B, &I, NewI);1944  return NewI;1945}1946 1947Instruction *SPIRVEmitIntrinsics::visitInsertValueInst(InsertValueInst &I) {1948  IRBuilder<> B(I.getParent());1949  B.SetInsertPoint(&I);1950  SmallVector<Type *, 1> Types = {I.getInsertedValueOperand()->getType()};1951  SmallVector<Value *> Args;1952  Value *AggregateOp = I.getAggregateOperand();1953  if (isa<UndefValue>(AggregateOp))1954    Args.push_back(UndefValue::get(B.getInt32Ty()));1955  else1956    Args.push_back(AggregateOp);1957  Args.push_back(I.getInsertedValueOperand());1958  for (auto &Op : I.indices())1959    Args.push_back(B.getInt32(Op));1960  Instruction *NewI =1961      B.CreateIntrinsic(Intrinsic::spv_insertv, {Types}, {Args});1962  replaceMemInstrUses(&I, NewI, B);1963  return NewI;1964}1965 1966Instruction *SPIRVEmitIntrinsics::visitExtractValueInst(ExtractValueInst &I) {1967  if (I.getAggregateOperand()->getType()->isAggregateType())1968    return &I;1969  IRBuilder<> B(I.getParent());1970  B.SetInsertPoint(&I);1971  SmallVector<Value *> Args(I.operands());1972  for (auto &Op : I.indices())1973    Args.push_back(B.getInt32(Op));1974  auto *NewI =1975      B.CreateIntrinsic(Intrinsic::spv_extractv, {I.getType()}, {Args});1976  replaceAllUsesWithAndErase(B, &I, NewI);1977  return NewI;1978}1979 1980Instruction *SPIRVEmitIntrinsics::visitLoadInst(LoadInst &I) {1981  if (!I.getType()->isAggregateType())1982    return &I;1983  IRBuilder<> B(I.getParent());1984  B.SetInsertPoint(&I);1985  TrackConstants = false;1986  const auto *TLI = TM->getSubtargetImpl()->getTargetLowering();1987  MachineMemOperand::Flags Flags =1988      TLI->getLoadMemOperandFlags(I, CurrF->getDataLayout());1989  auto *NewI =1990      B.CreateIntrinsic(Intrinsic::spv_load, {I.getOperand(0)->getType()},1991                        {I.getPointerOperand(), B.getInt16(Flags),1992                         B.getInt8(I.getAlign().value())});1993  replaceMemInstrUses(&I, NewI, B);1994  return NewI;1995}1996 1997Instruction *SPIRVEmitIntrinsics::visitStoreInst(StoreInst &I) {1998  if (!AggrStores.contains(&I))1999    return &I;2000  IRBuilder<> B(I.getParent());2001  B.SetInsertPoint(&I);2002  TrackConstants = false;2003  const auto *TLI = TM->getSubtargetImpl()->getTargetLowering();2004  MachineMemOperand::Flags Flags =2005      TLI->getStoreMemOperandFlags(I, CurrF->getDataLayout());2006  auto *PtrOp = I.getPointerOperand();2007  auto *NewI = B.CreateIntrinsic(2008      Intrinsic::spv_store, {I.getValueOperand()->getType(), PtrOp->getType()},2009      {I.getValueOperand(), PtrOp, B.getInt16(Flags),2010       B.getInt8(I.getAlign().value())});2011  NewI->copyMetadata(I);2012  I.eraseFromParent();2013  return NewI;2014}2015 2016Instruction *SPIRVEmitIntrinsics::visitAllocaInst(AllocaInst &I) {2017  Value *ArraySize = nullptr;2018  if (I.isArrayAllocation()) {2019    const SPIRVSubtarget *STI = TM->getSubtargetImpl(*I.getFunction());2020    if (!STI->canUseExtension(2021            SPIRV::Extension::SPV_INTEL_variable_length_array))2022      report_fatal_error(2023          "array allocation: this instruction requires the following "2024          "SPIR-V extension: SPV_INTEL_variable_length_array",2025          false);2026    ArraySize = I.getArraySize();2027  }2028  IRBuilder<> B(I.getParent());2029  B.SetInsertPoint(&I);2030  TrackConstants = false;2031  Type *PtrTy = I.getType();2032  auto *NewI =2033      ArraySize2034          ? B.CreateIntrinsic(Intrinsic::spv_alloca_array,2035                              {PtrTy, ArraySize->getType()},2036                              {ArraySize, B.getInt8(I.getAlign().value())})2037          : B.CreateIntrinsic(Intrinsic::spv_alloca, {PtrTy},2038                              {B.getInt8(I.getAlign().value())});2039  replaceAllUsesWithAndErase(B, &I, NewI);2040  return NewI;2041}2042 2043Instruction *SPIRVEmitIntrinsics::visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) {2044  assert(I.getType()->isAggregateType() && "Aggregate result is expected");2045  IRBuilder<> B(I.getParent());2046  B.SetInsertPoint(&I);2047  SmallVector<Value *> Args(I.operands());2048  Args.push_back(B.getInt32(2049      static_cast<uint32_t>(getMemScope(I.getContext(), I.getSyncScopeID()))));2050  Args.push_back(B.getInt32(2051      static_cast<uint32_t>(getMemSemantics(I.getSuccessOrdering()))));2052  Args.push_back(B.getInt32(2053      static_cast<uint32_t>(getMemSemantics(I.getFailureOrdering()))));2054  auto *NewI = B.CreateIntrinsic(Intrinsic::spv_cmpxchg,2055                                 {I.getPointerOperand()->getType()}, {Args});2056  replaceMemInstrUses(&I, NewI, B);2057  return NewI;2058}2059 2060Instruction *SPIRVEmitIntrinsics::visitUnreachableInst(UnreachableInst &I) {2061  IRBuilder<> B(I.getParent());2062  B.SetInsertPoint(&I);2063  B.CreateIntrinsic(Intrinsic::spv_unreachable, {});2064  return &I;2065}2066 2067void SPIRVEmitIntrinsics::processGlobalValue(GlobalVariable &GV,2068                                             IRBuilder<> &B) {2069  // Skip special artificial variables.2070  static const StringSet<> ArtificialGlobals{"llvm.global.annotations",2071                                             "llvm.compiler.used"};2072 2073  if (ArtificialGlobals.contains(GV.getName()))2074    return;2075 2076  Constant *Init = nullptr;2077  if (hasInitializer(&GV)) {2078    // Deduce element type and store results in Global Registry.2079    // Result is ignored, because TypedPointerType is not supported2080    // by llvm IR general logic.2081    deduceElementTypeHelper(&GV, false);2082    Init = GV.getInitializer();2083    Type *Ty = isAggrConstForceInt32(Init) ? B.getInt32Ty() : Init->getType();2084    Constant *Const = isAggrConstForceInt32(Init) ? B.getInt32(1) : Init;2085    auto *InitInst = B.CreateIntrinsic(Intrinsic::spv_init_global,2086                                       {GV.getType(), Ty}, {&GV, Const});2087    InitInst->setArgOperand(1, Init);2088  }2089  if (!Init && GV.use_empty())2090    B.CreateIntrinsic(Intrinsic::spv_unref_global, GV.getType(), &GV);2091}2092 2093// Return true, if we can't decide what is the pointee type now and will get2094// back to the question later. Return false is spv_assign_ptr_type is not needed2095// or can be inserted immediately.2096bool SPIRVEmitIntrinsics::insertAssignPtrTypeIntrs(Instruction *I,2097                                                   IRBuilder<> &B,2098                                                   bool UnknownElemTypeI8) {2099  reportFatalOnTokenType(I);2100  if (!isPointerTy(I->getType()) || !requireAssignType(I))2101    return false;2102 2103  setInsertPointAfterDef(B, I);2104  if (Type *ElemTy = deduceElementType(I, UnknownElemTypeI8)) {2105    GR->buildAssignPtr(B, ElemTy, I);2106    return false;2107  }2108  return true;2109}2110 2111void SPIRVEmitIntrinsics::insertAssignTypeIntrs(Instruction *I,2112                                                IRBuilder<> &B) {2113  // TODO: extend the list of functions with known result types2114  static StringMap<unsigned> ResTypeWellKnown = {2115      {"async_work_group_copy", WellKnownTypes::Event},2116      {"async_work_group_strided_copy", WellKnownTypes::Event},2117      {"__spirv_GroupAsyncCopy", WellKnownTypes::Event}};2118 2119  reportFatalOnTokenType(I);2120 2121  bool IsKnown = false;2122  if (auto *CI = dyn_cast<CallInst>(I)) {2123    if (!CI->isIndirectCall() && !CI->isInlineAsm() &&2124        CI->getCalledFunction() && !CI->getCalledFunction()->isIntrinsic()) {2125      Function *CalledF = CI->getCalledFunction();2126      std::string DemangledName =2127          getOclOrSpirvBuiltinDemangledName(CalledF->getName());2128      FPDecorationId DecorationId = FPDecorationId::NONE;2129      if (DemangledName.length() > 0)2130        DemangledName =2131            SPIRV::lookupBuiltinNameHelper(DemangledName, &DecorationId);2132      auto ResIt = ResTypeWellKnown.find(DemangledName);2133      if (ResIt != ResTypeWellKnown.end()) {2134        IsKnown = true;2135        setInsertPointAfterDef(B, I);2136        switch (ResIt->second) {2137        case WellKnownTypes::Event:2138          GR->buildAssignType(2139              B, TargetExtType::get(I->getContext(), "spirv.Event"), I);2140          break;2141        }2142      }2143      // check if a floating rounding mode or saturation info is present2144      switch (DecorationId) {2145      default:2146        break;2147      case FPDecorationId::SAT:2148        createSaturatedConversionDecoration(CI, B);2149        break;2150      case FPDecorationId::RTE:2151        createRoundingModeDecoration(2152            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTE, B);2153        break;2154      case FPDecorationId::RTZ:2155        createRoundingModeDecoration(2156            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTZ, B);2157        break;2158      case FPDecorationId::RTP:2159        createRoundingModeDecoration(2160            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTP, B);2161        break;2162      case FPDecorationId::RTN:2163        createRoundingModeDecoration(2164            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTN, B);2165        break;2166      }2167    }2168  }2169 2170  Type *Ty = I->getType();2171  if (!IsKnown && !Ty->isVoidTy() && !isPointerTy(Ty) && requireAssignType(I)) {2172    setInsertPointAfterDef(B, I);2173    Type *TypeToAssign = Ty;2174    if (auto *II = dyn_cast<IntrinsicInst>(I)) {2175      if (II->getIntrinsicID() == Intrinsic::spv_const_composite ||2176          II->getIntrinsicID() == Intrinsic::spv_undef) {2177        auto It = AggrConstTypes.find(II);2178        if (It == AggrConstTypes.end())2179          report_fatal_error("Unknown composite intrinsic type");2180        TypeToAssign = It->second;2181      }2182    }2183    TypeToAssign = restoreMutatedType(GR, I, TypeToAssign);2184    GR->buildAssignType(B, TypeToAssign, I);2185  }2186  for (const auto &Op : I->operands()) {2187    if (isa<ConstantPointerNull>(Op) || isa<UndefValue>(Op) ||2188        // Check GetElementPtrConstantExpr case.2189        (isa<ConstantExpr>(Op) &&2190         (isa<GEPOperator>(Op) ||2191          (cast<ConstantExpr>(Op)->getOpcode() == CastInst::IntToPtr)))) {2192      setInsertPointSkippingPhis(B, I);2193      Type *OpTy = Op->getType();2194      if (isa<UndefValue>(Op) && OpTy->isAggregateType()) {2195        CallInst *AssignCI =2196            buildIntrWithMD(Intrinsic::spv_assign_type, {B.getInt32Ty()}, Op,2197                            UndefValue::get(B.getInt32Ty()), {}, B);2198        GR->addAssignPtrTypeInstr(Op, AssignCI);2199      } else if (!isa<Instruction>(Op)) {2200        Type *OpTy = Op->getType();2201        Type *OpTyElem = getPointeeType(OpTy);2202        if (OpTyElem) {2203          GR->buildAssignPtr(B, OpTyElem, Op);2204        } else if (isPointerTy(OpTy)) {2205          Type *ElemTy = GR->findDeducedElementType(Op);2206          GR->buildAssignPtr(B, ElemTy ? ElemTy : deduceElementType(Op, true),2207                             Op);2208        } else {2209          Value *OpTyVal = Op;2210          if (OpTy->isTargetExtTy()) {2211            // We need to do this in order to be consistent with how target ext2212            // types are handled in `processInstrAfterVisit`2213            OpTyVal = getNormalizedPoisonValue(OpTy);2214          }2215          CallInst *AssignCI =2216              buildIntrWithMD(Intrinsic::spv_assign_type, {OpTy},2217                              getNormalizedPoisonValue(OpTy), OpTyVal, {}, B);2218          GR->addAssignPtrTypeInstr(OpTyVal, AssignCI);2219        }2220      }2221    }2222  }2223}2224 2225bool SPIRVEmitIntrinsics::shouldTryToAddMemAliasingDecoration(2226    Instruction *Inst) {2227  const SPIRVSubtarget *STI = TM->getSubtargetImpl(*Inst->getFunction());2228  if (!STI->canUseExtension(SPIRV::Extension::SPV_INTEL_memory_access_aliasing))2229    return false;2230  // Add aliasing decorations to internal load and store intrinsics2231  // and atomic instructions, skipping atomic store as it won't have ID to2232  // attach the decoration.2233  CallInst *CI = dyn_cast<CallInst>(Inst);2234  if (!CI)2235    return false;2236  if (Function *Fun = CI->getCalledFunction()) {2237    if (Fun->isIntrinsic()) {2238      switch (Fun->getIntrinsicID()) {2239      case Intrinsic::spv_load:2240      case Intrinsic::spv_store:2241        return true;2242      default:2243        return false;2244      }2245    }2246    std::string Name = getOclOrSpirvBuiltinDemangledName(Fun->getName());2247    const std::string Prefix = "__spirv_Atomic";2248    const bool IsAtomic = Name.find(Prefix) == 0;2249 2250    if (!Fun->getReturnType()->isVoidTy() && IsAtomic)2251      return true;2252  }2253  return false;2254}2255 2256void SPIRVEmitIntrinsics::insertSpirvDecorations(Instruction *I,2257                                                 IRBuilder<> &B) {2258  if (MDNode *MD = I->getMetadata("spirv.Decorations")) {2259    setInsertPointAfterDef(B, I);2260    B.CreateIntrinsic(Intrinsic::spv_assign_decoration, {I->getType()},2261                      {I, MetadataAsValue::get(I->getContext(), MD)});2262  }2263  // Lower alias.scope/noalias metadata2264  {2265    auto processMemAliasingDecoration = [&](unsigned Kind) {2266      if (MDNode *AliasListMD = I->getMetadata(Kind)) {2267        if (shouldTryToAddMemAliasingDecoration(I)) {2268          uint32_t Dec = Kind == LLVMContext::MD_alias_scope2269                             ? SPIRV::Decoration::AliasScopeINTEL2270                             : SPIRV::Decoration::NoAliasINTEL;2271          SmallVector<Value *, 3> Args = {2272              I, ConstantInt::get(B.getInt32Ty(), Dec),2273              MetadataAsValue::get(I->getContext(), AliasListMD)};2274          setInsertPointAfterDef(B, I);2275          B.CreateIntrinsic(Intrinsic::spv_assign_aliasing_decoration,2276                            {I->getType()}, {Args});2277        }2278      }2279    };2280    processMemAliasingDecoration(LLVMContext::MD_alias_scope);2281    processMemAliasingDecoration(LLVMContext::MD_noalias);2282  }2283  // MD_fpmath2284  if (MDNode *MD = I->getMetadata(LLVMContext::MD_fpmath)) {2285    const SPIRVSubtarget *STI = TM->getSubtargetImpl(*I->getFunction());2286    bool AllowFPMaxError =2287        STI->canUseExtension(SPIRV::Extension::SPV_INTEL_fp_max_error);2288    if (!AllowFPMaxError)2289      return;2290 2291    setInsertPointAfterDef(B, I);2292    B.CreateIntrinsic(Intrinsic::spv_assign_fpmaxerror_decoration,2293                      {I->getType()},2294                      {I, MetadataAsValue::get(I->getContext(), MD)});2295  }2296}2297 2298static SPIRV::FPFastMathDefaultInfoVector &getOrCreateFPFastMathDefaultInfoVec(2299    const Module &M,2300    DenseMap<Function *, SPIRV::FPFastMathDefaultInfoVector>2301        &FPFastMathDefaultInfoMap,2302    Function *F) {2303  auto it = FPFastMathDefaultInfoMap.find(F);2304  if (it != FPFastMathDefaultInfoMap.end())2305    return it->second;2306 2307  // If the map does not contain the entry, create a new one. Initialize it to2308  // contain all 3 elements sorted by bit width of target type: {half, float,2309  // double}.2310  SPIRV::FPFastMathDefaultInfoVector FPFastMathDefaultInfoVec;2311  FPFastMathDefaultInfoVec.emplace_back(Type::getHalfTy(M.getContext()),2312                                        SPIRV::FPFastMathMode::None);2313  FPFastMathDefaultInfoVec.emplace_back(Type::getFloatTy(M.getContext()),2314                                        SPIRV::FPFastMathMode::None);2315  FPFastMathDefaultInfoVec.emplace_back(Type::getDoubleTy(M.getContext()),2316                                        SPIRV::FPFastMathMode::None);2317  return FPFastMathDefaultInfoMap[F] = std::move(FPFastMathDefaultInfoVec);2318}2319 2320static SPIRV::FPFastMathDefaultInfo &getFPFastMathDefaultInfo(2321    SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec,2322    const Type *Ty) {2323  size_t BitWidth = Ty->getScalarSizeInBits();2324  int Index =2325      SPIRV::FPFastMathDefaultInfoVector::computeFPFastMathDefaultInfoVecIndex(2326          BitWidth);2327  assert(Index >= 0 && Index < 3 &&2328         "Expected FPFastMathDefaultInfo for half, float, or double");2329  assert(FPFastMathDefaultInfoVec.size() == 3 &&2330         "Expected FPFastMathDefaultInfoVec to have exactly 3 elements");2331  return FPFastMathDefaultInfoVec[Index];2332}2333 2334void SPIRVEmitIntrinsics::insertConstantsForFPFastMathDefault(Module &M) {2335  const SPIRVSubtarget *ST = TM->getSubtargetImpl();2336  if (!ST->canUseExtension(SPIRV::Extension::SPV_KHR_float_controls2))2337    return;2338 2339  // Store the FPFastMathDefaultInfo in the FPFastMathDefaultInfoMap.2340  // We need the entry point (function) as the key, and the target2341  // type and flags as the value.2342  // We also need to check ContractionOff and SignedZeroInfNanPreserve2343  // execution modes, as they are now deprecated and must be replaced2344  // with FPFastMathDefaultInfo.2345  auto Node = M.getNamedMetadata("spirv.ExecutionMode");2346  if (!Node) {2347    if (!M.getNamedMetadata("opencl.enable.FP_CONTRACT")) {2348      // This requires emitting ContractionOff. However, because2349      // ContractionOff is now deprecated, we need to replace it with2350      // FPFastMathDefaultInfo with FP Fast Math Mode bitmask set to all 0.2351      // We need to create the constant for that.2352 2353      // Create constant instruction with the bitmask flags.2354      Constant *InitValue =2355          ConstantInt::get(Type::getInt32Ty(M.getContext()), 0);2356      // TODO: Reuse constant if there is one already with the required2357      // value.2358      [[maybe_unused]] GlobalVariable *GV =2359          new GlobalVariable(M,                                // Module2360                             Type::getInt32Ty(M.getContext()), // Type2361                             true,                             // isConstant2362                             GlobalValue::InternalLinkage,     // Linkage2363                             InitValue                         // Initializer2364          );2365    }2366    return;2367  }2368 2369  // The table maps function pointers to their default FP fast math info. It2370  // can be assumed that the SmallVector is sorted by the bit width of the2371  // type. The first element is the smallest bit width, and the last element2372  // is the largest bit width, therefore, we will have {half, float, double}2373  // in the order of their bit widths.2374  DenseMap<Function *, SPIRV::FPFastMathDefaultInfoVector>2375      FPFastMathDefaultInfoMap;2376 2377  for (unsigned i = 0; i < Node->getNumOperands(); i++) {2378    MDNode *MDN = cast<MDNode>(Node->getOperand(i));2379    assert(MDN->getNumOperands() >= 2 && "Expected at least 2 operands");2380    Function *F = cast<Function>(2381        cast<ConstantAsMetadata>(MDN->getOperand(0))->getValue());2382    const auto EM =2383        cast<ConstantInt>(2384            cast<ConstantAsMetadata>(MDN->getOperand(1))->getValue())2385            ->getZExtValue();2386    if (EM == SPIRV::ExecutionMode::FPFastMathDefault) {2387      assert(MDN->getNumOperands() == 4 &&2388             "Expected 4 operands for FPFastMathDefault");2389      const Type *T = cast<ValueAsMetadata>(MDN->getOperand(2))->getType();2390      unsigned Flags =2391          cast<ConstantInt>(2392              cast<ConstantAsMetadata>(MDN->getOperand(3))->getValue())2393              ->getZExtValue();2394      SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec =2395          getOrCreateFPFastMathDefaultInfoVec(M, FPFastMathDefaultInfoMap, F);2396      SPIRV::FPFastMathDefaultInfo &Info =2397          getFPFastMathDefaultInfo(FPFastMathDefaultInfoVec, T);2398      Info.FastMathFlags = Flags;2399      Info.FPFastMathDefault = true;2400    } else if (EM == SPIRV::ExecutionMode::ContractionOff) {2401      assert(MDN->getNumOperands() == 2 &&2402             "Expected no operands for ContractionOff");2403 2404      // We need to save this info for every possible FP type, i.e. {half,2405      // float, double, fp128}.2406      SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec =2407          getOrCreateFPFastMathDefaultInfoVec(M, FPFastMathDefaultInfoMap, F);2408      for (SPIRV::FPFastMathDefaultInfo &Info : FPFastMathDefaultInfoVec) {2409        Info.ContractionOff = true;2410      }2411    } else if (EM == SPIRV::ExecutionMode::SignedZeroInfNanPreserve) {2412      assert(MDN->getNumOperands() == 3 &&2413             "Expected 1 operand for SignedZeroInfNanPreserve");2414      unsigned TargetWidth =2415          cast<ConstantInt>(2416              cast<ConstantAsMetadata>(MDN->getOperand(2))->getValue())2417              ->getZExtValue();2418      // We need to save this info only for the FP type with TargetWidth.2419      SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec =2420          getOrCreateFPFastMathDefaultInfoVec(M, FPFastMathDefaultInfoMap, F);2421      int Index = SPIRV::FPFastMathDefaultInfoVector::2422          computeFPFastMathDefaultInfoVecIndex(TargetWidth);2423      assert(Index >= 0 && Index < 3 &&2424             "Expected FPFastMathDefaultInfo for half, float, or double");2425      assert(FPFastMathDefaultInfoVec.size() == 3 &&2426             "Expected FPFastMathDefaultInfoVec to have exactly 3 elements");2427      FPFastMathDefaultInfoVec[Index].SignedZeroInfNanPreserve = true;2428    }2429  }2430 2431  std::unordered_map<unsigned, GlobalVariable *> GlobalVars;2432  for (auto &[Func, FPFastMathDefaultInfoVec] : FPFastMathDefaultInfoMap) {2433    if (FPFastMathDefaultInfoVec.empty())2434      continue;2435 2436    for (const SPIRV::FPFastMathDefaultInfo &Info : FPFastMathDefaultInfoVec) {2437      assert(Info.Ty && "Expected target type for FPFastMathDefaultInfo");2438      // Skip if none of the execution modes was used.2439      unsigned Flags = Info.FastMathFlags;2440      if (Flags == SPIRV::FPFastMathMode::None && !Info.ContractionOff &&2441          !Info.SignedZeroInfNanPreserve && !Info.FPFastMathDefault)2442        continue;2443 2444      // Check if flags are compatible.2445      if (Info.ContractionOff && (Flags & SPIRV::FPFastMathMode::AllowContract))2446        report_fatal_error("Conflicting FPFastMathFlags: ContractionOff "2447                           "and AllowContract");2448 2449      if (Info.SignedZeroInfNanPreserve &&2450          !(Flags &2451            (SPIRV::FPFastMathMode::NotNaN | SPIRV::FPFastMathMode::NotInf |2452             SPIRV::FPFastMathMode::NSZ))) {2453        if (Info.FPFastMathDefault)2454          report_fatal_error("Conflicting FPFastMathFlags: "2455                             "SignedZeroInfNanPreserve but at least one of "2456                             "NotNaN/NotInf/NSZ is enabled.");2457      }2458 2459      if ((Flags & SPIRV::FPFastMathMode::AllowTransform) &&2460          !((Flags & SPIRV::FPFastMathMode::AllowReassoc) &&2461            (Flags & SPIRV::FPFastMathMode::AllowContract))) {2462        report_fatal_error("Conflicting FPFastMathFlags: "2463                           "AllowTransform requires AllowReassoc and "2464                           "AllowContract to be set.");2465      }2466 2467      auto it = GlobalVars.find(Flags);2468      GlobalVariable *GV = nullptr;2469      if (it != GlobalVars.end()) {2470        // Reuse existing global variable.2471        GV = it->second;2472      } else {2473        // Create constant instruction with the bitmask flags.2474        Constant *InitValue =2475            ConstantInt::get(Type::getInt32Ty(M.getContext()), Flags);2476        // TODO: Reuse constant if there is one already with the required2477        // value.2478        GV = new GlobalVariable(M,                                // Module2479                                Type::getInt32Ty(M.getContext()), // Type2480                                true,                             // isConstant2481                                GlobalValue::InternalLinkage,     // Linkage2482                                InitValue                         // Initializer2483        );2484        GlobalVars[Flags] = GV;2485      }2486    }2487  }2488}2489 2490void SPIRVEmitIntrinsics::processInstrAfterVisit(Instruction *I,2491                                                 IRBuilder<> &B) {2492  auto *II = dyn_cast<IntrinsicInst>(I);2493  bool IsConstComposite =2494      II && II->getIntrinsicID() == Intrinsic::spv_const_composite;2495  if (IsConstComposite && TrackConstants) {2496    setInsertPointAfterDef(B, I);2497    auto t = AggrConsts.find(I);2498    assert(t != AggrConsts.end());2499    auto *NewOp =2500        buildIntrWithMD(Intrinsic::spv_track_constant,2501                        {II->getType(), II->getType()}, t->second, I, {}, B);2502    replaceAllUsesWith(I, NewOp, false);2503    NewOp->setArgOperand(0, I);2504  }2505  bool IsPhi = isa<PHINode>(I), BPrepared = false;2506  for (const auto &Op : I->operands()) {2507    if (isa<PHINode>(I) || isa<SwitchInst>(I) ||2508        !(isa<ConstantData>(Op) || isa<ConstantExpr>(Op)))2509      continue;2510    unsigned OpNo = Op.getOperandNo();2511    if (II && ((II->getIntrinsicID() == Intrinsic::spv_gep && OpNo == 0) ||2512               (II->paramHasAttr(OpNo, Attribute::ImmArg))))2513      continue;2514 2515    if (!BPrepared) {2516      IsPhi ? B.SetInsertPointPastAllocas(I->getParent()->getParent())2517            : B.SetInsertPoint(I);2518      BPrepared = true;2519    }2520    Type *OpTy = Op->getType();2521    Type *OpElemTy = GR->findDeducedElementType(Op);2522    Value *NewOp = Op;2523    if (OpTy->isTargetExtTy()) {2524      // Since this value is replaced by poison, we need to do the same in2525      // `insertAssignTypeIntrs`.2526      Value *OpTyVal = getNormalizedPoisonValue(OpTy);2527      NewOp = buildIntrWithMD(Intrinsic::spv_track_constant,2528                              {OpTy, OpTyVal->getType()}, Op, OpTyVal, {}, B);2529    }2530    if (!IsConstComposite && isPointerTy(OpTy) && OpElemTy != nullptr &&2531        OpElemTy != IntegerType::getInt8Ty(I->getContext())) {2532      SmallVector<Type *, 2> Types = {OpTy, OpTy};2533      SmallVector<Value *, 2> Args = {2534          NewOp, buildMD(getNormalizedPoisonValue(OpElemTy)),2535          B.getInt32(getPointerAddressSpace(OpTy))};2536      CallInst *PtrCasted =2537          B.CreateIntrinsic(Intrinsic::spv_ptrcast, {Types}, Args);2538      GR->buildAssignPtr(B, OpElemTy, PtrCasted);2539      NewOp = PtrCasted;2540    }2541    if (NewOp != Op)2542      I->setOperand(OpNo, NewOp);2543  }2544  if (Named.insert(I).second)2545    emitAssignName(I, B);2546}2547 2548Type *SPIRVEmitIntrinsics::deduceFunParamElementType(Function *F,2549                                                     unsigned OpIdx) {2550  std::unordered_set<Function *> FVisited;2551  return deduceFunParamElementType(F, OpIdx, FVisited);2552}2553 2554Type *SPIRVEmitIntrinsics::deduceFunParamElementType(2555    Function *F, unsigned OpIdx, std::unordered_set<Function *> &FVisited) {2556  // maybe a cycle2557  if (!FVisited.insert(F).second)2558    return nullptr;2559 2560  std::unordered_set<Value *> Visited;2561  SmallVector<std::pair<Function *, unsigned>> Lookup;2562  // search in function's call sites2563  for (User *U : F->users()) {2564    CallInst *CI = dyn_cast<CallInst>(U);2565    if (!CI || OpIdx >= CI->arg_size())2566      continue;2567    Value *OpArg = CI->getArgOperand(OpIdx);2568    if (!isPointerTy(OpArg->getType()))2569      continue;2570    // maybe we already know operand's element type2571    if (Type *KnownTy = GR->findDeducedElementType(OpArg))2572      return KnownTy;2573    // try to deduce from the operand itself2574    Visited.clear();2575    if (Type *Ty = deduceElementTypeHelper(OpArg, Visited, false))2576      return Ty;2577    // search in actual parameter's users2578    for (User *OpU : OpArg->users()) {2579      Instruction *Inst = dyn_cast<Instruction>(OpU);2580      if (!Inst || Inst == CI)2581        continue;2582      Visited.clear();2583      if (Type *Ty = deduceElementTypeHelper(Inst, Visited, false))2584        return Ty;2585    }2586    // check if it's a formal parameter of the outer function2587    if (!CI->getParent() || !CI->getParent()->getParent())2588      continue;2589    Function *OuterF = CI->getParent()->getParent();2590    if (FVisited.find(OuterF) != FVisited.end())2591      continue;2592    for (unsigned i = 0; i < OuterF->arg_size(); ++i) {2593      if (OuterF->getArg(i) == OpArg) {2594        Lookup.push_back(std::make_pair(OuterF, i));2595        break;2596      }2597    }2598  }2599 2600  // search in function parameters2601  for (auto &Pair : Lookup) {2602    if (Type *Ty = deduceFunParamElementType(Pair.first, Pair.second, FVisited))2603      return Ty;2604  }2605 2606  return nullptr;2607}2608 2609void SPIRVEmitIntrinsics::processParamTypesByFunHeader(Function *F,2610                                                       IRBuilder<> &B) {2611  B.SetInsertPointPastAllocas(F);2612  for (unsigned OpIdx = 0; OpIdx < F->arg_size(); ++OpIdx) {2613    Argument *Arg = F->getArg(OpIdx);2614    if (!isUntypedPointerTy(Arg->getType()))2615      continue;2616    Type *ElemTy = GR->findDeducedElementType(Arg);2617    if (ElemTy)2618      continue;2619    if (hasPointeeTypeAttr(Arg) &&2620        (ElemTy = getPointeeTypeByAttr(Arg)) != nullptr) {2621      GR->buildAssignPtr(B, ElemTy, Arg);2622      continue;2623    }2624    // search in function's call sites2625    for (User *U : F->users()) {2626      CallInst *CI = dyn_cast<CallInst>(U);2627      if (!CI || OpIdx >= CI->arg_size())2628        continue;2629      Value *OpArg = CI->getArgOperand(OpIdx);2630      if (!isPointerTy(OpArg->getType()))2631        continue;2632      // maybe we already know operand's element type2633      if ((ElemTy = GR->findDeducedElementType(OpArg)) != nullptr)2634        break;2635    }2636    if (ElemTy) {2637      GR->buildAssignPtr(B, ElemTy, Arg);2638      continue;2639    }2640    if (HaveFunPtrs) {2641      for (User *U : Arg->users()) {2642        CallInst *CI = dyn_cast<CallInst>(U);2643        if (CI && !isa<IntrinsicInst>(CI) && CI->isIndirectCall() &&2644            CI->getCalledOperand() == Arg &&2645            CI->getParent()->getParent() == CurrF) {2646          SmallVector<std::pair<Value *, unsigned>> Ops;2647          deduceOperandElementTypeFunctionPointer(CI, Ops, ElemTy, false);2648          if (ElemTy) {2649            GR->buildAssignPtr(B, ElemTy, Arg);2650            break;2651          }2652        }2653      }2654    }2655  }2656}2657 2658void SPIRVEmitIntrinsics::processParamTypes(Function *F, IRBuilder<> &B) {2659  B.SetInsertPointPastAllocas(F);2660  for (unsigned OpIdx = 0; OpIdx < F->arg_size(); ++OpIdx) {2661    Argument *Arg = F->getArg(OpIdx);2662    if (!isUntypedPointerTy(Arg->getType()))2663      continue;2664    Type *ElemTy = GR->findDeducedElementType(Arg);2665    if (!ElemTy && (ElemTy = deduceFunParamElementType(F, OpIdx)) != nullptr) {2666      if (CallInst *AssignCI = GR->findAssignPtrTypeInstr(Arg)) {2667        DenseSet<std::pair<Value *, Value *>> VisitedSubst;2668        GR->updateAssignType(AssignCI, Arg, getNormalizedPoisonValue(ElemTy));2669        propagateElemType(Arg, IntegerType::getInt8Ty(F->getContext()),2670                          VisitedSubst);2671      } else {2672        GR->buildAssignPtr(B, ElemTy, Arg);2673      }2674    }2675  }2676}2677 2678static FunctionType *getFunctionPointerElemType(Function *F,2679                                                SPIRVGlobalRegistry *GR) {2680  FunctionType *FTy = F->getFunctionType();2681  bool IsNewFTy = false;2682  SmallVector<Type *, 4> ArgTys;2683  for (Argument &Arg : F->args()) {2684    Type *ArgTy = Arg.getType();2685    if (ArgTy->isPointerTy())2686      if (Type *ElemTy = GR->findDeducedElementType(&Arg)) {2687        IsNewFTy = true;2688        ArgTy = getTypedPointerWrapper(ElemTy, getPointerAddressSpace(ArgTy));2689      }2690    ArgTys.push_back(ArgTy);2691  }2692  return IsNewFTy2693             ? FunctionType::get(FTy->getReturnType(), ArgTys, FTy->isVarArg())2694             : FTy;2695}2696 2697bool SPIRVEmitIntrinsics::processFunctionPointers(Module &M) {2698  SmallVector<Function *> Worklist;2699  for (auto &F : M) {2700    if (F.isIntrinsic())2701      continue;2702    if (F.isDeclaration()) {2703      for (User *U : F.users()) {2704        CallInst *CI = dyn_cast<CallInst>(U);2705        if (!CI || CI->getCalledFunction() != &F) {2706          Worklist.push_back(&F);2707          break;2708        }2709      }2710    } else {2711      if (F.user_empty())2712        continue;2713      Type *FPElemTy = GR->findDeducedElementType(&F);2714      if (!FPElemTy)2715        FPElemTy = getFunctionPointerElemType(&F, GR);2716      for (User *U : F.users()) {2717        IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);2718        if (!II || II->arg_size() != 3 || II->getOperand(0) != &F)2719          continue;2720        if (II->getIntrinsicID() == Intrinsic::spv_assign_ptr_type ||2721            II->getIntrinsicID() == Intrinsic::spv_ptrcast) {2722          GR->updateAssignType(II, &F, getNormalizedPoisonValue(FPElemTy));2723          break;2724        }2725      }2726    }2727  }2728  if (Worklist.empty())2729    return false;2730 2731  std::string ServiceFunName = SPIRV_BACKEND_SERVICE_FUN_NAME;2732  if (!getVacantFunctionName(M, ServiceFunName))2733    report_fatal_error(2734        "cannot allocate a name for the internal service function");2735  LLVMContext &Ctx = M.getContext();2736  Function *SF =2737      Function::Create(FunctionType::get(Type::getVoidTy(Ctx), {}, false),2738                       GlobalValue::PrivateLinkage, ServiceFunName, M);2739  SF->addFnAttr(SPIRV_BACKEND_SERVICE_FUN_NAME, "");2740  BasicBlock *BB = BasicBlock::Create(Ctx, "entry", SF);2741  IRBuilder<> IRB(BB);2742 2743  for (Function *F : Worklist) {2744    SmallVector<Value *> Args;2745    for (const auto &Arg : F->args())2746      Args.push_back(getNormalizedPoisonValue(Arg.getType()));2747    IRB.CreateCall(F, Args);2748  }2749  IRB.CreateRetVoid();2750 2751  return true;2752}2753 2754// Apply types parsed from demangled function declarations.2755void SPIRVEmitIntrinsics::applyDemangledPtrArgTypes(IRBuilder<> &B) {2756  DenseMap<Function *, CallInst *> Ptrcasts;2757  for (auto It : FDeclPtrTys) {2758    Function *F = It.first;2759    for (auto *U : F->users()) {2760      CallInst *CI = dyn_cast<CallInst>(U);2761      if (!CI || CI->getCalledFunction() != F)2762        continue;2763      unsigned Sz = CI->arg_size();2764      for (auto [Idx, ElemTy] : It.second) {2765        if (Idx >= Sz)2766          continue;2767        Value *Param = CI->getArgOperand(Idx);2768        if (GR->findDeducedElementType(Param) || isa<GlobalValue>(Param))2769          continue;2770        if (Argument *Arg = dyn_cast<Argument>(Param)) {2771          if (!hasPointeeTypeAttr(Arg)) {2772            B.SetInsertPointPastAllocas(Arg->getParent());2773            B.SetCurrentDebugLocation(DebugLoc());2774            GR->buildAssignPtr(B, ElemTy, Arg);2775          }2776        } else if (isa<GetElementPtrInst>(Param)) {2777          replaceUsesOfWithSpvPtrcast(Param, normalizeType(ElemTy), CI,2778                                      Ptrcasts);2779        } else if (isa<Instruction>(Param)) {2780          GR->addDeducedElementType(Param, normalizeType(ElemTy));2781          // insertAssignTypeIntrs() will complete buildAssignPtr()2782        } else {2783          B.SetInsertPoint(CI->getParent()2784                               ->getParent()2785                               ->getEntryBlock()2786                               .getFirstNonPHIOrDbgOrAlloca());2787          GR->buildAssignPtr(B, ElemTy, Param);2788        }2789        CallInst *Ref = dyn_cast<CallInst>(Param);2790        if (!Ref)2791          continue;2792        Function *RefF = Ref->getCalledFunction();2793        if (!RefF || !isPointerTy(RefF->getReturnType()) ||2794            GR->findDeducedElementType(RefF))2795          continue;2796        ElemTy = normalizeType(ElemTy);2797        GR->addDeducedElementType(RefF, ElemTy);2798        GR->addReturnType(2799            RefF, TypedPointerType::get(2800                      ElemTy, getPointerAddressSpace(RefF->getReturnType())));2801      }2802    }2803  }2804}2805 2806GetElementPtrInst *2807SPIRVEmitIntrinsics::simplifyZeroLengthArrayGepInst(GetElementPtrInst *GEP) {2808  // getelementptr [0 x T], P, 0 (zero), I -> getelementptr T, P, I.2809  // If type is 0-length array and first index is 0 (zero), drop both the2810  // 0-length array type and the first index. This is a common pattern in2811  // the IR, e.g. when using a zero-length array as a placeholder for a2812  // flexible array such as unbound arrays.2813  assert(GEP && "GEP is null");2814  Type *SrcTy = GEP->getSourceElementType();2815  SmallVector<Value *, 8> Indices(GEP->indices());2816  ArrayType *ArrTy = dyn_cast<ArrayType>(SrcTy);2817  if (ArrTy && ArrTy->getNumElements() == 0 &&2818      PatternMatch::match(Indices[0], PatternMatch::m_Zero())) {2819    IRBuilder<> Builder(GEP);2820    Indices.erase(Indices.begin());2821    SrcTy = ArrTy->getElementType();2822    Value *NewGEP = Builder.CreateGEP(SrcTy, GEP->getPointerOperand(), Indices,2823                                      "", GEP->getNoWrapFlags());2824    assert(llvm::isa<GetElementPtrInst>(NewGEP) && "NewGEP should be a GEP");2825    return cast<GetElementPtrInst>(NewGEP);2826  }2827  return nullptr;2828}2829 2830bool SPIRVEmitIntrinsics::runOnFunction(Function &Func) {2831  if (Func.isDeclaration())2832    return false;2833 2834  const SPIRVSubtarget &ST = TM->getSubtarget<SPIRVSubtarget>(Func);2835  GR = ST.getSPIRVGlobalRegistry();2836 2837  if (!CurrF)2838    HaveFunPtrs =2839        ST.canUseExtension(SPIRV::Extension::SPV_INTEL_function_pointers);2840 2841  CurrF = &Func;2842  IRBuilder<> B(Func.getContext());2843  AggrConsts.clear();2844  AggrConstTypes.clear();2845  AggrStores.clear();2846 2847  // Fix GEP result types ahead of inference, and simplify if possible.2848  // Data structure for dead instructions that were simplified and replaced.2849  SmallPtrSet<Instruction *, 4> DeadInsts;2850  for (auto &I : instructions(Func)) {2851    auto *Ref = dyn_cast<GetElementPtrInst>(&I);2852    if (!Ref || GR->findDeducedElementType(Ref))2853      continue;2854 2855    GetElementPtrInst *NewGEP = simplifyZeroLengthArrayGepInst(Ref);2856    if (NewGEP) {2857      Ref->replaceAllUsesWith(NewGEP);2858      DeadInsts.insert(Ref);2859      Ref = NewGEP;2860    }2861    if (Type *GepTy = getGEPType(Ref))2862      GR->addDeducedElementType(Ref, normalizeType(GepTy));2863  }2864  // Remove dead instructions that were simplified and replaced.2865  for (auto *I : DeadInsts) {2866    assert(I->use_empty() && "Dead instruction should not have any uses left");2867    I->eraseFromParent();2868  }2869 2870  processParamTypesByFunHeader(CurrF, B);2871 2872  // StoreInst's operand type can be changed during the next2873  // transformations, so we need to store it in the set. Also store already2874  // transformed types.2875  for (auto &I : instructions(Func)) {2876    StoreInst *SI = dyn_cast<StoreInst>(&I);2877    if (!SI)2878      continue;2879    Type *ElTy = SI->getValueOperand()->getType();2880    if (ElTy->isAggregateType() || ElTy->isVectorTy())2881      AggrStores.insert(&I);2882  }2883 2884  B.SetInsertPoint(&Func.getEntryBlock(), Func.getEntryBlock().begin());2885  for (auto &GV : Func.getParent()->globals())2886    processGlobalValue(GV, B);2887 2888  preprocessUndefs(B);2889  preprocessCompositeConstants(B);2890  SmallVector<Instruction *> Worklist(2891      llvm::make_pointer_range(instructions(Func)));2892 2893  applyDemangledPtrArgTypes(B);2894 2895  // Pass forward: use operand to deduce instructions result.2896  for (auto &I : Worklist) {2897    // Don't emit intrinsincs for convergence intrinsics.2898    if (isConvergenceIntrinsic(I))2899      continue;2900 2901    bool Postpone = insertAssignPtrTypeIntrs(I, B, false);2902    // if Postpone is true, we can't decide on pointee type yet2903    insertAssignTypeIntrs(I, B);2904    insertPtrCastOrAssignTypeInstr(I, B);2905    insertSpirvDecorations(I, B);2906    // if instruction requires a pointee type set, let's check if we know it2907    // already, and force it to be i8 if not2908    if (Postpone && !GR->findAssignPtrTypeInstr(I))2909      insertAssignPtrTypeIntrs(I, B, true);2910 2911    if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I))2912      useRoundingMode(FPI, B);2913  }2914 2915  // Pass backward: use instructions results to specify/update/cast operands2916  // where needed.2917  SmallPtrSet<Instruction *, 4> IncompleteRets;2918  for (auto &I : llvm::reverse(instructions(Func)))2919    deduceOperandElementType(&I, &IncompleteRets);2920 2921  // Pass forward for PHIs only, their operands are not preceed the2922  // instruction in meaning of `instructions(Func)`.2923  for (BasicBlock &BB : Func)2924    for (PHINode &Phi : BB.phis())2925      if (isPointerTy(Phi.getType()))2926        deduceOperandElementType(&Phi, nullptr);2927 2928  for (auto *I : Worklist) {2929    TrackConstants = true;2930    if (!I->getType()->isVoidTy() || isa<StoreInst>(I))2931      setInsertPointAfterDef(B, I);2932    // Visitors return either the original/newly created instruction for2933    // further processing, nullptr otherwise.2934    I = visit(*I);2935    if (!I)2936      continue;2937 2938    // Don't emit intrinsics for convergence operations.2939    if (isConvergenceIntrinsic(I))2940      continue;2941 2942    addSaturatedDecorationToIntrinsic(I, B);2943    processInstrAfterVisit(I, B);2944  }2945 2946  return true;2947}2948 2949// Try to deduce a better type for pointers to untyped ptr.2950bool SPIRVEmitIntrinsics::postprocessTypes(Module &M) {2951  if (!GR || TodoTypeSz == 0)2952    return false;2953 2954  unsigned SzTodo = TodoTypeSz;2955  DenseMap<Value *, SmallPtrSet<Value *, 4>> ToProcess;2956  for (auto [Op, Enabled] : TodoType) {2957    // TODO: add isa<CallInst>(Op) to continue2958    if (!Enabled || isa<GetElementPtrInst>(Op))2959      continue;2960    CallInst *AssignCI = GR->findAssignPtrTypeInstr(Op);2961    Type *KnownTy = GR->findDeducedElementType(Op);2962    if (!KnownTy || !AssignCI)2963      continue;2964    assert(Op == AssignCI->getArgOperand(0));2965    // Try to improve the type deduced after all Functions are processed.2966    if (auto *CI = dyn_cast<Instruction>(Op)) {2967      CurrF = CI->getParent()->getParent();2968      std::unordered_set<Value *> Visited;2969      if (Type *ElemTy = deduceElementTypeHelper(Op, Visited, false, true)) {2970        if (ElemTy != KnownTy) {2971          DenseSet<std::pair<Value *, Value *>> VisitedSubst;2972          propagateElemType(CI, ElemTy, VisitedSubst);2973          eraseTodoType(Op);2974          continue;2975        }2976      }2977    }2978 2979    if (Op->hasUseList()) {2980      for (User *U : Op->users()) {2981        Instruction *Inst = dyn_cast<Instruction>(U);2982        if (Inst && !isa<IntrinsicInst>(Inst))2983          ToProcess[Inst].insert(Op);2984      }2985    }2986  }2987  if (TodoTypeSz == 0)2988    return true;2989 2990  for (auto &F : M) {2991    CurrF = &F;2992    SmallPtrSet<Instruction *, 4> IncompleteRets;2993    for (auto &I : llvm::reverse(instructions(F))) {2994      auto It = ToProcess.find(&I);2995      if (It == ToProcess.end())2996        continue;2997      It->second.remove_if([this](Value *V) { return !isTodoType(V); });2998      if (It->second.size() == 0)2999        continue;3000      deduceOperandElementType(&I, &IncompleteRets, &It->second, true);3001      if (TodoTypeSz == 0)3002        return true;3003    }3004  }3005 3006  return SzTodo > TodoTypeSz;3007}3008 3009// Parse and store argument types of function declarations where needed.3010void SPIRVEmitIntrinsics::parseFunDeclarations(Module &M) {3011  for (auto &F : M) {3012    if (!F.isDeclaration() || F.isIntrinsic())3013      continue;3014    // get the demangled name3015    std::string DemangledName = getOclOrSpirvBuiltinDemangledName(F.getName());3016    if (DemangledName.empty())3017      continue;3018    // allow only OpGroupAsyncCopy use case at the moment3019    const SPIRVSubtarget &ST = TM->getSubtarget<SPIRVSubtarget>(F);3020    auto [Grp, Opcode, ExtNo] = SPIRV::mapBuiltinToOpcode(3021        DemangledName, ST.getPreferredInstructionSet());3022    if (Opcode != SPIRV::OpGroupAsyncCopy)3023      continue;3024    // find pointer arguments3025    SmallVector<unsigned> Idxs;3026    for (unsigned OpIdx = 0; OpIdx < F.arg_size(); ++OpIdx) {3027      Argument *Arg = F.getArg(OpIdx);3028      if (isPointerTy(Arg->getType()) && !hasPointeeTypeAttr(Arg))3029        Idxs.push_back(OpIdx);3030    }3031    if (!Idxs.size())3032      continue;3033    // parse function arguments3034    LLVMContext &Ctx = F.getContext();3035    SmallVector<StringRef, 10> TypeStrs;3036    SPIRV::parseBuiltinTypeStr(TypeStrs, DemangledName, Ctx);3037    if (!TypeStrs.size())3038      continue;3039    // find type info for pointer arguments3040    for (unsigned Idx : Idxs) {3041      if (Idx >= TypeStrs.size())3042        continue;3043      if (Type *ElemTy =3044              SPIRV::parseBuiltinCallArgumentType(TypeStrs[Idx].trim(), Ctx))3045        if (TypedPointerType::isValidElementType(ElemTy) &&3046            !ElemTy->isTargetExtTy())3047          FDeclPtrTys[&F].push_back(std::make_pair(Idx, ElemTy));3048    }3049  }3050}3051 3052bool SPIRVEmitIntrinsics::runOnModule(Module &M) {3053  bool Changed = false;3054 3055  parseFunDeclarations(M);3056  insertConstantsForFPFastMathDefault(M);3057 3058  TodoType.clear();3059  for (auto &F : M)3060    Changed |= runOnFunction(F);3061 3062  // Specify function parameters after all functions were processed.3063  for (auto &F : M) {3064    // check if function parameter types are set3065    CurrF = &F;3066    if (!F.isDeclaration() && !F.isIntrinsic()) {3067      IRBuilder<> B(F.getContext());3068      processParamTypes(&F, B);3069    }3070  }3071 3072  CanTodoType = false;3073  Changed |= postprocessTypes(M);3074 3075  if (HaveFunPtrs)3076    Changed |= processFunctionPointers(M);3077 3078  return Changed;3079}3080 3081ModulePass *llvm::createSPIRVEmitIntrinsicsPass(SPIRVTargetMachine *TM) {3082  return new SPIRVEmitIntrinsics(TM);3083}3084