lib/Transforms/Utils/BasicInliner.cpp

   1 //===- BasicInliner.cpp - Basic function level inliner --------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Devang Patel and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a simple function based inliner that does not use
  11 // call graph information.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "basicinliner"
  16
  17 #include "llvm/Module.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Transforms/Utils/BasicInliner.h"
  20 #include "llvm/Transforms/Utils/Cloning.h"
  21 #include "llvm/Support/CallSite.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/ADT/SmallPtrSet.h"
  25 #include <vector>
  26 #include <set>
  27
  28 using namespace llvm;
  29
  30 namespace {
  31   cl::opt<unsigned>
  32   BasicInlineThreshold("inline-threshold", cl::Hidden, cl::init(200),
  33                        cl::desc("Control the amount of basic inlining to perform (default = 200)"));
  34 }
  35
  36 namespace llvm {
  37
  38   /// BasicInlinerImpl - BasicInliner implemantation class. This hides
  39   /// container info, used by basic inliner, from public interface.
  40   struct VISIBILITY_HIDDEN BasicInlinerImpl {
  41
  42     BasicInlinerImpl(const BasicInlinerImpl&); // DO NOT IMPLEMENT
  43     void operator=(const BasicInlinerImpl&); // DO NO IMPLEMENT
  44   public:
  45     BasicInlinerImpl(TargetData *T) : TD(T) {}
  46
  47     /// addFunction - Add function into the list of functions to process.
  48     /// All functions must be inserted using this interface before invoking
  49     /// inlineFunctions().
  50     void addFunction(Function *F) {
  51       Functions.push_back(F);
  52     }
  53
  54     /// neverInlineFunction - Sometimes a function is never to be inlined
  55     /// because of one or other reason.
  56     void neverInlineFunction(Function *F) {
  57       NeverInline.insert(F);
  58     }
  59
  60     /// inlineFuctions - Walk all call sites in all functions supplied by
  61     /// client. Inline as many call sites as possible. Delete completely
  62     /// inlined functions.
  63     void inlineFunctions();
  64
  65   private:
  66     TargetData *TD;
  67     std::vector<Function *> Functions;
  68     std::set<const Function *> NeverInline;
  69     SmallPtrSet<Function *, 8> DeadFunctions;
  70     InlineCostAnalyzer CA;
  71   };
  72
  73 /// inlineFuctions - Walk all call sites in all functions supplied by
  74 /// client. Inline as many call sites as possible. Delete completely
  75 /// inlined functions.
  76 void BasicInlinerImpl::inlineFunctions() {
  77
  78   // Scan through and identify all call sites ahead of time so that we only
  79   // inline call sites in the original functions, not call sites that result
  80   // from inlining other functions.
  81   std::vector<CallSite> CallSites;
  82
  83   for (std::vector<Function *>::iterator FI = Functions.begin(),
  84          FE = Functions.end(); FI != FE; ++FI) {
  85     Function *F = *FI;
  86     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
  87       for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
  88         CallSite CS = CallSite::get(I);
  89         if (CS.getInstruction() && CS.getCalledFunction()
  90             && !CS.getCalledFunction()->isDeclaration())
  91           CallSites.push_back(CS);
  92       }
  93   }
  94
  95   DOUT << ": " << CallSites.size() << " call sites.\n";
  96
  97   // Inline call sites.
  98   bool Changed = false;
  99   do {
 100     Changed = false;
 101     for (unsigned index = 0; index != CallSites.size() && !CallSites.empty(); ++index) {
 102       CallSite CS = CallSites[index];
 103       if (Function *Callee = CS.getCalledFunction()) {
 104
 105         // Eliminate calls taht are never inlinable.
 106         if (Callee->isDeclaration() ||
 107             CS.getInstruction()->getParent()->getParent() == Callee) {
 108           CallSites.erase(CallSites.begin() + index);
 109               --index;
 110               continue;
 111         }
 112         int InlineCost = CA.getInlineCost(CS, NeverInline);
 113         if (InlineCost >= (int) BasicInlineThreshold) {
 114               DOUT << "  NOT Inlining: cost = " << InlineCost
 115                    << ", call: " <<  *CS.getInstruction();
 116               continue;
 117         }
 118
 119         DOUT << "  Inlining: cost=" << InlineCost
 120              <<", call: " << *CS.getInstruction();
 121
 122         // Inline
 123         if (InlineFunction(CS, NULL, TD)) {
 124           if (Callee->use_empty() && Callee->hasInternalLinkage())
 125                 DeadFunctions.insert(Callee);
 126           Changed = true;
 127           CallSites.erase(CallSites.begin() + index);
 128           --index;
 129         }
 130       }
 131     }
 132   } while (Changed);
 133
 134   // Remove completely inlined functions from module.
 135   for(SmallPtrSet<Function *, 8>::iterator I = DeadFunctions.begin(),
 136         E = DeadFunctions.end(); I != E; ++I) {
 137     Function *D = *I;
 138     Module *M = D->getParent();
 139     M->getFunctionList().remove(D);
 140   }
 141 }
 142
 143 BasicInliner::BasicInliner(TargetData *TD) {
 144   Impl = new BasicInlinerImpl(TD);
 145 }
 146
 147 BasicInliner::~BasicInliner() {
 148   delete Impl;
 149 }
 150
 151 /// addFunction - Add function into the list of functions to process.
 152 /// All functions must be inserted using this interface before invoking
 153 /// inlineFunctions().
 154 void BasicInliner::addFunction(Function *F) {
 155   Impl->addFunction(F);
 156 }
 157
 158 /// neverInlineFunction - Sometimes a function is never to be inlined because
 159 /// of one or other reason.
 160 void BasicInliner::neverInlineFunction(Function *F) {
 161   Impl->neverInlineFunction(F);
 162 }
 163
 164 /// inlineFuctions - Walk all call sites in all functions supplied by
 165 /// client. Inline as many call sites as possible. Delete completely
 166 /// inlined functions.
 167 void BasicInliner::inlineFunctions() {
 168   Impl->inlineFunctions();
 169 }
 170
 171 }