Home | History | Annotate | Download | only in Utils 
      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 }
    183