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/IR/Function.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/Value.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include "llvm/TargetTransformInfo.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), VTTI(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     /// Vector target information.
  56     const VectorTargetTransformInfo *VTTI;
  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
  79  // Target information.
  80  TargetTransformInfo *TTI;
  81  TTI = getAnalysisIfAvailable<TargetTransformInfo>();
  82  if (TTI)
  83    VTTI = TTI->getVectorTargetTransformInfo();
  84
  85  return false;
  86 }
  87
  88 unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const {
  89   if (!VTTI)
  90     return -1;
  91
  92   switch (I->getOpcode()) {
  93   case Instruction::Ret:
  94   case Instruction::PHI:
  95   case Instruction::Br: {
  96     return VTTI->getCFInstrCost(I->getOpcode());
  97   }
  98   case Instruction::Add:
  99   case Instruction::FAdd:
 100   case Instruction::Sub:
 101   case Instruction::FSub:
 102   case Instruction::Mul:
 103   case Instruction::FMul:
 104   case Instruction::UDiv:
 105   case Instruction::SDiv:
 106   case Instruction::FDiv:
 107   case Instruction::URem:
 108   case Instruction::SRem:
 109   case Instruction::FRem:
 110   case Instruction::Shl:
 111   case Instruction::LShr:
 112   case Instruction::AShr:
 113   case Instruction::And:
 114   case Instruction::Or:
 115   case Instruction::Xor: {
 116     return VTTI->getArithmeticInstrCost(I->getOpcode(), I->getType());
 117   }
 118   case Instruction::Select: {
 119     const SelectInst *SI = cast<SelectInst>(I);
 120     Type *CondTy = SI->getCondition()->getType();
 121     return VTTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy);
 122   }
 123   case Instruction::ICmp:
 124   case Instruction::FCmp: {
 125     Type *ValTy = I->getOperand(0)->getType();
 126     return VTTI->getCmpSelInstrCost(I->getOpcode(), ValTy);
 127   }
 128   case Instruction::Store: {
 129     const StoreInst *SI = cast<StoreInst>(I);
 130     Type *ValTy = SI->getValueOperand()->getType();
 131     return VTTI->getMemoryOpCost(I->getOpcode(), ValTy,
 132                                  SI->getAlignment(),
 133                                  SI->getPointerAddressSpace());
 134   }
 135   case Instruction::Load: {
 136     const LoadInst *LI = cast<LoadInst>(I);
 137     return VTTI->getMemoryOpCost(I->getOpcode(), I->getType(),
 138                                  LI->getAlignment(),
 139                                  LI->getPointerAddressSpace());
 140   }
 141   case Instruction::ZExt:
 142   case Instruction::SExt:
 143   case Instruction::FPToUI:
 144   case Instruction::FPToSI:
 145   case Instruction::FPExt:
 146   case Instruction::PtrToInt:
 147   case Instruction::IntToPtr:
 148   case Instruction::SIToFP:
 149   case Instruction::UIToFP:
 150   case Instruction::Trunc:
 151   case Instruction::FPTrunc:
 152   case Instruction::BitCast: {
 153     Type *SrcTy = I->getOperand(0)->getType();
 154     return VTTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy);
 155   }
 156   case Instruction::ExtractElement: {
 157     const ExtractElementInst * EEI = cast<ExtractElementInst>(I);
 158     ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
 159     unsigned Idx = -1;
 160     if (CI)
 161       Idx = CI->getZExtValue();
 162     return VTTI->getVectorInstrCost(I->getOpcode(),
 163                                     EEI->getOperand(0)->getType(), Idx);
 164   }
 165   case Instruction::InsertElement: {
 166       const InsertElementInst * IE = cast<InsertElementInst>(I);
 167       ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2));
 168       unsigned Idx = -1;
 169       if (CI)
 170         Idx = CI->getZExtValue();
 171       return VTTI->getVectorInstrCost(I->getOpcode(),
 172                                       IE->getType(), Idx);
 173     }
 174   default:
 175     // We don't have any information on this instruction.
 176     return -1;
 177   }
 178 }
 179
 180 void CostModelAnalysis::print(raw_ostream &OS, const Module*) const {
 181   if (!F)
 182     return;
 183
 184   for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) {
 185     for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) {
 186       Instruction *Inst = it;
 187       unsigned Cost = getInstructionCost(Inst);
 188       if (Cost != (unsigned)-1)
 189         OS << "Cost Model: Found an estimated cost of " << Cost;
 190       else
 191         OS << "Cost Model: Unknown cost";
 192
 193       OS << " for instruction: "<< *Inst << "\n";
 194     }
 195   }
 196 }