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" 31using namespace llvm; 32 33namespace { 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. 62char CostModelAnalysis::ID = 0; 63static const char cm_name[] = "Cost Model Analysis"; 64INITIALIZE_PASS_BEGIN(CostModelAnalysis, CM_NAME, cm_name, false, true) 65INITIALIZE_PASS_END (CostModelAnalysis, CM_NAME, cm_name, false, true) 66 67FunctionPass *llvm::createCostModelAnalysisPass() { 68 return new CostModelAnalysis(); 69} 70 71void 72CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 73 AU.setPreservesAll(); 74} 75 76bool 77CostModelAnalysis::runOnFunction(Function &F) { 78 this->F = &F; 79 TTI = getAnalysisIfAvailable<TargetTransformInfo>(); 80 81 return false; 82} 83 84static bool isReverseVectorMask(SmallVector<int, 16> &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 91unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { 92 if (!TTI) 93 return -1; 94 95 switch (I->getOpcode()) { 96 case Instruction::GetElementPtr:{ 97 Type *ValTy = I->getOperand(0)->getType()->getPointerElementType(); 98 return TTI->getAddressComputationCost(ValTy); 99 } 100 101 case Instruction::Ret: 102 case Instruction::PHI: 103 case Instruction::Br: { 104 return TTI->getCFInstrCost(I->getOpcode()); 105 } 106 case Instruction::Add: 107 case Instruction::FAdd: 108 case Instruction::Sub: 109 case Instruction::FSub: 110 case Instruction::Mul: 111 case Instruction::FMul: 112 case Instruction::UDiv: 113 case Instruction::SDiv: 114 case Instruction::FDiv: 115 case Instruction::URem: 116 case Instruction::SRem: 117 case Instruction::FRem: 118 case Instruction::Shl: 119 case Instruction::LShr: 120 case Instruction::AShr: 121 case Instruction::And: 122 case Instruction::Or: 123 case Instruction::Xor: { 124 return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType()); 125 } 126 case Instruction::Select: { 127 const SelectInst *SI = cast<SelectInst>(I); 128 Type *CondTy = SI->getCondition()->getType(); 129 return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy); 130 } 131 case Instruction::ICmp: 132 case Instruction::FCmp: { 133 Type *ValTy = I->getOperand(0)->getType(); 134 return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy); 135 } 136 case Instruction::Store: { 137 const StoreInst *SI = cast<StoreInst>(I); 138 Type *ValTy = SI->getValueOperand()->getType(); 139 return TTI->getMemoryOpCost(I->getOpcode(), ValTy, 140 SI->getAlignment(), 141 SI->getPointerAddressSpace()); 142 } 143 case Instruction::Load: { 144 const LoadInst *LI = cast<LoadInst>(I); 145 return TTI->getMemoryOpCost(I->getOpcode(), I->getType(), 146 LI->getAlignment(), 147 LI->getPointerAddressSpace()); 148 } 149 case Instruction::ZExt: 150 case Instruction::SExt: 151 case Instruction::FPToUI: 152 case Instruction::FPToSI: 153 case Instruction::FPExt: 154 case Instruction::PtrToInt: 155 case Instruction::IntToPtr: 156 case Instruction::SIToFP: 157 case Instruction::UIToFP: 158 case Instruction::Trunc: 159 case Instruction::FPTrunc: 160 case Instruction::BitCast: { 161 Type *SrcTy = I->getOperand(0)->getType(); 162 return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy); 163 } 164 case Instruction::ExtractElement: { 165 const ExtractElementInst * EEI = cast<ExtractElementInst>(I); 166 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1)); 167 unsigned Idx = -1; 168 if (CI) 169 Idx = CI->getZExtValue(); 170 return TTI->getVectorInstrCost(I->getOpcode(), 171 EEI->getOperand(0)->getType(), Idx); 172 } 173 case Instruction::InsertElement: { 174 const InsertElementInst * IE = cast<InsertElementInst>(I); 175 ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2)); 176 unsigned Idx = -1; 177 if (CI) 178 Idx = CI->getZExtValue(); 179 return TTI->getVectorInstrCost(I->getOpcode(), 180 IE->getType(), Idx); 181 } 182 case Instruction::ShuffleVector: { 183 const ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 184 Type *VecTypOp0 = Shuffle->getOperand(0)->getType(); 185 unsigned NumVecElems = VecTypOp0->getVectorNumElements(); 186 SmallVector<int, 16> Mask = Shuffle->getShuffleMask(); 187 188 if (NumVecElems == Mask.size() && isReverseVectorMask(Mask)) 189 return TTI->getShuffleCost(TargetTransformInfo::SK_Reverse, VecTypOp0, 0, 190 0); 191 return -1; 192 } 193 case Instruction::Call: 194 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 195 SmallVector<Type*, 4> Tys; 196 for (unsigned J = 0, JE = II->getNumArgOperands(); J != JE; ++J) 197 Tys.push_back(II->getArgOperand(J)->getType()); 198 199 return TTI->getIntrinsicInstrCost(II->getIntrinsicID(), II->getType(), 200 Tys); 201 } 202 return -1; 203 default: 204 // We don't have any information on this instruction. 205 return -1; 206 } 207} 208 209void CostModelAnalysis::print(raw_ostream &OS, const Module*) const { 210 if (!F) 211 return; 212 213 for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) { 214 for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) { 215 Instruction *Inst = it; 216 unsigned Cost = getInstructionCost(Inst); 217 if (Cost != (unsigned)-1) 218 OS << "Cost Model: Found an estimated cost of " << Cost; 219 else 220 OS << "Cost Model: Unknown cost"; 221 222 OS << " for instruction: "<< *Inst << "\n"; 223 } 224 } 225} 226