1//===- llvm/Analysis/TargetTransformInfo.cpp ------------------------------===//
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
10#define DEBUG_TYPE "tti"
11#include "llvm/Analysis/TargetTransformInfo.h"
12#include "llvm/IR/DataLayout.h"
13#include "llvm/IR/Operator.h"
14#include "llvm/IR/Instruction.h"
15#include "llvm/IR/IntrinsicInst.h"
16#include "llvm/IR/Instructions.h"
17#include "llvm/Support/CallSite.h"
18#include "llvm/Support/ErrorHandling.h"
19
20using namespace llvm;
21
22// Setup the analysis group to manage the TargetTransformInfo passes.
23INITIALIZE_ANALYSIS_GROUP(TargetTransformInfo, "Target Information", NoTTI)
24char TargetTransformInfo::ID = 0;
25
26TargetTransformInfo::~TargetTransformInfo() {
27}
28
29void TargetTransformInfo::pushTTIStack(Pass *P) {
30  TopTTI = this;
31  PrevTTI = &P->getAnalysis<TargetTransformInfo>();
32
33  // Walk up the chain and update the top TTI pointer.
34  for (TargetTransformInfo *PTTI = PrevTTI; PTTI; PTTI = PTTI->PrevTTI)
35    PTTI->TopTTI = this;
36}
37
38void TargetTransformInfo::popTTIStack() {
39  TopTTI = 0;
40
41  // Walk up the chain and update the top TTI pointer.
42  for (TargetTransformInfo *PTTI = PrevTTI; PTTI; PTTI = PTTI->PrevTTI)
43    PTTI->TopTTI = PrevTTI;
44
45  PrevTTI = 0;
46}
47
48void TargetTransformInfo::getAnalysisUsage(AnalysisUsage &AU) const {
49  AU.addRequired<TargetTransformInfo>();
50}
51
52unsigned TargetTransformInfo::getOperationCost(unsigned Opcode, Type *Ty,
53                                               Type *OpTy) const {
54  return PrevTTI->getOperationCost(Opcode, Ty, OpTy);
55}
56
57unsigned TargetTransformInfo::getGEPCost(
58    const Value *Ptr, ArrayRef<const Value *> Operands) const {
59  return PrevTTI->getGEPCost(Ptr, Operands);
60}
61
62unsigned TargetTransformInfo::getCallCost(FunctionType *FTy,
63                                          int NumArgs) const {
64  return PrevTTI->getCallCost(FTy, NumArgs);
65}
66
67unsigned TargetTransformInfo::getCallCost(const Function *F,
68                                          int NumArgs) const {
69  return PrevTTI->getCallCost(F, NumArgs);
70}
71
72unsigned TargetTransformInfo::getCallCost(
73    const Function *F, ArrayRef<const Value *> Arguments) const {
74  return PrevTTI->getCallCost(F, Arguments);
75}
76
77unsigned TargetTransformInfo::getIntrinsicCost(
78    Intrinsic::ID IID, Type *RetTy, ArrayRef<Type *> ParamTys) const {
79  return PrevTTI->getIntrinsicCost(IID, RetTy, ParamTys);
80}
81
82unsigned TargetTransformInfo::getIntrinsicCost(
83    Intrinsic::ID IID, Type *RetTy, ArrayRef<const Value *> Arguments) const {
84  return PrevTTI->getIntrinsicCost(IID, RetTy, Arguments);
85}
86
87unsigned TargetTransformInfo::getUserCost(const User *U) const {
88  return PrevTTI->getUserCost(U);
89}
90
91bool TargetTransformInfo::hasBranchDivergence() const {
92  return PrevTTI->hasBranchDivergence();
93}
94
95bool TargetTransformInfo::isLoweredToCall(const Function *F) const {
96  return PrevTTI->isLoweredToCall(F);
97}
98
99bool TargetTransformInfo::isLegalAddImmediate(int64_t Imm) const {
100  return PrevTTI->isLegalAddImmediate(Imm);
101}
102
103bool TargetTransformInfo::isLegalICmpImmediate(int64_t Imm) const {
104  return PrevTTI->isLegalICmpImmediate(Imm);
105}
106
107bool TargetTransformInfo::isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
108                                                int64_t BaseOffset,
109                                                bool HasBaseReg,
110                                                int64_t Scale) const {
111  return PrevTTI->isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg,
112                                        Scale);
113}
114
115int TargetTransformInfo::getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
116                                              int64_t BaseOffset,
117                                              bool HasBaseReg,
118                                              int64_t Scale) const {
119  return PrevTTI->getScalingFactorCost(Ty, BaseGV, BaseOffset, HasBaseReg,
120                                       Scale);
121}
122
123bool TargetTransformInfo::isTruncateFree(Type *Ty1, Type *Ty2) const {
124  return PrevTTI->isTruncateFree(Ty1, Ty2);
125}
126
127bool TargetTransformInfo::isTypeLegal(Type *Ty) const {
128  return PrevTTI->isTypeLegal(Ty);
129}
130
131unsigned TargetTransformInfo::getJumpBufAlignment() const {
132  return PrevTTI->getJumpBufAlignment();
133}
134
135unsigned TargetTransformInfo::getJumpBufSize() const {
136  return PrevTTI->getJumpBufSize();
137}
138
139bool TargetTransformInfo::shouldBuildLookupTables() const {
140  return PrevTTI->shouldBuildLookupTables();
141}
142
143TargetTransformInfo::PopcntSupportKind
144TargetTransformInfo::getPopcntSupport(unsigned IntTyWidthInBit) const {
145  return PrevTTI->getPopcntSupport(IntTyWidthInBit);
146}
147
148unsigned TargetTransformInfo::getIntImmCost(const APInt &Imm, Type *Ty) const {
149  return PrevTTI->getIntImmCost(Imm, Ty);
150}
151
152unsigned TargetTransformInfo::getNumberOfRegisters(bool Vector) const {
153  return PrevTTI->getNumberOfRegisters(Vector);
154}
155
156unsigned TargetTransformInfo::getRegisterBitWidth(bool Vector) const {
157  return PrevTTI->getRegisterBitWidth(Vector);
158}
159
160unsigned TargetTransformInfo::getMaximumUnrollFactor() const {
161  return PrevTTI->getMaximumUnrollFactor();
162}
163
164unsigned TargetTransformInfo::getArithmeticInstrCost(unsigned Opcode,
165                                                Type *Ty,
166                                                OperandValueKind Op1Info,
167                                                OperandValueKind Op2Info) const {
168  return PrevTTI->getArithmeticInstrCost(Opcode, Ty, Op1Info, Op2Info);
169}
170
171unsigned TargetTransformInfo::getShuffleCost(ShuffleKind Kind, Type *Tp,
172                                             int Index, Type *SubTp) const {
173  return PrevTTI->getShuffleCost(Kind, Tp, Index, SubTp);
174}
175
176unsigned TargetTransformInfo::getCastInstrCost(unsigned Opcode, Type *Dst,
177                                               Type *Src) const {
178  return PrevTTI->getCastInstrCost(Opcode, Dst, Src);
179}
180
181unsigned TargetTransformInfo::getCFInstrCost(unsigned Opcode) const {
182  return PrevTTI->getCFInstrCost(Opcode);
183}
184
185unsigned TargetTransformInfo::getCmpSelInstrCost(unsigned Opcode, Type *ValTy,
186                                                 Type *CondTy) const {
187  return PrevTTI->getCmpSelInstrCost(Opcode, ValTy, CondTy);
188}
189
190unsigned TargetTransformInfo::getVectorInstrCost(unsigned Opcode, Type *Val,
191                                                 unsigned Index) const {
192  return PrevTTI->getVectorInstrCost(Opcode, Val, Index);
193}
194
195unsigned TargetTransformInfo::getMemoryOpCost(unsigned Opcode, Type *Src,
196                                              unsigned Alignment,
197                                              unsigned AddressSpace) const {
198  return PrevTTI->getMemoryOpCost(Opcode, Src, Alignment, AddressSpace);
199  ;
200}
201
202unsigned
203TargetTransformInfo::getIntrinsicInstrCost(Intrinsic::ID ID,
204                                           Type *RetTy,
205                                           ArrayRef<Type *> Tys) const {
206  return PrevTTI->getIntrinsicInstrCost(ID, RetTy, Tys);
207}
208
209unsigned TargetTransformInfo::getNumberOfParts(Type *Tp) const {
210  return PrevTTI->getNumberOfParts(Tp);
211}
212
213unsigned TargetTransformInfo::getAddressComputationCost(Type *Tp,
214                                                        bool IsComplex) const {
215  return PrevTTI->getAddressComputationCost(Tp, IsComplex);
216}
217
218namespace {
219
220struct NoTTI : ImmutablePass, TargetTransformInfo {
221  const DataLayout *DL;
222
223  NoTTI() : ImmutablePass(ID), DL(0) {
224    initializeNoTTIPass(*PassRegistry::getPassRegistry());
225  }
226
227  virtual void initializePass() {
228    // Note that this subclass is special, and must *not* call initializeTTI as
229    // it does not chain.
230    TopTTI = this;
231    PrevTTI = 0;
232    DL = getAnalysisIfAvailable<DataLayout>();
233  }
234
235  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
236    // Note that this subclass is special, and must *not* call
237    // TTI::getAnalysisUsage as it breaks the recursion.
238  }
239
240  /// Pass identification.
241  static char ID;
242
243  /// Provide necessary pointer adjustments for the two base classes.
244  virtual void *getAdjustedAnalysisPointer(const void *ID) {
245    if (ID == &TargetTransformInfo::ID)
246      return (TargetTransformInfo*)this;
247    return this;
248  }
249
250  unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) const {
251    switch (Opcode) {
252    default:
253      // By default, just classify everything as 'basic'.
254      return TCC_Basic;
255
256    case Instruction::GetElementPtr:
257      llvm_unreachable("Use getGEPCost for GEP operations!");
258
259    case Instruction::BitCast:
260      assert(OpTy && "Cast instructions must provide the operand type");
261      if (Ty == OpTy || (Ty->isPointerTy() && OpTy->isPointerTy()))
262        // Identity and pointer-to-pointer casts are free.
263        return TCC_Free;
264
265      // Otherwise, the default basic cost is used.
266      return TCC_Basic;
267
268    case Instruction::IntToPtr:
269      // An inttoptr cast is free so long as the input is a legal integer type
270      // which doesn't contain values outside the range of a pointer.
271      if (DL && DL->isLegalInteger(OpTy->getScalarSizeInBits()) &&
272          OpTy->getScalarSizeInBits() <= DL->getPointerSizeInBits())
273        return TCC_Free;
274
275      // Otherwise it's not a no-op.
276      return TCC_Basic;
277
278    case Instruction::PtrToInt:
279      // A ptrtoint cast is free so long as the result is large enough to store
280      // the pointer, and a legal integer type.
281      if (DL && DL->isLegalInteger(Ty->getScalarSizeInBits()) &&
282          Ty->getScalarSizeInBits() >= DL->getPointerSizeInBits())
283        return TCC_Free;
284
285      // Otherwise it's not a no-op.
286      return TCC_Basic;
287
288    case Instruction::Trunc:
289      // trunc to a native type is free (assuming the target has compare and
290      // shift-right of the same width).
291      if (DL && DL->isLegalInteger(DL->getTypeSizeInBits(Ty)))
292        return TCC_Free;
293
294      return TCC_Basic;
295    }
296  }
297
298  unsigned getGEPCost(const Value *Ptr,
299                      ArrayRef<const Value *> Operands) const {
300    // In the basic model, we just assume that all-constant GEPs will be folded
301    // into their uses via addressing modes.
302    for (unsigned Idx = 0, Size = Operands.size(); Idx != Size; ++Idx)
303      if (!isa<Constant>(Operands[Idx]))
304        return TCC_Basic;
305
306    return TCC_Free;
307  }
308
309  unsigned getCallCost(FunctionType *FTy, int NumArgs = -1) const {
310    assert(FTy && "FunctionType must be provided to this routine.");
311
312    // The target-independent implementation just measures the size of the
313    // function by approximating that each argument will take on average one
314    // instruction to prepare.
315
316    if (NumArgs < 0)
317      // Set the argument number to the number of explicit arguments in the
318      // function.
319      NumArgs = FTy->getNumParams();
320
321    return TCC_Basic * (NumArgs + 1);
322  }
323
324  unsigned getCallCost(const Function *F, int NumArgs = -1) const {
325    assert(F && "A concrete function must be provided to this routine.");
326
327    if (NumArgs < 0)
328      // Set the argument number to the number of explicit arguments in the
329      // function.
330      NumArgs = F->arg_size();
331
332    if (Intrinsic::ID IID = (Intrinsic::ID)F->getIntrinsicID()) {
333      FunctionType *FTy = F->getFunctionType();
334      SmallVector<Type *, 8> ParamTys(FTy->param_begin(), FTy->param_end());
335      return TopTTI->getIntrinsicCost(IID, FTy->getReturnType(), ParamTys);
336    }
337
338    if (!TopTTI->isLoweredToCall(F))
339      return TCC_Basic; // Give a basic cost if it will be lowered directly.
340
341    return TopTTI->getCallCost(F->getFunctionType(), NumArgs);
342  }
343
344  unsigned getCallCost(const Function *F,
345                       ArrayRef<const Value *> Arguments) const {
346    // Simply delegate to generic handling of the call.
347    // FIXME: We should use instsimplify or something else to catch calls which
348    // will constant fold with these arguments.
349    return TopTTI->getCallCost(F, Arguments.size());
350  }
351
352  unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
353                            ArrayRef<Type *> ParamTys) const {
354    switch (IID) {
355    default:
356      // Intrinsics rarely (if ever) have normal argument setup constraints.
357      // Model them as having a basic instruction cost.
358      // FIXME: This is wrong for libc intrinsics.
359      return TCC_Basic;
360
361    case Intrinsic::dbg_declare:
362    case Intrinsic::dbg_value:
363    case Intrinsic::invariant_start:
364    case Intrinsic::invariant_end:
365    case Intrinsic::lifetime_start:
366    case Intrinsic::lifetime_end:
367    case Intrinsic::objectsize:
368    case Intrinsic::ptr_annotation:
369    case Intrinsic::var_annotation:
370      // These intrinsics don't actually represent code after lowering.
371      return TCC_Free;
372    }
373  }
374
375  unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
376                            ArrayRef<const Value *> Arguments) const {
377    // Delegate to the generic intrinsic handling code. This mostly provides an
378    // opportunity for targets to (for example) special case the cost of
379    // certain intrinsics based on constants used as arguments.
380    SmallVector<Type *, 8> ParamTys;
381    ParamTys.reserve(Arguments.size());
382    for (unsigned Idx = 0, Size = Arguments.size(); Idx != Size; ++Idx)
383      ParamTys.push_back(Arguments[Idx]->getType());
384    return TopTTI->getIntrinsicCost(IID, RetTy, ParamTys);
385  }
386
387  unsigned getUserCost(const User *U) const {
388    if (isa<PHINode>(U))
389      return TCC_Free; // Model all PHI nodes as free.
390
391    if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U))
392      // In the basic model we just assume that all-constant GEPs will be
393      // folded into their uses via addressing modes.
394      return GEP->hasAllConstantIndices() ? TCC_Free : TCC_Basic;
395
396    if (ImmutableCallSite CS = U) {
397      const Function *F = CS.getCalledFunction();
398      if (!F) {
399        // Just use the called value type.
400        Type *FTy = CS.getCalledValue()->getType()->getPointerElementType();
401        return TopTTI->getCallCost(cast<FunctionType>(FTy), CS.arg_size());
402      }
403
404      SmallVector<const Value *, 8> Arguments;
405      for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(),
406                                           AE = CS.arg_end();
407           AI != AE; ++AI)
408        Arguments.push_back(*AI);
409
410      return TopTTI->getCallCost(F, Arguments);
411    }
412
413    if (const CastInst *CI = dyn_cast<CastInst>(U)) {
414      // Result of a cmp instruction is often extended (to be used by other
415      // cmp instructions, logical or return instructions). These are usually
416      // nop on most sane targets.
417      if (isa<CmpInst>(CI->getOperand(0)))
418        return TCC_Free;
419    }
420
421    // Otherwise delegate to the fully generic implementations.
422    return getOperationCost(Operator::getOpcode(U), U->getType(),
423                            U->getNumOperands() == 1 ?
424                                U->getOperand(0)->getType() : 0);
425  }
426
427  bool hasBranchDivergence() const { return false; }
428
429  bool isLoweredToCall(const Function *F) const {
430    // FIXME: These should almost certainly not be handled here, and instead
431    // handled with the help of TLI or the target itself. This was largely
432    // ported from existing analysis heuristics here so that such refactorings
433    // can take place in the future.
434
435    if (F->isIntrinsic())
436      return false;
437
438    if (F->hasLocalLinkage() || !F->hasName())
439      return true;
440
441    StringRef Name = F->getName();
442
443    // These will all likely lower to a single selection DAG node.
444    if (Name == "copysign" || Name == "copysignf" || Name == "copysignl" ||
445        Name == "fabs" || Name == "fabsf" || Name == "fabsl" || Name == "sin" ||
446        Name == "sinf" || Name == "sinl" || Name == "cos" || Name == "cosf" ||
447        Name == "cosl" || Name == "sqrt" || Name == "sqrtf" || Name == "sqrtl")
448      return false;
449
450    // These are all likely to be optimized into something smaller.
451    if (Name == "pow" || Name == "powf" || Name == "powl" || Name == "exp2" ||
452        Name == "exp2l" || Name == "exp2f" || Name == "floor" || Name ==
453        "floorf" || Name == "ceil" || Name == "round" || Name == "ffs" ||
454        Name == "ffsl" || Name == "abs" || Name == "labs" || Name == "llabs")
455      return false;
456
457    return true;
458  }
459
460  bool isLegalAddImmediate(int64_t Imm) const {
461    return false;
462  }
463
464  bool isLegalICmpImmediate(int64_t Imm) const {
465    return false;
466  }
467
468  bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
469                             bool HasBaseReg, int64_t Scale) const {
470    // Guess that reg+reg addressing is allowed. This heuristic is taken from
471    // the implementation of LSR.
472    return !BaseGV && BaseOffset == 0 && Scale <= 1;
473  }
474
475  int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
476                           bool HasBaseReg, int64_t Scale) const {
477    // Guess that all legal addressing mode are free.
478    if(isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg, Scale))
479      return 0;
480    return -1;
481  }
482
483
484  bool isTruncateFree(Type *Ty1, Type *Ty2) const {
485    return false;
486  }
487
488  bool isTypeLegal(Type *Ty) const {
489    return false;
490  }
491
492  unsigned getJumpBufAlignment() const {
493    return 0;
494  }
495
496  unsigned getJumpBufSize() const {
497    return 0;
498  }
499
500  bool shouldBuildLookupTables() const {
501    return true;
502  }
503
504  PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) const {
505    return PSK_Software;
506  }
507
508  unsigned getIntImmCost(const APInt &Imm, Type *Ty) const {
509    return 1;
510  }
511
512  unsigned getNumberOfRegisters(bool Vector) const {
513    return 8;
514  }
515
516  unsigned  getRegisterBitWidth(bool Vector) const {
517    return 32;
518  }
519
520  unsigned getMaximumUnrollFactor() const {
521    return 1;
522  }
523
524  unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind,
525                                  OperandValueKind) const {
526    return 1;
527  }
528
529  unsigned getShuffleCost(ShuffleKind Kind, Type *Tp,
530                          int Index = 0, Type *SubTp = 0) const {
531    return 1;
532  }
533
534  unsigned getCastInstrCost(unsigned Opcode, Type *Dst,
535                            Type *Src) const {
536    return 1;
537  }
538
539  unsigned getCFInstrCost(unsigned Opcode) const {
540    return 1;
541  }
542
543  unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy,
544                              Type *CondTy = 0) const {
545    return 1;
546  }
547
548  unsigned getVectorInstrCost(unsigned Opcode, Type *Val,
549                              unsigned Index = -1) const {
550    return 1;
551  }
552
553  unsigned getMemoryOpCost(unsigned Opcode, Type *Src,
554                           unsigned Alignment,
555                           unsigned AddressSpace) const {
556    return 1;
557  }
558
559  unsigned getIntrinsicInstrCost(Intrinsic::ID ID,
560                                 Type *RetTy,
561                                 ArrayRef<Type*> Tys) const {
562    return 1;
563  }
564
565  unsigned getNumberOfParts(Type *Tp) const {
566    return 0;
567  }
568
569  unsigned getAddressComputationCost(Type *Tp, bool) const {
570    return 0;
571  }
572};
573
574} // end anonymous namespace
575
576INITIALIZE_AG_PASS(NoTTI, TargetTransformInfo, "notti",
577                   "No target information", true, true, true)
578char NoTTI::ID = 0;
579
580ImmutablePass *llvm::createNoTargetTransformInfoPass() {
581  return new NoTTI();
582}
583