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"
31using namespace llvm;
32
33namespace {
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.
62char CostModelAnalysis::ID = 0;
63static const char cm_name[] = "Cost Model Analysis";
64INITIALIZE_PASS_BEGIN(CostModelAnalysis, CM_NAME, cm_name, false, true)
65INITIALIZE_PASS_END  (CostModelAnalysis, CM_NAME, cm_name, false, true)
66
67FunctionPass *llvm::createCostModelAnalysisPass() {
68  return new CostModelAnalysis();
69}
70
71void
72CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
73  AU.setPreservesAll();
74}
75
76bool
77CostModelAnalysis::runOnFunction(Function &F) {
78 this->F = &F;
79 TTI = getAnalysisIfAvailable<TargetTransformInfo>();
80
81 return false;
82}
83
84static 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
91unsigned 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
209void 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}
226