lib/Transforms/Utils/BasicInliner.cpp

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