1 //===- CostModel.cpp ------ Cost Model Analysis ---------------------------===//
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 // This file defines the cost model analysis. It provides a very basic cost
11 // estimation for LLVM-IR. This analysis uses the services of the codegen
12 // to approximate the cost of any IR instruction when lowered to machine
13 // instructions. The cost results are unit-less and the cost number represents
14 // the throughput of the machine assuming that all loads hit the cache, all
15 // branches are predicted, etc. The cost numbers can be added in order to
16 // compare two or more transformation alternatives.
17 //
18 //===----------------------------------------------------------------------===//
19
20 #define CM_NAME "cost-model"
21 #define DEBUG_TYPE CM_NAME
22 #include "llvm/Analysis/Passes.h"
23 #include "llvm/Analysis/TargetTransformInfo.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Value.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/raw_ostream.h"
31 using namespace llvm;
32
33 namespace {
34 class CostModelAnalysis : public FunctionPass {
35
36 public:
37 static char ID; // Class identification, replacement for typeinfo
CostModelAnalysis()38 CostModelAnalysis() : FunctionPass(ID), F(0), TTI(0) {
39 initializeCostModelAnalysisPass(
40 *PassRegistry::getPassRegistry());
41 }
42
43 /// Returns the expected cost of the instruction.
44 /// Returns -1 if the cost is unknown.
45 /// Note, this method does not cache the cost calculation and it
46 /// can be expensive in some cases.
47 unsigned getInstructionCost(const Instruction *I) const;
48
49 private:
50 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
51 virtual bool runOnFunction(Function &F);
52 virtual void print(raw_ostream &OS, const Module*) const;
53
54 /// The function that we analyze.
55 Function *F;
56 /// Target information.
57 const TargetTransformInfo *TTI;
58 };
59 } // End of anonymous namespace
60
61 // Register this pass.
62 char CostModelAnalysis::ID = 0;
63 static const char cm_name[] = "Cost Model Analysis";
INITIALIZE_PASS_BEGIN(CostModelAnalysis,CM_NAME,cm_name,false,true)64 INITIALIZE_PASS_BEGIN(CostModelAnalysis, CM_NAME, cm_name, false, true)
65 INITIALIZE_PASS_END (CostModelAnalysis, CM_NAME, cm_name, false, true)
66
67 FunctionPass *llvm::createCostModelAnalysisPass() {
68 return new CostModelAnalysis();
69 }
70
71 void
getAnalysisUsage(AnalysisUsage & AU) const72 CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
73 AU.setPreservesAll();
74 }
75
76 bool
runOnFunction(Function & F)77 CostModelAnalysis::runOnFunction(Function &F) {
78 this->F = &F;
79 TTI = getAnalysisIfAvailable<TargetTransformInfo>();
80
81 return false;
82 }
83
isReverseVectorMask(SmallVectorImpl<int> & Mask)84 static bool isReverseVectorMask(SmallVectorImpl<int> &Mask) {
85 for (unsigned i = 0, MaskSize = Mask.size(); i < MaskSize; ++i)
86 if (Mask[i] > 0 && Mask[i] != (int)(MaskSize - 1 - i))
87 return false;
88 return true;
89 }
90
getOperandInfo(Value * V)91 static TargetTransformInfo::OperandValueKind getOperandInfo(Value *V) {
92 TargetTransformInfo::OperandValueKind OpInfo =
93 TargetTransformInfo::OK_AnyValue;
94
95 // Check for a splat of a constant.
96 ConstantDataVector *CDV = 0;
97 if ((CDV = dyn_cast<ConstantDataVector>(V)))
98 if (CDV->getSplatValue() != NULL)
99 OpInfo = TargetTransformInfo::OK_UniformConstantValue;
100 ConstantVector *CV = 0;
101 if ((CV = dyn_cast<ConstantVector>(V)))
102 if (CV->getSplatValue() != NULL)
103 OpInfo = TargetTransformInfo::OK_UniformConstantValue;
104
105 return OpInfo;
106 }
107
getInstructionCost(const Instruction * I) const108 unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const {
109 if (!TTI)
110 return -1;
111
112 switch (I->getOpcode()) {
113 case Instruction::GetElementPtr:{
114 Type *ValTy = I->getOperand(0)->getType()->getPointerElementType();
115 return TTI->getAddressComputationCost(ValTy);
116 }
117
118 case Instruction::Ret:
119 case Instruction::PHI:
120 case Instruction::Br: {
121 return TTI->getCFInstrCost(I->getOpcode());
122 }
123 case Instruction::Add:
124 case Instruction::FAdd:
125 case Instruction::Sub:
126 case Instruction::FSub:
127 case Instruction::Mul:
128 case Instruction::FMul:
129 case Instruction::UDiv:
130 case Instruction::SDiv:
131 case Instruction::FDiv:
132 case Instruction::URem:
133 case Instruction::SRem:
134 case Instruction::FRem:
135 case Instruction::Shl:
136 case Instruction::LShr:
137 case Instruction::AShr:
138 case Instruction::And:
139 case Instruction::Or:
140 case Instruction::Xor: {
141 TargetTransformInfo::OperandValueKind Op1VK =
142 getOperandInfo(I->getOperand(0));
143 TargetTransformInfo::OperandValueKind Op2VK =
144 getOperandInfo(I->getOperand(1));
145 return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK,
146 Op2VK);
147 }
148 case Instruction::Select: {
149 const SelectInst *SI = cast<SelectInst>(I);
150 Type *CondTy = SI->getCondition()->getType();
151 return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy);
152 }
153 case Instruction::ICmp:
154 case Instruction::FCmp: {
155 Type *ValTy = I->getOperand(0)->getType();
156 return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy);
157 }
158 case Instruction::Store: {
159 const StoreInst *SI = cast<StoreInst>(I);
160 Type *ValTy = SI->getValueOperand()->getType();
161 return TTI->getMemoryOpCost(I->getOpcode(), ValTy,
162 SI->getAlignment(),
163 SI->getPointerAddressSpace());
164 }
165 case Instruction::Load: {
166 const LoadInst *LI = cast<LoadInst>(I);
167 return TTI->getMemoryOpCost(I->getOpcode(), I->getType(),
168 LI->getAlignment(),
169 LI->getPointerAddressSpace());
170 }
171 case Instruction::ZExt:
172 case Instruction::SExt:
173 case Instruction::FPToUI:
174 case Instruction::FPToSI:
175 case Instruction::FPExt:
176 case Instruction::PtrToInt:
177 case Instruction::IntToPtr:
178 case Instruction::SIToFP:
179 case Instruction::UIToFP:
180 case Instruction::Trunc:
181 case Instruction::FPTrunc:
182 case Instruction::BitCast: {
183 Type *SrcTy = I->getOperand(0)->getType();
184 return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy);
185 }
186 case Instruction::ExtractElement: {
187 const ExtractElementInst * EEI = cast<ExtractElementInst>(I);
188 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
189 unsigned Idx = -1;
190 if (CI)
191 Idx = CI->getZExtValue();
192 return TTI->getVectorInstrCost(I->getOpcode(),
193 EEI->getOperand(0)->getType(), Idx);
194 }
195 case Instruction::InsertElement: {
196 const InsertElementInst * IE = cast<InsertElementInst>(I);
197 ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2));
198 unsigned Idx = -1;
199 if (CI)
200 Idx = CI->getZExtValue();
201 return TTI->getVectorInstrCost(I->getOpcode(),
202 IE->getType(), Idx);
203 }
204 case Instruction::ShuffleVector: {
205 const ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I);
206 Type *VecTypOp0 = Shuffle->getOperand(0)->getType();
207 unsigned NumVecElems = VecTypOp0->getVectorNumElements();
208 SmallVector<int, 16> Mask = Shuffle->getShuffleMask();
209
210 if (NumVecElems == Mask.size() && isReverseVectorMask(Mask))
211 return TTI->getShuffleCost(TargetTransformInfo::SK_Reverse, VecTypOp0, 0,
212 0);
213 return -1;
214 }
215 case Instruction::Call:
216 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
217 SmallVector<Type*, 4> Tys;
218 for (unsigned J = 0, JE = II->getNumArgOperands(); J != JE; ++J)
219 Tys.push_back(II->getArgOperand(J)->getType());
220
221 return TTI->getIntrinsicInstrCost(II->getIntrinsicID(), II->getType(),
222 Tys);
223 }
224 return -1;
225 default:
226 // We don't have any information on this instruction.
227 return -1;
228 }
229 }
230
print(raw_ostream & OS,const Module *) const231 void CostModelAnalysis::print(raw_ostream &OS, const Module*) const {
232 if (!F)
233 return;
234
235 for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) {
236 for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) {
237 Instruction *Inst = it;
238 unsigned Cost = getInstructionCost(Inst);
239 if (Cost != (unsigned)-1)
240 OS << "Cost Model: Found an estimated cost of " << Cost;
241 else
242 OS << "Cost Model: Unknown cost";
243
244 OS << " for instruction: "<< *Inst << "\n";
245 }
246 }
247 }
248