llvm/lib/Target/SPIRV/SPIRVEmitIntrinsics.cpp

   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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The pass emits SPIRV intrinsics keeping essential high-level information for
  10 // the translation of LLVM IR to SPIR-V.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "SPIRV.h"
  15 #include "SPIRVBuiltins.h"
  16 #include "SPIRVMetadata.h"
  17 #include "SPIRVSubtarget.h"
  18 #include "SPIRVTargetMachine.h"
  19 #include "SPIRVUtils.h"
  20 #include "llvm/IR/IRBuilder.h"
  21 #include "llvm/IR/InstIterator.h"
  22 #include "llvm/IR/InstVisitor.h"
  23 #include "llvm/IR/IntrinsicsSPIRV.h"
  24 #include "llvm/IR/TypedPointerType.h"
  25
  26 #include <queue>
  27
  28 // This pass performs the following transformation on LLVM IR level required
  29 // for the following translation to SPIR-V:
  30 // - replaces direct usages of aggregate constants with target-specific
  31 //   intrinsics;
  32 // - replaces aggregates-related instructions (extract/insert, ld/st, etc)
  33 //   with a target-specific intrinsics;
  34 // - emits intrinsics for the global variable initializers since IRTranslator
  35 //   doesn't handle them and it's not very convenient to translate them
  36 //   ourselves;
  37 // - emits intrinsics to keep track of the string names assigned to the values;
  38 // - emits intrinsics to keep track of constants (this is necessary to have an
  39 //   LLVM IR constant after the IRTranslation is completed) for their further
  40 //   deduplication;
  41 // - emits intrinsics to keep track of original LLVM types of the values
  42 //   to be able to emit proper SPIR-V types eventually.
  43 //
  44 // TODO: consider removing spv.track.constant in favor of spv.assign.type.
  45
  46 using namespace llvm;
  47
  48 namespace llvm {
  49 namespace SPIRV {
  50 #define GET_BuiltinGroup_DECL
  51 #include "SPIRVGenTables.inc"
  52 } // namespace SPIRV
  53 void initializeSPIRVEmitIntrinsicsPass(PassRegistry &);
  54 } // namespace llvm
  55
  56 namespace {
  57
  58 inline MetadataAsValue *buildMD(Value *Arg) {
  59   LLVMContext &Ctx = Arg->getContext();
  60   return MetadataAsValue::get(
  61       Ctx, MDNode::get(Ctx, ValueAsMetadata::getConstant(Arg)));
  62 }
  63
  64 class SPIRVEmitIntrinsics
  65     : public ModulePass,
  66       public InstVisitor<SPIRVEmitIntrinsics, Instruction *> {
  67   SPIRVTargetMachine *TM = nullptr;
  68   SPIRVGlobalRegistry *GR = nullptr;
  69   Function *F = nullptr;
  70   bool TrackConstants = true;
  71   DenseMap<Instruction *, Constant *> AggrConsts;
  72   DenseMap<Instruction *, Type *> AggrConstTypes;
  73   DenseSet<Instruction *> AggrStores;
  74   SPIRV::InstructionSet::InstructionSet InstrSet;
  75
  76   // a register of Instructions that don't have a complete type definition
  77   SmallPtrSet<Value *, 8> UncompleteTypeInfo;
  78   SmallVector<Instruction *> PostprocessWorklist;
  79
  80   // well known result types of builtins
  81   enum WellKnownTypes { Event };
  82
  83   // deduce element type of untyped pointers
  84   Type *deduceElementType(Value *I, bool UnknownElemTypeI8);
  85   Type *deduceElementTypeHelper(Value *I, bool UnknownElemTypeI8);
  86   Type *deduceElementTypeHelper(Value *I, std::unordered_set<Value *> &Visited,
  87                                 bool UnknownElemTypeI8);
  88   Type *deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,
  89                                      bool UnknownElemTypeI8);
  90   Type *deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,
  91                                      std::unordered_set<Value *> &Visited,
  92                                      bool UnknownElemTypeI8);
  93   Type *deduceElementTypeByUsersDeep(Value *Op,
  94                                      std::unordered_set<Value *> &Visited,
  95                                      bool UnknownElemTypeI8);
  96   void maybeAssignPtrType(Type *&Ty, Value *I, Type *RefTy,
  97                           bool UnknownElemTypeI8);
  98
  99   // deduce nested types of composites
 100   Type *deduceNestedTypeHelper(User *U, bool UnknownElemTypeI8);
 101   Type *deduceNestedTypeHelper(User *U, Type *Ty,
 102                                std::unordered_set<Value *> &Visited,
 103                                bool UnknownElemTypeI8);
 104
 105   // deduce Types of operands of the Instruction if possible
 106   void deduceOperandElementType(Instruction *I, Instruction *AskOp = 0,
 107                                 Type *AskTy = 0, CallInst *AssignCI = 0);
 108
 109   void preprocessCompositeConstants(IRBuilder<> &B);
 110   void preprocessUndefs(IRBuilder<> &B);
 111
 112   CallInst *buildIntrWithMD(Intrinsic::ID IntrID, ArrayRef<Type *> Types,
 113                             Value *Arg, Value *Arg2, ArrayRef<Constant *> Imms,
 114                             IRBuilder<> &B) {
 115     SmallVector<Value *, 4> Args;
 116     Args.push_back(Arg2);
 117     Args.push_back(buildMD(Arg));
 118     for (auto *Imm : Imms)
 119       Args.push_back(Imm);
 120     return B.CreateIntrinsic(IntrID, {Types}, Args);
 121   }
 122
 123   void buildAssignType(IRBuilder<> &B, Type *ElemTy, Value *Arg);
 124   void buildAssignPtr(IRBuilder<> &B, Type *ElemTy, Value *Arg);
 125   void updateAssignType(CallInst *AssignCI, Value *Arg, Value *OfType);
 126
 127   void replaceMemInstrUses(Instruction *Old, Instruction *New, IRBuilder<> &B);
 128   void processInstrAfterVisit(Instruction *I, IRBuilder<> &B);
 129   bool insertAssignPtrTypeIntrs(Instruction *I, IRBuilder<> &B,
 130                                 bool UnknownElemTypeI8);
 131   void insertAssignTypeIntrs(Instruction *I, IRBuilder<> &B);
 132   void insertAssignPtrTypeTargetExt(TargetExtType *AssignedType, Value *V,
 133                                     IRBuilder<> &B);
 134   void replacePointerOperandWithPtrCast(Instruction *I, Value *Pointer,
 135                                         Type *ExpectedElementType,
 136                                         unsigned OperandToReplace,
 137                                         IRBuilder<> &B);
 138   void insertPtrCastOrAssignTypeInstr(Instruction *I, IRBuilder<> &B);
 139   void insertSpirvDecorations(Instruction *I, IRBuilder<> &B);
 140   void processGlobalValue(GlobalVariable &GV, IRBuilder<> &B);
 141   void processParamTypes(Function *F, IRBuilder<> &B);
 142   void processParamTypesByFunHeader(Function *F, IRBuilder<> &B);
 143   Type *deduceFunParamElementType(Function *F, unsigned OpIdx);
 144   Type *deduceFunParamElementType(Function *F, unsigned OpIdx,
 145                                   std::unordered_set<Function *> &FVisited);
 146
 147 public:
 148   static char ID;
 149   SPIRVEmitIntrinsics() : ModulePass(ID) {
 150     initializeSPIRVEmitIntrinsicsPass(*PassRegistry::getPassRegistry());
 151   }
 152   SPIRVEmitIntrinsics(SPIRVTargetMachine *_TM) : ModulePass(ID), TM(_TM) {
 153     initializeSPIRVEmitIntrinsicsPass(*PassRegistry::getPassRegistry());
 154   }
 155   Instruction *visitInstruction(Instruction &I) { return &I; }
 156   Instruction *visitSwitchInst(SwitchInst &I);
 157   Instruction *visitGetElementPtrInst(GetElementPtrInst &I);
 158   Instruction *visitBitCastInst(BitCastInst &I);
 159   Instruction *visitInsertElementInst(InsertElementInst &I);
 160   Instruction *visitExtractElementInst(ExtractElementInst &I);
 161   Instruction *visitInsertValueInst(InsertValueInst &I);
 162   Instruction *visitExtractValueInst(ExtractValueInst &I);
 163   Instruction *visitLoadInst(LoadInst &I);
 164   Instruction *visitStoreInst(StoreInst &I);
 165   Instruction *visitAllocaInst(AllocaInst &I);
 166   Instruction *visitAtomicCmpXchgInst(AtomicCmpXchgInst &I);
 167   Instruction *visitUnreachableInst(UnreachableInst &I);
 168   Instruction *visitCallInst(CallInst &I);
 169
 170   StringRef getPassName() const override { return "SPIRV emit intrinsics"; }
 171
 172   bool runOnModule(Module &M) override;
 173   bool runOnFunction(Function &F);
 174   bool postprocessTypes();
 175
 176   void getAnalysisUsage(AnalysisUsage &AU) const override {
 177     ModulePass::getAnalysisUsage(AU);
 178   }
 179 };
 180
 181 bool isConvergenceIntrinsic(const Instruction *I) {
 182   const auto *II = dyn_cast<IntrinsicInst>(I);
 183   if (!II)
 184     return false;
 185
 186   return II->getIntrinsicID() == Intrinsic::experimental_convergence_entry ||
 187          II->getIntrinsicID() == Intrinsic::experimental_convergence_loop ||
 188          II->getIntrinsicID() == Intrinsic::experimental_convergence_anchor;
 189 }
 190 } // namespace
 191
 192 char SPIRVEmitIntrinsics::ID = 0;
 193
 194 INITIALIZE_PASS(SPIRVEmitIntrinsics, "emit-intrinsics", "SPIRV emit intrinsics",
 195                 false, false)
 196
 197 static inline bool isAssignTypeInstr(const Instruction *I) {
 198   return isa<IntrinsicInst>(I) &&
 199          cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::spv_assign_type;
 200 }
 201
 202 static bool isMemInstrToReplace(Instruction *I) {
 203   return isa<StoreInst>(I) || isa<LoadInst>(I) || isa<InsertValueInst>(I) ||
 204          isa<ExtractValueInst>(I) || isa<AtomicCmpXchgInst>(I);
 205 }
 206
 207 static bool isAggrConstForceInt32(const Value *V) {
 208   return isa<ConstantArray>(V) || isa<ConstantStruct>(V) ||
 209          isa<ConstantDataArray>(V) ||
 210          (isa<ConstantAggregateZero>(V) && !V->getType()->isVectorTy());
 211 }
 212
 213 static void setInsertPointSkippingPhis(IRBuilder<> &B, Instruction *I) {
 214   if (isa<PHINode>(I))
 215     B.SetInsertPoint(I->getParent()->getFirstNonPHIOrDbgOrAlloca());
 216   else
 217     B.SetInsertPoint(I);
 218 }
 219
 220 static void setInsertPointAfterDef(IRBuilder<> &B, Instruction *I) {
 221   B.SetCurrentDebugLocation(I->getDebugLoc());
 222   if (I->getType()->isVoidTy())
 223     B.SetInsertPoint(I->getNextNode());
 224   else
 225     B.SetInsertPoint(*I->getInsertionPointAfterDef());
 226 }
 227
 228 static bool requireAssignType(Instruction *I) {
 229   IntrinsicInst *Intr = dyn_cast<IntrinsicInst>(I);
 230   if (Intr) {
 231     switch (Intr->getIntrinsicID()) {
 232     case Intrinsic::invariant_start:
 233     case Intrinsic::invariant_end:
 234       return false;
 235     }
 236   }
 237   return true;
 238 }
 239
 240 static inline void reportFatalOnTokenType(const Instruction *I) {
 241   if (I->getType()->isTokenTy())
 242     report_fatal_error("A token is encountered but SPIR-V without extensions "
 243                        "does not support token type",
 244                        false);
 245 }
 246
 247 static bool IsKernelArgInt8(Function *F, StoreInst *SI) {
 248   return SI && F->getCallingConv() == CallingConv::SPIR_KERNEL &&
 249          isPointerTy(SI->getValueOperand()->getType()) &&
 250          isa<Argument>(SI->getValueOperand());
 251 }
 252
 253 // Maybe restore original function return type.
 254 static inline Type *restoreMutatedType(SPIRVGlobalRegistry *GR, Instruction *I,
 255                                        Type *Ty) {
 256   CallInst *CI = dyn_cast<CallInst>(I);
 257   if (!CI || CI->isIndirectCall() || CI->isInlineAsm() ||
 258       !CI->getCalledFunction() || CI->getCalledFunction()->isIntrinsic())
 259     return Ty;
 260   if (Type *OriginalTy = GR->findMutated(CI->getCalledFunction()))
 261     return OriginalTy;
 262   return Ty;
 263 }
 264
 265 // Reconstruct type with nested element types according to deduced type info.
 266 // Return nullptr if no detailed type info is available.
 267 static inline Type *reconstructType(SPIRVGlobalRegistry *GR, Value *Op) {
 268   Type *Ty = Op->getType();
 269   if (!isUntypedPointerTy(Ty))
 270     return Ty;
 271   // try to find the pointee type
 272   if (Type *NestedTy = GR->findDeducedElementType(Op))
 273     return getTypedPointerWrapper(NestedTy, getPointerAddressSpace(Ty));
 274   // not a pointer according to the type info (e.g., Event object)
 275   CallInst *CI = GR->findAssignPtrTypeInstr(Op);
 276   if (!CI)
 277     return nullptr;
 278   MetadataAsValue *MD = cast<MetadataAsValue>(CI->getArgOperand(1));
 279   return cast<ConstantAsMetadata>(MD->getMetadata())->getType();
 280 }
 281
 282 void SPIRVEmitIntrinsics::buildAssignType(IRBuilder<> &B, Type *Ty,
 283                                           Value *Arg) {
 284   Value *OfType = PoisonValue::get(Ty);
 285   CallInst *AssignCI = buildIntrWithMD(Intrinsic::spv_assign_type,
 286                                        {Arg->getType()}, OfType, Arg, {}, B);
 287   GR->addAssignPtrTypeInstr(Arg, AssignCI);
 288 }
 289
 290 void SPIRVEmitIntrinsics::buildAssignPtr(IRBuilder<> &B, Type *ElemTy,
 291                                          Value *Arg) {
 292   Value *OfType = PoisonValue::get(ElemTy);
 293   CallInst *AssignPtrTyCI = GR->findAssignPtrTypeInstr(Arg);
 294   if (AssignPtrTyCI == nullptr ||
 295       AssignPtrTyCI->getParent()->getParent() != F) {
 296     AssignPtrTyCI = buildIntrWithMD(
 297         Intrinsic::spv_assign_ptr_type, {Arg->getType()}, OfType, Arg,
 298         {B.getInt32(getPointerAddressSpace(Arg->getType()))}, B);
 299     GR->addDeducedElementType(AssignPtrTyCI, ElemTy);
 300     GR->addDeducedElementType(Arg, ElemTy);
 301     GR->addAssignPtrTypeInstr(Arg, AssignPtrTyCI);
 302   } else {
 303     updateAssignType(AssignPtrTyCI, Arg, OfType);
 304   }
 305 }
 306
 307 void SPIRVEmitIntrinsics::updateAssignType(CallInst *AssignCI, Value *Arg,
 308                                            Value *OfType) {
 309   AssignCI->setArgOperand(1, buildMD(OfType));
 310   if (cast<IntrinsicInst>(AssignCI)->getIntrinsicID() !=
 311       Intrinsic::spv_assign_ptr_type)
 312     return;
 313
 314   // update association with the pointee type
 315   Type *ElemTy = OfType->getType();
 316   GR->addDeducedElementType(AssignCI, ElemTy);
 317   GR->addDeducedElementType(Arg, ElemTy);
 318 }
 319
 320 // Set element pointer type to the given value of ValueTy and tries to
 321 // specify this type further (recursively) by Operand value, if needed.
 322 Type *
 323 SPIRVEmitIntrinsics::deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,
 324                                                   bool UnknownElemTypeI8) {
 325   std::unordered_set<Value *> Visited;
 326   return deduceElementTypeByValueDeep(ValueTy, Operand, Visited,
 327                                       UnknownElemTypeI8);
 328 }
 329
 330 Type *SPIRVEmitIntrinsics::deduceElementTypeByValueDeep(
 331     Type *ValueTy, Value *Operand, std::unordered_set<Value *> &Visited,
 332     bool UnknownElemTypeI8) {
 333   Type *Ty = ValueTy;
 334   if (Operand) {
 335     if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
 336       if (Type *NestedTy =
 337               deduceElementTypeHelper(Operand, Visited, UnknownElemTypeI8))
 338         Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
 339     } else {
 340       Ty = deduceNestedTypeHelper(dyn_cast<User>(Operand), Ty, Visited,
 341                                   UnknownElemTypeI8);
 342     }
 343   }
 344   return Ty;
 345 }
 346
 347 // Traverse User instructions to deduce an element pointer type of the operand.
 348 Type *SPIRVEmitIntrinsics::deduceElementTypeByUsersDeep(
 349     Value *Op, std::unordered_set<Value *> &Visited, bool UnknownElemTypeI8) {
 350   if (!Op || !isPointerTy(Op->getType()))
 351     return nullptr;
 352
 353   if (auto ElemTy = getPointeeType(Op->getType()))
 354     return ElemTy;
 355
 356   // maybe we already know operand's element type
 357   if (Type *KnownTy = GR->findDeducedElementType(Op))
 358     return KnownTy;
 359
 360   for (User *OpU : Op->users()) {
 361     if (Instruction *Inst = dyn_cast<Instruction>(OpU)) {
 362       if (Type *Ty = deduceElementTypeHelper(Inst, Visited, UnknownElemTypeI8))
 363         return Ty;
 364     }
 365   }
 366   return nullptr;
 367 }
 368
 369 // Implements what we know in advance about intrinsics and builtin calls
 370 // TODO: consider feasibility of this particular case to be generalized by
 371 // encoding knowledge about intrinsics and builtin calls by corresponding
 372 // specification rules
 373 static Type *getPointeeTypeByCallInst(StringRef DemangledName,
 374                                       Function *CalledF, unsigned OpIdx) {
 375   if ((DemangledName.starts_with("__spirv_ocl_printf(") ||
 376        DemangledName.starts_with("printf(")) &&
 377       OpIdx == 0)
 378     return IntegerType::getInt8Ty(CalledF->getContext());
 379   return nullptr;
 380 }
 381
 382 // Deduce and return a successfully deduced Type of the Instruction,
 383 // or nullptr otherwise.
 384 Type *SPIRVEmitIntrinsics::deduceElementTypeHelper(Value *I,
 385                                                    bool UnknownElemTypeI8) {
 386   std::unordered_set<Value *> Visited;
 387   return deduceElementTypeHelper(I, Visited, UnknownElemTypeI8);
 388 }
 389
 390 void SPIRVEmitIntrinsics::maybeAssignPtrType(Type *&Ty, Value *Op, Type *RefTy,
 391                                              bool UnknownElemTypeI8) {
 392   if (isUntypedPointerTy(RefTy)) {
 393     if (!UnknownElemTypeI8)
 394       return;
 395     if (auto *I = dyn_cast<Instruction>(Op)) {
 396       UncompleteTypeInfo.insert(I);
 397       PostprocessWorklist.push_back(I);
 398     }
 399   }
 400   Ty = RefTy;
 401 }
 402
 403 Type *SPIRVEmitIntrinsics::deduceElementTypeHelper(
 404     Value *I, std::unordered_set<Value *> &Visited, bool UnknownElemTypeI8) {
 405   // allow to pass nullptr as an argument
 406   if (!I)
 407     return nullptr;
 408
 409   // maybe already known
 410   if (Type *KnownTy = GR->findDeducedElementType(I))
 411     return KnownTy;
 412
 413   // maybe a cycle
 414   if (Visited.find(I) != Visited.end())
 415     return nullptr;
 416   Visited.insert(I);
 417
 418   // fallback value in case when we fail to deduce a type
 419   Type *Ty = nullptr;
 420   // look for known basic patterns of type inference
 421   if (auto *Ref = dyn_cast<AllocaInst>(I)) {
 422     maybeAssignPtrType(Ty, I, Ref->getAllocatedType(), UnknownElemTypeI8);
 423   } else if (auto *Ref = dyn_cast<GetElementPtrInst>(I)) {
 424     Ty = Ref->getResultElementType();
 425   } else if (auto *Ref = dyn_cast<GlobalValue>(I)) {
 426     Ty = deduceElementTypeByValueDeep(
 427         Ref->getValueType(),
 428         Ref->getNumOperands() > 0 ? Ref->getOperand(0) : nullptr, Visited,
 429         UnknownElemTypeI8);
 430   } else if (auto *Ref = dyn_cast<AddrSpaceCastInst>(I)) {
 431     Type *RefTy = deduceElementTypeHelper(Ref->getPointerOperand(), Visited,
 432                                           UnknownElemTypeI8);
 433     maybeAssignPtrType(Ty, I, RefTy, UnknownElemTypeI8);
 434   } else if (auto *Ref = dyn_cast<BitCastInst>(I)) {
 435     if (Type *Src = Ref->getSrcTy(), *Dest = Ref->getDestTy();
 436         isPointerTy(Src) && isPointerTy(Dest))
 437       Ty = deduceElementTypeHelper(Ref->getOperand(0), Visited,
 438                                    UnknownElemTypeI8);
 439   } else if (auto *Ref = dyn_cast<AtomicCmpXchgInst>(I)) {
 440     Value *Op = Ref->getNewValOperand();
 441     if (isPointerTy(Op->getType()))
 442       Ty = deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8);
 443   } else if (auto *Ref = dyn_cast<AtomicRMWInst>(I)) {
 444     Value *Op = Ref->getValOperand();
 445     if (isPointerTy(Op->getType()))
 446       Ty = deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8);
 447   } else if (auto *Ref = dyn_cast<PHINode>(I)) {
 448     for (unsigned i = 0; i < Ref->getNumIncomingValues(); i++) {
 449       Ty = deduceElementTypeByUsersDeep(Ref->getIncomingValue(i), Visited,
 450                                         UnknownElemTypeI8);
 451       if (Ty)
 452         break;
 453     }
 454   } else if (auto *Ref = dyn_cast<SelectInst>(I)) {
 455     for (Value *Op : {Ref->getTrueValue(), Ref->getFalseValue()}) {
 456       Ty = deduceElementTypeByUsersDeep(Op, Visited, UnknownElemTypeI8);
 457       if (Ty)
 458         break;
 459     }
 460   } else if (auto *CI = dyn_cast<CallInst>(I)) {
 461     static StringMap<unsigned> ResTypeByArg = {
 462         {"to_global", 0},
 463         {"to_local", 0},
 464         {"to_private", 0},
 465         {"__spirv_GenericCastToPtr_ToGlobal", 0},
 466         {"__spirv_GenericCastToPtr_ToLocal", 0},
 467         {"__spirv_GenericCastToPtr_ToPrivate", 0},
 468         {"__spirv_GenericCastToPtrExplicit_ToGlobal", 0},
 469         {"__spirv_GenericCastToPtrExplicit_ToLocal", 0},
 470         {"__spirv_GenericCastToPtrExplicit_ToPrivate", 0}};
 471     // TODO: maybe improve performance by caching demangled names
 472     if (Function *CalledF = CI->getCalledFunction()) {
 473       std::string DemangledName =
 474           getOclOrSpirvBuiltinDemangledName(CalledF->getName());
 475       if (DemangledName.length() > 0)
 476         DemangledName = SPIRV::lookupBuiltinNameHelper(DemangledName);
 477       auto AsArgIt = ResTypeByArg.find(DemangledName);
 478       if (AsArgIt != ResTypeByArg.end()) {
 479         Ty = deduceElementTypeHelper(CI->getArgOperand(AsArgIt->second),
 480                                      Visited, UnknownElemTypeI8);
 481       }
 482     }
 483   }
 484
 485   // remember the found relationship
 486   if (Ty) {
 487     // specify nested types if needed, otherwise return unchanged
 488     GR->addDeducedElementType(I, Ty);
 489   }
 490
 491   return Ty;
 492 }
 493
 494 // Re-create a type of the value if it has untyped pointer fields, also nested.
 495 // Return the original value type if no corrections of untyped pointer
 496 // information is found or needed.
 497 Type *SPIRVEmitIntrinsics::deduceNestedTypeHelper(User *U,
 498                                                   bool UnknownElemTypeI8) {
 499   std::unordered_set<Value *> Visited;
 500   return deduceNestedTypeHelper(U, U->getType(), Visited, UnknownElemTypeI8);
 501 }
 502
 503 Type *SPIRVEmitIntrinsics::deduceNestedTypeHelper(
 504     User *U, Type *OrigTy, std::unordered_set<Value *> &Visited,
 505     bool UnknownElemTypeI8) {
 506   if (!U)
 507     return OrigTy;
 508
 509   // maybe already known
 510   if (Type *KnownTy = GR->findDeducedCompositeType(U))
 511     return KnownTy;
 512
 513   // maybe a cycle
 514   if (Visited.find(U) != Visited.end())
 515     return OrigTy;
 516   Visited.insert(U);
 517
 518   if (dyn_cast<StructType>(OrigTy)) {
 519     SmallVector<Type *> Tys;
 520     bool Change = false;
 521     for (unsigned i = 0; i < U->getNumOperands(); ++i) {
 522       Value *Op = U->getOperand(i);
 523       Type *OpTy = Op->getType();
 524       Type *Ty = OpTy;
 525       if (Op) {
 526         if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
 527           if (Type *NestedTy =
 528                   deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))
 529             Ty = TypedPointerType::get(NestedTy, PtrTy->getAddressSpace());
 530         } else {
 531           Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,
 532                                       UnknownElemTypeI8);
 533         }
 534       }
 535       Tys.push_back(Ty);
 536       Change |= Ty != OpTy;
 537     }
 538     if (Change) {
 539       Type *NewTy = StructType::create(Tys);
 540       GR->addDeducedCompositeType(U, NewTy);
 541       return NewTy;
 542     }
 543   } else if (auto *ArrTy = dyn_cast<ArrayType>(OrigTy)) {
 544     if (Value *Op = U->getNumOperands() > 0 ? U->getOperand(0) : nullptr) {
 545       Type *OpTy = ArrTy->getElementType();
 546       Type *Ty = OpTy;
 547       if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
 548         if (Type *NestedTy =
 549                 deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))
 550           Ty = TypedPointerType::get(NestedTy, PtrTy->getAddressSpace());
 551       } else {
 552         Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,
 553                                     UnknownElemTypeI8);
 554       }
 555       if (Ty != OpTy) {
 556         Type *NewTy = ArrayType::get(Ty, ArrTy->getNumElements());
 557         GR->addDeducedCompositeType(U, NewTy);
 558         return NewTy;
 559       }
 560     }
 561   } else if (auto *VecTy = dyn_cast<VectorType>(OrigTy)) {
 562     if (Value *Op = U->getNumOperands() > 0 ? U->getOperand(0) : nullptr) {
 563       Type *OpTy = VecTy->getElementType();
 564       Type *Ty = OpTy;
 565       if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
 566         if (Type *NestedTy =
 567                 deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))
 568           Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
 569       } else {
 570         Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,
 571                                     UnknownElemTypeI8);
 572       }
 573       if (Ty != OpTy) {
 574         Type *NewTy = VectorType::get(Ty, VecTy->getElementCount());
 575         GR->addDeducedCompositeType(U, NewTy);
 576         return NewTy;
 577       }
 578     }
 579   }
 580
 581   return OrigTy;
 582 }
 583
 584 Type *SPIRVEmitIntrinsics::deduceElementType(Value *I, bool UnknownElemTypeI8) {
 585   if (Type *Ty = deduceElementTypeHelper(I, UnknownElemTypeI8))
 586     return Ty;
 587   if (!UnknownElemTypeI8)
 588     return nullptr;
 589   if (auto *Instr = dyn_cast<Instruction>(I)) {
 590     UncompleteTypeInfo.insert(Instr);
 591     PostprocessWorklist.push_back(Instr);
 592   }
 593   return IntegerType::getInt8Ty(I->getContext());
 594 }
 595
 596 static inline Type *getAtomicElemTy(SPIRVGlobalRegistry *GR, Instruction *I,
 597                                     Value *PointerOperand) {
 598   Type *PointeeTy = GR->findDeducedElementType(PointerOperand);
 599   if (PointeeTy && !isUntypedPointerTy(PointeeTy))
 600     return nullptr;
 601   auto *PtrTy = dyn_cast<PointerType>(I->getType());
 602   if (!PtrTy)
 603     return I->getType();
 604   if (Type *NestedTy = GR->findDeducedElementType(I))
 605     return getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
 606   return nullptr;
 607 }
 608
 609 // If the Instruction has Pointer operands with unresolved types, this function
 610 // tries to deduce them. If the Instruction has Pointer operands with known
 611 // types which differ from expected, this function tries to insert a bitcast to
 612 // resolve the issue.
 613 void SPIRVEmitIntrinsics::deduceOperandElementType(Instruction *I,
 614                                                    Instruction *AskOp,
 615                                                    Type *AskTy,
 616                                                    CallInst *AskCI) {
 617   SmallVector<std::pair<Value *, unsigned>> Ops;
 618   Type *KnownElemTy = nullptr;
 619   // look for known basic patterns of type inference
 620   if (auto *Ref = dyn_cast<PHINode>(I)) {
 621     if (!isPointerTy(I->getType()) ||
 622         !(KnownElemTy = GR->findDeducedElementType(I)))
 623       return;
 624     for (unsigned i = 0; i < Ref->getNumIncomingValues(); i++) {
 625       Value *Op = Ref->getIncomingValue(i);
 626       if (isPointerTy(Op->getType()))
 627         Ops.push_back(std::make_pair(Op, i));
 628     }
 629   } else if (auto *Ref = dyn_cast<AddrSpaceCastInst>(I)) {
 630     KnownElemTy = GR->findDeducedElementType(I);
 631     if (!KnownElemTy)
 632       return;
 633     Ops.push_back(std::make_pair(Ref->getPointerOperand(), 0));
 634   } else if (auto *Ref = dyn_cast<GetElementPtrInst>(I)) {
 635     KnownElemTy = Ref->getSourceElementType();
 636     if (isUntypedPointerTy(KnownElemTy))
 637       return;
 638     Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());
 639     if (PointeeTy && !isUntypedPointerTy(PointeeTy))
 640       return;
 641     Ops.push_back(std::make_pair(Ref->getPointerOperand(),
 642                                  GetElementPtrInst::getPointerOperandIndex()));
 643   } else if (auto *Ref = dyn_cast<LoadInst>(I)) {
 644     KnownElemTy = I->getType();
 645     if (isUntypedPointerTy(KnownElemTy))
 646       return;
 647     Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());
 648     if (PointeeTy && !isUntypedPointerTy(PointeeTy))
 649       return;
 650     Ops.push_back(std::make_pair(Ref->getPointerOperand(),
 651                                  LoadInst::getPointerOperandIndex()));
 652   } else if (auto *Ref = dyn_cast<StoreInst>(I)) {
 653     if (IsKernelArgInt8(Ref->getParent()->getParent(), Ref))
 654       return;
 655     if (!(KnownElemTy = reconstructType(GR, Ref->getValueOperand())))
 656       return;
 657     Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());
 658     if (PointeeTy && !isUntypedPointerTy(PointeeTy))
 659       return;
 660     Ops.push_back(std::make_pair(Ref->getPointerOperand(),
 661                                  StoreInst::getPointerOperandIndex()));
 662   } else if (auto *Ref = dyn_cast<AtomicCmpXchgInst>(I)) {
 663     KnownElemTy = getAtomicElemTy(GR, I, Ref->getPointerOperand());
 664     if (!KnownElemTy)
 665       return;
 666     Ops.push_back(std::make_pair(Ref->getPointerOperand(),
 667                                  AtomicCmpXchgInst::getPointerOperandIndex()));
 668   } else if (auto *Ref = dyn_cast<AtomicRMWInst>(I)) {
 669     KnownElemTy = getAtomicElemTy(GR, I, Ref->getPointerOperand());
 670     if (!KnownElemTy)
 671       return;
 672     Ops.push_back(std::make_pair(Ref->getPointerOperand(),
 673                                  AtomicRMWInst::getPointerOperandIndex()));
 674   } else if (auto *Ref = dyn_cast<SelectInst>(I)) {
 675     if (!isPointerTy(I->getType()) ||
 676         !(KnownElemTy = GR->findDeducedElementType(I)))
 677       return;
 678     for (unsigned i = 0; i < Ref->getNumOperands(); i++) {
 679       Value *Op = Ref->getOperand(i);
 680       if (isPointerTy(Op->getType()))
 681         Ops.push_back(std::make_pair(Op, i));
 682     }
 683   } else if (auto *Ref = dyn_cast<ReturnInst>(I)) {
 684     Type *RetTy = F->getReturnType();
 685     if (!isPointerTy(RetTy))
 686       return;
 687     Value *Op = Ref->getReturnValue();
 688     if (!Op)
 689       return;
 690     if (!(KnownElemTy = GR->findDeducedElementType(F))) {
 691       if (Type *OpElemTy = GR->findDeducedElementType(Op)) {
 692         GR->addDeducedElementType(F, OpElemTy);
 693         TypedPointerType *DerivedTy =
 694             TypedPointerType::get(OpElemTy, getPointerAddressSpace(RetTy));
 695         GR->addReturnType(F, DerivedTy);
 696       }
 697       return;
 698     }
 699     Ops.push_back(std::make_pair(Op, 0));
 700   } else if (auto *Ref = dyn_cast<ICmpInst>(I)) {
 701     if (!isPointerTy(Ref->getOperand(0)->getType()))
 702       return;
 703     Value *Op0 = Ref->getOperand(0);
 704     Value *Op1 = Ref->getOperand(1);
 705     Type *ElemTy0 = GR->findDeducedElementType(Op0);
 706     Type *ElemTy1 = GR->findDeducedElementType(Op1);
 707     if (ElemTy0) {
 708       KnownElemTy = ElemTy0;
 709       Ops.push_back(std::make_pair(Op1, 1));
 710     } else if (ElemTy1) {
 711       KnownElemTy = ElemTy1;
 712       Ops.push_back(std::make_pair(Op0, 0));
 713     }
 714   } else if (auto *CI = dyn_cast<CallInst>(I)) {
 715     if (Function *CalledF = CI->getCalledFunction()) {
 716       std::string DemangledName =
 717           getOclOrSpirvBuiltinDemangledName(CalledF->getName());
 718       if (DemangledName.length() > 0 &&
 719           !StringRef(DemangledName).starts_with("llvm.")) {
 720         auto [Grp, Opcode, ExtNo] =
 721             SPIRV::mapBuiltinToOpcode(DemangledName, InstrSet);
 722         if (Opcode == SPIRV::OpGroupAsyncCopy) {
 723           for (unsigned i = 0, PtrCnt = 0; i < CI->arg_size() && PtrCnt < 2;
 724                ++i) {
 725             Value *Op = CI->getArgOperand(i);
 726             if (!isPointerTy(Op->getType()))
 727               continue;
 728             ++PtrCnt;
 729             if (Type *ElemTy = GR->findDeducedElementType(Op))
 730               KnownElemTy = ElemTy; // src will rewrite dest if both are defined
 731             Ops.push_back(std::make_pair(Op, i));
 732           }
 733         } else if (Grp == SPIRV::Atomic || Grp == SPIRV::AtomicFloating) {
 734           if (CI->arg_size() < 2)
 735             return;
 736           Value *Op = CI->getArgOperand(0);
 737           if (!isPointerTy(Op->getType()))
 738             return;
 739           switch (Opcode) {
 740           case SPIRV::OpAtomicLoad:
 741           case SPIRV::OpAtomicCompareExchangeWeak:
 742           case SPIRV::OpAtomicCompareExchange:
 743           case SPIRV::OpAtomicExchange:
 744           case SPIRV::OpAtomicIAdd:
 745           case SPIRV::OpAtomicISub:
 746           case SPIRV::OpAtomicOr:
 747           case SPIRV::OpAtomicXor:
 748           case SPIRV::OpAtomicAnd:
 749           case SPIRV::OpAtomicUMin:
 750           case SPIRV::OpAtomicUMax:
 751           case SPIRV::OpAtomicSMin:
 752           case SPIRV::OpAtomicSMax: {
 753             KnownElemTy = getAtomicElemTy(GR, I, Op);
 754             if (!KnownElemTy)
 755               return;
 756             Ops.push_back(std::make_pair(Op, 0));
 757           } break;
 758           }
 759         }
 760       }
 761     }
 762   }
 763
 764   // There is no enough info to deduce types or all is valid.
 765   if (!KnownElemTy || Ops.size() == 0)
 766     return;
 767
 768   LLVMContext &Ctx = F->getContext();
 769   IRBuilder<> B(Ctx);
 770   for (auto &OpIt : Ops) {
 771     Value *Op = OpIt.first;
 772     if (Op->use_empty() || (AskOp && Op != AskOp))
 773       continue;
 774     Type *Ty = AskOp ? AskTy : GR->findDeducedElementType(Op);
 775     if (Ty == KnownElemTy)
 776       continue;
 777     Value *OpTyVal = PoisonValue::get(KnownElemTy);
 778     Type *OpTy = Op->getType();
 779     if (!Ty || AskTy || isUntypedPointerTy(Ty) ||
 780         UncompleteTypeInfo.contains(Op)) {
 781       GR->addDeducedElementType(Op, KnownElemTy);
 782       // check if there is existing Intrinsic::spv_assign_ptr_type instruction
 783       CallInst *AssignCI = AskCI ? AskCI : GR->findAssignPtrTypeInstr(Op);
 784       if (AssignCI == nullptr) {
 785         Instruction *User = dyn_cast<Instruction>(Op->use_begin()->get());
 786         setInsertPointSkippingPhis(B, User ? User->getNextNode() : I);
 787         CallInst *CI =
 788             buildIntrWithMD(Intrinsic::spv_assign_ptr_type, {OpTy}, OpTyVal, Op,
 789                             {B.getInt32(getPointerAddressSpace(OpTy))}, B);
 790         GR->addAssignPtrTypeInstr(Op, CI);
 791       } else {
 792         updateAssignType(AssignCI, Op, OpTyVal);
 793       }
 794     } else {
 795       if (auto *OpI = dyn_cast<Instruction>(Op)) {
 796         // spv_ptrcast's argument Op denotes an instruction that generates
 797         // a value, and we may use getInsertionPointAfterDef()
 798         B.SetInsertPoint(*OpI->getInsertionPointAfterDef());
 799         B.SetCurrentDebugLocation(OpI->getDebugLoc());
 800       } else if (auto *OpA = dyn_cast<Argument>(Op)) {
 801         B.SetInsertPointPastAllocas(OpA->getParent());
 802         B.SetCurrentDebugLocation(DebugLoc());
 803       } else {
 804         B.SetInsertPoint(F->getEntryBlock().getFirstNonPHIOrDbgOrAlloca());
 805       }
 806       SmallVector<Type *, 2> Types = {OpTy, OpTy};
 807       SmallVector<Value *, 2> Args = {Op, buildMD(OpTyVal),
 808                                       B.getInt32(getPointerAddressSpace(OpTy))};
 809       CallInst *PtrCastI =
 810           B.CreateIntrinsic(Intrinsic::spv_ptrcast, {Types}, Args);
 811       I->setOperand(OpIt.second, PtrCastI);
 812     }
 813   }
 814 }
 815
 816 void SPIRVEmitIntrinsics::replaceMemInstrUses(Instruction *Old,
 817                                               Instruction *New,
 818                                               IRBuilder<> &B) {
 819   while (!Old->user_empty()) {
 820     auto *U = Old->user_back();
 821     if (isAssignTypeInstr(U)) {
 822       B.SetInsertPoint(U);
 823       SmallVector<Value *, 2> Args = {New, U->getOperand(1)};
 824       CallInst *AssignCI =
 825           B.CreateIntrinsic(Intrinsic::spv_assign_type, {New->getType()}, Args);
 826       GR->addAssignPtrTypeInstr(New, AssignCI);
 827       U->eraseFromParent();
 828     } else if (isMemInstrToReplace(U) || isa<ReturnInst>(U) ||
 829                isa<CallInst>(U)) {
 830       U->replaceUsesOfWith(Old, New);
 831     } else {
 832       llvm_unreachable("illegal aggregate intrinsic user");
 833     }
 834   }
 835   Old->eraseFromParent();
 836 }
 837
 838 void SPIRVEmitIntrinsics::preprocessUndefs(IRBuilder<> &B) {
 839   std::queue<Instruction *> Worklist;
 840   for (auto &I : instructions(F))
 841     Worklist.push(&I);
 842
 843   while (!Worklist.empty()) {
 844     Instruction *I = Worklist.front();
 845     bool BPrepared = false;
 846     Worklist.pop();
 847
 848     for (auto &Op : I->operands()) {
 849       auto *AggrUndef = dyn_cast<UndefValue>(Op);
 850       if (!AggrUndef || !Op->getType()->isAggregateType())
 851         continue;
 852
 853       if (!BPrepared) {
 854         setInsertPointSkippingPhis(B, I);
 855         BPrepared = true;
 856       }
 857       auto *IntrUndef = B.CreateIntrinsic(Intrinsic::spv_undef, {}, {});
 858       Worklist.push(IntrUndef);
 859       I->replaceUsesOfWith(Op, IntrUndef);
 860       AggrConsts[IntrUndef] = AggrUndef;
 861       AggrConstTypes[IntrUndef] = AggrUndef->getType();
 862     }
 863   }
 864 }
 865
 866 void SPIRVEmitIntrinsics::preprocessCompositeConstants(IRBuilder<> &B) {
 867   std::queue<Instruction *> Worklist;
 868   for (auto &I : instructions(F))
 869     Worklist.push(&I);
 870
 871   while (!Worklist.empty()) {
 872     auto *I = Worklist.front();
 873     bool IsPhi = isa<PHINode>(I), BPrepared = false;
 874     assert(I);
 875     bool KeepInst = false;
 876     for (const auto &Op : I->operands()) {
 877       Constant *AggrConst = nullptr;
 878       Type *ResTy = nullptr;
 879       if (auto *COp = dyn_cast<ConstantVector>(Op)) {
 880         AggrConst = cast<Constant>(COp);
 881         ResTy = COp->getType();
 882       } else if (auto *COp = dyn_cast<ConstantArray>(Op)) {
 883         AggrConst = cast<Constant>(COp);
 884         ResTy = B.getInt32Ty();
 885       } else if (auto *COp = dyn_cast<ConstantStruct>(Op)) {
 886         AggrConst = cast<Constant>(COp);
 887         ResTy = B.getInt32Ty();
 888       } else if (auto *COp = dyn_cast<ConstantDataArray>(Op)) {
 889         AggrConst = cast<Constant>(COp);
 890         ResTy = B.getInt32Ty();
 891       } else if (auto *COp = dyn_cast<ConstantAggregateZero>(Op)) {
 892         AggrConst = cast<Constant>(COp);
 893         ResTy = Op->getType()->isVectorTy() ? COp->getType() : B.getInt32Ty();
 894       }
 895       if (AggrConst) {
 896         SmallVector<Value *> Args;
 897         if (auto *COp = dyn_cast<ConstantDataSequential>(Op))
 898           for (unsigned i = 0; i < COp->getNumElements(); ++i)
 899             Args.push_back(COp->getElementAsConstant(i));
 900         else
 901           for (auto &COp : AggrConst->operands())
 902             Args.push_back(COp);
 903         if (!BPrepared) {
 904           IsPhi ? B.SetInsertPointPastAllocas(I->getParent()->getParent())
 905                 : B.SetInsertPoint(I);
 906           BPrepared = true;
 907         }
 908         auto *CI =
 909             B.CreateIntrinsic(Intrinsic::spv_const_composite, {ResTy}, {Args});
 910         Worklist.push(CI);
 911         I->replaceUsesOfWith(Op, CI);
 912         KeepInst = true;
 913         AggrConsts[CI] = AggrConst;
 914         AggrConstTypes[CI] = deduceNestedTypeHelper(AggrConst, false);
 915       }
 916     }
 917     if (!KeepInst)
 918       Worklist.pop();
 919   }
 920 }
 921
 922 Instruction *SPIRVEmitIntrinsics::visitCallInst(CallInst &Call) {
 923   if (!Call.isInlineAsm())
 924     return &Call;
 925
 926   const InlineAsm *IA = cast<InlineAsm>(Call.getCalledOperand());
 927   LLVMContext &Ctx = F->getContext();
 928
 929   Constant *TyC = UndefValue::get(IA->getFunctionType());
 930   MDString *ConstraintString = MDString::get(Ctx, IA->getConstraintString());
 931   SmallVector<Value *> Args = {
 932       buildMD(TyC),
 933       MetadataAsValue::get(Ctx, MDNode::get(Ctx, ConstraintString))};
 934   for (unsigned OpIdx = 0; OpIdx < Call.arg_size(); OpIdx++)
 935     Args.push_back(Call.getArgOperand(OpIdx));
 936
 937   IRBuilder<> B(Call.getParent());
 938   B.SetInsertPoint(&Call);
 939   B.CreateIntrinsic(Intrinsic::spv_inline_asm, {}, {Args});
 940   return &Call;
 941 }
 942
 943 Instruction *SPIRVEmitIntrinsics::visitSwitchInst(SwitchInst &I) {
 944   BasicBlock *ParentBB = I.getParent();
 945   IRBuilder<> B(ParentBB);
 946   B.SetInsertPoint(&I);
 947   SmallVector<Value *, 4> Args;
 948   SmallVector<BasicBlock *> BBCases;
 949   for (auto &Op : I.operands()) {
 950     if (Op.get()->getType()->isSized()) {
 951       Args.push_back(Op);
 952     } else if (BasicBlock *BB = dyn_cast<BasicBlock>(Op.get())) {
 953       BBCases.push_back(BB);
 954       Args.push_back(BlockAddress::get(BB->getParent(), BB));
 955     } else {
 956       report_fatal_error("Unexpected switch operand");
 957     }
 958   }
 959   CallInst *NewI = B.CreateIntrinsic(Intrinsic::spv_switch,
 960                                      {I.getOperand(0)->getType()}, {Args});
 961   // remove switch to avoid its unneeded and undesirable unwrap into branches
 962   // and conditions
 963   I.replaceAllUsesWith(NewI);
 964   I.eraseFromParent();
 965   // insert artificial and temporary instruction to preserve valid CFG,
 966   // it will be removed after IR translation pass
 967   B.SetInsertPoint(ParentBB);
 968   IndirectBrInst *BrI = B.CreateIndirectBr(
 969       Constant::getNullValue(PointerType::getUnqual(ParentBB->getContext())),
 970       BBCases.size());
 971   for (BasicBlock *BBCase : BBCases)
 972     BrI->addDestination(BBCase);
 973   return BrI;
 974 }
 975
 976 Instruction *SPIRVEmitIntrinsics::visitGetElementPtrInst(GetElementPtrInst &I) {
 977   IRBuilder<> B(I.getParent());
 978   B.SetInsertPoint(&I);
 979   SmallVector<Type *, 2> Types = {I.getType(), I.getOperand(0)->getType()};
 980   SmallVector<Value *, 4> Args;
 981   Args.push_back(B.getInt1(I.isInBounds()));
 982   for (auto &Op : I.operands())
 983     Args.push_back(Op);
 984   auto *NewI = B.CreateIntrinsic(Intrinsic::spv_gep, {Types}, {Args});
 985   I.replaceAllUsesWith(NewI);
 986   I.eraseFromParent();
 987   return NewI;
 988 }
 989
 990 Instruction *SPIRVEmitIntrinsics::visitBitCastInst(BitCastInst &I) {
 991   IRBuilder<> B(I.getParent());
 992   B.SetInsertPoint(&I);
 993   Value *Source = I.getOperand(0);
 994
 995   // SPIR-V, contrary to LLVM 17+ IR, supports bitcasts between pointers of
 996   // varying element types. In case of IR coming from older versions of LLVM
 997   // such bitcasts do not provide sufficient information, should be just skipped
 998   // here, and handled in insertPtrCastOrAssignTypeInstr.
 999   if (isPointerTy(I.getType())) {
1000     I.replaceAllUsesWith(Source);
1001     I.eraseFromParent();
1002     return nullptr;
1003   }
1004
1005   SmallVector<Type *, 2> Types = {I.getType(), Source->getType()};
1006   SmallVector<Value *> Args(I.op_begin(), I.op_end());
1007   auto *NewI = B.CreateIntrinsic(Intrinsic::spv_bitcast, {Types}, {Args});
1008   std::string InstName = I.hasName() ? I.getName().str() : "";
1009   I.replaceAllUsesWith(NewI);
1010   I.eraseFromParent();
1011   NewI->setName(InstName);
1012   return NewI;
1013 }
1014
1015 void SPIRVEmitIntrinsics::insertAssignPtrTypeTargetExt(
1016     TargetExtType *AssignedType, Value *V, IRBuilder<> &B) {
1017   Type *VTy = V->getType();
1018
1019   // A couple of sanity checks.
1020   assert(isPointerTy(VTy) && "Expect a pointer type!");
1021   if (auto PType = dyn_cast<TypedPointerType>(VTy))
1022     if (PType->getElementType() != AssignedType)
1023       report_fatal_error("Unexpected pointer element type!");
1024
1025   CallInst *AssignCI = GR->findAssignPtrTypeInstr(V);
1026   if (!AssignCI) {
1027     buildAssignType(B, AssignedType, V);
1028     return;
1029   }
1030
1031   Type *CurrentType =
1032       dyn_cast<ConstantAsMetadata>(
1033           cast<MetadataAsValue>(AssignCI->getOperand(1))->getMetadata())
1034           ->getType();
1035   if (CurrentType == AssignedType)
1036     return;
1037
1038   // Builtin types cannot be redeclared or casted.
1039   if (CurrentType->isTargetExtTy())
1040     report_fatal_error("Type mismatch " + CurrentType->getTargetExtName() +
1041                            "/" + AssignedType->getTargetExtName() +
1042                            " for value " + V->getName(),
1043                        false);
1044
1045   // Our previous guess about the type seems to be wrong, let's update
1046   // inferred type according to a new, more precise type information.
1047   updateAssignType(AssignCI, V, PoisonValue::get(AssignedType));
1048 }
1049
1050 void SPIRVEmitIntrinsics::replacePointerOperandWithPtrCast(
1051     Instruction *I, Value *Pointer, Type *ExpectedElementType,
1052     unsigned OperandToReplace, IRBuilder<> &B) {
1053   // If Pointer is the result of nop BitCastInst (ptr -> ptr), use the source
1054   // pointer instead. The BitCastInst should be later removed when visited.
1055   while (BitCastInst *BC = dyn_cast<BitCastInst>(Pointer))
1056     Pointer = BC->getOperand(0);
1057
1058   // Do not emit spv_ptrcast if Pointer's element type is ExpectedElementType
1059   Type *PointerElemTy = deduceElementTypeHelper(Pointer, false);
1060   if (PointerElemTy == ExpectedElementType ||
1061       isEquivalentTypes(PointerElemTy, ExpectedElementType))
1062     return;
1063
1064   setInsertPointSkippingPhis(B, I);
1065   MetadataAsValue *VMD = buildMD(PoisonValue::get(ExpectedElementType));
1066   unsigned AddressSpace = getPointerAddressSpace(Pointer->getType());
1067   bool FirstPtrCastOrAssignPtrType = true;
1068
1069   // Do not emit new spv_ptrcast if equivalent one already exists or when
1070   // spv_assign_ptr_type already targets this pointer with the same element
1071   // type.
1072   for (auto User : Pointer->users()) {
1073     auto *II = dyn_cast<IntrinsicInst>(User);
1074     if (!II ||
1075         (II->getIntrinsicID() != Intrinsic::spv_assign_ptr_type &&
1076          II->getIntrinsicID() != Intrinsic::spv_ptrcast) ||
1077         II->getOperand(0) != Pointer)
1078       continue;
1079
1080     // There is some spv_ptrcast/spv_assign_ptr_type already targeting this
1081     // pointer.
1082     FirstPtrCastOrAssignPtrType = false;
1083     if (II->getOperand(1) != VMD ||
1084         dyn_cast<ConstantInt>(II->getOperand(2))->getSExtValue() !=
1085             AddressSpace)
1086       continue;
1087
1088     // The spv_ptrcast/spv_assign_ptr_type targeting this pointer is of the same
1089     // element type and address space.
1090     if (II->getIntrinsicID() != Intrinsic::spv_ptrcast)
1091       return;
1092
1093     // This must be a spv_ptrcast, do not emit new if this one has the same BB
1094     // as I. Otherwise, search for other spv_ptrcast/spv_assign_ptr_type.
1095     if (II->getParent() != I->getParent())
1096       continue;
1097
1098     I->setOperand(OperandToReplace, II);
1099     return;
1100   }
1101
1102   // // Do not emit spv_ptrcast if it would cast to the default pointer element
1103   // // type (i8) of the same address space.
1104   // if (ExpectedElementType->isIntegerTy(8))
1105   //   return;
1106
1107   // If this would be the first spv_ptrcast, do not emit spv_ptrcast and emit
1108   // spv_assign_ptr_type instead.
1109   if (FirstPtrCastOrAssignPtrType &&
1110       (isa<Instruction>(Pointer) || isa<Argument>(Pointer))) {
1111     buildAssignPtr(B, ExpectedElementType, Pointer);
1112     return;
1113   }
1114
1115   // Emit spv_ptrcast
1116   SmallVector<Type *, 2> Types = {Pointer->getType(), Pointer->getType()};
1117   SmallVector<Value *, 2> Args = {Pointer, VMD, B.getInt32(AddressSpace)};
1118   auto *PtrCastI = B.CreateIntrinsic(Intrinsic::spv_ptrcast, {Types}, Args);
1119   I->setOperand(OperandToReplace, PtrCastI);
1120 }
1121
1122 void SPIRVEmitIntrinsics::insertPtrCastOrAssignTypeInstr(Instruction *I,
1123                                                          IRBuilder<> &B) {
1124   // Handle basic instructions:
1125   StoreInst *SI = dyn_cast<StoreInst>(I);
1126   if (IsKernelArgInt8(F, SI)) {
1127     return replacePointerOperandWithPtrCast(
1128         I, SI->getValueOperand(), IntegerType::getInt8Ty(F->getContext()), 0,
1129         B);
1130   } else if (SI) {
1131     Value *Op = SI->getValueOperand();
1132     Type *OpTy = Op->getType();
1133     if (auto *OpI = dyn_cast<Instruction>(Op))
1134       OpTy = restoreMutatedType(GR, OpI, OpTy);
1135     if (OpTy == Op->getType())
1136       OpTy = deduceElementTypeByValueDeep(OpTy, Op, false);
1137     return replacePointerOperandWithPtrCast(I, SI->getPointerOperand(), OpTy, 1,
1138                                             B);
1139   } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1140     return replacePointerOperandWithPtrCast(I, LI->getPointerOperand(),
1141                                             LI->getType(), 0, B);
1142   } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1143     return replacePointerOperandWithPtrCast(I, GEPI->getPointerOperand(),
1144                                             GEPI->getSourceElementType(), 0, B);
1145   }
1146
1147   // Handle calls to builtins (non-intrinsics):
1148   CallInst *CI = dyn_cast<CallInst>(I);
1149   if (!CI || CI->isIndirectCall() || CI->isInlineAsm() ||
1150       !CI->getCalledFunction() || CI->getCalledFunction()->isIntrinsic())
1151     return;
1152
1153   // collect information about formal parameter types
1154   std::string DemangledName =
1155       getOclOrSpirvBuiltinDemangledName(CI->getCalledFunction()->getName());
1156   Function *CalledF = CI->getCalledFunction();
1157   SmallVector<Type *, 4> CalledArgTys;
1158   bool HaveTypes = false;
1159   for (unsigned OpIdx = 0; OpIdx < CalledF->arg_size(); ++OpIdx) {
1160     Argument *CalledArg = CalledF->getArg(OpIdx);
1161     Type *ArgType = CalledArg->getType();
1162     if (!isPointerTy(ArgType)) {
1163       CalledArgTys.push_back(nullptr);
1164     } else if (isTypedPointerTy(ArgType)) {
1165       CalledArgTys.push_back(cast<TypedPointerType>(ArgType)->getElementType());
1166       HaveTypes = true;
1167     } else {
1168       Type *ElemTy = GR->findDeducedElementType(CalledArg);
1169       if (!ElemTy && hasPointeeTypeAttr(CalledArg))
1170         ElemTy = getPointeeTypeByAttr(CalledArg);
1171       if (!ElemTy) {
1172         ElemTy = getPointeeTypeByCallInst(DemangledName, CalledF, OpIdx);
1173         if (ElemTy) {
1174           GR->addDeducedElementType(CalledArg, ElemTy);
1175         } else {
1176           for (User *U : CalledArg->users()) {
1177             if (Instruction *Inst = dyn_cast<Instruction>(U)) {
1178               if ((ElemTy = deduceElementTypeHelper(Inst, false)) != nullptr)
1179                 break;
1180             }
1181           }
1182         }
1183       }
1184       HaveTypes |= ElemTy != nullptr;
1185       CalledArgTys.push_back(ElemTy);
1186     }
1187   }
1188
1189   if (DemangledName.empty() && !HaveTypes)
1190     return;
1191
1192   for (unsigned OpIdx = 0; OpIdx < CI->arg_size(); OpIdx++) {
1193     Value *ArgOperand = CI->getArgOperand(OpIdx);
1194     if (!isPointerTy(ArgOperand->getType()))
1195       continue;
1196
1197     // Constants (nulls/undefs) are handled in insertAssignPtrTypeIntrs()
1198     if (!isa<Instruction>(ArgOperand) && !isa<Argument>(ArgOperand)) {
1199       // However, we may have assumptions about the formal argument's type and
1200       // may have a need to insert a ptr cast for the actual parameter of this
1201       // call.
1202       Argument *CalledArg = CalledF->getArg(OpIdx);
1203       if (!GR->findDeducedElementType(CalledArg))
1204         continue;
1205     }
1206
1207     Type *ExpectedType =
1208         OpIdx < CalledArgTys.size() ? CalledArgTys[OpIdx] : nullptr;
1209     if (!ExpectedType && !DemangledName.empty())
1210       ExpectedType = SPIRV::parseBuiltinCallArgumentBaseType(
1211           DemangledName, OpIdx, I->getContext());
1212     if (!ExpectedType || ExpectedType->isVoidTy())
1213       continue;
1214
1215     if (ExpectedType->isTargetExtTy())
1216       insertAssignPtrTypeTargetExt(cast<TargetExtType>(ExpectedType),
1217                                    ArgOperand, B);
1218     else
1219       replacePointerOperandWithPtrCast(CI, ArgOperand, ExpectedType, OpIdx, B);
1220   }
1221 }
1222
1223 Instruction *SPIRVEmitIntrinsics::visitInsertElementInst(InsertElementInst &I) {
1224   SmallVector<Type *, 4> Types = {I.getType(), I.getOperand(0)->getType(),
1225                                   I.getOperand(1)->getType(),
1226                                   I.getOperand(2)->getType()};
1227   IRBuilder<> B(I.getParent());
1228   B.SetInsertPoint(&I);
1229   SmallVector<Value *> Args(I.op_begin(), I.op_end());
1230   auto *NewI = B.CreateIntrinsic(Intrinsic::spv_insertelt, {Types}, {Args});
1231   std::string InstName = I.hasName() ? I.getName().str() : "";
1232   I.replaceAllUsesWith(NewI);
1233   I.eraseFromParent();
1234   NewI->setName(InstName);
1235   return NewI;
1236 }
1237
1238 Instruction *
1239 SPIRVEmitIntrinsics::visitExtractElementInst(ExtractElementInst &I) {
1240   IRBuilder<> B(I.getParent());
1241   B.SetInsertPoint(&I);
1242   SmallVector<Type *, 3> Types = {I.getType(), I.getVectorOperandType(),
1243                                   I.getIndexOperand()->getType()};
1244   SmallVector<Value *, 2> Args = {I.getVectorOperand(), I.getIndexOperand()};
1245   auto *NewI = B.CreateIntrinsic(Intrinsic::spv_extractelt, {Types}, {Args});
1246   std::string InstName = I.hasName() ? I.getName().str() : "";
1247   I.replaceAllUsesWith(NewI);
1248   I.eraseFromParent();
1249   NewI->setName(InstName);
1250   return NewI;
1251 }
1252
1253 Instruction *SPIRVEmitIntrinsics::visitInsertValueInst(InsertValueInst &I) {
1254   IRBuilder<> B(I.getParent());
1255   B.SetInsertPoint(&I);
1256   SmallVector<Type *, 1> Types = {I.getInsertedValueOperand()->getType()};
1257   SmallVector<Value *> Args;
1258   for (auto &Op : I.operands())
1259     if (isa<UndefValue>(Op))
1260       Args.push_back(UndefValue::get(B.getInt32Ty()));
1261     else
1262       Args.push_back(Op);
1263   for (auto &Op : I.indices())
1264     Args.push_back(B.getInt32(Op));
1265   Instruction *NewI =
1266       B.CreateIntrinsic(Intrinsic::spv_insertv, {Types}, {Args});
1267   replaceMemInstrUses(&I, NewI, B);
1268   return NewI;
1269 }
1270
1271 Instruction *SPIRVEmitIntrinsics::visitExtractValueInst(ExtractValueInst &I) {
1272   IRBuilder<> B(I.getParent());
1273   B.SetInsertPoint(&I);
1274   SmallVector<Value *> Args;
1275   for (auto &Op : I.operands())
1276     Args.push_back(Op);
1277   for (auto &Op : I.indices())
1278     Args.push_back(B.getInt32(Op));
1279   auto *NewI =
1280       B.CreateIntrinsic(Intrinsic::spv_extractv, {I.getType()}, {Args});
1281   I.replaceAllUsesWith(NewI);
1282   I.eraseFromParent();
1283   return NewI;
1284 }
1285
1286 Instruction *SPIRVEmitIntrinsics::visitLoadInst(LoadInst &I) {
1287   if (!I.getType()->isAggregateType())
1288     return &I;
1289   IRBuilder<> B(I.getParent());
1290   B.SetInsertPoint(&I);
1291   TrackConstants = false;
1292   const auto *TLI = TM->getSubtargetImpl()->getTargetLowering();
1293   MachineMemOperand::Flags Flags =
1294       TLI->getLoadMemOperandFlags(I, F->getDataLayout());
1295   auto *NewI =
1296       B.CreateIntrinsic(Intrinsic::spv_load, {I.getOperand(0)->getType()},
1297                         {I.getPointerOperand(), B.getInt16(Flags),
1298                          B.getInt8(I.getAlign().value())});
1299   replaceMemInstrUses(&I, NewI, B);
1300   return NewI;
1301 }
1302
1303 Instruction *SPIRVEmitIntrinsics::visitStoreInst(StoreInst &I) {
1304   if (!AggrStores.contains(&I))
1305     return &I;
1306   IRBuilder<> B(I.getParent());
1307   B.SetInsertPoint(&I);
1308   TrackConstants = false;
1309   const auto *TLI = TM->getSubtargetImpl()->getTargetLowering();
1310   MachineMemOperand::Flags Flags =
1311       TLI->getStoreMemOperandFlags(I, F->getDataLayout());
1312   auto *PtrOp = I.getPointerOperand();
1313   auto *NewI = B.CreateIntrinsic(
1314       Intrinsic::spv_store, {I.getValueOperand()->getType(), PtrOp->getType()},
1315       {I.getValueOperand(), PtrOp, B.getInt16(Flags),
1316        B.getInt8(I.getAlign().value())});
1317   I.eraseFromParent();
1318   return NewI;
1319 }
1320
1321 Instruction *SPIRVEmitIntrinsics::visitAllocaInst(AllocaInst &I) {
1322   Value *ArraySize = nullptr;
1323   if (I.isArrayAllocation()) {
1324     const SPIRVSubtarget *STI = TM->getSubtargetImpl(*I.getFunction());
1325     if (!STI->canUseExtension(
1326             SPIRV::Extension::SPV_INTEL_variable_length_array))
1327       report_fatal_error(
1328           "array allocation: this instruction requires the following "
1329           "SPIR-V extension: SPV_INTEL_variable_length_array",
1330           false);
1331     ArraySize = I.getArraySize();
1332   }
1333   IRBuilder<> B(I.getParent());
1334   B.SetInsertPoint(&I);
1335   TrackConstants = false;
1336   Type *PtrTy = I.getType();
1337   auto *NewI =
1338       ArraySize ? B.CreateIntrinsic(Intrinsic::spv_alloca_array,
1339                                     {PtrTy, ArraySize->getType()}, {ArraySize})
1340                 : B.CreateIntrinsic(Intrinsic::spv_alloca, {PtrTy}, {});
1341   std::string InstName = I.hasName() ? I.getName().str() : "";
1342   I.replaceAllUsesWith(NewI);
1343   I.eraseFromParent();
1344   NewI->setName(InstName);
1345   return NewI;
1346 }
1347
1348 Instruction *SPIRVEmitIntrinsics::visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) {
1349   assert(I.getType()->isAggregateType() && "Aggregate result is expected");
1350   IRBuilder<> B(I.getParent());
1351   B.SetInsertPoint(&I);
1352   SmallVector<Value *> Args;
1353   for (auto &Op : I.operands())
1354     Args.push_back(Op);
1355   Args.push_back(B.getInt32(I.getSyncScopeID()));
1356   Args.push_back(B.getInt32(
1357       static_cast<uint32_t>(getMemSemantics(I.getSuccessOrdering()))));
1358   Args.push_back(B.getInt32(
1359       static_cast<uint32_t>(getMemSemantics(I.getFailureOrdering()))));
1360   auto *NewI = B.CreateIntrinsic(Intrinsic::spv_cmpxchg,
1361                                  {I.getPointerOperand()->getType()}, {Args});
1362   replaceMemInstrUses(&I, NewI, B);
1363   return NewI;
1364 }
1365
1366 Instruction *SPIRVEmitIntrinsics::visitUnreachableInst(UnreachableInst &I) {
1367   IRBuilder<> B(I.getParent());
1368   B.SetInsertPoint(&I);
1369   B.CreateIntrinsic(Intrinsic::spv_unreachable, {}, {});
1370   return &I;
1371 }
1372
1373 void SPIRVEmitIntrinsics::processGlobalValue(GlobalVariable &GV,
1374                                              IRBuilder<> &B) {
1375   // Skip special artifical variable llvm.global.annotations.
1376   if (GV.getName() == "llvm.global.annotations")
1377     return;
1378   if (GV.hasInitializer() && !isa<UndefValue>(GV.getInitializer())) {
1379     // Deduce element type and store results in Global Registry.
1380     // Result is ignored, because TypedPointerType is not supported
1381     // by llvm IR general logic.
1382     deduceElementTypeHelper(&GV, false);
1383     Constant *Init = GV.getInitializer();
1384     Type *Ty = isAggrConstForceInt32(Init) ? B.getInt32Ty() : Init->getType();
1385     Constant *Const = isAggrConstForceInt32(Init) ? B.getInt32(1) : Init;
1386     auto *InitInst = B.CreateIntrinsic(Intrinsic::spv_init_global,
1387                                        {GV.getType(), Ty}, {&GV, Const});
1388     InitInst->setArgOperand(1, Init);
1389   }
1390   if ((!GV.hasInitializer() || isa<UndefValue>(GV.getInitializer())) &&
1391       GV.getNumUses() == 0)
1392     B.CreateIntrinsic(Intrinsic::spv_unref_global, GV.getType(), &GV);
1393 }
1394
1395 // Return true, if we can't decide what is the pointee type now and will get
1396 // back to the question later. Return false is spv_assign_ptr_type is not needed
1397 // or can be inserted immediately.
1398 bool SPIRVEmitIntrinsics::insertAssignPtrTypeIntrs(Instruction *I,
1399                                                    IRBuilder<> &B,
1400                                                    bool UnknownElemTypeI8) {
1401   reportFatalOnTokenType(I);
1402   if (!isPointerTy(I->getType()) || !requireAssignType(I) ||
1403       isa<BitCastInst>(I))
1404     return false;
1405
1406   setInsertPointAfterDef(B, I);
1407   if (Type *ElemTy = deduceElementType(I, UnknownElemTypeI8)) {
1408     buildAssignPtr(B, ElemTy, I);
1409     return false;
1410   }
1411   return true;
1412 }
1413
1414 void SPIRVEmitIntrinsics::insertAssignTypeIntrs(Instruction *I,
1415                                                 IRBuilder<> &B) {
1416   // TODO: extend the list of functions with known result types
1417   static StringMap<unsigned> ResTypeWellKnown = {
1418       {"async_work_group_copy", WellKnownTypes::Event},
1419       {"async_work_group_strided_copy", WellKnownTypes::Event},
1420       {"__spirv_GroupAsyncCopy", WellKnownTypes::Event}};
1421
1422   reportFatalOnTokenType(I);
1423
1424   bool IsKnown = false;
1425   if (auto *CI = dyn_cast<CallInst>(I)) {
1426     if (!CI->isIndirectCall() && !CI->isInlineAsm() &&
1427         CI->getCalledFunction() && !CI->getCalledFunction()->isIntrinsic()) {
1428       Function *CalledF = CI->getCalledFunction();
1429       std::string DemangledName =
1430           getOclOrSpirvBuiltinDemangledName(CalledF->getName());
1431       if (DemangledName.length() > 0)
1432         DemangledName = SPIRV::lookupBuiltinNameHelper(DemangledName);
1433       auto ResIt = ResTypeWellKnown.find(DemangledName);
1434       if (ResIt != ResTypeWellKnown.end()) {
1435         IsKnown = true;
1436         setInsertPointAfterDef(B, I);
1437         switch (ResIt->second) {
1438         case WellKnownTypes::Event:
1439           buildAssignType(B, TargetExtType::get(I->getContext(), "spirv.Event"),
1440                           I);
1441           break;
1442         }
1443       }
1444     }
1445   }
1446
1447   Type *Ty = I->getType();
1448   if (!IsKnown && !Ty->isVoidTy() && !isPointerTy(Ty) && requireAssignType(I)) {
1449     setInsertPointAfterDef(B, I);
1450     Type *TypeToAssign = Ty;
1451     if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1452       if (II->getIntrinsicID() == Intrinsic::spv_const_composite ||
1453           II->getIntrinsicID() == Intrinsic::spv_undef) {
1454         auto It = AggrConstTypes.find(II);
1455         if (It == AggrConstTypes.end())
1456           report_fatal_error("Unknown composite intrinsic type");
1457         TypeToAssign = It->second;
1458       }
1459     }
1460     TypeToAssign = restoreMutatedType(GR, I, TypeToAssign);
1461     buildAssignType(B, TypeToAssign, I);
1462   }
1463   for (const auto &Op : I->operands()) {
1464     if (isa<ConstantPointerNull>(Op) || isa<UndefValue>(Op) ||
1465         // Check GetElementPtrConstantExpr case.
1466         (isa<ConstantExpr>(Op) && isa<GEPOperator>(Op))) {
1467       setInsertPointSkippingPhis(B, I);
1468       Type *OpTy = Op->getType();
1469       if (isa<UndefValue>(Op) && OpTy->isAggregateType()) {
1470         CallInst *AssignCI =
1471             buildIntrWithMD(Intrinsic::spv_assign_type, {B.getInt32Ty()}, Op,
1472                             UndefValue::get(B.getInt32Ty()), {}, B);
1473         GR->addAssignPtrTypeInstr(Op, AssignCI);
1474       } else if (!isa<Instruction>(Op)) {
1475         Type *OpTy = Op->getType();
1476         if (auto PType = dyn_cast<TypedPointerType>(OpTy)) {
1477           buildAssignPtr(B, PType->getElementType(), Op);
1478         } else if (isPointerTy(OpTy)) {
1479           Type *ElemTy = GR->findDeducedElementType(Op);
1480           buildAssignPtr(B, ElemTy ? ElemTy : deduceElementType(Op, true), Op);
1481         } else {
1482           CallInst *AssignCI = buildIntrWithMD(Intrinsic::spv_assign_type,
1483                                                {OpTy}, Op, Op, {}, B);
1484           GR->addAssignPtrTypeInstr(Op, AssignCI);
1485         }
1486       }
1487     }
1488   }
1489 }
1490
1491 void SPIRVEmitIntrinsics::insertSpirvDecorations(Instruction *I,
1492                                                  IRBuilder<> &B) {
1493   if (MDNode *MD = I->getMetadata("spirv.Decorations")) {
1494     setInsertPointAfterDef(B, I);
1495     B.CreateIntrinsic(Intrinsic::spv_assign_decoration, {I->getType()},
1496                       {I, MetadataAsValue::get(I->getContext(), MD)});
1497   }
1498 }
1499
1500 void SPIRVEmitIntrinsics::processInstrAfterVisit(Instruction *I,
1501                                                  IRBuilder<> &B) {
1502   auto *II = dyn_cast<IntrinsicInst>(I);
1503   if (II && II->getIntrinsicID() == Intrinsic::spv_const_composite &&
1504       TrackConstants) {
1505     setInsertPointAfterDef(B, I);
1506     auto t = AggrConsts.find(I);
1507     assert(t != AggrConsts.end());
1508     auto *NewOp =
1509         buildIntrWithMD(Intrinsic::spv_track_constant,
1510                         {II->getType(), II->getType()}, t->second, I, {}, B);
1511     I->replaceAllUsesWith(NewOp);
1512     NewOp->setArgOperand(0, I);
1513   }
1514   bool IsPhi = isa<PHINode>(I), BPrepared = false;
1515   for (const auto &Op : I->operands()) {
1516     if (isa<PHINode>(I) || isa<SwitchInst>(I))
1517       TrackConstants = false;
1518     if ((isa<ConstantData>(Op) || isa<ConstantExpr>(Op)) && TrackConstants) {
1519       unsigned OpNo = Op.getOperandNo();
1520       if (II && ((II->getIntrinsicID() == Intrinsic::spv_gep && OpNo == 0) ||
1521                  (II->paramHasAttr(OpNo, Attribute::ImmArg))))
1522         continue;
1523       if (!BPrepared) {
1524         IsPhi ? B.SetInsertPointPastAllocas(I->getParent()->getParent())
1525               : B.SetInsertPoint(I);
1526         BPrepared = true;
1527       }
1528       Value *OpTyVal = Op;
1529       if (Op->getType()->isTargetExtTy())
1530         OpTyVal = PoisonValue::get(Op->getType());
1531       auto *NewOp = buildIntrWithMD(Intrinsic::spv_track_constant,
1532                                     {Op->getType(), OpTyVal->getType()}, Op,
1533                                     OpTyVal, {}, B);
1534       I->setOperand(OpNo, NewOp);
1535     }
1536   }
1537   if (I->hasName()) {
1538     reportFatalOnTokenType(I);
1539     setInsertPointAfterDef(B, I);
1540     std::vector<Value *> Args = {I};
1541     addStringImm(I->getName(), B, Args);
1542     B.CreateIntrinsic(Intrinsic::spv_assign_name, {I->getType()}, Args);
1543   }
1544 }
1545
1546 Type *SPIRVEmitIntrinsics::deduceFunParamElementType(Function *F,
1547                                                      unsigned OpIdx) {
1548   std::unordered_set<Function *> FVisited;
1549   return deduceFunParamElementType(F, OpIdx, FVisited);
1550 }
1551
1552 Type *SPIRVEmitIntrinsics::deduceFunParamElementType(
1553     Function *F, unsigned OpIdx, std::unordered_set<Function *> &FVisited) {
1554   // maybe a cycle
1555   if (FVisited.find(F) != FVisited.end())
1556     return nullptr;
1557   FVisited.insert(F);
1558
1559   std::unordered_set<Value *> Visited;
1560   SmallVector<std::pair<Function *, unsigned>> Lookup;
1561   // search in function's call sites
1562   for (User *U : F->users()) {
1563     CallInst *CI = dyn_cast<CallInst>(U);
1564     if (!CI || OpIdx >= CI->arg_size())
1565       continue;
1566     Value *OpArg = CI->getArgOperand(OpIdx);
1567     if (!isPointerTy(OpArg->getType()))
1568       continue;
1569     // maybe we already know operand's element type
1570     if (Type *KnownTy = GR->findDeducedElementType(OpArg))
1571       return KnownTy;
1572     // try to deduce from the operand itself
1573     Visited.clear();
1574     if (Type *Ty = deduceElementTypeHelper(OpArg, Visited, false))
1575       return Ty;
1576     // search in actual parameter's users
1577     for (User *OpU : OpArg->users()) {
1578       Instruction *Inst = dyn_cast<Instruction>(OpU);
1579       if (!Inst || Inst == CI)
1580         continue;
1581       Visited.clear();
1582       if (Type *Ty = deduceElementTypeHelper(Inst, Visited, false))
1583         return Ty;
1584     }
1585     // check if it's a formal parameter of the outer function
1586     if (!CI->getParent() || !CI->getParent()->getParent())
1587       continue;
1588     Function *OuterF = CI->getParent()->getParent();
1589     if (FVisited.find(OuterF) != FVisited.end())
1590       continue;
1591     for (unsigned i = 0; i < OuterF->arg_size(); ++i) {
1592       if (OuterF->getArg(i) == OpArg) {
1593         Lookup.push_back(std::make_pair(OuterF, i));
1594         break;
1595       }
1596     }
1597   }
1598
1599   // search in function parameters
1600   for (auto &Pair : Lookup) {
1601     if (Type *Ty = deduceFunParamElementType(Pair.first, Pair.second, FVisited))
1602       return Ty;
1603   }
1604
1605   return nullptr;
1606 }
1607
1608 void SPIRVEmitIntrinsics::processParamTypesByFunHeader(Function *F,
1609                                                        IRBuilder<> &B) {
1610   B.SetInsertPointPastAllocas(F);
1611   for (unsigned OpIdx = 0; OpIdx < F->arg_size(); ++OpIdx) {
1612     Argument *Arg = F->getArg(OpIdx);
1613     if (!isUntypedPointerTy(Arg->getType()))
1614       continue;
1615     Type *ElemTy = GR->findDeducedElementType(Arg);
1616     if (!ElemTy && hasPointeeTypeAttr(Arg) &&
1617         (ElemTy = getPointeeTypeByAttr(Arg)) != nullptr)
1618       buildAssignPtr(B, ElemTy, Arg);
1619   }
1620 }
1621
1622 void SPIRVEmitIntrinsics::processParamTypes(Function *F, IRBuilder<> &B) {
1623   B.SetInsertPointPastAllocas(F);
1624   for (unsigned OpIdx = 0; OpIdx < F->arg_size(); ++OpIdx) {
1625     Argument *Arg = F->getArg(OpIdx);
1626     if (!isUntypedPointerTy(Arg->getType()))
1627       continue;
1628     Type *ElemTy = GR->findDeducedElementType(Arg);
1629     if (!ElemTy && (ElemTy = deduceFunParamElementType(F, OpIdx)) != nullptr)
1630       buildAssignPtr(B, ElemTy, Arg);
1631   }
1632 }
1633
1634 bool SPIRVEmitIntrinsics::runOnFunction(Function &Func) {
1635   if (Func.isDeclaration())
1636     return false;
1637
1638   const SPIRVSubtarget &ST = TM->getSubtarget<SPIRVSubtarget>(Func);
1639   GR = ST.getSPIRVGlobalRegistry();
1640   InstrSet = ST.isOpenCLEnv() ? SPIRV::InstructionSet::OpenCL_std
1641                               : SPIRV::InstructionSet::GLSL_std_450;
1642
1643   F = &Func;
1644   IRBuilder<> B(Func.getContext());
1645   AggrConsts.clear();
1646   AggrConstTypes.clear();
1647   AggrStores.clear();
1648
1649   processParamTypesByFunHeader(F, B);
1650
1651   // StoreInst's operand type can be changed during the next transformations,
1652   // so we need to store it in the set. Also store already transformed types.
1653   for (auto &I : instructions(Func)) {
1654     StoreInst *SI = dyn_cast<StoreInst>(&I);
1655     if (!SI)
1656       continue;
1657     Type *ElTy = SI->getValueOperand()->getType();
1658     if (ElTy->isAggregateType() || ElTy->isVectorTy())
1659       AggrStores.insert(&I);
1660   }
1661
1662   B.SetInsertPoint(&Func.getEntryBlock(), Func.getEntryBlock().begin());
1663   for (auto &GV : Func.getParent()->globals())
1664     processGlobalValue(GV, B);
1665
1666   preprocessUndefs(B);
1667   preprocessCompositeConstants(B);
1668   SmallVector<Instruction *> Worklist;
1669   for (auto &I : instructions(Func))
1670     Worklist.push_back(&I);
1671
1672   for (auto &I : Worklist) {
1673     // Don't emit intrinsincs for convergence intrinsics.
1674     if (isConvergenceIntrinsic(I))
1675       continue;
1676
1677     bool Postpone = insertAssignPtrTypeIntrs(I, B, false);
1678     // if Postpone is true, we can't decide on pointee type yet
1679     insertAssignTypeIntrs(I, B);
1680     insertPtrCastOrAssignTypeInstr(I, B);
1681     insertSpirvDecorations(I, B);
1682     // if instruction requires a pointee type set, let's check if we know it
1683     // already, and force it to be i8 if not
1684     if (Postpone && !GR->findAssignPtrTypeInstr(I))
1685       insertAssignPtrTypeIntrs(I, B, true);
1686   }
1687
1688   for (auto &I : instructions(Func))
1689     deduceOperandElementType(&I);
1690
1691   for (auto *I : Worklist) {
1692     TrackConstants = true;
1693     if (!I->getType()->isVoidTy() || isa<StoreInst>(I))
1694       setInsertPointAfterDef(B, I);
1695     // Visitors return either the original/newly created instruction for further
1696     // processing, nullptr otherwise.
1697     I = visit(*I);
1698     if (!I)
1699       continue;
1700
1701     // Don't emit intrinsics for convergence operations.
1702     if (isConvergenceIntrinsic(I))
1703       continue;
1704
1705     processInstrAfterVisit(I, B);
1706   }
1707
1708   return true;
1709 }
1710
1711 // Try to deduce a better type for pointers to untyped ptr.
1712 bool SPIRVEmitIntrinsics::postprocessTypes() {
1713   bool Changed = false;
1714   if (!GR)
1715     return Changed;
1716   for (auto IB = PostprocessWorklist.rbegin(), IE = PostprocessWorklist.rend();
1717        IB != IE; ++IB) {
1718     CallInst *AssignCI = GR->findAssignPtrTypeInstr(*IB);
1719     Type *KnownTy = GR->findDeducedElementType(*IB);
1720     if (!KnownTy || !AssignCI || !isa<Instruction>(AssignCI->getArgOperand(0)))
1721       continue;
1722     Instruction *I = cast<Instruction>(AssignCI->getArgOperand(0));
1723     for (User *U : I->users()) {
1724       Instruction *Inst = dyn_cast<Instruction>(U);
1725       if (!Inst || isa<IntrinsicInst>(Inst))
1726         continue;
1727       deduceOperandElementType(Inst, I, KnownTy, AssignCI);
1728       if (KnownTy != GR->findDeducedElementType(I)) {
1729         Changed = true;
1730         break;
1731       }
1732     }
1733   }
1734   return Changed;
1735 }
1736
1737 bool SPIRVEmitIntrinsics::runOnModule(Module &M) {
1738   bool Changed = false;
1739
1740   UncompleteTypeInfo.clear();
1741   PostprocessWorklist.clear();
1742   for (auto &F : M)
1743     Changed |= runOnFunction(F);
1744
1745   for (auto &F : M) {
1746     // check if function parameter types are set
1747     if (!F.isDeclaration() && !F.isIntrinsic()) {
1748       const SPIRVSubtarget &ST = TM->getSubtarget<SPIRVSubtarget>(F);
1749       GR = ST.getSPIRVGlobalRegistry();
1750       IRBuilder<> B(F.getContext());
1751       processParamTypes(&F, B);
1752     }
1753   }
1754
1755   Changed |= postprocessTypes();
1756
1757   return Changed;
1758 }
1759
1760 ModulePass *llvm::createSPIRVEmitIntrinsicsPass(SPIRVTargetMachine *TM) {
1761   return new SPIRVEmitIntrinsics(TM);
1762 }