lib/Transforms/IPO/Inliner.cpp

   1 //===- Inliner.cpp - Code common to all inliners --------------------------===//
   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 implements the mechanics required to implement inlining without
  11 // missing any calls and updating the call graph.  The decisions of which calls
  12 // are profitable to inline are implemented elsewhere.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "inline"
  17 #include "llvm/Module.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/IntrinsicInst.h"
  20 #include "llvm/Analysis/CallGraph.h"
  21 #include "llvm/Support/CallSite.h"
  22 #include "llvm/Target/TargetData.h"
  23 #include "llvm/Transforms/IPO/InlinerPass.h"
  24 #include "llvm/Transforms/Utils/InlineCost.h"
  25 #include "llvm/Transforms/Utils/Cloning.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include "llvm/ADT/SmallPtrSet.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include <set>
  32 using namespace llvm;
  33
  34 STATISTIC(NumInlined, "Number of functions inlined");
  35 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
  36 STATISTIC(NumMergedAllocas, "Number of allocas merged together");
  37
  38 static cl::opt<int>
  39 InlineLimit("inline-threshold", cl::Hidden, cl::init(200), cl::ZeroOrMore,
  40         cl::desc("Control the amount of inlining to perform (default = 200)"));
  41
  42 Inliner::Inliner(void *ID)
  43   : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {}
  44
  45 Inliner::Inliner(void *ID, int Threshold)
  46   : CallGraphSCCPass(ID), InlineThreshold(Threshold) {}
  47
  48 /// getAnalysisUsage - For this class, we declare that we require and preserve
  49 /// the call graph.  If the derived class implements this method, it should
  50 /// always explicitly call the implementation here.
  51 void Inliner::getAnalysisUsage(AnalysisUsage &Info) const {
  52   CallGraphSCCPass::getAnalysisUsage(Info);
  53 }
  54
  55
  56 typedef DenseMap<const ArrayType*, std::vector<AllocaInst*> >
  57 InlinedArrayAllocasTy;
  58
  59 /// InlineCallIfPossible - If it is possible to inline the specified call site,
  60 /// do so and update the CallGraph for this operation.
  61 ///
  62 /// This function also does some basic book-keeping to update the IR.  The
  63 /// InlinedArrayAllocas map keeps track of any
  64 static bool InlineCallIfPossible(CallSite CS, CallGraph &CG,
  65                                  const TargetData *TD,
  66                                  InlinedArrayAllocasTy &InlinedArrayAllocas) {
  67   Function *Callee = CS.getCalledFunction();
  68   Function *Caller = CS.getCaller();
  69
  70   // Try to inline the function.  Get the list of static allocas that were
  71   // inlined.
  72   SmallVector<AllocaInst*, 16> StaticAllocas;
  73   if (!InlineFunction(CS, &CG, TD, &StaticAllocas))
  74     return false;
  75
  76   // If the inlined function had a higher stack protection level than the
  77   // calling function, then bump up the caller's stack protection level.
  78   if (Callee->hasFnAttr(Attribute::StackProtectReq))
  79     Caller->addFnAttr(Attribute::StackProtectReq);
  80   else if (Callee->hasFnAttr(Attribute::StackProtect) &&
  81            !Caller->hasFnAttr(Attribute::StackProtectReq))
  82     Caller->addFnAttr(Attribute::StackProtect);
  83
  84
  85   // Look at all of the allocas that we inlined through this call site.  If we
  86   // have already inlined other allocas through other calls into this function,
  87   // then we know that they have disjoint lifetimes and that we can merge them.
  88   //
  89   // There are many heuristics possible for merging these allocas, and the
  90   // different options have different tradeoffs.  One thing that we *really*
  91   // don't want to hurt is SRoA: once inlining happens, often allocas are no
  92   // longer address taken and so they can be promoted.
  93   //
  94   // Our "solution" for that is to only merge allocas whose outermost type is an
  95   // array type.  These are usually not promoted because someone is using a
  96   // variable index into them.  These are also often the most important ones to
  97   // merge.
  98   //
  99   // A better solution would be to have real memory lifetime markers in the IR
 100   // and not have the inliner do any merging of allocas at all.  This would
 101   // allow the backend to do proper stack slot coloring of all allocas that
 102   // *actually make it to the backend*, which is really what we want.
 103   //
 104   // Because we don't have this information, we do this simple and useful hack.
 105   //
 106   SmallPtrSet<AllocaInst*, 16> UsedAllocas;
 107
 108   // Loop over all the allocas we have so far and see if they can be merged with
 109   // a previously inlined alloca.  If not, remember that we had it.
 110   for (unsigned AllocaNo = 0, e = StaticAllocas.size();
 111        AllocaNo != e; ++AllocaNo) {
 112     AllocaInst *AI = StaticAllocas[AllocaNo];
 113
 114     // Don't bother trying to merge array allocations (they will usually be
 115     // canonicalized to be an allocation *of* an array), or allocations whose
 116     // type is not itself an array (because we're afraid of pessimizing SRoA).
 117     const ArrayType *ATy = dyn_cast<ArrayType>(AI->getAllocatedType());
 118     if (ATy == 0 || AI->isArrayAllocation())
 119       continue;
 120
 121     // Get the list of all available allocas for this array type.
 122     std::vector<AllocaInst*> &AllocasForType = InlinedArrayAllocas[ATy];
 123
 124     // Loop over the allocas in AllocasForType to see if we can reuse one.  Note
 125     // that we have to be careful not to reuse the same "available" alloca for
 126     // multiple different allocas that we just inlined, we use the 'UsedAllocas'
 127     // set to keep track of which "available" allocas are being used by this
 128     // function.  Also, AllocasForType can be empty of course!
 129     bool MergedAwayAlloca = false;
 130     for (unsigned i = 0, e = AllocasForType.size(); i != e; ++i) {
 131       AllocaInst *AvailableAlloca = AllocasForType[i];
 132
 133       // The available alloca has to be in the right function, not in some other
 134       // function in this SCC.
 135       if (AvailableAlloca->getParent() != AI->getParent())
 136         continue;
 137
 138       // If the inlined function already uses this alloca then we can't reuse
 139       // it.
 140       if (!UsedAllocas.insert(AvailableAlloca))
 141         continue;
 142
 143       // Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare
 144       // success!
 145       DEBUG(errs() << "    ***MERGED ALLOCA: " << *AI);
 146
 147       AI->replaceAllUsesWith(AvailableAlloca);
 148       AI->eraseFromParent();
 149       MergedAwayAlloca = true;
 150       ++NumMergedAllocas;
 151       break;
 152     }
 153
 154     // If we already nuked the alloca, we're done with it.
 155     if (MergedAwayAlloca)
 156       continue;
 157
 158     // If we were unable to merge away the alloca either because there are no
 159     // allocas of the right type available or because we reused them all
 160     // already, remember that this alloca came from an inlined function and mark
 161     // it used so we don't reuse it for other allocas from this inline
 162     // operation.
 163     AllocasForType.push_back(AI);
 164     UsedAllocas.insert(AI);
 165   }
 166
 167   return true;
 168 }
 169
 170 /// shouldInline - Return true if the inliner should attempt to inline
 171 /// at the given CallSite.
 172 bool Inliner::shouldInline(CallSite CS) {
 173   InlineCost IC = getInlineCost(CS);
 174
 175   if (IC.isAlways()) {
 176     DEBUG(errs() << "    Inlining: cost=always"
 177           << ", Call: " << *CS.getInstruction() << "\n");
 178     return true;
 179   }
 180
 181   if (IC.isNever()) {
 182     DEBUG(errs() << "    NOT Inlining: cost=never"
 183           << ", Call: " << *CS.getInstruction() << "\n");
 184     return false;
 185   }
 186
 187   int Cost = IC.getValue();
 188   int CurrentThreshold = InlineThreshold;
 189   Function *Fn = CS.getCaller();
 190   if (Fn && !Fn->isDeclaration() &&
 191       Fn->hasFnAttr(Attribute::OptimizeForSize) &&
 192       InlineThreshold != 50)
 193     CurrentThreshold = 50;
 194
 195   float FudgeFactor = getInlineFudgeFactor(CS);
 196   if (Cost >= (int)(CurrentThreshold * FudgeFactor)) {
 197     DEBUG(errs() << "    NOT Inlining: cost=" << Cost
 198           << ", Call: " << *CS.getInstruction() << "\n");
 199     return false;
 200   }
 201
 202   DEBUG(errs() << "    Inlining: cost=" << Cost
 203         << ", Call: " << *CS.getInstruction() << "\n");
 204   return true;
 205 }
 206
 207 bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
 208   CallGraph &CG = getAnalysis<CallGraph>();
 209   const TargetData *TD = getAnalysisIfAvailable<TargetData>();
 210
 211   SmallPtrSet<Function*, 8> SCCFunctions;
 212   DEBUG(errs() << "Inliner visiting SCC:");
 213   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
 214     Function *F = SCC[i]->getFunction();
 215     if (F) SCCFunctions.insert(F);
 216     DEBUG(errs() << " " << (F ? F->getName() : "INDIRECTNODE"));
 217   }
 218
 219   // Scan through and identify all call sites ahead of time so that we only
 220   // inline call sites in the original functions, not call sites that result
 221   // from inlining other functions.
 222   SmallVector<CallSite, 16> CallSites;
 223
 224   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
 225     Function *F = SCC[i]->getFunction();
 226     if (!F) continue;
 227
 228     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 229       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 230         CallSite CS = CallSite::get(I);
 231         if (CS.getInstruction() == 0 || isa<DbgInfoIntrinsic>(I))
 232           continue;
 233
 234         if (CS.getCalledFunction() == 0 ||
 235             !CS.getCalledFunction()->isDeclaration())
 236           CallSites.push_back(CS);
 237       }
 238   }
 239
 240   DEBUG(errs() << ": " << CallSites.size() << " call sites.\n");
 241
 242   // Now that we have all of the call sites, move the ones to functions in the
 243   // current SCC to the end of the list.
 244   unsigned FirstCallInSCC = CallSites.size();
 245   for (unsigned i = 0; i < FirstCallInSCC; ++i)
 246     if (Function *F = CallSites[i].getCalledFunction())
 247       if (SCCFunctions.count(F))
 248         std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
 249
 250
 251   InlinedArrayAllocasTy InlinedArrayAllocas;
 252
 253   // Now that we have all of the call sites, loop over them and inline them if
 254   // it looks profitable to do so.
 255   bool Changed = false;
 256   bool LocalChange;
 257   do {
 258     LocalChange = false;
 259     // Iterate over the outer loop because inlining functions can cause indirect
 260     // calls to become direct calls.
 261     for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
 262       // We can only inline direct calls.
 263       CallSite CS = CallSites[CSi];
 264
 265       Function *Callee = CS.getCalledFunction();
 266       if (!Callee) continue;
 267
 268       // Calls to external functions are never inlinable.
 269       if (Callee->isDeclaration()) {
 270         if (SCC.size() == 1) {
 271           std::swap(CallSites[CSi], CallSites.back());
 272           CallSites.pop_back();
 273         } else {
 274           // Keep the 'in SCC / not in SCC' boundary correct.
 275           CallSites.erase(CallSites.begin()+CSi);
 276         }
 277         --CSi;
 278         continue;
 279       }
 280
 281       // If the policy determines that we should inline this function,
 282       // try to do so.
 283       if (!shouldInline(CS))
 284         continue;
 285
 286       Function *Caller = CS.getCaller();
 287       // Attempt to inline the function...
 288       if (!InlineCallIfPossible(CS, CG, TD, InlinedArrayAllocas))
 289         continue;
 290
 291       // If we inlined the last possible call site to the function, delete the
 292       // function body now.
 293       if (Callee->use_empty() &&
 294           (Callee->hasLocalLinkage() ||
 295            Callee->hasAvailableExternallyLinkage()) &&
 296           !SCCFunctions.count(Callee)) {
 297         DEBUG(errs() << "    -> Deleting dead function: "
 298               << Callee->getName() << "\n");
 299         CallGraphNode *CalleeNode = CG[Callee];
 300
 301         // Remove any call graph edges from the callee to its callees.
 302         CalleeNode->removeAllCalledFunctions();
 303
 304         resetCachedCostInfo(Callee);
 305
 306         // Removing the node for callee from the call graph and delete it.
 307         delete CG.removeFunctionFromModule(CalleeNode);
 308         ++NumDeleted;
 309       }
 310
 311       // Remove any cached cost info for this caller, as inlining the
 312       // callee has increased the size of the caller (which may be the
 313       // same as the callee).
 314       resetCachedCostInfo(Caller);
 315
 316       // Remove this call site from the list.  If possible, use
 317       // swap/pop_back for efficiency, but do not use it if doing so would
 318       // move a call site to a function in this SCC before the
 319       // 'FirstCallInSCC' barrier.
 320       if (SCC.size() == 1) {
 321         std::swap(CallSites[CSi], CallSites.back());
 322         CallSites.pop_back();
 323       } else {
 324         CallSites.erase(CallSites.begin()+CSi);
 325       }
 326       --CSi;
 327
 328       ++NumInlined;
 329       Changed = true;
 330       LocalChange = true;
 331     }
 332   } while (LocalChange);
 333
 334   return Changed;
 335 }
 336
 337 // doFinalization - Remove now-dead linkonce functions at the end of
 338 // processing to avoid breaking the SCC traversal.
 339 bool Inliner::doFinalization(CallGraph &CG) {
 340   return removeDeadFunctions(CG);
 341 }
 342
 343 /// removeDeadFunctions - Remove dead functions that are not included in
 344 /// DNR (Do Not Remove) list.
 345 bool Inliner::removeDeadFunctions(CallGraph &CG,
 346                                   SmallPtrSet<const Function *, 16> *DNR) {
 347   SmallPtrSet<CallGraphNode*, 16> FunctionsToRemove;
 348
 349   // Scan for all of the functions, looking for ones that should now be removed
 350   // from the program.  Insert the dead ones in the FunctionsToRemove set.
 351   for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
 352     CallGraphNode *CGN = I->second;
 353     if (CGN == 0 || CGN->getFunction() == 0)
 354       continue;
 355
 356     Function *F = CGN->getFunction();
 357
 358     // If the only remaining users of the function are dead constants, remove
 359     // them.
 360     F->removeDeadConstantUsers();
 361
 362     if (DNR && DNR->count(F))
 363       continue;
 364     if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage())
 365       continue;
 366     if (!F->use_empty())
 367       continue;
 368
 369     // Remove any call graph edges from the function to its callees.
 370     CGN->removeAllCalledFunctions();
 371
 372     // Remove any edges from the external node to the function's call graph
 373     // node.  These edges might have been made irrelegant due to
 374     // optimization of the program.
 375     CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
 376
 377     // Removing the node for callee from the call graph and delete it.
 378     FunctionsToRemove.insert(CGN);
 379   }
 380
 381   // Now that we know which functions to delete, do so.  We didn't want to do
 382   // this inline, because that would invalidate our CallGraph::iterator
 383   // objects. :(
 384   //
 385   // Note that it doesn't matter that we are iterating over a non-stable set
 386   // here to do this, it doesn't matter which order the functions are deleted
 387   // in.
 388   bool Changed = false;
 389   for (SmallPtrSet<CallGraphNode*, 16>::iterator I = FunctionsToRemove.begin(),
 390        E = FunctionsToRemove.end(); I != E; ++I) {
 391     resetCachedCostInfo((*I)->getFunction());
 392     delete CG.removeFunctionFromModule(*I);
 393     ++NumDeleted;
 394     Changed = true;
 395   }
 396
 397   return Changed;
 398 }