BasicTTIImpl.h

Go to the documentation of this file.

//===- BasicTTIImpl.h -------------------------------------------*- 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
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file provides a helper that implements much of the TTI interface in
/// terms of the target-independent code generator and TargetLowering
/// interfaces.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CODEGEN_BASICTTIIMPL_H
#define LLVM_CODEGEN_BASICTTIIMPL_H
 
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/TargetTransformInfoImpl.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Alignment.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <optional>
#include <utility>
 
namespace llvm {
 
class Function;
class GlobalValue;
class LLVMContext;
class ScalarEvolution;
class SCEV;
class TargetMachine;
 
extern LLVM_ABI cl::opt<unsigned> PartialUnrollingThreshold;
 
/// Base class which can be used to help build a TTI implementation.
///
/// This class provides as much implementation of the TTI interface as is
/// possible using the target independent parts of the code generator.
///
/// In order to subclass it, your class must implement a getST() method to
/// return the subtarget, and a getTLI() method to return the target lowering.
/// We need these methods implemented in the derived class so that this class
/// doesn't have to duplicate storage for them.
template <typename T>
class BasicTTIImplBase : public TargetTransformInfoImplCRTPBase<T> {
private:
  using BaseT = TargetTransformInfoImplCRTPBase<T>;
  using TTI = TargetTransformInfo;
 
  /// Helper function to access this as a T.
  const T *thisT() const { return static_cast<const T *>(this); }
 
  /// Estimate a cost of Broadcast as an extract and sequence of insert
  /// operations.
  InstructionCost
  getBroadcastShuffleOverhead(FixedVectorType *VTy,
                              TTI::TargetCostKind CostKind) const {
    InstructionCost Cost = 0;
    // Broadcast cost is equal to the cost of extracting the zero'th element
    // plus the cost of inserting it into every element of the result vector.
    Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VTy,
                                        CostKind, 0, nullptr, nullptr);
 
    for (int i = 0, e = VTy->getNumElements(); i < e; ++i) {
      Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, VTy,
                                          CostKind, i, nullptr, nullptr);
    }
    return Cost;
  }
 
  /// Estimate a cost of shuffle as a sequence of extract and insert
  /// operations.
  InstructionCost
  getPermuteShuffleOverhead(FixedVectorType *VTy,
                            TTI::TargetCostKind CostKind) const {
    InstructionCost Cost = 0;
    // Shuffle cost is equal to the cost of extracting element from its argument
    // plus the cost of inserting them onto the result vector.
 
    // e.g. <4 x float> has a mask of <0,5,2,7> i.e we need to extract from
    // index 0 of first vector, index 1 of second vector,index 2 of first
    // vector and finally index 3 of second vector and insert them at index
    // <0,1,2,3> of result vector.
    for (int i = 0, e = VTy->getNumElements(); i < e; ++i) {
      Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, VTy,
                                          CostKind, i, nullptr, nullptr);
      Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VTy,
                                          CostKind, i, nullptr, nullptr);
    }
    return Cost;
  }
 
  /// Estimate a cost of subvector extraction as a sequence of extract and
  /// insert operations.
  InstructionCost getExtractSubvectorOverhead(VectorType *VTy,
                                              TTI::TargetCostKind CostKind,
                                              int Index,
                                              FixedVectorType *SubVTy) const {
    assert(VTy && SubVTy &&
           "Can only extract subvectors from vectors");
    int NumSubElts = SubVTy->getNumElements();
    assert((!isa<FixedVectorType>(VTy) ||
            (Index + NumSubElts) <=
                (int)cast<FixedVectorType>(VTy)->getNumElements()) &&
           "SK_ExtractSubvector index out of range");
 
    InstructionCost Cost = 0;
    // Subvector extraction cost is equal to the cost of extracting element from
    // the source type plus the cost of inserting them into the result vector
    // type.
    for (int i = 0; i != NumSubElts; ++i) {
      Cost +=
          thisT()->getVectorInstrCost(Instruction::ExtractElement, VTy,
                                      CostKind, i + Index, nullptr, nullptr);
      Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, SubVTy,
                                          CostKind, i, nullptr, nullptr);
    }
    return Cost;
  }
 
  /// Estimate a cost of subvector insertion as a sequence of extract and
  /// insert operations.
  InstructionCost getInsertSubvectorOverhead(VectorType *VTy,
                                             TTI::TargetCostKind CostKind,
                                             int Index,
                                             FixedVectorType *SubVTy) const {
    assert(VTy && SubVTy &&
           "Can only insert subvectors into vectors");
    int NumSubElts = SubVTy->getNumElements();
    assert((!isa<FixedVectorType>(VTy) ||
            (Index + NumSubElts) <=
                (int)cast<FixedVectorType>(VTy)->getNumElements()) &&
           "SK_InsertSubvector index out of range");
 
    InstructionCost Cost = 0;
    // Subvector insertion cost is equal to the cost of extracting element from
    // the source type plus the cost of inserting them into the result vector
    // type.
    for (int i = 0; i != NumSubElts; ++i) {
      Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, SubVTy,
                                          CostKind, i, nullptr, nullptr);
      Cost +=
          thisT()->getVectorInstrCost(Instruction::InsertElement, VTy, CostKind,
                                      i + Index, nullptr, nullptr);
    }
    return Cost;
  }
 
  /// Local query method delegates up to T which *must* implement this!
  const TargetSubtargetInfo *getST() const {
    return static_cast<const T *>(this)->getST();
  }
 
  /// Local query method delegates up to T which *must* implement this!
  const TargetLoweringBase *getTLI() const {
    return static_cast<const T *>(this)->getTLI();
  }
 
  static ISD::MemIndexedMode getISDIndexedMode(TTI::MemIndexedMode M) {
    switch (M) {
      case TTI::MIM_Unindexed:
        return ISD::UNINDEXED;
      case TTI::MIM_PreInc:
        return ISD::PRE_INC;
      case TTI::MIM_PreDec:
        return ISD::PRE_DEC;
      case TTI::MIM_PostInc:
        return ISD::POST_INC;
      case TTI::MIM_PostDec:
        return ISD::POST_DEC;
    }
    llvm_unreachable("Unexpected MemIndexedMode");
  }
 
  InstructionCost getCommonMaskedMemoryOpCost(unsigned Opcode, Type *DataTy,
                                              Align Alignment,
                                              bool VariableMask,
                                              bool IsGatherScatter,
                                              TTI::TargetCostKind CostKind,
                                              unsigned AddressSpace = 0) const {
    // We cannot scalarize scalable vectors, so return Invalid.
    if (isa<ScalableVectorType>(DataTy))
      return InstructionCost::getInvalid();
 
    auto *VT = cast<FixedVectorType>(DataTy);
    unsigned VF = VT->getNumElements();
 
    // Assume the target does not have support for gather/scatter operations
    // and provide a rough estimate.
    //
    // First, compute the cost of the individual memory operations.
    InstructionCost AddrExtractCost =
        IsGatherScatter ? getScalarizationOverhead(
                              FixedVectorType::get(
                                  PointerType::get(VT->getContext(), 0), VF),
                              /*Insert=*/false, /*Extract=*/true, CostKind)
                        : 0;
 
    // The cost of the scalar loads/stores.
    InstructionCost MemoryOpCost =
        VF * thisT()->getMemoryOpCost(Opcode, VT->getElementType(), Alignment,
                                      AddressSpace, CostKind);
 
    // Next, compute the cost of packing the result in a vector.
    InstructionCost PackingCost =
        getScalarizationOverhead(VT, Opcode != Instruction::Store,
                                 Opcode == Instruction::Store, CostKind);
 
    InstructionCost ConditionalCost = 0;
    if (VariableMask) {
      // Compute the cost of conditionally executing the memory operations with
      // variable masks. This includes extracting the individual conditions, a
      // branches and PHIs to combine the results.
      // NOTE: Estimating the cost of conditionally executing the memory
      // operations accurately is quite difficult and the current solution
      // provides a very rough estimate only.
      ConditionalCost =
          getScalarizationOverhead(
              FixedVectorType::get(Type::getInt1Ty(DataTy->getContext()), VF),
              /*Insert=*/false, /*Extract=*/true, CostKind) +
          VF * (thisT()->getCFInstrCost(Instruction::CondBr, CostKind) +
                thisT()->getCFInstrCost(Instruction::PHI, CostKind));
    }
 
    return AddrExtractCost + MemoryOpCost + PackingCost + ConditionalCost;
  }
 
  /// Checks if the provided mask \p is a splat mask, i.e. it contains only -1
  /// or same non -1 index value and this index value contained at least twice.
  /// So, mask <0, -1,-1, -1> is not considered splat (it is just identity),
  /// same for <-1, 0, -1, -1> (just a slide), while <2, -1, 2, -1> is a splat
  /// with \p Index=2.
  static bool isSplatMask(ArrayRef<int> Mask, unsigned NumSrcElts, int &Index) {
    // Check that the broadcast index meets at least twice.
    bool IsCompared = false;
    if (int SplatIdx = PoisonMaskElem;
        all_of(enumerate(Mask), [&](const auto &P) {
          if (P.value() == PoisonMaskElem)
            return P.index() != Mask.size() - 1 || IsCompared;
          if (static_cast<unsigned>(P.value()) >= NumSrcElts * 2)
            return false;
          if (SplatIdx == PoisonMaskElem) {
            SplatIdx = P.value();
            return P.index() != Mask.size() - 1;
          }
          IsCompared = true;
          return SplatIdx == P.value();
        })) {
      Index = SplatIdx;
      return true;
    }
    return false;
  }
 
  /// Several intrinsics that return structs (including llvm.sincos[pi] and
  /// llvm.modf) can be lowered to a vector library call (for certain VFs). The
  /// vector library functions correspond to the scalar calls (e.g. sincos or
  /// modf), which unlike the intrinsic return values via output pointers. This
  /// helper checks if a vector call exists for the given intrinsic, and returns
  /// the cost, which includes the cost of the mask (if required), and the loads
  /// for values returned via output pointers. \p LC is the scalar libcall and
  /// \p CallRetElementIndex (optional) is the struct element which is mapped to
  /// the call return value. If std::nullopt is returned, then no vector library
  /// call is available, so the intrinsic should be assigned the default cost
  /// (e.g. scalarization).
  std::optional<InstructionCost> getMultipleResultIntrinsicVectorLibCallCost(
      const IntrinsicCostAttributes &ICA, TTI::TargetCostKind CostKind,
      std::optional<unsigned> CallRetElementIndex = {}) const {
    Type *RetTy = ICA.getReturnType();
    // Vector variants of the intrinsic can be mapped to a vector library call.
    if (!isa<StructType>(RetTy) ||
        !isVectorizedStructTy(cast<StructType>(RetTy)))
      return std::nullopt;
 
    Type *Ty = getContainedTypes(RetTy).front();
    EVT VT = getTLI()->getValueType(DL, Ty);
 
    RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
 
    switch (ICA.getID()) {
    case Intrinsic::modf:
      LC = RTLIB::getMODF(VT);
      break;
    case Intrinsic::sincospi:
      LC = RTLIB::getSINCOSPI(VT);
      break;
    case Intrinsic::sincos:
      LC = RTLIB::getSINCOS(VT);
      break;
    default:
      return std::nullopt;
    }
 
    // Find associated libcall.
    RTLIB::LibcallImpl LibcallImpl = getTLI()->getLibcallImpl(LC);
    if (LibcallImpl == RTLIB::Unsupported)
      return std::nullopt;
 
    LLVMContext &Ctx = RetTy->getContext();
 
    // Cost the call + mask.
    auto Cost =
        thisT()->getCallInstrCost(nullptr, RetTy, ICA.getArgTypes(), CostKind);
 
    if (RTLIB::RuntimeLibcallsInfo::hasVectorMaskArgument(LibcallImpl)) {
      ElementCount VF = getVectorizedTypeVF(RetTy);
      auto VecTy = VectorType::get(IntegerType::getInt1Ty(Ctx), VF);
      Cost += thisT()->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy,
                                      VecTy, CostKind, {}, 0, nullptr, {});
    }
 
    // Lowering to a library call (with output pointers) may require us to emit
    // reloads for the results.
    for (auto [Idx, VectorTy] : enumerate(getContainedTypes(RetTy))) {
      if (Idx == CallRetElementIndex)
        continue;
      Cost += thisT()->getMemoryOpCost(
          Instruction::Load, VectorTy,
          thisT()->getDataLayout().getABITypeAlign(VectorTy), 0, CostKind);
    }
    return Cost;
  }
 
  /// Filter out constant and duplicated entries in \p Ops and return a vector
  /// containing the types from \p Tys corresponding to the remaining operands.
  static SmallVector<Type *, 4>
  filterConstantAndDuplicatedOperands(ArrayRef<const Value *> Ops,
                                      ArrayRef<Type *> Tys) {
    SmallPtrSet<const Value *, 4> UniqueOperands;
    SmallVector<Type *, 4> FilteredTys;
    for (const auto &[Op, Ty] : zip_equal(Ops, Tys)) {
      if (isa<Constant>(Op) || !UniqueOperands.insert(Op).second)
        continue;
      FilteredTys.push_back(Ty);
    }
    return FilteredTys;
  }
 
protected:
  explicit BasicTTIImplBase(const TargetMachine *TM, const DataLayout &DL)
      : BaseT(DL) {}
  ~BasicTTIImplBase() override = default;
 
  using TargetTransformInfoImplBase::DL;
  using TargetTransformInfoImplBase::getScalarizationOverhead;
 
public:
  /// \name Scalar TTI Implementations
  /// @{
  bool allowsMisalignedMemoryAccesses(LLVMContext &Context, unsigned BitWidth,
                                      unsigned AddressSpace, Align Alignment,
                                      unsigned *Fast) const override {
    EVT E = EVT::getIntegerVT(Context, BitWidth);
    return getTLI()->allowsMisalignedMemoryAccesses(
        E, AddressSpace, Alignment, MachineMemOperand::MONone, Fast);
  }
 
  bool areInlineCompatible(const Function *Caller,
                           const Function *Callee) const override {
    const TargetMachine &TM = getTLI()->getTargetMachine();
 
    const TargetSubtargetInfo *CallerSTI = TM.getSubtargetImpl(*Caller);
    const TargetSubtargetInfo *CalleeSTI = TM.getSubtargetImpl(*Callee);
    FeatureBitset InlineIgnoreFeatures = CallerSTI->getInlineIgnoreFeatures();
    FeatureBitset InlineInverseFeatures = CallerSTI->getInlineInverseFeatures();
    FeatureBitset InlineMustMatchFeatures =
        CallerSTI->getInlineMustMatchFeatures();
 
    FeatureBitset CallerBits =
        (CallerSTI->getFeatureBits() ^ InlineInverseFeatures) &
        ~InlineIgnoreFeatures;
    FeatureBitset CalleeBits =
        (CalleeSTI->getFeatureBits() ^ InlineInverseFeatures) &
        ~InlineIgnoreFeatures;
 
    if ((CallerBits & InlineMustMatchFeatures) !=
        (CalleeBits & InlineMustMatchFeatures))
      return false;
 
    // Inline a callee if its target-features are a subset of the callers
    // target-features.
    return (CallerBits & CalleeBits) == CalleeBits;
  }
 
  bool hasBranchDivergence(const Function *F = nullptr) const override {
    return false;
  }
 
  bool isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const override {
    return false;
  }
 
  bool addrspacesMayAlias(unsigned AS0, unsigned AS1) const override {
    return true;
  }
 
  unsigned getFlatAddressSpace() const override {
    // Return an invalid address space.
    return -1;
  }
 
  bool collectFlatAddressOperands(SmallVectorImpl<int> &OpIndexes,
                                  Intrinsic::ID IID) const override {
    return false;
  }
 
  bool isNoopAddrSpaceCast(unsigned FromAS, unsigned ToAS) const override {
    return getTLI()->getTargetMachine().isNoopAddrSpaceCast(DL, FromAS, ToAS);
  }
 
  unsigned getAssumedAddrSpace(const Value *V) const override {
    return getTLI()->getTargetMachine().getAssumedAddrSpace(V);
  }
 
  std::pair<const Value *, unsigned>
  getPredicatedAddrSpace(const Value *V) const override {
    return getTLI()->getTargetMachine().getPredicatedAddrSpace(V);
  }
 
  Value *rewriteIntrinsicWithAddressSpace(IntrinsicInst *II, Value *OldV,
                                          Value *NewV) const override {
    return nullptr;
  }
 
  bool isLegalAddImmediate(int64_t imm) const override {
    return getTLI()->isLegalAddImmediate(imm);
  }
 
  bool isLegalAddScalableImmediate(int64_t Imm) const override {
    return getTLI()->isLegalAddScalableImmediate(Imm);
  }
 
  bool isLegalICmpImmediate(int64_t imm) const override {
    return getTLI()->isLegalICmpImmediate(imm);
  }
 
  bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                             bool HasBaseReg, int64_t Scale, unsigned AddrSpace,
                             Instruction *I = nullptr,
                             int64_t ScalableOffset = 0) const override {
    TargetLoweringBase::AddrMode AM;
    AM.BaseGV = BaseGV;
    AM.BaseOffs = BaseOffset;
    AM.HasBaseReg = HasBaseReg;
    AM.Scale = Scale;
    AM.ScalableOffset = ScalableOffset;
    return getTLI()->isLegalAddressingMode(DL, AM, Ty, AddrSpace, I);
  }
 
  int64_t getPreferredLargeGEPBaseOffset(int64_t MinOffset, int64_t MaxOffset) {
    return getTLI()->getPreferredLargeGEPBaseOffset(MinOffset, MaxOffset);
  }
 
  unsigned getStoreMinimumVF(unsigned VF, Type *ScalarMemTy, Type *ScalarValTy,
                             Align Alignment,
                             unsigned AddrSpace) const override {
    auto &&IsSupportedByTarget = [this, ScalarMemTy, ScalarValTy, Alignment,
                                  AddrSpace](unsigned VF) {
      auto *SrcTy = FixedVectorType::get(ScalarMemTy, VF / 2);
      EVT VT = getTLI()->getValueType(DL, SrcTy);
      if (getTLI()->isOperationLegal(ISD::STORE, VT) ||
          getTLI()->isOperationCustom(ISD::STORE, VT))
        return true;
 
      EVT ValVT =
          getTLI()->getValueType(DL, FixedVectorType::get(ScalarValTy, VF / 2));
      EVT LegalizedVT =
          getTLI()->getTypeToTransformTo(ScalarMemTy->getContext(), VT);
      return getTLI()->isTruncStoreLegal(LegalizedVT, ValVT, Alignment,
                                         AddrSpace);
    };
    while (VF > 2 && IsSupportedByTarget(VF))
      VF /= 2;
    return VF;
  }
 
  bool isIndexedLoadLegal(TTI::MemIndexedMode M, Type *Ty) const override {
    EVT VT = getTLI()->getValueType(DL, Ty, /*AllowUnknown=*/true);
    return getTLI()->isIndexedLoadLegal(getISDIndexedMode(M), VT);
  }
 
  bool isIndexedStoreLegal(TTI::MemIndexedMode M, Type *Ty) const override {
    EVT VT = getTLI()->getValueType(DL, Ty, /*AllowUnknown=*/true);
    return getTLI()->isIndexedStoreLegal(getISDIndexedMode(M), VT);
  }
 
  bool isLSRCostLess(const TTI::LSRCost &C1,
                     const TTI::LSRCost &C2) const override {
    return TargetTransformInfoImplBase::isLSRCostLess(C1, C2);
  }
 
  bool isNumRegsMajorCostOfLSR() const override {
    return TargetTransformInfoImplBase::isNumRegsMajorCostOfLSR();
  }
 
  bool shouldDropLSRSolutionIfLessProfitable() const override {
    return TargetTransformInfoImplBase::shouldDropLSRSolutionIfLessProfitable();
  }
 
  bool isProfitableLSRChainElement(Instruction *I) const override {
    return TargetTransformInfoImplBase::isProfitableLSRChainElement(I);
  }
 
  InstructionCost getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                       StackOffset BaseOffset, bool HasBaseReg,
                                       int64_t Scale,
                                       unsigned AddrSpace) const override {
    TargetLoweringBase::AddrMode AM;
    AM.BaseGV = BaseGV;
    AM.BaseOffs = BaseOffset.getFixed();
    AM.HasBaseReg = HasBaseReg;
    AM.Scale = Scale;
    AM.ScalableOffset = BaseOffset.getScalable();
    if (getTLI()->isLegalAddressingMode(DL, AM, Ty, AddrSpace))
      return 0;
    return InstructionCost::getInvalid();
  }
 
  bool isTruncateFree(Type *Ty1, Type *Ty2) const override {
    return getTLI()->isTruncateFree(Ty1, Ty2);
  }
 
  bool isProfitableToHoist(Instruction *I) const override {
    return getTLI()->isProfitableToHoist(I);
  }
 
  bool useAA() const override { return getST()->useAA(); }
 
  bool isTypeLegal(Type *Ty) const override {
    EVT VT = getTLI()->getValueType(DL, Ty, /*AllowUnknown=*/true);
    return getTLI()->isTypeLegal(VT);
  }
 
  unsigned getRegUsageForType(Type *Ty) const override {
    EVT ETy = getTLI()->getValueType(DL, Ty);
    return getTLI()->getNumRegisters(Ty->getContext(), ETy);
  }
 
  InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr,
                             ArrayRef<const Value *> Operands,
                             TTI::TargetCostKind CostKind,
                             Type *AccessType) const override {
    return BaseT::getGEPCost(PointeeType, Ptr, Operands, CostKind, AccessType);
  }
 
  unsigned getEstimatedNumberOfCaseClusters(
      const SwitchInst &SI, unsigned &JumpTableSize, ProfileSummaryInfo *PSI,
      BlockFrequencyInfo *BFI) const override {
    /// Try to find the estimated number of clusters. Note that the number of
    /// clusters identified in this function could be different from the actual
    /// numbers found in lowering. This function ignore switches that are
    /// lowered with a mix of jump table / bit test / BTree. This function was
    /// initially intended to be used when estimating the cost of switch in
    /// inline cost heuristic, but it's a generic cost model to be used in other
    /// places (e.g., in loop unrolling).
    unsigned N = SI.getNumCases();
    const TargetLoweringBase *TLI = getTLI();
    const DataLayout &DL = this->getDataLayout();
 
    JumpTableSize = 0;
    bool IsJTAllowed = TLI->areJTsAllowed(SI.getParent()->getParent());
 
    // Early exit if both a jump table and bit test are not allowed.
    if (N < 1 || (!IsJTAllowed && DL.getIndexSizeInBits(0u) < N))
      return N;
 
    APInt MaxCaseVal = SI.case_begin()->getCaseValue()->getValue();
    APInt MinCaseVal = MaxCaseVal;
    for (auto CI : SI.cases()) {
      const APInt &CaseVal = CI.getCaseValue()->getValue();
      if (CaseVal.sgt(MaxCaseVal))
        MaxCaseVal = CaseVal;
      if (CaseVal.slt(MinCaseVal))
        MinCaseVal = CaseVal;
    }
 
    // Check if suitable for a bit test
    if (N <= DL.getIndexSizeInBits(0u)) {
      DenseMap<const BasicBlock *, unsigned int> DestMap;
      for (auto I : SI.cases()) {
        const BasicBlock *BB = I.getCaseSuccessor();
        ++DestMap[BB];
      }
 
      if (TLI->isSuitableForBitTests(DestMap, MinCaseVal, MaxCaseVal, DL))
        return 1;
    }
 
    // Check if suitable for a jump table.
    if (IsJTAllowed) {
      if (N < 2 || N < TLI->getMinimumJumpTableEntries())
        return N;
      uint64_t Range =
          (MaxCaseVal - MinCaseVal)
              .getLimitedValue(std::numeric_limits<uint64_t>::max() - 1) + 1;
      // Check whether a range of clusters is dense enough for a jump table
      if (TLI->isSuitableForJumpTable(&SI, N, Range, PSI, BFI)) {
        JumpTableSize = Range;
        return 1;
      }
    }
    return N;
  }
 
  bool shouldBuildLookupTables() const override {
    const TargetLoweringBase *TLI = getTLI();
    return TLI->isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
           TLI->isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
  }
 
  bool shouldBuildRelLookupTables() const override {
    const TargetMachine &TM = getTLI()->getTargetMachine();
    // If non-PIC mode, do not generate a relative lookup table.
    if (!TM.isPositionIndependent())
      return false;
 
    /// Relative lookup table entries consist of 32-bit offsets.
    /// Do not generate relative lookup tables for large code models
    /// in 64-bit achitectures where 32-bit offsets might not be enough.
    if (TM.getCodeModel() == CodeModel::Medium ||
        TM.getCodeModel() == CodeModel::Large)
      return false;
 
    const Triple &TargetTriple = TM.getTargetTriple();
    if (!TargetTriple.isArch64Bit())
      return false;
 
    // TODO: Triggers issues on aarch64 on darwin, so temporarily disable it
    // there.
    if (TargetTriple.getArch() == Triple::aarch64 && TargetTriple.isOSDarwin())
      return false;
 
    return true;
  }
 
  bool haveFastSqrt(Type *Ty) const override {
    const TargetLoweringBase *TLI = getTLI();
    EVT VT = TLI->getValueType(DL, Ty);
    return TLI->isTypeLegal(VT) &&
           TLI->isOperationLegalOrCustom(ISD::FSQRT, VT);
  }
 
  bool haveFastClmul(IntegerType *Ty) const override {
    // FIXME: clmul should really be Promote for any bitwidth under the largest
    // legal bitwidth for clmul. Using IndexTy instead of Ty is a hack to get
    // around that shortcoming.
    const DataLayout &DL = thisT()->DL;
    IntegerType *IndexTy =
        DL.getIndexType(Ty->getContext(), DL.getAllocaAddrSpace());
    if (Ty->getBitWidth() > IndexTy->getBitWidth())
      return false;
 
    const TargetLoweringBase *TLI = getTLI();
    EVT VT = TLI->getValueType(DL, IndexTy);
    return TLI->isOperationLegalOrCustom(ISD::CLMUL, VT);
  }
 
  bool isFCmpOrdCheaperThanFCmpZero(Type *Ty) const override { return true; }
 
  InstructionCost getFPOpCost(Type *Ty) const override {
    // Check whether FADD is available, as a proxy for floating-point in
    // general.
    const TargetLoweringBase *TLI = getTLI();
    EVT VT = TLI->getValueType(DL, Ty);
    if (TLI->isOperationLegalOrCustomOrPromote(ISD::FADD, VT))
      return TargetTransformInfo::TCC_Basic;
    return TargetTransformInfo::TCC_Expensive;
  }
 
  bool preferToKeepConstantsAttached(const Instruction &Inst,
                                     const Function &Fn) const override {
    switch (Inst.getOpcode()) {
    default:
      break;
    case Instruction::SDiv:
    case Instruction::SRem:
    case Instruction::UDiv:
    case Instruction::URem: {
      if (!isa<ConstantInt>(Inst.getOperand(1)))
        return false;
      EVT VT = getTLI()->getValueType(DL, Inst.getType());
      return !getTLI()->isIntDivCheap(VT, Fn.getAttributes());
    }
    };
 
    return false;
  }
 
  unsigned getInliningThresholdMultiplier() const override { return 1; }
  unsigned adjustInliningThreshold(const CallBase *CB) const override {
    return 0;
  }
  unsigned getCallerAllocaCost(const CallBase *CB,
                               const AllocaInst *AI) const override {
    return 0;
  }
 
  int getInlinerVectorBonusPercent() const override { return 150; }
 
  void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                               TTI::UnrollingPreferences &UP,
                               OptimizationRemarkEmitter *ORE) const override {
    // This unrolling functionality is target independent, but to provide some
    // motivation for its intended use, for x86:
 
    // According to the Intel 64 and IA-32 Architectures Optimization Reference
    // Manual, Intel Core models and later have a loop stream detector (and
    // associated uop queue) that can benefit from partial unrolling.
    // The relevant requirements are:
    //  - The loop must have no more than 4 (8 for Nehalem and later) branches
    //    taken, and none of them may be calls.
    //  - The loop can have no more than 18 (28 for Nehalem and later) uops.
 
    // According to the Software Optimization Guide for AMD Family 15h
    // Processors, models 30h-4fh (Steamroller and later) have a loop predictor
    // and loop buffer which can benefit from partial unrolling.
    // The relevant requirements are:
    //  - The loop must have fewer than 16 branches
    //  - The loop must have less than 40 uops in all executed loop branches
 
    // The number of taken branches in a loop is hard to estimate here, and
    // benchmarking has revealed that it is better not to be conservative when
    // estimating the branch count. As a result, we'll ignore the branch limits
    // until someone finds a case where it matters in practice.
 
    unsigned MaxOps;
    const TargetSubtargetInfo *ST = getST();
    if (PartialUnrollingThreshold.getNumOccurrences() > 0)
      MaxOps = PartialUnrollingThreshold;
    else if (ST->getSchedModel().LoopMicroOpBufferSize > 0)
      MaxOps = ST->getSchedModel().LoopMicroOpBufferSize;
    else
      return;
 
    // Scan the loop: don't unroll loops with calls.
    for (BasicBlock *BB : L->blocks()) {
      for (Instruction &I : *BB) {
        if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
          if (const Function *F = cast<CallBase>(I).getCalledFunction()) {
            if (!thisT()->isLoweredToCall(F))
              continue;
          }
 
          if (ORE) {
            ORE->emit([&]() {
              return OptimizationRemark("TTI", "DontUnroll", L->getStartLoc(),
                                        L->getHeader())
                     << "advising against unrolling the loop because it "
                        "contains a "
                     << ore::NV("Call", &I);
            });
          }
          return;
        }
      }
    }
 
    // Enable runtime and partial unrolling up to the specified size.
    // Enable using trip count upper bound to unroll loops.
    UP.Partial = UP.Runtime = UP.UpperBound = true;
    UP.PartialThreshold = MaxOps;
 
    // Avoid unrolling when optimizing for size.
    UP.OptSizeThreshold = 0;
    UP.PartialOptSizeThreshold = 0;
 
    // Set number of instructions optimized when "back edge"
    // becomes "fall through" to default value of 2.
    UP.BEInsns = 2;
  }
 
  void getPeelingPreferences(Loop *L, ScalarEvolution &SE,
                             TTI::PeelingPreferences &PP) const override {
    PP.PeelCount = 0;
    PP.AllowPeeling = true;
    PP.AllowLoopNestsPeeling = false;
    PP.PeelProfiledIterations = true;
  }
 
  bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                AssumptionCache &AC, TargetLibraryInfo *LibInfo,
                                HardwareLoopInfo &HWLoopInfo) const override {
    return BaseT::isHardwareLoopProfitable(L, SE, AC, LibInfo, HWLoopInfo);
  }
 
  unsigned getEpilogueVectorizationMinVF() const override {
    return BaseT::getEpilogueVectorizationMinVF();
  }
 
  bool preferTailFoldingOverEpilogue(TailFoldingInfo *TFI) const override {
    return BaseT::preferTailFoldingOverEpilogue(TFI);
  }
 
  TailFoldingStyle getPreferredTailFoldingStyle() const override {
    return BaseT::getPreferredTailFoldingStyle();
  }
 
  std::optional<Instruction *>
  instCombineIntrinsic(InstCombiner &IC, IntrinsicInst &II) const override {
    return BaseT::instCombineIntrinsic(IC, II);
  }
 
  std::optional<Value *>
  simplifyDemandedUseBitsIntrinsic(InstCombiner &IC, IntrinsicInst &II,
                                   APInt DemandedMask, KnownBits &Known,
                                   bool &KnownBitsComputed) const override {
    return BaseT::simplifyDemandedUseBitsIntrinsic(IC, II, DemandedMask, Known,
                                                   KnownBitsComputed);
  }
 
  std::optional<Value *> simplifyDemandedVectorEltsIntrinsic(
      InstCombiner &IC, IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
      APInt &UndefElts2, APInt &UndefElts3,
      std::function<void(Instruction *, unsigned, APInt, APInt &)>
          SimplifyAndSetOp) const override {
    return BaseT::simplifyDemandedVectorEltsIntrinsic(
        IC, II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
        SimplifyAndSetOp);
  }
 
  InstructionCost getBranchMispredictPenalty() const override {
    return getST()->getMispredictionPenalty();
  }
 
  std::optional<unsigned>
  getCacheSize(TargetTransformInfo::CacheLevel Level) const override {
    return std::optional<unsigned>(
        getST()->getCacheSize(static_cast<unsigned>(Level)));
  }
 
  std::optional<unsigned>
  getCacheAssociativity(TargetTransformInfo::CacheLevel Level) const override {
    std::optional<unsigned> TargetResult =
        getST()->getCacheAssociativity(static_cast<unsigned>(Level));
 
    if (TargetResult)
      return TargetResult;
 
    return BaseT::getCacheAssociativity(Level);
  }
 
  unsigned getCacheLineSize() const override {
    return getST()->getCacheLineSize();
  }
 
  unsigned getPrefetchDistance() const override {
    return getST()->getPrefetchDistance();
  }
 
  unsigned getMinPrefetchStride(unsigned NumMemAccesses,
                                unsigned NumStridedMemAccesses,
                                unsigned NumPrefetches,
                                bool HasCall) const override {
    return getST()->getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses,
                                         NumPrefetches, HasCall);
  }
 
  unsigned getMaxPrefetchIterationsAhead() const override {
    return getST()->getMaxPrefetchIterationsAhead();
  }
 
  bool enableWritePrefetching() const override {
    return getST()->enableWritePrefetching();
  }
 
  bool shouldPrefetchAddressSpace(unsigned AS) const override {
    return getST()->shouldPrefetchAddressSpace(AS);
  }
 
  /// @}
 
  /// \name Vector TTI Implementations
  /// @{
 
  TypeSize
  getRegisterBitWidth(TargetTransformInfo::RegisterKind K) const override {
    return TypeSize::getFixed(32);
  }
 
  std::optional<unsigned> getVScaleForTuning() const override {
    return std::nullopt;
  }
 
  /// Estimate the overhead of scalarizing an instruction. Insert and Extract
  /// are set if the demanded result elements need to be inserted and/or
  /// extracted from vectors.
  InstructionCost
  getScalarizationOverhead(VectorType *InTy, const APInt &DemandedElts,
                           bool Insert, bool Extract,
                           TTI::TargetCostKind CostKind,
                           bool ForPoisonSrc = true, ArrayRef<Value *> VL = {},
                           TTI::VectorInstrContext VIC =
                               TTI::VectorInstrContext::None) const override {
    /// FIXME: a bitfield is not a reasonable abstraction for talking about
    /// which elements are needed from a scalable vector
    if (isa<ScalableVectorType>(InTy))
      return InstructionCost::getInvalid();
    auto *Ty = cast<FixedVectorType>(InTy);
 
    assert(DemandedElts.getBitWidth() == Ty->getNumElements() &&
           (VL.empty() || VL.size() == Ty->getNumElements()) &&
           "Vector size mismatch");
 
    InstructionCost Cost = 0;
 
    for (int i = 0, e = Ty->getNumElements(); i < e; ++i) {
      if (!DemandedElts[i])
        continue;
      if (Insert) {
        Value *InsertedVal = VL.empty() ? nullptr : VL[i];
        Cost +=
            thisT()->getVectorInstrCost(Instruction::InsertElement, Ty,
                                        CostKind, i, nullptr, InsertedVal, VIC);
      }
      if (Extract)
        Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty,
                                            CostKind, i, nullptr, nullptr, VIC);
    }
 
    return Cost;
  }
 
  bool
  isTargetIntrinsicWithScalarOpAtArg(Intrinsic::ID ID,
                                     unsigned ScalarOpdIdx) const override {
    return false;
  }
 
  bool isTargetIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID,
                                              int OpdIdx) const override {
    return OpdIdx == -1;
  }
 
  bool
  isTargetIntrinsicWithStructReturnOverloadAtField(Intrinsic::ID ID,
                                                   int RetIdx) const override {
    return RetIdx == 0;
  }
 
  /// Helper wrapper for the DemandedElts variant of getScalarizationOverhead.
  InstructionCost getScalarizationOverhead(
      VectorType *InTy, bool Insert, bool Extract, TTI::TargetCostKind CostKind,
      bool ForPoisonSrc = true, ArrayRef<Value *> VL = {},
      TTI::VectorInstrContext VIC = TTI::VectorInstrContext::None) const {
    if (isa<ScalableVectorType>(InTy))
      return InstructionCost::getInvalid();
    auto *Ty = cast<FixedVectorType>(InTy);
 
    APInt DemandedElts = APInt::getAllOnes(Ty->getNumElements());
    // Use CRTP to allow target overrides
    return thisT()->getScalarizationOverhead(Ty, DemandedElts, Insert, Extract,
                                             CostKind, ForPoisonSrc, VL, VIC);
  }
 
  /// Estimate the overhead of scalarizing an instruction's
  /// operands. The (potentially vector) types to use for each of
  /// argument are passes via Tys.
  InstructionCost getOperandsScalarizationOverhead(
      ArrayRef<Type *> Tys, TTI::TargetCostKind CostKind,
      TTI::VectorInstrContext VIC =
          TTI::VectorInstrContext::None) const override {
    InstructionCost Cost = 0;
    for (Type *Ty : Tys) {
      // Disregard things like metadata arguments.
      if (!Ty->isIntOrIntVectorTy() && !Ty->isFPOrFPVectorTy() &&
          !Ty->isPtrOrPtrVectorTy())
        continue;
 
      if (auto *VecTy = dyn_cast<VectorType>(Ty))
        Cost += getScalarizationOverhead(VecTy, /*Insert*/ false,
                                         /*Extract*/ true, CostKind,
                                         /*ForPoisonSrc=*/true, {}, VIC);
    }
 
    return Cost;
  }
 
  /// Estimate the overhead of scalarizing the inputs and outputs of an
  /// instruction, with return type RetTy and arguments Args of type Tys. If
  /// Args are unknown (empty), then the cost associated with one argument is
  /// added as a heuristic.
  InstructionCost getScalarizationOverhead(VectorType *RetTy,
                                           ArrayRef<const Value *> Args,
                                           ArrayRef<Type *> Tys,
                                           TTI::TargetCostKind CostKind) const {
    InstructionCost Cost = getScalarizationOverhead(
        RetTy, /*Insert*/ true, /*Extract*/ false, CostKind);
    if (!Args.empty())
      Cost += getOperandsScalarizationOverhead(
          filterConstantAndDuplicatedOperands(Args, Tys), CostKind);
    else
      // When no information on arguments is provided, we add the cost
      // associated with one argument as a heuristic.
      Cost += getScalarizationOverhead(RetTy, /*Insert*/ false,
                                       /*Extract*/ true, CostKind);
 
    return Cost;
  }
 
  /// Estimate the cost of type-legalization and the legalized type.
  std::pair<InstructionCost, MVT> getTypeLegalizationCost(Type *Ty) const {
    auto [It, Inserted] = TypeLegalizationCostCache.try_emplace(Ty);
    if (Inserted)
      It->second = computeTypeLegalizationCost(Ty);
    return It->second;
  }
 
private:
  std::pair<InstructionCost, MVT> computeTypeLegalizationCost(Type *Ty) const {
    LLVMContext &C = Ty->getContext();
    EVT MTy = getTLI()->getValueType(DL, Ty);
 
    InstructionCost Cost = 1;
    // We keep legalizing the type until we find a legal kind. We assume that
    // the only operation that costs anything is the split. After splitting
    // we need to handle two types.
    while (true) {
      TargetLoweringBase::LegalizeKind LK = getTLI()->getTypeConversion(C, MTy);
 
      if (LK.first == TargetLoweringBase::TypeScalarizeScalableVector) {
        // Ensure we return a sensible simple VT here, since many callers of
        // this function require it.
        MVT VT = MTy.isSimple() ? MTy.getSimpleVT() : MVT::i64;
        return std::make_pair(InstructionCost::getInvalid(), VT);
      }
 
      if (LK.first == TargetLoweringBase::TypeLegal)
        return std::make_pair(Cost, MTy.getSimpleVT());
 
      if (LK.first == TargetLoweringBase::TypeSplitVector ||
          LK.first == TargetLoweringBase::TypeExpandInteger)
        Cost *= 2;
 
      // Do not loop with f128 type.
      if (MTy == LK.second)
        return std::make_pair(Cost, MTy.getSimpleVT());
 
      // Keep legalizing the type.
      MTy = LK.second;
    }
  }
 
  /// Memoizes type legalization cost. The mapping does not depend on the IR, so
  /// entries stay valid for the lifetime of this object.
  mutable DenseMap<Type *, std::pair<InstructionCost, MVT>>
      TypeLegalizationCostCache;
 
public:
  unsigned getMaxInterleaveFactor(ElementCount VF,
                                  bool HasUnorderedReductions) const override {
    return 1;
  }
 
  InstructionCost getArithmeticInstrCost(
      unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind,
      TTI::OperandValueInfo Opd1Info = {TTI::OK_AnyValue, TTI::OP_None},
      TTI::OperandValueInfo Opd2Info = {TTI::OK_AnyValue, TTI::OP_None},
      ArrayRef<const Value *> Args = {},
      const Instruction *CtxI = nullptr) const override {
    // Check if any of the operands are vector operands.
    const TargetLoweringBase *TLI = getTLI();
    int ISD = TLI->InstructionOpcodeToISD(Opcode);
    assert(ISD && "Invalid opcode");
 
    // TODO: Handle more cost kinds.
    if (CostKind != TTI::TCK_RecipThroughput)
      return BaseT::getArithmeticInstrCost(Opcode, Ty, CostKind,
                                           Opd1Info, Opd2Info,
                                           Args, CtxI);
 
    std::pair<InstructionCost, MVT> LT = getTypeLegalizationCost(Ty);
 
    bool IsFloat = Ty->isFPOrFPVectorTy();
    // Assume that floating point arithmetic operations cost twice as much as
    // integer operations.
    InstructionCost OpCost = (IsFloat ? 2 : 1);
 
    if (TLI->isOperationLegalOrPromote(ISD, LT.second)) {
      // The operation is legal. Assume it costs 1.
      // TODO: Once we have extract/insert subvector cost we need to use them.
      return LT.first * OpCost;
    }
 
    if (!TLI->isOperationExpand(ISD, LT.second)) {
      // If the operation is custom lowered, then assume that the code is twice
      // as expensive.
      return LT.first * 2 * OpCost;
    }
 
    // An 'Expand' of URem and SRem is special because it may default
    // to expanding the operation into a sequence of sub-operations
    // i.e. X % Y -> X-(X/Y)*Y.
    if (ISD == ISD::UREM || ISD == ISD::SREM) {
      bool IsSigned = ISD == ISD::SREM;
      if (TLI->isOperationLegalOrCustom(IsSigned ? ISD::SDIVREM : ISD::UDIVREM,
                                        LT.second) ||
          TLI->isOperationLegalOrCustom(IsSigned ? ISD::SDIV : ISD::UDIV,
                                        LT.second)) {
        unsigned DivOpc = IsSigned ? Instruction::SDiv : Instruction::UDiv;
        InstructionCost DivCost = thisT()->getArithmeticInstrCost(
            DivOpc, Ty, CostKind, Opd1Info, Opd2Info);
        InstructionCost MulCost =
            thisT()->getArithmeticInstrCost(Instruction::Mul, Ty, CostKind);
        InstructionCost SubCost =
            thisT()->getArithmeticInstrCost(Instruction::Sub, Ty, CostKind);
        return DivCost + MulCost + SubCost;
      }
    }
 
    // We cannot scalarize scalable vectors, so return Invalid.
    if (isa<ScalableVectorType>(Ty))
      return InstructionCost::getInvalid();
 
    // Else, assume that we need to scalarize this op.
    // TODO: If one of the types get legalized by splitting, handle this
    // similarly to what getCastInstrCost() does.
    if (auto *VTy = dyn_cast<FixedVectorType>(Ty)) {
      InstructionCost Cost = thisT()->getArithmeticInstrCost(
          Opcode, VTy->getScalarType(), CostKind, Opd1Info, Opd2Info,
          Args, CtxI);
      // Return the cost of multiple scalar invocation plus the cost of
      // inserting and extracting the values.
      SmallVector<Type *> Tys(Args.size(), Ty);
      return getScalarizationOverhead(VTy, Args, Tys, CostKind) +
             VTy->getNumElements() * Cost;
    }
 
    // We don't know anything about this scalar instruction.
    return OpCost;
  }
 
  TTI::ShuffleKind improveShuffleKindFromMask(TTI::ShuffleKind Kind,
                                              ArrayRef<int> Mask,
                                              VectorType *SrcTy, int &Index,
                                              VectorType *&SubTy) const {
    if (Mask.empty())
      return Kind;
    int NumDstElts = Mask.size();
    int NumSrcElts = SrcTy->getElementCount().getKnownMinValue();
    switch (Kind) {
    case TTI::SK_PermuteSingleSrc: {
      if (ShuffleVectorInst::isReverseMask(Mask, NumSrcElts))
        return TTI::SK_Reverse;
      if (ShuffleVectorInst::isZeroEltSplatMask(Mask, NumSrcElts))
        return TTI::SK_Broadcast;
      if (isSplatMask(Mask, NumSrcElts, Index))
        return TTI::SK_Broadcast;
      if (ShuffleVectorInst::isExtractSubvectorMask(Mask, NumSrcElts, Index) &&
          (Index + NumDstElts) <= NumSrcElts) {
        SubTy = FixedVectorType::get(SrcTy->getElementType(), NumDstElts);
        return TTI::SK_ExtractSubvector;
      }
      break;
    }
    case TTI::SK_PermuteTwoSrc: {
      if (all_of(Mask, [NumSrcElts](int M) { return M < NumSrcElts; }))
        return improveShuffleKindFromMask(TTI::SK_PermuteSingleSrc, Mask, SrcTy,
                                          Index, SubTy);
      int NumSubElts;
      if (NumDstElts > 2 && ShuffleVectorInst::isInsertSubvectorMask(
                                Mask, NumSrcElts, NumSubElts, Index)) {
        if (Index + NumSubElts > NumSrcElts)
          return Kind;
        SubTy = FixedVectorType::get(SrcTy->getElementType(), NumSubElts);
        return TTI::SK_InsertSubvector;
      }
      if (ShuffleVectorInst::isSelectMask(Mask, NumSrcElts))
        return TTI::SK_Select;
      if (ShuffleVectorInst::isTransposeMask(Mask, NumSrcElts))
        return TTI::SK_Transpose;
      if (ShuffleVectorInst::isSpliceMask(Mask, NumSrcElts, Index))
        return TTI::SK_Splice;
      break;
    }
    case TTI::SK_Select:
    case TTI::SK_Reverse:
    case TTI::SK_Broadcast:
    case TTI::SK_Transpose:
    case TTI::SK_InsertSubvector:
    case TTI::SK_ExtractSubvector:
    case TTI::SK_Splice:
      break;
    }
    return Kind;
  }
 
  InstructionCost
  getShuffleCost(TTI::ShuffleKind Kind, VectorType *DstTy, VectorType *SrcTy,
                 TTI::TargetCostKind CostKind, ArrayRef<int> Mask, int Index,
                 VectorType *SubTp, ArrayRef<const Value *> Args = {},
                 const Instruction *CtxI = nullptr,
                 TTI::VectorInstrContext VIC =
                     TTI::VectorInstrContext::None) const override {
    switch (improveShuffleKindFromMask(Kind, Mask, SrcTy, Index, SubTp)) {
    case TTI::SK_Broadcast:
      if (auto *FVT = dyn_cast<FixedVectorType>(SrcTy))
        return getBroadcastShuffleOverhead(FVT, CostKind);
      return InstructionCost::getInvalid();
    case TTI::SK_Select:
    case TTI::SK_Splice:
    case TTI::SK_Reverse:
    case TTI::SK_Transpose:
    case TTI::SK_PermuteSingleSrc:
    case TTI::SK_PermuteTwoSrc:
      if (auto *FVT = dyn_cast<FixedVectorType>(SrcTy))
        return getPermuteShuffleOverhead(FVT, CostKind);
      return InstructionCost::getInvalid();
    case TTI::SK_ExtractSubvector:
      return getExtractSubvectorOverhead(SrcTy, CostKind, Index,
                                         cast<FixedVectorType>(SubTp));
    case TTI::SK_InsertSubvector:
      return getInsertSubvectorOverhead(DstTy, CostKind, Index,
                                        cast<FixedVectorType>(SubTp));
    }
    llvm_unreachable("Unknown TTI::ShuffleKind");
  }
 
  InstructionCost
  getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src,
                   TTI::CastContextHint CCH, TTI::TargetCostKind CostKind,
                   const Instruction *I = nullptr) const override {
    if (BaseT::getCastInstrCost(Opcode, Dst, Src, CCH, CostKind, I) == 0)
      return 0;
 
    const TargetLoweringBase *TLI = getTLI();
    int ISD = TLI->InstructionOpcodeToISD(Opcode);
    assert(ISD && "Invalid opcode");
    std::pair<InstructionCost, MVT> SrcLT = getTypeLegalizationCost(Src);
    std::pair<InstructionCost, MVT> DstLT = getTypeLegalizationCost(Dst);
 
    TypeSize SrcSize = SrcLT.second.getSizeInBits();
    TypeSize DstSize = DstLT.second.getSizeInBits();
    bool IntOrPtrSrc = Src->isIntegerTy() || Src->isPointerTy();
    bool IntOrPtrDst = Dst->isIntegerTy() || Dst->isPointerTy();
 
    switch (Opcode) {
    default:
      break;
    case Instruction::Trunc:
      // Check for NOOP conversions.
      if (TLI->isTruncateFree(SrcLT.second, DstLT.second))
        return 0;
      [[fallthrough]];
    case Instruction::BitCast:
      // Bitcast between types that are legalized to the same type are free and
      // assume int to/from ptr of the same size is also free.
      if (SrcLT.first == DstLT.first && IntOrPtrSrc == IntOrPtrDst &&
          SrcSize == DstSize)
        return 0;
      break;
    case Instruction::FPExt:
      if (I && getTLI()->isExtFree(I))
        return 0;
      break;
    case Instruction::ZExt:
      if (TLI->isZExtFree(SrcLT.second, DstLT.second))
        return 0;
      [[fallthrough]];
    case Instruction::SExt:
      if (I && getTLI()->isExtFree(I))
        return 0;
 
      // If this is a zext/sext of a load, return 0 if the corresponding
      // extending load exists on target and the result type is legal.
      if (CCH == TTI::CastContextHint::Normal) {
        EVT ExtVT = EVT::getEVT(Dst);
        EVT LoadVT = EVT::getEVT(Src);
        unsigned LType =
            Opcode == Instruction::ZExt ? ISD::ZEXTLOAD : ISD::SEXTLOAD;
        if (I) {
          if (auto *LI = dyn_cast<LoadInst>(I->getOperand(0))) {
            if (DstLT.first == SrcLT.first &&
                TLI->isLoadLegal(ExtVT, LoadVT, LI->getAlign(),
                                 LI->getPointerAddressSpace(), LType, false))
              return 0;
          } else if (auto *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
            switch (II->getIntrinsicID()) {
            case Intrinsic::masked_load: {
              Type *PtrType = II->getArgOperand(0)->getType();
              assert(PtrType->isPointerTy());
 
              if (DstLT.first == SrcLT.first &&
                  TLI->isLoadLegal(
                      ExtVT, LoadVT, II->getParamAlign(0).valueOrOne(),
                      PtrType->getPointerAddressSpace(), LType, false))
                return 0;
 
              break;
            }
            default:
              break;
            }
          }
        }
      }
      break;
    case Instruction::AddrSpaceCast:
      if (TLI->isFreeAddrSpaceCast(DL, Src->getPointerAddressSpace(),
                                   Dst->getPointerAddressSpace()))
        return 0;
      break;
    }
 
    auto *SrcVTy = dyn_cast<VectorType>(Src);
    auto *DstVTy = dyn_cast<VectorType>(Dst);
 
    // If the cast is marked as legal (or promote) then assume low cost.
    if (SrcLT.first == DstLT.first &&
        TLI->isOperationLegalOrPromote(ISD, DstLT.second))
      return SrcLT.first;
 
    // Handle scalar conversions.
    if (!SrcVTy && !DstVTy) {
      // Just check the op cost. If the operation is legal then assume it costs
      // 1.
      if (!TLI->isOperationExpand(ISD, DstLT.second))
        return 1;
 
      // Assume that illegal scalar instruction are expensive.
      return 4;
    }
 
    // Check vector-to-vector casts.
    if (DstVTy && SrcVTy) {
      // If the cast is between same-sized registers, then the check is simple.
      if (SrcLT.first == DstLT.first && SrcSize == DstSize) {
 
        // Assume that Zext is done using AND.
        if (Opcode == Instruction::ZExt)
          return SrcLT.first;
 
        // Assume that sext is done using SHL and SRA.
        if (Opcode == Instruction::SExt)
          return SrcLT.first * 2;
 
        // Just check the op cost. If the operation is legal then assume it
        // costs
        // 1 and multiply by the type-legalization overhead.
        if (!TLI->isOperationExpand(ISD, DstLT.second))
          return SrcLT.first * 1;
      }
 
      // If we are legalizing by splitting, query the concrete TTI for the cost
      // of casting the original vector twice. We also need to factor in the
      // cost of the split itself. Count that as 1, to be consistent with
      // getTypeLegalizationCost().
      bool SplitSrc =
          TLI->getTypeAction(Src->getContext(), TLI->getValueType(DL, Src)) ==
          TargetLowering::TypeSplitVector;
      bool SplitDst =
          TLI->getTypeAction(Dst->getContext(), TLI->getValueType(DL, Dst)) ==
          TargetLowering::TypeSplitVector;
      if ((SplitSrc || SplitDst) && SrcVTy->getElementCount().isKnownEven() &&
          DstVTy->getElementCount().isKnownEven()) {
        Type *SplitDstTy = VectorType::getHalfElementsVectorType(DstVTy);
        Type *SplitSrcTy = VectorType::getHalfElementsVectorType(SrcVTy);
        const T *TTI = thisT();
        // If both types need to be split then the split is free.
        InstructionCost SplitCost =
            (!SplitSrc || !SplitDst) ? TTI->getVectorSplitCost() : 0;
        return SplitCost +
               (2 * TTI->getCastInstrCost(Opcode, SplitDstTy, SplitSrcTy, CCH,
                                          CostKind, I));
      }
 
      // Scalarization cost is Invalid, can't assume any num elements.
      if (isa<ScalableVectorType>(DstVTy))
        return InstructionCost::getInvalid();
 
      // In other cases where the source or destination are illegal, assume
      // the operation will get scalarized.
      unsigned Num = cast<FixedVectorType>(DstVTy)->getNumElements();
      InstructionCost Cost = thisT()->getCastInstrCost(
          Opcode, Dst->getScalarType(), Src->getScalarType(), CCH, CostKind, I);
 
      // Return the cost of multiple scalar invocation plus the cost of
      // inserting and extracting the values.
      return getScalarizationOverhead(DstVTy, /*Insert*/ true, /*Extract*/ true,
                                      CostKind) +
             Num * Cost;
    }
 
    // We already handled vector-to-vector and scalar-to-scalar conversions.
    // This
    // is where we handle bitcast between vectors and scalars. We need to assume
    //  that the conversion is scalarized in one way or another.
    if (Opcode == Instruction::BitCast) {
      // Illegal bitcasts are done by storing and loading from a stack slot.
      return (SrcVTy ? getScalarizationOverhead(SrcVTy, /*Insert*/ false,
                                                /*Extract*/ true, CostKind)
                     : 0) +
             (DstVTy ? getScalarizationOverhead(DstVTy, /*Insert*/ true,
                                                /*Extract*/ false, CostKind)
                     : 0);
    }
 
    llvm_unreachable("Unhandled cast");
  }
 
  InstructionCost
  getExtractWithExtendCost(unsigned Opcode, Type *Dst, VectorType *VecTy,
                           unsigned Index,
                           TTI::TargetCostKind CostKind) const override {
    return thisT()->getVectorInstrCost(Instruction::ExtractElement, VecTy,
                                       CostKind, Index, nullptr, nullptr) +
           thisT()->getCastInstrCost(Opcode, Dst, VecTy->getElementType(),
                                     TTI::CastContextHint::None, CostKind);
  }
 
  InstructionCost
  getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind,
                 const Instruction *I = nullptr) const override {
    return BaseT::getCFInstrCost(Opcode, CostKind, I);
  }
 
  InstructionCost getCmpSelInstrCost(
      unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred,
      TTI::TargetCostKind CostKind,
      TTI::OperandValueInfo Op1Info = {TTI::OK_AnyValue, TTI::OP_None},
      TTI::OperandValueInfo Op2Info = {TTI::OK_AnyValue, TTI::OP_None},
      const Instruction *I = nullptr) const override {
    const TargetLoweringBase *TLI = getTLI();
    int ISD = TLI->InstructionOpcodeToISD(Opcode);
    assert(ISD && "Invalid opcode");
 
    if (getTLI()->getValueType(DL, ValTy, true) == MVT::Other)
      return BaseT::getCmpSelInstrCost(Opcode, ValTy, CondTy, VecPred, CostKind,
                                       Op1Info, Op2Info, I);
 
    // Selects on vectors are actually vector selects.
    if (ISD == ISD::SELECT) {
      assert(CondTy && "CondTy must exist");
      if (CondTy->isVectorTy())
        ISD = ISD::VSELECT;
    }
    std::pair<InstructionCost, MVT> LT = getTypeLegalizationCost(ValTy);
 
    if (!(ValTy->isVectorTy() && !LT.second.isVector()) &&
        !TLI->isOperationExpand(ISD, LT.second)) {
      // The operation is legal. Assume it costs 1. Multiply
      // by the type-legalization overhead.
      return LT.first * 1;
    }
 
    // Otherwise, assume that the cast is scalarized.
    // TODO: If one of the types get legalized by splitting, handle this
    // similarly to what getCastInstrCost() does.
    if (auto *ValVTy = dyn_cast<VectorType>(ValTy)) {
      if (isa<ScalableVectorType>(ValTy))
        return InstructionCost::getInvalid();
 
      unsigned Num = cast<FixedVectorType>(ValVTy)->getNumElements();
      InstructionCost Cost = thisT()->getCmpSelInstrCost(
          Opcode, ValVTy->getScalarType(), CondTy->getScalarType(), VecPred,
          CostKind, Op1Info, Op2Info, I);
 
      // Return the cost of multiple scalar invocation plus the cost of
      // inserting and extracting the values.
      return getScalarizationOverhead(ValVTy, /*Insert*/ true,
                                      /*Extract*/ false, CostKind) +
             Num * Cost;
    }
 
    // Unknown scalar opcode.
    return 1;
  }
 
  InstructionCost
  getVectorInstrCost(unsigned Opcode, Type *Val, TTI::TargetCostKind CostKind,
                     unsigned Index, const Value *Op0, const Value *Op1,
                     TTI::VectorInstrContext VIC =
                         TTI::VectorInstrContext::None) const override {
    return getRegUsageForType(Val->getScalarType());
  }
 
  /// \param ScalarUserAndIdx encodes the information about extracts from a
  /// vector with 'Scalar' being the value being extracted,'User' being the user
  /// of the extract(nullptr if user is not known before vectorization) and
  /// 'Idx' being the extract lane.
  InstructionCost getVectorInstrCost(
      unsigned Opcode, Type *Val, TTI::TargetCostKind CostKind, unsigned Index,
      Value *Scalar,
      ArrayRef<std::tuple<Value *, User *, int>> ScalarUserAndIdx,
      TTI::VectorInstrContext VIC =
          TTI::VectorInstrContext::None) const override {
    return getVectorInstrCost(Opcode, Val, CostKind, Index, nullptr, nullptr,
                              VIC);
  }
 
  InstructionCost
  getVectorInstrCost(const Instruction &I, Type *Val,
                     TTI::TargetCostKind CostKind, unsigned Index,
                     TTI::VectorInstrContext VIC =
                         TTI::VectorInstrContext::None) const override {
    Value *Op0 = nullptr;
    Value *Op1 = nullptr;
    if (auto *IE = dyn_cast<InsertElementInst>(&I)) {
      Op0 = IE->getOperand(0);
      Op1 = IE->getOperand(1);
    }
    // If VIC is None, compute it from the instruction
    if (VIC == TTI::VectorInstrContext::None)
      VIC = TTI::getVectorInstrContextHint(&I);
    return thisT()->getVectorInstrCost(I.getOpcode(), Val, CostKind, Index, Op0,
                                       Op1, VIC);
  }
 
  InstructionCost
  getIndexedVectorInstrCostFromEnd(unsigned Opcode, Type *Val,
                                   TTI::TargetCostKind CostKind,
                                   unsigned Index) const override {
    unsigned NewIndex = -1;
    if (auto *FVTy = dyn_cast<FixedVectorType>(Val)) {
      assert(Index < FVTy->getNumElements() &&
             "Unexpected index from end of vector");
      NewIndex = FVTy->getNumElements() - 1 - Index;
    }
    return thisT()->getVectorInstrCost(Opcode, Val, CostKind, NewIndex, nullptr,
                                       nullptr);
  }
 
  InstructionCost
  getReplicationShuffleCost(Type *EltTy, int ReplicationFactor, int VF,
                            const APInt &DemandedDstElts,
                            TTI::TargetCostKind CostKind) const override {
    assert(DemandedDstElts.getBitWidth() == (unsigned)VF * ReplicationFactor &&
           "Unexpected size of DemandedDstElts.");
 
    InstructionCost Cost;
 
    auto *SrcVT = FixedVectorType::get(EltTy, VF);
    auto *ReplicatedVT = FixedVectorType::get(EltTy, VF * ReplicationFactor);
 
    // The Mask shuffling cost is extract all the elements of the Mask
    // and insert each of them Factor times into the wide vector:
    //
    // E.g. an interleaved group with factor 3:
    //    %mask = icmp ult <8 x i32> %vec1, %vec2
    //    %interleaved.mask = shufflevector <8 x i1> %mask, <8 x i1> undef,
    //        <24 x i32> <0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7>
    // The cost is estimated as extract all mask elements from the <8xi1> mask
    // vector and insert them factor times into the <24xi1> shuffled mask
    // vector.
    APInt DemandedSrcElts = APIntOps::ScaleBitMask(DemandedDstElts, VF);
    Cost += thisT()->getScalarizationOverhead(SrcVT, DemandedSrcElts,
                                              /*Insert*/ false,
                                              /*Extract*/ true, CostKind);
    Cost += thisT()->getScalarizationOverhead(ReplicatedVT, DemandedDstElts,
                                              /*Insert*/ true,
                                              /*Extract*/ false, CostKind);
 
    return Cost;
  }
 
  InstructionCost getMemoryOpCost(
      unsigned Opcode, Type *Src, Align Alignment, unsigned AddressSpace,
      TTI::TargetCostKind CostKind,
      TTI::OperandValueInfo OpInfo = {TTI::OK_AnyValue, TTI::OP_None},
      const Instruction *I = nullptr) const override {
    assert(!Src->isVoidTy() && "Invalid type");
    // Assume types, such as structs, are expensive.
    if (getTLI()->getValueType(DL, Src,  true) == MVT::Other)
      return 4;
    std::pair<InstructionCost, MVT> LT = getTypeLegalizationCost(Src);
 
    // FIXME: Arbitrary cost
    if (Opcode == Instruction::Load && CostKind == TTI::TCK_Latency)
      return 4;
 
    // Assuming that all loads of legal types cost 1.
    InstructionCost Cost = LT.first;
    if (CostKind != TTI::TCK_RecipThroughput)
      return Cost;
 
    const DataLayout &DL = this->getDataLayout();
    if (Src->isVectorTy() &&
        // In practice it's not currently possible to have a change in lane
        // length for extending loads or truncating stores so both types should
        // have the same scalable property.
        TypeSize::isKnownLT(DL.getTypeStoreSizeInBits(Src),
                            LT.second.getSizeInBits())) {
      // This is a vector load that legalizes to a larger type than the vector
      // itself. Unless the corresponding extending load or truncating store is
      // legal, then this will scalarize.
      TargetLowering::LegalizeAction LA = TargetLowering::Expand;
      EVT MemVT = getTLI()->getValueType(DL, Src);
      if (Opcode == Instruction::Store)
        LA = getTLI()->getTruncStoreAction(LT.second, MemVT, Alignment,
                                           AddressSpace);
      else
        LA = getTLI()->getLoadAction(LT.second, MemVT, Alignment, AddressSpace,
                                     ISD::EXTLOAD, false);
 
      if (LA != TargetLowering::Legal && LA != TargetLowering::Custom) {
        // This is a vector load/store for some illegal type that is scalarized.
        // We must account for the cost of building or decomposing the vector.
        Cost += getScalarizationOverhead(
            cast<VectorType>(Src), Opcode != Instruction::Store,
            Opcode == Instruction::Store, CostKind);
      }
    }
 
    return Cost;
  }
 
  InstructionCost getInterleavedMemoryOpCost(
      unsigned Opcode, Type *VecTy, unsigned Factor, ArrayRef<unsigned> Indices,
      Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind,
      bool UseMaskForCond = false, bool UseMaskForGaps = false) const override {
 
    // We cannot scalarize scalable vectors, so return Invalid.
    if (isa<ScalableVectorType>(VecTy))
      return InstructionCost::getInvalid();
 
    auto *VT = cast<FixedVectorType>(VecTy);
 
    unsigned NumElts = VT->getNumElements();
    assert(Factor > 1 && NumElts % Factor == 0 && "Invalid interleave factor");
 
    unsigned NumSubElts = NumElts / Factor;
    auto *SubVT = FixedVectorType::get(VT->getElementType(), NumSubElts);
 
    // Firstly, the cost of load/store operation.
    InstructionCost Cost;
    if (UseMaskForCond || UseMaskForGaps) {
      unsigned IID = Opcode == Instruction::Load ? Intrinsic::masked_load
                                                 : Intrinsic::masked_store;
      Cost = thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, VecTy, Alignment, AddressSpace),
          CostKind);
    } else
      Cost = thisT()->getMemoryOpCost(Opcode, VecTy, Alignment, AddressSpace,
                                      CostKind);
 
    // Legalize the vector type, and get the legalized and unlegalized type
    // sizes.
    MVT VecTyLT = getTypeLegalizationCost(VecTy).second;
    unsigned VecTySize = thisT()->getDataLayout().getTypeStoreSize(VecTy);
    unsigned VecTyLTSize = VecTyLT.getStoreSize();
 
    // Scale the cost of the memory operation by the fraction of legalized
    // instructions that will actually be used. We shouldn't account for the
    // cost of dead instructions since they will be removed.
    //
    // E.g., An interleaved load of factor 8:
    //       %vec = load <16 x i64>, <16 x i64>* %ptr
    //       %v0 = shufflevector %vec, undef, <0, 8>
    //
    // If <16 x i64> is legalized to 8 v2i64 loads, only 2 of the loads will be
    // used (those corresponding to elements [0:1] and [8:9] of the unlegalized
    // type). The other loads are unused.
    //
    // TODO: Note that legalization can turn masked loads/stores into unmasked
    // (legalized) loads/stores. This can be reflected in the cost.
    if (Cost.isValid() && VecTySize > VecTyLTSize) {
      // The number of loads of a legal type it will take to represent a load
      // of the unlegalized vector type.
      unsigned NumLegalInsts = divideCeil(VecTySize, VecTyLTSize);
 
      // The number of elements of the unlegalized type that correspond to a
      // single legal instruction.
      unsigned NumEltsPerLegalInst = divideCeil(NumElts, NumLegalInsts);
 
      // Determine which legal instructions will be used.
      BitVector UsedInsts(NumLegalInsts, false);
      for (unsigned Index : Indices)
        for (unsigned Elt = 0; Elt < NumSubElts; ++Elt)
          UsedInsts.set((Index + Elt * Factor) / NumEltsPerLegalInst);
 
      // Scale the cost of the load by the fraction of legal instructions that
      // will be used.
      Cost = divideCeil(UsedInsts.count() * Cost.getValue(), NumLegalInsts);
    }
 
    // Then plus the cost of interleave operation.
    assert(Indices.size() <= Factor &&
           "Interleaved memory op has too many members");
 
    const APInt DemandedAllSubElts = APInt::getAllOnes(NumSubElts);
    const APInt DemandedAllResultElts = APInt::getAllOnes(NumElts);
 
    APInt DemandedLoadStoreElts = APInt::getZero(NumElts);
    for (unsigned Index : Indices) {
      assert(Index < Factor && "Invalid index for interleaved memory op");
      for (unsigned Elm = 0; Elm < NumSubElts; Elm++)
        DemandedLoadStoreElts.setBit(Index + Elm * Factor);
    }
 
    if (Opcode == Instruction::Load) {
      // The interleave cost is similar to extract sub vectors' elements
      // from the wide vector, and insert them into sub vectors.
      //
      // E.g. An interleaved load of factor 2 (with one member of index 0):
      //      %vec = load <8 x i32>, <8 x i32>* %ptr
      //      %v0 = shuffle %vec, undef, <0, 2, 4, 6>         ; Index 0
      // The cost is estimated as extract elements at 0, 2, 4, 6 from the
      // <8 x i32> vector and insert them into a <4 x i32> vector.
      InstructionCost InsSubCost = thisT()->getScalarizationOverhead(
          SubVT, DemandedAllSubElts,
          /*Insert*/ true, /*Extract*/ false, CostKind);
      Cost += Indices.size() * InsSubCost;
      Cost += thisT()->getScalarizationOverhead(VT, DemandedLoadStoreElts,
                                                /*Insert*/ false,
                                                /*Extract*/ true, CostKind);
    } else {
      // The interleave cost is extract elements from sub vectors, and
      // insert them into the wide vector.
      //
      // E.g. An interleaved store of factor 3 with 2 members at indices 0,1:
      // (using VF=4):
      //    %v0_v1 = shuffle %v0, %v1, <0,4,undef,1,5,undef,2,6,undef,3,7,undef>
      //    %gaps.mask = <true, true, false, true, true, false,
      //                  true, true, false, true, true, false>
      //    call llvm.masked.store <12 x i32> %v0_v1, <12 x i32>* %ptr,
      //                           i32 Align, <12 x i1> %gaps.mask
      // The cost is estimated as extract all elements (of actual members,
      // excluding gaps) from both <4 x i32> vectors and insert into the <12 x
      // i32> vector.
      InstructionCost ExtSubCost = thisT()->getScalarizationOverhead(
          SubVT, DemandedAllSubElts,
          /*Insert*/ false, /*Extract*/ true, CostKind);
      Cost += ExtSubCost * Indices.size();
      Cost += thisT()->getScalarizationOverhead(VT, DemandedLoadStoreElts,
                                                /*Insert*/ true,
                                                /*Extract*/ false, CostKind);
    }
 
    if (!UseMaskForCond)
      return Cost;
 
    Type *I8Type = Type::getInt8Ty(VT->getContext());
 
    Cost += thisT()->getReplicationShuffleCost(
        I8Type, Factor, NumSubElts,
        UseMaskForGaps ? DemandedLoadStoreElts : DemandedAllResultElts,
        CostKind);
 
    // The Gaps mask is invariant and created outside the loop, therefore the
    // cost of creating it is not accounted for here. However if we have both
    // a MaskForGaps and some other mask that guards the execution of the
    // memory access, we need to account for the cost of And-ing the two masks
    // inside the loop.
    if (UseMaskForGaps) {
      auto *MaskVT = FixedVectorType::get(I8Type, NumElts);
      Cost += thisT()->getArithmeticInstrCost(BinaryOperator::And, MaskVT,
                                              CostKind);
    }
 
    return Cost;
  }
 
  /// Get intrinsic cost based on arguments.
  InstructionCost
  getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
                        TTI::TargetCostKind CostKind) const override {
    // Check for generically free intrinsics.
    if (BaseT::getIntrinsicInstrCost(ICA, CostKind) == 0)
      return 0;
 
    // Assume that target intrinsics are cheap.
    Intrinsic::ID IID = ICA.getID();
    if (Intrinsic::isTargetIntrinsic(IID))
      return TargetTransformInfo::TCC_Basic;
 
    // VP Intrinsics should have the same cost as their non-vp counterpart.
    // TODO: Adjust the cost to make the vp intrinsic cheaper than its non-vp
    // counterpart when the vector length argument is smaller than the maximum
    // vector length.
    // TODO: Support other kinds of VPIntrinsics
    if (VPIntrinsic::isVPIntrinsic(ICA.getID())) {
      std::optional<unsigned> FOp =
          VPIntrinsic::getFunctionalOpcodeForVP(ICA.getID());
      if (FOp) {
        if (ICA.getID() == Intrinsic::vp_load) {
          Align Alignment;
          if (auto *VPI = dyn_cast_or_null<VPIntrinsic>(ICA.getInst()))
            Alignment = VPI->getPointerAlignment().valueOrOne();
          unsigned AS = 0;
          if (ICA.getArgTypes().size() > 1)
            if (auto *PtrTy = dyn_cast<PointerType>(ICA.getArgTypes()[0]))
              AS = PtrTy->getAddressSpace();
          return thisT()->getMemoryOpCost(*FOp, ICA.getReturnType(), Alignment,
                                          AS, CostKind);
        }
        if (ICA.getID() == Intrinsic::vp_store) {
          Align Alignment;
          if (auto *VPI = dyn_cast_or_null<VPIntrinsic>(ICA.getInst()))
            Alignment = VPI->getPointerAlignment().valueOrOne();
          unsigned AS = 0;
          if (ICA.getArgTypes().size() >= 2)
            if (auto *PtrTy = dyn_cast<PointerType>(ICA.getArgTypes()[1]))
              AS = PtrTy->getAddressSpace();
          return thisT()->getMemoryOpCost(*FOp, ICA.getArgTypes()[0], Alignment,
                                          AS, CostKind);
        }
        if (ICA.getID() == Intrinsic::vp_udiv ||
            ICA.getID() == Intrinsic::vp_sdiv ||
            ICA.getID() == Intrinsic::vp_urem ||
            ICA.getID() == Intrinsic::vp_srem) {
          return thisT()->getArithmeticInstrCost(*FOp, ICA.getReturnType(),
                                                 CostKind);
        }
      }
      if (ICA.getID() == Intrinsic::vp_load_ff) {
        Type *RetTy = ICA.getReturnType();
        Type *DataTy = cast<StructType>(RetTy)->getElementType(0);
        Align Alignment;
        if (auto *VPI = dyn_cast_or_null<VPIntrinsic>(ICA.getInst()))
          Alignment = VPI->getPointerAlignment().valueOrOne();
        return thisT()->getMemIntrinsicInstrCost(
            MemIntrinsicCostAttributes(ICA.getID(), DataTy, Alignment),
            CostKind);
      }
      if (ICA.getID() == Intrinsic::vp_scatter) {
        if (ICA.isTypeBasedOnly()) {
          IntrinsicCostAttributes MaskedScatter(
              *VPIntrinsic::getFunctionalIntrinsicIDForVP(ICA.getID()),
              ICA.getReturnType(), ArrayRef(ICA.getArgTypes()).drop_back(1),
              ICA.getFlags());
          return getTypeBasedIntrinsicInstrCost(MaskedScatter, CostKind);
        }
        Align Alignment;
        if (auto *VPI = dyn_cast_or_null<VPIntrinsic>(ICA.getInst()))
          Alignment = VPI->getPointerAlignment().valueOrOne();
        bool VarMask = isa<Constant>(ICA.getArgs()[2]);
        return thisT()->getMemIntrinsicInstrCost(
            MemIntrinsicCostAttributes(Intrinsic::vp_scatter,
                                       ICA.getArgTypes()[0], ICA.getArgs()[1],
                                       VarMask, Alignment, nullptr),
            CostKind);
      }
      if (ICA.getID() == Intrinsic::vp_gather) {
        if (ICA.isTypeBasedOnly()) {
          IntrinsicCostAttributes MaskedGather(
              *VPIntrinsic::getFunctionalIntrinsicIDForVP(ICA.getID()),
              ICA.getReturnType(), ArrayRef(ICA.getArgTypes()).drop_back(1),
              ICA.getFlags());
          return getTypeBasedIntrinsicInstrCost(MaskedGather, CostKind);
        }
        Align Alignment;
        if (auto *VPI = dyn_cast_or_null<VPIntrinsic>(ICA.getInst()))
          Alignment = VPI->getPointerAlignment().valueOrOne();
        bool VarMask = isa<Constant>(ICA.getArgs()[1]);
        return thisT()->getMemIntrinsicInstrCost(
            MemIntrinsicCostAttributes(Intrinsic::vp_gather,
                                       ICA.getReturnType(), ICA.getArgs()[0],
                                       VarMask, Alignment, nullptr),
            CostKind);
      }
 
      if (ICA.getID() == Intrinsic::vp_merge) {
        TTI::OperandValueInfo OpInfoX, OpInfoY;
        if (!ICA.isTypeBasedOnly()) {
          OpInfoX = TTI::getOperandInfo(ICA.getArgs()[0]);
          OpInfoY = TTI::getOperandInfo(ICA.getArgs()[1]);
        }
        return getCmpSelInstrCost(
            Instruction::Select, ICA.getReturnType(), ICA.getArgTypes()[0],
            CmpInst::BAD_ICMP_PREDICATE, CostKind, OpInfoX, OpInfoY);
      }
 
      std::optional<Intrinsic::ID> FID =
          VPIntrinsic::getFunctionalIntrinsicIDForVP(ICA.getID());
 
      // Not functionally equivalent but close enough for cost modelling.
      if (ICA.getID() == Intrinsic::experimental_vp_reverse)
        FID = Intrinsic::vector_reverse;
 
      if (FID) {
        // Non-vp version will have same arg types except mask and vector
        // length.
        assert(ICA.getArgTypes().size() >= 2 &&
               "Expected VPIntrinsic to have Mask and Vector Length args and "
               "types");
 
        ArrayRef<const Value *> NewArgs = ArrayRef(ICA.getArgs());
        if (!ICA.isTypeBasedOnly())
          NewArgs = NewArgs.drop_back(2);
        ArrayRef<Type *> NewTys = ArrayRef(ICA.getArgTypes()).drop_back(2);
 
        // VPReduction intrinsics have a start value argument that their non-vp
        // counterparts do not have, except for the fadd and fmul non-vp
        // counterpart.
        if (VPReductionIntrinsic::isVPReduction(ICA.getID()) &&
            *FID != Intrinsic::vector_reduce_fadd &&
            *FID != Intrinsic::vector_reduce_fmul) {
          if (!ICA.isTypeBasedOnly())
            NewArgs = NewArgs.drop_front();
          NewTys = NewTys.drop_front();
        }
 
        IntrinsicCostAttributes NewICA(*FID, ICA.getReturnType(), NewArgs,
                                       NewTys, ICA.getFlags());
        return thisT()->getIntrinsicInstrCost(NewICA, CostKind);
      }
    }
 
    if (ICA.isTypeBasedOnly())
      return getTypeBasedIntrinsicInstrCost(ICA, CostKind);
 
    Type *RetTy = ICA.getReturnType();
 
    ElementCount RetVF = isVectorizedTy(RetTy) ? getVectorizedTypeVF(RetTy)
                                               : ElementCount::getFixed(1);
 
    const IntrinsicInst *I = ICA.getInst();
    const SmallVectorImpl<const Value *> &Args = ICA.getArgs();
    FastMathFlags FMF = ICA.getFlags();
    switch (IID) {
    default:
      break;
 
    case Intrinsic::powi:
      if (auto *RHSC = dyn_cast<ConstantInt>(Args[1])) {
        bool ShouldOptForSize = I->getParent()->getParent()->hasOptSize();
        if (getTLI()->isBeneficialToExpandPowI(RHSC->getSExtValue(),
                                               ShouldOptForSize)) {
          // The cost is modeled on the expansion performed by ExpandPowI in
          // SelectionDAGBuilder.
          APInt Exponent = RHSC->getValue().abs();
          unsigned ActiveBits = Exponent.getActiveBits();
          unsigned PopCount = Exponent.popcount();
          InstructionCost Cost = (ActiveBits + PopCount - 2) *
                                 thisT()->getArithmeticInstrCost(
                                     Instruction::FMul, RetTy, CostKind);
          if (RHSC->isNegative())
            Cost += thisT()->getArithmeticInstrCost(Instruction::FDiv, RetTy,
                                                    CostKind);
          return Cost;
        }
      }
      break;
    case Intrinsic::cttz:
      // FIXME: If necessary, this should go in target-specific overrides.
      if (RetVF.isScalar() && getTLI()->isCheapToSpeculateCttz(RetTy))
        return TargetTransformInfo::TCC_Basic;
      break;
 
    case Intrinsic::ctlz:
      // FIXME: If necessary, this should go in target-specific overrides.
      if (RetVF.isScalar() && getTLI()->isCheapToSpeculateCtlz(RetTy))
        return TargetTransformInfo::TCC_Basic;
      break;
 
    case Intrinsic::memcpy:
      return thisT()->getMemcpyCost(ICA.getInst());
 
    case Intrinsic::masked_scatter: {
      const Value *Mask = Args[2];
      bool VarMask = !isa<Constant>(Mask);
      Align Alignment = I->getParamAlign(1).valueOrOne();
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(Intrinsic::masked_scatter,
                                     ICA.getArgTypes()[0], Args[1], VarMask,
                                     Alignment, I),
          CostKind);
    }
    case Intrinsic::masked_gather: {
      const Value *Mask = Args[1];
      bool VarMask = !isa<Constant>(Mask);
      Align Alignment = I->getParamAlign(0).valueOrOne();
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(Intrinsic::masked_gather, RetTy, Args[0],
                                     VarMask, Alignment, I),
          CostKind);
    }
    case Intrinsic::masked_compressstore: {
      const Value *Data = Args[0];
      const Value *Mask = Args[2];
      Align Alignment = I->getParamAlign(1).valueOrOne();
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, Data->getType(), !isa<Constant>(Mask),
                                     Alignment, I),
          CostKind);
    }
    case Intrinsic::masked_expandload: {
      const Value *Mask = Args[1];
      Align Alignment = I->getParamAlign(0).valueOrOne();
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, RetTy, !isa<Constant>(Mask),
                                     Alignment, I),
          CostKind);
    }
    case Intrinsic::experimental_vp_strided_store: {
      const Value *Data = Args[0];
      const Value *Ptr = Args[1];
      const Value *Stride = Args[2];
      const Value *Mask = Args[3];
      const Value *EVL = Args[4];
      bool VarMask = !isa<Constant>(Mask) || !isa<Constant>(EVL);
      Type *EltTy = cast<VectorType>(Data->getType())->getElementType();
      Align Alignment =
          I->getParamAlign(1).value_or(thisT()->DL.getABITypeAlign(EltTy));
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, Data->getType(), Ptr, VarMask,
                                     Alignment, I, Stride),
          CostKind);
    }
    case Intrinsic::experimental_vp_strided_load: {
      const Value *Ptr = Args[0];
      const Value *Stride = Args[1];
      const Value *Mask = Args[2];
      const Value *EVL = Args[3];
      bool VarMask = !isa<Constant>(Mask) || !isa<Constant>(EVL);
      Type *EltTy = cast<VectorType>(RetTy)->getElementType();
      Align Alignment =
          I->getParamAlign(0).value_or(thisT()->DL.getABITypeAlign(EltTy));
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, RetTy, Ptr, VarMask, Alignment, I,
                                     Stride),
          CostKind);
    }
    case Intrinsic::stepvector: {
      if (isa<ScalableVectorType>(RetTy))
        return BaseT::getIntrinsicInstrCost(ICA, CostKind);
      // The cost of materialising a constant integer vector.
      return TargetTransformInfo::TCC_Basic;
    }
    case Intrinsic::vector_extract: {
      // FIXME: Handle case where a scalable vector is extracted from a scalable
      // vector
      if (isa<ScalableVectorType>(RetTy))
        return BaseT::getIntrinsicInstrCost(ICA, CostKind);
      unsigned Index = cast<ConstantInt>(Args[1])->getZExtValue();
      return thisT()->getShuffleCost(
          TTI::SK_ExtractSubvector, cast<VectorType>(RetTy),
          cast<VectorType>(Args[0]->getType()), CostKind, {}, Index,
          cast<VectorType>(RetTy));
    }
    case Intrinsic::vector_insert: {
      // FIXME: Handle case where a scalable vector is inserted into a scalable
      // vector
      if (isa<ScalableVectorType>(Args[1]->getType()))
        return BaseT::getIntrinsicInstrCost(ICA, CostKind);
      unsigned Index = cast<ConstantInt>(Args[2])->getZExtValue();
      return thisT()->getShuffleCost(
          TTI::SK_InsertSubvector, cast<VectorType>(RetTy),
          cast<VectorType>(Args[0]->getType()), CostKind, {}, Index,
          cast<VectorType>(Args[1]->getType()));
    }
    case Intrinsic::vector_splice_left:
    case Intrinsic::vector_splice_right: {
      auto *COffset = dyn_cast<ConstantInt>(Args[2]);
      if (!COffset)
        break;
      unsigned Index = COffset->getZExtValue();
      return thisT()->getShuffleCost(
          TTI::SK_Splice, cast<VectorType>(RetTy),
          cast<VectorType>(Args[0]->getType()), CostKind, {},
          IID == Intrinsic::vector_splice_left ? Index : -Index,
          cast<VectorType>(RetTy));
    }
    case Intrinsic::vector_reduce_add:
    case Intrinsic::vector_reduce_mul:
    case Intrinsic::vector_reduce_and:
    case Intrinsic::vector_reduce_or:
    case Intrinsic::vector_reduce_xor:
    case Intrinsic::vector_reduce_smax:
    case Intrinsic::vector_reduce_smin:
    case Intrinsic::vector_reduce_fmax:
    case Intrinsic::vector_reduce_fmin:
    case Intrinsic::vector_reduce_fmaximum:
    case Intrinsic::vector_reduce_fminimum:
    case Intrinsic::vector_reduce_fmaximumnum:
    case Intrinsic::vector_reduce_fminimumnum:
    case Intrinsic::vector_reduce_umax:
    case Intrinsic::vector_reduce_umin: {
      IntrinsicCostAttributes Attrs(IID, RetTy, Args[0]->getType(), FMF, I, 1);
      return getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
    }
    case Intrinsic::vector_reduce_fadd:
    case Intrinsic::vector_reduce_fmul: {
      IntrinsicCostAttributes Attrs(
          IID, RetTy, {Args[0]->getType(), Args[1]->getType()}, FMF, I, 1);
      return getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
    }
    case Intrinsic::fshl:
    case Intrinsic::fshr: {
      const Value *X = Args[0];
      const Value *Y = Args[1];
      const Value *Z = Args[2];
      const TTI::OperandValueInfo OpInfoX = TTI::getOperandInfo(X);
      const TTI::OperandValueInfo OpInfoY = TTI::getOperandInfo(Y);
      const TTI::OperandValueInfo OpInfoZ = TTI::getOperandInfo(Z);
 
      // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
      // fshr: (X << (BW - (Z % BW))) | (Y >> (Z % BW))
      InstructionCost Cost = 0;
      Cost +=
          thisT()->getArithmeticInstrCost(BinaryOperator::Or, RetTy, CostKind);
      Cost += thisT()->getArithmeticInstrCost(
          BinaryOperator::Shl, RetTy, CostKind, OpInfoX,
          {OpInfoZ.Kind, TTI::OP_None});
      Cost += thisT()->getArithmeticInstrCost(
          BinaryOperator::LShr, RetTy, CostKind, OpInfoY,
          {OpInfoZ.Kind, TTI::OP_None});
 
      if (!OpInfoZ.isConstant()) {
        Cost += thisT()->getArithmeticInstrCost(BinaryOperator::Sub, RetTy,
                                                CostKind);
        // Non-constant shift amounts requires a modulo. If the typesize is a
        // power-2 then this will be converted to an and, otherwise it will use
        // a urem.
        Cost += thisT()->getArithmeticInstrCost(
            isPowerOf2_32(RetTy->getScalarSizeInBits()) ? BinaryOperator::And
                                                        : BinaryOperator::URem,
            RetTy, CostKind, OpInfoZ,
            {TTI::OK_UniformConstantValue, TTI::OP_None});
        // For non-rotates (X != Y) we must add shift-by-zero handling costs.
        if (X != Y) {
          Type *CondTy = RetTy->getWithNewBitWidth(1);
          Cost += thisT()->getCmpSelInstrCost(
              BinaryOperator::ICmp, RetTy, CondTy, CmpInst::ICMP_EQ, CostKind);
          Cost +=
              thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
                                          CmpInst::ICMP_EQ, CostKind);
        }
      }
      return Cost;
    }
    case Intrinsic::experimental_cttz_elts: {
      EVT ArgType = getTLI()->getValueType(DL, ICA.getArgTypes()[0], true);
 
      // TODO: The costs below reflect the expansion code in
      // TargetLowering::expandCttzElts, but we may want to sacrifice some
      // accuracy in favour of compile time.
 
      // Find the smallest "sensible" element type to use for the expansion.
      bool ZeroIsPoison = !cast<ConstantInt>(Args[1])->isZero();
      ConstantRange VScaleRange(APInt(64, 1), APInt::getZero(64));
      if (isa<ScalableVectorType>(ICA.getArgTypes()[0]) && I && I->getCaller())
        VScaleRange = getVScaleRange(I->getCaller(), 64);
 
      unsigned EltWidth = getTLI()->getBitWidthForCttzElements(
          getTLI()->getValueType(DL, RetTy), ArgType.getVectorElementCount(),
          ZeroIsPoison, &VScaleRange);
      Type *NewEltTy = IntegerType::getIntNTy(RetTy->getContext(), EltWidth);
 
      // Create the new vector type & get the vector length
      Type *NewVecTy = VectorType::get(
          NewEltTy, cast<VectorType>(Args[0]->getType())->getElementCount());
 
      IntrinsicCostAttributes StepVecAttrs(Intrinsic::stepvector, NewVecTy, {},
                                           FMF);
      InstructionCost Cost =
          thisT()->getIntrinsicInstrCost(StepVecAttrs, CostKind);
 
      Cost +=
          thisT()->getArithmeticInstrCost(Instruction::Sub, NewVecTy, CostKind);
      Cost += thisT()->getCastInstrCost(Instruction::SExt, NewVecTy,
                                        Args[0]->getType(),
                                        TTI::CastContextHint::None, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(Instruction::And, NewVecTy, CostKind);
 
      IntrinsicCostAttributes ReducAttrs(Intrinsic::vector_reduce_umax,
                                         NewEltTy, NewVecTy, FMF, I, 1);
      Cost += thisT()->getTypeBasedIntrinsicInstrCost(ReducAttrs, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(Instruction::Sub, NewEltTy, CostKind);
 
      return Cost;
    }
    case Intrinsic::get_active_lane_mask:
    case Intrinsic::experimental_vector_match:
    case Intrinsic::experimental_vector_histogram_add:
    case Intrinsic::experimental_vector_histogram_uadd_sat:
    case Intrinsic::experimental_vector_histogram_umax:
    case Intrinsic::experimental_vector_histogram_umin:
    case Intrinsic::masked_udiv:
    case Intrinsic::masked_sdiv:
    case Intrinsic::masked_urem:
    case Intrinsic::masked_srem:
      return thisT()->getTypeBasedIntrinsicInstrCost(ICA, CostKind);
    case Intrinsic::modf:
    case Intrinsic::sincos:
    case Intrinsic::sincospi: {
      std::optional<unsigned> CallRetElementIndex;
      // The first element of the modf result is returned by value in the
      // libcall.
      if (ICA.getID() == Intrinsic::modf)
        CallRetElementIndex = 0;
 
      if (auto Cost = getMultipleResultIntrinsicVectorLibCallCost(
              ICA, CostKind, CallRetElementIndex))
        return *Cost;
      // Otherwise, fallback to default scalarization cost.
      break;
    }
    case Intrinsic::loop_dependence_war_mask:
    case Intrinsic::loop_dependence_raw_mask: {
      // Compute the cost of the expanded version of these intrinsics:
      //
      // The possible expansions are...
      //
      // loop_dependence_war_mask:
      //   diff = (addrB - addrA) / eltSize
      //   cmp = icmp sle diff, 0
      //   upper_bound = select cmp, -1, diff
      //   mask = get_active_lane_mask 0, upper_bound
      //
      // loop_dependence_raw_mask:
      //   diff = (abs(addrB - addrA)) / eltSize
      //   cmp = icmp eq diff, 0
      //   upper_bound = select cmp, -1, diff
      //   mask = get_active_lane_mask 0, upper_bound
      //
      Type *AddrTy = ICA.getArgTypes()[0];
      bool IsReadAfterWrite = IID == Intrinsic::loop_dependence_raw_mask;
 
      InstructionCost Cost =
          thisT()->getArithmeticInstrCost(Instruction::Sub, AddrTy, CostKind);
      if (IsReadAfterWrite) {
        IntrinsicCostAttributes AbsAttrs(Intrinsic::abs, AddrTy, {AddrTy}, {});
        Cost += thisT()->getIntrinsicInstrCost(AbsAttrs, CostKind);
      }
 
      TTI::OperandValueInfo EltSizeOpInfo =
          TTI::getOperandInfo(ICA.getArgs()[2]);
      Cost += thisT()->getArithmeticInstrCost(Instruction::SDiv, AddrTy,
                                              CostKind, {}, EltSizeOpInfo);
 
      Type *CondTy = IntegerType::getInt1Ty(RetTy->getContext());
      CmpInst::Predicate Pred =
          IsReadAfterWrite ? CmpInst::ICMP_EQ : CmpInst::ICMP_SLE;
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, CondTy, AddrTy,
                                          Pred, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::Select, AddrTy,
                                          CondTy, Pred, CostKind);
 
      IntrinsicCostAttributes Attrs(Intrinsic::get_active_lane_mask, RetTy,
                                    {AddrTy, AddrTy}, FMF);
      Cost += thisT()->getIntrinsicInstrCost(Attrs, CostKind);
      return Cost;
    }
    }
 
    // Assume that we need to scalarize this intrinsic.)
    // Compute the scalarization overhead based on Args for a vector
    // intrinsic.
    InstructionCost ScalarizationCost = InstructionCost::getInvalid();
    if (RetVF.isVector() && !RetVF.isScalable()) {
      ScalarizationCost = 0;
      if (!RetTy->isVoidTy()) {
        for (Type *VectorTy : getContainedTypes(RetTy)) {
          ScalarizationCost += getScalarizationOverhead(
              cast<VectorType>(VectorTy),
              /*Insert=*/true, /*Extract=*/false, CostKind);
        }
      }
      ScalarizationCost += getOperandsScalarizationOverhead(
          filterConstantAndDuplicatedOperands(Args, ICA.getArgTypes()),
          CostKind);
    }
 
    IntrinsicCostAttributes Attrs(IID, RetTy, ICA.getArgTypes(), FMF, I,
                                  ScalarizationCost);
    return thisT()->getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
  }
 
  /// Get intrinsic cost based on argument types.
  /// If ScalarizationCostPassed is std::numeric_limits<unsigned>::max(), the
  /// cost of scalarizing the arguments and the return value will be computed
  /// based on types.
  InstructionCost
  getTypeBasedIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
                                 TTI::TargetCostKind CostKind) const {
    Intrinsic::ID IID = ICA.getID();
    Type *RetTy = ICA.getReturnType();
    const SmallVectorImpl<Type *> &Tys = ICA.getArgTypes();
    FastMathFlags FMF = ICA.getFlags();
    InstructionCost ScalarizationCostPassed = ICA.getScalarizationCost();
    bool SkipScalarizationCost = ICA.skipScalarizationCost();
 
    VectorType *VecOpTy = nullptr;
    if (!Tys.empty()) {
      // The vector reduction operand is operand 0 except for fadd/fmul.
      // Their operand 0 is a scalar start value, so the vector op is operand 1.
      unsigned VecTyIndex = 0;
      if (IID == Intrinsic::vector_reduce_fadd ||
          IID == Intrinsic::vector_reduce_fmul)
        VecTyIndex = 1;
      assert(Tys.size() > VecTyIndex && "Unexpected IntrinsicCostAttributes");
      VecOpTy = dyn_cast<VectorType>(Tys[VecTyIndex]);
    }
 
    // Library call cost - other than size, make it expensive.
    unsigned SingleCallCost = CostKind == TTI::TCK_CodeSize ? 1 : 10;
    unsigned ISD = 0;
    switch (IID) {
    default: {
      // Scalable vectors cannot be scalarized, so return Invalid.
      if (isa<ScalableVectorType>(RetTy) || any_of(Tys, [](const Type *Ty) {
            return isa<ScalableVectorType>(Ty);
          }))
        return InstructionCost::getInvalid();
 
      // Assume that we need to scalarize this intrinsic.
      InstructionCost ScalarizationCost =
          SkipScalarizationCost ? ScalarizationCostPassed : 0;
      unsigned ScalarCalls = 1;
      Type *ScalarRetTy = RetTy;
      if (auto *RetVTy = dyn_cast<VectorType>(RetTy)) {
        if (!SkipScalarizationCost)
          ScalarizationCost = getScalarizationOverhead(
              RetVTy, /*Insert*/ true, /*Extract*/ false, CostKind);
        ScalarCalls = std::max(ScalarCalls,
                               cast<FixedVectorType>(RetVTy)->getNumElements());
        ScalarRetTy = RetTy->getScalarType();
      }
      SmallVector<Type *, 4> ScalarTys;
      for (Type *Ty : Tys) {
        if (auto *VTy = dyn_cast<VectorType>(Ty)) {
          if (!SkipScalarizationCost)
            ScalarizationCost += getScalarizationOverhead(
                VTy, /*Insert*/ false, /*Extract*/ true, CostKind);
          ScalarCalls = std::max(ScalarCalls,
                                 cast<FixedVectorType>(VTy)->getNumElements());
          Ty = Ty->getScalarType();
        }
        ScalarTys.push_back(Ty);
      }
      if (ScalarCalls == 1)
        return 1; // Return cost of a scalar intrinsic. Assume it to be cheap.
 
      IntrinsicCostAttributes ScalarAttrs(IID, ScalarRetTy, ScalarTys, FMF);
      InstructionCost ScalarCost =
          thisT()->getIntrinsicInstrCost(ScalarAttrs, CostKind);
 
      return ScalarCalls * ScalarCost + ScalarizationCost;
    }
    // Look for intrinsics that can be lowered directly or turned into a scalar
    // intrinsic call.
    case Intrinsic::sqrt:
      ISD = ISD::FSQRT;
      break;
    case Intrinsic::sin:
      ISD = ISD::FSIN;
      break;
    case Intrinsic::cos:
      ISD = ISD::FCOS;
      break;
    case Intrinsic::sincos:
      ISD = ISD::FSINCOS;
      break;
    case Intrinsic::sincospi:
      ISD = ISD::FSINCOSPI;
      break;
    case Intrinsic::modf:
      ISD = ISD::FMODF;
      break;
    case Intrinsic::tan:
      ISD = ISD::FTAN;
      break;
    case Intrinsic::asin:
      ISD = ISD::FASIN;
      break;
    case Intrinsic::acos:
      ISD = ISD::FACOS;
      break;
    case Intrinsic::atan:
      ISD = ISD::FATAN;
      break;
    case Intrinsic::atan2:
      ISD = ISD::FATAN2;
      break;
    case Intrinsic::sinh:
      ISD = ISD::FSINH;
      break;
    case Intrinsic::cosh:
      ISD = ISD::FCOSH;
      break;
    case Intrinsic::tanh:
      ISD = ISD::FTANH;
      break;
    case Intrinsic::exp:
      ISD = ISD::FEXP;
      break;
    case Intrinsic::exp2:
      ISD = ISD::FEXP2;
      break;
    case Intrinsic::exp10:
      ISD = ISD::FEXP10;
      break;
    case Intrinsic::log:
      ISD = ISD::FLOG;
      break;
    case Intrinsic::log10:
      ISD = ISD::FLOG10;
      break;
    case Intrinsic::log2:
      ISD = ISD::FLOG2;
      break;
    case Intrinsic::ldexp:
      ISD = ISD::FLDEXP;
      break;
    case Intrinsic::fabs:
      ISD = ISD::FABS;
      break;
    case Intrinsic::canonicalize:
      ISD = ISD::FCANONICALIZE;
      break;
    case Intrinsic::minnum:
      ISD = ISD::FMINNUM;
      break;
    case Intrinsic::maxnum:
      ISD = ISD::FMAXNUM;
      break;
    case Intrinsic::minimum:
      ISD = ISD::FMINIMUM;
      break;
    case Intrinsic::maximum:
      ISD = ISD::FMAXIMUM;
      break;
    case Intrinsic::minimumnum:
      ISD = ISD::FMINIMUMNUM;
      break;
    case Intrinsic::maximumnum:
      ISD = ISD::FMAXIMUMNUM;
      break;
    case Intrinsic::copysign:
      ISD = ISD::FCOPYSIGN;
      break;
    case Intrinsic::floor:
      ISD = ISD::FFLOOR;
      break;
    case Intrinsic::ceil:
      ISD = ISD::FCEIL;
      break;
    case Intrinsic::trunc:
      ISD = ISD::FTRUNC;
      break;
    case Intrinsic::nearbyint:
      ISD = ISD::FNEARBYINT;
      break;
    case Intrinsic::rint:
      ISD = ISD::FRINT;
      break;
    case Intrinsic::lrint:
      ISD = ISD::LRINT;
      break;
    case Intrinsic::llrint:
      ISD = ISD::LLRINT;
      break;
    case Intrinsic::round:
      ISD = ISD::FROUND;
      break;
    case Intrinsic::roundeven:
      ISD = ISD::FROUNDEVEN;
      break;
    case Intrinsic::lround:
      ISD = ISD::LROUND;
      break;
    case Intrinsic::llround:
      ISD = ISD::LLROUND;
      break;
    case Intrinsic::pow:
      ISD = ISD::FPOW;
      break;
    case Intrinsic::fma:
      ISD = ISD::FMA;
      break;
    case Intrinsic::fmuladd:
      ISD = ISD::FMA;
      break;
    case Intrinsic::experimental_constrained_fmuladd:
      ISD = ISD::STRICT_FMA;
      break;
    // FIXME: We should return 0 whenever getIntrinsicCost == TCC_Free.
    case Intrinsic::lifetime_start:
    case Intrinsic::lifetime_end:
    case Intrinsic::sideeffect:
    case Intrinsic::pseudoprobe:
    case Intrinsic::arithmetic_fence:
      return 0;
    case Intrinsic::masked_store: {
      Type *Ty = Tys[0];
      Align TyAlign = thisT()->DL.getABITypeAlign(Ty);
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, Ty, TyAlign, 0), CostKind);
    }
    case Intrinsic::masked_load: {
      Type *Ty = RetTy;
      Align TyAlign = thisT()->DL.getABITypeAlign(Ty);
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, Ty, TyAlign, 0), CostKind);
    }
    case Intrinsic::speculative_load: {
      const IntrinsicInst *I = ICA.getInst();
      Align Alignment = I ? I->getParamAlign(0).valueOrOne() : Align(1);
      unsigned AS = Tys[0]->getPointerAddressSpace();
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, RetTy, Alignment, AS), CostKind);
    }
    case Intrinsic::experimental_vp_strided_store: {
      auto *Ty = cast<VectorType>(ICA.getArgTypes()[0]);
      Align Alignment = thisT()->DL.getABITypeAlign(Ty->getElementType());
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, Ty, /*Ptr=*/nullptr,
                                     /*VariableMask=*/true, Alignment,
                                     ICA.getInst()),
          CostKind);
    }
    case Intrinsic::experimental_vp_strided_load: {
      auto *Ty = cast<VectorType>(ICA.getReturnType());
      Align Alignment = thisT()->DL.getABITypeAlign(Ty->getElementType());
      return thisT()->getMemIntrinsicInstrCost(
          MemIntrinsicCostAttributes(IID, Ty, /*Ptr=*/nullptr,
                                     /*VariableMask=*/true, Alignment,
                                     ICA.getInst()),
          CostKind);
    }
    case Intrinsic::vector_reduce_add:
    case Intrinsic::vector_reduce_mul:
    case Intrinsic::vector_reduce_and:
    case Intrinsic::vector_reduce_or:
    case Intrinsic::vector_reduce_xor:
      return thisT()->getArithmeticReductionCost(
          getArithmeticReductionInstruction(IID), VecOpTy, std::nullopt,
          CostKind);
    case Intrinsic::vector_reduce_fadd:
    case Intrinsic::vector_reduce_fmul:
      return thisT()->getArithmeticReductionCost(
          getArithmeticReductionInstruction(IID), VecOpTy, FMF, CostKind);
    case Intrinsic::vector_reduce_smax:
    case Intrinsic::vector_reduce_smin:
    case Intrinsic::vector_reduce_umax:
    case Intrinsic::vector_reduce_umin:
    case Intrinsic::vector_reduce_fmax:
    case Intrinsic::vector_reduce_fmin:
    case Intrinsic::vector_reduce_fmaximum:
    case Intrinsic::vector_reduce_fminimum:
    case Intrinsic::vector_reduce_fmaximumnum:
    case Intrinsic::vector_reduce_fminimumnum:
      return thisT()->getMinMaxReductionCost(getMinMaxReductionIntrinsicOp(IID),
                                             VecOpTy, ICA.getFlags(), CostKind);
    case Intrinsic::experimental_vector_match: {
      auto *SearchTy = cast<VectorType>(ICA.getArgTypes()[0]);
      auto *NeedleTy = cast<FixedVectorType>(ICA.getArgTypes()[1]);
      unsigned SearchSize = NeedleTy->getNumElements();
 
      // Approximate the cost based on the expansion code in
      // TargetLowering::expandVectorMatch.
      InstructionCost Cost = 0;
      Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, NeedleTy,
                                          CostKind, 1, nullptr, nullptr);
      Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, SearchTy,
                                          CostKind, 0, nullptr, nullptr);
      Cost += thisT()->getShuffleCost(TTI::SK_Broadcast, SearchTy, SearchTy,
                                      CostKind, {}, 0, nullptr);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, SearchTy, RetTy,
                                          CmpInst::ICMP_EQ, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(BinaryOperator::Or, RetTy, CostKind);
      Cost *= SearchSize;
      Cost +=
          thisT()->getArithmeticInstrCost(BinaryOperator::And, RetTy, CostKind);
      return Cost;
    }
    case Intrinsic::vector_reverse:
      return thisT()->getShuffleCost(TTI::SK_Reverse, cast<VectorType>(RetTy),
                                     cast<VectorType>(ICA.getArgTypes()[0]),
                                     CostKind, {}, 0, cast<VectorType>(RetTy));
    case Intrinsic::experimental_vector_histogram_add:
    case Intrinsic::experimental_vector_histogram_uadd_sat:
    case Intrinsic::experimental_vector_histogram_umax:
    case Intrinsic::experimental_vector_histogram_umin: {
      FixedVectorType *PtrsTy = dyn_cast<FixedVectorType>(ICA.getArgTypes()[0]);
      Type *EltTy = ICA.getArgTypes()[1];
 
      // Targets with scalable vectors must handle this on their own.
      if (!PtrsTy)
        return InstructionCost::getInvalid();
 
      Align Alignment = thisT()->DL.getABITypeAlign(EltTy);
      InstructionCost Cost = 0;
      Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, PtrsTy,
                                          CostKind, 1, nullptr, nullptr);
      Cost += thisT()->getMemoryOpCost(Instruction::Load, EltTy, Alignment, 0,
                                       CostKind);
      switch (IID) {
      default:
        llvm_unreachable("Unhandled histogram update operation.");
      case Intrinsic::experimental_vector_histogram_add:
        Cost +=
            thisT()->getArithmeticInstrCost(Instruction::Add, EltTy, CostKind);
        break;
      case Intrinsic::experimental_vector_histogram_uadd_sat: {
        IntrinsicCostAttributes UAddSat(Intrinsic::uadd_sat, EltTy, {EltTy});
        Cost += thisT()->getIntrinsicInstrCost(UAddSat, CostKind);
        break;
      }
      case Intrinsic::experimental_vector_histogram_umax: {
        IntrinsicCostAttributes UMax(Intrinsic::umax, EltTy, {EltTy});
        Cost += thisT()->getIntrinsicInstrCost(UMax, CostKind);
        break;
      }
      case Intrinsic::experimental_vector_histogram_umin: {
        IntrinsicCostAttributes UMin(Intrinsic::umin, EltTy, {EltTy});
        Cost += thisT()->getIntrinsicInstrCost(UMin, CostKind);
        break;
      }
      }
      Cost += thisT()->getMemoryOpCost(Instruction::Store, EltTy, Alignment, 0,
                                       CostKind);
      Cost *= PtrsTy->getNumElements();
      return Cost;
    }
    case Intrinsic::get_active_lane_mask: {
      Type *ArgTy = ICA.getArgTypes()[0];
      EVT ResVT = getTLI()->getValueType(DL, RetTy, true);
      EVT ArgVT = getTLI()->getValueType(DL, ArgTy, true);
 
      // If we're not expanding the intrinsic then we assume this is cheap
      // to implement.
      if (!getTLI()->shouldExpandGetActiveLaneMask(ResVT, ArgVT))
        return getTypeLegalizationCost(RetTy).first;
 
      // Create the expanded types that will be used to calculate the uadd_sat
      // operation.
      Type *ExpRetTy =
          VectorType::get(ArgTy, cast<VectorType>(RetTy)->getElementCount());
      IntrinsicCostAttributes Attrs(Intrinsic::uadd_sat, ExpRetTy, {}, FMF);
      InstructionCost Cost =
          thisT()->getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, ExpRetTy, RetTy,
                                          CmpInst::ICMP_ULT, CostKind);
      return Cost;
    }
    case Intrinsic::experimental_memset_pattern:
      // This cost is set to match the cost of the memset_pattern16 libcall.
      // It should likely be re-evaluated after migration to this intrinsic
      // is complete.
      return TTI::TCC_Basic * 4;
    case Intrinsic::abs:
      ISD = ISD::ABS;
      break;
    case Intrinsic::fshl:
      ISD = ISD::FSHL;
      break;
    case Intrinsic::fshr:
      ISD = ISD::FSHR;
      break;
    case Intrinsic::smax:
      ISD = ISD::SMAX;
      break;
    case Intrinsic::smin:
      ISD = ISD::SMIN;
      break;
    case Intrinsic::umax:
      ISD = ISD::UMAX;
      break;
    case Intrinsic::umin:
      ISD = ISD::UMIN;
      break;
    case Intrinsic::sadd_sat:
      ISD = ISD::SADDSAT;
      break;
    case Intrinsic::ssub_sat:
      ISD = ISD::SSUBSAT;
      break;
    case Intrinsic::uadd_sat:
      ISD = ISD::UADDSAT;
      break;
    case Intrinsic::usub_sat:
      ISD = ISD::USUBSAT;
      break;
    case Intrinsic::smul_fix:
      ISD = ISD::SMULFIX;
      break;
    case Intrinsic::umul_fix:
      ISD = ISD::UMULFIX;
      break;
    case Intrinsic::sadd_with_overflow:
      ISD = ISD::SADDO;
      break;
    case Intrinsic::ssub_with_overflow:
      ISD = ISD::SSUBO;
      break;
    case Intrinsic::uadd_with_overflow:
      ISD = ISD::UADDO;
      break;
    case Intrinsic::usub_with_overflow:
      ISD = ISD::USUBO;
      break;
    case Intrinsic::smul_with_overflow:
      ISD = ISD::SMULO;
      break;
    case Intrinsic::umul_with_overflow:
      ISD = ISD::UMULO;
      break;
    case Intrinsic::fptosi_sat:
    case Intrinsic::fptoui_sat: {
      std::pair<InstructionCost, MVT> SrcLT = getTypeLegalizationCost(Tys[0]);
      std::pair<InstructionCost, MVT> RetLT = getTypeLegalizationCost(RetTy);
 
      // For cast instructions, types are different between source and
      // destination. Also need to check if the source type can be legalize.
      if (!SrcLT.first.isValid() || !RetLT.first.isValid())
        return InstructionCost::getInvalid();
      ISD = IID == Intrinsic::fptosi_sat ? ISD::FP_TO_SINT_SAT
                                         : ISD::FP_TO_UINT_SAT;
      break;
    }
    case Intrinsic::ctpop:
      ISD = ISD::CTPOP;
      // In case of legalization use TCC_Expensive. This is cheaper than a
      // library call but still not a cheap instruction.
      SingleCallCost = TargetTransformInfo::TCC_Expensive;
      break;
    case Intrinsic::ctlz:
      ISD = ISD::CTLZ;
      break;
    case Intrinsic::cttz:
      ISD = ISD::CTTZ;
      break;
    case Intrinsic::bswap:
      ISD = ISD::BSWAP;
      break;
    case Intrinsic::bitreverse:
      ISD = ISD::BITREVERSE;
      break;
    case Intrinsic::ucmp:
      ISD = ISD::UCMP;
      break;
    case Intrinsic::scmp:
      ISD = ISD::SCMP;
      break;
    case Intrinsic::clmul:
      ISD = ISD::CLMUL;
      break;
    case Intrinsic::smulh:
      ISD = ISD::MULHS;
      break;
    case Intrinsic::umulh:
      ISD = ISD::MULHU;
      break;
    case Intrinsic::masked_udiv:
    case Intrinsic::masked_sdiv:
    case Intrinsic::masked_urem:
    case Intrinsic::masked_srem: {
      unsigned UnmaskedOpc;
      switch (IID) {
      case Intrinsic::masked_udiv:
        ISD = ISD::MASKED_UDIV;
        UnmaskedOpc = Instruction::UDiv;
        break;
      case Intrinsic::masked_sdiv:
        ISD = ISD::MASKED_SDIV;
        UnmaskedOpc = Instruction::SDiv;
        break;
      case Intrinsic::masked_urem:
        ISD = ISD::MASKED_UREM;
        UnmaskedOpc = Instruction::URem;
        break;
      case Intrinsic::masked_srem:
        ISD = ISD::MASKED_SREM;
        UnmaskedOpc = Instruction::SRem;
        break;
      default:
        llvm_unreachable("Unexpected intrinsic ID");
      }
      InstructionCost Cost =
          thisT()->getArithmeticInstrCost(UnmaskedOpc, RetTy, CostKind);
 
      // Expansion generates a (select %mask, %rhs, 1) for the divisor.
      MVT LT = getTypeLegalizationCost(RetTy).second;
      if (!getTLI()->isOperationLegalOrCustom(ISD, LT)) {
        Type *CondTy = cast<VectorType>(RetTy)->getWithNewType(
            IntegerType::getInt1Ty(RetTy->getContext()));
        Cost += thisT()->getCmpSelInstrCost(
            BinaryOperator::Select, RetTy, CondTy, CmpInst::BAD_ICMP_PREDICATE,
            CostKind, {}, {TTI::OK_UniformConstantValue, TTI::OP_PowerOf2});
      }
 
      return Cost;
    }
    }
 
    auto *ST = dyn_cast<StructType>(RetTy);
    Type *LegalizeTy = ST ? ST->getContainedType(0) : RetTy;
    std::pair<InstructionCost, MVT> LT = getTypeLegalizationCost(LegalizeTy);
 
    const TargetLoweringBase *TLI = getTLI();
 
    if (TLI->isOperationLegalOrPromote(ISD, LT.second)) {
      if (IID == Intrinsic::fabs && LT.second.isFloatingPoint() &&
          TLI->isFAbsFree(LT.second)) {
        return 0;
      }
 
      // The operation is legal. Assume it costs 1.
      // If the type is split to multiple registers, assume that there is some
      // overhead to this.
      // TODO: Once we have extract/insert subvector cost we need to use them.
      if (LT.first > 1)
        return (LT.first * 2);
      else
        return (LT.first * 1);
    } else if (TLI->isOperationCustom(ISD, LT.second)) {
      // If the operation is custom lowered then assume
      // that the code is twice as expensive.
      return (LT.first * 2);
    }
 
    switch (IID) {
    case Intrinsic::fmuladd: {
      // If we can't lower fmuladd into an FMA estimate the cost as a floating
      // point mul followed by an add.
 
      return thisT()->getArithmeticInstrCost(BinaryOperator::FMul, RetTy,
                                             CostKind) +
             thisT()->getArithmeticInstrCost(BinaryOperator::FAdd, RetTy,
                                             CostKind);
    }
    case Intrinsic::experimental_constrained_fmuladd: {
      IntrinsicCostAttributes FMulAttrs(
        Intrinsic::experimental_constrained_fmul, RetTy, Tys);
      IntrinsicCostAttributes FAddAttrs(
        Intrinsic::experimental_constrained_fadd, RetTy, Tys);
      return thisT()->getIntrinsicInstrCost(FMulAttrs, CostKind) +
             thisT()->getIntrinsicInstrCost(FAddAttrs, CostKind);
    }
    case Intrinsic::smin:
    case Intrinsic::smax:
    case Intrinsic::umin:
    case Intrinsic::umax: {
      // minmax(X,Y) = select(icmp(X,Y),X,Y)
      Type *CondTy = RetTy->getWithNewBitWidth(1);
      bool IsUnsigned = IID == Intrinsic::umax || IID == Intrinsic::umin;
      CmpInst::Predicate Pred =
          IsUnsigned ? CmpInst::ICMP_UGT : CmpInst::ICMP_SGT;
      InstructionCost Cost = 0;
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
                                          Pred, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
                                          Pred, CostKind);
      return Cost;
    }
    case Intrinsic::sadd_with_overflow:
    case Intrinsic::ssub_with_overflow: {
      Type *SumTy = RetTy->getContainedType(0);
      Type *OverflowTy = RetTy->getContainedType(1);
      unsigned Opcode = IID == Intrinsic::sadd_with_overflow
                            ? BinaryOperator::Add
                            : BinaryOperator::Sub;
 
      //   Add:
      //   Overflow -> (Result < LHS) ^ (RHS < 0)
      //   Sub:
      //   Overflow -> (Result < LHS) ^ (RHS > 0)
      InstructionCost Cost = 0;
      Cost += thisT()->getArithmeticInstrCost(Opcode, SumTy, CostKind);
      Cost +=
          2 * thisT()->getCmpSelInstrCost(Instruction::ICmp, SumTy, OverflowTy,
                                          CmpInst::ICMP_SGT, CostKind);
      Cost += thisT()->getArithmeticInstrCost(BinaryOperator::Xor, OverflowTy,
                                              CostKind);
      return Cost;
    }
    case Intrinsic::uadd_with_overflow:
    case Intrinsic::usub_with_overflow: {
      Type *SumTy = RetTy->getContainedType(0);
      Type *OverflowTy = RetTy->getContainedType(1);
      unsigned Opcode = IID == Intrinsic::uadd_with_overflow
                            ? BinaryOperator::Add
                            : BinaryOperator::Sub;
      CmpInst::Predicate Pred = IID == Intrinsic::uadd_with_overflow
                                    ? CmpInst::ICMP_ULT
                                    : CmpInst::ICMP_UGT;
 
      InstructionCost Cost = 0;
      Cost += thisT()->getArithmeticInstrCost(Opcode, SumTy, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, SumTy,
                                          OverflowTy, Pred, CostKind);
      return Cost;
    }
    case Intrinsic::smul_with_overflow:
    case Intrinsic::umul_with_overflow: {
      Type *MulTy = RetTy->getContainedType(0);
      Type *OverflowTy = RetTy->getContainedType(1);
      unsigned ExtSize = MulTy->getScalarSizeInBits() * 2;
      Type *ExtTy = MulTy->getWithNewBitWidth(ExtSize);
      bool IsSigned = IID == Intrinsic::smul_with_overflow;
 
      unsigned ExtOp = IsSigned ? Instruction::SExt : Instruction::ZExt;
      TTI::CastContextHint CCH = TTI::CastContextHint::None;
 
      InstructionCost Cost = 0;
      Cost += 2 * thisT()->getCastInstrCost(ExtOp, ExtTy, MulTy, CCH, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(Instruction::Mul, ExtTy, CostKind);
      Cost += 2 * thisT()->getCastInstrCost(Instruction::Trunc, MulTy, ExtTy,
                                            CCH, CostKind);
      Cost += thisT()->getArithmeticInstrCost(
          Instruction::LShr, ExtTy, CostKind, {TTI::OK_AnyValue, TTI::OP_None},
          {TTI::OK_UniformConstantValue, TTI::OP_None});
 
      if (IsSigned)
        Cost += thisT()->getArithmeticInstrCost(
            Instruction::AShr, MulTy, CostKind,
            {TTI::OK_AnyValue, TTI::OP_None},
            {TTI::OK_UniformConstantValue, TTI::OP_None});
 
      Cost += thisT()->getCmpSelInstrCost(
          BinaryOperator::ICmp, MulTy, OverflowTy, CmpInst::ICMP_NE, CostKind);
      return Cost;
    }
    case Intrinsic::sadd_sat:
    case Intrinsic::ssub_sat: {
      // Assume a default expansion.
      Type *CondTy = RetTy->getWithNewBitWidth(1);
 
      Type *OpTy = StructType::create({RetTy, CondTy});
      Intrinsic::ID OverflowOp = IID == Intrinsic::sadd_sat
                                     ? Intrinsic::sadd_with_overflow
                                     : Intrinsic::ssub_with_overflow;
      CmpInst::Predicate Pred = CmpInst::ICMP_SGT;
 
      // SatMax -> Overflow && SumDiff < 0
      // SatMin -> Overflow && SumDiff >= 0
      InstructionCost Cost = 0;
      IntrinsicCostAttributes Attrs(OverflowOp, OpTy, {RetTy, RetTy}, FMF,
                                    nullptr, ScalarizationCostPassed);
      Cost += thisT()->getIntrinsicInstrCost(Attrs, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
                                          Pred, CostKind);
      Cost += 2 * thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy,
                                              CondTy, Pred, CostKind);
      return Cost;
    }
    case Intrinsic::uadd_sat:
    case Intrinsic::usub_sat: {
      Type *CondTy = RetTy->getWithNewBitWidth(1);
 
      Type *OpTy = StructType::create({RetTy, CondTy});
      Intrinsic::ID OverflowOp = IID == Intrinsic::uadd_sat
                                     ? Intrinsic::uadd_with_overflow
                                     : Intrinsic::usub_with_overflow;
 
      InstructionCost Cost = 0;
      IntrinsicCostAttributes Attrs(OverflowOp, OpTy, {RetTy, RetTy}, FMF,
                                    nullptr, ScalarizationCostPassed);
      Cost += thisT()->getIntrinsicInstrCost(Attrs, CostKind);
      Cost +=
          thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
                                      CmpInst::BAD_ICMP_PREDICATE, CostKind);
      return Cost;
    }
    case Intrinsic::smul_fix:
    case Intrinsic::umul_fix: {
      unsigned ExtSize = RetTy->getScalarSizeInBits() * 2;
      Type *ExtTy = RetTy->getWithNewBitWidth(ExtSize);
 
      unsigned ExtOp =
          IID == Intrinsic::smul_fix ? Instruction::SExt : Instruction::ZExt;
      TTI::CastContextHint CCH = TTI::CastContextHint::None;
 
      InstructionCost Cost = 0;
      Cost += 2 * thisT()->getCastInstrCost(ExtOp, ExtTy, RetTy, CCH, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(Instruction::Mul, ExtTy, CostKind);
      Cost += 2 * thisT()->getCastInstrCost(Instruction::Trunc, RetTy, ExtTy,
                                            CCH, CostKind);
      Cost += thisT()->getArithmeticInstrCost(
          Instruction::LShr, RetTy, CostKind, {TTI::OK_AnyValue, TTI::OP_None},
          {TTI::OK_UniformConstantValue, TTI::OP_None});
      Cost += thisT()->getArithmeticInstrCost(
          Instruction::Shl, RetTy, CostKind, {TTI::OK_AnyValue, TTI::OP_None},
          {TTI::OK_UniformConstantValue, TTI::OP_None});
      Cost += thisT()->getArithmeticInstrCost(Instruction::Or, RetTy, CostKind);
      return Cost;
    }
    case Intrinsic::abs: {
      // abs(X) = select(icmp(X,0),X,sub(0,X))
      Type *CondTy = RetTy->getWithNewBitWidth(1);
      CmpInst::Predicate Pred = CmpInst::ICMP_SGT;
      InstructionCost Cost = 0;
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
                                          Pred, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
                                          Pred, CostKind);
      // TODO: Should we add an OperandValueProperties::OP_Zero property?
      Cost += thisT()->getArithmeticInstrCost(
          BinaryOperator::Sub, RetTy, CostKind,
          {TTI::OK_UniformConstantValue, TTI::OP_None});
      return Cost;
    }
    case Intrinsic::fshl:
    case Intrinsic::fshr: {
      // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
      // fshr: (X << (BW - (Z % BW))) | (Y >> (Z % BW))
      Type *CondTy = RetTy->getWithNewBitWidth(1);
      InstructionCost Cost = 0;
      Cost +=
          thisT()->getArithmeticInstrCost(BinaryOperator::Or, RetTy, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(BinaryOperator::Sub, RetTy, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(BinaryOperator::Shl, RetTy, CostKind);
      Cost += thisT()->getArithmeticInstrCost(BinaryOperator::LShr, RetTy,
                                              CostKind);
      // Non-constant shift amounts requires a modulo. If the typesize is a
      // power-2 then this will be converted to an and, otherwise it will use a
      // urem.
      Cost += thisT()->getArithmeticInstrCost(
          isPowerOf2_32(RetTy->getScalarSizeInBits()) ? BinaryOperator::And
                                                      : BinaryOperator::URem,
          RetTy, CostKind, {TTI::OK_AnyValue, TTI::OP_None},
          {TTI::OK_UniformConstantValue, TTI::OP_None});
      // Shift-by-zero handling.
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
                                          CmpInst::ICMP_EQ, CostKind);
      Cost += thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
                                          CmpInst::ICMP_EQ, CostKind);
      return Cost;
    }
    case Intrinsic::fptosi_sat:
    case Intrinsic::fptoui_sat: {
      if (Tys.empty())
        break;
      Type *FromTy = Tys[0];
      bool IsSigned = IID == Intrinsic::fptosi_sat;
 
      InstructionCost Cost = 0;
      IntrinsicCostAttributes Attrs1(Intrinsic::minnum, FromTy,
                                     {FromTy, FromTy});
      Cost += thisT()->getIntrinsicInstrCost(Attrs1, CostKind);
      IntrinsicCostAttributes Attrs2(Intrinsic::maxnum, FromTy,
                                     {FromTy, FromTy});
      Cost += thisT()->getIntrinsicInstrCost(Attrs2, CostKind);
      Cost += thisT()->getCastInstrCost(
          IsSigned ? Instruction::FPToSI : Instruction::FPToUI, RetTy, FromTy,
          TTI::CastContextHint::None, CostKind);
      if (IsSigned) {
        Type *CondTy = RetTy->getWithNewBitWidth(1);
        Cost += thisT()->getCmpSelInstrCost(
            BinaryOperator::FCmp, FromTy, CondTy, CmpInst::FCMP_UNO, CostKind);
        Cost += thisT()->getCmpSelInstrCost(
            BinaryOperator::Select, RetTy, CondTy, CmpInst::FCMP_UNO, CostKind);
      }
      return Cost;
    }
    case Intrinsic::ucmp:
    case Intrinsic::scmp: {
      Type *CmpTy = Tys[0];
      Type *CondTy = RetTy->getWithNewBitWidth(1);
      InstructionCost Cost =
          thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, CmpTy, CondTy,
                                      CmpIntrinsic::getGTPredicate(IID),
                                      CostKind) +
          thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, CmpTy, CondTy,
                                      CmpIntrinsic::getLTPredicate(IID),
                                      CostKind);
 
      EVT VT = TLI->getValueType(DL, CmpTy, true);
      if (TLI->preferSelectsOverBooleanArithmetic(VT)) {
        // x < y ? -1 : (x > y ? 1 : 0)
        Cost += 2 * thisT()->getCmpSelInstrCost(
                        BinaryOperator::Select, RetTy, CondTy,
                        ICmpInst::BAD_ICMP_PREDICATE, CostKind);
      } else {
        // zext(x > y) - zext(x < y)
        Cost +=
            2 * thisT()->getCastInstrCost(CastInst::ZExt, RetTy, CondTy,
                                          TTI::CastContextHint::None, CostKind);
        Cost += thisT()->getArithmeticInstrCost(BinaryOperator::Sub, RetTy,
                                                CostKind);
      }
      return Cost;
    }
    case Intrinsic::maximumnum:
    case Intrinsic::minimumnum: {
      // On platform that support FMAXNUM_IEEE/FMINNUM_IEEE, we expand
      // maximumnum/minimumnum to
      //    ARG0 = fcanonicalize ARG0, ARG0  // to quiet ARG0
      //    ARG1 = fcanonicalize ARG1, ARG1  // to quiet ARG1
      //    RESULT = MAXNUM_IEEE ARG0, ARG1  // or MINNUM_IEEE
      // FIXME: In LangRef, we claimed FMAXNUM has the same behaviour of
      //        FMAXNUM_IEEE, while the backend hasn't migrated the code yet.
      //        Finally, we will remove FMAXNUM_IEEE and FMINNUM_IEEE.
      int IeeeISD =
          IID == Intrinsic::maximumnum ? ISD::FMAXNUM_IEEE : ISD::FMINNUM_IEEE;
      if (TLI->isOperationLegal(IeeeISD, LT.second)) {
        IntrinsicCostAttributes FCanonicalizeAttrs(Intrinsic::canonicalize,
                                                   RetTy, Tys[0]);
        InstructionCost FCanonicalizeCost =
            thisT()->getIntrinsicInstrCost(FCanonicalizeAttrs, CostKind);
        return LT.first + FCanonicalizeCost * 2;
      }
      break;
    }
    case Intrinsic::clmul: {
      // This cost model should match the expansion in
      // TargetLowering::expandCLMUL.
      unsigned BW = RetTy->getScalarSizeInBits();
      InstructionCost AndCost =
          thisT()->getArithmeticInstrCost(Instruction::And, RetTy, CostKind);
      InstructionCost OrCost =
          thisT()->getArithmeticInstrCost(Instruction::Or, RetTy, CostKind);
      InstructionCost XorCost =
          thisT()->getArithmeticInstrCost(Instruction::Xor, RetTy, CostKind);
      InstructionCost MulCost =
          thisT()->getArithmeticInstrCost(Instruction::Mul, RetTy, CostKind);
 
      // When the multiplication with holes approach is used, it splits the
      // operands into S phases (the smallest stride with ceil(BW/S) <= 2^S) and
      // emits S*S MULs, 3*S ANDs, S*(S-1) XORs and S-1 ORs.
      //
      // * BW <= 8 uses S = 2
      // * BW <= 24 uses S = 3
      // * BW <= 64 uses S = 4
      // * BW <= 160 uses S = 5
      // * BW <= 384 uses S = 6
      unsigned S = 1;
      while (S < 32 && divideCeil(BW, S) > (1u << S))
        ++S;
 
      // The naive algorithm usually uses AND+MUL+XOR per bit.
      unsigned NaiveCost = 3 * BW;
      unsigned HolesCost = S * S + 3 * S + S * (S - 1) + (S - 1);
 
      if (HolesCost < NaiveCost &&
          TLI->isOperationLegalOrCustom(ISD::MUL,
                                        TLI->getValueType(DL, RetTy))) {
        return S * S * MulCost + 3 * S * AndCost + S * (S - 1) * XorCost +
               (S - 1) * OrCost;
      }
 
      InstructionCost PerBitCostMul = AndCost + MulCost + XorCost;
      InstructionCost PerBitCostBittest =
          AndCost +
          thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, RetTy,
                                      ICmpInst::BAD_ICMP_PREDICATE, CostKind) +
          thisT()->getCmpSelInstrCost(Instruction::ICmp, RetTy, RetTy,
                                      ICmpInst::ICMP_NE, CostKind);
      InstructionCost PerBitCost = std::min(PerBitCostMul, PerBitCostBittest);
      return BW * PerBitCost;
    }
    case Intrinsic::smulh:
    case Intrinsic::umulh: {
      unsigned BW = RetTy->getScalarSizeInBits();
      Type *WideTy = RetTy->getWithNewBitWidth(BW * 2);
      bool IsSigned = IID == Intrinsic::smulh;
      unsigned ExtOp = IsSigned ? Instruction::SExt : Instruction::ZExt;
      InstructionCost Cost = 0;
      Cost +=
          2 * thisT()->getCastInstrCost(ExtOp, WideTy, RetTy,
                                        TTI::CastContextHint::None, CostKind);
      Cost +=
          thisT()->getArithmeticInstrCost(Instruction::Mul, WideTy, CostKind);
      Cost += thisT()->getArithmeticInstrCost(
          Instruction::LShr, WideTy, CostKind, {TTI::OK_AnyValue, TTI::OP_None},
          {TTI::OK_UniformConstantValue, TTI::OP_None});
      Cost += thisT()->getCastInstrCost(Instruction::Trunc, RetTy, WideTy,
                                        TTI::CastContextHint::None, CostKind);
      return Cost;
    }
    default:
      break;
    }
 
    // Else, assume that we need to scalarize this intrinsic. For math builtins
    // this will emit a costly libcall, adding call overhead and spills. Make it
    // very expensive.
    if (isVectorizedTy(RetTy)) {
      ArrayRef<Type *> RetVTys = getContainedTypes(RetTy);
 
      // Scalable vectors cannot be scalarized, so return Invalid.
      if (any_of(concat<Type *const>(RetVTys, Tys),
                 [](Type *Ty) { return isa<ScalableVectorType>(Ty); }))
        return InstructionCost::getInvalid();
 
      InstructionCost ScalarizationCost = ScalarizationCostPassed;
      if (!SkipScalarizationCost) {
        ScalarizationCost = 0;
        for (Type *RetVTy : RetVTys) {
          ScalarizationCost += getScalarizationOverhead(
              cast<VectorType>(RetVTy), /*Insert=*/true,
              /*Extract=*/false, CostKind);
        }
      }
 
      unsigned ScalarCalls = getVectorizedTypeVF(RetTy).getFixedValue();
      SmallVector<Type *, 4> ScalarTys;
      for (Type *Ty : Tys) {
        if (Ty->isVectorTy())
          Ty = Ty->getScalarType();
        ScalarTys.push_back(Ty);
      }
      IntrinsicCostAttributes Attrs(IID, toScalarizedTy(RetTy), ScalarTys, FMF);
      InstructionCost ScalarCost =
          thisT()->getIntrinsicInstrCost(Attrs, CostKind);
      for (Type *Ty : Tys) {
        if (auto *VTy = dyn_cast<VectorType>(Ty)) {
          if (!ICA.skipScalarizationCost())
            ScalarizationCost += getScalarizationOverhead(
                VTy, /*Insert*/ false, /*Extract*/ true, CostKind);
          ScalarCalls = std::max(ScalarCalls,
                                 cast<FixedVectorType>(VTy)->getNumElements());
        }
      }
      return ScalarCalls * ScalarCost + ScalarizationCost;
    }
 
    // This is going to be turned into a library call, make it expensive.
    return SingleCallCost;
  }
 
  /// Get memory intrinsic cost based on arguments.
  InstructionCost
  getMemIntrinsicInstrCost(const MemIntrinsicCostAttributes &MICA,
                           TTI::TargetCostKind CostKind) const override {
    unsigned Id = MICA.getID();
    Type *DataTy = MICA.getDataType();
    bool VariableMask = MICA.getVariableMask();
    Align Alignment = MICA.getAlignment();
 
    switch (Id) {
    case Intrinsic::experimental_vp_strided_load:
    case Intrinsic::experimental_vp_strided_store: {
      unsigned Opcode = Id == Intrinsic::experimental_vp_strided_load
                            ? Instruction::Load
                            : Instruction::Store;
      // For a target without strided memory operations (or for an illegal
      // operation type on one which does), assume we lower to a gather/scatter
      // operation.  (Which may in turn be scalarized.)
      return getCommonMaskedMemoryOpCost(Opcode, DataTy, Alignment,
                                         VariableMask, true, CostKind);
    }
    case Intrinsic::masked_scatter:
    case Intrinsic::masked_gather:
    case Intrinsic::vp_scatter:
    case Intrinsic::vp_gather: {
      unsigned Opcode = (MICA.getID() == Intrinsic::masked_gather ||
                         MICA.getID() == Intrinsic::vp_gather)
                            ? Instruction::Load
                            : Instruction::Store;
 
      return getCommonMaskedMemoryOpCost(Opcode, DataTy, Alignment,
                                         VariableMask, true, CostKind);
    }
    case Intrinsic::vp_load:
    case Intrinsic::vp_store:
      return InstructionCost::getInvalid();
    case Intrinsic::masked_load:
    case Intrinsic::masked_store: {
      unsigned Opcode =
          Id == Intrinsic::masked_load ? Instruction::Load : Instruction::Store;
      // TODO: Pass on AddressSpace when we have test coverage.
      return getCommonMaskedMemoryOpCost(Opcode, DataTy, Alignment, true, false,
                                         CostKind);
    }
    case Intrinsic::masked_compressstore:
    case Intrinsic::masked_expandload: {
      unsigned Opcode = MICA.getID() == Intrinsic::masked_expandload
                            ? Instruction::Load
                            : Instruction::Store;
      // Treat expand load/compress store as gather/scatter operation.
      // TODO: implement more precise cost estimation for these intrinsics.
      return getCommonMaskedMemoryOpCost(Opcode, DataTy, Alignment,
                                         VariableMask,
                                         /*IsGatherScatter*/ true, CostKind);
    }
    case Intrinsic::vp_load_ff:
      return InstructionCost::getInvalid();
    case Intrinsic::speculative_load:
      // Speculative loads are lowered to regular loads of the full type.
      return thisT()->getMemoryOpCost(Instruction::Load, DataTy, Alignment,
                                      MICA.getAddressSpace(), CostKind);
    default:
      llvm_unreachable("unexpected intrinsic");
    }
  }
 
  /// Compute a cost of the given call instruction.
  ///
  /// Compute the cost of calling function F with return type RetTy and
  /// argument types Tys. F might be nullptr, in this case the cost of an
  /// arbitrary call with the specified signature will be returned.
  /// This is used, for instance,  when we estimate call of a vector
  /// counterpart of the given function.
  /// \param F Called function, might be nullptr.
  /// \param RetTy Return value types.
  /// \param Tys Argument types.
  /// \returns The cost of Call instruction.
  InstructionCost
  getCallInstrCost(Function *F, Type *RetTy, ArrayRef<Type *> Tys,
                   TTI::TargetCostKind CostKind) const override {
    return 10;
  }
 
  unsigned getNumberOfParts(Type *Tp) const override {
    std::pair<InstructionCost, MVT> LT = getTypeLegalizationCost(Tp);
    if (!LT.first.isValid())
      return 0;
    // Try to find actual number of parts for non-power-of-2 elements as
    // ceil(num-of-elements/num-of-subtype-elements).
    if (auto *FTp = dyn_cast<FixedVectorType>(Tp);
        FTp && LT.second.isFixedLengthVector() &&
        !has_single_bit(FTp->getNumElements())) {
      if (auto *SubTp = dyn_cast_if_present<FixedVectorType>(
              EVT(LT.second).getTypeForEVT(Tp->getContext()));
          SubTp && SubTp->getElementType() == FTp->getElementType())
        return divideCeil(FTp->getNumElements(), SubTp->getNumElements());
    }
    return LT.first.getValue();
  }
 
  InstructionCost
  getAddressComputationCost(Type *PtrTy, ScalarEvolution *, const SCEV *,
                            TTI::TargetCostKind) const override {
    return 0;
  }
 
  /// Try to calculate arithmetic and shuffle op costs for reduction intrinsics.
  /// We're assuming that reduction operation are performing the following way:
  ///
  /// %val1 = shufflevector<n x t> %val, <n x t> %undef,
  /// <n x i32> <i32 n/2, i32 n/2 + 1, ..., i32 n, i32 undef, ..., i32 undef>
  ///            \----------------v-------------/  \----------v------------/
  ///                            n/2 elements               n/2 elements
  /// %red1 = op <n x t> %val, <n x t> val1
  /// After this operation we have a vector %red1 where only the first n/2
  /// elements are meaningful, the second n/2 elements are undefined and can be
  /// dropped. All other operations are actually working with the vector of
  /// length n/2, not n, though the real vector length is still n.
  /// %val2 = shufflevector<n x t> %red1, <n x t> %undef,
  /// <n x i32> <i32 n/4, i32 n/4 + 1, ..., i32 n/2, i32 undef, ..., i32 undef>
  ///            \----------------v-------------/  \----------v------------/
  ///                            n/4 elements               3*n/4 elements
  /// %red2 = op <n x t> %red1, <n x t> val2  - working with the vector of
  /// length n/2, the resulting vector has length n/4 etc.
  ///
  /// The cost model should take into account that the actual length of the
  /// vector is reduced on each iteration.
  InstructionCost getTreeReductionCost(unsigned Opcode, VectorType *Ty,
                                       TTI::TargetCostKind CostKind) const {
    // Targets must implement a default value for the scalable case, since
    // we don't know how many lanes the vector has.
    if (isa<ScalableVectorType>(Ty))
      return InstructionCost::getInvalid();
 
    Type *ScalarTy = Ty->getElementType();
    unsigned NumVecElts = cast<FixedVectorType>(Ty)->getNumElements();
    if ((Opcode == Instruction::Or || Opcode == Instruction::And) &&
        ScalarTy == IntegerType::getInt1Ty(Ty->getContext()) &&
        NumVecElts >= 2) {
      // Or reduction for i1 is represented as:
      // %val = bitcast <ReduxWidth x i1> to iReduxWidth
      // %res = cmp ne iReduxWidth %val, 0
      // And reduction for i1 is represented as:
      // %val = bitcast <ReduxWidth x i1> to iReduxWidth
      // %res = cmp eq iReduxWidth %val, 11111
      Type *ValTy = IntegerType::get(Ty->getContext(), NumVecElts);
      return thisT()->getCastInstrCost(Instruction::BitCast, ValTy, Ty,
                                       TTI::CastContextHint::None, CostKind) +
             thisT()->getCmpSelInstrCost(Instruction::ICmp, ValTy,
                                         CmpInst::makeCmpResultType(ValTy),
                                         CmpInst::BAD_ICMP_PREDICATE, CostKind);
    }
    unsigned NumReduxLevels = Log2_32(NumVecElts);
    InstructionCost ArithCost = 0;
    InstructionCost ShuffleCost = 0;
    std::pair<InstructionCost, MVT> LT = thisT()->getTypeLegalizationCost(Ty);
    unsigned LongVectorCount = 0;
    unsigned MVTLen =
        LT.second.isVector() ? LT.second.getVectorNumElements() : 1;
    while (NumVecElts > MVTLen) {
      NumVecElts /= 2;
      VectorType *SubTy = FixedVectorType::get(ScalarTy, NumVecElts);
      ShuffleCost += thisT()->getShuffleCost(
          TTI::SK_ExtractSubvector, SubTy, Ty, CostKind, {}, NumVecElts, SubTy);
      ArithCost += thisT()->getArithmeticInstrCost(Opcode, SubTy, CostKind);
      Ty = SubTy;
      ++LongVectorCount;
    }
 
    NumReduxLevels -= LongVectorCount;
 
    // The minimal length of the vector is limited by the real length of vector
    // operations performed on the current platform. That's why several final
    // reduction operations are performed on the vectors with the same
    // architecture-dependent length.
 
    // By default reductions need one shuffle per reduction level.
    ShuffleCost +=
        NumReduxLevels * thisT()->getShuffleCost(TTI::SK_PermuteSingleSrc, Ty,
                                                 Ty, CostKind, {}, 0, Ty);
    ArithCost +=
        NumReduxLevels * thisT()->getArithmeticInstrCost(Opcode, Ty, CostKind);
    return ShuffleCost + ArithCost +
           thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty,
                                       CostKind, 0, nullptr, nullptr);
  }
 
  /// Try to calculate the cost of performing strict (in-order) reductions,
  /// which involves doing a sequence of floating point additions in lane
  /// order, starting with an initial value. For example, consider a scalar
  /// initial value 'InitVal' of type float and a vector of type <4 x float>:
  ///
  ///   Vector = <float %v0, float %v1, float %v2, float %v3>
  ///
  ///   %add1 = %InitVal + %v0
  ///   %add2 = %add1 + %v1
  ///   %add3 = %add2 + %v2
  ///   %add4 = %add3 + %v3
  ///
  /// As a simple estimate we can say the cost of such a reduction is 4 times
  /// the cost of a scalar FP addition. We can only estimate the costs for
  /// fixed-width vectors here because for scalable vectors we do not know the
  /// runtime number of operations.
  InstructionCost getOrderedReductionCost(unsigned Opcode, VectorType *Ty,
                                          TTI::TargetCostKind CostKind) const {
    // Targets must implement a default value for the scalable case, since
    // we don't know how many lanes the vector has.
    if (isa<ScalableVectorType>(Ty))
      return InstructionCost::getInvalid();
 
    auto *VTy = cast<FixedVectorType>(Ty);
    InstructionCost ExtractCost = getScalarizationOverhead(
        VTy, /*Insert=*/false, /*Extract=*/true, CostKind);
    InstructionCost ArithCost = thisT()->getArithmeticInstrCost(
        Opcode, VTy->getElementType(), CostKind);
    ArithCost *= VTy->getNumElements();
 
    return ExtractCost + ArithCost;
  }
 
  InstructionCost
  getArithmeticReductionCost(unsigned Opcode, VectorType *Ty,
                             std::optional<FastMathFlags> FMF,
                             TTI::TargetCostKind CostKind) const override {
    assert(Ty && "Unknown reduction vector type");
    if (TTI::requiresOrderedReduction(FMF))
      return getOrderedReductionCost(Opcode, Ty, CostKind);
    return getTreeReductionCost(Opcode, Ty, CostKind);
  }
 
  /// Try to calculate op costs for min/max reduction operations.
  /// \param CondTy Conditional type for the Select instruction.
  InstructionCost
  getMinMaxReductionCost(Intrinsic::ID IID, VectorType *Ty, FastMathFlags FMF,
                         TTI::TargetCostKind CostKind) const override {
    // Targets must implement a default value for the scalable case, since
    // we don't know how many lanes the vector has.
    if (isa<ScalableVectorType>(Ty))
      return InstructionCost::getInvalid();
 
    Type *ScalarTy = Ty->getElementType();
    unsigned NumVecElts = cast<FixedVectorType>(Ty)->getNumElements();
    unsigned NumReduxLevels = Log2_32(NumVecElts);
    InstructionCost MinMaxCost = 0;
    InstructionCost ShuffleCost = 0;
    std::pair<InstructionCost, MVT> LT = thisT()->getTypeLegalizationCost(Ty);
    unsigned LongVectorCount = 0;
    unsigned MVTLen =
        LT.second.isVector() ? LT.second.getVectorNumElements() : 1;
    while (NumVecElts > MVTLen) {
      NumVecElts /= 2;
      auto *SubTy = FixedVectorType::get(ScalarTy, NumVecElts);
 
      ShuffleCost += thisT()->getShuffleCost(
          TTI::SK_ExtractSubvector, SubTy, Ty, CostKind, {}, NumVecElts, SubTy);
 
      IntrinsicCostAttributes Attrs(IID, SubTy, {SubTy, SubTy}, FMF);
      MinMaxCost += getIntrinsicInstrCost(Attrs, CostKind);
      Ty = SubTy;
      ++LongVectorCount;
    }
 
    NumReduxLevels -= LongVectorCount;
 
    // The minimal length of the vector is limited by the real length of vector
    // operations performed on the current platform. That's why several final
    // reduction opertions are perfomed on the vectors with the same
    // architecture-dependent length.
    ShuffleCost +=
        NumReduxLevels * thisT()->getShuffleCost(TTI::SK_PermuteSingleSrc, Ty,
                                                 Ty, CostKind, {}, 0, Ty);
    IntrinsicCostAttributes Attrs(IID, Ty, {Ty, Ty}, FMF);
    MinMaxCost += NumReduxLevels * getIntrinsicInstrCost(Attrs, CostKind);
    // The last min/max should be in vector registers and we counted it above.
    // So just need a single extractelement.
    return ShuffleCost + MinMaxCost +
           thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty,
                                       CostKind, 0, nullptr, nullptr);
  }
 
  InstructionCost
  getExtendedReductionCost(unsigned Opcode, bool IsUnsigned, Type *ResTy,
                           VectorType *Ty, std::optional<FastMathFlags> FMF,
                           TTI::TargetCostKind CostKind) const override {
    if (auto *FTy = dyn_cast<FixedVectorType>(Ty);
        FTy && IsUnsigned && Opcode == Instruction::Add &&
        FTy->getElementType() == IntegerType::getInt1Ty(Ty->getContext())) {
      // Represent vector_reduce_add(ZExt(<n x i1>)) as
      // ZExtOrTrunc(ctpop(bitcast <n x i1> to in)).
      auto *IntTy =
          IntegerType::get(ResTy->getContext(), FTy->getNumElements());
      IntrinsicCostAttributes ICA(Intrinsic::ctpop, IntTy, {IntTy},
                                  FMF ? *FMF : FastMathFlags());
      return thisT()->getCastInstrCost(Instruction::BitCast, IntTy, FTy,
                                       TTI::CastContextHint::None, CostKind) +
             thisT()->getIntrinsicInstrCost(ICA, CostKind);
    }
    // Without any native support, this is equivalent to the cost of
    // vecreduce.opcode(ext(Ty A)).
    VectorType *ExtTy = VectorType::get(ResTy, Ty);
    InstructionCost RedCost =
        thisT()->getArithmeticReductionCost(Opcode, ExtTy, FMF, CostKind);
    InstructionCost ExtCost = thisT()->getCastInstrCost(
        IsUnsigned ? Instruction::ZExt : Instruction::SExt, ExtTy, Ty,
        TTI::CastContextHint::None, CostKind);
 
    return RedCost + ExtCost;
  }
 
  InstructionCost
  getMulAccReductionCost(bool IsUnsigned, unsigned RedOpcode, Type *ResTy,
                         VectorType *Ty,
                         TTI::TargetCostKind CostKind) const override {
    // Without any native support, this is equivalent to the cost of
    // vecreduce.add(mul(ext(Ty A), ext(Ty B))) or
    // vecreduce.add(mul(A, B)).
    assert((RedOpcode == Instruction::Add || RedOpcode == Instruction::Sub) &&
           "The reduction opcode is expected to be Add or Sub.");
    VectorType *ExtTy = VectorType::get(ResTy, Ty);
    InstructionCost RedCost = thisT()->getArithmeticReductionCost(
        RedOpcode, ExtTy, std::nullopt, CostKind);
    InstructionCost ExtCost = thisT()->getCastInstrCost(
        IsUnsigned ? Instruction::ZExt : Instruction::SExt, ExtTy, Ty,
        TTI::CastContextHint::None, CostKind);
 
    InstructionCost MulCost =
        thisT()->getArithmeticInstrCost(Instruction::Mul, ExtTy, CostKind);
 
    return RedCost + MulCost + 2 * ExtCost;
  }
 
  InstructionCost getPartialReductionCost(
      unsigned Opcode, Type *InputTypeA, Type *InputTypeB, Type *AccumType,
      ElementCount VF, TTI::PartialReductionExtendKind OpAExtend,
      TTI::PartialReductionExtendKind OpBExtend, std::optional<unsigned> BinOp,
      TTI::TargetCostKind CostKind,
      std::optional<FastMathFlags> FMF) const override {
    unsigned EltSizeAcc = AccumType->getScalarSizeInBits();
    unsigned EltSizeInA = InputTypeA->getScalarSizeInBits();
    unsigned Ratio = EltSizeAcc / EltSizeInA;
    if (VF.getKnownMinValue() <= Ratio || VF.getKnownMinValue() % Ratio != 0 ||
        EltSizeAcc % EltSizeInA != 0 || (BinOp && InputTypeA != InputTypeB))
      return InstructionCost::getInvalid();
 
    Type *InputVectorType = VectorType::get(InputTypeA, VF);
    Type *ExtInputVectorType = VectorType::get(AccumType, VF);
    Type *AccumVectorType =
        VectorType::get(AccumType, VF.divideCoefficientBy(Ratio));
 
    InstructionCost ExtendCostA = 0;
    if (OpAExtend != TTI::PartialReductionExtendKind::PR_None)
      ExtendCostA = getCastInstrCost(
          TTI::getOpcodeForPartialReductionExtendKind(OpAExtend),
          ExtInputVectorType, InputVectorType, TTI::CastContextHint::None,
          CostKind);
 
    // TODO: add cost of extracting subvectors from the source vector that
    // is to be partially reduced.
    InstructionCost ReductionOpCost =
        Ratio * getArithmeticInstrCost(Opcode, AccumVectorType, CostKind);
 
    if (!BinOp)
      return ExtendCostA + ReductionOpCost;
 
    InstructionCost ExtendCostB = 0;
    if (OpBExtend != TTI::PartialReductionExtendKind::PR_None)
      ExtendCostB = getCastInstrCost(
          TTI::getOpcodeForPartialReductionExtendKind(OpBExtend),
          ExtInputVectorType, InputVectorType, TTI::CastContextHint::None,
          CostKind);
    return ExtendCostA + ExtendCostB + ReductionOpCost +
           getArithmeticInstrCost(*BinOp, ExtInputVectorType, CostKind);
  }
 
  InstructionCost getVectorSplitCost() const { return 1; }
 
  /// @}
};
 
/// Concrete BasicTTIImpl that can be used if no further customization
/// is needed.
class BasicTTIImpl : public BasicTTIImplBase<BasicTTIImpl> {
  using BaseT = BasicTTIImplBase<BasicTTIImpl>;
 
  friend class BasicTTIImplBase<BasicTTIImpl>;
 
  const TargetSubtargetInfo *ST;
  const TargetLoweringBase *TLI;
 
  const TargetSubtargetInfo *getST() const { return ST; }
  const TargetLoweringBase *getTLI() const { return TLI; }
 
public:
  LLVM_ABI explicit BasicTTIImpl(const TargetMachine *TM, const Function &F);
};
 
} // end namespace llvm
 
#endif // LLVM_CODEGEN_BASICTTIIMPL_H