LLVM API Documentation

BasicInliner.cpp

Go to the documentation of this file.
00001 //===- BasicInliner.cpp - Basic function level inliner --------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines a simple function based inliner that does not use
00011 // call graph information. 
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "basicinliner"
00016 
00017 #include "llvm/Module.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/Transforms/Utils/BasicInliner.h"
00020 #include "llvm/Transforms/Utils/Cloning.h"
00021 #include "llvm/Support/CallSite.h"
00022 #include "llvm/Support/CommandLine.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/ADT/SmallPtrSet.h"
00025 #include <vector>
00026 
00027 using namespace llvm;
00028 
00029 static cl::opt<unsigned>     
00030 BasicInlineThreshold("basic-inline-threshold", cl::Hidden, cl::init(200),
00031    cl::desc("Control the amount of basic inlining to perform (default = 200)"));
00032 
00033 namespace llvm {
00034 
00035   /// BasicInlinerImpl - BasicInliner implemantation class. This hides
00036   /// container info, used by basic inliner, from public interface.
00037   struct VISIBILITY_HIDDEN BasicInlinerImpl {
00038     
00039     BasicInlinerImpl(const BasicInlinerImpl&); // DO NOT IMPLEMENT
00040     void operator=(const BasicInlinerImpl&); // DO NO IMPLEMENT
00041   public:
00042     BasicInlinerImpl(TargetData *T) : TD(T) {}
00043 
00044     /// addFunction - Add function into the list of functions to process.
00045     /// All functions must be inserted using this interface before invoking
00046     /// inlineFunctions().
00047     void addFunction(Function *F) {
00048       Functions.push_back(F);
00049     }
00050 
00051     /// neverInlineFunction - Sometimes a function is never to be inlined 
00052     /// because of one or other reason. 
00053     void neverInlineFunction(Function *F) {
00054       NeverInline.insert(F);
00055     }
00056 
00057     /// inlineFuctions - Walk all call sites in all functions supplied by
00058     /// client. Inline as many call sites as possible. Delete completely
00059     /// inlined functions.
00060     void inlineFunctions();
00061     
00062   private:
00063     TargetData *TD;
00064     std::vector<Function *> Functions;
00065     SmallPtrSet<const Function *, 16> NeverInline;
00066     SmallPtrSet<Function *, 8> DeadFunctions;
00067     InlineCostAnalyzer CA;
00068   };
00069 
00070 /// inlineFuctions - Walk all call sites in all functions supplied by
00071 /// client. Inline as many call sites as possible. Delete completely
00072 /// inlined functions.
00073 void BasicInlinerImpl::inlineFunctions() {
00074       
00075   // Scan through and identify all call sites ahead of time so that we only
00076   // inline call sites in the original functions, not call sites that result
00077   // from inlining other functions.
00078   std::vector<CallSite> CallSites;
00079   
00080   for (std::vector<Function *>::iterator FI = Functions.begin(),
00081          FE = Functions.end(); FI != FE; ++FI) {
00082     Function *F = *FI;
00083     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00084       for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
00085         CallSite CS = CallSite::get(I);
00086         if (CS.getInstruction() && CS.getCalledFunction()
00087             && !CS.getCalledFunction()->isDeclaration())
00088           CallSites.push_back(CS);
00089       }
00090   }
00091   
00092   DOUT << ": " << CallSites.size() << " call sites.\n";
00093   
00094   // Inline call sites.
00095   bool Changed = false;
00096   do {
00097     Changed = false;
00098     for (unsigned index = 0; index != CallSites.size() && !CallSites.empty(); 
00099          ++index) {
00100       CallSite CS = CallSites[index];
00101       if (Function *Callee = CS.getCalledFunction()) {
00102         
00103         // Eliminate calls that are never inlinable.
00104         if (Callee->isDeclaration() ||
00105             CS.getInstruction()->getParent()->getParent() == Callee) {
00106           CallSites.erase(CallSites.begin() + index);
00107           --index;
00108           continue;
00109         }
00110         InlineCost IC = CA.getInlineCost(CS, NeverInline);
00111         if (IC.isAlways()) {        
00112           DOUT << "  Inlining: cost=always"
00113                <<", call: " << *CS.getInstruction();
00114         } else if (IC.isNever()) {
00115           DOUT << "  NOT Inlining: cost=never"
00116                <<", call: " << *CS.getInstruction();
00117           continue;
00118         } else {
00119           int Cost = IC.getValue();
00120           
00121           if (Cost >= (int) BasicInlineThreshold) {
00122             DOUT << "  NOT Inlining: cost = " << Cost
00123                  << ", call: " <<  *CS.getInstruction();
00124             continue;
00125           } else {
00126             DOUT << "  Inlining: cost = " << Cost
00127                  << ", call: " <<  *CS.getInstruction();
00128           }
00129         }
00130         
00131         // Inline
00132         if (InlineFunction(CS, NULL, TD)) {
00133           if (Callee->use_empty() && (Callee->hasLocalLinkage() ||
00134                                       Callee->hasAvailableExternallyLinkage()))
00135             DeadFunctions.insert(Callee);
00136           Changed = true;
00137           CallSites.erase(CallSites.begin() + index);
00138           --index;
00139         }
00140       }
00141     }
00142   } while (Changed);
00143   
00144   // Remove completely inlined functions from module.
00145   for(SmallPtrSet<Function *, 8>::iterator I = DeadFunctions.begin(),
00146         E = DeadFunctions.end(); I != E; ++I) {
00147     Function *D = *I;
00148     Module *M = D->getParent();
00149     M->getFunctionList().remove(D);
00150   }
00151 }
00152 
00153 BasicInliner::BasicInliner(TargetData *TD) {
00154   Impl = new BasicInlinerImpl(TD);
00155 }
00156 
00157 BasicInliner::~BasicInliner() {
00158   delete Impl;
00159 }
00160 
00161 /// addFunction - Add function into the list of functions to process.
00162 /// All functions must be inserted using this interface before invoking
00163 /// inlineFunctions().
00164 void BasicInliner::addFunction(Function *F) {
00165   Impl->addFunction(F);
00166 }
00167 
00168 /// neverInlineFunction - Sometimes a function is never to be inlined because
00169 /// of one or other reason. 
00170 void BasicInliner::neverInlineFunction(Function *F) {
00171   Impl->neverInlineFunction(F);
00172 }
00173 
00174 /// inlineFuctions - Walk all call sites in all functions supplied by
00175 /// client. Inline as many call sites as possible. Delete completely
00176 /// inlined functions.
00177 void BasicInliner::inlineFunctions() {
00178   Impl->inlineFunctions();
00179 }
00180 
00181 }