lib/CodeGen/BasicTargetTransformInfo.cpp

   1 //===- BasicTargetTransformInfo.cpp - Basic target-independent TTI impl ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 /// This file provides the implementation of a basic TargetTransformInfo pass
  11 /// predicated on the target abstractions present in the target independent
  12 /// code generator. It uses these (primarily TargetLowering) to model as much
  13 /// of the TTI query interface as possible. It is included by most targets so
  14 /// that they can specialize only a small subset of the query space.
  15 ///
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "basictti"
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/Analysis/TargetTransformInfo.h"
  21 #include "llvm/Target/TargetLowering.h"
  22 #include <utility>
  23 using namespace llvm;
  24
  25 namespace {
  26
  27 class BasicTTI final : public ImmutablePass, public TargetTransformInfo {
  28   const TargetMachine *TM;
  29
  30   /// Estimate the overhead of scalarizing an instruction. Insert and Extract
  31   /// are set if the result needs to be inserted and/or extracted from vectors.
  32   unsigned getScalarizationOverhead(Type *Ty, bool Insert, bool Extract) const;
  33
  34   const TargetLoweringBase *getTLI() const { return TM->getTargetLowering(); }
  35
  36 public:
  37   BasicTTI() : ImmutablePass(ID), TM(0) {
  38     llvm_unreachable("This pass cannot be directly constructed");
  39   }
  40
  41   BasicTTI(const TargetMachine *TM) : ImmutablePass(ID), TM(TM) {
  42     initializeBasicTTIPass(*PassRegistry::getPassRegistry());
  43   }
  44
  45   void initializePass() override {
  46     pushTTIStack(this);
  47   }
  48
  49   void getAnalysisUsage(AnalysisUsage &AU) const override {
  50     TargetTransformInfo::getAnalysisUsage(AU);
  51   }
  52
  53   /// Pass identification.
  54   static char ID;
  55
  56   /// Provide necessary pointer adjustments for the two base classes.
  57   void *getAdjustedAnalysisPointer(const void *ID) override {
  58     if (ID == &TargetTransformInfo::ID)
  59       return (TargetTransformInfo*)this;
  60     return this;
  61   }
  62
  63   bool hasBranchDivergence() const override;
  64
  65   /// \name Scalar TTI Implementations
  66   /// @{
  67
  68   bool isLegalAddImmediate(int64_t imm) const override;
  69   bool isLegalICmpImmediate(int64_t imm) const override;
  70   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
  71                              int64_t BaseOffset, bool HasBaseReg,
  72                              int64_t Scale) const override;
  73   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
  74                            int64_t BaseOffset, bool HasBaseReg,
  75                            int64_t Scale) const override;
  76   bool isTruncateFree(Type *Ty1, Type *Ty2) const override;
  77   bool isTypeLegal(Type *Ty) const override;
  78   unsigned getJumpBufAlignment() const override;
  79   unsigned getJumpBufSize() const override;
  80   bool shouldBuildLookupTables() const override;
  81   bool haveFastSqrt(Type *Ty) const override;
  82   void getUnrollingPreferences(Loop *L,
  83                                UnrollingPreferences &UP) const override;
  84
  85   /// @}
  86
  87   /// \name Vector TTI Implementations
  88   /// @{
  89
  90   unsigned getNumberOfRegisters(bool Vector) const override;
  91   unsigned getMaximumUnrollFactor() const override;
  92   unsigned getRegisterBitWidth(bool Vector) const override;
  93   unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind,
  94                                   OperandValueKind) const override;
  95   unsigned getShuffleCost(ShuffleKind Kind, Type *Tp,
  96                           int Index, Type *SubTp) const override;
  97   unsigned getCastInstrCost(unsigned Opcode, Type *Dst,
  98                             Type *Src) const override;
  99   unsigned getCFInstrCost(unsigned Opcode) const override;
 100   unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy,
 101                               Type *CondTy) const override;
 102   unsigned getVectorInstrCost(unsigned Opcode, Type *Val,
 103                               unsigned Index) const override;
 104   unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
 105                            unsigned AddressSpace) const override;
 106   unsigned getIntrinsicInstrCost(Intrinsic::ID, Type *RetTy,
 107                                  ArrayRef<Type*> Tys) const override;
 108   unsigned getNumberOfParts(Type *Tp) const override;
 109   unsigned getAddressComputationCost( Type *Ty, bool IsComplex) const override;
 110   unsigned getReductionCost(unsigned Opcode, Type *Ty,
 111                             bool IsPairwise) const override;
 112
 113   /// @}
 114 };
 115
 116 }
 117
 118 INITIALIZE_AG_PASS(BasicTTI, TargetTransformInfo, "basictti",
 119                    "Target independent code generator's TTI", true, true, false)
 120 char BasicTTI::ID = 0;
 121
 122 ImmutablePass *
 123 llvm::createBasicTargetTransformInfoPass(const TargetMachine *TM) {
 124   return new BasicTTI(TM);
 125 }
 126
 127 bool BasicTTI::hasBranchDivergence() const { return false; }
 128
 129 bool BasicTTI::isLegalAddImmediate(int64_t imm) const {
 130   return getTLI()->isLegalAddImmediate(imm);
 131 }
 132
 133 bool BasicTTI::isLegalICmpImmediate(int64_t imm) const {
 134   return getTLI()->isLegalICmpImmediate(imm);
 135 }
 136
 137 bool BasicTTI::isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
 138                                      int64_t BaseOffset, bool HasBaseReg,
 139                                      int64_t Scale) const {
 140   TargetLoweringBase::AddrMode AM;
 141   AM.BaseGV = BaseGV;
 142   AM.BaseOffs = BaseOffset;
 143   AM.HasBaseReg = HasBaseReg;
 144   AM.Scale = Scale;
 145   return getTLI()->isLegalAddressingMode(AM, Ty);
 146 }
 147
 148 int BasicTTI::getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
 149                                    int64_t BaseOffset, bool HasBaseReg,
 150                                    int64_t Scale) const {
 151   TargetLoweringBase::AddrMode AM;
 152   AM.BaseGV = BaseGV;
 153   AM.BaseOffs = BaseOffset;
 154   AM.HasBaseReg = HasBaseReg;
 155   AM.Scale = Scale;
 156   return getTLI()->getScalingFactorCost(AM, Ty);
 157 }
 158
 159 bool BasicTTI::isTruncateFree(Type *Ty1, Type *Ty2) const {
 160   return getTLI()->isTruncateFree(Ty1, Ty2);
 161 }
 162
 163 bool BasicTTI::isTypeLegal(Type *Ty) const {
 164   EVT T = getTLI()->getValueType(Ty);
 165   return getTLI()->isTypeLegal(T);
 166 }
 167
 168 unsigned BasicTTI::getJumpBufAlignment() const {
 169   return getTLI()->getJumpBufAlignment();
 170 }
 171
 172 unsigned BasicTTI::getJumpBufSize() const {
 173   return getTLI()->getJumpBufSize();
 174 }
 175
 176 bool BasicTTI::shouldBuildLookupTables() const {
 177   const TargetLoweringBase *TLI = getTLI();
 178   return TLI->supportJumpTables() &&
 179       (TLI->isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
 180        TLI->isOperationLegalOrCustom(ISD::BRIND, MVT::Other));
 181 }
 182
 183 bool BasicTTI::haveFastSqrt(Type *Ty) const {
 184   const TargetLoweringBase *TLI = getTLI();
 185   EVT VT = TLI->getValueType(Ty);
 186   return TLI->isTypeLegal(VT) && TLI->isOperationLegalOrCustom(ISD::FSQRT, VT);
 187 }
 188
 189 void BasicTTI::getUnrollingPreferences(Loop *, UnrollingPreferences &) const { }
 190
 191 //===----------------------------------------------------------------------===//
 192 //
 193 // Calls used by the vectorizers.
 194 //
 195 //===----------------------------------------------------------------------===//
 196
 197 unsigned BasicTTI::getScalarizationOverhead(Type *Ty, bool Insert,
 198                                             bool Extract) const {
 199   assert (Ty->isVectorTy() && "Can only scalarize vectors");
 200   unsigned Cost = 0;
 201
 202   for (int i = 0, e = Ty->getVectorNumElements(); i < e; ++i) {
 203     if (Insert)
 204       Cost += TopTTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
 205     if (Extract)
 206       Cost += TopTTI->getVectorInstrCost(Instruction::ExtractElement, Ty, i);
 207   }
 208
 209   return Cost;
 210 }
 211
 212 unsigned BasicTTI::getNumberOfRegisters(bool Vector) const {
 213   return 1;
 214 }
 215
 216 unsigned BasicTTI::getRegisterBitWidth(bool Vector) const {
 217   return 32;
 218 }
 219
 220 unsigned BasicTTI::getMaximumUnrollFactor() const {
 221   return 1;
 222 }
 223
 224 unsigned BasicTTI::getArithmeticInstrCost(unsigned Opcode, Type *Ty,
 225                                           OperandValueKind,
 226                                           OperandValueKind) const {
 227   // Check if any of the operands are vector operands.
 228   const TargetLoweringBase *TLI = getTLI();
 229   int ISD = TLI->InstructionOpcodeToISD(Opcode);
 230   assert(ISD && "Invalid opcode");
 231
 232   std::pair<unsigned, MVT> LT = TLI->getTypeLegalizationCost(Ty);
 233
 234   bool IsFloat = Ty->getScalarType()->isFloatingPointTy();
 235   // Assume that floating point arithmetic operations cost twice as much as
 236   // integer operations.
 237   unsigned OpCost = (IsFloat ? 2 : 1);
 238
 239   if (TLI->isOperationLegalOrPromote(ISD, LT.second)) {
 240     // The operation is legal. Assume it costs 1.
 241     // If the type is split to multiple registers, assume that there is some
 242     // overhead to this.
 243     // TODO: Once we have extract/insert subvector cost we need to use them.
 244     if (LT.first > 1)
 245       return LT.first * 2 * OpCost;
 246     return LT.first * 1 * OpCost;
 247   }
 248
 249   if (!TLI->isOperationExpand(ISD, LT.second)) {
 250     // If the operation is custom lowered then assume
 251     // thare the code is twice as expensive.
 252     return LT.first * 2 * OpCost;
 253   }
 254
 255   // Else, assume that we need to scalarize this op.
 256   if (Ty->isVectorTy()) {
 257     unsigned Num = Ty->getVectorNumElements();
 258     unsigned Cost = TopTTI->getArithmeticInstrCost(Opcode, Ty->getScalarType());
 259     // return the cost of multiple scalar invocation plus the cost of inserting
 260     // and extracting the values.
 261     return getScalarizationOverhead(Ty, true, true) + Num * Cost;
 262   }
 263
 264   // We don't know anything about this scalar instruction.
 265   return OpCost;
 266 }
 267
 268 unsigned BasicTTI::getShuffleCost(ShuffleKind Kind, Type *Tp, int Index,
 269                                   Type *SubTp) const {
 270   return 1;
 271 }
 272
 273 unsigned BasicTTI::getCastInstrCost(unsigned Opcode, Type *Dst,
 274                                     Type *Src) const {
 275   const TargetLoweringBase *TLI = getTLI();
 276   int ISD = TLI->InstructionOpcodeToISD(Opcode);
 277   assert(ISD && "Invalid opcode");
 278
 279   std::pair<unsigned, MVT> SrcLT = TLI->getTypeLegalizationCost(Src);
 280   std::pair<unsigned, MVT> DstLT = TLI->getTypeLegalizationCost(Dst);
 281
 282   // Check for NOOP conversions.
 283   if (SrcLT.first == DstLT.first &&
 284       SrcLT.second.getSizeInBits() == DstLT.second.getSizeInBits()) {
 285
 286       // Bitcast between types that are legalized to the same type are free.
 287       if (Opcode == Instruction::BitCast || Opcode == Instruction::Trunc)
 288         return 0;
 289   }
 290
 291   if (Opcode == Instruction::Trunc &&
 292       TLI->isTruncateFree(SrcLT.second, DstLT.second))
 293     return 0;
 294
 295   if (Opcode == Instruction::ZExt &&
 296       TLI->isZExtFree(SrcLT.second, DstLT.second))
 297     return 0;
 298
 299   // If the cast is marked as legal (or promote) then assume low cost.
 300   if (TLI->isOperationLegalOrPromote(ISD, DstLT.second))
 301     return 1;
 302
 303   // Handle scalar conversions.
 304   if (!Src->isVectorTy() && !Dst->isVectorTy()) {
 305
 306     // Scalar bitcasts are usually free.
 307     if (Opcode == Instruction::BitCast)
 308       return 0;
 309
 310     // Just check the op cost. If the operation is legal then assume it costs 1.
 311     if (!TLI->isOperationExpand(ISD, DstLT.second))
 312       return  1;
 313
 314     // Assume that illegal scalar instruction are expensive.
 315     return 4;
 316   }
 317
 318   // Check vector-to-vector casts.
 319   if (Dst->isVectorTy() && Src->isVectorTy()) {
 320
 321     // If the cast is between same-sized registers, then the check is simple.
 322     if (SrcLT.first == DstLT.first &&
 323         SrcLT.second.getSizeInBits() == DstLT.second.getSizeInBits()) {
 324
 325       // Assume that Zext is done using AND.
 326       if (Opcode == Instruction::ZExt)
 327         return 1;
 328
 329       // Assume that sext is done using SHL and SRA.
 330       if (Opcode == Instruction::SExt)
 331         return 2;
 332
 333       // Just check the op cost. If the operation is legal then assume it costs
 334       // 1 and multiply by the type-legalization overhead.
 335       if (!TLI->isOperationExpand(ISD, DstLT.second))
 336         return SrcLT.first * 1;
 337     }
 338
 339     // If we are converting vectors and the operation is illegal, or
 340     // if the vectors are legalized to different types, estimate the
 341     // scalarization costs.
 342     unsigned Num = Dst->getVectorNumElements();
 343     unsigned Cost = TopTTI->getCastInstrCost(Opcode, Dst->getScalarType(),
 344                                              Src->getScalarType());
 345
 346     // Return the cost of multiple scalar invocation plus the cost of
 347     // inserting and extracting the values.
 348     return getScalarizationOverhead(Dst, true, true) + Num * Cost;
 349   }
 350
 351   // We already handled vector-to-vector and scalar-to-scalar conversions. This
 352   // is where we handle bitcast between vectors and scalars. We need to assume
 353   //  that the conversion is scalarized in one way or another.
 354   if (Opcode == Instruction::BitCast)
 355     // Illegal bitcasts are done by storing and loading from a stack slot.
 356     return (Src->isVectorTy()? getScalarizationOverhead(Src, false, true):0) +
 357            (Dst->isVectorTy()? getScalarizationOverhead(Dst, true, false):0);
 358
 359   llvm_unreachable("Unhandled cast");
 360  }
 361
 362 unsigned BasicTTI::getCFInstrCost(unsigned Opcode) const {
 363   // Branches are assumed to be predicted.
 364   return 0;
 365 }
 366
 367 unsigned BasicTTI::getCmpSelInstrCost(unsigned Opcode, Type *ValTy,
 368                                       Type *CondTy) const {
 369   const TargetLoweringBase *TLI = getTLI();
 370   int ISD = TLI->InstructionOpcodeToISD(Opcode);
 371   assert(ISD && "Invalid opcode");
 372
 373   // Selects on vectors are actually vector selects.
 374   if (ISD == ISD::SELECT) {
 375     assert(CondTy && "CondTy must exist");
 376     if (CondTy->isVectorTy())
 377       ISD = ISD::VSELECT;
 378   }
 379
 380   std::pair<unsigned, MVT> LT = TLI->getTypeLegalizationCost(ValTy);
 381
 382   if (!TLI->isOperationExpand(ISD, LT.second)) {
 383     // The operation is legal. Assume it costs 1. Multiply
 384     // by the type-legalization overhead.
 385     return LT.first * 1;
 386   }
 387
 388   // Otherwise, assume that the cast is scalarized.
 389   if (ValTy->isVectorTy()) {
 390     unsigned Num = ValTy->getVectorNumElements();
 391     if (CondTy)
 392       CondTy = CondTy->getScalarType();
 393     unsigned Cost = TopTTI->getCmpSelInstrCost(Opcode, ValTy->getScalarType(),
 394                                                CondTy);
 395
 396     // Return the cost of multiple scalar invocation plus the cost of inserting
 397     // and extracting the values.
 398     return getScalarizationOverhead(ValTy, true, false) + Num * Cost;
 399   }
 400
 401   // Unknown scalar opcode.
 402   return 1;
 403 }
 404
 405 unsigned BasicTTI::getVectorInstrCost(unsigned Opcode, Type *Val,
 406                                       unsigned Index) const {
 407   std::pair<unsigned, MVT> LT =  getTLI()->getTypeLegalizationCost(Val->getScalarType());
 408
 409   return LT.first;
 410 }
 411
 412 unsigned BasicTTI::getMemoryOpCost(unsigned Opcode, Type *Src,
 413                                    unsigned Alignment,
 414                                    unsigned AddressSpace) const {
 415   assert(!Src->isVoidTy() && "Invalid type");
 416   std::pair<unsigned, MVT> LT = getTLI()->getTypeLegalizationCost(Src);
 417
 418   // Assume that all loads of legal types cost 1.
 419   return LT.first;
 420 }
 421
 422 unsigned BasicTTI::getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
 423                                          ArrayRef<Type *> Tys) const {
 424   unsigned ISD = 0;
 425   switch (IID) {
 426   default: {
 427     // Assume that we need to scalarize this intrinsic.
 428     unsigned ScalarizationCost = 0;
 429     unsigned ScalarCalls = 1;
 430     if (RetTy->isVectorTy()) {
 431       ScalarizationCost = getScalarizationOverhead(RetTy, true, false);
 432       ScalarCalls = std::max(ScalarCalls, RetTy->getVectorNumElements());
 433     }
 434     for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
 435       if (Tys[i]->isVectorTy()) {
 436         ScalarizationCost += getScalarizationOverhead(Tys[i], false, true);
 437         ScalarCalls = std::max(ScalarCalls, RetTy->getVectorNumElements());
 438       }
 439     }
 440
 441     return ScalarCalls + ScalarizationCost;
 442   }
 443   // Look for intrinsics that can be lowered directly or turned into a scalar
 444   // intrinsic call.
 445   case Intrinsic::sqrt:    ISD = ISD::FSQRT;  break;
 446   case Intrinsic::sin:     ISD = ISD::FSIN;   break;
 447   case Intrinsic::cos:     ISD = ISD::FCOS;   break;
 448   case Intrinsic::exp:     ISD = ISD::FEXP;   break;
 449   case Intrinsic::exp2:    ISD = ISD::FEXP2;  break;
 450   case Intrinsic::log:     ISD = ISD::FLOG;   break;
 451   case Intrinsic::log10:   ISD = ISD::FLOG10; break;
 452   case Intrinsic::log2:    ISD = ISD::FLOG2;  break;
 453   case Intrinsic::fabs:    ISD = ISD::FABS;   break;
 454   case Intrinsic::copysign: ISD = ISD::FCOPYSIGN; break;
 455   case Intrinsic::floor:   ISD = ISD::FFLOOR; break;
 456   case Intrinsic::ceil:    ISD = ISD::FCEIL;  break;
 457   case Intrinsic::trunc:   ISD = ISD::FTRUNC; break;
 458   case Intrinsic::nearbyint:
 459                            ISD = ISD::FNEARBYINT; break;
 460   case Intrinsic::rint:    ISD = ISD::FRINT;  break;
 461   case Intrinsic::round:   ISD = ISD::FROUND; break;
 462   case Intrinsic::pow:     ISD = ISD::FPOW;   break;
 463   case Intrinsic::fma:     ISD = ISD::FMA;    break;
 464   case Intrinsic::fmuladd: ISD = ISD::FMA;    break; // FIXME: mul + add?
 465   case Intrinsic::lifetime_start:
 466   case Intrinsic::lifetime_end:
 467     return 0;
 468   }
 469
 470   const TargetLoweringBase *TLI = getTLI();
 471   std::pair<unsigned, MVT> LT = TLI->getTypeLegalizationCost(RetTy);
 472
 473   if (TLI->isOperationLegalOrPromote(ISD, LT.second)) {
 474     // The operation is legal. Assume it costs 1.
 475     // If the type is split to multiple registers, assume that thre is some
 476     // overhead to this.
 477     // TODO: Once we have extract/insert subvector cost we need to use them.
 478     if (LT.first > 1)
 479       return LT.first * 2;
 480     return LT.first * 1;
 481   }
 482
 483   if (!TLI->isOperationExpand(ISD, LT.second)) {
 484     // If the operation is custom lowered then assume
 485     // thare the code is twice as expensive.
 486     return LT.first * 2;
 487   }
 488
 489   // Else, assume that we need to scalarize this intrinsic. For math builtins
 490   // this will emit a costly libcall, adding call overhead and spills. Make it
 491   // very expensive.
 492   if (RetTy->isVectorTy()) {
 493     unsigned Num = RetTy->getVectorNumElements();
 494     unsigned Cost = TopTTI->getIntrinsicInstrCost(IID, RetTy->getScalarType(),
 495                                                   Tys);
 496     return 10 * Cost * Num;
 497   }
 498
 499   // This is going to be turned into a library call, make it expensive.
 500   return 10;
 501 }
 502
 503 unsigned BasicTTI::getNumberOfParts(Type *Tp) const {
 504   std::pair<unsigned, MVT> LT = getTLI()->getTypeLegalizationCost(Tp);
 505   return LT.first;
 506 }
 507
 508 unsigned BasicTTI::getAddressComputationCost(Type *Ty, bool IsComplex) const {
 509   return 0;
 510 }
 511
 512 unsigned BasicTTI::getReductionCost(unsigned Opcode, Type *Ty,
 513                                     bool IsPairwise) const {
 514   assert(Ty->isVectorTy() && "Expect a vector type");
 515   unsigned NumVecElts = Ty->getVectorNumElements();
 516   unsigned NumReduxLevels = Log2_32(NumVecElts);
 517   unsigned ArithCost = NumReduxLevels *
 518     TopTTI->getArithmeticInstrCost(Opcode, Ty);
 519   // Assume the pairwise shuffles add a cost.
 520   unsigned ShuffleCost =
 521       NumReduxLevels * (IsPairwise + 1) *
 522       TopTTI->getShuffleCost(SK_ExtractSubvector, Ty, NumVecElts / 2, Ty);
 523   return ShuffleCost + ArithCost + getScalarizationOverhead(Ty, false, true);
 524 }