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