contrib/llvm/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 static TargetTransformInfo::OperandValueKind getOperandInfo(Value *V) {
  92   TargetTransformInfo::OperandValueKind OpInfo =
  93     TargetTransformInfo::OK_AnyValue;
  94
  95   // Check for a splat of a constant.
  96   ConstantDataVector *CDV = 0;
  97   if ((CDV = dyn_cast<ConstantDataVector>(V)))
  98     if (CDV->getSplatValue() != NULL)
  99       OpInfo = TargetTransformInfo::OK_UniformConstantValue;
 100   ConstantVector *CV = 0;
 101   if ((CV = dyn_cast<ConstantVector>(V)))
 102     if (CV->getSplatValue() != NULL)
 103       OpInfo = TargetTransformInfo::OK_UniformConstantValue;
 104
 105   return OpInfo;
 106 }
 107
 108 unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const {
 109   if (!TTI)
 110     return -1;
 111
 112   switch (I->getOpcode()) {
 113   case Instruction::GetElementPtr:{
 114     Type *ValTy = I->getOperand(0)->getType()->getPointerElementType();
 115     return TTI->getAddressComputationCost(ValTy);
 116   }
 117
 118   case Instruction::Ret:
 119   case Instruction::PHI:
 120   case Instruction::Br: {
 121     return TTI->getCFInstrCost(I->getOpcode());
 122   }
 123   case Instruction::Add:
 124   case Instruction::FAdd:
 125   case Instruction::Sub:
 126   case Instruction::FSub:
 127   case Instruction::Mul:
 128   case Instruction::FMul:
 129   case Instruction::UDiv:
 130   case Instruction::SDiv:
 131   case Instruction::FDiv:
 132   case Instruction::URem:
 133   case Instruction::SRem:
 134   case Instruction::FRem:
 135   case Instruction::Shl:
 136   case Instruction::LShr:
 137   case Instruction::AShr:
 138   case Instruction::And:
 139   case Instruction::Or:
 140   case Instruction::Xor: {
 141     TargetTransformInfo::OperandValueKind Op1VK =
 142       getOperandInfo(I->getOperand(0));
 143     TargetTransformInfo::OperandValueKind Op2VK =
 144       getOperandInfo(I->getOperand(1));
 145     return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK,
 146                                        Op2VK);
 147   }
 148   case Instruction::Select: {
 149     const SelectInst *SI = cast<SelectInst>(I);
 150     Type *CondTy = SI->getCondition()->getType();
 151     return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy);
 152   }
 153   case Instruction::ICmp:
 154   case Instruction::FCmp: {
 155     Type *ValTy = I->getOperand(0)->getType();
 156     return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy);
 157   }
 158   case Instruction::Store: {
 159     const StoreInst *SI = cast<StoreInst>(I);
 160     Type *ValTy = SI->getValueOperand()->getType();
 161     return TTI->getMemoryOpCost(I->getOpcode(), ValTy,
 162                                  SI->getAlignment(),
 163                                  SI->getPointerAddressSpace());
 164   }
 165   case Instruction::Load: {
 166     const LoadInst *LI = cast<LoadInst>(I);
 167     return TTI->getMemoryOpCost(I->getOpcode(), I->getType(),
 168                                  LI->getAlignment(),
 169                                  LI->getPointerAddressSpace());
 170   }
 171   case Instruction::ZExt:
 172   case Instruction::SExt:
 173   case Instruction::FPToUI:
 174   case Instruction::FPToSI:
 175   case Instruction::FPExt:
 176   case Instruction::PtrToInt:
 177   case Instruction::IntToPtr:
 178   case Instruction::SIToFP:
 179   case Instruction::UIToFP:
 180   case Instruction::Trunc:
 181   case Instruction::FPTrunc:
 182   case Instruction::BitCast: {
 183     Type *SrcTy = I->getOperand(0)->getType();
 184     return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy);
 185   }
 186   case Instruction::ExtractElement: {
 187     const ExtractElementInst * EEI = cast<ExtractElementInst>(I);
 188     ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
 189     unsigned Idx = -1;
 190     if (CI)
 191       Idx = CI->getZExtValue();
 192     return TTI->getVectorInstrCost(I->getOpcode(),
 193                                    EEI->getOperand(0)->getType(), Idx);
 194   }
 195   case Instruction::InsertElement: {
 196       const InsertElementInst * IE = cast<InsertElementInst>(I);
 197       ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2));
 198       unsigned Idx = -1;
 199       if (CI)
 200         Idx = CI->getZExtValue();
 201       return TTI->getVectorInstrCost(I->getOpcode(),
 202                                      IE->getType(), Idx);
 203     }
 204   case Instruction::ShuffleVector: {
 205     const ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I);
 206     Type *VecTypOp0 = Shuffle->getOperand(0)->getType();
 207     unsigned NumVecElems = VecTypOp0->getVectorNumElements();
 208     SmallVector<int, 16> Mask = Shuffle->getShuffleMask();
 209
 210     if (NumVecElems == Mask.size() && isReverseVectorMask(Mask))
 211       return TTI->getShuffleCost(TargetTransformInfo::SK_Reverse, VecTypOp0, 0,
 212                                  0);
 213     return -1;
 214   }
 215   case Instruction::Call:
 216     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 217       SmallVector<Type*, 4> Tys;
 218       for (unsigned J = 0, JE = II->getNumArgOperands(); J != JE; ++J)
 219         Tys.push_back(II->getArgOperand(J)->getType());
 220
 221       return TTI->getIntrinsicInstrCost(II->getIntrinsicID(), II->getType(),
 222                                         Tys);
 223     }
 224     return -1;
 225   default:
 226     // We don't have any information on this instruction.
 227     return -1;
 228   }
 229 }
 230
 231 void CostModelAnalysis::print(raw_ostream &OS, const Module*) const {
 232   if (!F)
 233     return;
 234
 235   for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) {
 236     for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) {
 237       Instruction *Inst = it;
 238       unsigned Cost = getInstructionCost(Inst);
 239       if (Cost != (unsigned)-1)
 240         OS << "Cost Model: Found an estimated cost of " << Cost;
 241       else
 242         OS << "Cost Model: Unknown cost";
 243
 244       OS << " for instruction: "<< *Inst << "\n";
 245     }
 246   }
 247 }