Implemented cost model for masked gather and scatter operations
[oota-llvm.git] / include / llvm / Analysis / TargetTransformInfoImpl.h
1 //===- TargetTransformInfoImpl.h --------------------------------*- C++ -*-===//
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 helpers for the implementation of
11 /// a TargetTransformInfo-conforming class.
12 ///
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_ANALYSIS_TARGETTRANSFORMINFOIMPL_H
16 #define LLVM_ANALYSIS_TARGETTRANSFORMINFOIMPL_H
17
18 #include "llvm/Analysis/TargetTransformInfo.h"
19 #include "llvm/IR/CallSite.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/GetElementPtrTypeIterator.h"
23 #include "llvm/IR/Operator.h"
24 #include "llvm/IR/Type.h"
25 #include "llvm/Analysis/VectorUtils.h"
26
27 namespace llvm {
28
29 /// \brief Base class for use as a mix-in that aids implementing
30 /// a TargetTransformInfo-compatible class.
31 class TargetTransformInfoImplBase {
32 protected:
33   typedef TargetTransformInfo TTI;
34
35   const DataLayout &DL;
36
37   explicit TargetTransformInfoImplBase(const DataLayout &DL) : DL(DL) {}
38
39 public:
40   // Provide value semantics. MSVC requires that we spell all of these out.
41   TargetTransformInfoImplBase(const TargetTransformInfoImplBase &Arg)
42       : DL(Arg.DL) {}
43   TargetTransformInfoImplBase(TargetTransformInfoImplBase &&Arg) : DL(Arg.DL) {}
44
45   const DataLayout &getDataLayout() const { return DL; }
46
47   unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) {
48     switch (Opcode) {
49     default:
50       // By default, just classify everything as 'basic'.
51       return TTI::TCC_Basic;
52
53     case Instruction::GetElementPtr:
54       llvm_unreachable("Use getGEPCost for GEP operations!");
55
56     case Instruction::BitCast:
57       assert(OpTy && "Cast instructions must provide the operand type");
58       if (Ty == OpTy || (Ty->isPointerTy() && OpTy->isPointerTy()))
59         // Identity and pointer-to-pointer casts are free.
60         return TTI::TCC_Free;
61
62       // Otherwise, the default basic cost is used.
63       return TTI::TCC_Basic;
64
65     case Instruction::FDiv:
66     case Instruction::FRem:
67     case Instruction::SDiv:
68     case Instruction::SRem:
69     case Instruction::UDiv:
70     case Instruction::URem:
71       return TTI::TCC_Expensive;
72
73     case Instruction::IntToPtr: {
74       // An inttoptr cast is free so long as the input is a legal integer type
75       // which doesn't contain values outside the range of a pointer.
76       unsigned OpSize = OpTy->getScalarSizeInBits();
77       if (DL.isLegalInteger(OpSize) &&
78           OpSize <= DL.getPointerTypeSizeInBits(Ty))
79         return TTI::TCC_Free;
80
81       // Otherwise it's not a no-op.
82       return TTI::TCC_Basic;
83     }
84     case Instruction::PtrToInt: {
85       // A ptrtoint cast is free so long as the result is large enough to store
86       // the pointer, and a legal integer type.
87       unsigned DestSize = Ty->getScalarSizeInBits();
88       if (DL.isLegalInteger(DestSize) &&
89           DestSize >= DL.getPointerTypeSizeInBits(OpTy))
90         return TTI::TCC_Free;
91
92       // Otherwise it's not a no-op.
93       return TTI::TCC_Basic;
94     }
95     case Instruction::Trunc:
96       // trunc to a native type is free (assuming the target has compare and
97       // shift-right of the same width).
98       if (DL.isLegalInteger(DL.getTypeSizeInBits(Ty)))
99         return TTI::TCC_Free;
100
101       return TTI::TCC_Basic;
102     }
103   }
104
105   unsigned getGEPCost(Type *PointeeType, const Value *Ptr,
106                       ArrayRef<const Value *> Operands) {
107     // In the basic model, we just assume that all-constant GEPs will be folded
108     // into their uses via addressing modes.
109     for (unsigned Idx = 0, Size = Operands.size(); Idx != Size; ++Idx)
110       if (!isa<Constant>(Operands[Idx]))
111         return TTI::TCC_Basic;
112
113     return TTI::TCC_Free;
114   }
115
116   unsigned getCallCost(FunctionType *FTy, int NumArgs) {
117     assert(FTy && "FunctionType must be provided to this routine.");
118
119     // The target-independent implementation just measures the size of the
120     // function by approximating that each argument will take on average one
121     // instruction to prepare.
122
123     if (NumArgs < 0)
124       // Set the argument number to the number of explicit arguments in the
125       // function.
126       NumArgs = FTy->getNumParams();
127
128     return TTI::TCC_Basic * (NumArgs + 1);
129   }
130
131   unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
132                             ArrayRef<Type *> ParamTys) {
133     switch (IID) {
134     default:
135       // Intrinsics rarely (if ever) have normal argument setup constraints.
136       // Model them as having a basic instruction cost.
137       // FIXME: This is wrong for libc intrinsics.
138       return TTI::TCC_Basic;
139
140     case Intrinsic::annotation:
141     case Intrinsic::assume:
142     case Intrinsic::dbg_declare:
143     case Intrinsic::dbg_value:
144     case Intrinsic::invariant_start:
145     case Intrinsic::invariant_end:
146     case Intrinsic::lifetime_start:
147     case Intrinsic::lifetime_end:
148     case Intrinsic::objectsize:
149     case Intrinsic::ptr_annotation:
150     case Intrinsic::var_annotation:
151     case Intrinsic::experimental_gc_result:
152     case Intrinsic::experimental_gc_relocate:
153       // These intrinsics don't actually represent code after lowering.
154       return TTI::TCC_Free;
155     }
156   }
157
158   bool hasBranchDivergence() { return false; }
159
160   bool isSourceOfDivergence(const Value *V) { return false; }
161
162   bool isLoweredToCall(const Function *F) {
163     // FIXME: These should almost certainly not be handled here, and instead
164     // handled with the help of TLI or the target itself. This was largely
165     // ported from existing analysis heuristics here so that such refactorings
166     // can take place in the future.
167
168     if (F->isIntrinsic())
169       return false;
170
171     if (F->hasLocalLinkage() || !F->hasName())
172       return true;
173
174     StringRef Name = F->getName();
175
176     // These will all likely lower to a single selection DAG node.
177     if (Name == "copysign" || Name == "copysignf" || Name == "copysignl" ||
178         Name == "fabs" || Name == "fabsf" || Name == "fabsl" || Name == "sin" ||
179         Name == "fmin" || Name == "fminf" || Name == "fminl" ||
180         Name == "fmax" || Name == "fmaxf" || Name == "fmaxl" ||
181         Name == "sinf" || Name == "sinl" || Name == "cos" || Name == "cosf" ||
182         Name == "cosl" || Name == "sqrt" || Name == "sqrtf" || Name == "sqrtl")
183       return false;
184
185     // These are all likely to be optimized into something smaller.
186     if (Name == "pow" || Name == "powf" || Name == "powl" || Name == "exp2" ||
187         Name == "exp2l" || Name == "exp2f" || Name == "floor" ||
188         Name == "floorf" || Name == "ceil" || Name == "round" ||
189         Name == "ffs" || Name == "ffsl" || Name == "abs" || Name == "labs" ||
190         Name == "llabs")
191       return false;
192
193     return true;
194   }
195
196   void getUnrollingPreferences(Loop *, TTI::UnrollingPreferences &) {}
197
198   bool isLegalAddImmediate(int64_t Imm) { return false; }
199
200   bool isLegalICmpImmediate(int64_t Imm) { return false; }
201
202   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
203                              bool HasBaseReg, int64_t Scale,
204                              unsigned AddrSpace) {
205     // Guess that only reg and reg+reg addressing is allowed. This heuristic is
206     // taken from the implementation of LSR.
207     return !BaseGV && BaseOffset == 0 && (Scale == 0 || Scale == 1);
208   }
209
210   bool isLegalMaskedStore(Type *DataType) { return false; }
211
212   bool isLegalMaskedLoad(Type *DataType) { return false; }
213
214   bool isLegalMaskedScatter(Type *DataType) { return false; }
215
216   bool isLegalMaskedGather(Type *DataType) { return false; }
217
218   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
219                            bool HasBaseReg, int64_t Scale, unsigned AddrSpace) {
220     // Guess that all legal addressing mode are free.
221     if (isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg,
222                               Scale, AddrSpace))
223       return 0;
224     return -1;
225   }
226
227   bool isTruncateFree(Type *Ty1, Type *Ty2) { return false; }
228
229   bool isProfitableToHoist(Instruction *I) { return true; }
230
231   bool isTypeLegal(Type *Ty) { return false; }
232
233   unsigned getJumpBufAlignment() { return 0; }
234
235   unsigned getJumpBufSize() { return 0; }
236
237   bool shouldBuildLookupTables() { return true; }
238
239   bool enableAggressiveInterleaving(bool LoopHasReductions) { return false; }
240
241   bool enableInterleavedAccessVectorization() { return false; }
242
243   TTI::PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) {
244     return TTI::PSK_Software;
245   }
246
247   bool haveFastSqrt(Type *Ty) { return false; }
248
249   unsigned getFPOpCost(Type *Ty) { return TargetTransformInfo::TCC_Basic; }
250
251   unsigned getIntImmCost(const APInt &Imm, Type *Ty) { return TTI::TCC_Basic; }
252
253   unsigned getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm,
254                          Type *Ty) {
255     return TTI::TCC_Free;
256   }
257
258   unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
259                          Type *Ty) {
260     return TTI::TCC_Free;
261   }
262
263   unsigned getNumberOfRegisters(bool Vector) { return 8; }
264
265   unsigned getRegisterBitWidth(bool Vector) { return 32; }
266
267   unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
268
269   unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty,
270                                   TTI::OperandValueKind Opd1Info,
271                                   TTI::OperandValueKind Opd2Info,
272                                   TTI::OperandValueProperties Opd1PropInfo,
273                                   TTI::OperandValueProperties Opd2PropInfo) {
274     return 1;
275   }
276
277   unsigned getShuffleCost(TTI::ShuffleKind Kind, Type *Ty, int Index,
278                           Type *SubTp) {
279     return 1;
280   }
281
282   unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) { return 1; }
283
284   unsigned getCFInstrCost(unsigned Opcode) { return 1; }
285
286   unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy) {
287     return 1;
288   }
289
290   unsigned getVectorInstrCost(unsigned Opcode, Type *Val, unsigned Index) {
291     return 1;
292   }
293
294   unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
295                            unsigned AddressSpace) {
296     return 1;
297   }
298
299   unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
300                                  unsigned AddressSpace) {
301     return 1;
302   }
303
304   unsigned getGatherScatterOpCost(unsigned Opcode, Type *DataTy, Value *Ptr,
305                                   bool VariableMask,
306                                   unsigned Alignment) {
307     return 1;
308   }
309
310   unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
311                                       unsigned Factor,
312                                       ArrayRef<unsigned> Indices,
313                                       unsigned Alignment,
314                                       unsigned AddressSpace) {
315     return 1;
316   }
317
318   unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
319                                  ArrayRef<Type *> Tys) {
320     return 1;
321   }
322   unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
323                                  ArrayRef<Value *> Args) {
324     return 1;
325   }
326
327   unsigned getCallInstrCost(Function *F, Type *RetTy, ArrayRef<Type *> Tys) {
328     return 1;
329   }
330
331   unsigned getNumberOfParts(Type *Tp) { return 0; }
332
333   unsigned getAddressComputationCost(Type *Tp, bool) { return 0; }
334
335   unsigned getReductionCost(unsigned, Type *, bool) { return 1; }
336
337   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) { return 0; }
338
339   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) {
340     return false;
341   }
342
343   Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
344                                            Type *ExpectedType) {
345     return nullptr;
346   }
347
348   bool areInlineCompatible(const Function *Caller,
349                            const Function *Callee) const {
350     return (Caller->getFnAttribute("target-cpu") ==
351             Callee->getFnAttribute("target-cpu")) &&
352            (Caller->getFnAttribute("target-features") ==
353             Callee->getFnAttribute("target-features"));
354   }
355 };
356
357 /// \brief CRTP base class for use as a mix-in that aids implementing
358 /// a TargetTransformInfo-compatible class.
359 template <typename T>
360 class TargetTransformInfoImplCRTPBase : public TargetTransformInfoImplBase {
361 private:
362   typedef TargetTransformInfoImplBase BaseT;
363
364 protected:
365   explicit TargetTransformInfoImplCRTPBase(const DataLayout &DL) : BaseT(DL) {}
366
367 public:
368   // Provide value semantics. MSVC requires that we spell all of these out.
369   TargetTransformInfoImplCRTPBase(const TargetTransformInfoImplCRTPBase &Arg)
370       : BaseT(static_cast<const BaseT &>(Arg)) {}
371   TargetTransformInfoImplCRTPBase(TargetTransformInfoImplCRTPBase &&Arg)
372       : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
373
374   using BaseT::getCallCost;
375
376   unsigned getCallCost(const Function *F, int NumArgs) {
377     assert(F && "A concrete function must be provided to this routine.");
378
379     if (NumArgs < 0)
380       // Set the argument number to the number of explicit arguments in the
381       // function.
382       NumArgs = F->arg_size();
383
384     if (Intrinsic::ID IID = F->getIntrinsicID()) {
385       FunctionType *FTy = F->getFunctionType();
386       SmallVector<Type *, 8> ParamTys(FTy->param_begin(), FTy->param_end());
387       return static_cast<T *>(this)
388           ->getIntrinsicCost(IID, FTy->getReturnType(), ParamTys);
389     }
390
391     if (!static_cast<T *>(this)->isLoweredToCall(F))
392       return TTI::TCC_Basic; // Give a basic cost if it will be lowered
393                              // directly.
394
395     return static_cast<T *>(this)->getCallCost(F->getFunctionType(), NumArgs);
396   }
397
398   unsigned getCallCost(const Function *F, ArrayRef<const Value *> Arguments) {
399     // Simply delegate to generic handling of the call.
400     // FIXME: We should use instsimplify or something else to catch calls which
401     // will constant fold with these arguments.
402     return static_cast<T *>(this)->getCallCost(F, Arguments.size());
403   }
404
405   using BaseT::getGEPCost;
406
407   unsigned getGEPCost(Type *PointeeType, const Value *Ptr,
408                       ArrayRef<const Value *> Operands) {
409     const GlobalValue *BaseGV = nullptr;
410     if (Ptr != nullptr) {
411       // TODO: will remove this when pointers have an opaque type.
412       assert(Ptr->getType()->getScalarType()->getPointerElementType() ==
413                  PointeeType &&
414              "explicit pointee type doesn't match operand's pointee type");
415       BaseGV = dyn_cast<GlobalValue>(Ptr->stripPointerCasts());
416     }
417     bool HasBaseReg = (BaseGV == nullptr);
418     int64_t BaseOffset = 0;
419     int64_t Scale = 0;
420
421     // Assumes the address space is 0 when Ptr is nullptr.
422     unsigned AS =
423         (Ptr == nullptr ? 0 : Ptr->getType()->getPointerAddressSpace());
424     auto GTI = gep_type_begin(PointerType::get(PointeeType, AS), Operands);
425     for (auto I = Operands.begin(); I != Operands.end(); ++I, ++GTI) {
426       // We assume that the cost of Scalar GEP with constant index and the
427       // cost of Vector GEP with splat constant index are the same.
428       const ConstantInt *ConstIdx = dyn_cast<ConstantInt>(*I);
429       if (!ConstIdx)
430         if (auto Splat = getSplatValue(*I))
431           ConstIdx = dyn_cast<ConstantInt>(Splat);
432       if (isa<SequentialType>(*GTI)) {
433         int64_t ElementSize = DL.getTypeAllocSize(GTI.getIndexedType());
434         if (ConstIdx)
435           BaseOffset += ConstIdx->getSExtValue() * ElementSize;
436         else {
437           // Needs scale register.
438           if (Scale != 0)
439             // No addressing mode takes two scale registers.
440             return TTI::TCC_Basic;
441           Scale = ElementSize;
442         }
443       } else {
444         StructType *STy = cast<StructType>(*GTI);
445         // For structures the index is always splat or scalar constant
446         assert(ConstIdx && "Unexpected GEP index");
447         uint64_t Field = ConstIdx->getZExtValue();
448         BaseOffset += DL.getStructLayout(STy)->getElementOffset(Field);
449       }
450     }
451
452     if (static_cast<T *>(this)->isLegalAddressingMode(
453             PointerType::get(*GTI, AS), const_cast<GlobalValue *>(BaseGV),
454             BaseOffset, HasBaseReg, Scale, AS)) {
455       return TTI::TCC_Free;
456     }
457     return TTI::TCC_Basic;
458   }
459
460   using BaseT::getIntrinsicCost;
461
462   unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
463                             ArrayRef<const Value *> Arguments) {
464     // Delegate to the generic intrinsic handling code. This mostly provides an
465     // opportunity for targets to (for example) special case the cost of
466     // certain intrinsics based on constants used as arguments.
467     SmallVector<Type *, 8> ParamTys;
468     ParamTys.reserve(Arguments.size());
469     for (unsigned Idx = 0, Size = Arguments.size(); Idx != Size; ++Idx)
470       ParamTys.push_back(Arguments[Idx]->getType());
471     return static_cast<T *>(this)->getIntrinsicCost(IID, RetTy, ParamTys);
472   }
473
474   unsigned getUserCost(const User *U) {
475     if (isa<PHINode>(U))
476       return TTI::TCC_Free; // Model all PHI nodes as free.
477
478     if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U)) {
479       SmallVector<Value *, 4> Indices(GEP->idx_begin(), GEP->idx_end());
480       return static_cast<T *>(this)->getGEPCost(
481           GEP->getSourceElementType(), GEP->getPointerOperand(), Indices);
482     }
483
484     if (auto CS = ImmutableCallSite(U)) {
485       const Function *F = CS.getCalledFunction();
486       if (!F) {
487         // Just use the called value type.
488         Type *FTy = CS.getCalledValue()->getType()->getPointerElementType();
489         return static_cast<T *>(this)
490             ->getCallCost(cast<FunctionType>(FTy), CS.arg_size());
491       }
492
493       SmallVector<const Value *, 8> Arguments(CS.arg_begin(), CS.arg_end());
494       return static_cast<T *>(this)->getCallCost(F, Arguments);
495     }
496
497     if (const CastInst *CI = dyn_cast<CastInst>(U)) {
498       // Result of a cmp instruction is often extended (to be used by other
499       // cmp instructions, logical or return instructions). These are usually
500       // nop on most sane targets.
501       if (isa<CmpInst>(CI->getOperand(0)))
502         return TTI::TCC_Free;
503     }
504
505     return static_cast<T *>(this)->getOperationCost(
506         Operator::getOpcode(U), U->getType(),
507         U->getNumOperands() == 1 ? U->getOperand(0)->getType() : nullptr);
508   }
509 };
510 }
511
512 #endif