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