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 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"; 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 72 CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 73 AU.setPreservesAll(); 74 } 75 76 bool 77 CostModelAnalysis::runOnFunction(Function &F) { 78 this->F = &F; 79 TTI = getAnalysisIfAvailable<TargetTransformInfo>(); 80 81 return false; 82 } 83 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 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 108 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 231 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