lib/Analysis/CostModel.cpp

   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(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
  91 unsigned 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
 209 void 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 }