1243789Sdim//===- CostModel.cpp ------ Cost Model Analysis ---------------------------===// 2243789Sdim// 3243789Sdim// The LLVM Compiler Infrastructure 4243789Sdim// 5243789Sdim// This file is distributed under the University of Illinois Open Source 6243789Sdim// License. See LICENSE.TXT for details. 7243789Sdim// 8243789Sdim//===----------------------------------------------------------------------===// 9243789Sdim// 10243789Sdim// This file defines the cost model analysis. It provides a very basic cost 11249423Sdim// estimation for LLVM-IR. This analysis uses the services of the codegen 12249423Sdim// to approximate the cost of any IR instruction when lowered to machine 13249423Sdim// instructions. The cost results are unit-less and the cost number represents 14249423Sdim// the throughput of the machine assuming that all loads hit the cache, all 15249423Sdim// branches are predicted, etc. The cost numbers can be added in order to 16249423Sdim// compare two or more transformation alternatives. 17243789Sdim// 18243789Sdim//===----------------------------------------------------------------------===// 19243789Sdim 20243789Sdim#define CM_NAME "cost-model" 21243789Sdim#define DEBUG_TYPE CM_NAME 22243789Sdim#include "llvm/Analysis/Passes.h" 23249423Sdim#include "llvm/Analysis/TargetTransformInfo.h" 24249423Sdim#include "llvm/IR/Function.h" 25249423Sdim#include "llvm/IR/Instructions.h" 26249423Sdim#include "llvm/IR/IntrinsicInst.h" 27249423Sdim#include "llvm/IR/Value.h" 28243789Sdim#include "llvm/Pass.h" 29243789Sdim#include "llvm/Support/Debug.h" 30243789Sdim#include "llvm/Support/raw_ostream.h" 31243789Sdimusing namespace llvm; 32243789Sdim 33243789Sdimnamespace { 34243789Sdim class CostModelAnalysis : public FunctionPass { 35243789Sdim 36243789Sdim public: 37243789Sdim static char ID; // Class identification, replacement for typeinfo 38249423Sdim CostModelAnalysis() : FunctionPass(ID), F(0), TTI(0) { 39243789Sdim initializeCostModelAnalysisPass( 40243789Sdim *PassRegistry::getPassRegistry()); 41243789Sdim } 42243789Sdim 43243789Sdim /// Returns the expected cost of the instruction. 44243789Sdim /// Returns -1 if the cost is unknown. 45243789Sdim /// Note, this method does not cache the cost calculation and it 46243789Sdim /// can be expensive in some cases. 47249423Sdim unsigned getInstructionCost(const Instruction *I) const; 48243789Sdim 49243789Sdim private: 50243789Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 51243789Sdim virtual bool runOnFunction(Function &F); 52243789Sdim virtual void print(raw_ostream &OS, const Module*) const; 53243789Sdim 54243789Sdim /// The function that we analyze. 55243789Sdim Function *F; 56249423Sdim /// Target information. 57249423Sdim const TargetTransformInfo *TTI; 58243789Sdim }; 59243789Sdim} // End of anonymous namespace 60243789Sdim 61243789Sdim// Register this pass. 62243789Sdimchar CostModelAnalysis::ID = 0; 63243789Sdimstatic const char cm_name[] = "Cost Model Analysis"; 64243789SdimINITIALIZE_PASS_BEGIN(CostModelAnalysis, CM_NAME, cm_name, false, true) 65243789SdimINITIALIZE_PASS_END (CostModelAnalysis, CM_NAME, cm_name, false, true) 66243789Sdim 67243789SdimFunctionPass *llvm::createCostModelAnalysisPass() { 68243789Sdim return new CostModelAnalysis(); 69243789Sdim} 70243789Sdim 71243789Sdimvoid 72243789SdimCostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 73243789Sdim AU.setPreservesAll(); 74243789Sdim} 75243789Sdim 76243789Sdimbool 77243789SdimCostModelAnalysis::runOnFunction(Function &F) { 78243789Sdim this->F = &F; 79243789Sdim TTI = getAnalysisIfAvailable<TargetTransformInfo>(); 80243789Sdim 81243789Sdim return false; 82243789Sdim} 83243789Sdim 84249423Sdimstatic bool isReverseVectorMask(SmallVector<int, 16> &Mask) { 85249423Sdim for (unsigned i = 0, MaskSize = Mask.size(); i < MaskSize; ++i) 86249423Sdim if (Mask[i] > 0 && Mask[i] != (int)(MaskSize - 1 - i)) 87249423Sdim return false; 88249423Sdim return true; 89249423Sdim} 90249423Sdim 91249423Sdimstatic TargetTransformInfo::OperandValueKind getOperandInfo(Value *V) { 92249423Sdim TargetTransformInfo::OperandValueKind OpInfo = 93249423Sdim TargetTransformInfo::OK_AnyValue; 94249423Sdim 95249423Sdim // Check for a splat of a constant. 96249423Sdim ConstantDataVector *CDV = 0; 97249423Sdim if ((CDV = dyn_cast<ConstantDataVector>(V))) 98249423Sdim if (CDV->getSplatValue() != NULL) 99249423Sdim OpInfo = TargetTransformInfo::OK_UniformConstantValue; 100249423Sdim ConstantVector *CV = 0; 101249423Sdim if ((CV = dyn_cast<ConstantVector>(V))) 102249423Sdim if (CV->getSplatValue() != NULL) 103249423Sdim OpInfo = TargetTransformInfo::OK_UniformConstantValue; 104249423Sdim 105249423Sdim return OpInfo; 106249423Sdim} 107249423Sdim 108249423Sdimunsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { 109249423Sdim if (!TTI) 110243789Sdim return -1; 111243789Sdim 112243789Sdim switch (I->getOpcode()) { 113249423Sdim case Instruction::GetElementPtr:{ 114249423Sdim Type *ValTy = I->getOperand(0)->getType()->getPointerElementType(); 115249423Sdim return TTI->getAddressComputationCost(ValTy); 116249423Sdim } 117249423Sdim 118243789Sdim case Instruction::Ret: 119243789Sdim case Instruction::PHI: 120243789Sdim case Instruction::Br: { 121249423Sdim return TTI->getCFInstrCost(I->getOpcode()); 122243789Sdim } 123243789Sdim case Instruction::Add: 124243789Sdim case Instruction::FAdd: 125243789Sdim case Instruction::Sub: 126243789Sdim case Instruction::FSub: 127243789Sdim case Instruction::Mul: 128243789Sdim case Instruction::FMul: 129243789Sdim case Instruction::UDiv: 130243789Sdim case Instruction::SDiv: 131243789Sdim case Instruction::FDiv: 132243789Sdim case Instruction::URem: 133243789Sdim case Instruction::SRem: 134243789Sdim case Instruction::FRem: 135243789Sdim case Instruction::Shl: 136243789Sdim case Instruction::LShr: 137243789Sdim case Instruction::AShr: 138243789Sdim case Instruction::And: 139243789Sdim case Instruction::Or: 140243789Sdim case Instruction::Xor: { 141249423Sdim TargetTransformInfo::OperandValueKind Op1VK = 142249423Sdim getOperandInfo(I->getOperand(0)); 143249423Sdim TargetTransformInfo::OperandValueKind Op2VK = 144249423Sdim getOperandInfo(I->getOperand(1)); 145249423Sdim return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK, 146249423Sdim Op2VK); 147243789Sdim } 148243789Sdim case Instruction::Select: { 149249423Sdim const SelectInst *SI = cast<SelectInst>(I); 150243789Sdim Type *CondTy = SI->getCondition()->getType(); 151249423Sdim return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy); 152243789Sdim } 153243789Sdim case Instruction::ICmp: 154243789Sdim case Instruction::FCmp: { 155243789Sdim Type *ValTy = I->getOperand(0)->getType(); 156249423Sdim return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy); 157243789Sdim } 158243789Sdim case Instruction::Store: { 159249423Sdim const StoreInst *SI = cast<StoreInst>(I); 160243789Sdim Type *ValTy = SI->getValueOperand()->getType(); 161249423Sdim return TTI->getMemoryOpCost(I->getOpcode(), ValTy, 162243789Sdim SI->getAlignment(), 163243789Sdim SI->getPointerAddressSpace()); 164243789Sdim } 165243789Sdim case Instruction::Load: { 166249423Sdim const LoadInst *LI = cast<LoadInst>(I); 167249423Sdim return TTI->getMemoryOpCost(I->getOpcode(), I->getType(), 168243789Sdim LI->getAlignment(), 169243789Sdim LI->getPointerAddressSpace()); 170243789Sdim } 171243789Sdim case Instruction::ZExt: 172243789Sdim case Instruction::SExt: 173243789Sdim case Instruction::FPToUI: 174243789Sdim case Instruction::FPToSI: 175243789Sdim case Instruction::FPExt: 176243789Sdim case Instruction::PtrToInt: 177243789Sdim case Instruction::IntToPtr: 178243789Sdim case Instruction::SIToFP: 179243789Sdim case Instruction::UIToFP: 180243789Sdim case Instruction::Trunc: 181243789Sdim case Instruction::FPTrunc: 182243789Sdim case Instruction::BitCast: { 183243789Sdim Type *SrcTy = I->getOperand(0)->getType(); 184249423Sdim return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy); 185243789Sdim } 186243789Sdim case Instruction::ExtractElement: { 187249423Sdim const ExtractElementInst * EEI = cast<ExtractElementInst>(I); 188243789Sdim ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1)); 189243789Sdim unsigned Idx = -1; 190243789Sdim if (CI) 191243789Sdim Idx = CI->getZExtValue(); 192249423Sdim return TTI->getVectorInstrCost(I->getOpcode(), 193249423Sdim EEI->getOperand(0)->getType(), Idx); 194243789Sdim } 195243789Sdim case Instruction::InsertElement: { 196249423Sdim const InsertElementInst * IE = cast<InsertElementInst>(I); 197243789Sdim ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2)); 198243789Sdim unsigned Idx = -1; 199243789Sdim if (CI) 200243789Sdim Idx = CI->getZExtValue(); 201249423Sdim return TTI->getVectorInstrCost(I->getOpcode(), 202249423Sdim IE->getType(), Idx); 203243789Sdim } 204249423Sdim case Instruction::ShuffleVector: { 205249423Sdim const ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 206249423Sdim Type *VecTypOp0 = Shuffle->getOperand(0)->getType(); 207249423Sdim unsigned NumVecElems = VecTypOp0->getVectorNumElements(); 208249423Sdim SmallVector<int, 16> Mask = Shuffle->getShuffleMask(); 209249423Sdim 210249423Sdim if (NumVecElems == Mask.size() && isReverseVectorMask(Mask)) 211249423Sdim return TTI->getShuffleCost(TargetTransformInfo::SK_Reverse, VecTypOp0, 0, 212249423Sdim 0); 213249423Sdim return -1; 214249423Sdim } 215249423Sdim case Instruction::Call: 216249423Sdim if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 217249423Sdim SmallVector<Type*, 4> Tys; 218249423Sdim for (unsigned J = 0, JE = II->getNumArgOperands(); J != JE; ++J) 219249423Sdim Tys.push_back(II->getArgOperand(J)->getType()); 220249423Sdim 221249423Sdim return TTI->getIntrinsicInstrCost(II->getIntrinsicID(), II->getType(), 222249423Sdim Tys); 223249423Sdim } 224249423Sdim return -1; 225243789Sdim default: 226243789Sdim // We don't have any information on this instruction. 227243789Sdim return -1; 228243789Sdim } 229243789Sdim} 230243789Sdim 231243789Sdimvoid CostModelAnalysis::print(raw_ostream &OS, const Module*) const { 232243789Sdim if (!F) 233243789Sdim return; 234243789Sdim 235243789Sdim for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) { 236243789Sdim for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) { 237243789Sdim Instruction *Inst = it; 238243789Sdim unsigned Cost = getInstructionCost(Inst); 239243789Sdim if (Cost != (unsigned)-1) 240243789Sdim OS << "Cost Model: Found an estimated cost of " << Cost; 241243789Sdim else 242243789Sdim OS << "Cost Model: Unknown cost"; 243243789Sdim 244243789Sdim OS << " for instruction: "<< *Inst << "\n"; 245243789Sdim } 246243789Sdim } 247243789Sdim} 248