SPIRVEmitIntrinsics.cpp

Go to the documentation of this file.

//===-- SPIRVEmitIntrinsics.cpp - emit SPIRV intrinsics ---------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The pass emits SPIRV intrinsics keeping essential high-level information for
// the translation of LLVM IR to SPIR-V.
//
//===----------------------------------------------------------------------===//
 
#include "SPIRVEmitIntrinsics.h"
#include "SPIRV.h"
#include "SPIRVBuiltins.h"
#include "SPIRVSubtarget.h"
#include "SPIRVTargetMachine.h"
#include "SPIRVUtils.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/IntrinsicsSPIRV.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/TypedPointerType.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/Local.h"
 
#include <cassert>
#include <optional>
#include <queue>
 
// This pass performs the following transformation on LLVM IR level required
// for the following translation to SPIR-V:
// - replaces direct usages of aggregate constants with target-specific
//   intrinsics;
// - replaces aggregates-related instructions (extract/insert, ld/st, etc)
//   with a target-specific intrinsics;
// - emits intrinsics for the global variable initializers since IRTranslator
//   doesn't handle them and it's not very convenient to translate them
//   ourselves;
// - emits intrinsics to keep track of the string names assigned to the values;
// - emits intrinsics to keep track of constants (this is necessary to have an
//   LLVM IR constant after the IRTranslation is completed) for their further
//   deduplication;
// - emits intrinsics to keep track of original LLVM types of the values
//   to be able to emit proper SPIR-V types eventually.
//
// TODO: consider removing spv.track.constant in favor of spv.assign.type.
 
using namespace llvm;
using namespace llvm::PatternMatch;
 
#define DEBUG_TYPE "spirv-emit-intrinsics"
 
static cl::opt<bool>
    SpirvEmitOpNames("spirv-emit-op-names",
                     cl::desc("Emit OpName for all instructions"),
                     cl::init(false));
 
namespace llvm::SPIRV {
#define GET_BuiltinGroup_DECL
#include "SPIRVGenTables.inc"
} // namespace llvm::SPIRV
 
namespace {
// This class keeps track of which functions reference which global variables.
class GlobalVariableUsers {
  template <typename T1, typename T2>
  using OneToManyMapTy = DenseMap<T1, SmallPtrSet<T2, 4>>;
 
  OneToManyMapTy<const GlobalVariable *, const Function *> GlobalIsUsedByFun;
 
  void collectGlobalUsers(
      const GlobalVariable *GV,
      OneToManyMapTy<const GlobalVariable *, const GlobalVariable *>
          &GlobalIsUsedByGlobal) {
    SmallVector<const Value *> Stack = {GV->user_begin(), GV->user_end()};
    while (!Stack.empty()) {
      const Value *V = Stack.pop_back_val();
 
      if (const Instruction *I = dyn_cast<Instruction>(V)) {
        GlobalIsUsedByFun[GV].insert(I->getFunction());
        continue;
      }
 
      if (const GlobalVariable *UserGV = dyn_cast<GlobalVariable>(V)) {
        GlobalIsUsedByGlobal[GV].insert(UserGV);
        continue;
      }
 
      if (const Constant *C = dyn_cast<Constant>(V))
        Stack.append(C->user_begin(), C->user_end());
    }
  }
 
  bool propagateGlobalToGlobalUsers(
      OneToManyMapTy<const GlobalVariable *, const GlobalVariable *>
          &GlobalIsUsedByGlobal) {
    SmallVector<const GlobalVariable *> OldUsersGlobals;
    bool Changed = false;
    for (auto &[GV, UserGlobals] : GlobalIsUsedByGlobal) {
      OldUsersGlobals.assign(UserGlobals.begin(), UserGlobals.end());
      for (const GlobalVariable *UserGV : OldUsersGlobals) {
        auto It = GlobalIsUsedByGlobal.find(UserGV);
        if (It == GlobalIsUsedByGlobal.end())
          continue;
        Changed |= set_union(UserGlobals, It->second);
      }
    }
    return Changed;
  }
 
  void propagateGlobalToFunctionReferences(
      OneToManyMapTy<const GlobalVariable *, const GlobalVariable *>
          &GlobalIsUsedByGlobal) {
    for (auto &[GV, UserGlobals] : GlobalIsUsedByGlobal) {
      auto &UserFunctions = GlobalIsUsedByFun[GV];
      for (const GlobalVariable *UserGV : UserGlobals) {
        auto It = GlobalIsUsedByFun.find(UserGV);
        if (It == GlobalIsUsedByFun.end())
          continue;
        set_union(UserFunctions, It->second);
      }
    }
  }
 
public:
  void init(Module &M) {
    // Collect which global variables are referenced by which global variables
    // and which functions reference each global variables.
    OneToManyMapTy<const GlobalVariable *, const GlobalVariable *>
        GlobalIsUsedByGlobal;
    GlobalIsUsedByFun.clear();
    for (GlobalVariable &GV : M.globals())
      collectGlobalUsers(&GV, GlobalIsUsedByGlobal);
 
    // Compute indirect references by iterating until a fixed point is reached.
    while (propagateGlobalToGlobalUsers(GlobalIsUsedByGlobal))
      (void)0;
 
    propagateGlobalToFunctionReferences(GlobalIsUsedByGlobal);
  }
 
  using FunctionSetType = typename decltype(GlobalIsUsedByFun)::mapped_type;
  const FunctionSetType &
  getTransitiveUserFunctions(const GlobalVariable &GV) const {
    auto It = GlobalIsUsedByFun.find(&GV);
    if (It != GlobalIsUsedByFun.end())
      return It->second;
 
    static const FunctionSetType Empty{};
    return Empty;
  }
};
 
static bool isaGEP(const Value *V) {
  return isa<StructuredGEPInst>(V) || isa<GetElementPtrInst>(V);
}
 
// If Ty is a byte-addressing type, return the multiplier for the offset.
// Otherwise return std::nullopt.
static std::optional<uint64_t> getByteAddressingMultiplier(Type *Ty) {
  if (Ty == IntegerType::getInt8Ty(Ty->getContext())) {
    return 1;
  }
  if (auto *AT = dyn_cast<ArrayType>(Ty)) {
    if (AT->getElementType() == IntegerType::getInt8Ty(Ty->getContext())) {
      return AT->getNumElements();
    }
  }
  return std::nullopt;
}
 
class SPIRVEmitIntrinsicsImpl
    : public InstVisitor<SPIRVEmitIntrinsicsImpl, Instruction *> {
  const SPIRVTargetMachine &TM;
  SPIRVGlobalRegistry *GR = nullptr;
  Function *CurrF = nullptr;
  bool TrackConstants = true;
  bool HaveFunPtrs = false;
  DenseMap<Instruction *, Constant *> AggrConsts;
  DenseMap<Instruction *, Type *> AggrConstTypes;
  SmallPtrSet<Instruction *, 0> AggrStores;
  GlobalVariableUsers GVUsers;
  SmallPtrSet<Value *, 0> Named;
 
  // map of function declarations to <pointer arg index => element type>
  DenseMap<Function *, SmallVector<std::pair<unsigned, Type *>>> FDeclPtrTys;
 
  // a register of Instructions that don't have a complete type definition
  bool CanTodoType = true;
  unsigned TodoTypeSz = 0;
  DenseMap<Value *, bool> TodoType;
  void insertTodoType(Value *Op) {
    // TODO: add isa<CallInst>(Op) to no-insert
    if (CanTodoType && !isaGEP(Op)) {
      auto It = TodoType.try_emplace(Op, true);
      if (It.second)
        ++TodoTypeSz;
    }
  }
  void eraseTodoType(Value *Op) {
    auto It = TodoType.find(Op);
    if (It != TodoType.end() && It->second) {
      It->second = false;
      --TodoTypeSz;
    }
  }
  bool isTodoType(Value *Op) {
    if (isaGEP(Op))
      return false;
    auto It = TodoType.find(Op);
    return It != TodoType.end() && It->second;
  }
  // a register of Instructions that were visited by deduceOperandElementType()
  // to validate operand types with an instruction
  SmallPtrSet<Instruction *, 0> TypeValidated;
 
  // well known result types of builtins
  enum WellKnownTypes { Event };
 
  // deduce element type of untyped pointers
  Type *deduceElementType(Value *I, bool UnknownElemTypeI8);
  Type *deduceElementTypeHelper(Value *I, bool UnknownElemTypeI8);
  Type *deduceElementTypeHelper(Value *I, SmallPtrSetImpl<Value *> &Visited,
                                bool UnknownElemTypeI8,
                                bool IgnoreKnownType = false);
  Type *deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,
                                     bool UnknownElemTypeI8);
  Type *deduceElementTypeByValueDeep(Type *ValueTy, Value *Operand,
                                     SmallPtrSetImpl<Value *> &Visited,
                                     bool UnknownElemTypeI8);
  Type *deduceElementTypeByUsersDeep(Value *Op,
                                     SmallPtrSetImpl<Value *> &Visited,
                                     bool UnknownElemTypeI8);
  void maybeAssignPtrType(Type *&Ty, Value *I, Type *RefTy,
                          bool UnknownElemTypeI8);
 
  // deduce nested types of composites
  Type *deduceNestedTypeHelper(User *U, bool UnknownElemTypeI8);
  Type *deduceNestedTypeHelper(User *U, Type *Ty,
                               SmallPtrSetImpl<Value *> &Visited,
                               bool UnknownElemTypeI8);
 
  // deduce Types of operands of the Instruction if possible
  void
  deduceOperandElementType(Instruction *I,
                           SmallPtrSetImpl<Instruction *> *IncompleteRets,
                           const SmallPtrSetImpl<Value *> *AskOps = nullptr,
                           bool IsPostprocessing = false);
 
  void preprocessCompositeConstants(IRBuilder<> &B);
  Value *lowerUndefOrPoison(Value *Op, IRBuilder<> &B, bool HasPoisonExt);
  void preprocessUndefsAndPoisons(IRBuilder<> &B);
  void insertCompositeAggregateArms(Instruction *I, IRBuilder<> &B);
  void simplifyNullAddrSpaceCasts();
 
  Type *reconstructType(Value *Op, bool UnknownElemTypeI8,
                        bool IsPostprocessing);
 
  void replaceMemInstrUses(Instruction *Old, Instruction *New, IRBuilder<> &B);
  void processInstrAfterVisit(Instruction *I, IRBuilder<> &B);
  bool insertAssignPtrTypeIntrs(Instruction *I, IRBuilder<> &B,
                                bool UnknownElemTypeI8);
  void insertAssignTypeIntrs(Instruction *I, IRBuilder<> &B);
  void insertAssignPtrTypeTargetExt(TargetExtType *AssignedType, Value *V,
                                    IRBuilder<> &B);
  void replacePointerOperandWithPtrCast(Instruction *I, Value *Pointer,
                                        Type *ExpectedElementType,
                                        unsigned OperandToReplace,
                                        IRBuilder<> &B);
  void insertPtrCastOrAssignTypeInstr(Instruction *I, IRBuilder<> &B);
  bool shouldTryToAddMemAliasingDecoration(Instruction *Inst);
  void insertSpirvDecorations(Instruction *I, IRBuilder<> &B);
  void insertConstantsForFPFastMathDefault(Module &M);
  Value *buildSpvUndefComposite(Type *AggrTy, IRBuilder<> &B);
  void reconstructAggregateReturns(Function &Func, IRBuilder<> &B);
  void processGlobalValue(GlobalVariable &GV, IRBuilder<> &B);
  void processParamTypes(Function *F, IRBuilder<> &B);
  void processParamTypesByFunHeader(Function *F, IRBuilder<> &B);
  Type *deduceFunParamElementType(Function *F, unsigned OpIdx);
  Type *deduceFunParamElementType(Function *F, unsigned OpIdx,
                                  SmallPtrSetImpl<Function *> &FVisited);
 
  bool deduceOperandElementTypeCalledFunction(
      CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,
      Type *&KnownElemTy, bool &Incomplete);
  void deduceOperandElementTypeFunctionPointer(
      CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,
      Type *&KnownElemTy, bool IsPostprocessing);
  bool deduceOperandElementTypeFunctionRet(
      Instruction *I, SmallPtrSetImpl<Instruction *> *IncompleteRets,
      const SmallPtrSetImpl<Value *> *AskOps, bool IsPostprocessing,
      Type *&KnownElemTy, Value *Op, Function *F);
 
  CallInst *buildSpvPtrcast(Function *F, Value *Op, Type *ElemTy);
  void replaceUsesOfWithSpvPtrcast(Value *Op, Type *ElemTy, Instruction *I,
                                   DenseMap<Function *, CallInst *> Ptrcasts);
  void propagateElemType(Value *Op, Type *ElemTy,
                         DenseSet<std::pair<Value *, Value *>> &VisitedSubst);
  void
  propagateElemTypeRec(Value *Op, Type *PtrElemTy, Type *CastElemTy,
                       DenseSet<std::pair<Value *, Value *>> &VisitedSubst);
  void propagateElemTypeRec(Value *Op, Type *PtrElemTy, Type *CastElemTy,
                            DenseSet<std::pair<Value *, Value *>> &VisitedSubst,
                            SmallPtrSetImpl<Value *> &Visited,
                            DenseMap<Function *, CallInst *> Ptrcasts);
 
  void replaceAllUsesWith(Value *Src, Value *Dest, bool DeleteOld = true);
  void replaceAllUsesWithAndErase(IRBuilder<> &B, Instruction *Src,
                                  Instruction *Dest, bool DeleteOld = true);
 
  void applyDemangledPtrArgTypes(IRBuilder<> &B);
 
  GetElementPtrInst *simplifyZeroLengthArrayGepInst(GetElementPtrInst *GEP);
 
  bool runOnFunction(Function &F);
  bool postprocessTypes(Module &M);
  bool processFunctionPointers(Module &M);
  void parseFunDeclarations(Module &M);
  void useRoundingMode(ConstrainedFPIntrinsic *FPI, IRBuilder<> &B);
  bool processMaskedMemIntrinsic(IntrinsicInst &I);
  bool convertMaskedMemIntrinsics(Module &M);
  void preprocessBoolVectorBitcasts(Function &F);
 
  void emitUnstructuredLoopControls(Function &F, IRBuilder<> &B);
 
  // Tries to walk the type accessed by the given GEP instruction.
  // For each nested type access, one of the 2 callbacks is called:
  //  - OnLiteralIndexing when the index is a known constant value.
  //    Parameters:
  //      PointedType: the pointed type resulting of this indexing.
  //        If the parent type is an array, this is the index in the array.
  //        If the parent type is a struct, this is the field index.
  //      Index: index of the element in the parent type.
  //  - OnDynamnicIndexing when the index is a non-constant value.
  //    This callback is only called when indexing into an array.
  //    Parameters:
  //      ElementType: the type of the elements stored in the parent array.
  //      Offset: the Value* containing the byte offset into the array.
  //      Multiplier: a scaling factor for the offset.
  // Return true if an error occurred during the walk, false otherwise.
  bool walkLogicalAccessChain(
      GetElementPtrInst &GEP,
      const std::function<void(Type *PointedType, uint64_t Index)>
          &OnLiteralIndexing,
      const std::function<void(Type *ElementType, Value *Offset,
                               uint64_t Multiplier)> &OnDynamicIndexing);
 
  bool walkLogicalAccessChainDynamic(
      Type *CurType, Value *Operand, uint64_t Multiplier,
      const std::function<void(Type *, uint64_t)> &OnLiteralIndexing,
      const std::function<void(Type *, Value *, uint64_t)> &OnDynamicIndexing);
 
  bool walkLogicalAccessChainConstant(
      Type *CurType, uint64_t Offset,
      const std::function<void(Type *, uint64_t)> &OnLiteralIndexing);
 
  // Returns the type accessed using the given GEP instruction by relying
  // on the GEP type.
  // FIXME: GEP types are not supposed to be used to retrieve the pointed
  // type. This must be fixed.
  Type *getGEPType(GetElementPtrInst *GEP);
 
  // Returns the type accessed using the given GEP instruction by walking
  // the source type using the GEP indices.
  // FIXME: without help from the frontend, this method cannot reliably retrieve
  // the stored type, nor can robustly determine the depth of the type
  // we are accessing.
  Type *getGEPTypeLogical(GetElementPtrInst *GEP);
 
  Instruction *buildLogicalAccessChainFromGEP(GetElementPtrInst &GEP);
 
public:
  SPIRVEmitIntrinsicsImpl(const SPIRVTargetMachine &TM) : TM(TM) {}
  Instruction *visitInstruction(Instruction &I) { return &I; }
  Instruction *visitSwitchInst(SwitchInst &I);
  Instruction *visitGetElementPtrInst(GetElementPtrInst &I);
  Instruction *visitIntrinsicInst(IntrinsicInst &I);
  Instruction *visitBitCastInst(BitCastInst &I);
  Instruction *visitInsertElementInst(InsertElementInst &I);
  Instruction *visitExtractElementInst(ExtractElementInst &I);
  Instruction *visitInsertValueInst(InsertValueInst &I);
  Instruction *visitExtractValueInst(ExtractValueInst &I);
  Instruction *visitLoadInst(LoadInst &I);
  Instruction *visitStoreInst(StoreInst &I);
  Instruction *visitAllocaInst(AllocaInst &I);
  Instruction *visitAtomicCmpXchgInst(AtomicCmpXchgInst &I);
  Instruction *visitUnreachableInst(UnreachableInst &I);
  Instruction *visitCallInst(CallInst &I);
 
  bool runOnModule(Module &M);
};
 
class SPIRVEmitIntrinsicsLegacy : public ModulePass {
  const SPIRVTargetMachine &TM;
 
public:
  static char ID;
  SPIRVEmitIntrinsicsLegacy(const SPIRVTargetMachine &TM)
      : ModulePass(ID), TM(TM) {}
 
  StringRef getPassName() const override { return "SPIRV emit intrinsics"; }
 
  bool runOnModule(Module &M) override {
    return SPIRVEmitIntrinsicsImpl(TM).runOnModule(M);
  }
};
 
bool isConvergenceIntrinsic(const Instruction *I) {
  return match(I, m_AnyIntrinsic<Intrinsic::experimental_convergence_entry,
                                 Intrinsic::experimental_convergence_loop,
                                 Intrinsic::experimental_convergence_anchor>());
}
 
bool expectIgnoredInIRTranslation(const Instruction *I) {
  return match(I, m_AnyIntrinsic<Intrinsic::invariant_start,
                                 Intrinsic::spv_resource_handlefrombinding,
                                 Intrinsic::spv_resource_getbasepointer,
                                 Intrinsic::spv_resource_getpointer>());
}
 
// Returns the source pointer from `I` ignoring intermediate ptrcast.
Value *getPointerRoot(Value *I) {
  Value *V;
  if (match(I, m_Intrinsic<Intrinsic::spv_ptrcast>(m_Value(V))))
    return getPointerRoot(V);
  return I;
}
 
} // namespace
 
char SPIRVEmitIntrinsicsLegacy::ID = 0;
 
INITIALIZE_PASS(SPIRVEmitIntrinsicsLegacy, "spirv-emit-intrinsics",
                "SPIRV emit intrinsics", false, false)
 
static inline bool isAssignTypeInstr(const Instruction *I) {
  return match(I, m_Intrinsic<Intrinsic::spv_assign_type>());
}
 
static bool isMemInstrToReplace(Instruction *I) {
  return isa<StoreInst>(I) || isa<LoadInst>(I) || isa<InsertValueInst>(I) ||
         isa<ExtractValueInst>(I) || isa<AtomicCmpXchgInst>(I);
}
 
static bool isAggrConstForceInt32(const Value *V) {
  bool IsAggrZero =
      isa<ConstantAggregateZero>(V) && !V->getType()->isVectorTy();
  bool IsUndefAggregate = isa<UndefValue>(V) && V->getType()->isAggregateType();
  return isa<ConstantArray>(V) || isa<ConstantStruct>(V) ||
         isa<ConstantDataArray>(V) || IsAggrZero || IsUndefAggregate;
}
 
static bool isSpvAggrPlaceholder(const Value *V) {
  return match(
      V,
      m_AnyIntrinsic<Intrinsic::spv_undef, Intrinsic::spv_const_composite>());
}
 
static void setInsertPointSkippingPhis(IRBuilder<> &B, Instruction *I) {
  if (isa<PHINode>(I))
    B.SetInsertPoint(I->getParent()->getFirstNonPHIOrDbgOrAlloca());
  else
    B.SetInsertPoint(I);
}
 
static void setInsertPointAfterDef(IRBuilder<> &B, Instruction *I) {
  B.SetCurrentDebugLocation(I->getDebugLoc());
  if (I->getType()->isVoidTy())
    B.SetInsertPoint(I->getNextNode());
  else
    B.SetInsertPoint(*I->getInsertionPointAfterDef());
}
 
static bool requireAssignType(Instruction *I) {
  return !match(
      I,
      m_AnyIntrinsic<Intrinsic::invariant_start, Intrinsic::invariant_end>());
}
 
static inline void reportFatalOnTokenType(const Instruction *I) {
  if (I->getType()->isTokenTy())
    report_fatal_error("A token is encountered but SPIR-V without extensions "
                       "does not support token type",
                       false);
}
 
static void emitAssignName(Instruction *I, IRBuilder<> &B) {
  if (!I->hasName() || I->getType()->isAggregateType() ||
      expectIgnoredInIRTranslation(I))
    return;
 
  // We want to be conservative when adding the names because they can interfere
  // with later optimizations.
  bool KeepName = SpirvEmitOpNames;
  if (!KeepName) {
    if (isa<AllocaInst>(I)) {
      KeepName = true;
    } else if (auto *CI = dyn_cast<CallBase>(I)) {
      Function *F = CI->getCalledFunction();
      if (F && F->getName().starts_with("llvm.spv.alloca"))
        KeepName = true;
    }
  }
 
  if (!KeepName)
    return;
 
  reportFatalOnTokenType(I);
  setInsertPointAfterDef(B, I);
  LLVMContext &Ctx = I->getContext();
  std::vector<Value *> Args = {
      I, MetadataAsValue::get(
             Ctx, MDNode::get(Ctx, MDString::get(Ctx, I->getName())))};
  B.CreateIntrinsic(Intrinsic::spv_assign_name, {I->getType()}, Args);
}
 
void SPIRVEmitIntrinsicsImpl::replaceAllUsesWith(Value *Src, Value *Dest,
                                                 bool DeleteOld) {
  GR->replaceAllUsesWith(Src, Dest, DeleteOld);
  // Update uncomplete type records if any
  if (isTodoType(Src)) {
    if (DeleteOld)
      eraseTodoType(Src);
    insertTodoType(Dest);
  }
}
 
void SPIRVEmitIntrinsicsImpl::replaceAllUsesWithAndErase(IRBuilder<> &B,
                                                         Instruction *Src,
                                                         Instruction *Dest,
                                                         bool DeleteOld) {
  replaceAllUsesWith(Src, Dest, DeleteOld);
  std::string Name = Src->hasName() ? Src->getName().str() : "";
  Src->eraseFromParent();
  if (!Name.empty()) {
    Dest->setName(Name);
    if (Named.insert(Dest).second)
      emitAssignName(Dest, B);
  }
}
 
static bool IsKernelArgInt8(Function *F, StoreInst *SI) {
  return SI && F->getCallingConv() == CallingConv::SPIR_KERNEL &&
         isPointerTy(SI->getValueOperand()->getType()) &&
         isa<Argument>(SI->getValueOperand());
}
 
// A pointer-typed local holds a pointer, so its deduced pointee must stay a
// pointer.
static bool tracesToPointerAlloca(Value *V) {
  using namespace PatternMatch;
  V = V->stripPointerCasts();
  if (auto *AI = dyn_cast<AllocaInst>(V))
    return isUntypedPointerTy(AI->getAllocatedType());
  return match(
      V, m_AnyIntrinsic<Intrinsic::spv_alloca, Intrinsic::spv_alloca_array>());
}
 
// Maybe restore original function return type.
static inline Type *restoreMutatedType(SPIRVGlobalRegistry *GR, Instruction *I,
                                       Type *Ty) {
  CallInst *CI = dyn_cast<CallInst>(I);
  if (!CI || CI->isIndirectCall() || CI->isInlineAsm() ||
      !CI->getCalledFunction() || CI->getCalledFunction()->isIntrinsic())
    return Ty;
  if (Type *OriginalTy = GR->findMutated(CI->getCalledFunction()))
    return OriginalTy;
  return Ty;
}
 
// Reconstruct type with nested element types according to deduced type info.
// Return nullptr if no detailed type info is available.
Type *SPIRVEmitIntrinsicsImpl::reconstructType(Value *Op,
                                               bool UnknownElemTypeI8,
                                               bool IsPostprocessing) {
  Type *Ty = Op->getType();
  if (auto *OpI = dyn_cast<Instruction>(Op)) {
    Ty = restoreMutatedType(GR, OpI, Ty);
    if (auto It = AggrConstTypes.find(OpI); It != AggrConstTypes.end())
      Ty = It->second;
  }
  if (!isUntypedPointerTy(Ty))
    return Ty;
  // try to find the pointee type
  if (Type *NestedTy = GR->findDeducedElementType(Op))
    return getTypedPointerWrapper(NestedTy, getPointerAddressSpace(Ty));
  // not a pointer according to the type info (e.g., Event object)
  CallInst *CI = GR->findAssignPtrTypeInstr(Op);
  if (CI) {
    MetadataAsValue *MD = cast<MetadataAsValue>(CI->getArgOperand(1));
    return cast<ConstantAsMetadata>(MD->getMetadata())->getType();
  }
  if (UnknownElemTypeI8) {
    if (!IsPostprocessing)
      insertTodoType(Op);
    return getTypedPointerWrapper(IntegerType::getInt8Ty(Op->getContext()),
                                  getPointerAddressSpace(Ty));
  }
  return nullptr;
}
 
CallInst *SPIRVEmitIntrinsicsImpl::buildSpvPtrcast(Function *F, Value *Op,
                                                   Type *ElemTy) {
  IRBuilder<> B(Op->getContext());
  if (auto *OpI = dyn_cast<Instruction>(Op)) {
    // spv_ptrcast's argument Op denotes an instruction that generates
    // a value, and we may use getInsertionPointAfterDef()
    setInsertPointAfterDef(B, OpI);
  } else if (auto *OpA = dyn_cast<Argument>(Op)) {
    B.SetInsertPointPastAllocas(OpA->getParent());
    B.SetCurrentDebugLocation(DebugLoc());
  } else {
    B.SetInsertPoint(F->getEntryBlock().getFirstNonPHIOrDbgOrAlloca());
  }
  Type *OpTy = Op->getType();
  SmallVector<Type *, 2> Types = {OpTy, OpTy};
  SmallVector<Value *, 2> Args = {Op, buildMD(getNormalizedPoisonValue(ElemTy)),
                                  B.getInt32(getPointerAddressSpace(OpTy))};
  CallInst *PtrCasted =
      B.CreateIntrinsicWithoutFolding(Intrinsic::spv_ptrcast, {Types}, Args);
  GR->buildAssignPtr(B, ElemTy, PtrCasted);
  return PtrCasted;
}
 
void SPIRVEmitIntrinsicsImpl::replaceUsesOfWithSpvPtrcast(
    Value *Op, Type *ElemTy, Instruction *I,
    DenseMap<Function *, CallInst *> Ptrcasts) {
  Function *F = I->getParent()->getParent();
  CallInst *PtrCastedI = nullptr;
  auto It = Ptrcasts.find(F);
  if (It == Ptrcasts.end()) {
    PtrCastedI = buildSpvPtrcast(F, Op, ElemTy);
    Ptrcasts[F] = PtrCastedI;
  } else {
    PtrCastedI = It->second;
  }
  I->replaceUsesOfWith(Op, PtrCastedI);
}
 
void SPIRVEmitIntrinsicsImpl::propagateElemType(
    Value *Op, Type *ElemTy,
    DenseSet<std::pair<Value *, Value *>> &VisitedSubst) {
  DenseMap<Function *, CallInst *> Ptrcasts;
  SmallVector<User *> Users(Op->users());
  for (auto *U : Users) {
    if (!isa<Instruction>(U) || isSpvIntrinsic(U))
      continue;
    if (!VisitedSubst.insert(std::make_pair(U, Op)).second)
      continue;
    Instruction *UI = dyn_cast<Instruction>(U);
    // If the instruction was validated already, we need to keep it valid by
    // keeping current Op type.
    if (isaGEP(UI) || TypeValidated.find(UI) != TypeValidated.end())
      replaceUsesOfWithSpvPtrcast(Op, ElemTy, UI, Ptrcasts);
  }
}
 
void SPIRVEmitIntrinsicsImpl::propagateElemTypeRec(
    Value *Op, Type *PtrElemTy, Type *CastElemTy,
    DenseSet<std::pair<Value *, Value *>> &VisitedSubst) {
  SmallPtrSet<Value *, 0> Visited;
  DenseMap<Function *, CallInst *> Ptrcasts;
  propagateElemTypeRec(Op, PtrElemTy, CastElemTy, VisitedSubst, Visited,
                       std::move(Ptrcasts));
}
 
void SPIRVEmitIntrinsicsImpl::propagateElemTypeRec(
    Value *Op, Type *PtrElemTy, Type *CastElemTy,
    DenseSet<std::pair<Value *, Value *>> &VisitedSubst,
    SmallPtrSetImpl<Value *> &Visited,
    DenseMap<Function *, CallInst *> Ptrcasts) {
  if (!Visited.insert(Op).second)
    return;
  SmallVector<User *> Users(Op->users());
  for (auto *U : Users) {
    if (!isa<Instruction>(U) || isSpvIntrinsic(U))
      continue;
    if (!VisitedSubst.insert(std::make_pair(U, Op)).second)
      continue;
    Instruction *UI = dyn_cast<Instruction>(U);
    // If the instruction was validated already, we need to keep it valid by
    // keeping current Op type.
    if (isaGEP(UI) || TypeValidated.find(UI) != TypeValidated.end())
      replaceUsesOfWithSpvPtrcast(Op, CastElemTy, UI, Ptrcasts);
  }
}
 
// Set element pointer type to the given value of ValueTy and tries to
// specify this type further (recursively) by Operand value, if needed.
 
Type *SPIRVEmitIntrinsicsImpl::deduceElementTypeByValueDeep(
    Type *ValueTy, Value *Operand, bool UnknownElemTypeI8) {
  SmallPtrSet<Value *, 0> Visited;
  return deduceElementTypeByValueDeep(ValueTy, Operand, Visited,
                                      UnknownElemTypeI8);
}
 
Type *SPIRVEmitIntrinsicsImpl::deduceElementTypeByValueDeep(
    Type *ValueTy, Value *Operand, SmallPtrSetImpl<Value *> &Visited,
    bool UnknownElemTypeI8) {
  Type *Ty = ValueTy;
  if (Operand) {
    if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
      if (Type *NestedTy =
              deduceElementTypeHelper(Operand, Visited, UnknownElemTypeI8))
        Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
    } else {
      Ty = deduceNestedTypeHelper(dyn_cast<User>(Operand), Ty, Visited,
                                  UnknownElemTypeI8);
    }
  }
  return Ty;
}
 
// Traverse User instructions to deduce an element pointer type of the operand.
Type *SPIRVEmitIntrinsicsImpl::deduceElementTypeByUsersDeep(
    Value *Op, SmallPtrSetImpl<Value *> &Visited, bool UnknownElemTypeI8) {
  if (!Op || !isPointerTy(Op->getType()) || isa<ConstantPointerNull>(Op) ||
      isa<UndefValue>(Op))
    return nullptr;
 
  if (auto ElemTy = getPointeeType(Op->getType()))
    return ElemTy;
 
  // maybe we already know operand's element type
  if (Type *KnownTy = GR->findDeducedElementType(Op))
    return KnownTy;
 
  for (User *OpU : Op->users()) {
    if (Instruction *Inst = dyn_cast<Instruction>(OpU)) {
      if (Type *Ty = deduceElementTypeHelper(Inst, Visited, UnknownElemTypeI8))
        return Ty;
    }
  }
  return nullptr;
}
 
// Implements what we know in advance about intrinsics and builtin calls
// TODO: consider feasibility of this particular case to be generalized by
// encoding knowledge about intrinsics and builtin calls by corresponding
// specification rules
static Type *getPointeeTypeByCallInst(StringRef DemangledName,
                                      Function *CalledF, unsigned OpIdx) {
  if ((DemangledName.starts_with("__spirv_ocl_printf(") ||
       DemangledName.starts_with("printf(")) &&
      OpIdx == 0)
    return IntegerType::getInt8Ty(CalledF->getContext());
  return nullptr;
}
 
// Deduce and return a successfully deduced Type of the Instruction,
// or nullptr otherwise.
Type *SPIRVEmitIntrinsicsImpl::deduceElementTypeHelper(Value *I,
                                                       bool UnknownElemTypeI8) {
  SmallPtrSet<Value *, 0> Visited;
  return deduceElementTypeHelper(I, Visited, UnknownElemTypeI8);
}
 
void SPIRVEmitIntrinsicsImpl::maybeAssignPtrType(Type *&Ty, Value *Op,
                                                 Type *RefTy,
                                                 bool UnknownElemTypeI8) {
  if (isUntypedPointerTy(RefTy)) {
    if (!UnknownElemTypeI8)
      return;
    insertTodoType(Op);
    if (isa<IntToPtrInst>(Op))
      return;
  }
  Ty = RefTy;
}
 
bool SPIRVEmitIntrinsicsImpl::walkLogicalAccessChainDynamic(
    Type *CurType, Value *Operand, uint64_t Multiplier,
    const std::function<void(Type *, uint64_t)> &OnLiteralIndexing,
    const std::function<void(Type *, Value *, uint64_t)> &OnDynamicIndexing) {
  // Dynamic indexing into a struct is not possible.
  // We know that we must be accessing the first element
  // of the struct if the current type is a struct.
  // Try to find the first array type that is at offset 0 in the struct.
  while (auto *ST = dyn_cast<StructType>(CurType)) {
    if (ST->getNumElements() == 0)
      break;
    CurType = ST->getElementType(0);
    OnLiteralIndexing(CurType, 0);
  }
 
  assert(CurType);
  ArrayType *AT = dyn_cast<ArrayType>(CurType);
  // Operand is not constant. Either we have an array and accept it, or we
  // give up.
  if (AT)
    OnDynamicIndexing(AT->getElementType(), Operand, Multiplier);
  return AT == nullptr;
}
 
bool SPIRVEmitIntrinsicsImpl::walkLogicalAccessChainConstant(
    Type *CurType, uint64_t Offset,
    const std::function<void(Type *, uint64_t)> &OnLiteralIndexing) {
  auto &DL = CurrF->getDataLayout();
 
  do {
    if (ArrayType *AT = dyn_cast<ArrayType>(CurType)) {
      uint64_t EltTypeSize = DL.getTypeAllocSize(AT->getElementType());
      assert(Offset < AT->getNumElements() * EltTypeSize);
      uint64_t Index = Offset / EltTypeSize;
      Offset = Offset - (Index * EltTypeSize);
      CurType = AT->getElementType();
      OnLiteralIndexing(CurType, Index);
    } else if (StructType *ST = dyn_cast<StructType>(CurType)) {
      uint32_t StructSize = DL.getTypeSizeInBits(ST) / 8;
      assert(Offset < StructSize);
      (void)StructSize;
      const auto &STL = DL.getStructLayout(ST);
      unsigned Element = STL->getElementContainingOffset(Offset);
      Offset -= STL->getElementOffset(Element);
      CurType = ST->getElementType(Element);
      OnLiteralIndexing(CurType, Element);
    } else if (auto *VT = dyn_cast<FixedVectorType>(CurType)) {
      Type *EltTy = VT->getElementType();
      TypeSize EltSizeBits = DL.getTypeSizeInBits(EltTy);
      assert(EltSizeBits % 8 == 0 &&
             "Element type size in bits must be a multiple of 8.");
      uint32_t EltTypeSize = EltSizeBits / 8;
      assert(Offset < VT->getNumElements() * EltTypeSize);
      uint64_t Index = Offset / EltTypeSize;
      Offset -= Index * EltTypeSize;
      CurType = EltTy;
      OnLiteralIndexing(CurType, Index);
    } else {
      // Unknown composite kind; give up.
      return true;
    }
  } while (Offset > 0);
 
  return false;
}
 
bool SPIRVEmitIntrinsicsImpl::walkLogicalAccessChain(
    GetElementPtrInst &GEP,
    const std::function<void(Type *, uint64_t)> &OnLiteralIndexing,
    const std::function<void(Type *, Value *, uint64_t)> &OnDynamicIndexing) {
  // We only rewrite byte-addressing GEP. Other should be left as-is.
  // Valid byte-addressing GEP must always have a single index.
  std::optional<uint64_t> MultiplierOpt =
      getByteAddressingMultiplier(GEP.getSourceElementType());
  assert(MultiplierOpt && "We only rewrite byte-addressing GEP");
  uint64_t Multiplier = *MultiplierOpt;
  assert(GEP.getNumIndices() == 1);
 
  Value *Src = getPointerRoot(GEP.getPointerOperand());
  Type *CurType = deduceElementType(Src, true);
 
  Value *Operand = *GEP.idx_begin();
  if (ConstantInt *CI = dyn_cast<ConstantInt>(Operand))
    return walkLogicalAccessChainConstant(
        CurType, CI->getZExtValue() * Multiplier, OnLiteralIndexing);
 
  return walkLogicalAccessChainDynamic(CurType, Operand, Multiplier,
                                       OnLiteralIndexing, OnDynamicIndexing);
}
 
Instruction *SPIRVEmitIntrinsicsImpl::buildLogicalAccessChainFromGEP(
    GetElementPtrInst &GEP) {
  auto &DL = CurrF->getDataLayout();
  IRBuilder<> B(GEP.getParent());
  B.SetInsertPoint(&GEP);
 
  std::vector<Value *> Indices;
  Indices.push_back(ConstantInt::get(
      IntegerType::getInt32Ty(CurrF->getContext()), 0, /* Signed= */ false));
  walkLogicalAccessChain(
      GEP,
      [&Indices, &B](Type *EltType, uint64_t Index) {
        Indices.push_back(
            ConstantInt::get(B.getInt64Ty(), Index, /* Signed= */ false));
      },
      [&Indices, &B, &DL, this](Type *EltType, Value *Offset,
                                uint64_t Multiplier) {
        Value *Index = nullptr;
        uint32_t EltTypeSize = DL.getTypeSizeInBits(EltType) / 8;
        assert(Multiplier != 0);
        if (Multiplier == EltTypeSize) {
          Index = Offset;
        } else if (EltTypeSize % Multiplier == 0) {
          Index =
              B.CreateUDiv(Offset, ConstantInt::get(Offset->getType(),
                                                    EltTypeSize / Multiplier,
                                                    /* Signed= */ false));
        } else {
          Index = B.CreateMul(Offset,
                              ConstantInt::get(Offset->getType(), Multiplier,
                                               /* Signed= */ false));
          insertAssignTypeIntrs(cast<Instruction>(Index), B);
          Index = B.CreateUDiv(Index,
                               ConstantInt::get(Offset->getType(), EltTypeSize,
                                                /* Signed= */ false));
        }
        insertAssignTypeIntrs(cast<Instruction>(Index), B);
        Indices.push_back(Index);
      });
 
  SmallVector<Type *, 2> Types = {GEP.getType(), GEP.getOperand(0)->getType()};
  SmallVector<Value *, 4> Args;
  Args.push_back(B.getInt1(GEP.isInBounds()));
  Args.push_back(GEP.getOperand(0));
  llvm::append_range(Args, Indices);
  Instruction *NewI =
      B.CreateIntrinsicWithoutFolding(Intrinsic::spv_gep, {Types}, {Args});
  replaceAllUsesWithAndErase(B, &GEP, NewI);
  return NewI;
}
 
Type *SPIRVEmitIntrinsicsImpl::getGEPTypeLogical(GetElementPtrInst *GEP) {
 
  Type *CurType = GEP->getResultElementType();
 
  bool Interrupted = walkLogicalAccessChain(
      *GEP, [&CurType](Type *EltType, uint64_t Index) { CurType = EltType; },
      [&CurType](Type *EltType, Value *Index, uint64_t) { CurType = EltType; });
 
  return Interrupted ? GEP->getResultElementType() : CurType;
}
 
Type *SPIRVEmitIntrinsicsImpl::getGEPType(GetElementPtrInst *Ref) {
  if (getByteAddressingMultiplier(Ref->getSourceElementType()) &&
      TM.getSubtargetImpl()->isLogicalSPIRV()) {
    return getGEPTypeLogical(Ref);
  }
 
  Type *Ty = nullptr;
  // TODO: not sure if GetElementPtrInst::getTypeAtIndex() does anything
  // useful here
  if (isNestedPointer(Ref->getSourceElementType())) {
    Ty = Ref->getSourceElementType();
    for (Use &U : drop_begin(Ref->indices()))
      Ty = GetElementPtrInst::getTypeAtIndex(Ty, U.get());
  } else {
    Ty = Ref->getResultElementType();
  }
  return Ty;
}
 
Type *SPIRVEmitIntrinsicsImpl::deduceElementTypeHelper(
    Value *I, SmallPtrSetImpl<Value *> &Visited, bool UnknownElemTypeI8,
    bool IgnoreKnownType) {
  // allow to pass nullptr as an argument
  if (!I)
    return nullptr;
 
  // maybe already known
  if (!IgnoreKnownType)
    if (Type *KnownTy = GR->findDeducedElementType(I))
      return KnownTy;
 
  // maybe a cycle
  if (!Visited.insert(I).second)
    return nullptr;
 
  // fallback value in case when we fail to deduce a type
  Type *Ty = nullptr;
  // look for known basic patterns of type inference
  if (auto *Ref = dyn_cast<AllocaInst>(I)) {
    maybeAssignPtrType(Ty, I, Ref->getAllocatedType(), UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<GetElementPtrInst>(I)) {
    Ty = getGEPType(Ref);
  } else if (auto *SGEP = dyn_cast<StructuredGEPInst>(I)) {
    Ty = SGEP->getResultElementType();
  } else if (auto *Ref = dyn_cast<LoadInst>(I)) {
    Value *Op = Ref->getPointerOperand();
    Type *KnownTy = GR->findDeducedElementType(Op);
    if (!KnownTy)
      KnownTy = Op->getType();
    if (Type *ElemTy = getPointeeType(KnownTy))
      maybeAssignPtrType(Ty, I, ElemTy, UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<GlobalValue>(I)) {
    if (auto *Fn = dyn_cast<Function>(Ref)) {
      Ty = SPIRV::getOriginalFunctionType(*Fn);
      GR->addDeducedElementType(I, Ty);
    } else {
      Ty = deduceElementTypeByValueDeep(
          Ref->getValueType(),
          Ref->getNumOperands() > 0 ? Ref->getOperand(0) : nullptr, Visited,
          UnknownElemTypeI8);
    }
  } else if (auto *Ref = dyn_cast<AddrSpaceCastInst>(I)) {
    Type *RefTy = deduceElementTypeHelper(Ref->getPointerOperand(), Visited,
                                          UnknownElemTypeI8);
    maybeAssignPtrType(Ty, I, RefTy, UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<IntToPtrInst>(I)) {
    maybeAssignPtrType(Ty, I, Ref->getDestTy(), UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<BitCastInst>(I)) {
    if (Type *Src = Ref->getSrcTy(), *Dest = Ref->getDestTy();
        isPointerTy(Src) && isPointerTy(Dest))
      Ty = deduceElementTypeHelper(Ref->getOperand(0), Visited,
                                   UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<AtomicCmpXchgInst>(I)) {
    Value *Op = Ref->getNewValOperand();
    if (isPointerTy(Op->getType()))
      Ty = deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<AtomicRMWInst>(I)) {
    Value *Op = Ref->getValOperand();
    if (isPointerTy(Op->getType()))
      Ty = deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8);
  } else if (auto *Ref = dyn_cast<PHINode>(I)) {
    Type *BestTy = nullptr;
    unsigned MaxN = 1;
    DenseMap<Type *, unsigned> PhiTys;
    for (int i = Ref->getNumIncomingValues() - 1; i >= 0; --i) {
      Ty = deduceElementTypeByUsersDeep(Ref->getIncomingValue(i), Visited,
                                        UnknownElemTypeI8);
      if (!Ty)
        continue;
      auto It = PhiTys.try_emplace(Ty, 1);
      if (!It.second) {
        ++It.first->second;
        if (It.first->second > MaxN) {
          MaxN = It.first->second;
          BestTy = Ty;
        }
      }
    }
    if (BestTy)
      Ty = BestTy;
  } else if (auto *Ref = dyn_cast<SelectInst>(I)) {
    for (Value *Op : {Ref->getTrueValue(), Ref->getFalseValue()}) {
      // A function pointer operand carries its function type directly. Other
      // operands are deduced from their uses.
      Ty = isa<Function>(Op)
               ? deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8)
               : deduceElementTypeByUsersDeep(Op, Visited, UnknownElemTypeI8);
      if (Ty)
        break;
    }
  } else if (auto *CI = dyn_cast<CallInst>(I)) {
    static StringMap<unsigned> ResTypeByArg = {
        {"to_global", 0},
        {"to_local", 0},
        {"to_private", 0},
        {"__spirv_GenericCastToPtr_ToGlobal", 0},
        {"__spirv_GenericCastToPtr_ToLocal", 0},
        {"__spirv_GenericCastToPtr_ToPrivate", 0},
        {"__spirv_GenericCastToPtrExplicit_ToGlobal", 0},
        {"__spirv_GenericCastToPtrExplicit_ToLocal", 0},
        {"__spirv_GenericCastToPtrExplicit_ToPrivate", 0}};
    // TODO: maybe improve performance by caching demangled names
 
    auto *II = dyn_cast<IntrinsicInst>(I);
    if (II && (II->getIntrinsicID() == Intrinsic::spv_resource_getbasepointer ||
               II->getIntrinsicID() == Intrinsic::spv_resource_getpointer)) {
      auto *HandleType = cast<TargetExtType>(II->getOperand(0)->getType());
      if (HandleType->getTargetExtName() == "spirv.Image" ||
          HandleType->getTargetExtName() == "spirv.SignedImage") {
        for (User *U : II->users()) {
          Ty = cast<Instruction>(U)->getAccessType();
          if (Ty)
            break;
        }
      } else if (HandleType->getTargetExtName() == "spirv.VulkanBuffer") {
        // This call is supposed to index into an array
        Ty = HandleType->getTypeParameter(0);
        if (II->getIntrinsicID() == Intrinsic::spv_resource_getpointer) {
          if (Ty->isArrayTy())
            Ty = Ty->getArrayElementType();
          else {
            assert(Ty && Ty->isStructTy());
            uint32_t Index =
                cast<ConstantInt>(II->getOperand(1))->getZExtValue();
            Ty = cast<StructType>(Ty)->getElementType(Index);
          }
        }
        Ty = reconstitutePeeledArrayType(Ty);
      } else {
        llvm_unreachable("Unknown handle type for spv_resource_getpointer.");
      }
    } else if (II && II->getIntrinsicID() ==
                         Intrinsic::spv_generic_cast_to_ptr_explicit) {
      Ty = deduceElementTypeHelper(CI->getArgOperand(0), Visited,
                                   UnknownElemTypeI8);
    } else if (Function *CalledF = CI->getCalledFunction()) {
      std::string DemangledName =
          getOclOrSpirvBuiltinDemangledName(CalledF->getName());
      if (DemangledName.length() > 0)
        DemangledName = SPIRV::lookupBuiltinNameHelper(DemangledName);
      auto AsArgIt = ResTypeByArg.find(DemangledName);
      if (AsArgIt != ResTypeByArg.end())
        Ty = deduceElementTypeHelper(CI->getArgOperand(AsArgIt->second),
                                     Visited, UnknownElemTypeI8);
      else if (Type *KnownRetTy = GR->findDeducedElementType(CalledF))
        Ty = KnownRetTy;
    }
  }
 
  // remember the found relationship
  if (Ty && !IgnoreKnownType) {
    // specify nested types if needed, otherwise return unchanged
    GR->addDeducedElementType(I, normalizeType(Ty));
  }
 
  return Ty;
}
 
// Re-create a type of the value if it has untyped pointer fields, also nested.
// Return the original value type if no corrections of untyped pointer
// information is found or needed.
Type *SPIRVEmitIntrinsicsImpl::deduceNestedTypeHelper(User *U,
                                                      bool UnknownElemTypeI8) {
  SmallPtrSet<Value *, 0> Visited;
  return deduceNestedTypeHelper(U, U->getType(), Visited, UnknownElemTypeI8);
}
 
Type *SPIRVEmitIntrinsicsImpl::deduceNestedTypeHelper(
    User *U, Type *OrigTy, SmallPtrSetImpl<Value *> &Visited,
    bool UnknownElemTypeI8) {
  if (!U)
    return OrigTy;
 
  // maybe already known
  if (Type *KnownTy = GR->findDeducedCompositeType(U))
    return KnownTy;
 
  // maybe a cycle
  if (!Visited.insert(U).second)
    return OrigTy;
 
  if (isa<StructType>(OrigTy)) {
    SmallVector<Type *> Tys;
    bool Change = false;
    for (unsigned i = 0; i < U->getNumOperands(); ++i) {
      Value *Op = U->getOperand(i);
      assert(Op && "Operands should not be null.");
      Type *OpTy = Op->getType();
      Type *Ty = OpTy;
      if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
        if (Type *NestedTy =
                deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))
          Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
      } else {
        Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,
                                    UnknownElemTypeI8);
      }
      Tys.push_back(Ty);
      Change |= Ty != OpTy;
    }
    if (Change) {
      Type *NewTy = StructType::create(Tys);
      GR->addDeducedCompositeType(U, NewTy);
      return NewTy;
    }
  } else if (auto *ArrTy = dyn_cast<ArrayType>(OrigTy)) {
    if (Value *Op = U->getNumOperands() > 0 ? U->getOperand(0) : nullptr) {
      Type *OpTy = ArrTy->getElementType();
      Type *Ty = OpTy;
      if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
        if (Type *NestedTy =
                deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))
          Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
      } else {
        Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,
                                    UnknownElemTypeI8);
      }
      if (Ty != OpTy) {
        Type *NewTy = ArrayType::get(Ty, ArrTy->getNumElements());
        GR->addDeducedCompositeType(U, NewTy);
        return NewTy;
      }
    }
  } else if (auto *VecTy = dyn_cast<VectorType>(OrigTy)) {
    if (Value *Op = U->getNumOperands() > 0 ? U->getOperand(0) : nullptr) {
      Type *OpTy = VecTy->getElementType();
      Type *Ty = OpTy;
      if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
        if (Type *NestedTy =
                deduceElementTypeHelper(Op, Visited, UnknownElemTypeI8))
          Ty = getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
      } else {
        Ty = deduceNestedTypeHelper(dyn_cast<User>(Op), OpTy, Visited,
                                    UnknownElemTypeI8);
      }
      if (Ty != OpTy) {
        Type *NewTy = VectorType::get(Ty, VecTy->getElementCount());
        GR->addDeducedCompositeType(U, normalizeType(NewTy));
        return NewTy;
      }
    }
  }
 
  return OrigTy;
}
 
Type *SPIRVEmitIntrinsicsImpl::deduceElementType(Value *I,
                                                 bool UnknownElemTypeI8) {
  if (Type *Ty = deduceElementTypeHelper(I, UnknownElemTypeI8))
    return Ty;
  if (!UnknownElemTypeI8)
    return nullptr;
  insertTodoType(I);
  return IntegerType::getInt8Ty(I->getContext());
}
 
static inline Type *getAtomicElemTy(SPIRVGlobalRegistry *GR, Instruction *I,
                                    Value *PointerOperand) {
  Type *PointeeTy = GR->findDeducedElementType(PointerOperand);
  if (PointeeTy && !isUntypedPointerTy(PointeeTy))
    return nullptr;
  auto *PtrTy = dyn_cast<PointerType>(I->getType());
  if (!PtrTy)
    return I->getType();
  if (Type *NestedTy = GR->findDeducedElementType(I))
    return getTypedPointerWrapper(NestedTy, PtrTy->getAddressSpace());
  return nullptr;
}
 
// Try to deduce element type for a call base. Returns false if this is an
// indirect function invocation, and true otherwise.
bool SPIRVEmitIntrinsicsImpl::deduceOperandElementTypeCalledFunction(
    CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,
    Type *&KnownElemTy, bool &Incomplete) {
  Function *CalledF = CI->getCalledFunction();
  if (!CalledF)
    return false;
  std::string DemangledName =
      getOclOrSpirvBuiltinDemangledName(CalledF->getName());
  if (DemangledName.length() > 0 &&
      !StringRef(DemangledName).starts_with("llvm.")) {
    const SPIRVSubtarget &ST = TM.getSubtarget<SPIRVSubtarget>(*CalledF);
    auto [Grp, Opcode, ExtNo] = SPIRV::mapBuiltinToOpcode(
        DemangledName, ST.getPreferredInstructionSet());
    if (Opcode == SPIRV::OpGroupAsyncCopy) {
      for (unsigned i = 0, PtrCnt = 0; i < CI->arg_size() && PtrCnt < 2; ++i) {
        Value *Op = CI->getArgOperand(i);
        if (!isPointerTy(Op->getType()))
          continue;
        ++PtrCnt;
        if (Type *ElemTy = GR->findDeducedElementType(Op))
          KnownElemTy = ElemTy; // src will rewrite dest if both are defined
        Ops.push_back(std::make_pair(Op, i));
      }
    } else if (Grp == SPIRV::Atomic || Grp == SPIRV::AtomicFloating) {
      if (CI->arg_size() == 0)
        return true;
      Value *Op = CI->getArgOperand(0);
      if (!isPointerTy(Op->getType()))
        return true;
      switch (Opcode) {
      case SPIRV::OpAtomicFAddEXT:
      case SPIRV::OpAtomicFMinEXT:
      case SPIRV::OpAtomicFMaxEXT:
      case SPIRV::OpAtomicLoad:
      case SPIRV::OpAtomicCompareExchangeWeak:
      case SPIRV::OpAtomicCompareExchange:
      case SPIRV::OpAtomicExchange:
      case SPIRV::OpAtomicIAdd:
      case SPIRV::OpAtomicISub:
      case SPIRV::OpAtomicOr:
      case SPIRV::OpAtomicXor:
      case SPIRV::OpAtomicAnd:
      case SPIRV::OpAtomicUMin:
      case SPIRV::OpAtomicUMax:
      case SPIRV::OpAtomicSMin:
      case SPIRV::OpAtomicSMax: {
        KnownElemTy = isPointerTy(CI->getType()) ? getAtomicElemTy(GR, CI, Op)
                                                 : CI->getType();
        if (!KnownElemTy)
          return true;
        Incomplete = isTodoType(Op);
        Ops.push_back(std::make_pair(Op, 0));
      } break;
      case SPIRV::OpAtomicStore: {
        if (CI->arg_size() < 4)
          return true;
        Value *ValOp = CI->getArgOperand(3);
        KnownElemTy = isPointerTy(ValOp->getType())
                          ? getAtomicElemTy(GR, CI, Op)
                          : ValOp->getType();
        if (!KnownElemTy)
          return true;
        Incomplete = isTodoType(Op);
        Ops.push_back(std::make_pair(Op, 0));
      } break;
      }
    }
  }
  return true;
}
 
// Try to deduce element type for a function pointer.
void SPIRVEmitIntrinsicsImpl::deduceOperandElementTypeFunctionPointer(
    CallInst *CI, SmallVector<std::pair<Value *, unsigned>> &Ops,
    Type *&KnownElemTy, bool IsPostprocessing) {
  Value *Op = CI->getCalledOperand();
  if (!Op || !isPointerTy(Op->getType()))
    return;
  Ops.push_back(std::make_pair(Op, std::numeric_limits<unsigned>::max()));
  FunctionType *FTy = SPIRV::getOriginalFunctionType(*CI);
  bool IsNewFTy = false, IsIncomplete = false;
  SmallVector<Type *, 4> ArgTys;
  for (auto &&[ParmIdx, Arg] : llvm::enumerate(CI->args())) {
    Type *ArgTy = Arg->getType();
    if (ArgTy->isPointerTy()) {
      if (Type *ElemTy = GR->findDeducedElementType(Arg)) {
        IsNewFTy = true;
        ArgTy = getTypedPointerWrapper(ElemTy, getPointerAddressSpace(ArgTy));
        if (isTodoType(Arg))
          IsIncomplete = true;
      } else {
        IsIncomplete = true;
      }
    } else {
      ArgTy = FTy->getFunctionParamType(ParmIdx);
    }
    ArgTys.push_back(ArgTy);
  }
  Type *RetTy = FTy->getReturnType();
  if (CI->getType()->isPointerTy()) {
    if (Type *ElemTy = GR->findDeducedElementType(CI)) {
      IsNewFTy = true;
      RetTy =
          getTypedPointerWrapper(ElemTy, getPointerAddressSpace(CI->getType()));
      if (isTodoType(CI))
        IsIncomplete = true;
    } else {
      IsIncomplete = true;
    }
  }
  if (!IsPostprocessing && IsIncomplete)
    insertTodoType(Op);
  KnownElemTy =
      IsNewFTy ? FunctionType::get(RetTy, ArgTys, FTy->isVarArg()) : FTy;
}
 
bool SPIRVEmitIntrinsicsImpl::deduceOperandElementTypeFunctionRet(
    Instruction *I, SmallPtrSetImpl<Instruction *> *IncompleteRets,
    const SmallPtrSetImpl<Value *> *AskOps, bool IsPostprocessing,
    Type *&KnownElemTy, Value *Op, Function *F) {
  KnownElemTy = GR->findDeducedElementType(F);
  if (KnownElemTy)
    return false;
  if (Type *OpElemTy = GR->findDeducedElementType(Op)) {
    OpElemTy = normalizeType(OpElemTy);
    GR->addDeducedElementType(F, OpElemTy);
    GR->addReturnType(
        F, TypedPointerType::get(OpElemTy,
                                 getPointerAddressSpace(F->getReturnType())));
    // non-recursive update of types in function uses
    DenseSet<std::pair<Value *, Value *>> VisitedSubst{std::make_pair(I, Op)};
    for (User *U : F->users()) {
      CallInst *CI = dyn_cast<CallInst>(U);
      if (!CI || CI->getCalledFunction() != F)
        continue;
      if (CallInst *AssignCI = GR->findAssignPtrTypeInstr(CI)) {
        if (Type *PrevElemTy = GR->findDeducedElementType(CI)) {
          GR->updateAssignType(AssignCI, CI,
                               getNormalizedPoisonValue(OpElemTy));
          propagateElemType(CI, PrevElemTy, VisitedSubst);
        }
      }
    }
    // Non-recursive update of types in the function uncomplete returns.
    // This may happen just once per a function, the latch is a pair of
    // findDeducedElementType(F) / addDeducedElementType(F, ...).
    // With or without the latch it is a non-recursive call due to
    // IncompleteRets set to nullptr in this call.
    if (IncompleteRets)
      for (Instruction *IncompleteRetI : *IncompleteRets)
        deduceOperandElementType(IncompleteRetI, nullptr, AskOps,
                                 IsPostprocessing);
  } else if (IncompleteRets) {
    IncompleteRets->insert(I);
  }
  TypeValidated.insert(I);
  return true;
}
 
// If the Instruction has Pointer operands with unresolved types, this function
// tries to deduce them. If the Instruction has Pointer operands with known
// types which differ from expected, this function tries to insert a bitcast to
// resolve the issue.
void SPIRVEmitIntrinsicsImpl::deduceOperandElementType(
    Instruction *I, SmallPtrSetImpl<Instruction *> *IncompleteRets,
    const SmallPtrSetImpl<Value *> *AskOps, bool IsPostprocessing) {
  SmallVector<std::pair<Value *, unsigned>> Ops;
  Type *KnownElemTy = nullptr;
  bool Incomplete = false;
  // look for known basic patterns of type inference
  if (auto *Ref = dyn_cast<PHINode>(I)) {
    if (!isPointerTy(I->getType()) ||
        !(KnownElemTy = GR->findDeducedElementType(I)))
      return;
    Incomplete = isTodoType(I);
    for (unsigned i = 0; i < Ref->getNumIncomingValues(); i++) {
      Value *Op = Ref->getIncomingValue(i);
      if (isPointerTy(Op->getType()))
        Ops.push_back(std::make_pair(Op, i));
    }
  } else if (auto *Ref = dyn_cast<AddrSpaceCastInst>(I)) {
    KnownElemTy = GR->findDeducedElementType(I);
    if (!KnownElemTy)
      return;
    Incomplete = isTodoType(I);
    Ops.push_back(std::make_pair(Ref->getPointerOperand(), 0));
  } else if (auto *Ref = dyn_cast<BitCastInst>(I)) {
    if (!isPointerTy(I->getType()))
      return;
    KnownElemTy = GR->findDeducedElementType(I);
    if (!KnownElemTy)
      return;
    Incomplete = isTodoType(I);
    Ops.push_back(std::make_pair(Ref->getOperand(0), 0));
  } else if (auto *Ref = dyn_cast<GetElementPtrInst>(I)) {
    if (GR->findDeducedElementType(Ref->getPointerOperand()))
      return;
    KnownElemTy = Ref->getSourceElementType();
    Ops.push_back(std::make_pair(Ref->getPointerOperand(),
                                 GetElementPtrInst::getPointerOperandIndex()));
  } else if (auto *Ref = dyn_cast<StructuredGEPInst>(I)) {
    if (GR->findDeducedElementType(Ref->getPointerOperand()))
      return;
    KnownElemTy = Ref->getBaseType();
    Ops.push_back(std::make_pair(Ref->getPointerOperand(),
                                 StructuredGEPInst::getPointerOperandIndex()));
  } else if (auto *Ref = dyn_cast<LoadInst>(I)) {
    KnownElemTy = I->getType();
    if (isUntypedPointerTy(KnownElemTy)) {
      // A T** loaded back from its alloca comes out opaque, dropping type info.
      // When the load is a pointer-to-pointer, type the alloca as that pointer.
      Type *LoadedElemTy = GR->findDeducedElementType(I);
      if (!LoadedElemTy || !isPointerTyOrWrapper(LoadedElemTy))
        return;
      Value *Root = Ref->getPointerOperand()->stripPointerCasts();
      if (!isa<AllocaInst>(Root))
        return;
      KnownElemTy = getTypedPointerWrapper(LoadedElemTy,
                                           getPointerAddressSpace(KnownElemTy));
    }
    Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());
    if (PointeeTy && !isUntypedPointerTy(PointeeTy))
      return;
    Ops.push_back(std::make_pair(Ref->getPointerOperand(),
                                 LoadInst::getPointerOperandIndex()));
  } else if (auto *Ref = dyn_cast<StoreInst>(I)) {
    if (!(KnownElemTy =
              reconstructType(Ref->getValueOperand(), false, IsPostprocessing)))
      return;
    Type *PointeeTy = GR->findDeducedElementType(Ref->getPointerOperand());
    if (PointeeTy && !isUntypedPointerTy(PointeeTy))
      return;
    Ops.push_back(std::make_pair(Ref->getPointerOperand(),
                                 StoreInst::getPointerOperandIndex()));
  } else if (auto *Ref = dyn_cast<AtomicCmpXchgInst>(I)) {
    KnownElemTy = isPointerTy(I->getType())
                      ? getAtomicElemTy(GR, I, Ref->getPointerOperand())
                      : I->getType();
    if (!KnownElemTy)
      return;
    Incomplete = isTodoType(Ref->getPointerOperand());
    Ops.push_back(std::make_pair(Ref->getPointerOperand(),
                                 AtomicCmpXchgInst::getPointerOperandIndex()));
  } else if (auto *Ref = dyn_cast<AtomicRMWInst>(I)) {
    KnownElemTy = isPointerTy(I->getType())
                      ? getAtomicElemTy(GR, I, Ref->getPointerOperand())
                      : I->getType();
    if (!KnownElemTy)
      return;
    Incomplete = isTodoType(Ref->getPointerOperand());
    Ops.push_back(std::make_pair(Ref->getPointerOperand(),
                                 AtomicRMWInst::getPointerOperandIndex()));
  } else if (auto *Ref = dyn_cast<SelectInst>(I)) {
    if (!isPointerTy(I->getType()) ||
        !(KnownElemTy = GR->findDeducedElementType(I)))
      return;
    Incomplete = isTodoType(I);
    for (unsigned i = 0; i < Ref->getNumOperands(); i++) {
      Value *Op = Ref->getOperand(i);
      if (isPointerTy(Op->getType()))
        Ops.push_back(std::make_pair(Op, i));
    }
  } else if (auto *Ref = dyn_cast<ReturnInst>(I)) {
    if (!isPointerTy(CurrF->getReturnType()))
      return;
    Value *Op = Ref->getReturnValue();
    if (!Op)
      return;
    if (deduceOperandElementTypeFunctionRet(I, IncompleteRets, AskOps,
                                            IsPostprocessing, KnownElemTy, Op,
                                            CurrF))
      return;
    Incomplete = isTodoType(CurrF);
    Ops.push_back(std::make_pair(Op, 0));
  } else if (auto *Ref = dyn_cast<ICmpInst>(I)) {
    if (!isPointerTy(Ref->getOperand(0)->getType()))
      return;
    Value *Op0 = Ref->getOperand(0);
    Value *Op1 = Ref->getOperand(1);
    bool Incomplete0 = isTodoType(Op0);
    bool Incomplete1 = isTodoType(Op1);
    Type *ElemTy1 = GR->findDeducedElementType(Op1);
    Type *ElemTy0 = (Incomplete0 && !Incomplete1 && ElemTy1)
                        ? nullptr
                        : GR->findDeducedElementType(Op0);
    if (ElemTy0) {
      KnownElemTy = ElemTy0;
      Incomplete = Incomplete0;
      Ops.push_back(std::make_pair(Op1, 1));
    } else if (ElemTy1) {
      KnownElemTy = ElemTy1;
      Incomplete = Incomplete1;
      Ops.push_back(std::make_pair(Op0, 0));
    }
  } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
    if (!CI->isIndirectCall())
      deduceOperandElementTypeCalledFunction(CI, Ops, KnownElemTy, Incomplete);
    else if (HaveFunPtrs)
      deduceOperandElementTypeFunctionPointer(CI, Ops, KnownElemTy,
                                              IsPostprocessing);
  }
 
  // There is no enough info to deduce types or all is valid.
  if (!KnownElemTy || Ops.size() == 0)
    return;
 
  LLVMContext &Ctx = CurrF->getContext();
  IRBuilder<> B(Ctx);
  for (auto &OpIt : Ops) {
    Value *Op = OpIt.first;
    if (AskOps && !AskOps->contains(Op))
      continue;
    Type *AskTy = nullptr;
    CallInst *AskCI = nullptr;
    if (IsPostprocessing && AskOps) {
      AskTy = GR->findDeducedElementType(Op);
      AskCI = GR->findAssignPtrTypeInstr(Op);
      assert(AskTy && AskCI);
    }
    Type *Ty = AskTy ? AskTy : GR->findDeducedElementType(Op);
    if (Ty == KnownElemTy)
      continue;
    Value *OpTyVal = getNormalizedPoisonValue(KnownElemTy);
    Type *OpTy = Op->getType();
    // Do not let a non-pointer element type clobber an already-deduced pointer
    // element type for the same operand.
    bool WouldClobberPtrWithNonPtr = Ty && isPointerTyOrWrapper(Ty) &&
                                     !isPointerTyOrWrapper(KnownElemTy) &&
                                     tracesToPointerAlloca(Op);
    if (Op->hasUseList() && !WouldClobberPtrWithNonPtr &&
        (!Ty || AskTy || isUntypedPointerTy(Ty) || isTodoType(Op))) {
      Type *PrevElemTy = GR->findDeducedElementType(Op);
      GR->addDeducedElementType(Op, normalizeType(KnownElemTy));
      // check if KnownElemTy is complete
      if (!Incomplete)
        eraseTodoType(Op);
      else if (!IsPostprocessing)
        insertTodoType(Op);
      // check if there is existing Intrinsic::spv_assign_ptr_type instruction
      CallInst *AssignCI = AskCI ? AskCI : GR->findAssignPtrTypeInstr(Op);
      if (AssignCI == nullptr) {
        Instruction *User = dyn_cast<Instruction>(Op->use_begin()->get());
        setInsertPointSkippingPhis(B, User ? User->getNextNode() : I);
        CallInst *CI =
            buildIntrWithMD(Intrinsic::spv_assign_ptr_type, {OpTy}, OpTyVal, Op,
                            {B.getInt32(getPointerAddressSpace(OpTy))}, B);
        GR->addAssignPtrTypeInstr(Op, CI);
      } else {
        GR->updateAssignType(AssignCI, Op, OpTyVal);
        DenseSet<std::pair<Value *, Value *>> VisitedSubst{
            std::make_pair(I, Op)};
        propagateElemTypeRec(Op, KnownElemTy, PrevElemTy, VisitedSubst);
      }
    } else {
      eraseTodoType(Op);
      CallInst *PtrCastI =
          buildSpvPtrcast(I->getParent()->getParent(), Op, KnownElemTy);
      if (OpIt.second == std::numeric_limits<unsigned>::max())
        dyn_cast<CallInst>(I)->setCalledOperand(PtrCastI);
      else
        I->setOperand(OpIt.second, PtrCastI);
    }
  }
  TypeValidated.insert(I);
}
 
void SPIRVEmitIntrinsicsImpl::replaceMemInstrUses(Instruction *Old,
                                                  Instruction *New,
                                                  IRBuilder<> &B) {
  while (!Old->user_empty()) {
    auto *U = Old->user_back();
    if (isAssignTypeInstr(U)) {
      B.SetInsertPoint(U);
      SmallVector<Value *, 2> Args = {New, U->getOperand(1)};
      CallInst *AssignCI = B.CreateIntrinsicWithoutFolding(
          Intrinsic::spv_assign_type, {New->getType()}, Args);
      GR->addAssignPtrTypeInstr(New, AssignCI);
      U->eraseFromParent();
    } else if (isMemInstrToReplace(U) || isa<ReturnInst>(U) ||
               isa<CallInst>(U)) {
      U->replaceUsesOfWith(Old, New);
      // For a `llvm.spv.abort` call whose composite message argument was
      // rewritten to a value-id (i32), also retarget the call to a matching
      // intrinsic declaration so the IR verifier is satisfied. The SPIR-V
      // type of the value is tracked via the GlobalRegistry, so the selector
      // still emits OpAbortKHR with the original composite type.
      if (auto *CI = dyn_cast<CallInst>(U);
          CI && CI->getIntrinsicID() == Intrinsic::spv_abort) {
        Type *NewArgTy = New->getType();
        Type *ExpectedArgTy = CI->getFunctionType()->getParamType(0);
        if (NewArgTy != ExpectedArgTy) {
          Module *M = CI->getModule();
          Function *NewF = Intrinsic::getOrInsertDeclaration(
              M, Intrinsic::spv_abort, {NewArgTy});
          CI->setCalledFunction(NewF);
        }
      }
    } else if (isa<PHINode>(U) || isa<SelectInst>(U) || isa<FreezeInst>(U)) {
      // Aggregate-typed PHIs, selects and freezes have already been mutated to
      // the i32 value-id type up front in runOnFunction, so only the operand
      // needs replacing here; their extractvalue users are lowered to
      // spv_extractv by visitExtractValueInst.
      assert(U->getType() == New->getType() &&
             "aggregate PHI/select/freeze should have been mutated to value-id "
             "type");
      U->replaceUsesOfWith(Old, New);
    } else {
      llvm_unreachable("illegal aggregate intrinsic user");
    }
  }
  New->copyMetadata(*Old);
  Old->eraseFromParent();
}
 
// Lower a poison or undef Op to its placeholder intrinsic.
Value *SPIRVEmitIntrinsicsImpl::lowerUndefOrPoison(Value *Op, IRBuilder<> &B,
                                                   bool HasPoisonExt) {
  auto *UV = dyn_cast<UndefValue>(Op);
  if (!UV)
    return nullptr;
 
  bool AsPoison = HasPoisonExt && isa<PoisonValue>(UV);
  if (isa<PoisonValue>(UV) && !HasPoisonExt)
    LLVM_DEBUG(dbgs() << "SPV_KHR_poison_freeze is not enabled. Poison is "
                         "lowered as undef\n");
 
  Intrinsic::ID IID = AsPoison ? Intrinsic::spv_poison : Intrinsic::spv_undef;
  Type *Ty = UV->getType();
 
  // Aggregates use an i32-result placeholder with the real type kept in
  // AggrConstTypes and scalar poison uses a type-overloaded one.
  if (Ty->isAggregateType()) {
    auto *Call =
        AsPoison ? B.CreateIntrinsicWithoutFolding(IID, {B.getInt32Ty()}, {})
                 : B.CreateIntrinsicWithoutFolding(IID, {});
    AggrConsts[Call] = UV;
    AggrConstTypes[Call] = Ty;
    return Call;
  }
 
  if (AsPoison)
    return B.CreateIntrinsic(IID, {Ty}, {});
  return nullptr;
}
 
// Replace aggregate undef or poison operands and extension-enabled scalar
// poison operands with placeholder intrinsics. Scalar undef is left as is. See
// lowerUndefOrPoison.
void SPIRVEmitIntrinsicsImpl::preprocessUndefsAndPoisons(IRBuilder<> &B) {
  const SPIRVSubtarget *STI = TM.getSubtargetImpl(*CurrF);
  bool HasPoisonExt =
      STI->canUseExtension(SPIRV::Extension::SPV_KHR_poison_freeze);
 
  SmallVector<Instruction *, 16> Insts;
  for (auto &I : instructions(CurrF))
    Insts.push_back(&I);
 
  for (Instruction *I : Insts) {
    bool BPrepared = false;
    auto *Phi = dyn_cast<PHINode>(I);
    for (unsigned Idx = 0; Idx < I->getNumOperands(); ++Idx) {
      Value *Op = I->getOperand(Idx);
      if (!isa<UndefValue>(Op) || Op->getType()->isMetadataTy())
        continue;
      bool IsScalar = !Op->getType()->isAggregateType();
      bool AsPoison = HasPoisonExt && isa<PoisonValue>(Op);
      // Scalar undef or extensionless scalar poison is directly translatable.
      if (IsScalar && !AsPoison)
        continue;
      // Scalar poison in a phi materializes in the incoming block. Everything
      // else materializes right before I.
      if (IsScalar && Phi)
        B.SetInsertPoint(Phi->getIncomingBlock(Idx)->getTerminator());
      else if (!BPrepared) {
        setInsertPointSkippingPhis(B, I);
        BPrepared = true;
      }
      if (Value *Repl = lowerUndefOrPoison(Op, B, HasPoisonExt))
        I->setOperand(Idx, Repl);
    }
  }
}
 
// Simplify addrspacecast(null) instructions to ConstantPointerNull of the
// target type. Casting null always yields null, and this avoids SPIR-V
// lowering issues where the null gets typed as an integer instead of a
// pointer.
void SPIRVEmitIntrinsicsImpl::simplifyNullAddrSpaceCasts() {
  for (Instruction &I : make_early_inc_range(instructions(CurrF)))
    if (auto *ASC = dyn_cast<AddrSpaceCastInst>(&I))
      if (isa<ConstantPointerNull>(ASC->getPointerOperand())) {
        ASC->replaceAllUsesWith(
            ConstantPointerNull::get(cast<PointerType>(ASC->getType())));
        ASC->eraseFromParent();
      }
}
 
// True for an aggregate value the legalizer splits into a multi-result op
// (with.overflow -> G_UADDO, frexp/sincos/modf -> G_FFREXP/...). These keep a
// genuine multi-register result; all other aggregates become a single value-id.
static bool isMultiRegisterAggregate(Value *V) {
  if (!V->getType()->isAggregateType())
    return false;
  return isa<IntrinsicInst>(V) && !isSpvIntrinsic(V);
}
 
// True for an aggregate PHI/select/freeze, which is lowered to a single
// value-id.
static bool isAggregateValueIdInstr(const Instruction &I) {
  return (isa<PHINode>(I) || isa<SelectInst>(I) || isa<FreezeInst>(I)) &&
         I.getType()->isAggregateType();
}
 
// Give each multi-register aggregate arm of an aggregate PHI/select/freeze a
// single value-id by reassembling it with extractvalue + insertvalue, so the
// arm matches the result once it is mutated to a value-id.
void SPIRVEmitIntrinsicsImpl::insertCompositeAggregateArms(Instruction *I,
                                                           IRBuilder<> &B) {
  auto *Phi = dyn_cast<PHINode>(I);
  for (Use &U : I->operands()) {
    Value *Op = U.get();
    if (!isMultiRegisterAggregate(Op))
      continue;
    // A PHI arm materializes in its incoming block, everything else after the
    // producer.
    if (Phi)
      B.SetInsertPoint(Phi->getIncomingBlock(U)->getTerminator());
    else
      setInsertPointAfterDef(B, cast<Instruction>(Op));
    auto *AggrTy = cast<StructType>(Op->getType());
    Value *Composite = PoisonValue::get(AggrTy);
    for (unsigned Idx = 0, E = AggrTy->getNumElements(); Idx != E; ++Idx) {
      Value *Field = B.CreateExtractValue(Op, Idx);
      Composite = B.CreateInsertValue(Composite, Field, Idx);
    }
    U.set(Composite);
  }
}
 
void SPIRVEmitIntrinsicsImpl::preprocessCompositeConstants(IRBuilder<> &B) {
  const SPIRVSubtarget *STI = TM.getSubtargetImpl(*CurrF);
  bool HasPoisonExt =
      STI->canUseExtension(SPIRV::Extension::SPV_KHR_poison_freeze);
  std::queue<Instruction *> Worklist;
  for (auto &I : instructions(CurrF))
    Worklist.push(&I);
 
  while (!Worklist.empty()) {
    auto *I = Worklist.front();
    bool IsPhi = isa<PHINode>(I), BPrepared = false;
    assert(I);
    bool KeepInst = false;
    for (const auto &Op : I->operands()) {
      Constant *AggrConst = nullptr;
      Type *ResTy = nullptr;
      if (auto *COp = dyn_cast<ConstantVector>(Op)) {
        AggrConst = COp;
        ResTy = COp->getType();
      } else if (auto *COp = dyn_cast<ConstantArray>(Op)) {
        AggrConst = COp;
        ResTy = B.getInt32Ty();
      } else if (auto *COp = dyn_cast<ConstantStruct>(Op)) {
        AggrConst = COp;
        ResTy = B.getInt32Ty();
      } else if (auto *COp = dyn_cast<ConstantDataArray>(Op)) {
        AggrConst = COp;
        ResTy = B.getInt32Ty();
      } else if (auto *COp = dyn_cast<ConstantAggregateZero>(Op)) {
        AggrConst = COp;
        ResTy = Op->getType()->isVectorTy() ? COp->getType() : B.getInt32Ty();
      }
      if (AggrConst) {
        auto PrepareInsert = [&]() {
          if (BPrepared)
            return;
          IsPhi ? B.SetInsertPointPastAllocas(I->getParent()->getParent())
                : B.SetInsertPoint(I);
          BPrepared = true;
        };
        SmallVector<Value *> Args;
        if (auto *COp = dyn_cast<ConstantDataSequential>(Op))
          for (unsigned i = 0; i < COp->getNumElements(); ++i)
            Args.push_back(COp->getElementAsConstant(i));
        else
          for (Value *Op : AggrConst->operands()) {
            // Simplify addrspacecast(null) to null in the target address space
            // so that null pointers get the correct pointer type when lowered.
            if (auto *CE = dyn_cast<ConstantExpr>(Op);
                CE && CE->getOpcode() == Instruction::AddrSpaceCast &&
                isa<ConstantPointerNull>(CE->getOperand(0)))
              Op = ConstantPointerNull::get(cast<PointerType>(CE->getType()));
            // Undef or poison nested in a constant aggregate is not a direct
            // instruction operand, so preprocessUndefsAndPoisons() misses it.
            // An unlowered aggregate one would reach IRTranslator as an
            // untranslatable spv_const_composite operand.
            if (isa<UndefValue>(Op)) {
              PrepareInsert();
              if (Value *Repl = lowerUndefOrPoison(Op, B, HasPoisonExt))
                Op = Repl;
            }
            Args.push_back(Op);
          }
        PrepareInsert();
        auto *CI = B.CreateIntrinsicWithoutFolding(
            Intrinsic::spv_const_composite, {ResTy}, {Args});
        Worklist.push(CI);
        I->replaceUsesOfWith(Op, CI);
        KeepInst = true;
        AggrConsts[CI] = AggrConst;
        AggrConstTypes[CI] = deduceNestedTypeHelper(AggrConst, false);
      }
    }
    if (!KeepInst)
      Worklist.pop();
  }
}
 
static void createDecorationIntrinsic(Instruction *I, MDNode *Node,
                                      IRBuilder<> &B) {
  LLVMContext &Ctx = I->getContext();
  setInsertPointAfterDef(B, I);
  B.CreateIntrinsic(Intrinsic::spv_assign_decoration, {I->getType()},
                    {I, MetadataAsValue::get(Ctx, MDNode::get(Ctx, {Node}))});
}
 
static void createRoundingModeDecoration(Instruction *I,
                                         unsigned RoundingModeDeco,
                                         IRBuilder<> &B) {
  LLVMContext &Ctx = I->getContext();
  Type *Int32Ty = Type::getInt32Ty(Ctx);
  MDNode *RoundingModeNode = MDNode::get(
      Ctx,
      {ConstantAsMetadata::get(
           ConstantInt::get(Int32Ty, SPIRV::Decoration::FPRoundingMode)),
       ConstantAsMetadata::get(ConstantInt::get(Int32Ty, RoundingModeDeco))});
  createDecorationIntrinsic(I, RoundingModeNode, B);
}
 
static void createSaturatedConversionDecoration(Instruction *I,
                                                IRBuilder<> &B) {
  LLVMContext &Ctx = I->getContext();
  Type *Int32Ty = Type::getInt32Ty(Ctx);
  MDNode *SaturatedConversionNode =
      MDNode::get(Ctx, {ConstantAsMetadata::get(ConstantInt::get(
                           Int32Ty, SPIRV::Decoration::SaturatedConversion))});
  createDecorationIntrinsic(I, SaturatedConversionNode, B);
}
 
static void addSaturatedDecorationToIntrinsic(Instruction *I, IRBuilder<> &B) {
  if (match(I, m_AnyIntrinsic<Intrinsic::fptosi_sat, Intrinsic::fptoui_sat>()))
    createSaturatedConversionDecoration(I, B);
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitCallInst(CallInst &Call) {
  if (!Call.isInlineAsm())
    return &Call;
 
  LLVMContext &Ctx = CurrF->getContext();
  // TODO: this does not retain elementtype info for memory constraints, which
  //       in turn means that we lower them into pointers to i8, rather than
  //       pointers to elementtype; this can be fixed during reverse translation
  //       but we should correct it here, possibly by tweaking the function
  //       type to take TypedPointerType args.
  Constant *TyC = UndefValue::get(SPIRV::getOriginalFunctionType(Call));
  MDString *ConstraintString =
      MDString::get(Ctx, SPIRV::getOriginalAsmConstraints(Call));
  SmallVector<Value *> Args = {
      buildMD(TyC),
      MetadataAsValue::get(Ctx, MDNode::get(Ctx, ConstraintString))};
  for (unsigned OpIdx = 0; OpIdx < Call.arg_size(); OpIdx++)
    Args.push_back(Call.getArgOperand(OpIdx));
 
  IRBuilder<> B(Call.getParent());
  B.SetInsertPoint(&Call);
  B.CreateIntrinsic(Intrinsic::spv_inline_asm, {Args});
  return &Call;
}
 
// Use a tip about rounding mode to create a decoration.
void SPIRVEmitIntrinsicsImpl::useRoundingMode(ConstrainedFPIntrinsic *FPI,
                                              IRBuilder<> &B) {
  std::optional<RoundingMode> RM = FPI->getRoundingMode();
  if (!RM.has_value())
    return;
  unsigned RoundingModeDeco = std::numeric_limits<unsigned>::max();
  switch (RM.value()) {
  default:
    // ignore unknown rounding modes
    break;
  case RoundingMode::NearestTiesToEven:
    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTE;
    break;
  case RoundingMode::TowardNegative:
    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTN;
    break;
  case RoundingMode::TowardPositive:
    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTP;
    break;
  case RoundingMode::TowardZero:
    RoundingModeDeco = SPIRV::FPRoundingMode::FPRoundingMode::RTZ;
    break;
  case RoundingMode::Dynamic:
  case RoundingMode::NearestTiesToAway:
    // TODO: check if supported
    break;
  }
  if (RoundingModeDeco == std::numeric_limits<unsigned>::max())
    return;
  // Convert the tip about rounding mode into a decoration record.
  createRoundingModeDecoration(FPI, RoundingModeDeco, B);
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitSwitchInst(SwitchInst &I) {
  BasicBlock *ParentBB = I.getParent();
  Function *F = ParentBB->getParent();
  IRBuilder<> B(ParentBB);
  B.SetInsertPoint(&I);
  SmallVector<Value *, 4> Args;
  SmallVector<BasicBlock *> BBCases;
  Args.push_back(I.getCondition());
  BBCases.push_back(I.getDefaultDest());
  Args.push_back(BlockAddress::get(F, I.getDefaultDest()));
  for (auto &Case : I.cases()) {
    Args.push_back(Case.getCaseValue());
    BBCases.push_back(Case.getCaseSuccessor());
    Args.push_back(BlockAddress::get(F, Case.getCaseSuccessor()));
  }
  CallInst *NewI = B.CreateIntrinsicWithoutFolding(
      Intrinsic::spv_switch, {I.getOperand(0)->getType()}, {Args});
  // remove switch to avoid its unneeded and undesirable unwrap into branches
  // and conditions
  replaceAllUsesWith(&I, NewI);
  I.eraseFromParent();
  // insert artificial and temporary instruction to preserve valid CFG,
  // it will be removed after IR translation pass
  B.SetInsertPoint(ParentBB);
  IndirectBrInst *BrI = B.CreateIndirectBr(
      Constant::getNullValue(PointerType::getUnqual(ParentBB->getContext())),
      BBCases.size());
  for (BasicBlock *BBCase : BBCases)
    BrI->addDestination(BBCase);
  return BrI;
}
 
static bool isFirstIndexZero(const GetElementPtrInst *GEP) {
  return GEP->getNumIndices() > 0 && match(GEP->getOperand(1), m_Zero());
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitIntrinsicInst(IntrinsicInst &I) {
  auto *SGEP = dyn_cast<StructuredGEPInst>(&I);
  if (!SGEP)
    return &I;
 
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  SmallVector<Type *, 2> Types = {I.getType(), I.getOperand(0)->getType()};
  SmallVector<Value *, 4> Args;
  Args.push_back(/* inBounds= */ B.getInt1(true));
  Args.push_back(I.getOperand(0));
  Args.push_back(/* zero index */ B.getInt32(0));
  for (unsigned J = 0; J < SGEP->getNumIndices(); ++J)
    Args.push_back(SGEP->getIndexOperand(J));
 
  Instruction *NewI =
      B.CreateIntrinsicWithoutFolding(Intrinsic::spv_gep, Types, Args);
  replaceAllUsesWithAndErase(B, &I, NewI);
  return NewI;
}
 
Instruction *
SPIRVEmitIntrinsicsImpl::visitGetElementPtrInst(GetElementPtrInst &I) {
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
 
  // OpPtrAccessChain requires a scalar pointer result; scalarize per-lane
  // GEPs that return <N x ptr> and rebuild the vector via insertelement.
  if (auto *RetVTy = dyn_cast<FixedVectorType>(I.getType())) {
    unsigned N = RetVTy->getNumElements();
    Value *PtrOp = I.getPointerOperand();
    bool PtrIsVec = isa<VectorType>(PtrOp->getType());
    Type *ResultPtrTy = RetVTy->getElementType();
    Type *ScalarPtrTy = PtrOp->getType()->getScalarType();
    SmallVector<Type *, 2> GepTypes = {ResultPtrTy, ScalarPtrTy};
    Value *InBounds = B.getInt1(I.isInBounds());
    Type *LanePointeeTy = getGEPType(&I);
    Type *SrcElemTy = I.getSourceElementType();
 
    // Pin the lane pointee type on the vector operand and on each extracted
    // lane so the prelegalizer wraps them as OpTypeVector/OpTypePointer of
    // the right element type instead of defaulting to i8.
    if (PtrIsVec)
      GR->buildAssignPtr(B, SrcElemTy, PtrOp);
 
    Value *VecResult = PoisonValue::get(RetVTy);
    for (unsigned Lane = 0; Lane < N; ++Lane) {
      Value *LaneIdx = B.getInt32(Lane);
      Value *ScalarPtr = PtrOp;
      if (PtrIsVec) {
        SmallVector<Type *, 3> ExtractTypes = {ScalarPtrTy, PtrOp->getType(),
                                               LaneIdx->getType()};
        ScalarPtr = B.CreateIntrinsic(Intrinsic::spv_extractelt, {ExtractTypes},
                                      {PtrOp, LaneIdx});
        GR->buildAssignPtr(B, SrcElemTy, ScalarPtr);
      }
      SmallVector<Value *, 4> Args;
      Args.push_back(InBounds);
      Args.push_back(ScalarPtr);
      for (Value *Idx : I.indices()) {
        if (isa<VectorType>(Idx->getType()))
          Args.push_back(B.CreateExtractElement(Idx, LaneIdx));
        else
          Args.push_back(Idx);
      }
      Value *ScalarGep = B.CreateIntrinsic(Intrinsic::spv_gep, GepTypes, Args);
      GR->buildAssignPtr(B, LanePointeeTy, ScalarGep);
      VecResult = B.CreateInsertElement(VecResult, ScalarGep, LaneIdx);
    }
 
    auto *NewI = cast<Instruction>(VecResult);
    replaceAllUsesWithAndErase(B, &I, NewI);
 
    if (CallInst *Old = GR->findAssignPtrTypeInstr(NewI)) {
      Old->eraseFromParent();
      GR->addAssignPtrTypeInstr(NewI, nullptr);
    }
    setInsertPointAfterDef(B, NewI);
    GR->buildAssignPtr(B, LanePointeeTy, NewI);
 
    return NewI;
  }
 
  if (TM.getSubtargetImpl()->isLogicalSPIRV() && !isFirstIndexZero(&I)) {
    // Logical SPIR-V cannot use the OpPtrAccessChain instruction. If the first
    // index of the GEP is not 0, then we need to try to adjust it.
    //
    // If the GEP is doing byte addressing, try to rebuild the full access chain
    // from the type of the pointer.
    if (getByteAddressingMultiplier(I.getSourceElementType())) {
      return buildLogicalAccessChainFromGEP(I);
    }
 
    // Look for the array-to-pointer decay. If this is the pattern
    // we can adjust the types, and prepend a 0 to the indices.
    Value *PtrOp = I.getPointerOperand();
    Type *SrcElemTy = I.getSourceElementType();
    Type *DeducedPointeeTy = deduceElementType(PtrOp, true);
 
    if (auto *ArrTy = dyn_cast<ArrayType>(DeducedPointeeTy)) {
      if (ArrTy->getElementType() == SrcElemTy) {
        SmallVector<Value *> NewIndices;
        Type *FirstIdxType = I.getOperand(1)->getType();
        NewIndices.push_back(ConstantInt::get(FirstIdxType, 0));
        for (Value *Idx : I.indices())
          NewIndices.push_back(Idx);
 
        SmallVector<Type *, 2> Types = {I.getType(), I.getPointerOperandType()};
        SmallVector<Value *, 4> Args;
        Args.push_back(B.getInt1(I.isInBounds()));
        Args.push_back(I.getPointerOperand());
        Args.append(NewIndices.begin(), NewIndices.end());
 
        Instruction *NewI = B.CreateIntrinsicWithoutFolding(Intrinsic::spv_gep,
                                                            {Types}, {Args});
        replaceAllUsesWithAndErase(B, &I, NewI);
        return NewI;
      }
    }
  }
 
  SmallVector<Type *, 2> Types = {I.getType(), I.getOperand(0)->getType()};
  SmallVector<Value *, 4> Args;
  Args.push_back(B.getInt1(I.isInBounds()));
  llvm::append_range(Args, I.operands());
  Instruction *NewI =
      B.CreateIntrinsicWithoutFolding(Intrinsic::spv_gep, {Types}, {Args});
  replaceAllUsesWithAndErase(B, &I, NewI);
  return NewI;
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitBitCastInst(BitCastInst &I) {
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  Value *Source = I.getOperand(0);
 
  // SPIR-V, contrary to LLVM 17+ IR, supports bitcasts between pointers of
  // varying element types. In case of IR coming from older versions of LLVM
  // such bitcasts do not provide sufficient information, should be just skipped
  // here, and handled in insertPtrCastOrAssignTypeInstr.
  if (isPointerTy(I.getType())) {
    replaceAllUsesWith(&I, Source);
    I.eraseFromParent();
    return nullptr;
  }
 
  SmallVector<Type *, 2> Types = {I.getType(), Source->getType()};
  SmallVector<Value *> Args(I.op_begin(), I.op_end());
  Instruction *NewI =
      B.CreateIntrinsicWithoutFolding(Intrinsic::spv_bitcast, {Types}, {Args});
  replaceAllUsesWithAndErase(B, &I, NewI);
  return NewI;
}
 
void SPIRVEmitIntrinsicsImpl::insertAssignPtrTypeTargetExt(
    TargetExtType *AssignedType, Value *V, IRBuilder<> &B) {
  Type *VTy = V->getType();
 
  // A couple of sanity checks.
  assert((isPointerTy(VTy)) && "Expect a pointer type!");
  if (Type *ElemTy = getPointeeType(VTy))
    if (ElemTy != AssignedType)
      report_fatal_error("Unexpected pointer element type!");
 
  CallInst *AssignCI = GR->findAssignPtrTypeInstr(V);
  if (!AssignCI) {
    GR->buildAssignType(B, AssignedType, V);
    return;
  }
 
  Type *CurrentType =
      dyn_cast<ConstantAsMetadata>(
          cast<MetadataAsValue>(AssignCI->getOperand(1))->getMetadata())
          ->getType();
  if (CurrentType == AssignedType)
    return;
 
  // Builtin types cannot be redeclared or casted.
  if (CurrentType->isTargetExtTy())
    report_fatal_error("Type mismatch " + CurrentType->getTargetExtName() +
                           "/" + AssignedType->getTargetExtName() +
                           " for value " + V->getName(),
                       false);
 
  // Our previous guess about the type seems to be wrong, let's update
  // inferred type according to a new, more precise type information.
  GR->updateAssignType(AssignCI, V, getNormalizedPoisonValue(AssignedType));
}
 
void SPIRVEmitIntrinsicsImpl::replacePointerOperandWithPtrCast(
    Instruction *I, Value *Pointer, Type *ExpectedElementType,
    unsigned OperandToReplace, IRBuilder<> &B) {
  TypeValidated.insert(I);
 
  // Do not emit spv_ptrcast if Pointer's element type is ExpectedElementType
  Type *PointerElemTy = deduceElementTypeHelper(Pointer, false);
  if (PointerElemTy == ExpectedElementType ||
      isEquivalentTypes(PointerElemTy, ExpectedElementType))
    return;
 
  setInsertPointSkippingPhis(B, I);
  Value *ExpectedElementVal = getNormalizedPoisonValue(ExpectedElementType);
  MetadataAsValue *VMD = buildMD(ExpectedElementVal);
  unsigned AddressSpace = getPointerAddressSpace(Pointer->getType());
  bool FirstPtrCastOrAssignPtrType = true;
 
  // Do not emit new spv_ptrcast if equivalent one already exists or when
  // spv_assign_ptr_type already targets this pointer with the same element
  // type.
  if (Pointer->hasUseList()) {
    for (auto User : Pointer->users()) {
      auto *II = dyn_cast<IntrinsicInst>(User);
      if (!II ||
          (II->getIntrinsicID() != Intrinsic::spv_assign_ptr_type &&
           II->getIntrinsicID() != Intrinsic::spv_ptrcast) ||
          II->getOperand(0) != Pointer)
        continue;
 
      // There is some spv_ptrcast/spv_assign_ptr_type already targeting this
      // pointer.
      FirstPtrCastOrAssignPtrType = false;
      if (II->getOperand(1) != VMD ||
          dyn_cast<ConstantInt>(II->getOperand(2))->getSExtValue() !=
              AddressSpace)
        continue;
 
      // The spv_ptrcast/spv_assign_ptr_type targeting this pointer is of the
      // same element type and address space.
      if (II->getIntrinsicID() != Intrinsic::spv_ptrcast)
        return;
 
      // This must be a spv_ptrcast, do not emit new if this one has the same BB
      // as I. Otherwise, search for other spv_ptrcast/spv_assign_ptr_type.
      if (II->getParent() != I->getParent())
        continue;
 
      I->setOperand(OperandToReplace, II);
      return;
    }
  }
 
  // Never replace an already-deduced pointer element type with a non-pointer
  // one. The conflicting use comes from a mis-deduced expected type. Leave the
  // operand untouched rather than emitting a ptrcast that re-introduces the
  // collapsed type at the use site.
  if (PointerElemTy && isPointerTyOrWrapper(PointerElemTy) &&
      !isPointerTyOrWrapper(ExpectedElementType) &&
      tracesToPointerAlloca(Pointer))
    return;
 
  if (isa<Instruction>(Pointer) || isa<Argument>(Pointer)) {
    if (FirstPtrCastOrAssignPtrType) {
      // If this would be the first spv_ptrcast, do not emit spv_ptrcast and
      // emit spv_assign_ptr_type instead.
      GR->buildAssignPtr(B, ExpectedElementType, Pointer);
      return;
    } else if (isTodoType(Pointer)) {
      eraseTodoType(Pointer);
      if (!isa<CallInst>(Pointer) && !isaGEP(Pointer) &&
          !isa<AllocaInst>(Pointer)) {
        //  If this wouldn't be the first spv_ptrcast but existing type info is
        //  uncomplete, update spv_assign_ptr_type arguments.
        if (CallInst *AssignCI = GR->findAssignPtrTypeInstr(Pointer)) {
          Type *PrevElemTy = GR->findDeducedElementType(Pointer);
          assert(PrevElemTy);
          DenseSet<std::pair<Value *, Value *>> VisitedSubst{
              std::make_pair(I, Pointer)};
          GR->updateAssignType(AssignCI, Pointer, ExpectedElementVal);
          propagateElemType(Pointer, PrevElemTy, VisitedSubst);
        } else {
          GR->buildAssignPtr(B, ExpectedElementType, Pointer);
        }
        return;
      }
    }
  }
 
  // Emit spv_ptrcast
  SmallVector<Type *, 2> Types = {Pointer->getType(), Pointer->getType()};
  SmallVector<Value *, 2> Args = {Pointer, VMD, B.getInt32(AddressSpace)};
  auto *PtrCastI = B.CreateIntrinsic(Intrinsic::spv_ptrcast, {Types}, Args);
  I->setOperand(OperandToReplace, PtrCastI);
  // We need to set up a pointee type for the newly created spv_ptrcast.
  GR->buildAssignPtr(B, ExpectedElementType, PtrCastI);
}
 
void SPIRVEmitIntrinsicsImpl::insertPtrCastOrAssignTypeInstr(Instruction *I,
                                                             IRBuilder<> &B) {
  // Handle basic instructions:
  StoreInst *SI = dyn_cast<StoreInst>(I);
  if (IsKernelArgInt8(CurrF, SI)) {
    replacePointerOperandWithPtrCast(
        I, SI->getValueOperand(), IntegerType::getInt8Ty(CurrF->getContext()),
        0, B);
  }
  if (SI) {
    Value *Op = SI->getValueOperand();
    Value *Pointer = SI->getPointerOperand();
    Type *OpTy = Op->getType();
    if (auto *OpI = dyn_cast<Instruction>(Op)) {
      OpTy = restoreMutatedType(GR, OpI, OpTy);
      if (auto It = AggrConstTypes.find(OpI); It != AggrConstTypes.end())
        OpTy = It->second;
    }
    if (OpTy == Op->getType())
      OpTy = deduceElementTypeByValueDeep(OpTy, Op, false);
    replacePointerOperandWithPtrCast(I, Pointer, OpTy, 1, B);
    return;
  }
  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
    Value *Pointer = LI->getPointerOperand();
    Type *OpTy = LI->getType();
    if (auto *PtrTy = dyn_cast<PointerType>(OpTy)) {
      if (Type *ElemTy = GR->findDeducedElementType(LI)) {
        OpTy = getTypedPointerWrapper(ElemTy, PtrTy->getAddressSpace());
      } else {
        Type *NewOpTy = OpTy;
        OpTy = deduceElementTypeByValueDeep(OpTy, LI, false);
        if (OpTy == NewOpTy)
          insertTodoType(Pointer);
      }
    }
    replacePointerOperandWithPtrCast(I, Pointer, OpTy, 0, B);
    return;
  }
  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
    Value *Pointer = GEPI->getPointerOperand();
    Type *OpTy = nullptr;
 
    // Logical SPIR-V is not allowed to use Op*PtrAccessChain instructions. If
    // the first index is 0, then we can trivially lower to OpAccessChain. If
    // not we need to try to rewrite the GEP. We avoid adding a pointer cast at
    // this time, and will rewrite the GEP when visiting it.
    if (TM.getSubtargetImpl()->isLogicalSPIRV() && !isFirstIndexZero(GEPI)) {
      return;
    }
 
    // In all cases, fall back to the GEP type if type scavenging failed.
    if (!OpTy)
      OpTy = GEPI->getSourceElementType();
 
    replacePointerOperandWithPtrCast(I, Pointer, OpTy, 0, B);
    if (isNestedPointer(OpTy))
      insertTodoType(Pointer);
    return;
  }
 
  // TODO: review and merge with existing logics:
  // Handle calls to builtins (non-intrinsics):
  CallInst *CI = dyn_cast<CallInst>(I);
  if (!CI || CI->isIndirectCall() || CI->isInlineAsm() ||
      !CI->getCalledFunction() || CI->getCalledFunction()->isIntrinsic())
    return;
 
  // collect information about formal parameter types
  std::string DemangledName =
      getOclOrSpirvBuiltinDemangledName(CI->getCalledFunction()->getName());
  Function *CalledF = CI->getCalledFunction();
  SmallVector<Type *, 4> CalledArgTys;
  bool HaveTypes = false;
  for (unsigned OpIdx = 0; OpIdx < CalledF->arg_size(); ++OpIdx) {
    Argument *CalledArg = CalledF->getArg(OpIdx);
    Type *ArgType = CalledArg->getType();
    if (!isPointerTy(ArgType)) {
      CalledArgTys.push_back(nullptr);
    } else if (Type *ArgTypeElem = getPointeeType(ArgType)) {
      CalledArgTys.push_back(ArgTypeElem);
      HaveTypes = true;
    } else {
      Type *ElemTy = GR->findDeducedElementType(CalledArg);
      if (!ElemTy && hasPointeeTypeAttr(CalledArg))
        ElemTy = getPointeeTypeByAttr(CalledArg);
      if (!ElemTy) {
        ElemTy = getPointeeTypeByCallInst(DemangledName, CalledF, OpIdx);
        if (ElemTy) {
          GR->addDeducedElementType(CalledArg, normalizeType(ElemTy));
        } else {
          for (User *U : CalledArg->users()) {
            if (Instruction *Inst = dyn_cast<Instruction>(U)) {
              if ((ElemTy = deduceElementTypeHelper(Inst, false)) != nullptr)
                break;
            }
          }
        }
      }
      HaveTypes |= ElemTy != nullptr;
      CalledArgTys.push_back(ElemTy);
    }
  }
 
  if (DemangledName.empty() && !HaveTypes)
    return;
 
  for (unsigned OpIdx = 0; OpIdx < CI->arg_size(); OpIdx++) {
    Value *ArgOperand = CI->getArgOperand(OpIdx);
    if (!isPointerTy(ArgOperand->getType()))
      continue;
 
    // Constants (nulls/undefs) are handled in insertAssignPtrTypeIntrs()
    if (!isa<Instruction>(ArgOperand) && !isa<Argument>(ArgOperand)) {
      // However, we may have assumptions about the formal argument's type and
      // may have a need to insert a ptr cast for the actual parameter of this
      // call.
      Argument *CalledArg = CalledF->getArg(OpIdx);
      if (!GR->findDeducedElementType(CalledArg))
        continue;
    }
 
    Type *ExpectedType =
        OpIdx < CalledArgTys.size() ? CalledArgTys[OpIdx] : nullptr;
    if (!ExpectedType && !DemangledName.empty())
      ExpectedType = SPIRV::parseBuiltinCallArgumentBaseType(
          DemangledName, OpIdx, I->getContext());
    if (!ExpectedType || ExpectedType->isVoidTy())
      continue;
 
    if (ExpectedType->isTargetExtTy() &&
        !isTypedPointerWrapper(cast<TargetExtType>(ExpectedType)))
      insertAssignPtrTypeTargetExt(cast<TargetExtType>(ExpectedType),
                                   ArgOperand, B);
    else
      replacePointerOperandWithPtrCast(CI, ArgOperand, ExpectedType, OpIdx, B);
  }
}
 
Instruction *
SPIRVEmitIntrinsicsImpl::visitInsertElementInst(InsertElementInst &I) {
  // If it's a <1 x Type> vector type, don't modify it. It's not a legal vector
  // type in LLT and IRTranslator will replace it by the scalar.
  if (isVector1(I.getType()))
    return &I;
 
  SmallVector<Type *, 4> Types = {I.getType(), I.getOperand(0)->getType(),
                                  I.getOperand(1)->getType(),
                                  I.getOperand(2)->getType()};
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  SmallVector<Value *> Args(I.op_begin(), I.op_end());
  Instruction *NewI = B.CreateIntrinsicWithoutFolding(Intrinsic::spv_insertelt,
                                                      {Types}, {Args});
  replaceAllUsesWithAndErase(B, &I, NewI);
  return NewI;
}
 
Instruction *
SPIRVEmitIntrinsicsImpl::visitExtractElementInst(ExtractElementInst &I) {
  // If it's a <1 x Type> vector type, don't modify it. It's not a legal vector
  // type in LLT and IRTranslator will replace it by the scalar.
  if (isVector1(I.getVectorOperandType()))
    return &I;
 
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  SmallVector<Type *, 3> Types = {I.getType(), I.getVectorOperandType(),
                                  I.getIndexOperand()->getType()};
  SmallVector<Value *, 2> Args = {I.getVectorOperand(), I.getIndexOperand()};
  Instruction *NewI = B.CreateIntrinsicWithoutFolding(Intrinsic::spv_extractelt,
                                                      {Types}, {Args});
  replaceAllUsesWithAndErase(B, &I, NewI);
  return NewI;
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitInsertValueInst(InsertValueInst &I) {
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  SmallVector<Type *, 1> Types = {I.getInsertedValueOperand()->getType()};
  SmallVector<Value *> Args;
  Value *AggregateOp = I.getAggregateOperand();
  if (isa<UndefValue>(AggregateOp))
    Args.push_back(UndefValue::get(B.getInt32Ty()));
  else
    Args.push_back(AggregateOp);
  Args.push_back(I.getInsertedValueOperand());
  for (auto &Op : I.indices())
    Args.push_back(B.getInt32(Op));
  Instruction *NewI =
      B.CreateIntrinsicWithoutFolding(Intrinsic::spv_insertv, {Types}, {Args});
  replaceMemInstrUses(&I, NewI, B);
  return NewI;
}
 
Instruction *
SPIRVEmitIntrinsicsImpl::visitExtractValueInst(ExtractValueInst &I) {
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  if (I.getAggregateOperand()->getType()->isAggregateType()) {
    // Mutate an aggregate-returning spv_extractv producer to i32 so
    // IRTranslator does not see a multi-register value.
    CallBase *CB = dyn_cast<CallBase>(I.getAggregateOperand());
    if (!CB || CB->getIntrinsicID() != Intrinsic::spv_extractv)
      return &I;
    CB->mutateType(B.getInt32Ty());
  }
  SmallVector<Value *> Args(I.operands());
  for (auto &Op : I.indices())
    Args.push_back(B.getInt32(Op));
  Instruction *NewI = B.CreateIntrinsicWithoutFolding(Intrinsic::spv_extractv,
                                                      {I.getType()}, {Args});
  // If this aggregate extract feeds another insertvalue, the extracted
  // composite is used as a SPIR-V value-id by llvm.spv.insertv. Keep the real
  // aggregate type in metadata, but expose the value itself as i32 so the
  // intrinsic signature remains valid.
  if (NewI->getType()->isAggregateType() &&
      any_of(I.users(), [](User *U) { return isa<InsertValueInst>(U); })) {
    AggrConstTypes[NewI] = I.getType();
    NewI->mutateType(B.getInt32Ty());
    replaceMemInstrUses(&I, NewI, B);
    return NewI;
  }
  replaceAllUsesWithAndErase(B, &I, NewI);
  // If the aggregate result feeds a return or callsite whose type was rewritten
  // to an i32 value-id by SPIRVPrepareFunctions, mutate it to match.
  if (NewI->getType()->isAggregateType()) {
    for (const Use &U : NewI->uses()) {
      User *Usr = U.getUser();
      if (auto *RI = dyn_cast<ReturnInst>(Usr)) {
        if (RI->getFunction()->getReturnType() != NewI->getType()) {
          NewI->mutateType(B.getInt32Ty());
          break;
        }
        continue;
      }
      auto *CB = dyn_cast<CallBase>(Usr);
      if (!CB || !CB->isArgOperand(&U))
        continue;
      unsigned ArgNo = CB->getArgOperandNo(&U);
      FunctionType *FT = CB->getFunctionType();
      if (ArgNo < FT->getNumParams() &&
          !FT->getParamType(ArgNo)->isAggregateType()) {
        NewI->mutateType(B.getInt32Ty());
        break;
      }
    }
  }
  return NewI;
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitLoadInst(LoadInst &I) {
  if (!I.getType()->isAggregateType())
    return &I;
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  TrackConstants = false;
  const auto *TLI = TM.getSubtargetImpl()->getTargetLowering();
  MachineMemOperand::Flags Flags =
      TLI->getLoadMemOperandFlags(I, CurrF->getDataLayout());
 
  unsigned IntrinsicId;
  SmallVector<Value *, 4> Args = {I.getPointerOperand(), B.getInt16(Flags)};
  if (!I.isAtomic()) {
    IntrinsicId = Intrinsic::spv_load;
    Args.push_back(B.getInt32(I.getAlign().value()));
  } else {
    IntrinsicId = Intrinsic::spv_atomic_load;
    Args.push_back(B.getInt8(static_cast<uint8_t>(I.getOrdering())));
  }
  CallInst *NewI = B.CreateIntrinsicWithoutFolding(
      IntrinsicId, {I.getOperand(0)->getType()}, Args);
 
  replaceMemInstrUses(&I, NewI, B);
  return NewI;
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitStoreInst(StoreInst &I) {
  if (!AggrStores.contains(&I))
    return &I;
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  TrackConstants = false;
  const auto *TLI = TM.getSubtargetImpl()->getTargetLowering();
  MachineMemOperand::Flags Flags =
      TLI->getStoreMemOperandFlags(I, CurrF->getDataLayout());
  auto *PtrOp = I.getPointerOperand();
 
  if (I.getValueOperand()->getType()->isAggregateType()) {
    // It is possible that what used to be an ExtractValueInst has been replaced
    // with a call to the spv_extractv intrinsic, and that said call hasn't
    // had its return type replaced with i32 during the dedicated pass (because
    // it was emitted later); we have to handle this here, because IRTranslator
    // cannot deal with multi-register types at the moment.
    CallBase *CB = dyn_cast<CallBase>(I.getValueOperand());
    assert(CB && CB->getIntrinsicID() == Intrinsic::spv_extractv &&
           "Unexpected argument of aggregate type, should be spv_extractv!");
    CB->mutateType(B.getInt32Ty());
  }
 
  unsigned IntrinsicId;
  SmallVector<Value *, 4> Args = {I.getValueOperand(), PtrOp,
                                  B.getInt16(Flags)};
  if (!I.isAtomic()) {
    IntrinsicId = Intrinsic::spv_store;
    Args.push_back(B.getInt32(I.getAlign().value()));
  } else {
    IntrinsicId = Intrinsic::spv_atomic_store;
    Args.push_back(B.getInt8(static_cast<uint8_t>(I.getOrdering())));
  }
  Instruction *NewI = B.CreateIntrinsicWithoutFolding(
      IntrinsicId, {I.getValueOperand()->getType(), PtrOp->getType()}, Args);
  NewI->copyMetadata(I);
  I.eraseFromParent();
  return NewI;
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitAllocaInst(AllocaInst &I) {
  Value *ArraySize = nullptr;
  if (I.isArrayAllocation()) {
    const SPIRVSubtarget *STI = TM.getSubtargetImpl(*I.getFunction());
    if (!STI->canUseExtension(
            SPIRV::Extension::SPV_INTEL_variable_length_array))
      report_fatal_error(
          "array allocation: this instruction requires the following "
          "SPIR-V extension: SPV_INTEL_variable_length_array",
          false);
    ArraySize = I.getArraySize();
  }
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  TrackConstants = false;
  Type *PtrTy = I.getType();
  Instruction *NewI =
      ArraySize
          ? B.CreateIntrinsicWithoutFolding(
                Intrinsic::spv_alloca_array, {PtrTy, ArraySize->getType()},
                {ArraySize, B.getInt32(I.getAlign().value())})
          : B.CreateIntrinsicWithoutFolding(Intrinsic::spv_alloca, {PtrTy},
                                            {B.getInt32(I.getAlign().value())});
  replaceAllUsesWithAndErase(B, &I, NewI);
  return NewI;
}
 
Instruction *
SPIRVEmitIntrinsicsImpl::visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) {
  assert(I.getType()->isAggregateType() && "Aggregate result is expected");
  IRBuilder<> B(I.getParent());
  B.SetInsertPoint(&I);
  SmallVector<Value *> Args(I.operands());
  Args.push_back(B.getInt32(static_cast<uint32_t>(
      getMemScope(TM.getTargetTriple(), I.getContext(), I.getSyncScopeID()))));
  // Per SPIR-V spec atomic ops must combine the ordering bits with the
  // storage-class bit.
  const SPIRVSubtarget &ST = TM.getSubtarget<SPIRVSubtarget>(*I.getFunction());
  unsigned AS = I.getPointerOperand()->getType()->getPointerAddressSpace();
  uint32_t ScSem = static_cast<uint32_t>(
      getMemSemanticsForStorageClass(addressSpaceToStorageClass(AS, ST)));
  Args.push_back(B.getInt32(
      static_cast<uint32_t>(getMemSemantics(I.getSuccessOrdering())) | ScSem));
  Args.push_back(B.getInt32(
      static_cast<uint32_t>(getMemSemantics(I.getFailureOrdering())) | ScSem));
  Instruction *NewI = B.CreateIntrinsicWithoutFolding(
      Intrinsic::spv_cmpxchg, {I.getPointerOperand()->getType()}, {Args});
  replaceMemInstrUses(&I, NewI, B);
  return NewI;
}
 
static bool isAbortCall(const Instruction &I, const SPIRVSubtarget &ST) {
  auto *CI = dyn_cast<CallInst>(&I);
  if (!CI)
    return false;
  switch (CI->getIntrinsicID()) {
  case Intrinsic::spv_abort:
    return true;
  case Intrinsic::trap:
  case Intrinsic::ubsantrap:
    // When the extension is enabled, selection lowers these to OpAbortKHR.
    return ST.canUseExtension(SPIRV::Extension::SPV_KHR_abort);
  default:
    return false;
  }
}
 
// The OpAbortKHR instruction itself is a block terminator, so we don't need to
// emit an extra OpUnreachable instruction.
static bool precededByAbortIntrinsic(const UnreachableInst &I,
                                     const SPIRVSubtarget &ST) {
  // Find a previous non-debug instruction.
  const Instruction *Prev = I.getPrevNode();
  while (Prev && Prev->isDebugOrPseudoInst())
    Prev = Prev->getPrevNode();
 
  if (Prev && isAbortCall(*Prev, ST))
    return true;
 
  assert(llvm::none_of(
             *I.getParent(),
             [&ST](const Instruction &II) { return isAbortCall(II, ST); }) &&
         "abort-like call must be the last non-debug instruction before its "
         "block's terminator");
  return false;
}
 
Instruction *SPIRVEmitIntrinsicsImpl::visitUnreachableInst(UnreachableInst &I) {
  const SPIRVSubtarget &ST = TM.getSubtarget<SPIRVSubtarget>(*I.getFunction());
  if (precededByAbortIntrinsic(I, ST))
    return &I;
  IRBuilder<> B(&I);
  B.CreateIntrinsic(Intrinsic::spv_unreachable, {});
  return &I;
}
 
// llvm.compiler.used and llvm.used hold use-list entries that protect their
// referenced globals from DCE without participating in code generation.
static bool isUseListGlobal(StringRef Name) {
  return Name == "llvm.compiler.used" || Name == "llvm.used";
}
 
// Returns true for module-level globals that should not have SPIR-V intrinsics
// emitted (use-list globals plus llvm.global.annotations).
static bool isArtificialGlobal(StringRef Name) {
  return isUseListGlobal(Name) || Name == "llvm.global.annotations";
}
 
// Returns true if every use of GV traces back to llvm.compiler.used or
// llvm.used.
static bool hasOnlyArtificialUses(const GlobalVariable &GV) {
  SmallPtrSet<const Value *, 8> Visited;
  SmallVector<const Value *> Stack(GV.users());
  while (!Stack.empty()) {
    const Value *V = Stack.pop_back_val();
    if (!Visited.insert(V).second)
      continue;
    if (const auto *GVUser = dyn_cast<GlobalVariable>(V)) {
      if (!isUseListGlobal(GVUser->getName()))
        return false;
      continue;
    }
    if (const auto *C = dyn_cast<Constant>(V)) {
      Stack.append(C->user_begin(), C->user_end());
      continue;
    }
    return false;
  }
  return true;
}
 
static bool
shouldEmitIntrinsicsForGlobalValue(const GlobalVariableUsers &GVUsers,
                                   const GlobalVariable &GV,
                                   const Function *F) {
  // Skip special artificial variables.
  if (isArtificialGlobal(GV.getName()))
    return false;
 
  auto &UserFunctions = GVUsers.getTransitiveUserFunctions(GV);
  if (UserFunctions.contains(F))
    return true;
 
  // Do not emit the intrinsics in this function, it's going to be emitted on
  // the functions that reference it.
  if (!UserFunctions.empty())
    return false;
 
  // Emit definitions for globals that are not referenced by any function on the
  // first function definition.
  const Module &M = *F->getParent();
  const Function &FirstDefinition = *M.getFunctionDefs().begin();
  return F == &FirstDefinition;
}
 
Value *SPIRVEmitIntrinsicsImpl::buildSpvUndefComposite(Type *AggrTy,
                                                       IRBuilder<> &B) {
  auto MakeLeaf = [&](Type *ElemTy) -> Instruction * {
    CallInst *Leaf = B.CreateIntrinsicWithoutFolding(Intrinsic::spv_undef, {});
    AggrConsts[Leaf] = PoisonValue::get(ElemTy);
    AggrConstTypes[Leaf] = ElemTy;
    return Leaf;
  };
  SmallVector<Value *, 4> Elems;
  if (auto *ArrTy = dyn_cast<ArrayType>(AggrTy)) {
    Elems.assign(ArrTy->getNumElements(), MakeLeaf(ArrTy->getElementType()));
  } else {
    auto *StructTy = cast<StructType>(AggrTy);
    DenseMap<Type *, Instruction *> LeafByType;
    for (unsigned I = 0; I < StructTy->getNumElements(); ++I) {
      Type *ElemTy = StructTy->getContainedType(I);
      auto &Entry = LeafByType[ElemTy];
      if (!Entry)
        Entry = MakeLeaf(ElemTy);
      Elems.push_back(Entry);
    }
  }
  CallInst *Composite = B.CreateIntrinsicWithoutFolding(
      Intrinsic::spv_const_composite, {B.getInt32Ty()}, Elems);
  AggrConsts[Composite] = PoisonValue::get(AggrTy);
  AggrConstTypes[Composite] = AggrTy;
  return Composite;
}
 
// If a function directly returns an aggregate-typed call result,
// the ReturnInst carries an aggregate while the function signature
// was rewritten to i32 by SPIRVPrepareFunctions. Rebuild the return value
// via extractvalue/insertvalue so the regular spv_extractv/spv_insertv
// lowering produces a valid OpReturnValue.
void SPIRVEmitIntrinsicsImpl::reconstructAggregateReturns(Function &Func,
                                                          IRBuilder<> &B) {
  Type *OrigRetTy = GR->findMutated(&Func);
  if (!OrigRetTy || !OrigRetTy->isAggregateType())
    return;
  for (BasicBlock &BB : Func) {
    auto *RI = dyn_cast<ReturnInst>(BB.getTerminator());
    if (!RI)
      continue;
    Value *RetVal = RI->getReturnValue();
    if (!RetVal || RetVal->getType() != OrigRetTy || !isa<CallBase>(RetVal))
      continue;
    Type *AggrTy = RetVal->getType();
    uint64_t NumElts = isa<StructType>(AggrTy)
                           ? cast<StructType>(AggrTy)->getNumElements()
                           : cast<ArrayType>(AggrTy)->getNumElements();
    B.SetInsertPoint(RI);
    Value *Rebuilt = PoisonValue::get(AggrTy);
    for (uint64_t I = 0; I < NumElts; ++I) {
      Value *Elt = B.CreateExtractValue(RetVal, I);
      Rebuilt = B.CreateInsertValue(Rebuilt, Elt, I);
    }
    RI->setOperand(0, Rebuilt);
  }
}
 
void SPIRVEmitIntrinsicsImpl::processGlobalValue(GlobalVariable &GV,
                                                 IRBuilder<> &B) {
 
  if (!shouldEmitIntrinsicsForGlobalValue(GVUsers, GV, CurrF))
    return;
 
  // Record the pointee type for every global, not only initialized ones, so an
  // undef non-constant aggregate global is not later collapsed to its element
  // type. Result is ignored, because TypedPointerType is not supported
  // by llvm IR general logic.
  deduceElementTypeHelper(&GV, false);
 
  Constant *Init = nullptr;
  if (hasInitializer(&GV)) {
    Init = GV.getInitializer();
    Value *InitOp = Init;
    if (isa<UndefValue>(Init) && Init->getType()->isAggregateType()) {
      const SPIRVSubtarget *STI = TM.getSubtargetImpl();
      bool UsePoison =
          isa<PoisonValue>(Init) &&
          STI->canUseExtension(SPIRV::Extension::SPV_KHR_poison_freeze);
      if (UsePoison) {
        CallInst *Call = B.CreateIntrinsicWithoutFolding(Intrinsic::spv_poison,
                                                         {B.getInt32Ty()}, {});
        AggrConsts[Call] = cast<PoisonValue>(Init);
        AggrConstTypes[Call] = Init->getType();
        InitOp = Call;
      } else {
        InitOp = buildSpvUndefComposite(Init->getType(), B);
      }
    }
    Type *Ty = isAggrConstForceInt32(Init) ? B.getInt32Ty() : Init->getType();
    Constant *Const = isAggrConstForceInt32(Init) ? B.getInt32(1) : Init;
    CallInst *InitInst = B.CreateIntrinsicWithoutFolding(
        Intrinsic::spv_init_global, {GV.getType(), Ty}, {&GV, Const});
    InitInst->setArgOperand(1, InitOp);
  }
  // Globals with only use-list references have no real function uses. Emit
  // spv_unref_global so buildGlobalVariable is called for them.
  if (!Init && hasOnlyArtificialUses(GV))
    B.CreateIntrinsic(Intrinsic::spv_unref_global, GV.getType(), &GV);
}
 
// Return true, if we can't decide what is the pointee type now and will get
// back to the question later. Return false is spv_assign_ptr_type is not needed
// or can be inserted immediately.
bool SPIRVEmitIntrinsicsImpl::insertAssignPtrTypeIntrs(Instruction *I,
                                                       IRBuilder<> &B,
                                                       bool UnknownElemTypeI8) {
  reportFatalOnTokenType(I);
  if (!isPointerTy(I->getType()) || !requireAssignType(I))
    return false;
 
  setInsertPointAfterDef(B, I);
  if (Type *ElemTy = deduceElementType(I, UnknownElemTypeI8)) {
    GR->buildAssignPtr(B, ElemTy, I);
    return false;
  }
  return true;
}
 
void SPIRVEmitIntrinsicsImpl::insertAssignTypeIntrs(Instruction *I,
                                                    IRBuilder<> &B) {
  // TODO: extend the list of functions with known result types
  static StringMap<unsigned> ResTypeWellKnown = {
      {"async_work_group_copy", WellKnownTypes::Event},
      {"async_work_group_strided_copy", WellKnownTypes::Event},
      {"__spirv_GroupAsyncCopy", WellKnownTypes::Event}};
 
  reportFatalOnTokenType(I);
 
  bool IsKnown = false;
  if (auto *CI = dyn_cast<CallInst>(I)) {
    if (!CI->isIndirectCall() && !CI->isInlineAsm() &&
        CI->getCalledFunction() && !CI->getCalledFunction()->isIntrinsic()) {
      Function *CalledF = CI->getCalledFunction();
      std::string DemangledName =
          getOclOrSpirvBuiltinDemangledName(CalledF->getName());
      FPDecorationId DecorationId = FPDecorationId::NONE;
      if (DemangledName.length() > 0)
        DemangledName =
            SPIRV::lookupBuiltinNameHelper(DemangledName, &DecorationId);
      auto ResIt = ResTypeWellKnown.find(DemangledName);
      if (ResIt != ResTypeWellKnown.end()) {
        IsKnown = true;
        setInsertPointAfterDef(B, I);
        switch (ResIt->second) {
        case WellKnownTypes::Event:
          GR->buildAssignType(
              B, TargetExtType::get(I->getContext(), "spirv.Event"), I);
          break;
        }
      }
      // check if a floating rounding mode or saturation info is present
      switch (DecorationId) {
      default:
        break;
      case FPDecorationId::SAT:
        createSaturatedConversionDecoration(CI, B);
        break;
      case FPDecorationId::RTE:
        createRoundingModeDecoration(
            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTE, B);
        break;
      case FPDecorationId::RTZ:
        createRoundingModeDecoration(
            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTZ, B);
        break;
      case FPDecorationId::RTP:
        createRoundingModeDecoration(
            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTP, B);
        break;
      case FPDecorationId::RTN:
        createRoundingModeDecoration(
            CI, SPIRV::FPRoundingMode::FPRoundingMode::RTN, B);
        break;
      }
    }
  }
 
  Type *Ty = I->getType();
  if (!IsKnown && !Ty->isVoidTy() && !isPointerTy(Ty) && requireAssignType(I)) {
    setInsertPointAfterDef(B, I);
    Type *TypeToAssign = Ty;
    if (auto *II = dyn_cast<IntrinsicInst>(I)) {
      if (isSpvAggrPlaceholder(II)) {
        auto It = AggrConstTypes.find(II);
        if (It == AggrConstTypes.end())
          report_fatal_error("Unknown composite intrinsic type");
        TypeToAssign = It->second;
      } else if (II->getIntrinsicID() == Intrinsic::spv_poison) {
        if (auto It = AggrConstTypes.find(II); It != AggrConstTypes.end())
          TypeToAssign = It->second;
      }
    } else if (auto It = AggrConstTypes.find(I); It != AggrConstTypes.end())
      TypeToAssign = It->second;
    TypeToAssign = restoreMutatedType(GR, I, TypeToAssign);
    GR->buildAssignType(B, TypeToAssign, I);
  }
  for (const auto &Op : I->operands()) {
    if (isa<ConstantPointerNull>(Op) || isa<UndefValue>(Op) ||
        // Check GetElementPtrConstantExpr case.
        (isa<ConstantExpr>(Op) &&
         (isa<GEPOperator>(Op) ||
          (cast<ConstantExpr>(Op)->getOpcode() == CastInst::IntToPtr)))) {
      setInsertPointSkippingPhis(B, I);
      Type *OpTy = Op->getType();
      if (isa<UndefValue>(Op) && OpTy->isAggregateType()) {
        CallInst *AssignCI =
            buildIntrWithMD(Intrinsic::spv_assign_type, {B.getInt32Ty()}, Op,
                            UndefValue::get(B.getInt32Ty()), {}, B);
        GR->addAssignPtrTypeInstr(Op, AssignCI);
      } else if (!isa<Instruction>(Op)) {
        Type *OpTy = Op->getType();
        Type *OpTyElem = getPointeeType(OpTy);
        if (OpTyElem) {
          GR->buildAssignPtr(B, OpTyElem, Op);
        } else if (isPointerTy(OpTy)) {
          Type *ElemTy = GR->findDeducedElementType(Op);
          GR->buildAssignPtr(B, ElemTy ? ElemTy : deduceElementType(Op, true),
                             Op);
        } else {
          Value *OpTyVal = Op;
          if (OpTy->isTargetExtTy()) {
            // We need to do this in order to be consistent with how target ext
            // types are handled in `processInstrAfterVisit`
            OpTyVal = getNormalizedPoisonValue(OpTy);
          }
          CallInst *AssignCI =
              buildIntrWithMD(Intrinsic::spv_assign_type, {OpTy},
                              getNormalizedPoisonValue(OpTy), OpTyVal, {}, B);
          GR->addAssignPtrTypeInstr(OpTyVal, AssignCI);
        }
      }
    }
  }
}
 
bool SPIRVEmitIntrinsicsImpl::shouldTryToAddMemAliasingDecoration(
    Instruction *Inst) {
  const SPIRVSubtarget *STI = TM.getSubtargetImpl(*Inst->getFunction());
  if (!STI->canUseExtension(SPIRV::Extension::SPV_INTEL_memory_access_aliasing))
    return false;
  // Add aliasing decorations to internal load and store intrinsics.
  // Do not attach them to store atomic or load atomic intrinsics / instructions
  // since the extension is inconsistent at the moment (we cannot add the
  // decoration to atomic stores because they do not have an id).
  return match(Inst,
               m_AnyIntrinsic<Intrinsic::spv_load, Intrinsic::spv_store>());
}
 
void SPIRVEmitIntrinsicsImpl::insertSpirvDecorations(Instruction *I,
                                                     IRBuilder<> &B) {
  if (MDNode *MD = I->getMetadata("spirv.Decorations")) {
    setInsertPointAfterDef(B, I);
    B.CreateIntrinsic(Intrinsic::spv_assign_decoration, {I->getType()},
                      {I, MetadataAsValue::get(I->getContext(), MD)});
  }
  // Lower alias.scope/noalias metadata
  {
    auto processMemAliasingDecoration = [&](unsigned Kind) {
      if (MDNode *AliasListMD = I->getMetadata(Kind)) {
        if (shouldTryToAddMemAliasingDecoration(I)) {
          uint32_t Dec = Kind == LLVMContext::MD_alias_scope
                             ? SPIRV::Decoration::AliasScopeINTEL
                             : SPIRV::Decoration::NoAliasINTEL;
          SmallVector<Value *, 3> Args = {
              I, ConstantInt::get(B.getInt32Ty(), Dec),
              MetadataAsValue::get(I->getContext(), AliasListMD)};
          setInsertPointAfterDef(B, I);
          B.CreateIntrinsic(Intrinsic::spv_assign_aliasing_decoration,
                            {I->getType()}, {Args});
        }
      }
    };
    processMemAliasingDecoration(LLVMContext::MD_alias_scope);
    processMemAliasingDecoration(LLVMContext::MD_noalias);
  }
  // MD_fpmath
  if (MDNode *MD = I->getMetadata(LLVMContext::MD_fpmath)) {
    const SPIRVSubtarget *STI = TM.getSubtargetImpl(*I->getFunction());
    bool AllowFPMaxError =
        STI->canUseExtension(SPIRV::Extension::SPV_INTEL_fp_max_error);
    if (!AllowFPMaxError)
      return;
 
    setInsertPointAfterDef(B, I);
    B.CreateIntrinsic(Intrinsic::spv_assign_fpmaxerror_decoration,
                      {I->getType()},
                      {I, MetadataAsValue::get(I->getContext(), MD)});
  }
  if (I->getModule()->getTargetTriple().getVendor() == Triple::AMD &&
      isa<AtomicRMWInst>(I)) {
    // If present, we encode AMDGPU atomic metadata as UserSemantic string
    // decorations, which will be parsed during reverse translation.
    auto &Ctx = B.getContext();
    auto *US = ConstantAsMetadata::get(
        ConstantInt::get(B.getInt32Ty(), SPIRV::Decoration::UserSemantic));
 
    SmallVector<Metadata *> MDs;
    if (I->hasMetadata("amdgpu.no.fine.grained.memory"))
      MDs.push_back(MDNode::get(
          Ctx, {US, MDString::get(Ctx, "amdgpu.no.fine.grained.memory")}));
    if (I->hasMetadata("amdgpu.no.remote.memory"))
      MDs.push_back(MDNode::get(
          Ctx, {US, MDString::get(Ctx, "amdgpu.no.remote.memory")}));
    if (I->hasMetadata("amdgpu.ignore.denormal.mode"))
      MDs.push_back(MDNode::get(
          Ctx, {US, MDString::get(Ctx, "amdgpu.ignore.denormal.mode")}));
    if (!MDs.empty())
      B.CreateIntrinsic(Intrinsic::spv_assign_decoration, {I->getType()},
                        {I, MetadataAsValue::get(Ctx, MDNode::get(Ctx, MDs))});
  }
}
 
static SPIRV::FPFastMathDefaultInfoVector &getOrCreateFPFastMathDefaultInfoVec(
    const Module &M,
    DenseMap<Function *, SPIRV::FPFastMathDefaultInfoVector>
        &FPFastMathDefaultInfoMap,
    Function *F) {
  auto it = FPFastMathDefaultInfoMap.find(F);
  if (it != FPFastMathDefaultInfoMap.end())
    return it->second;
 
  // If the map does not contain the entry, create a new one. Initialize it to
  // contain all 3 elements sorted by bit width of target type: {half, float,
  // double}.
  SPIRV::FPFastMathDefaultInfoVector FPFastMathDefaultInfoVec;
  FPFastMathDefaultInfoVec.emplace_back(Type::getHalfTy(M.getContext()),
                                        SPIRV::FPFastMathMode::None);
  FPFastMathDefaultInfoVec.emplace_back(Type::getFloatTy(M.getContext()),
                                        SPIRV::FPFastMathMode::None);
  FPFastMathDefaultInfoVec.emplace_back(Type::getDoubleTy(M.getContext()),
                                        SPIRV::FPFastMathMode::None);
  return FPFastMathDefaultInfoMap[F] = std::move(FPFastMathDefaultInfoVec);
}
 
static SPIRV::FPFastMathDefaultInfo &getFPFastMathDefaultInfo(
    SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec,
    const Type *Ty) {
  size_t BitWidth = Ty->getScalarSizeInBits();
  int Index =
      SPIRV::FPFastMathDefaultInfoVector::computeFPFastMathDefaultInfoVecIndex(
          BitWidth);
  assert(Index >= 0 && Index < 3 &&
         "Expected FPFastMathDefaultInfo for half, float, or double");
  assert(FPFastMathDefaultInfoVec.size() == 3 &&
         "Expected FPFastMathDefaultInfoVec to have exactly 3 elements");
  return FPFastMathDefaultInfoVec[Index];
}
 
void SPIRVEmitIntrinsicsImpl::insertConstantsForFPFastMathDefault(Module &M) {
  const SPIRVSubtarget *ST = TM.getSubtargetImpl();
  if (!ST->canUseExtension(SPIRV::Extension::SPV_KHR_float_controls2))
    return;
 
  // Store the FPFastMathDefaultInfo in the FPFastMathDefaultInfoMap.
  // We need the entry point (function) as the key, and the target
  // type and flags as the value.
  // We also need to check ContractionOff and SignedZeroInfNanPreserve
  // execution modes, as they are now deprecated and must be replaced
  // with FPFastMathDefaultInfo.
  auto Node = M.getNamedMetadata("spirv.ExecutionMode");
  if (!Node) {
    if (!M.getNamedMetadata("opencl.enable.FP_CONTRACT")) {
      // This requires emitting ContractionOff. However, because
      // ContractionOff is now deprecated, we need to replace it with
      // FPFastMathDefaultInfo with FP Fast Math Mode bitmask set to all 0.
      // We need to create the constant for that.
 
      // Create constant instruction with the bitmask flags.
      Constant *InitValue =
          ConstantInt::get(Type::getInt32Ty(M.getContext()), 0);
      // TODO: Reuse constant if there is one already with the required
      // value.
      [[maybe_unused]] GlobalVariable *GV =
          new GlobalVariable(M,                                // Module
                             Type::getInt32Ty(M.getContext()), // Type
                             true,                             // isConstant
                             GlobalValue::InternalLinkage,     // Linkage
                             InitValue                         // Initializer
          );
    }
    return;
  }
 
  // The table maps function pointers to their default FP fast math info. It
  // can be assumed that the SmallVector is sorted by the bit width of the
  // type. The first element is the smallest bit width, and the last element
  // is the largest bit width, therefore, we will have {half, float, double}
  // in the order of their bit widths.
  DenseMap<Function *, SPIRV::FPFastMathDefaultInfoVector>
      FPFastMathDefaultInfoMap;
 
  for (unsigned i = 0; i < Node->getNumOperands(); i++) {
    MDNode *MDN = cast<MDNode>(Node->getOperand(i));
    assert(MDN->getNumOperands() >= 2 && "Expected at least 2 operands");
    Function *F = cast<Function>(
        cast<ConstantAsMetadata>(MDN->getOperand(0))->getValue());
    const auto EM =
        cast<ConstantInt>(
            cast<ConstantAsMetadata>(MDN->getOperand(1))->getValue())
            ->getZExtValue();
    if (EM == SPIRV::ExecutionMode::FPFastMathDefault) {
      assert(MDN->getNumOperands() == 4 &&
             "Expected 4 operands for FPFastMathDefault");
      const Type *T = cast<ValueAsMetadata>(MDN->getOperand(2))->getType();
      unsigned Flags =
          cast<ConstantInt>(
              cast<ConstantAsMetadata>(MDN->getOperand(3))->getValue())
              ->getZExtValue();
      SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec =
          getOrCreateFPFastMathDefaultInfoVec(M, FPFastMathDefaultInfoMap, F);
      SPIRV::FPFastMathDefaultInfo &Info =
          getFPFastMathDefaultInfo(FPFastMathDefaultInfoVec, T);
      Info.FastMathFlags = Flags;
      Info.FPFastMathDefault = true;
    } else if (EM == SPIRV::ExecutionMode::ContractionOff) {
      assert(MDN->getNumOperands() == 2 &&
             "Expected no operands for ContractionOff");
 
      // We need to save this info for every possible FP type, i.e. {half,
      // float, double, fp128}.
      SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec =
          getOrCreateFPFastMathDefaultInfoVec(M, FPFastMathDefaultInfoMap, F);
      for (SPIRV::FPFastMathDefaultInfo &Info : FPFastMathDefaultInfoVec) {
        Info.ContractionOff = true;
      }
    } else if (EM == SPIRV::ExecutionMode::SignedZeroInfNanPreserve) {
      assert(MDN->getNumOperands() == 3 &&
             "Expected 1 operand for SignedZeroInfNanPreserve");
      unsigned TargetWidth =
          cast<ConstantInt>(
              cast<ConstantAsMetadata>(MDN->getOperand(2))->getValue())
              ->getZExtValue();
      // We need to save this info only for the FP type with TargetWidth.
      SPIRV::FPFastMathDefaultInfoVector &FPFastMathDefaultInfoVec =
          getOrCreateFPFastMathDefaultInfoVec(M, FPFastMathDefaultInfoMap, F);
      int Index = SPIRV::FPFastMathDefaultInfoVector::
          computeFPFastMathDefaultInfoVecIndex(TargetWidth);
      assert(Index >= 0 && Index < 3 &&
             "Expected FPFastMathDefaultInfo for half, float, or double");
      assert(FPFastMathDefaultInfoVec.size() == 3 &&
             "Expected FPFastMathDefaultInfoVec to have exactly 3 elements");
      FPFastMathDefaultInfoVec[Index].SignedZeroInfNanPreserve = true;
    }
  }
 
  DenseMap<unsigned, GlobalVariable *> GlobalVars;
  for (auto &[Func, FPFastMathDefaultInfoVec] : FPFastMathDefaultInfoMap) {
    if (FPFastMathDefaultInfoVec.empty())
      continue;
 
    for (const SPIRV::FPFastMathDefaultInfo &Info : FPFastMathDefaultInfoVec) {
      assert(Info.Ty && "Expected target type for FPFastMathDefaultInfo");
      // Skip if none of the execution modes was used.
      unsigned Flags = Info.FastMathFlags;
      if (Flags == SPIRV::FPFastMathMode::None && !Info.ContractionOff &&
          !Info.SignedZeroInfNanPreserve && !Info.FPFastMathDefault)
        continue;
 
      // Check if flags are compatible.
      if (Info.ContractionOff && (Flags & SPIRV::FPFastMathMode::AllowContract))
        report_fatal_error("Conflicting FPFastMathFlags: ContractionOff "
                           "and AllowContract");
 
      if (Info.SignedZeroInfNanPreserve &&
          !(Flags &
            (SPIRV::FPFastMathMode::NotNaN | SPIRV::FPFastMathMode::NotInf |
             SPIRV::FPFastMathMode::NSZ))) {
        if (Info.FPFastMathDefault)
          report_fatal_error("Conflicting FPFastMathFlags: "
                             "SignedZeroInfNanPreserve but at least one of "
                             "NotNaN/NotInf/NSZ is enabled.");
      }
 
      if ((Flags & SPIRV::FPFastMathMode::AllowTransform) &&
          !((Flags & SPIRV::FPFastMathMode::AllowReassoc) &&
            (Flags & SPIRV::FPFastMathMode::AllowContract))) {
        report_fatal_error("Conflicting FPFastMathFlags: "
                           "AllowTransform requires AllowReassoc and "
                           "AllowContract to be set.");
      }
 
      auto it = GlobalVars.find(Flags);
      GlobalVariable *GV = nullptr;
      if (it != GlobalVars.end()) {
        // Reuse existing global variable.
        GV = it->second;
      } else {
        // Create constant instruction with the bitmask flags.
        Constant *InitValue =
            ConstantInt::get(Type::getInt32Ty(M.getContext()), Flags);
        // TODO: Reuse constant if there is one already with the required
        // value.
        GV = new GlobalVariable(M,                                // Module
                                Type::getInt32Ty(M.getContext()), // Type
                                true,                             // isConstant
                                GlobalValue::InternalLinkage,     // Linkage
                                InitValue                         // Initializer
        );
        GlobalVars[Flags] = GV;
      }
    }
  }
}
 
void SPIRVEmitIntrinsicsImpl::processInstrAfterVisit(Instruction *I,
                                                     IRBuilder<> &B) {
  auto *II = dyn_cast<IntrinsicInst>(I);
  bool IsConstComposite =
      II && II->getIntrinsicID() == Intrinsic::spv_const_composite;
  if (IsConstComposite && TrackConstants) {
    setInsertPointAfterDef(B, I);
    auto t = AggrConsts.find(I);
    assert(t != AggrConsts.end());
    auto *NewOp =
        buildIntrWithMD(Intrinsic::spv_track_constant,
                        {II->getType(), II->getType()}, t->second, I, {}, B);
    replaceAllUsesWith(I, NewOp, false);
    NewOp->setArgOperand(0, I);
  }
  bool IsPhi = isa<PHINode>(I), BPrepared = false;
  for (const auto &Op : I->operands()) {
    if (isa<PHINode>(I) || isa<SwitchInst>(I) ||
        !(isa<ConstantData>(Op) || isa<ConstantExpr>(Op)))
      continue;
    unsigned OpNo = Op.getOperandNo();
    if (II && ((II->getIntrinsicID() == Intrinsic::spv_gep && OpNo == 0) ||
               (!II->isBundleOperand(OpNo) &&
                II->paramHasAttr(OpNo, Attribute::ImmArg))))
      continue;
 
    if (!BPrepared) {
      IsPhi ? B.SetInsertPointPastAllocas(I->getParent()->getParent())
            : B.SetInsertPoint(I);
      BPrepared = true;
    }
    Type *OpTy = Op->getType();
    Type *OpElemTy = GR->findDeducedElementType(Op);
    Value *NewOp = Op;
    if (OpTy->isTargetExtTy()) {
      // Since this value is replaced by poison, we need to do the same in
      // `insertAssignTypeIntrs`.
      Value *OpTyVal = getNormalizedPoisonValue(OpTy);
      NewOp = buildIntrWithMD(Intrinsic::spv_track_constant,
                              {OpTy, OpTyVal->getType()}, Op, OpTyVal, {}, B);
    }
    if (!IsConstComposite && isPointerTy(OpTy) && OpElemTy != nullptr &&
        OpElemTy != IntegerType::getInt8Ty(I->getContext())) {
      SmallVector<Type *, 2> Types = {OpTy, OpTy};
      SmallVector<Value *, 2> Args = {
          NewOp, buildMD(getNormalizedPoisonValue(OpElemTy)),
          B.getInt32(getPointerAddressSpace(OpTy))};
      CallInst *PtrCasted = B.CreateIntrinsicWithoutFolding(
          Intrinsic::spv_ptrcast, {Types}, Args);
      GR->buildAssignPtr(B, OpElemTy, PtrCasted);
      NewOp = PtrCasted;
    }
    if (NewOp != Op)
      I->setOperand(OpNo, NewOp);
  }
  if (Named.insert(I).second)
    emitAssignName(I, B);
}
 
Type *SPIRVEmitIntrinsicsImpl::deduceFunParamElementType(Function *F,
                                                         unsigned OpIdx) {
  SmallPtrSet<Function *, 0> FVisited;
  return deduceFunParamElementType(F, OpIdx, FVisited);
}
 
Type *SPIRVEmitIntrinsicsImpl::deduceFunParamElementType(
    Function *F, unsigned OpIdx, SmallPtrSetImpl<Function *> &FVisited) {
  // maybe a cycle
  if (!FVisited.insert(F).second)
    return nullptr;
 
  SmallPtrSet<Value *, 0> Visited;
  SmallVector<std::pair<Function *, unsigned>> Lookup;
  // search in function's call sites
  for (User *U : F->users()) {
    CallInst *CI = dyn_cast<CallInst>(U);
    if (!CI || OpIdx >= CI->arg_size())
      continue;
    Value *OpArg = CI->getArgOperand(OpIdx);
    if (!isPointerTy(OpArg->getType()))
      continue;
    // maybe we already know operand's element type
    if (Type *KnownTy = GR->findDeducedElementType(OpArg))
      return KnownTy;
    // try to deduce from the operand itself
    Visited.clear();
    if (Type *Ty = deduceElementTypeHelper(OpArg, Visited, false))
      return Ty;
    // search in actual parameter's users
    for (User *OpU : OpArg->users()) {
      Instruction *Inst = dyn_cast<Instruction>(OpU);
      if (!Inst || Inst == CI)
        continue;
      Visited.clear();
      if (Type *Ty = deduceElementTypeHelper(Inst, Visited, false))
        return Ty;
    }
    // check if it's a formal parameter of the outer function
    if (!CI->getParent() || !CI->getParent()->getParent())
      continue;
    Function *OuterF = CI->getParent()->getParent();
    if (FVisited.find(OuterF) != FVisited.end())
      continue;
    for (unsigned i = 0; i < OuterF->arg_size(); ++i) {
      if (OuterF->getArg(i) == OpArg) {
        Lookup.push_back(std::make_pair(OuterF, i));
        break;
      }
    }
  }
 
  // search in function parameters
  for (auto &Pair : Lookup) {
    if (Type *Ty = deduceFunParamElementType(Pair.first, Pair.second, FVisited))
      return Ty;
  }
 
  return nullptr;
}
 
void SPIRVEmitIntrinsicsImpl::processParamTypesByFunHeader(Function *F,
                                                           IRBuilder<> &B) {
  B.SetInsertPointPastAllocas(F);
  for (unsigned OpIdx = 0; OpIdx < F->arg_size(); ++OpIdx) {
    Argument *Arg = F->getArg(OpIdx);
    // Vector-of-pointers arg: deduce pointee from a GEP user so the function
    // type isn't emitted with the default i8 pointee.
    if (isUntypedPointerVectorTy(Arg->getType()) &&
        !GR->findDeducedElementType(Arg)) {
      for (User *U : Arg->users()) {
        auto *GEP = dyn_cast<GetElementPtrInst>(U);
        if (GEP && GEP->getPointerOperand() == Arg) {
          GR->buildAssignPtr(B, GEP->getSourceElementType(), Arg);
          break;
        }
      }
      continue;
    }
    if (!isUntypedPointerTy(Arg->getType()))
      continue;
    Type *ElemTy = GR->findDeducedElementType(Arg);
    if (ElemTy)
      continue;
    if (hasPointeeTypeAttr(Arg) &&
        (ElemTy = getPointeeTypeByAttr(Arg)) != nullptr) {
      GR->buildAssignPtr(B, ElemTy, Arg);
      continue;
    }
    // search in function's call sites
    for (User *U : F->users()) {
      CallInst *CI = dyn_cast<CallInst>(U);
      if (!CI || OpIdx >= CI->arg_size())
        continue;
      Value *OpArg = CI->getArgOperand(OpIdx);
      if (!isPointerTy(OpArg->getType()))
        continue;
      // maybe we already know operand's element type
      if ((ElemTy = GR->findDeducedElementType(OpArg)) != nullptr)
        break;
    }
    if (ElemTy) {
      GR->buildAssignPtr(B, ElemTy, Arg);
      continue;
    }
    if (HaveFunPtrs) {
      for (User *U : Arg->users()) {
        CallInst *CI = dyn_cast<CallInst>(U);
        if (CI && !isa<IntrinsicInst>(CI) && CI->isIndirectCall() &&
            CI->getCalledOperand() == Arg &&
            CI->getParent()->getParent() == CurrF) {
          SmallVector<std::pair<Value *, unsigned>> Ops;
          deduceOperandElementTypeFunctionPointer(CI, Ops, ElemTy, false);
          if (ElemTy) {
            GR->buildAssignPtr(B, ElemTy, Arg);
            break;
          }
        }
      }
    }
  }
}
 
void SPIRVEmitIntrinsicsImpl::processParamTypes(Function *F, IRBuilder<> &B) {
  B.SetInsertPointPastAllocas(F);
  for (unsigned OpIdx = 0; OpIdx < F->arg_size(); ++OpIdx) {
    Argument *Arg = F->getArg(OpIdx);
    if (!isUntypedPointerTy(Arg->getType()))
      continue;
    Type *ElemTy = GR->findDeducedElementType(Arg);
    if (!ElemTy && (ElemTy = deduceFunParamElementType(F, OpIdx)) != nullptr) {
      if (CallInst *AssignCI = GR->findAssignPtrTypeInstr(Arg)) {
        DenseSet<std::pair<Value *, Value *>> VisitedSubst;
        GR->updateAssignType(AssignCI, Arg, getNormalizedPoisonValue(ElemTy));
        propagateElemType(Arg, IntegerType::getInt8Ty(F->getContext()),
                          VisitedSubst);
      } else {
        GR->buildAssignPtr(B, ElemTy, Arg);
      }
    }
  }
}
 
static FunctionType *getFunctionPointerElemType(Function *F,
                                                SPIRVGlobalRegistry *GR) {
  FunctionType *FTy = F->getFunctionType();
  bool IsNewFTy = false;
  SmallVector<Type *, 4> ArgTys;
  for (Argument &Arg : F->args()) {
    Type *ArgTy = Arg.getType();
    if (ArgTy->isPointerTy())
      if (Type *ElemTy = GR->findDeducedElementType(&Arg)) {
        IsNewFTy = true;
        ArgTy = getTypedPointerWrapper(ElemTy, getPointerAddressSpace(ArgTy));
      }
    ArgTys.push_back(ArgTy);
  }
  return IsNewFTy
             ? FunctionType::get(FTy->getReturnType(), ArgTys, FTy->isVarArg())
             : FTy;
}
 
bool SPIRVEmitIntrinsicsImpl::processFunctionPointers(Module &M) {
  SmallVector<Function *> Worklist;
  for (auto &F : M) {
    if (F.isIntrinsic())
      continue;
    if (F.isDeclaration()) {
      for (User *U : F.users()) {
        CallInst *CI = dyn_cast<CallInst>(U);
        if (!CI || CI->getCalledFunction() != &F) {
          Worklist.push_back(&F);
          break;
        }
      }
    } else {
      if (F.user_empty())
        continue;
      Type *FPElemTy = GR->findDeducedElementType(&F);
      if (!FPElemTy)
        FPElemTy = getFunctionPointerElemType(&F, GR);
      for (User *U : F.users()) {
        IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
        if (!II || II->arg_size() != 3 || II->getOperand(0) != &F)
          continue;
        if (II->getIntrinsicID() == Intrinsic::spv_assign_ptr_type ||
            II->getIntrinsicID() == Intrinsic::spv_ptrcast) {
          GR->updateAssignType(II, &F, getNormalizedPoisonValue(FPElemTy));
          break;
        }
      }
    }
  }
  if (Worklist.empty())
    return false;
 
  LLVMContext &Ctx = M.getContext();
  Function *SF = getOrCreateBackendServiceFunction(M);
  BasicBlock *BB = BasicBlock::Create(Ctx, "entry", SF);
  IRBuilder<> IRB(BB);
 
  for (Function *F : Worklist) {
    SmallVector<Value *> Args;
    for (const auto &Arg : F->args())
      Args.push_back(getNormalizedPoisonValue(Arg.getType()));
    IRB.CreateCall(F, Args);
  }
  IRB.CreateRetVoid();
 
  return true;
}
 
// Apply types parsed from demangled function declarations.
void SPIRVEmitIntrinsicsImpl::applyDemangledPtrArgTypes(IRBuilder<> &B) {
  DenseMap<Function *, CallInst *> Ptrcasts;
  for (auto It : FDeclPtrTys) {
    Function *F = It.first;
    for (auto *U : F->users()) {
      CallInst *CI = dyn_cast<CallInst>(U);
      if (!CI || CI->getCalledFunction() != F)
        continue;
      unsigned Sz = CI->arg_size();
      for (auto [Idx, ElemTy] : It.second) {
        if (Idx >= Sz)
          continue;
        Value *Param = CI->getArgOperand(Idx);
        if (GR->findDeducedElementType(Param) || isa<GlobalValue>(Param))
          continue;
        if (Argument *Arg = dyn_cast<Argument>(Param)) {
          if (!hasPointeeTypeAttr(Arg)) {
            B.SetInsertPointPastAllocas(Arg->getParent());
            B.SetCurrentDebugLocation(DebugLoc());
            GR->buildAssignPtr(B, ElemTy, Arg);
          }
        } else if (isaGEP(Param)) {
          replaceUsesOfWithSpvPtrcast(Param, normalizeType(ElemTy), CI,
                                      Ptrcasts);
        } else if (isa<Instruction>(Param)) {
          GR->addDeducedElementType(Param, normalizeType(ElemTy));
          // insertAssignTypeIntrs() will complete buildAssignPtr()
        } else {
          B.SetInsertPoint(CI->getParent()
                               ->getParent()
                               ->getEntryBlock()
                               .getFirstNonPHIOrDbgOrAlloca());
          GR->buildAssignPtr(B, ElemTy, Param);
        }
        CallInst *Ref = dyn_cast<CallInst>(Param);
        if (!Ref)
          continue;
        Function *RefF = Ref->getCalledFunction();
        if (!RefF || !isPointerTy(RefF->getReturnType()) ||
            GR->findDeducedElementType(RefF))
          continue;
        ElemTy = normalizeType(ElemTy);
        GR->addDeducedElementType(RefF, ElemTy);
        GR->addReturnType(
            RefF, TypedPointerType::get(
                      ElemTy, getPointerAddressSpace(RefF->getReturnType())));
      }
    }
  }
}
 
GetElementPtrInst *SPIRVEmitIntrinsicsImpl::simplifyZeroLengthArrayGepInst(
    GetElementPtrInst *GEP) {
  // getelementptr [0 x T], P, 0 (zero), I -> getelementptr T, P, I.
  // If type is 0-length array and first index is 0 (zero), drop both the
  // 0-length array type and the first index. This is a common pattern in
  // the IR, e.g. when using a zero-length array as a placeholder for a
  // flexible array such as unbound arrays.
  assert(GEP && "GEP is null");
  Type *SrcTy = GEP->getSourceElementType();
  SmallVector<Value *, 8> Indices(GEP->indices());
  ArrayType *ArrTy = dyn_cast<ArrayType>(SrcTy);
  if (ArrTy && ArrTy->getNumElements() == 0 && match(Indices[0], m_Zero())) {
    Indices.erase(Indices.begin());
    SrcTy = ArrTy->getElementType();
    return GetElementPtrInst::Create(SrcTy, GEP->getPointerOperand(), Indices,
                                     GEP->getNoWrapFlags(), "",
                                     GEP->getIterator());
  }
  return nullptr;
}
 
void SPIRVEmitIntrinsicsImpl::emitUnstructuredLoopControls(Function &F,
                                                           IRBuilder<> &B) {
  const SPIRVSubtarget *ST = TM.getSubtargetImpl(F);
  // Shaders use SPIRVStructurizer which emits OpLoopMerge via spv_loop_merge.
  if (ST->isShader())
    return;
 
  if (ST->canUseExtension(
          SPIRV::Extension::SPV_INTEL_unstructured_loop_controls)) {
    for (BasicBlock &BB : F) {
      Instruction *Term = BB.getTerminator();
      MDNode *LoopMD = Term->getMetadata(LLVMContext::MD_loop);
      if (!LoopMD)
        continue;
 
      SmallVector<unsigned, 1> Ops =
          getSpirvLoopControlOperandsFromLoopMetadata(LoopMD);
      unsigned LC = Ops[0];
      if (LC == SPIRV::LoopControl::None)
        continue;
 
      // Emit intrinsic: loop control mask + optional parameters.
      B.SetInsertPoint(Term);
      SmallVector<Value *, 4> IntrArgs;
      for (unsigned Op : Ops)
        IntrArgs.push_back(B.getInt32(Op));
      B.CreateIntrinsic(Intrinsic::spv_loop_control_intel, IntrArgs);
    }
    return;
  }
 
  // For non-shader targets without the Intel extension, emit OpLoopMerge
  // using spv_loop_merge intrinsics, mirroring the structurizer approach.
  LoopInfo LI;
  LI.analyze(&F);
  if (LI.empty())
    return;
 
  for (Loop *L : LI.getLoopsInPreorder()) {
    BasicBlock *Latch = L->getLoopLatch();
    if (!Latch)
      continue;
    BasicBlock *MergeBlock = L->getUniqueExitBlock();
    if (!MergeBlock)
      continue;
 
    // Check for loop unroll metadata on the latch terminator.
    SmallVector<unsigned, 1> LoopControlOps =
        getSpirvLoopControlOperandsFromLoopMetadata(L);
    if (LoopControlOps[0] == SPIRV::LoopControl::None)
      continue;
 
    BasicBlock *Header = L->getHeader();
    B.SetInsertPoint(Header->getTerminator());
    auto *MergeAddress = BlockAddress::get(&F, MergeBlock);
    auto *ContinueAddress = BlockAddress::get(&F, Latch);
    SmallVector<Value *, 4> Args = {MergeAddress, ContinueAddress};
    for (unsigned Imm : LoopControlOps)
      Args.emplace_back(B.getInt32(Imm));
    B.CreateIntrinsic(Intrinsic::spv_loop_merge, {Args});
  }
}
 
bool SPIRVEmitIntrinsicsImpl::runOnFunction(Function &Func) {
  if (Func.isDeclaration())
    return false;
 
  const SPIRVSubtarget &ST = TM.getSubtarget<SPIRVSubtarget>(Func);
  GR = ST.getSPIRVGlobalRegistry();
 
  if (!CurrF)
    HaveFunPtrs =
        ST.canUseExtension(SPIRV::Extension::SPV_INTEL_function_pointers);
 
  CurrF = &Func;
  IRBuilder<> B(Func.getContext());
  AggrConsts.clear();
  AggrConstTypes.clear();
  AggrStores.clear();
 
  processParamTypesByFunHeader(CurrF, B);
 
  // Fix GEP result types ahead of inference, and simplify if possible.
  // Data structure for dead instructions that were simplified and replaced.
  SmallPtrSet<Instruction *, 4> DeadInsts;
  for (auto &I : instructions(Func)) {
    if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
      Type *ElTy = SI->getValueOperand()->getType();
      if (ElTy->isAggregateType() || ElTy->isVectorTy())
        AggrStores.insert(&I);
      continue;
    }
 
    auto *GEP = dyn_cast<GetElementPtrInst>(&I);
    auto *SGEP = dyn_cast<StructuredGEPInst>(&I);
 
    if ((!GEP && !SGEP) || GR->findDeducedElementType(&I))
      continue;
 
    if (SGEP) {
      GR->addDeducedElementType(SGEP,
                                normalizeType(SGEP->getResultElementType()));
      continue;
    }
 
    GetElementPtrInst *NewGEP = simplifyZeroLengthArrayGepInst(GEP);
    if (NewGEP) {
      GEP->replaceAllUsesWith(NewGEP);
      DeadInsts.insert(GEP);
      GEP = NewGEP;
    }
    if (Type *GepTy = getGEPType(GEP))
      GR->addDeducedElementType(GEP, normalizeType(GepTy));
  }
  // Remove dead instructions that were simplified and replaced.
  for (auto *I : DeadInsts) {
    assert(I->use_empty() && "Dead instruction should not have any uses left");
    I->eraseFromParent();
  }
 
  B.SetInsertPoint(&Func.getEntryBlock(), Func.getEntryBlock().begin());
  for (auto &GV : Func.getParent()->globals())
    processGlobalValue(GV, B);
 
  reconstructAggregateReturns(Func, B);
  preprocessUndefsAndPoisons(B);
  simplifyNullAddrSpaceCasts();
  preprocessCompositeConstants(B);
 
  // A PHINode, SelectInst or FreezeInst takes its result type from its
  // operands. Aggregate arms are lowered to i32 value-ids (composite constants
  // here, loads and other producers during the visitor pass below), so mutate
  // an aggregate PHI, select or freeze to match. The original type is tracked
  // in AggrConstTypes (used to assign the SPIR-V type) and its extractvalue
  // users are lowered to spv_extractv.
  Type *I32Ty = B.getInt32Ty();
  for (Instruction &I : instructions(Func)) {
    if (!isAggregateValueIdInstr(I))
      continue;
    // Give multi-register arms a value-id first, before the result is mutated.
    insertCompositeAggregateArms(&I, B);
    AggrConstTypes[&I] = I.getType();
    I.mutateType(I32Ty);
  }
 
  preprocessBoolVectorBitcasts(Func);
  SmallVector<Instruction *> Worklist(
      llvm::make_pointer_range(instructions(Func)));
 
  applyDemangledPtrArgTypes(B);
 
  // Pass forward: use operand to deduce instructions result.
  for (auto &I : Worklist) {
    // Don't emit intrinsincs for convergence intrinsics.
    if (isConvergenceIntrinsic(I))
      continue;
 
    bool Postpone = insertAssignPtrTypeIntrs(I, B, false);
    // if Postpone is true, we can't decide on pointee type yet
    insertAssignTypeIntrs(I, B);
    insertPtrCastOrAssignTypeInstr(I, B);
    insertSpirvDecorations(I, B);
    // if instruction requires a pointee type set, let's check if we know it
    // already, and force it to be i8 if not
    if (Postpone && !GR->findAssignPtrTypeInstr(I))
      insertAssignPtrTypeIntrs(I, B, true);
 
    if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I))
      useRoundingMode(FPI, B);
  }
 
  // Pass backward: use instructions results to specify/update/cast operands
  // where needed.
  SmallPtrSet<Instruction *, 4> IncompleteRets;
  for (auto &I : llvm::reverse(instructions(Func)))
    deduceOperandElementType(&I, &IncompleteRets);
 
  // Pass forward for PHIs only, their operands are not preceed the
  // instruction in meaning of `instructions(Func)`.
  for (BasicBlock &BB : Func)
    for (PHINode &Phi : BB.phis())
      if (isPointerTy(Phi.getType()))
        deduceOperandElementType(&Phi, nullptr);
 
  for (auto *I : Worklist) {
    TrackConstants = true;
    if (!I->getType()->isVoidTy() || isa<StoreInst>(I))
      setInsertPointAfterDef(B, I);
    // Visitors return either the original/newly created instruction for
    // further processing, nullptr otherwise.
    I = visit(*I);
    if (!I)
      continue;
 
    // Don't emit intrinsics for convergence operations.
    if (isConvergenceIntrinsic(I))
      continue;
 
    addSaturatedDecorationToIntrinsic(I, B);
    processInstrAfterVisit(I, B);
  }
 
  emitUnstructuredLoopControls(Func, B);
 
  return true;
}
 
// Try to deduce a better type for pointers to untyped ptr.
bool SPIRVEmitIntrinsicsImpl::postprocessTypes(Module &M) {
  if (!GR || TodoTypeSz == 0)
    return false;
 
  unsigned SzTodo = TodoTypeSz;
  DenseMap<Value *, SmallPtrSet<Value *, 4>> ToProcess;
  for (auto [Op, Enabled] : TodoType) {
    // TODO: add isa<CallInst>(Op) to continue
    if (!Enabled || isaGEP(Op))
      continue;
    CallInst *AssignCI = GR->findAssignPtrTypeInstr(Op);
    Type *KnownTy = GR->findDeducedElementType(Op);
    if (!KnownTy || !AssignCI)
      continue;
    assert(Op == AssignCI->getArgOperand(0));
    // Try to improve the type deduced after all Functions are processed.
    if (auto *CI = dyn_cast<Instruction>(Op)) {
      CurrF = CI->getParent()->getParent();
      SmallPtrSet<Value *, 0> Visited;
      if (Type *ElemTy = deduceElementTypeHelper(Op, Visited, false, true)) {
        if (ElemTy != KnownTy) {
          DenseSet<std::pair<Value *, Value *>> VisitedSubst;
          propagateElemType(CI, ElemTy, VisitedSubst);
          eraseTodoType(Op);
          continue;
        }
      }
    }
 
    if (Op->hasUseList()) {
      for (User *U : Op->users()) {
        Instruction *Inst = dyn_cast<Instruction>(U);
        if (Inst && !isa<IntrinsicInst>(Inst))
          ToProcess[Inst].insert(Op);
      }
    }
  }
  if (TodoTypeSz == 0)
    return true;
 
  for (auto &F : M) {
    CurrF = &F;
    SmallPtrSet<Instruction *, 4> IncompleteRets;
    for (auto &I : llvm::reverse(instructions(F))) {
      auto It = ToProcess.find(&I);
      if (It == ToProcess.end())
        continue;
      It->second.remove_if([this](Value *V) { return !isTodoType(V); });
      if (It->second.size() == 0)
        continue;
      deduceOperandElementType(&I, &IncompleteRets, &It->second, true);
      if (TodoTypeSz == 0)
        return true;
    }
  }
 
  return SzTodo > TodoTypeSz;
}
 
// Parse and store argument types of function declarations where needed.
void SPIRVEmitIntrinsicsImpl::parseFunDeclarations(Module &M) {
  for (auto &F : M) {
    if (!F.isDeclaration() || F.isIntrinsic())
      continue;
    // get the demangled name
    std::string DemangledName = getOclOrSpirvBuiltinDemangledName(F.getName());
    if (DemangledName.empty())
      continue;
    // allow only OpGroupAsyncCopy use case at the moment
    const SPIRVSubtarget &ST = TM.getSubtarget<SPIRVSubtarget>(F);
    auto [Grp, Opcode, ExtNo] = SPIRV::mapBuiltinToOpcode(
        DemangledName, ST.getPreferredInstructionSet());
    if (Opcode != SPIRV::OpGroupAsyncCopy)
      continue;
    // find pointer arguments
    SmallVector<unsigned> Idxs;
    for (unsigned OpIdx = 0; OpIdx < F.arg_size(); ++OpIdx) {
      Argument *Arg = F.getArg(OpIdx);
      if (isPointerTy(Arg->getType()) && !hasPointeeTypeAttr(Arg))
        Idxs.push_back(OpIdx);
    }
    if (!Idxs.size())
      continue;
    // parse function arguments
    LLVMContext &Ctx = F.getContext();
    SmallVector<StringRef, 10> TypeStrs;
    SPIRV::parseBuiltinTypeStr(TypeStrs, DemangledName, Ctx);
    if (!TypeStrs.size())
      continue;
    // find type info for pointer arguments
    for (unsigned Idx : Idxs) {
      if (Idx >= TypeStrs.size())
        continue;
      if (Type *ElemTy =
              SPIRV::parseBuiltinCallArgumentType(TypeStrs[Idx].trim(), Ctx))
        if (TypedPointerType::isValidElementType(ElemTy) &&
            !ElemTy->isTargetExtTy())
          FDeclPtrTys[&F].push_back(std::make_pair(Idx, ElemTy));
    }
  }
}
 
bool SPIRVEmitIntrinsicsImpl::processMaskedMemIntrinsic(IntrinsicInst &I) {
  const SPIRVSubtarget &ST = TM.getSubtarget<SPIRVSubtarget>(*I.getFunction());
 
  if (I.getIntrinsicID() == Intrinsic::masked_gather) {
    if (!ST.canUseExtension(
            SPIRV::Extension::SPV_INTEL_masked_gather_scatter)) {
      I.getContext().emitError(
          &I, "llvm.masked.gather requires SPV_INTEL_masked_gather_scatter "
              "extension");
      // Replace with poison to allow compilation to continue and report error.
      I.replaceAllUsesWith(PoisonValue::get(I.getType()));
      I.eraseFromParent();
      return true;
    }
 
    IRBuilder<> B(&I);
 
    Value *Ptrs = I.getArgOperand(0);
    Value *Mask = I.getArgOperand(1);
    Value *Passthru = I.getArgOperand(2);
 
    // Alignment is stored as a parameter attribute, not as a regular parameter.
    uint32_t Alignment = I.getParamAlign(0).valueOrOne().value();
 
    SmallVector<Value *, 4> Args = {Ptrs, B.getInt32(Alignment), Mask,
                                    Passthru};
    SmallVector<Type *, 4> Types = {I.getType(), Ptrs->getType(),
                                    Mask->getType(), Passthru->getType()};
 
    auto *NewI = B.CreateIntrinsic(Intrinsic::spv_masked_gather, Types, Args);
    I.replaceAllUsesWith(NewI);
    I.eraseFromParent();
    return true;
  }
 
  if (I.getIntrinsicID() == Intrinsic::masked_scatter) {
    if (!ST.canUseExtension(
            SPIRV::Extension::SPV_INTEL_masked_gather_scatter)) {
      I.getContext().emitError(
          &I, "llvm.masked.scatter requires SPV_INTEL_masked_gather_scatter "
              "extension");
      // Erase the intrinsic to allow compilation to continue and report error.
      I.eraseFromParent();
      return true;
    }
 
    IRBuilder<> B(&I);
 
    Value *Values = I.getArgOperand(0);
    Value *Ptrs = I.getArgOperand(1);
    Value *Mask = I.getArgOperand(2);
 
    // Alignment is stored as a parameter attribute on the ptrs parameter (arg
    // 1).
    uint32_t Alignment = I.getParamAlign(1).valueOrOne().value();
 
    SmallVector<Value *, 4> Args = {Values, Ptrs, B.getInt32(Alignment), Mask};
    SmallVector<Type *, 3> Types = {Values->getType(), Ptrs->getType(),
                                    Mask->getType()};
 
    B.CreateIntrinsic(Intrinsic::spv_masked_scatter, Types, Args);
    I.eraseFromParent();
    return true;
  }
 
  return false;
}
 
// SPIR-V doesn't support bitcasts involving vector boolean type. Decompose such
// bitcasts into element-wise operations before building instructions
// worklist, so new instructions are properly visited and converted to
// SPIR-V intrinsics.
void SPIRVEmitIntrinsicsImpl::preprocessBoolVectorBitcasts(Function &F) {
  struct BoolVecBitcast {
    BitCastInst *BC;
    FixedVectorType *BoolVecTy;
    bool SrcIsBoolVec;
  };
 
  auto getAsBoolVec = [](Type *Ty) -> FixedVectorType * {
    auto *VTy = dyn_cast<FixedVectorType>(Ty);
    return (VTy && VTy->getElementType()->isIntegerTy(1)) ? VTy : nullptr;
  };
 
  SmallVector<BoolVecBitcast, 4> ToReplace;
  for (auto &I : instructions(F)) {
    auto *BC = dyn_cast<BitCastInst>(&I);
    if (!BC)
      continue;
    if (auto *BVTy = getAsBoolVec(BC->getSrcTy()))
      ToReplace.push_back({BC, BVTy, true});
    else if (auto *BVTy = getAsBoolVec(BC->getDestTy()))
      ToReplace.push_back({BC, BVTy, false});
  }
 
  for (auto &[BC, BoolVecTy, SrcIsBoolVec] : ToReplace) {
    IRBuilder<> B(BC);
    Value *Src = BC->getOperand(0);
    unsigned BoolVecN = BoolVecTy->getNumElements();
    // Use iN as the scalar intermediate type for the bool vector side.
    Type *IntTy = B.getIntNTy(BoolVecN);
 
    // Convert source to scalar integer.
    Value *IntVal;
    if (SrcIsBoolVec) {
      // Extract each bool, zext, shift, and OR.
      IntVal = ConstantInt::get(IntTy, 0);
      for (unsigned I = 0; I < BoolVecN; ++I) {
        Value *Elem = B.CreateExtractElement(Src, B.getInt32(I));
        Value *Ext = B.CreateZExt(Elem, IntTy);
        if (I > 0)
          Ext = B.CreateShl(Ext, ConstantInt::get(IntTy, I));
        IntVal = B.CreateOr(IntVal, Ext);
      }
    } else {
      // Source is a non-bool type. If it's already a scalar integer, use it
      // directly, otherwise bitcast to iN first.
      IntVal = Src;
      if (!Src->getType()->isIntegerTy())
        IntVal = B.CreateBitCast(Src, IntTy);
    }
 
    // Convert scalar integer to destination type.
    Value *Result;
    if (!SrcIsBoolVec) {
      // Test each bit with AND + icmp.
      Result = PoisonValue::get(BoolVecTy);
      for (unsigned I = 0; I < BoolVecN; ++I) {
        Value *Mask = ConstantInt::get(IntTy, APInt::getOneBitSet(BoolVecN, I));
        Value *And = B.CreateAnd(IntVal, Mask);
        Value *Cmp = B.CreateICmpNE(And, ConstantInt::get(IntTy, 0));
        Result = B.CreateInsertElement(Result, Cmp, B.getInt32(I));
      }
    } else {
      // Destination is a non-bool type. If it's a scalar integer, use IntVal
      // directly, otherwise bitcast from iN.
      Result = IntVal;
      if (!BC->getDestTy()->isIntegerTy())
        Result = B.CreateBitCast(IntVal, BC->getDestTy());
    }
 
    BC->replaceAllUsesWith(Result);
    BC->eraseFromParent();
  }
}
 
bool SPIRVEmitIntrinsicsImpl::convertMaskedMemIntrinsics(Module &M) {
  bool Changed = false;
 
  for (Function &F : make_early_inc_range(M)) {
    if (!F.isIntrinsic())
      continue;
    Intrinsic::ID IID = F.getIntrinsicID();
    if (IID != Intrinsic::masked_gather && IID != Intrinsic::masked_scatter)
      continue;
 
    for (User *U : make_early_inc_range(F.users())) {
      if (auto *II = dyn_cast<IntrinsicInst>(U))
        Changed |= processMaskedMemIntrinsic(*II);
    }
 
    if (F.use_empty())
      F.eraseFromParent();
  }
 
  return Changed;
}
 
bool SPIRVEmitIntrinsicsImpl::runOnModule(Module &M) {
  bool Changed = false;
 
  Changed |= convertMaskedMemIntrinsics(M);
 
  parseFunDeclarations(M);
  insertConstantsForFPFastMathDefault(M);
  GVUsers.init(M);
 
  TodoType.clear();
  for (auto &F : M)
    Changed |= runOnFunction(F);
 
  // Specify function parameters after all functions were processed.
  for (auto &F : M) {
    // check if function parameter types are set
    CurrF = &F;
    if (!F.isDeclaration() && !F.isIntrinsic()) {
      IRBuilder<> B(F.getContext());
      processParamTypes(&F, B);
    }
  }
 
  CanTodoType = false;
  Changed |= postprocessTypes(M);
 
  if (HaveFunPtrs)
    Changed |= processFunctionPointers(M);
 
  return Changed;
}
 
PreservedAnalyses
llvm::SPIRVEmitIntrinsicsPass::run(Module &M, ModuleAnalysisManager &AM) {
  if (SPIRVEmitIntrinsicsImpl(TM).runOnModule(M))
    return PreservedAnalyses::none();
  return PreservedAnalyses::all();
}
 
ModulePass *llvm::createSPIRVEmitIntrinsicsPass(const SPIRVTargetMachine &TM) {
  return new SPIRVEmitIntrinsicsLegacy(TM);
}