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