contrib/llvm-project/llvm/include/llvm/CodeGen/BasicTTIImpl.h

   1 //===- BasicTTIImpl.h -------------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// This file provides a helper that implements much of the TTI interface in
  11 /// terms of the target-independent code generator and TargetLowering
  12 /// interfaces.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CODEGEN_BASICTTIIMPL_H
  17 #define LLVM_CODEGEN_BASICTTIIMPL_H
  18
  19 #include "llvm/ADT/APInt.h"
  20 #include "llvm/ADT/ArrayRef.h"
  21 #include "llvm/ADT/BitVector.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/Analysis/LoopInfo.h"
  25 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  26 #include "llvm/Analysis/TargetTransformInfo.h"
  27 #include "llvm/Analysis/TargetTransformInfoImpl.h"
  28 #include "llvm/CodeGen/ISDOpcodes.h"
  29 #include "llvm/CodeGen/TargetLowering.h"
  30 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  31 #include "llvm/CodeGen/ValueTypes.h"
  32 #include "llvm/IR/BasicBlock.h"
  33 #include "llvm/IR/Constant.h"
  34 #include "llvm/IR/Constants.h"
  35 #include "llvm/IR/DataLayout.h"
  36 #include "llvm/IR/DerivedTypes.h"
  37 #include "llvm/IR/InstrTypes.h"
  38 #include "llvm/IR/Instruction.h"
  39 #include "llvm/IR/Instructions.h"
  40 #include "llvm/IR/Intrinsics.h"
  41 #include "llvm/IR/Operator.h"
  42 #include "llvm/IR/Type.h"
  43 #include "llvm/IR/Value.h"
  44 #include "llvm/Support/Casting.h"
  45 #include "llvm/Support/CommandLine.h"
  46 #include "llvm/Support/ErrorHandling.h"
  47 #include "llvm/Support/MachineValueType.h"
  48 #include "llvm/Support/MathExtras.h"
  49 #include "llvm/Target/TargetMachine.h"
  50 #include <algorithm>
  51 #include <cassert>
  52 #include <cstdint>
  53 #include <limits>
  54 #include <utility>
  55
  56 namespace llvm {
  57
  58 class Function;
  59 class GlobalValue;
  60 class LLVMContext;
  61 class ScalarEvolution;
  62 class SCEV;
  63 class TargetMachine;
  64
  65 extern cl::opt<unsigned> PartialUnrollingThreshold;
  66
  67 /// Base class which can be used to help build a TTI implementation.
  68 ///
  69 /// This class provides as much implementation of the TTI interface as is
  70 /// possible using the target independent parts of the code generator.
  71 ///
  72 /// In order to subclass it, your class must implement a getST() method to
  73 /// return the subtarget, and a getTLI() method to return the target lowering.
  74 /// We need these methods implemented in the derived class so that this class
  75 /// doesn't have to duplicate storage for them.
  76 template <typename T>
  77 class BasicTTIImplBase : public TargetTransformInfoImplCRTPBase<T> {
  78 private:
  79   using BaseT = TargetTransformInfoImplCRTPBase<T>;
  80   using TTI = TargetTransformInfo;
  81
  82   /// Helper function to access this as a T.
  83   T *thisT() { return static_cast<T *>(this); }
  84
  85   /// Estimate a cost of Broadcast as an extract and sequence of insert
  86   /// operations.
  87   InstructionCost getBroadcastShuffleOverhead(FixedVectorType *VTy) {
  88     InstructionCost Cost = 0;
  89     // Broadcast cost is equal to the cost of extracting the zero'th element
  90     // plus the cost of inserting it into every element of the result vector.
  91     Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VTy, 0);
  92
  93     for (int i = 0, e = VTy->getNumElements(); i < e; ++i) {
  94       Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, VTy, i);
  95     }
  96     return Cost;
  97   }
  98
  99   /// Estimate a cost of shuffle as a sequence of extract and insert
 100   /// operations.
 101   InstructionCost getPermuteShuffleOverhead(FixedVectorType *VTy) {
 102     InstructionCost Cost = 0;
 103     // Shuffle cost is equal to the cost of extracting element from its argument
 104     // plus the cost of inserting them onto the result vector.
 105
 106     // e.g. <4 x float> has a mask of <0,5,2,7> i.e we need to extract from
 107     // index 0 of first vector, index 1 of second vector,index 2 of first
 108     // vector and finally index 3 of second vector and insert them at index
 109     // <0,1,2,3> of result vector.
 110     for (int i = 0, e = VTy->getNumElements(); i < e; ++i) {
 111       Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, VTy, i);
 112       Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VTy, i);
 113     }
 114     return Cost;
 115   }
 116
 117   /// Estimate a cost of subvector extraction as a sequence of extract and
 118   /// insert operations.
 119   InstructionCost getExtractSubvectorOverhead(VectorType *VTy, int Index,
 120                                        FixedVectorType *SubVTy) {
 121     assert(VTy && SubVTy &&
 122            "Can only extract subvectors from vectors");
 123     int NumSubElts = SubVTy->getNumElements();
 124     assert((!isa<FixedVectorType>(VTy) ||
 125             (Index + NumSubElts) <=
 126                 (int)cast<FixedVectorType>(VTy)->getNumElements()) &&
 127            "SK_ExtractSubvector index out of range");
 128
 129     InstructionCost Cost = 0;
 130     // Subvector extraction cost is equal to the cost of extracting element from
 131     // the source type plus the cost of inserting them into the result vector
 132     // type.
 133     for (int i = 0; i != NumSubElts; ++i) {
 134       Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VTy,
 135                                           i + Index);
 136       Cost +=
 137           thisT()->getVectorInstrCost(Instruction::InsertElement, SubVTy, i);
 138     }
 139     return Cost;
 140   }
 141
 142   /// Estimate a cost of subvector insertion as a sequence of extract and
 143   /// insert operations.
 144   InstructionCost getInsertSubvectorOverhead(VectorType *VTy, int Index,
 145                                       FixedVectorType *SubVTy) {
 146     assert(VTy && SubVTy &&
 147            "Can only insert subvectors into vectors");
 148     int NumSubElts = SubVTy->getNumElements();
 149     assert((!isa<FixedVectorType>(VTy) ||
 150             (Index + NumSubElts) <=
 151                 (int)cast<FixedVectorType>(VTy)->getNumElements()) &&
 152            "SK_InsertSubvector index out of range");
 153
 154     InstructionCost Cost = 0;
 155     // Subvector insertion cost is equal to the cost of extracting element from
 156     // the source type plus the cost of inserting them into the result vector
 157     // type.
 158     for (int i = 0; i != NumSubElts; ++i) {
 159       Cost +=
 160           thisT()->getVectorInstrCost(Instruction::ExtractElement, SubVTy, i);
 161       Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, VTy,
 162                                           i + Index);
 163     }
 164     return Cost;
 165   }
 166
 167   /// Local query method delegates up to T which *must* implement this!
 168   const TargetSubtargetInfo *getST() const {
 169     return static_cast<const T *>(this)->getST();
 170   }
 171
 172   /// Local query method delegates up to T which *must* implement this!
 173   const TargetLoweringBase *getTLI() const {
 174     return static_cast<const T *>(this)->getTLI();
 175   }
 176
 177   static ISD::MemIndexedMode getISDIndexedMode(TTI::MemIndexedMode M) {
 178     switch (M) {
 179       case TTI::MIM_Unindexed:
 180         return ISD::UNINDEXED;
 181       case TTI::MIM_PreInc:
 182         return ISD::PRE_INC;
 183       case TTI::MIM_PreDec:
 184         return ISD::PRE_DEC;
 185       case TTI::MIM_PostInc:
 186         return ISD::POST_INC;
 187       case TTI::MIM_PostDec:
 188         return ISD::POST_DEC;
 189     }
 190     llvm_unreachable("Unexpected MemIndexedMode");
 191   }
 192
 193   InstructionCost getCommonMaskedMemoryOpCost(unsigned Opcode, Type *DataTy,
 194                                               Align Alignment,
 195                                               bool VariableMask,
 196                                               bool IsGatherScatter,
 197                                               TTI::TargetCostKind CostKind) {
 198     auto *VT = cast<FixedVectorType>(DataTy);
 199     // Assume the target does not have support for gather/scatter operations
 200     // and provide a rough estimate.
 201     //
 202     // First, compute the cost of the individual memory operations.
 203     InstructionCost AddrExtractCost =
 204         IsGatherScatter
 205             ? getVectorInstrCost(Instruction::ExtractElement,
 206                                  FixedVectorType::get(
 207                                      PointerType::get(VT->getElementType(), 0),
 208                                      VT->getNumElements()),
 209                                  -1)
 210             : 0;
 211     InstructionCost LoadCost =
 212         VT->getNumElements() *
 213         (AddrExtractCost +
 214          getMemoryOpCost(Opcode, VT->getElementType(), Alignment, 0, CostKind));
 215
 216     // Next, compute the cost of packing the result in a vector.
 217     InstructionCost PackingCost = getScalarizationOverhead(
 218         VT, Opcode != Instruction::Store, Opcode == Instruction::Store);
 219
 220     InstructionCost ConditionalCost = 0;
 221     if (VariableMask) {
 222       // Compute the cost of conditionally executing the memory operations with
 223       // variable masks. This includes extracting the individual conditions, a
 224       // branches and PHIs to combine the results.
 225       // NOTE: Estimating the cost of conditionally executing the memory
 226       // operations accurately is quite difficult and the current solution
 227       // provides a very rough estimate only.
 228       ConditionalCost =
 229           VT->getNumElements() *
 230           (getVectorInstrCost(
 231                Instruction::ExtractElement,
 232                FixedVectorType::get(Type::getInt1Ty(DataTy->getContext()),
 233                                     VT->getNumElements()),
 234                -1) +
 235            getCFInstrCost(Instruction::Br, CostKind) +
 236            getCFInstrCost(Instruction::PHI, CostKind));
 237     }
 238
 239     return LoadCost + PackingCost + ConditionalCost;
 240   }
 241
 242 protected:
 243   explicit BasicTTIImplBase(const TargetMachine *TM, const DataLayout &DL)
 244       : BaseT(DL) {}
 245   virtual ~BasicTTIImplBase() = default;
 246
 247   using TargetTransformInfoImplBase::DL;
 248
 249 public:
 250   /// \name Scalar TTI Implementations
 251   /// @{
 252   bool allowsMisalignedMemoryAccesses(LLVMContext &Context, unsigned BitWidth,
 253                                       unsigned AddressSpace, Align Alignment,
 254                                       bool *Fast) const {
 255     EVT E = EVT::getIntegerVT(Context, BitWidth);
 256     return getTLI()->allowsMisalignedMemoryAccesses(
 257         E, AddressSpace, Alignment, MachineMemOperand::MONone, Fast);
 258   }
 259
 260   bool hasBranchDivergence() { return false; }
 261
 262   bool useGPUDivergenceAnalysis() { return false; }
 263
 264   bool isSourceOfDivergence(const Value *V) { return false; }
 265
 266   bool isAlwaysUniform(const Value *V) { return false; }
 267
 268   unsigned getFlatAddressSpace() {
 269     // Return an invalid address space.
 270     return -1;
 271   }
 272
 273   bool collectFlatAddressOperands(SmallVectorImpl<int> &OpIndexes,
 274                                   Intrinsic::ID IID) const {
 275     return false;
 276   }
 277
 278   bool isNoopAddrSpaceCast(unsigned FromAS, unsigned ToAS) const {
 279     return getTLI()->getTargetMachine().isNoopAddrSpaceCast(FromAS, ToAS);
 280   }
 281
 282   unsigned getAssumedAddrSpace(const Value *V) const {
 283     return getTLI()->getTargetMachine().getAssumedAddrSpace(V);
 284   }
 285
 286   std::pair<const Value *, unsigned>
 287   getPredicatedAddrSpace(const Value *V) const {
 288     return getTLI()->getTargetMachine().getPredicatedAddrSpace(V);
 289   }
 290
 291   Value *rewriteIntrinsicWithAddressSpace(IntrinsicInst *II, Value *OldV,
 292                                           Value *NewV) const {
 293     return nullptr;
 294   }
 295
 296   bool isLegalAddImmediate(int64_t imm) {
 297     return getTLI()->isLegalAddImmediate(imm);
 298   }
 299
 300   bool isLegalICmpImmediate(int64_t imm) {
 301     return getTLI()->isLegalICmpImmediate(imm);
 302   }
 303
 304   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
 305                              bool HasBaseReg, int64_t Scale,
 306                              unsigned AddrSpace, Instruction *I = nullptr) {
 307     TargetLoweringBase::AddrMode AM;
 308     AM.BaseGV = BaseGV;
 309     AM.BaseOffs = BaseOffset;
 310     AM.HasBaseReg = HasBaseReg;
 311     AM.Scale = Scale;
 312     return getTLI()->isLegalAddressingMode(DL, AM, Ty, AddrSpace, I);
 313   }
 314
 315   bool isIndexedLoadLegal(TTI::MemIndexedMode M, Type *Ty,
 316                           const DataLayout &DL) const {
 317     EVT VT = getTLI()->getValueType(DL, Ty);
 318     return getTLI()->isIndexedLoadLegal(getISDIndexedMode(M), VT);
 319   }
 320
 321   bool isIndexedStoreLegal(TTI::MemIndexedMode M, Type *Ty,
 322                            const DataLayout &DL) const {
 323     EVT VT = getTLI()->getValueType(DL, Ty);
 324     return getTLI()->isIndexedStoreLegal(getISDIndexedMode(M), VT);
 325   }
 326
 327   bool isLSRCostLess(TTI::LSRCost C1, TTI::LSRCost C2) {
 328     return TargetTransformInfoImplBase::isLSRCostLess(C1, C2);
 329   }
 330
 331   bool isNumRegsMajorCostOfLSR() {
 332     return TargetTransformInfoImplBase::isNumRegsMajorCostOfLSR();
 333   }
 334
 335   bool isProfitableLSRChainElement(Instruction *I) {
 336     return TargetTransformInfoImplBase::isProfitableLSRChainElement(I);
 337   }
 338
 339   InstructionCost getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
 340                                        int64_t BaseOffset, bool HasBaseReg,
 341                                        int64_t Scale, unsigned AddrSpace) {
 342     TargetLoweringBase::AddrMode AM;
 343     AM.BaseGV = BaseGV;
 344     AM.BaseOffs = BaseOffset;
 345     AM.HasBaseReg = HasBaseReg;
 346     AM.Scale = Scale;
 347     return getTLI()->getScalingFactorCost(DL, AM, Ty, AddrSpace);
 348   }
 349
 350   bool isTruncateFree(Type *Ty1, Type *Ty2) {
 351     return getTLI()->isTruncateFree(Ty1, Ty2);
 352   }
 353
 354   bool isProfitableToHoist(Instruction *I) {
 355     return getTLI()->isProfitableToHoist(I);
 356   }
 357
 358   bool useAA() const { return getST()->useAA(); }
 359
 360   bool isTypeLegal(Type *Ty) {
 361     EVT VT = getTLI()->getValueType(DL, Ty);
 362     return getTLI()->isTypeLegal(VT);
 363   }
 364
 365   InstructionCost getRegUsageForType(Type *Ty) {
 366     InstructionCost Val = getTLI()->getTypeLegalizationCost(DL, Ty).first;
 367     assert(Val >= 0 && "Negative cost!");
 368     return Val;
 369   }
 370
 371   InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr,
 372                              ArrayRef<const Value *> Operands,
 373                              TTI::TargetCostKind CostKind) {
 374     return BaseT::getGEPCost(PointeeType, Ptr, Operands, CostKind);
 375   }
 376
 377   unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI,
 378                                             unsigned &JumpTableSize,
 379                                             ProfileSummaryInfo *PSI,
 380                                             BlockFrequencyInfo *BFI) {
 381     /// Try to find the estimated number of clusters. Note that the number of
 382     /// clusters identified in this function could be different from the actual
 383     /// numbers found in lowering. This function ignore switches that are
 384     /// lowered with a mix of jump table / bit test / BTree. This function was
 385     /// initially intended to be used when estimating the cost of switch in
 386     /// inline cost heuristic, but it's a generic cost model to be used in other
 387     /// places (e.g., in loop unrolling).
 388     unsigned N = SI.getNumCases();
 389     const TargetLoweringBase *TLI = getTLI();
 390     const DataLayout &DL = this->getDataLayout();
 391
 392     JumpTableSize = 0;
 393     bool IsJTAllowed = TLI->areJTsAllowed(SI.getParent()->getParent());
 394
 395     // Early exit if both a jump table and bit test are not allowed.
 396     if (N < 1 || (!IsJTAllowed && DL.getIndexSizeInBits(0u) < N))
 397       return N;
 398
 399     APInt MaxCaseVal = SI.case_begin()->getCaseValue()->getValue();
 400     APInt MinCaseVal = MaxCaseVal;
 401     for (auto CI : SI.cases()) {
 402       const APInt &CaseVal = CI.getCaseValue()->getValue();
 403       if (CaseVal.sgt(MaxCaseVal))
 404         MaxCaseVal = CaseVal;
 405       if (CaseVal.slt(MinCaseVal))
 406         MinCaseVal = CaseVal;
 407     }
 408
 409     // Check if suitable for a bit test
 410     if (N <= DL.getIndexSizeInBits(0u)) {
 411       SmallPtrSet<const BasicBlock *, 4> Dests;
 412       for (auto I : SI.cases())
 413         Dests.insert(I.getCaseSuccessor());
 414
 415       if (TLI->isSuitableForBitTests(Dests.size(), N, MinCaseVal, MaxCaseVal,
 416                                      DL))
 417         return 1;
 418     }
 419
 420     // Check if suitable for a jump table.
 421     if (IsJTAllowed) {
 422       if (N < 2 || N < TLI->getMinimumJumpTableEntries())
 423         return N;
 424       uint64_t Range =
 425           (MaxCaseVal - MinCaseVal)
 426               .getLimitedValue(std::numeric_limits<uint64_t>::max() - 1) + 1;
 427       // Check whether a range of clusters is dense enough for a jump table
 428       if (TLI->isSuitableForJumpTable(&SI, N, Range, PSI, BFI)) {
 429         JumpTableSize = Range;
 430         return 1;
 431       }
 432     }
 433     return N;
 434   }
 435
 436   bool shouldBuildLookupTables() {
 437     const TargetLoweringBase *TLI = getTLI();
 438     return TLI->isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
 439            TLI->isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
 440   }
 441
 442   bool shouldBuildRelLookupTables() const {
 443     const TargetMachine &TM = getTLI()->getTargetMachine();
 444     // If non-PIC mode, do not generate a relative lookup table.
 445     if (!TM.isPositionIndependent())
 446       return false;
 447
 448     /// Relative lookup table entries consist of 32-bit offsets.
 449     /// Do not generate relative lookup tables for large code models
 450     /// in 64-bit achitectures where 32-bit offsets might not be enough.
 451     if (TM.getCodeModel() == CodeModel::Medium ||
 452         TM.getCodeModel() == CodeModel::Large)
 453       return false;
 454
 455     Triple TargetTriple = TM.getTargetTriple();
 456     if (!TargetTriple.isArch64Bit())
 457       return false;
 458
 459     // TODO: Triggers issues on aarch64 on darwin, so temporarily disable it
 460     // there.
 461     if (TargetTriple.getArch() == Triple::aarch64 && TargetTriple.isOSDarwin())
 462       return false;
 463
 464     return true;
 465   }
 466
 467   bool haveFastSqrt(Type *Ty) {
 468     const TargetLoweringBase *TLI = getTLI();
 469     EVT VT = TLI->getValueType(DL, Ty);
 470     return TLI->isTypeLegal(VT) &&
 471            TLI->isOperationLegalOrCustom(ISD::FSQRT, VT);
 472   }
 473
 474   bool isFCmpOrdCheaperThanFCmpZero(Type *Ty) {
 475     return true;
 476   }
 477
 478   InstructionCost getFPOpCost(Type *Ty) {
 479     // Check whether FADD is available, as a proxy for floating-point in
 480     // general.
 481     const TargetLoweringBase *TLI = getTLI();
 482     EVT VT = TLI->getValueType(DL, Ty);
 483     if (TLI->isOperationLegalOrCustomOrPromote(ISD::FADD, VT))
 484       return TargetTransformInfo::TCC_Basic;
 485     return TargetTransformInfo::TCC_Expensive;
 486   }
 487
 488   unsigned getInliningThresholdMultiplier() { return 1; }
 489   unsigned adjustInliningThreshold(const CallBase *CB) { return 0; }
 490
 491   int getInlinerVectorBonusPercent() { return 150; }
 492
 493   void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
 494                                TTI::UnrollingPreferences &UP,
 495                                OptimizationRemarkEmitter *ORE) {
 496     // This unrolling functionality is target independent, but to provide some
 497     // motivation for its intended use, for x86:
 498
 499     // According to the Intel 64 and IA-32 Architectures Optimization Reference
 500     // Manual, Intel Core models and later have a loop stream detector (and
 501     // associated uop queue) that can benefit from partial unrolling.
 502     // The relevant requirements are:
 503     //  - The loop must have no more than 4 (8 for Nehalem and later) branches
 504     //    taken, and none of them may be calls.
 505     //  - The loop can have no more than 18 (28 for Nehalem and later) uops.
 506
 507     // According to the Software Optimization Guide for AMD Family 15h
 508     // Processors, models 30h-4fh (Steamroller and later) have a loop predictor
 509     // and loop buffer which can benefit from partial unrolling.
 510     // The relevant requirements are:
 511     //  - The loop must have fewer than 16 branches
 512     //  - The loop must have less than 40 uops in all executed loop branches
 513
 514     // The number of taken branches in a loop is hard to estimate here, and
 515     // benchmarking has revealed that it is better not to be conservative when
 516     // estimating the branch count. As a result, we'll ignore the branch limits
 517     // until someone finds a case where it matters in practice.
 518
 519     unsigned MaxOps;
 520     const TargetSubtargetInfo *ST = getST();
 521     if (PartialUnrollingThreshold.getNumOccurrences() > 0)
 522       MaxOps = PartialUnrollingThreshold;
 523     else if (ST->getSchedModel().LoopMicroOpBufferSize > 0)
 524       MaxOps = ST->getSchedModel().LoopMicroOpBufferSize;
 525     else
 526       return;
 527
 528     // Scan the loop: don't unroll loops with calls.
 529     for (BasicBlock *BB : L->blocks()) {
 530       for (Instruction &I : *BB) {
 531         if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 532           if (const Function *F = cast<CallBase>(I).getCalledFunction()) {
 533             if (!thisT()->isLoweredToCall(F))
 534               continue;
 535           }
 536
 537           if (ORE) {
 538             ORE->emit([&]() {
 539               return OptimizationRemark("TTI", "DontUnroll", L->getStartLoc(),
 540                                         L->getHeader())
 541                      << "advising against unrolling the loop because it "
 542                         "contains a "
 543                      << ore::NV("Call", &I);
 544             });
 545           }
 546           return;
 547         }
 548       }
 549     }
 550
 551     // Enable runtime and partial unrolling up to the specified size.
 552     // Enable using trip count upper bound to unroll loops.
 553     UP.Partial = UP.Runtime = UP.UpperBound = true;
 554     UP.PartialThreshold = MaxOps;
 555
 556     // Avoid unrolling when optimizing for size.
 557     UP.OptSizeThreshold = 0;
 558     UP.PartialOptSizeThreshold = 0;
 559
 560     // Set number of instructions optimized when "back edge"
 561     // becomes "fall through" to default value of 2.
 562     UP.BEInsns = 2;
 563   }
 564
 565   void getPeelingPreferences(Loop *L, ScalarEvolution &SE,
 566                              TTI::PeelingPreferences &PP) {
 567     PP.PeelCount = 0;
 568     PP.AllowPeeling = true;
 569     PP.AllowLoopNestsPeeling = false;
 570     PP.PeelProfiledIterations = true;
 571   }
 572
 573   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
 574                                 AssumptionCache &AC,
 575                                 TargetLibraryInfo *LibInfo,
 576                                 HardwareLoopInfo &HWLoopInfo) {
 577     return BaseT::isHardwareLoopProfitable(L, SE, AC, LibInfo, HWLoopInfo);
 578   }
 579
 580   bool preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
 581                                    AssumptionCache &AC, TargetLibraryInfo *TLI,
 582                                    DominatorTree *DT,
 583                                    const LoopAccessInfo *LAI) {
 584     return BaseT::preferPredicateOverEpilogue(L, LI, SE, AC, TLI, DT, LAI);
 585   }
 586
 587   bool emitGetActiveLaneMask() {
 588     return BaseT::emitGetActiveLaneMask();
 589   }
 590
 591   Optional<Instruction *> instCombineIntrinsic(InstCombiner &IC,
 592                                                IntrinsicInst &II) {
 593     return BaseT::instCombineIntrinsic(IC, II);
 594   }
 595
 596   Optional<Value *> simplifyDemandedUseBitsIntrinsic(InstCombiner &IC,
 597                                                      IntrinsicInst &II,
 598                                                      APInt DemandedMask,
 599                                                      KnownBits &Known,
 600                                                      bool &KnownBitsComputed) {
 601     return BaseT::simplifyDemandedUseBitsIntrinsic(IC, II, DemandedMask, Known,
 602                                                    KnownBitsComputed);
 603   }
 604
 605   Optional<Value *> simplifyDemandedVectorEltsIntrinsic(
 606       InstCombiner &IC, IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
 607       APInt &UndefElts2, APInt &UndefElts3,
 608       std::function<void(Instruction *, unsigned, APInt, APInt &)>
 609           SimplifyAndSetOp) {
 610     return BaseT::simplifyDemandedVectorEltsIntrinsic(
 611         IC, II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
 612         SimplifyAndSetOp);
 613   }
 614
 615   InstructionCost getInstructionLatency(const Instruction *I) {
 616     if (isa<LoadInst>(I))
 617       return getST()->getSchedModel().DefaultLoadLatency;
 618
 619     return BaseT::getInstructionLatency(I);
 620   }
 621
 622   virtual Optional<unsigned>
 623   getCacheSize(TargetTransformInfo::CacheLevel Level) const {
 624     return Optional<unsigned>(
 625       getST()->getCacheSize(static_cast<unsigned>(Level)));
 626   }
 627
 628   virtual Optional<unsigned>
 629   getCacheAssociativity(TargetTransformInfo::CacheLevel Level) const {
 630     Optional<unsigned> TargetResult =
 631         getST()->getCacheAssociativity(static_cast<unsigned>(Level));
 632
 633     if (TargetResult)
 634       return TargetResult;
 635
 636     return BaseT::getCacheAssociativity(Level);
 637   }
 638
 639   virtual unsigned getCacheLineSize() const {
 640     return getST()->getCacheLineSize();
 641   }
 642
 643   virtual unsigned getPrefetchDistance() const {
 644     return getST()->getPrefetchDistance();
 645   }
 646
 647   virtual unsigned getMinPrefetchStride(unsigned NumMemAccesses,
 648                                         unsigned NumStridedMemAccesses,
 649                                         unsigned NumPrefetches,
 650                                         bool HasCall) const {
 651     return getST()->getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses,
 652                                          NumPrefetches, HasCall);
 653   }
 654
 655   virtual unsigned getMaxPrefetchIterationsAhead() const {
 656     return getST()->getMaxPrefetchIterationsAhead();
 657   }
 658
 659   virtual bool enableWritePrefetching() const {
 660     return getST()->enableWritePrefetching();
 661   }
 662
 663   /// @}
 664
 665   /// \name Vector TTI Implementations
 666   /// @{
 667
 668   TypeSize getRegisterBitWidth(TargetTransformInfo::RegisterKind K) const {
 669     return TypeSize::getFixed(32);
 670   }
 671
 672   Optional<unsigned> getMaxVScale() const { return None; }
 673   Optional<unsigned> getVScaleForTuning() const { return None; }
 674
 675   /// Estimate the overhead of scalarizing an instruction. Insert and Extract
 676   /// are set if the demanded result elements need to be inserted and/or
 677   /// extracted from vectors.
 678   InstructionCost getScalarizationOverhead(VectorType *InTy,
 679                                            const APInt &DemandedElts,
 680                                            bool Insert, bool Extract) {
 681     /// FIXME: a bitfield is not a reasonable abstraction for talking about
 682     /// which elements are needed from a scalable vector
 683     auto *Ty = cast<FixedVectorType>(InTy);
 684
 685     assert(DemandedElts.getBitWidth() == Ty->getNumElements() &&
 686            "Vector size mismatch");
 687
 688     InstructionCost Cost = 0;
 689
 690     for (int i = 0, e = Ty->getNumElements(); i < e; ++i) {
 691       if (!DemandedElts[i])
 692         continue;
 693       if (Insert)
 694         Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, Ty, i);
 695       if (Extract)
 696         Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty, i);
 697     }
 698
 699     return Cost;
 700   }
 701
 702   /// Helper wrapper for the DemandedElts variant of getScalarizationOverhead.
 703   InstructionCost getScalarizationOverhead(VectorType *InTy, bool Insert,
 704                                            bool Extract) {
 705     auto *Ty = cast<FixedVectorType>(InTy);
 706
 707     APInt DemandedElts = APInt::getAllOnes(Ty->getNumElements());
 708     return thisT()->getScalarizationOverhead(Ty, DemandedElts, Insert, Extract);
 709   }
 710
 711   /// Estimate the overhead of scalarizing an instructions unique
 712   /// non-constant operands. The (potentially vector) types to use for each of
 713   /// argument are passes via Tys.
 714   InstructionCost getOperandsScalarizationOverhead(ArrayRef<const Value *> Args,
 715                                                    ArrayRef<Type *> Tys) {
 716     assert(Args.size() == Tys.size() && "Expected matching Args and Tys");
 717
 718     InstructionCost Cost = 0;
 719     SmallPtrSet<const Value*, 4> UniqueOperands;
 720     for (int I = 0, E = Args.size(); I != E; I++) {
 721       // Disregard things like metadata arguments.
 722       const Value *A = Args[I];
 723       Type *Ty = Tys[I];
 724       if (!Ty->isIntOrIntVectorTy() && !Ty->isFPOrFPVectorTy() &&
 725           !Ty->isPtrOrPtrVectorTy())
 726         continue;
 727
 728       if (!isa<Constant>(A) && UniqueOperands.insert(A).second) {
 729         if (auto *VecTy = dyn_cast<VectorType>(Ty))
 730           Cost += getScalarizationOverhead(VecTy, false, true);
 731       }
 732     }
 733
 734     return Cost;
 735   }
 736
 737   /// Estimate the overhead of scalarizing the inputs and outputs of an
 738   /// instruction, with return type RetTy and arguments Args of type Tys. If
 739   /// Args are unknown (empty), then the cost associated with one argument is
 740   /// added as a heuristic.
 741   InstructionCost getScalarizationOverhead(VectorType *RetTy,
 742                                            ArrayRef<const Value *> Args,
 743                                            ArrayRef<Type *> Tys) {
 744     InstructionCost Cost = getScalarizationOverhead(RetTy, true, false);
 745     if (!Args.empty())
 746       Cost += getOperandsScalarizationOverhead(Args, Tys);
 747     else
 748       // When no information on arguments is provided, we add the cost
 749       // associated with one argument as a heuristic.
 750       Cost += getScalarizationOverhead(RetTy, false, true);
 751
 752     return Cost;
 753   }
 754
 755   unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
 756
 757   InstructionCost getArithmeticInstrCost(
 758       unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind,
 759       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
 760       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
 761       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
 762       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None,
 763       ArrayRef<const Value *> Args = ArrayRef<const Value *>(),
 764       const Instruction *CxtI = nullptr) {
 765     // Check if any of the operands are vector operands.
 766     const TargetLoweringBase *TLI = getTLI();
 767     int ISD = TLI->InstructionOpcodeToISD(Opcode);
 768     assert(ISD && "Invalid opcode");
 769
 770     // TODO: Handle more cost kinds.
 771     if (CostKind != TTI::TCK_RecipThroughput)
 772       return BaseT::getArithmeticInstrCost(Opcode, Ty, CostKind,
 773                                            Opd1Info, Opd2Info,
 774                                            Opd1PropInfo, Opd2PropInfo,
 775                                            Args, CxtI);
 776
 777     std::pair<InstructionCost, MVT> LT = TLI->getTypeLegalizationCost(DL, Ty);
 778
 779     bool IsFloat = Ty->isFPOrFPVectorTy();
 780     // Assume that floating point arithmetic operations cost twice as much as
 781     // integer operations.
 782     InstructionCost OpCost = (IsFloat ? 2 : 1);
 783
 784     if (TLI->isOperationLegalOrPromote(ISD, LT.second)) {
 785       // The operation is legal. Assume it costs 1.
 786       // TODO: Once we have extract/insert subvector cost we need to use them.
 787       return LT.first * OpCost;
 788     }
 789
 790     if (!TLI->isOperationExpand(ISD, LT.second)) {
 791       // If the operation is custom lowered, then assume that the code is twice
 792       // as expensive.
 793       return LT.first * 2 * OpCost;
 794     }
 795
 796     // An 'Expand' of URem and SRem is special because it may default
 797     // to expanding the operation into a sequence of sub-operations
 798     // i.e. X % Y -> X-(X/Y)*Y.
 799     if (ISD == ISD::UREM || ISD == ISD::SREM) {
 800       bool IsSigned = ISD == ISD::SREM;
 801       if (TLI->isOperationLegalOrCustom(IsSigned ? ISD::SDIVREM : ISD::UDIVREM,
 802                                         LT.second) ||
 803           TLI->isOperationLegalOrCustom(IsSigned ? ISD::SDIV : ISD::UDIV,
 804                                         LT.second)) {
 805         unsigned DivOpc = IsSigned ? Instruction::SDiv : Instruction::UDiv;
 806         InstructionCost DivCost = thisT()->getArithmeticInstrCost(
 807             DivOpc, Ty, CostKind, Opd1Info, Opd2Info, Opd1PropInfo,
 808             Opd2PropInfo);
 809         InstructionCost MulCost =
 810             thisT()->getArithmeticInstrCost(Instruction::Mul, Ty, CostKind);
 811         InstructionCost SubCost =
 812             thisT()->getArithmeticInstrCost(Instruction::Sub, Ty, CostKind);
 813         return DivCost + MulCost + SubCost;
 814       }
 815     }
 816
 817     // We cannot scalarize scalable vectors, so return Invalid.
 818     if (isa<ScalableVectorType>(Ty))
 819       return InstructionCost::getInvalid();
 820
 821     // Else, assume that we need to scalarize this op.
 822     // TODO: If one of the types get legalized by splitting, handle this
 823     // similarly to what getCastInstrCost() does.
 824     if (auto *VTy = dyn_cast<FixedVectorType>(Ty)) {
 825       InstructionCost Cost = thisT()->getArithmeticInstrCost(
 826           Opcode, VTy->getScalarType(), CostKind, Opd1Info, Opd2Info,
 827           Opd1PropInfo, Opd2PropInfo, Args, CxtI);
 828       // Return the cost of multiple scalar invocation plus the cost of
 829       // inserting and extracting the values.
 830       SmallVector<Type *> Tys(Args.size(), Ty);
 831       return getScalarizationOverhead(VTy, Args, Tys) +
 832              VTy->getNumElements() * Cost;
 833     }
 834
 835     // We don't know anything about this scalar instruction.
 836     return OpCost;
 837   }
 838
 839   TTI::ShuffleKind improveShuffleKindFromMask(TTI::ShuffleKind Kind,
 840                                               ArrayRef<int> Mask) const {
 841     int Limit = Mask.size() * 2;
 842     if (Mask.empty() ||
 843         // Extra check required by isSingleSourceMaskImpl function (called by
 844         // ShuffleVectorInst::isSingleSourceMask).
 845         any_of(Mask, [Limit](int I) { return I >= Limit; }))
 846       return Kind;
 847     switch (Kind) {
 848     case TTI::SK_PermuteSingleSrc:
 849       if (ShuffleVectorInst::isReverseMask(Mask))
 850         return TTI::SK_Reverse;
 851       if (ShuffleVectorInst::isZeroEltSplatMask(Mask))
 852         return TTI::SK_Broadcast;
 853       break;
 854     case TTI::SK_PermuteTwoSrc:
 855       if (ShuffleVectorInst::isSelectMask(Mask))
 856         return TTI::SK_Select;
 857       if (ShuffleVectorInst::isTransposeMask(Mask))
 858         return TTI::SK_Transpose;
 859       break;
 860     case TTI::SK_Select:
 861     case TTI::SK_Reverse:
 862     case TTI::SK_Broadcast:
 863     case TTI::SK_Transpose:
 864     case TTI::SK_InsertSubvector:
 865     case TTI::SK_ExtractSubvector:
 866     case TTI::SK_Splice:
 867       break;
 868     }
 869     return Kind;
 870   }
 871
 872   InstructionCost getShuffleCost(TTI::ShuffleKind Kind, VectorType *Tp,
 873                                  ArrayRef<int> Mask, int Index,
 874                                  VectorType *SubTp) {
 875
 876     switch (improveShuffleKindFromMask(Kind, Mask)) {
 877     case TTI::SK_Broadcast:
 878       if (auto *FVT = dyn_cast<FixedVectorType>(Tp))
 879         return getBroadcastShuffleOverhead(FVT);
 880       return InstructionCost::getInvalid();
 881     case TTI::SK_Select:
 882     case TTI::SK_Splice:
 883     case TTI::SK_Reverse:
 884     case TTI::SK_Transpose:
 885     case TTI::SK_PermuteSingleSrc:
 886     case TTI::SK_PermuteTwoSrc:
 887       if (auto *FVT = dyn_cast<FixedVectorType>(Tp))
 888         return getPermuteShuffleOverhead(FVT);
 889       return InstructionCost::getInvalid();
 890     case TTI::SK_ExtractSubvector:
 891       return getExtractSubvectorOverhead(Tp, Index,
 892                                          cast<FixedVectorType>(SubTp));
 893     case TTI::SK_InsertSubvector:
 894       return getInsertSubvectorOverhead(Tp, Index,
 895                                         cast<FixedVectorType>(SubTp));
 896     }
 897     llvm_unreachable("Unknown TTI::ShuffleKind");
 898   }
 899
 900   InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src,
 901                                    TTI::CastContextHint CCH,
 902                                    TTI::TargetCostKind CostKind,
 903                                    const Instruction *I = nullptr) {
 904     if (BaseT::getCastInstrCost(Opcode, Dst, Src, CCH, CostKind, I) == 0)
 905       return 0;
 906
 907     const TargetLoweringBase *TLI = getTLI();
 908     int ISD = TLI->InstructionOpcodeToISD(Opcode);
 909     assert(ISD && "Invalid opcode");
 910     std::pair<InstructionCost, MVT> SrcLT =
 911         TLI->getTypeLegalizationCost(DL, Src);
 912     std::pair<InstructionCost, MVT> DstLT =
 913         TLI->getTypeLegalizationCost(DL, Dst);
 914
 915     TypeSize SrcSize = SrcLT.second.getSizeInBits();
 916     TypeSize DstSize = DstLT.second.getSizeInBits();
 917     bool IntOrPtrSrc = Src->isIntegerTy() || Src->isPointerTy();
 918     bool IntOrPtrDst = Dst->isIntegerTy() || Dst->isPointerTy();
 919
 920     switch (Opcode) {
 921     default:
 922       break;
 923     case Instruction::Trunc:
 924       // Check for NOOP conversions.
 925       if (TLI->isTruncateFree(SrcLT.second, DstLT.second))
 926         return 0;
 927       LLVM_FALLTHROUGH;
 928     case Instruction::BitCast:
 929       // Bitcast between types that are legalized to the same type are free and
 930       // assume int to/from ptr of the same size is also free.
 931       if (SrcLT.first == DstLT.first && IntOrPtrSrc == IntOrPtrDst &&
 932           SrcSize == DstSize)
 933         return 0;
 934       break;
 935     case Instruction::FPExt:
 936       if (I && getTLI()->isExtFree(I))
 937         return 0;
 938       break;
 939     case Instruction::ZExt:
 940       if (TLI->isZExtFree(SrcLT.second, DstLT.second))
 941         return 0;
 942       LLVM_FALLTHROUGH;
 943     case Instruction::SExt:
 944       if (I && getTLI()->isExtFree(I))
 945         return 0;
 946
 947       // If this is a zext/sext of a load, return 0 if the corresponding
 948       // extending load exists on target and the result type is legal.
 949       if (CCH == TTI::CastContextHint::Normal) {
 950         EVT ExtVT = EVT::getEVT(Dst);
 951         EVT LoadVT = EVT::getEVT(Src);
 952         unsigned LType =
 953           ((Opcode == Instruction::ZExt) ? ISD::ZEXTLOAD : ISD::SEXTLOAD);
 954         if (DstLT.first == SrcLT.first &&
 955             TLI->isLoadExtLegal(LType, ExtVT, LoadVT))
 956           return 0;
 957       }
 958       break;
 959     case Instruction::AddrSpaceCast:
 960       if (TLI->isFreeAddrSpaceCast(Src->getPointerAddressSpace(),
 961                                    Dst->getPointerAddressSpace()))
 962         return 0;
 963       break;
 964     }
 965
 966     auto *SrcVTy = dyn_cast<VectorType>(Src);
 967     auto *DstVTy = dyn_cast<VectorType>(Dst);
 968
 969     // If the cast is marked as legal (or promote) then assume low cost.
 970     if (SrcLT.first == DstLT.first &&
 971         TLI->isOperationLegalOrPromote(ISD, DstLT.second))
 972       return SrcLT.first;
 973
 974     // Handle scalar conversions.
 975     if (!SrcVTy && !DstVTy) {
 976       // Just check the op cost. If the operation is legal then assume it costs
 977       // 1.
 978       if (!TLI->isOperationExpand(ISD, DstLT.second))
 979         return 1;
 980
 981       // Assume that illegal scalar instruction are expensive.
 982       return 4;
 983     }
 984
 985     // Check vector-to-vector casts.
 986     if (DstVTy && SrcVTy) {
 987       // If the cast is between same-sized registers, then the check is simple.
 988       if (SrcLT.first == DstLT.first && SrcSize == DstSize) {
 989
 990         // Assume that Zext is done using AND.
 991         if (Opcode == Instruction::ZExt)
 992           return SrcLT.first;
 993
 994         // Assume that sext is done using SHL and SRA.
 995         if (Opcode == Instruction::SExt)
 996           return SrcLT.first * 2;
 997
 998         // Just check the op cost. If the operation is legal then assume it
 999         // costs
1000         // 1 and multiply by the type-legalization overhead.
1001         if (!TLI->isOperationExpand(ISD, DstLT.second))
1002           return SrcLT.first * 1;
1003       }
1004
1005       // If we are legalizing by splitting, query the concrete TTI for the cost
1006       // of casting the original vector twice. We also need to factor in the
1007       // cost of the split itself. Count that as 1, to be consistent with
1008       // TLI->getTypeLegalizationCost().
1009       bool SplitSrc =
1010           TLI->getTypeAction(Src->getContext(), TLI->getValueType(DL, Src)) ==
1011           TargetLowering::TypeSplitVector;
1012       bool SplitDst =
1013           TLI->getTypeAction(Dst->getContext(), TLI->getValueType(DL, Dst)) ==
1014           TargetLowering::TypeSplitVector;
1015       if ((SplitSrc || SplitDst) && SrcVTy->getElementCount().isVector() &&
1016           DstVTy->getElementCount().isVector()) {
1017         Type *SplitDstTy = VectorType::getHalfElementsVectorType(DstVTy);
1018         Type *SplitSrcTy = VectorType::getHalfElementsVectorType(SrcVTy);
1019         T *TTI = static_cast<T *>(this);
1020         // If both types need to be split then the split is free.
1021         InstructionCost SplitCost =
1022             (!SplitSrc || !SplitDst) ? TTI->getVectorSplitCost() : 0;
1023         return SplitCost +
1024                (2 * TTI->getCastInstrCost(Opcode, SplitDstTy, SplitSrcTy, CCH,
1025                                           CostKind, I));
1026       }
1027
1028       // Scalarization cost is Invalid, can't assume any num elements.
1029       if (isa<ScalableVectorType>(DstVTy))
1030         return InstructionCost::getInvalid();
1031
1032       // In other cases where the source or destination are illegal, assume
1033       // the operation will get scalarized.
1034       unsigned Num = cast<FixedVectorType>(DstVTy)->getNumElements();
1035       InstructionCost Cost = thisT()->getCastInstrCost(
1036           Opcode, Dst->getScalarType(), Src->getScalarType(), CCH, CostKind, I);
1037
1038       // Return the cost of multiple scalar invocation plus the cost of
1039       // inserting and extracting the values.
1040       return getScalarizationOverhead(DstVTy, true, true) + Num * Cost;
1041     }
1042
1043     // We already handled vector-to-vector and scalar-to-scalar conversions.
1044     // This
1045     // is where we handle bitcast between vectors and scalars. We need to assume
1046     //  that the conversion is scalarized in one way or another.
1047     if (Opcode == Instruction::BitCast) {
1048       // Illegal bitcasts are done by storing and loading from a stack slot.
1049       return (SrcVTy ? getScalarizationOverhead(SrcVTy, false, true) : 0) +
1050              (DstVTy ? getScalarizationOverhead(DstVTy, true, false) : 0);
1051     }
1052
1053     llvm_unreachable("Unhandled cast");
1054   }
1055
1056   InstructionCost getExtractWithExtendCost(unsigned Opcode, Type *Dst,
1057                                            VectorType *VecTy, unsigned Index) {
1058     return thisT()->getVectorInstrCost(Instruction::ExtractElement, VecTy,
1059                                        Index) +
1060            thisT()->getCastInstrCost(Opcode, Dst, VecTy->getElementType(),
1061                                      TTI::CastContextHint::None,
1062                                      TTI::TCK_RecipThroughput);
1063   }
1064
1065   InstructionCost getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind,
1066                                  const Instruction *I = nullptr) {
1067     return BaseT::getCFInstrCost(Opcode, CostKind, I);
1068   }
1069
1070   InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy,
1071                                      CmpInst::Predicate VecPred,
1072                                      TTI::TargetCostKind CostKind,
1073                                      const Instruction *I = nullptr) {
1074     const TargetLoweringBase *TLI = getTLI();
1075     int ISD = TLI->InstructionOpcodeToISD(Opcode);
1076     assert(ISD && "Invalid opcode");
1077
1078     // TODO: Handle other cost kinds.
1079     if (CostKind != TTI::TCK_RecipThroughput)
1080       return BaseT::getCmpSelInstrCost(Opcode, ValTy, CondTy, VecPred, CostKind,
1081                                        I);
1082
1083     // Selects on vectors are actually vector selects.
1084     if (ISD == ISD::SELECT) {
1085       assert(CondTy && "CondTy must exist");
1086       if (CondTy->isVectorTy())
1087         ISD = ISD::VSELECT;
1088     }
1089     std::pair<InstructionCost, MVT> LT =
1090         TLI->getTypeLegalizationCost(DL, ValTy);
1091
1092     if (!(ValTy->isVectorTy() && !LT.second.isVector()) &&
1093         !TLI->isOperationExpand(ISD, LT.second)) {
1094       // The operation is legal. Assume it costs 1. Multiply
1095       // by the type-legalization overhead.
1096       return LT.first * 1;
1097     }
1098
1099     // Otherwise, assume that the cast is scalarized.
1100     // TODO: If one of the types get legalized by splitting, handle this
1101     // similarly to what getCastInstrCost() does.
1102     if (auto *ValVTy = dyn_cast<VectorType>(ValTy)) {
1103       unsigned Num = cast<FixedVectorType>(ValVTy)->getNumElements();
1104       if (CondTy)
1105         CondTy = CondTy->getScalarType();
1106       InstructionCost Cost = thisT()->getCmpSelInstrCost(
1107           Opcode, ValVTy->getScalarType(), CondTy, VecPred, CostKind, I);
1108
1109       // Return the cost of multiple scalar invocation plus the cost of
1110       // inserting and extracting the values.
1111       return getScalarizationOverhead(ValVTy, true, false) + Num * Cost;
1112     }
1113
1114     // Unknown scalar opcode.
1115     return 1;
1116   }
1117
1118   InstructionCost getVectorInstrCost(unsigned Opcode, Type *Val,
1119                                      unsigned Index) {
1120     std::pair<InstructionCost, MVT> LT =
1121         getTLI()->getTypeLegalizationCost(DL, Val->getScalarType());
1122
1123     return LT.first;
1124   }
1125
1126   InstructionCost getReplicationShuffleCost(Type *EltTy, int ReplicationFactor,
1127                                             int VF,
1128                                             const APInt &DemandedDstElts,
1129                                             TTI::TargetCostKind CostKind) {
1130     assert(DemandedDstElts.getBitWidth() == (unsigned)VF * ReplicationFactor &&
1131            "Unexpected size of DemandedDstElts.");
1132
1133     InstructionCost Cost;
1134
1135     auto *SrcVT = FixedVectorType::get(EltTy, VF);
1136     auto *ReplicatedVT = FixedVectorType::get(EltTy, VF * ReplicationFactor);
1137
1138     // The Mask shuffling cost is extract all the elements of the Mask
1139     // and insert each of them Factor times into the wide vector:
1140     //
1141     // E.g. an interleaved group with factor 3:
1142     //    %mask = icmp ult <8 x i32> %vec1, %vec2
1143     //    %interleaved.mask = shufflevector <8 x i1> %mask, <8 x i1> undef,
1144     //        <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>
1145     // The cost is estimated as extract all mask elements from the <8xi1> mask
1146     // vector and insert them factor times into the <24xi1> shuffled mask
1147     // vector.
1148     APInt DemandedSrcElts = APIntOps::ScaleBitMask(DemandedDstElts, VF);
1149     Cost += thisT()->getScalarizationOverhead(SrcVT, DemandedSrcElts,
1150                                               /*Insert*/ false,
1151                                               /*Extract*/ true);
1152     Cost +=
1153         thisT()->getScalarizationOverhead(ReplicatedVT, DemandedDstElts,
1154                                           /*Insert*/ true, /*Extract*/ false);
1155
1156     return Cost;
1157   }
1158
1159   InstructionCost getMemoryOpCost(unsigned Opcode, Type *Src,
1160                                   MaybeAlign Alignment, unsigned AddressSpace,
1161                                   TTI::TargetCostKind CostKind,
1162                                   const Instruction *I = nullptr) {
1163     assert(!Src->isVoidTy() && "Invalid type");
1164     // Assume types, such as structs, are expensive.
1165     if (getTLI()->getValueType(DL, Src,  true) == MVT::Other)
1166       return 4;
1167     std::pair<InstructionCost, MVT> LT =
1168         getTLI()->getTypeLegalizationCost(DL, Src);
1169
1170     // Assuming that all loads of legal types cost 1.
1171     InstructionCost Cost = LT.first;
1172     if (CostKind != TTI::TCK_RecipThroughput)
1173       return Cost;
1174
1175     if (Src->isVectorTy() &&
1176         // In practice it's not currently possible to have a change in lane
1177         // length for extending loads or truncating stores so both types should
1178         // have the same scalable property.
1179         TypeSize::isKnownLT(Src->getPrimitiveSizeInBits(),
1180                             LT.second.getSizeInBits())) {
1181       // This is a vector load that legalizes to a larger type than the vector
1182       // itself. Unless the corresponding extending load or truncating store is
1183       // legal, then this will scalarize.
1184       TargetLowering::LegalizeAction LA = TargetLowering::Expand;
1185       EVT MemVT = getTLI()->getValueType(DL, Src);
1186       if (Opcode == Instruction::Store)
1187         LA = getTLI()->getTruncStoreAction(LT.second, MemVT);
1188       else
1189         LA = getTLI()->getLoadExtAction(ISD::EXTLOAD, LT.second, MemVT);
1190
1191       if (LA != TargetLowering::Legal && LA != TargetLowering::Custom) {
1192         // This is a vector load/store for some illegal type that is scalarized.
1193         // We must account for the cost of building or decomposing the vector.
1194         Cost += getScalarizationOverhead(cast<VectorType>(Src),
1195                                          Opcode != Instruction::Store,
1196                                          Opcode == Instruction::Store);
1197       }
1198     }
1199
1200     return Cost;
1201   }
1202
1203   InstructionCost getMaskedMemoryOpCost(unsigned Opcode, Type *DataTy,
1204                                         Align Alignment, unsigned AddressSpace,
1205                                         TTI::TargetCostKind CostKind) {
1206     return getCommonMaskedMemoryOpCost(Opcode, DataTy, Alignment, true, false,
1207                                        CostKind);
1208   }
1209
1210   InstructionCost getGatherScatterOpCost(unsigned Opcode, Type *DataTy,
1211                                          const Value *Ptr, bool VariableMask,
1212                                          Align Alignment,
1213                                          TTI::TargetCostKind CostKind,
1214                                          const Instruction *I = nullptr) {
1215     return getCommonMaskedMemoryOpCost(Opcode, DataTy, Alignment, VariableMask,
1216                                        true, CostKind);
1217   }
1218
1219   InstructionCost getInterleavedMemoryOpCost(
1220       unsigned Opcode, Type *VecTy, unsigned Factor, ArrayRef<unsigned> Indices,
1221       Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind,
1222       bool UseMaskForCond = false, bool UseMaskForGaps = false) {
1223     auto *VT = cast<FixedVectorType>(VecTy);
1224
1225     unsigned NumElts = VT->getNumElements();
1226     assert(Factor > 1 && NumElts % Factor == 0 && "Invalid interleave factor");
1227
1228     unsigned NumSubElts = NumElts / Factor;
1229     auto *SubVT = FixedVectorType::get(VT->getElementType(), NumSubElts);
1230
1231     // Firstly, the cost of load/store operation.
1232     InstructionCost Cost;
1233     if (UseMaskForCond || UseMaskForGaps)
1234       Cost = thisT()->getMaskedMemoryOpCost(Opcode, VecTy, Alignment,
1235                                             AddressSpace, CostKind);
1236     else
1237       Cost = thisT()->getMemoryOpCost(Opcode, VecTy, Alignment, AddressSpace,
1238                                       CostKind);
1239
1240     // Legalize the vector type, and get the legalized and unlegalized type
1241     // sizes.
1242     MVT VecTyLT = getTLI()->getTypeLegalizationCost(DL, VecTy).second;
1243     unsigned VecTySize = thisT()->getDataLayout().getTypeStoreSize(VecTy);
1244     unsigned VecTyLTSize = VecTyLT.getStoreSize();
1245
1246     // Scale the cost of the memory operation by the fraction of legalized
1247     // instructions that will actually be used. We shouldn't account for the
1248     // cost of dead instructions since they will be removed.
1249     //
1250     // E.g., An interleaved load of factor 8:
1251     //       %vec = load <16 x i64>, <16 x i64>* %ptr
1252     //       %v0 = shufflevector %vec, undef, <0, 8>
1253     //
1254     // If <16 x i64> is legalized to 8 v2i64 loads, only 2 of the loads will be
1255     // used (those corresponding to elements [0:1] and [8:9] of the unlegalized
1256     // type). The other loads are unused.
1257     //
1258     // TODO: Note that legalization can turn masked loads/stores into unmasked
1259     // (legalized) loads/stores. This can be reflected in the cost.
1260     if (Cost.isValid() && VecTySize > VecTyLTSize) {
1261       // The number of loads of a legal type it will take to represent a load
1262       // of the unlegalized vector type.
1263       unsigned NumLegalInsts = divideCeil(VecTySize, VecTyLTSize);
1264
1265       // The number of elements of the unlegalized type that correspond to a
1266       // single legal instruction.
1267       unsigned NumEltsPerLegalInst = divideCeil(NumElts, NumLegalInsts);
1268
1269       // Determine which legal instructions will be used.
1270       BitVector UsedInsts(NumLegalInsts, false);
1271       for (unsigned Index : Indices)
1272         for (unsigned Elt = 0; Elt < NumSubElts; ++Elt)
1273           UsedInsts.set((Index + Elt * Factor) / NumEltsPerLegalInst);
1274
1275       // Scale the cost of the load by the fraction of legal instructions that
1276       // will be used.
1277       Cost = divideCeil(UsedInsts.count() * Cost.getValue().getValue(),
1278                         NumLegalInsts);
1279     }
1280
1281     // Then plus the cost of interleave operation.
1282     assert(Indices.size() <= Factor &&
1283            "Interleaved memory op has too many members");
1284
1285     const APInt DemandedAllSubElts = APInt::getAllOnes(NumSubElts);
1286     const APInt DemandedAllResultElts = APInt::getAllOnes(NumElts);
1287
1288     APInt DemandedLoadStoreElts = APInt::getZero(NumElts);
1289     for (unsigned Index : Indices) {
1290       assert(Index < Factor && "Invalid index for interleaved memory op");
1291       for (unsigned Elm = 0; Elm < NumSubElts; Elm++)
1292         DemandedLoadStoreElts.setBit(Index + Elm * Factor);
1293     }
1294
1295     if (Opcode == Instruction::Load) {
1296       // The interleave cost is similar to extract sub vectors' elements
1297       // from the wide vector, and insert them into sub vectors.
1298       //
1299       // E.g. An interleaved load of factor 2 (with one member of index 0):
1300       //      %vec = load <8 x i32>, <8 x i32>* %ptr
1301       //      %v0 = shuffle %vec, undef, <0, 2, 4, 6>         ; Index 0
1302       // The cost is estimated as extract elements at 0, 2, 4, 6 from the
1303       // <8 x i32> vector and insert them into a <4 x i32> vector.
1304       InstructionCost InsSubCost =
1305           thisT()->getScalarizationOverhead(SubVT, DemandedAllSubElts,
1306                                             /*Insert*/ true, /*Extract*/ false);
1307       Cost += Indices.size() * InsSubCost;
1308       Cost +=
1309           thisT()->getScalarizationOverhead(VT, DemandedLoadStoreElts,
1310                                             /*Insert*/ false, /*Extract*/ true);
1311     } else {
1312       // The interleave cost is extract elements from sub vectors, and
1313       // insert them into the wide vector.
1314       //
1315       // E.g. An interleaved store of factor 3 with 2 members at indices 0,1:
1316       // (using VF=4):
1317       //    %v0_v1 = shuffle %v0, %v1, <0,4,undef,1,5,undef,2,6,undef,3,7,undef>
1318       //    %gaps.mask = <true, true, false, true, true, false,
1319       //                  true, true, false, true, true, false>
1320       //    call llvm.masked.store <12 x i32> %v0_v1, <12 x i32>* %ptr,
1321       //                           i32 Align, <12 x i1> %gaps.mask
1322       // The cost is estimated as extract all elements (of actual members,
1323       // excluding gaps) from both <4 x i32> vectors and insert into the <12 x
1324       // i32> vector.
1325       InstructionCost ExtSubCost =
1326           thisT()->getScalarizationOverhead(SubVT, DemandedAllSubElts,
1327                                             /*Insert*/ false, /*Extract*/ true);
1328       Cost += ExtSubCost * Indices.size();
1329       Cost += thisT()->getScalarizationOverhead(VT, DemandedLoadStoreElts,
1330                                                 /*Insert*/ true,
1331                                                 /*Extract*/ false);
1332     }
1333
1334     if (!UseMaskForCond)
1335       return Cost;
1336
1337     Type *I8Type = Type::getInt8Ty(VT->getContext());
1338
1339     Cost += thisT()->getReplicationShuffleCost(
1340         I8Type, Factor, NumSubElts,
1341         UseMaskForGaps ? DemandedLoadStoreElts : DemandedAllResultElts,
1342         CostKind);
1343
1344     // The Gaps mask is invariant and created outside the loop, therefore the
1345     // cost of creating it is not accounted for here. However if we have both
1346     // a MaskForGaps and some other mask that guards the execution of the
1347     // memory access, we need to account for the cost of And-ing the two masks
1348     // inside the loop.
1349     if (UseMaskForGaps) {
1350       auto *MaskVT = FixedVectorType::get(I8Type, NumElts);
1351       Cost += thisT()->getArithmeticInstrCost(BinaryOperator::And, MaskVT,
1352                                               CostKind);
1353     }
1354
1355     return Cost;
1356   }
1357
1358   /// Get intrinsic cost based on arguments.
1359   InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
1360                                         TTI::TargetCostKind CostKind) {
1361     // Check for generically free intrinsics.
1362     if (BaseT::getIntrinsicInstrCost(ICA, CostKind) == 0)
1363       return 0;
1364
1365     // Assume that target intrinsics are cheap.
1366     Intrinsic::ID IID = ICA.getID();
1367     if (Function::isTargetIntrinsic(IID))
1368       return TargetTransformInfo::TCC_Basic;
1369
1370     if (ICA.isTypeBasedOnly())
1371       return getTypeBasedIntrinsicInstrCost(ICA, CostKind);
1372
1373     Type *RetTy = ICA.getReturnType();
1374
1375     ElementCount RetVF =
1376         (RetTy->isVectorTy() ? cast<VectorType>(RetTy)->getElementCount()
1377                              : ElementCount::getFixed(1));
1378     const IntrinsicInst *I = ICA.getInst();
1379     const SmallVectorImpl<const Value *> &Args = ICA.getArgs();
1380     FastMathFlags FMF = ICA.getFlags();
1381     switch (IID) {
1382     default:
1383       break;
1384
1385     case Intrinsic::cttz:
1386       // FIXME: If necessary, this should go in target-specific overrides.
1387       if (RetVF.isScalar() && getTLI()->isCheapToSpeculateCttz())
1388         return TargetTransformInfo::TCC_Basic;
1389       break;
1390
1391     case Intrinsic::ctlz:
1392       // FIXME: If necessary, this should go in target-specific overrides.
1393       if (RetVF.isScalar() && getTLI()->isCheapToSpeculateCtlz())
1394         return TargetTransformInfo::TCC_Basic;
1395       break;
1396
1397     case Intrinsic::memcpy:
1398       return thisT()->getMemcpyCost(ICA.getInst());
1399
1400     case Intrinsic::masked_scatter: {
1401       const Value *Mask = Args[3];
1402       bool VarMask = !isa<Constant>(Mask);
1403       Align Alignment = cast<ConstantInt>(Args[2])->getAlignValue();
1404       return thisT()->getGatherScatterOpCost(Instruction::Store,
1405                                              ICA.getArgTypes()[0], Args[1],
1406                                              VarMask, Alignment, CostKind, I);
1407     }
1408     case Intrinsic::masked_gather: {
1409       const Value *Mask = Args[2];
1410       bool VarMask = !isa<Constant>(Mask);
1411       Align Alignment = cast<ConstantInt>(Args[1])->getAlignValue();
1412       return thisT()->getGatherScatterOpCost(Instruction::Load, RetTy, Args[0],
1413                                              VarMask, Alignment, CostKind, I);
1414     }
1415     case Intrinsic::experimental_stepvector: {
1416       if (isa<ScalableVectorType>(RetTy))
1417         return BaseT::getIntrinsicInstrCost(ICA, CostKind);
1418       // The cost of materialising a constant integer vector.
1419       return TargetTransformInfo::TCC_Basic;
1420     }
1421     case Intrinsic::experimental_vector_extract: {
1422       // FIXME: Handle case where a scalable vector is extracted from a scalable
1423       // vector
1424       if (isa<ScalableVectorType>(RetTy))
1425         return BaseT::getIntrinsicInstrCost(ICA, CostKind);
1426       unsigned Index = cast<ConstantInt>(Args[1])->getZExtValue();
1427       return thisT()->getShuffleCost(TTI::SK_ExtractSubvector,
1428                                      cast<VectorType>(Args[0]->getType()), None,
1429                                      Index, cast<VectorType>(RetTy));
1430     }
1431     case Intrinsic::experimental_vector_insert: {
1432       // FIXME: Handle case where a scalable vector is inserted into a scalable
1433       // vector
1434       if (isa<ScalableVectorType>(Args[1]->getType()))
1435         return BaseT::getIntrinsicInstrCost(ICA, CostKind);
1436       unsigned Index = cast<ConstantInt>(Args[2])->getZExtValue();
1437       return thisT()->getShuffleCost(
1438           TTI::SK_InsertSubvector, cast<VectorType>(Args[0]->getType()), None,
1439           Index, cast<VectorType>(Args[1]->getType()));
1440     }
1441     case Intrinsic::experimental_vector_reverse: {
1442       return thisT()->getShuffleCost(TTI::SK_Reverse,
1443                                      cast<VectorType>(Args[0]->getType()), None,
1444                                      0, cast<VectorType>(RetTy));
1445     }
1446     case Intrinsic::experimental_vector_splice: {
1447       unsigned Index = cast<ConstantInt>(Args[2])->getZExtValue();
1448       return thisT()->getShuffleCost(TTI::SK_Splice,
1449                                      cast<VectorType>(Args[0]->getType()), None,
1450                                      Index, cast<VectorType>(RetTy));
1451     }
1452     case Intrinsic::vector_reduce_add:
1453     case Intrinsic::vector_reduce_mul:
1454     case Intrinsic::vector_reduce_and:
1455     case Intrinsic::vector_reduce_or:
1456     case Intrinsic::vector_reduce_xor:
1457     case Intrinsic::vector_reduce_smax:
1458     case Intrinsic::vector_reduce_smin:
1459     case Intrinsic::vector_reduce_fmax:
1460     case Intrinsic::vector_reduce_fmin:
1461     case Intrinsic::vector_reduce_umax:
1462     case Intrinsic::vector_reduce_umin: {
1463       IntrinsicCostAttributes Attrs(IID, RetTy, Args[0]->getType(), FMF, I, 1);
1464       return getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
1465     }
1466     case Intrinsic::vector_reduce_fadd:
1467     case Intrinsic::vector_reduce_fmul: {
1468       IntrinsicCostAttributes Attrs(
1469           IID, RetTy, {Args[0]->getType(), Args[1]->getType()}, FMF, I, 1);
1470       return getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
1471     }
1472     case Intrinsic::fshl:
1473     case Intrinsic::fshr: {
1474       if (isa<ScalableVectorType>(RetTy))
1475         return BaseT::getIntrinsicInstrCost(ICA, CostKind);
1476       const Value *X = Args[0];
1477       const Value *Y = Args[1];
1478       const Value *Z = Args[2];
1479       TTI::OperandValueProperties OpPropsX, OpPropsY, OpPropsZ, OpPropsBW;
1480       TTI::OperandValueKind OpKindX = TTI::getOperandInfo(X, OpPropsX);
1481       TTI::OperandValueKind OpKindY = TTI::getOperandInfo(Y, OpPropsY);
1482       TTI::OperandValueKind OpKindZ = TTI::getOperandInfo(Z, OpPropsZ);
1483       TTI::OperandValueKind OpKindBW = TTI::OK_UniformConstantValue;
1484       OpPropsBW = isPowerOf2_32(RetTy->getScalarSizeInBits()) ? TTI::OP_PowerOf2
1485                                                               : TTI::OP_None;
1486       // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
1487       // fshr: (X << (BW - (Z % BW))) | (Y >> (Z % BW))
1488       InstructionCost Cost = 0;
1489       Cost +=
1490           thisT()->getArithmeticInstrCost(BinaryOperator::Or, RetTy, CostKind);
1491       Cost +=
1492           thisT()->getArithmeticInstrCost(BinaryOperator::Sub, RetTy, CostKind);
1493       Cost += thisT()->getArithmeticInstrCost(
1494           BinaryOperator::Shl, RetTy, CostKind, OpKindX, OpKindZ, OpPropsX);
1495       Cost += thisT()->getArithmeticInstrCost(
1496           BinaryOperator::LShr, RetTy, CostKind, OpKindY, OpKindZ, OpPropsY);
1497       // Non-constant shift amounts requires a modulo.
1498       if (OpKindZ != TTI::OK_UniformConstantValue &&
1499           OpKindZ != TTI::OK_NonUniformConstantValue)
1500         Cost += thisT()->getArithmeticInstrCost(BinaryOperator::URem, RetTy,
1501                                                 CostKind, OpKindZ, OpKindBW,
1502                                                 OpPropsZ, OpPropsBW);
1503       // For non-rotates (X != Y) we must add shift-by-zero handling costs.
1504       if (X != Y) {
1505         Type *CondTy = RetTy->getWithNewBitWidth(1);
1506         Cost +=
1507             thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
1508                                         CmpInst::ICMP_EQ, CostKind);
1509         Cost +=
1510             thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
1511                                         CmpInst::ICMP_EQ, CostKind);
1512       }
1513       return Cost;
1514     }
1515     }
1516
1517     // Assume that we need to scalarize this intrinsic.
1518     // Compute the scalarization overhead based on Args for a vector
1519     // intrinsic.
1520     InstructionCost ScalarizationCost = InstructionCost::getInvalid();
1521     if (RetVF.isVector() && !RetVF.isScalable()) {
1522       ScalarizationCost = 0;
1523       if (!RetTy->isVoidTy())
1524         ScalarizationCost +=
1525             getScalarizationOverhead(cast<VectorType>(RetTy), true, false);
1526       ScalarizationCost +=
1527           getOperandsScalarizationOverhead(Args, ICA.getArgTypes());
1528     }
1529
1530     IntrinsicCostAttributes Attrs(IID, RetTy, ICA.getArgTypes(), FMF, I,
1531                                   ScalarizationCost);
1532     return thisT()->getTypeBasedIntrinsicInstrCost(Attrs, CostKind);
1533   }
1534
1535   /// Get intrinsic cost based on argument types.
1536   /// If ScalarizationCostPassed is std::numeric_limits<unsigned>::max(), the
1537   /// cost of scalarizing the arguments and the return value will be computed
1538   /// based on types.
1539   InstructionCost
1540   getTypeBasedIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
1541                                  TTI::TargetCostKind CostKind) {
1542     Intrinsic::ID IID = ICA.getID();
1543     Type *RetTy = ICA.getReturnType();
1544     const SmallVectorImpl<Type *> &Tys = ICA.getArgTypes();
1545     FastMathFlags FMF = ICA.getFlags();
1546     InstructionCost ScalarizationCostPassed = ICA.getScalarizationCost();
1547     bool SkipScalarizationCost = ICA.skipScalarizationCost();
1548
1549     VectorType *VecOpTy = nullptr;
1550     if (!Tys.empty()) {
1551       // The vector reduction operand is operand 0 except for fadd/fmul.
1552       // Their operand 0 is a scalar start value, so the vector op is operand 1.
1553       unsigned VecTyIndex = 0;
1554       if (IID == Intrinsic::vector_reduce_fadd ||
1555           IID == Intrinsic::vector_reduce_fmul)
1556         VecTyIndex = 1;
1557       assert(Tys.size() > VecTyIndex && "Unexpected IntrinsicCostAttributes");
1558       VecOpTy = dyn_cast<VectorType>(Tys[VecTyIndex]);
1559     }
1560
1561     // Library call cost - other than size, make it expensive.
1562     unsigned SingleCallCost = CostKind == TTI::TCK_CodeSize ? 1 : 10;
1563     SmallVector<unsigned, 2> ISDs;
1564     switch (IID) {
1565     default: {
1566       // Scalable vectors cannot be scalarized, so return Invalid.
1567       if (isa<ScalableVectorType>(RetTy) || any_of(Tys, [](const Type *Ty) {
1568             return isa<ScalableVectorType>(Ty);
1569           }))
1570         return InstructionCost::getInvalid();
1571
1572       // Assume that we need to scalarize this intrinsic.
1573       InstructionCost ScalarizationCost =
1574           SkipScalarizationCost ? ScalarizationCostPassed : 0;
1575       unsigned ScalarCalls = 1;
1576       Type *ScalarRetTy = RetTy;
1577       if (auto *RetVTy = dyn_cast<VectorType>(RetTy)) {
1578         if (!SkipScalarizationCost)
1579           ScalarizationCost = getScalarizationOverhead(RetVTy, true, false);
1580         ScalarCalls = std::max(ScalarCalls,
1581                                cast<FixedVectorType>(RetVTy)->getNumElements());
1582         ScalarRetTy = RetTy->getScalarType();
1583       }
1584       SmallVector<Type *, 4> ScalarTys;
1585       for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
1586         Type *Ty = Tys[i];
1587         if (auto *VTy = dyn_cast<VectorType>(Ty)) {
1588           if (!SkipScalarizationCost)
1589             ScalarizationCost += getScalarizationOverhead(VTy, false, true);
1590           ScalarCalls = std::max(ScalarCalls,
1591                                  cast<FixedVectorType>(VTy)->getNumElements());
1592           Ty = Ty->getScalarType();
1593         }
1594         ScalarTys.push_back(Ty);
1595       }
1596       if (ScalarCalls == 1)
1597         return 1; // Return cost of a scalar intrinsic. Assume it to be cheap.
1598
1599       IntrinsicCostAttributes ScalarAttrs(IID, ScalarRetTy, ScalarTys, FMF);
1600       InstructionCost ScalarCost =
1601           thisT()->getIntrinsicInstrCost(ScalarAttrs, CostKind);
1602
1603       return ScalarCalls * ScalarCost + ScalarizationCost;
1604     }
1605     // Look for intrinsics that can be lowered directly or turned into a scalar
1606     // intrinsic call.
1607     case Intrinsic::sqrt:
1608       ISDs.push_back(ISD::FSQRT);
1609       break;
1610     case Intrinsic::sin:
1611       ISDs.push_back(ISD::FSIN);
1612       break;
1613     case Intrinsic::cos:
1614       ISDs.push_back(ISD::FCOS);
1615       break;
1616     case Intrinsic::exp:
1617       ISDs.push_back(ISD::FEXP);
1618       break;
1619     case Intrinsic::exp2:
1620       ISDs.push_back(ISD::FEXP2);
1621       break;
1622     case Intrinsic::log:
1623       ISDs.push_back(ISD::FLOG);
1624       break;
1625     case Intrinsic::log10:
1626       ISDs.push_back(ISD::FLOG10);
1627       break;
1628     case Intrinsic::log2:
1629       ISDs.push_back(ISD::FLOG2);
1630       break;
1631     case Intrinsic::fabs:
1632       ISDs.push_back(ISD::FABS);
1633       break;
1634     case Intrinsic::canonicalize:
1635       ISDs.push_back(ISD::FCANONICALIZE);
1636       break;
1637     case Intrinsic::minnum:
1638       ISDs.push_back(ISD::FMINNUM);
1639       break;
1640     case Intrinsic::maxnum:
1641       ISDs.push_back(ISD::FMAXNUM);
1642       break;
1643     case Intrinsic::minimum:
1644       ISDs.push_back(ISD::FMINIMUM);
1645       break;
1646     case Intrinsic::maximum:
1647       ISDs.push_back(ISD::FMAXIMUM);
1648       break;
1649     case Intrinsic::copysign:
1650       ISDs.push_back(ISD::FCOPYSIGN);
1651       break;
1652     case Intrinsic::floor:
1653       ISDs.push_back(ISD::FFLOOR);
1654       break;
1655     case Intrinsic::ceil:
1656       ISDs.push_back(ISD::FCEIL);
1657       break;
1658     case Intrinsic::trunc:
1659       ISDs.push_back(ISD::FTRUNC);
1660       break;
1661     case Intrinsic::nearbyint:
1662       ISDs.push_back(ISD::FNEARBYINT);
1663       break;
1664     case Intrinsic::rint:
1665       ISDs.push_back(ISD::FRINT);
1666       break;
1667     case Intrinsic::round:
1668       ISDs.push_back(ISD::FROUND);
1669       break;
1670     case Intrinsic::roundeven:
1671       ISDs.push_back(ISD::FROUNDEVEN);
1672       break;
1673     case Intrinsic::pow:
1674       ISDs.push_back(ISD::FPOW);
1675       break;
1676     case Intrinsic::fma:
1677       ISDs.push_back(ISD::FMA);
1678       break;
1679     case Intrinsic::fmuladd:
1680       ISDs.push_back(ISD::FMA);
1681       break;
1682     case Intrinsic::experimental_constrained_fmuladd:
1683       ISDs.push_back(ISD::STRICT_FMA);
1684       break;
1685     // FIXME: We should return 0 whenever getIntrinsicCost == TCC_Free.
1686     case Intrinsic::lifetime_start:
1687     case Intrinsic::lifetime_end:
1688     case Intrinsic::sideeffect:
1689     case Intrinsic::pseudoprobe:
1690     case Intrinsic::arithmetic_fence:
1691       return 0;
1692     case Intrinsic::masked_store: {
1693       Type *Ty = Tys[0];
1694       Align TyAlign = thisT()->DL.getABITypeAlign(Ty);
1695       return thisT()->getMaskedMemoryOpCost(Instruction::Store, Ty, TyAlign, 0,
1696                                             CostKind);
1697     }
1698     case Intrinsic::masked_load: {
1699       Type *Ty = RetTy;
1700       Align TyAlign = thisT()->DL.getABITypeAlign(Ty);
1701       return thisT()->getMaskedMemoryOpCost(Instruction::Load, Ty, TyAlign, 0,
1702                                             CostKind);
1703     }
1704     case Intrinsic::vector_reduce_add:
1705       return thisT()->getArithmeticReductionCost(Instruction::Add, VecOpTy,
1706                                                  None, CostKind);
1707     case Intrinsic::vector_reduce_mul:
1708       return thisT()->getArithmeticReductionCost(Instruction::Mul, VecOpTy,
1709                                                  None, CostKind);
1710     case Intrinsic::vector_reduce_and:
1711       return thisT()->getArithmeticReductionCost(Instruction::And, VecOpTy,
1712                                                  None, CostKind);
1713     case Intrinsic::vector_reduce_or:
1714       return thisT()->getArithmeticReductionCost(Instruction::Or, VecOpTy, None,
1715                                                  CostKind);
1716     case Intrinsic::vector_reduce_xor:
1717       return thisT()->getArithmeticReductionCost(Instruction::Xor, VecOpTy,
1718                                                  None, CostKind);
1719     case Intrinsic::vector_reduce_fadd:
1720       return thisT()->getArithmeticReductionCost(Instruction::FAdd, VecOpTy,
1721                                                  FMF, CostKind);
1722     case Intrinsic::vector_reduce_fmul:
1723       return thisT()->getArithmeticReductionCost(Instruction::FMul, VecOpTy,
1724                                                  FMF, CostKind);
1725     case Intrinsic::vector_reduce_smax:
1726     case Intrinsic::vector_reduce_smin:
1727     case Intrinsic::vector_reduce_fmax:
1728     case Intrinsic::vector_reduce_fmin:
1729       return thisT()->getMinMaxReductionCost(
1730           VecOpTy, cast<VectorType>(CmpInst::makeCmpResultType(VecOpTy)),
1731           /*IsUnsigned=*/false, CostKind);
1732     case Intrinsic::vector_reduce_umax:
1733     case Intrinsic::vector_reduce_umin:
1734       return thisT()->getMinMaxReductionCost(
1735           VecOpTy, cast<VectorType>(CmpInst::makeCmpResultType(VecOpTy)),
1736           /*IsUnsigned=*/true, CostKind);
1737     case Intrinsic::abs: {
1738       // abs(X) = select(icmp(X,0),X,sub(0,X))
1739       Type *CondTy = RetTy->getWithNewBitWidth(1);
1740       CmpInst::Predicate Pred = CmpInst::ICMP_SGT;
1741       InstructionCost Cost = 0;
1742       Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
1743                                           Pred, CostKind);
1744       Cost += thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
1745                                           Pred, CostKind);
1746       // TODO: Should we add an OperandValueProperties::OP_Zero property?
1747       Cost += thisT()->getArithmeticInstrCost(
1748           BinaryOperator::Sub, RetTy, CostKind, TTI::OK_UniformConstantValue);
1749       return Cost;
1750     }
1751     case Intrinsic::smax:
1752     case Intrinsic::smin:
1753     case Intrinsic::umax:
1754     case Intrinsic::umin: {
1755       // minmax(X,Y) = select(icmp(X,Y),X,Y)
1756       Type *CondTy = RetTy->getWithNewBitWidth(1);
1757       bool IsUnsigned = IID == Intrinsic::umax || IID == Intrinsic::umin;
1758       CmpInst::Predicate Pred =
1759           IsUnsigned ? CmpInst::ICMP_UGT : CmpInst::ICMP_SGT;
1760       InstructionCost Cost = 0;
1761       Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
1762                                           Pred, CostKind);
1763       Cost += thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
1764                                           Pred, CostKind);
1765       return Cost;
1766     }
1767     case Intrinsic::sadd_sat:
1768     case Intrinsic::ssub_sat: {
1769       Type *CondTy = RetTy->getWithNewBitWidth(1);
1770
1771       Type *OpTy = StructType::create({RetTy, CondTy});
1772       Intrinsic::ID OverflowOp = IID == Intrinsic::sadd_sat
1773                                      ? Intrinsic::sadd_with_overflow
1774                                      : Intrinsic::ssub_with_overflow;
1775       CmpInst::Predicate Pred = CmpInst::ICMP_SGT;
1776
1777       // SatMax -> Overflow && SumDiff < 0
1778       // SatMin -> Overflow && SumDiff >= 0
1779       InstructionCost Cost = 0;
1780       IntrinsicCostAttributes Attrs(OverflowOp, OpTy, {RetTy, RetTy}, FMF,
1781                                     nullptr, ScalarizationCostPassed);
1782       Cost += thisT()->getIntrinsicInstrCost(Attrs, CostKind);
1783       Cost += thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, RetTy, CondTy,
1784                                           Pred, CostKind);
1785       Cost += 2 * thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy,
1786                                               CondTy, Pred, CostKind);
1787       return Cost;
1788     }
1789     case Intrinsic::uadd_sat:
1790     case Intrinsic::usub_sat: {
1791       Type *CondTy = RetTy->getWithNewBitWidth(1);
1792
1793       Type *OpTy = StructType::create({RetTy, CondTy});
1794       Intrinsic::ID OverflowOp = IID == Intrinsic::uadd_sat
1795                                      ? Intrinsic::uadd_with_overflow
1796                                      : Intrinsic::usub_with_overflow;
1797
1798       InstructionCost Cost = 0;
1799       IntrinsicCostAttributes Attrs(OverflowOp, OpTy, {RetTy, RetTy}, FMF,
1800                                     nullptr, ScalarizationCostPassed);
1801       Cost += thisT()->getIntrinsicInstrCost(Attrs, CostKind);
1802       Cost +=
1803           thisT()->getCmpSelInstrCost(BinaryOperator::Select, RetTy, CondTy,
1804                                       CmpInst::BAD_ICMP_PREDICATE, CostKind);
1805       return Cost;
1806     }
1807     case Intrinsic::smul_fix:
1808     case Intrinsic::umul_fix: {
1809       unsigned ExtSize = RetTy->getScalarSizeInBits() * 2;
1810       Type *ExtTy = RetTy->getWithNewBitWidth(ExtSize);
1811
1812       unsigned ExtOp =
1813           IID == Intrinsic::smul_fix ? Instruction::SExt : Instruction::ZExt;
1814       TTI::CastContextHint CCH = TTI::CastContextHint::None;
1815
1816       InstructionCost Cost = 0;
1817       Cost += 2 * thisT()->getCastInstrCost(ExtOp, ExtTy, RetTy, CCH, CostKind);
1818       Cost +=
1819           thisT()->getArithmeticInstrCost(Instruction::Mul, ExtTy, CostKind);
1820       Cost += 2 * thisT()->getCastInstrCost(Instruction::Trunc, RetTy, ExtTy,
1821                                             CCH, CostKind);
1822       Cost += thisT()->getArithmeticInstrCost(Instruction::LShr, RetTy,
1823                                               CostKind, TTI::OK_AnyValue,
1824                                               TTI::OK_UniformConstantValue);
1825       Cost += thisT()->getArithmeticInstrCost(Instruction::Shl, RetTy, CostKind,
1826                                               TTI::OK_AnyValue,
1827                                               TTI::OK_UniformConstantValue);
1828       Cost += thisT()->getArithmeticInstrCost(Instruction::Or, RetTy, CostKind);
1829       return Cost;
1830     }
1831     case Intrinsic::sadd_with_overflow:
1832     case Intrinsic::ssub_with_overflow: {
1833       Type *SumTy = RetTy->getContainedType(0);
1834       Type *OverflowTy = RetTy->getContainedType(1);
1835       unsigned Opcode = IID == Intrinsic::sadd_with_overflow
1836                             ? BinaryOperator::Add
1837                             : BinaryOperator::Sub;
1838
1839       //   Add:
1840       //   Overflow -> (Result < LHS) ^ (RHS < 0)
1841       //   Sub:
1842       //   Overflow -> (Result < LHS) ^ (RHS > 0)
1843       InstructionCost Cost = 0;
1844       Cost += thisT()->getArithmeticInstrCost(Opcode, SumTy, CostKind);
1845       Cost += 2 * thisT()->getCmpSelInstrCost(
1846                       Instruction::ICmp, SumTy, OverflowTy,
1847                       CmpInst::ICMP_SGT, CostKind);
1848       Cost += thisT()->getArithmeticInstrCost(BinaryOperator::Xor, OverflowTy,
1849                                               CostKind);
1850       return Cost;
1851     }
1852     case Intrinsic::uadd_with_overflow:
1853     case Intrinsic::usub_with_overflow: {
1854       Type *SumTy = RetTy->getContainedType(0);
1855       Type *OverflowTy = RetTy->getContainedType(1);
1856       unsigned Opcode = IID == Intrinsic::uadd_with_overflow
1857                             ? BinaryOperator::Add
1858                             : BinaryOperator::Sub;
1859       CmpInst::Predicate Pred = IID == Intrinsic::uadd_with_overflow
1860                                     ? CmpInst::ICMP_ULT
1861                                     : CmpInst::ICMP_UGT;
1862
1863       InstructionCost Cost = 0;
1864       Cost += thisT()->getArithmeticInstrCost(Opcode, SumTy, CostKind);
1865       Cost +=
1866           thisT()->getCmpSelInstrCost(BinaryOperator::ICmp, SumTy, OverflowTy,
1867                                       Pred, CostKind);
1868       return Cost;
1869     }
1870     case Intrinsic::smul_with_overflow:
1871     case Intrinsic::umul_with_overflow: {
1872       Type *MulTy = RetTy->getContainedType(0);
1873       Type *OverflowTy = RetTy->getContainedType(1);
1874       unsigned ExtSize = MulTy->getScalarSizeInBits() * 2;
1875       Type *ExtTy = MulTy->getWithNewBitWidth(ExtSize);
1876       bool IsSigned = IID == Intrinsic::smul_with_overflow;
1877
1878       unsigned ExtOp = IsSigned ? Instruction::SExt : Instruction::ZExt;
1879       TTI::CastContextHint CCH = TTI::CastContextHint::None;
1880
1881       InstructionCost Cost = 0;
1882       Cost += 2 * thisT()->getCastInstrCost(ExtOp, ExtTy, MulTy, CCH, CostKind);
1883       Cost +=
1884           thisT()->getArithmeticInstrCost(Instruction::Mul, ExtTy, CostKind);
1885       Cost += 2 * thisT()->getCastInstrCost(Instruction::Trunc, MulTy, ExtTy,
1886                                             CCH, CostKind);
1887       Cost += thisT()->getArithmeticInstrCost(Instruction::LShr, ExtTy,
1888                                               CostKind, TTI::OK_AnyValue,
1889                                               TTI::OK_UniformConstantValue);
1890
1891       if (IsSigned)
1892         Cost += thisT()->getArithmeticInstrCost(Instruction::AShr, MulTy,
1893                                                 CostKind, TTI::OK_AnyValue,
1894                                                 TTI::OK_UniformConstantValue);
1895
1896       Cost += thisT()->getCmpSelInstrCost(
1897           BinaryOperator::ICmp, MulTy, OverflowTy, CmpInst::ICMP_NE, CostKind);
1898       return Cost;
1899     }
1900     case Intrinsic::ctpop:
1901       ISDs.push_back(ISD::CTPOP);
1902       // In case of legalization use TCC_Expensive. This is cheaper than a
1903       // library call but still not a cheap instruction.
1904       SingleCallCost = TargetTransformInfo::TCC_Expensive;
1905       break;
1906     case Intrinsic::ctlz:
1907       ISDs.push_back(ISD::CTLZ);
1908       break;
1909     case Intrinsic::cttz:
1910       ISDs.push_back(ISD::CTTZ);
1911       break;
1912     case Intrinsic::bswap:
1913       ISDs.push_back(ISD::BSWAP);
1914       break;
1915     case Intrinsic::bitreverse:
1916       ISDs.push_back(ISD::BITREVERSE);
1917       break;
1918     }
1919
1920     const TargetLoweringBase *TLI = getTLI();
1921     std::pair<InstructionCost, MVT> LT =
1922         TLI->getTypeLegalizationCost(DL, RetTy);
1923
1924     SmallVector<InstructionCost, 2> LegalCost;
1925     SmallVector<InstructionCost, 2> CustomCost;
1926     for (unsigned ISD : ISDs) {
1927       if (TLI->isOperationLegalOrPromote(ISD, LT.second)) {
1928         if (IID == Intrinsic::fabs && LT.second.isFloatingPoint() &&
1929             TLI->isFAbsFree(LT.second)) {
1930           return 0;
1931         }
1932
1933         // The operation is legal. Assume it costs 1.
1934         // If the type is split to multiple registers, assume that there is some
1935         // overhead to this.
1936         // TODO: Once we have extract/insert subvector cost we need to use them.
1937         if (LT.first > 1)
1938           LegalCost.push_back(LT.first * 2);
1939         else
1940           LegalCost.push_back(LT.first * 1);
1941       } else if (!TLI->isOperationExpand(ISD, LT.second)) {
1942         // If the operation is custom lowered then assume
1943         // that the code is twice as expensive.
1944         CustomCost.push_back(LT.first * 2);
1945       }
1946     }
1947
1948     auto *MinLegalCostI = std::min_element(LegalCost.begin(), LegalCost.end());
1949     if (MinLegalCostI != LegalCost.end())
1950       return *MinLegalCostI;
1951
1952     auto MinCustomCostI =
1953         std::min_element(CustomCost.begin(), CustomCost.end());
1954     if (MinCustomCostI != CustomCost.end())
1955       return *MinCustomCostI;
1956
1957     // If we can't lower fmuladd into an FMA estimate the cost as a floating
1958     // point mul followed by an add.
1959     if (IID == Intrinsic::fmuladd)
1960       return thisT()->getArithmeticInstrCost(BinaryOperator::FMul, RetTy,
1961                                              CostKind) +
1962              thisT()->getArithmeticInstrCost(BinaryOperator::FAdd, RetTy,
1963                                              CostKind);
1964     if (IID == Intrinsic::experimental_constrained_fmuladd) {
1965       IntrinsicCostAttributes FMulAttrs(
1966         Intrinsic::experimental_constrained_fmul, RetTy, Tys);
1967       IntrinsicCostAttributes FAddAttrs(
1968         Intrinsic::experimental_constrained_fadd, RetTy, Tys);
1969       return thisT()->getIntrinsicInstrCost(FMulAttrs, CostKind) +
1970              thisT()->getIntrinsicInstrCost(FAddAttrs, CostKind);
1971     }
1972
1973     // Else, assume that we need to scalarize this intrinsic. For math builtins
1974     // this will emit a costly libcall, adding call overhead and spills. Make it
1975     // very expensive.
1976     if (auto *RetVTy = dyn_cast<VectorType>(RetTy)) {
1977       // Scalable vectors cannot be scalarized, so return Invalid.
1978       if (isa<ScalableVectorType>(RetTy) || any_of(Tys, [](const Type *Ty) {
1979             return isa<ScalableVectorType>(Ty);
1980           }))
1981         return InstructionCost::getInvalid();
1982
1983       InstructionCost ScalarizationCost =
1984           SkipScalarizationCost ? ScalarizationCostPassed
1985                                 : getScalarizationOverhead(RetVTy, true, false);
1986
1987       unsigned ScalarCalls = cast<FixedVectorType>(RetVTy)->getNumElements();
1988       SmallVector<Type *, 4> ScalarTys;
1989       for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
1990         Type *Ty = Tys[i];
1991         if (Ty->isVectorTy())
1992           Ty = Ty->getScalarType();
1993         ScalarTys.push_back(Ty);
1994       }
1995       IntrinsicCostAttributes Attrs(IID, RetTy->getScalarType(), ScalarTys, FMF);
1996       InstructionCost ScalarCost =
1997           thisT()->getIntrinsicInstrCost(Attrs, CostKind);
1998       for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
1999         if (auto *VTy = dyn_cast<VectorType>(Tys[i])) {
2000           if (!ICA.skipScalarizationCost())
2001             ScalarizationCost += getScalarizationOverhead(VTy, false, true);
2002           ScalarCalls = std::max(ScalarCalls,
2003                                  cast<FixedVectorType>(VTy)->getNumElements());
2004         }
2005       }
2006       return ScalarCalls * ScalarCost + ScalarizationCost;
2007     }
2008
2009     // This is going to be turned into a library call, make it expensive.
2010     return SingleCallCost;
2011   }
2012
2013   /// Compute a cost of the given call instruction.
2014   ///
2015   /// Compute the cost of calling function F with return type RetTy and
2016   /// argument types Tys. F might be nullptr, in this case the cost of an
2017   /// arbitrary call with the specified signature will be returned.
2018   /// This is used, for instance,  when we estimate call of a vector
2019   /// counterpart of the given function.
2020   /// \param F Called function, might be nullptr.
2021   /// \param RetTy Return value types.
2022   /// \param Tys Argument types.
2023   /// \returns The cost of Call instruction.
2024   InstructionCost getCallInstrCost(Function *F, Type *RetTy,
2025                                    ArrayRef<Type *> Tys,
2026                                    TTI::TargetCostKind CostKind) {
2027     return 10;
2028   }
2029
2030   unsigned getNumberOfParts(Type *Tp) {
2031     std::pair<InstructionCost, MVT> LT =
2032         getTLI()->getTypeLegalizationCost(DL, Tp);
2033     return LT.first.isValid() ? *LT.first.getValue() : 0;
2034   }
2035
2036   InstructionCost getAddressComputationCost(Type *Ty, ScalarEvolution *,
2037                                             const SCEV *) {
2038     return 0;
2039   }
2040
2041   /// Try to calculate arithmetic and shuffle op costs for reduction intrinsics.
2042   /// We're assuming that reduction operation are performing the following way:
2043   ///
2044   /// %val1 = shufflevector<n x t> %val, <n x t> %undef,
2045   /// <n x i32> <i32 n/2, i32 n/2 + 1, ..., i32 n, i32 undef, ..., i32 undef>
2046   ///            \----------------v-------------/  \----------v------------/
2047   ///                            n/2 elements               n/2 elements
2048   /// %red1 = op <n x t> %val, <n x t> val1
2049   /// After this operation we have a vector %red1 where only the first n/2
2050   /// elements are meaningful, the second n/2 elements are undefined and can be
2051   /// dropped. All other operations are actually working with the vector of
2052   /// length n/2, not n, though the real vector length is still n.
2053   /// %val2 = shufflevector<n x t> %red1, <n x t> %undef,
2054   /// <n x i32> <i32 n/4, i32 n/4 + 1, ..., i32 n/2, i32 undef, ..., i32 undef>
2055   ///            \----------------v-------------/  \----------v------------/
2056   ///                            n/4 elements               3*n/4 elements
2057   /// %red2 = op <n x t> %red1, <n x t> val2  - working with the vector of
2058   /// length n/2, the resulting vector has length n/4 etc.
2059   ///
2060   /// The cost model should take into account that the actual length of the
2061   /// vector is reduced on each iteration.
2062   InstructionCost getTreeReductionCost(unsigned Opcode, VectorType *Ty,
2063                                        TTI::TargetCostKind CostKind) {
2064     Type *ScalarTy = Ty->getElementType();
2065     unsigned NumVecElts = cast<FixedVectorType>(Ty)->getNumElements();
2066     if ((Opcode == Instruction::Or || Opcode == Instruction::And) &&
2067         ScalarTy == IntegerType::getInt1Ty(Ty->getContext()) &&
2068         NumVecElts >= 2) {
2069       // Or reduction for i1 is represented as:
2070       // %val = bitcast <ReduxWidth x i1> to iReduxWidth
2071       // %res = cmp ne iReduxWidth %val, 0
2072       // And reduction for i1 is represented as:
2073       // %val = bitcast <ReduxWidth x i1> to iReduxWidth
2074       // %res = cmp eq iReduxWidth %val, 11111
2075       Type *ValTy = IntegerType::get(Ty->getContext(), NumVecElts);
2076       return thisT()->getCastInstrCost(Instruction::BitCast, ValTy, Ty,
2077                                        TTI::CastContextHint::None, CostKind) +
2078              thisT()->getCmpSelInstrCost(Instruction::ICmp, ValTy,
2079                                          CmpInst::makeCmpResultType(ValTy),
2080                                          CmpInst::BAD_ICMP_PREDICATE, CostKind);
2081     }
2082     unsigned NumReduxLevels = Log2_32(NumVecElts);
2083     InstructionCost ArithCost = 0;
2084     InstructionCost ShuffleCost = 0;
2085     std::pair<InstructionCost, MVT> LT =
2086         thisT()->getTLI()->getTypeLegalizationCost(DL, Ty);
2087     unsigned LongVectorCount = 0;
2088     unsigned MVTLen =
2089         LT.second.isVector() ? LT.second.getVectorNumElements() : 1;
2090     while (NumVecElts > MVTLen) {
2091       NumVecElts /= 2;
2092       VectorType *SubTy = FixedVectorType::get(ScalarTy, NumVecElts);
2093       ShuffleCost += thisT()->getShuffleCost(TTI::SK_ExtractSubvector, Ty, None,
2094                                              NumVecElts, SubTy);
2095       ArithCost += thisT()->getArithmeticInstrCost(Opcode, SubTy, CostKind);
2096       Ty = SubTy;
2097       ++LongVectorCount;
2098     }
2099
2100     NumReduxLevels -= LongVectorCount;
2101
2102     // The minimal length of the vector is limited by the real length of vector
2103     // operations performed on the current platform. That's why several final
2104     // reduction operations are performed on the vectors with the same
2105     // architecture-dependent length.
2106
2107     // By default reductions need one shuffle per reduction level.
2108     ShuffleCost += NumReduxLevels * thisT()->getShuffleCost(
2109                                      TTI::SK_PermuteSingleSrc, Ty, None, 0, Ty);
2110     ArithCost +=
2111         NumReduxLevels * thisT()->getArithmeticInstrCost(Opcode, Ty, CostKind);
2112     return ShuffleCost + ArithCost +
2113            thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty, 0);
2114   }
2115
2116   /// Try to calculate the cost of performing strict (in-order) reductions,
2117   /// which involves doing a sequence of floating point additions in lane
2118   /// order, starting with an initial value. For example, consider a scalar
2119   /// initial value 'InitVal' of type float and a vector of type <4 x float>:
2120   ///
2121   ///   Vector = <float %v0, float %v1, float %v2, float %v3>
2122   ///
2123   ///   %add1 = %InitVal + %v0
2124   ///   %add2 = %add1 + %v1
2125   ///   %add3 = %add2 + %v2
2126   ///   %add4 = %add3 + %v3
2127   ///
2128   /// As a simple estimate we can say the cost of such a reduction is 4 times
2129   /// the cost of a scalar FP addition. We can only estimate the costs for
2130   /// fixed-width vectors here because for scalable vectors we do not know the
2131   /// runtime number of operations.
2132   InstructionCost getOrderedReductionCost(unsigned Opcode, VectorType *Ty,
2133                                           TTI::TargetCostKind CostKind) {
2134     // Targets must implement a default value for the scalable case, since
2135     // we don't know how many lanes the vector has.
2136     if (isa<ScalableVectorType>(Ty))
2137       return InstructionCost::getInvalid();
2138
2139     auto *VTy = cast<FixedVectorType>(Ty);
2140     InstructionCost ExtractCost =
2141         getScalarizationOverhead(VTy, /*Insert=*/false, /*Extract=*/true);
2142     InstructionCost ArithCost = thisT()->getArithmeticInstrCost(
2143         Opcode, VTy->getElementType(), CostKind);
2144     ArithCost *= VTy->getNumElements();
2145
2146     return ExtractCost + ArithCost;
2147   }
2148
2149   InstructionCost getArithmeticReductionCost(unsigned Opcode, VectorType *Ty,
2150                                              Optional<FastMathFlags> FMF,
2151                                              TTI::TargetCostKind CostKind) {
2152     if (TTI::requiresOrderedReduction(FMF))
2153       return getOrderedReductionCost(Opcode, Ty, CostKind);
2154     return getTreeReductionCost(Opcode, Ty, CostKind);
2155   }
2156
2157   /// Try to calculate op costs for min/max reduction operations.
2158   /// \param CondTy Conditional type for the Select instruction.
2159   InstructionCost getMinMaxReductionCost(VectorType *Ty, VectorType *CondTy,
2160                                          bool IsUnsigned,
2161                                          TTI::TargetCostKind CostKind) {
2162     Type *ScalarTy = Ty->getElementType();
2163     Type *ScalarCondTy = CondTy->getElementType();
2164     unsigned NumVecElts = cast<FixedVectorType>(Ty)->getNumElements();
2165     unsigned NumReduxLevels = Log2_32(NumVecElts);
2166     unsigned CmpOpcode;
2167     if (Ty->isFPOrFPVectorTy()) {
2168       CmpOpcode = Instruction::FCmp;
2169     } else {
2170       assert(Ty->isIntOrIntVectorTy() &&
2171              "expecting floating point or integer type for min/max reduction");
2172       CmpOpcode = Instruction::ICmp;
2173     }
2174     InstructionCost MinMaxCost = 0;
2175     InstructionCost ShuffleCost = 0;
2176     std::pair<InstructionCost, MVT> LT =
2177         thisT()->getTLI()->getTypeLegalizationCost(DL, Ty);
2178     unsigned LongVectorCount = 0;
2179     unsigned MVTLen =
2180         LT.second.isVector() ? LT.second.getVectorNumElements() : 1;
2181     while (NumVecElts > MVTLen) {
2182       NumVecElts /= 2;
2183       auto *SubTy = FixedVectorType::get(ScalarTy, NumVecElts);
2184       CondTy = FixedVectorType::get(ScalarCondTy, NumVecElts);
2185
2186       ShuffleCost += thisT()->getShuffleCost(TTI::SK_ExtractSubvector, Ty, None,
2187                                              NumVecElts, SubTy);
2188       MinMaxCost +=
2189           thisT()->getCmpSelInstrCost(CmpOpcode, SubTy, CondTy,
2190                                       CmpInst::BAD_ICMP_PREDICATE, CostKind) +
2191           thisT()->getCmpSelInstrCost(Instruction::Select, SubTy, CondTy,
2192                                       CmpInst::BAD_ICMP_PREDICATE, CostKind);
2193       Ty = SubTy;
2194       ++LongVectorCount;
2195     }
2196
2197     NumReduxLevels -= LongVectorCount;
2198
2199     // The minimal length of the vector is limited by the real length of vector
2200     // operations performed on the current platform. That's why several final
2201     // reduction opertions are perfomed on the vectors with the same
2202     // architecture-dependent length.
2203     ShuffleCost += NumReduxLevels * thisT()->getShuffleCost(
2204                                      TTI::SK_PermuteSingleSrc, Ty, None, 0, Ty);
2205     MinMaxCost +=
2206         NumReduxLevels *
2207         (thisT()->getCmpSelInstrCost(CmpOpcode, Ty, CondTy,
2208                                      CmpInst::BAD_ICMP_PREDICATE, CostKind) +
2209          thisT()->getCmpSelInstrCost(Instruction::Select, Ty, CondTy,
2210                                      CmpInst::BAD_ICMP_PREDICATE, CostKind));
2211     // The last min/max should be in vector registers and we counted it above.
2212     // So just need a single extractelement.
2213     return ShuffleCost + MinMaxCost +
2214            thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty, 0);
2215   }
2216
2217   InstructionCost getExtendedAddReductionCost(bool IsMLA, bool IsUnsigned,
2218                                               Type *ResTy, VectorType *Ty,
2219                                               TTI::TargetCostKind CostKind) {
2220     // Without any native support, this is equivalent to the cost of
2221     // vecreduce.add(ext) or if IsMLA vecreduce.add(mul(ext, ext))
2222     VectorType *ExtTy = VectorType::get(ResTy, Ty);
2223     InstructionCost RedCost = thisT()->getArithmeticReductionCost(
2224         Instruction::Add, ExtTy, None, CostKind);
2225     InstructionCost MulCost = 0;
2226     InstructionCost ExtCost = thisT()->getCastInstrCost(
2227         IsUnsigned ? Instruction::ZExt : Instruction::SExt, ExtTy, Ty,
2228         TTI::CastContextHint::None, CostKind);
2229     if (IsMLA) {
2230       MulCost =
2231           thisT()->getArithmeticInstrCost(Instruction::Mul, ExtTy, CostKind);
2232       ExtCost *= 2;
2233     }
2234
2235     return RedCost + MulCost + ExtCost;
2236   }
2237
2238   InstructionCost getVectorSplitCost() { return 1; }
2239
2240   /// @}
2241 };
2242
2243 /// Concrete BasicTTIImpl that can be used if no further customization
2244 /// is needed.
2245 class BasicTTIImpl : public BasicTTIImplBase<BasicTTIImpl> {
2246   using BaseT = BasicTTIImplBase<BasicTTIImpl>;
2247
2248   friend class BasicTTIImplBase<BasicTTIImpl>;
2249
2250   const TargetSubtargetInfo *ST;
2251   const TargetLoweringBase *TLI;
2252
2253   const TargetSubtargetInfo *getST() const { return ST; }
2254   const TargetLoweringBase *getTLI() const { return TLI; }
2255
2256 public:
2257   explicit BasicTTIImpl(const TargetMachine *TM, const Function &F);
2258 };
2259
2260 } // end namespace llvm
2261
2262 #endif // LLVM_CODEGEN_BASICTTIIMPL_H