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/Value.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 using namespace llvm;
31 
32 namespace {
33   class CostModelAnalysis : public FunctionPass {
34 
35   public:
36     static char ID; // Class identification, replacement for typeinfo
37     CostModelAnalysis() : FunctionPass(ID), F(0), TTI(0) {
38       initializeCostModelAnalysisPass(
39         *PassRegistry::getPassRegistry());
40     }
41 
42     /// Returns the expected cost of the instruction.
43     /// Returns -1 if the cost is unknown.
44     /// Note, this method does not cache the cost calculation and it
45     /// can be expensive in some cases.
46     unsigned getInstructionCost(const Instruction *I) const;
47 
48   private:
49     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
50     virtual bool runOnFunction(Function &F);
51     virtual void print(raw_ostream &OS, const Module*) const;
52 
53     /// The function that we analyze.
54     Function *F;
55     /// Target information.
56     const TargetTransformInfo *TTI;
57   };
58 }  // End of anonymous namespace
59 
60 // Register this pass.
61 char CostModelAnalysis::ID = 0;
62 static const char cm_name[] = "Cost Model Analysis";
63 INITIALIZE_PASS_BEGIN(CostModelAnalysis, CM_NAME, cm_name, false, true)
64 INITIALIZE_PASS_END  (CostModelAnalysis, CM_NAME, cm_name, false, true)
65 
66 FunctionPass *llvm::createCostModelAnalysisPass() {
67   return new CostModelAnalysis();
68 }
69 
70 void
71 CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
72   AU.setPreservesAll();
73 }
74 
75 bool
76 CostModelAnalysis::runOnFunction(Function &F) {
77  this->F = &F;
78  TTI = getAnalysisIfAvailable<TargetTransformInfo>();
79 
80  return false;
81 }
82 
83 unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const {
84   if (!TTI)
85     return -1;
86 
87   switch (I->getOpcode()) {
88   case Instruction::Ret:
89   case Instruction::PHI:
90   case Instruction::Br: {
91     return TTI->getCFInstrCost(I->getOpcode());
92   }
93   case Instruction::Add:
94   case Instruction::FAdd:
95   case Instruction::Sub:
96   case Instruction::FSub:
97   case Instruction::Mul:
98   case Instruction::FMul:
99   case Instruction::UDiv:
100   case Instruction::SDiv:
101   case Instruction::FDiv:
102   case Instruction::URem:
103   case Instruction::SRem:
104   case Instruction::FRem:
105   case Instruction::Shl:
106   case Instruction::LShr:
107   case Instruction::AShr:
108   case Instruction::And:
109   case Instruction::Or:
110   case Instruction::Xor: {
111     return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType());
112   }
113   case Instruction::Select: {
114     const SelectInst *SI = cast<SelectInst>(I);
115     Type *CondTy = SI->getCondition()->getType();
116     return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy);
117   }
118   case Instruction::ICmp:
119   case Instruction::FCmp: {
120     Type *ValTy = I->getOperand(0)->getType();
121     return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy);
122   }
123   case Instruction::Store: {
124     const StoreInst *SI = cast<StoreInst>(I);
125     Type *ValTy = SI->getValueOperand()->getType();
126     return TTI->getMemoryOpCost(I->getOpcode(), ValTy,
127                                  SI->getAlignment(),
128                                  SI->getPointerAddressSpace());
129   }
130   case Instruction::Load: {
131     const LoadInst *LI = cast<LoadInst>(I);
132     return TTI->getMemoryOpCost(I->getOpcode(), I->getType(),
133                                  LI->getAlignment(),
134                                  LI->getPointerAddressSpace());
135   }
136   case Instruction::ZExt:
137   case Instruction::SExt:
138   case Instruction::FPToUI:
139   case Instruction::FPToSI:
140   case Instruction::FPExt:
141   case Instruction::PtrToInt:
142   case Instruction::IntToPtr:
143   case Instruction::SIToFP:
144   case Instruction::UIToFP:
145   case Instruction::Trunc:
146   case Instruction::FPTrunc:
147   case Instruction::BitCast: {
148     Type *SrcTy = I->getOperand(0)->getType();
149     return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy);
150   }
151   case Instruction::ExtractElement: {
152     const ExtractElementInst * EEI = cast<ExtractElementInst>(I);
153     ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
154     unsigned Idx = -1;
155     if (CI)
156       Idx = CI->getZExtValue();
157     return TTI->getVectorInstrCost(I->getOpcode(),
158                                    EEI->getOperand(0)->getType(), Idx);
159   }
160   case Instruction::InsertElement: {
161       const InsertElementInst * IE = cast<InsertElementInst>(I);
162       ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2));
163       unsigned Idx = -1;
164       if (CI)
165         Idx = CI->getZExtValue();
166       return TTI->getVectorInstrCost(I->getOpcode(),
167                                      IE->getType(), Idx);
168     }
169   default:
170     // We don't have any information on this instruction.
171     return -1;
172   }
173 }
174 
175 void CostModelAnalysis::print(raw_ostream &OS, const Module*) const {
176   if (!F)
177     return;
178 
179   for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) {
180     for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) {
181       Instruction *Inst = it;
182       unsigned Cost = getInstructionCost(Inst);
183       if (Cost != (unsigned)-1)
184         OS << "Cost Model: Found an estimated cost of " << Cost;
185       else
186         OS << "Cost Model: Unknown cost";
187 
188       OS << " for instruction: "<< *Inst << "\n";
189     }
190   }
191 }
192