Inliner.cpp revision 135755dae4c3fa8003b76150689d5064aa4612ee
1cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51Chris Lattner//===- Inliner.cpp - Code common to all inliners --------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// 10befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// This file implements the mechanics required to implement inlining without 11befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// missing any calls and updating the call graph. The decisions of which calls 12befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// are profitable to inline are implemented elsewhere. 13237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// 14237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner//===----------------------------------------------------------------------===// 15237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 1686453c52ba02e743d29c08456e51006500041456Chris Lattner#define DEBUG_TYPE "inline" 17237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Module.h" 1847b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 191f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen#include "llvm/IntrinsicInst.h" 20237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Analysis/CallGraph.h" 21237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Support/CallSite.h" 22ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner#include "llvm/Target/TargetData.h" 236f7426ec2e46bb19cc9f9e75f1c355b35cf12d7dTanya Lattner#include "llvm/Transforms/IPO/InlinerPass.h" 24237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 25551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 27ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 29befa499d45ffcc32bd9902518aec18589464e47cChris Lattner#include <set> 30a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattnerusing namespace llvm; 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3286453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumInlined, "Number of functions inlined"); 3386453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 3486453c52ba02e743d29c08456e51006500041456Chris Lattner 35844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> 365fee49eff92c2ae2f70eb84d136c31a706560750Dale JohannesenInlineLimit("inline-threshold", cl::Hidden, cl::init(200), cl::ZeroOrMore, 37cbfdf9644ce38fd3404469c26ac3c8466c940b6eDale Johannesen cl::desc("Control the amount of inlining to perform (default = 200)")); 38237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 39ae73dc1448d25b02cabc7c64c86c64371453dda8Dan GohmanInliner::Inliner(void *ID) 40ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {} 41237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 42ae73dc1448d25b02cabc7c64c86c64371453dda8Dan GohmanInliner::Inliner(void *ID, int Threshold) 43ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : CallGraphSCCPass(ID), InlineThreshold(Threshold) {} 44120d053e3ba810b44047fbcb719824bed5673ca9Chris Lattner 45ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// getAnalysisUsage - For this class, we declare that we require and preserve 46ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// the call graph. If the derived class implements this method, it should 47ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// always explicitly call the implementation here. 48ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattnervoid Inliner::getAnalysisUsage(AnalysisUsage &Info) const { 49ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner CallGraphSCCPass::getAnalysisUsage(Info); 50ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner} 51ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner 52befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// InlineCallIfPossible - If it is possible to inline the specified call site, 53befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// do so and update the CallGraph for this operation. 541f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesenbool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, 5516581bf931c0ccf2f8993397acfa4e1d509a68dcDale Johannesen const SmallPtrSet<Function*, 8> &SCCFunctions, 5602a436c48ecff9e34d50ce0a2f861e5acdd9bf3fDan Gohman const TargetData *TD) { 57befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *Callee = CS.getCalledFunction(); 5866c75aaa028683c389c55b377ee2411b61081677Bill Wendling Function *Caller = CS.getCaller(); 5966c75aaa028683c389c55b377ee2411b61081677Bill Wendling 6002a436c48ecff9e34d50ce0a2f861e5acdd9bf3fDan Gohman if (!InlineFunction(CS, &CG, TD)) return false; 61fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 628c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling // If the inlined function had a higher stack protection level than the 638c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling // calling function, then bump up the caller's stack protection level. 648c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling if (Callee->hasFnAttr(Attribute::StackProtectReq)) 658c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling Caller->addFnAttr(Attribute::StackProtectReq); 668c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling else if (Callee->hasFnAttr(Attribute::StackProtect) && 678c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling !Caller->hasFnAttr(Attribute::StackProtectReq)) 688c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling Caller->addFnAttr(Attribute::StackProtect); 698c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling 7054970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // If we inlined the last possible call site to the function, delete the 7154970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // function body now. 72135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (Callee->use_empty() && 73135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner (Callee->hasLocalLinkage() || Callee->hasAvailableExternallyLinkage()) && 74befa499d45ffcc32bd9902518aec18589464e47cChris Lattner !SCCFunctions.count(Callee)) { 75ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar DEBUG(errs() << " -> Deleting dead function: " 76ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << Callee->getName() << "\n"); 776f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CallGraphNode *CalleeNode = CG[Callee]; 78fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 79befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Remove any call graph edges from the callee to its callees. 806f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CalleeNode->removeAllCalledFunctions(); 81fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 821f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen resetCachedCostInfo(CalleeNode->getFunction()); 831f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen 84befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Removing the node for callee from the call graph and delete it. 85befa499d45ffcc32bd9902518aec18589464e47cChris Lattner delete CG.removeFunctionFromModule(CalleeNode); 86befa499d45ffcc32bd9902518aec18589464e47cChris Lattner ++NumDeleted; 87befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 88befa499d45ffcc32bd9902518aec18589464e47cChris Lattner return true; 89237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 901a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 911a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar/// shouldInline - Return true if the inliner should attempt to inline 921a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar/// at the given CallSite. 931a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbarbool Inliner::shouldInline(CallSite CS) { 94c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar InlineCost IC = getInlineCost(CS); 951a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 96c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar if (IC.isAlways()) { 9784a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << " Inlining: cost=always" 9884a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling << ", Call: " << *CS.getInstruction() << "\n"); 99c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar return true; 100c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar } 101c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar 102c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar if (IC.isNever()) { 10384a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << " NOT Inlining: cost=never" 10484a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling << ", Call: " << *CS.getInstruction() << "\n"); 105c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar return false; 106c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar } 107c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar 108c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar int Cost = IC.getValue(); 1091a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar int CurrentThreshold = InlineThreshold; 1101a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar Function *Fn = CS.getCaller(); 11184a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling if (Fn && !Fn->isDeclaration() && 11284a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling Fn->hasFnAttr(Attribute::OptimizeForSize) && 11384a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling InlineThreshold != 50) 1141a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar CurrentThreshold = 50; 1151a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 116135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner float FudgeFactor = getInlineFudgeFactor(CS); 1171a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar if (Cost >= (int)(CurrentThreshold * FudgeFactor)) { 11884a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << " NOT Inlining: cost=" << Cost 11984a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling << ", Call: " << *CS.getInstruction() << "\n"); 1201a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar return false; 1211a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar } 122135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 123135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner DEBUG(errs() << " Inlining: cost=" << Cost 124135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner << ", Call: " << *CS.getInstruction() << "\n"); 125135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner return true; 1261a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar} 127237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 128237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 129237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallGraph &CG = getAnalysis<CallGraph>(); 13002a436c48ecff9e34d50ce0a2f861e5acdd9bf3fDan Gohman const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 131237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 13216581bf931c0ccf2f8993397acfa4e1d509a68dcDale Johannesen SmallPtrSet<Function*, 8> SCCFunctions; 13384a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << "Inliner visiting SCC:"); 134237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 135befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *F = SCC[i]->getFunction(); 136befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (F) SCCFunctions.insert(F); 137ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar DEBUG(errs() << " " << (F ? F->getName() : "INDIRECTNODE")); 138237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 139237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 140befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Scan through and identify all call sites ahead of time so that we only 141befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // inline call sites in the original functions, not call sites that result 142befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // from inlining other functions. 143befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::vector<CallSite> CallSites; 144befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 145135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 146135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *F = SCC[i]->getFunction(); 147135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!F) continue; 148135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 149135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 150135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 151135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSite CS = CallSite::get(I); 152135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CS.getInstruction() == 0 || isa<DbgInfoIntrinsic>(I)) 153135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 154135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 155135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CS.getCalledFunction() == 0 || 156135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner !CS.getCalledFunction()->isDeclaration()) 157135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.push_back(CS); 158135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 159135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 160237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 16184a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << ": " << CallSites.size() << " call sites.\n"); 162fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 163befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, move the ones to functions in the 164befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // current SCC to the end of the list. 165befa499d45ffcc32bd9902518aec18589464e47cChris Lattner unsigned FirstCallInSCC = CallSites.size(); 166befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (unsigned i = 0; i < FirstCallInSCC; ++i) 167befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Function *F = CallSites[i].getCalledFunction()) 168befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (SCCFunctions.count(F)) 169befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); 170fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 171befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, loop over them and inline them if 172befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // it looks profitable to do so. 173befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool Changed = false; 174befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool LocalChange; 175befa499d45ffcc32bd9902518aec18589464e47cChris Lattner do { 176befa499d45ffcc32bd9902518aec18589464e47cChris Lattner LocalChange = false; 177befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Iterate over the outer loop because inlining functions can cause indirect 178befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // calls to become direct calls. 179135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) { 180135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // We can only inline direct calls. 181135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *Callee = CallSites[CSi].getCalledFunction(); 182135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!Callee) continue; 183135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 184135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Calls to external functions are never inlinable. 185135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (Callee->isDeclaration()) { 186135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (SCC.size() == 1) { 187135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner std::swap(CallSites[CSi], CallSites.back()); 188135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.pop_back(); 189135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } else { 190135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Keep the 'in SCC / not in SCC' boundary correct. 191135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.erase(CallSites.begin()+CSi); 192befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 193135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner --CSi; 194135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 195135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 196befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 197135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If the policy determines that we should inline this function, 198135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // try to do so. 199135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSite CS = CallSites[CSi]; 200135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!shouldInline(CS)) 201135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 202135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 203135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *Caller = CS.getCaller(); 204135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Attempt to inline the function... 205135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!InlineCallIfPossible(CS, CG, SCCFunctions, TD)) 206135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 207135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 208135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove any cached cost info for this caller, as inlining the 209135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // callee has increased the size of the caller (which may be the 210135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // same as the callee). 211135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner resetCachedCostInfo(Caller); 212135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 213135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove this call site from the list. If possible, use 214135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // swap/pop_back for efficiency, but do not use it if doing so would 215135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // move a call site to a function in this SCC before the 216135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // 'FirstCallInSCC' barrier. 217135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (SCC.size() == 1) { 218135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner std::swap(CallSites[CSi], CallSites.back()); 219135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.pop_back(); 220135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } else { 221135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.erase(CallSites.begin()+CSi); 222237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 223135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner --CSi; 224135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 225135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner ++NumInlined; 226135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Changed = true; 227135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner LocalChange = true; 228135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 229befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } while (LocalChange); 230237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 231775cbdd51a3b33dd5eb343689f65ab5cc8ac7118Chris Lattner return Changed; 232237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 233d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 23468d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// doFinalization - Remove now-dead linkonce functions at the end of 23568d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// processing to avoid breaking the SCC traversal. 23668d57e7ae80044401efd889270a12c71b3efb9abChris Lattnerbool Inliner::doFinalization(CallGraph &CG) { 237b7c6bf1e073088635951435acedff793add1cefdDevang Patel return removeDeadFunctions(CG); 238b7c6bf1e073088635951435acedff793add1cefdDevang Patel} 239b7c6bf1e073088635951435acedff793add1cefdDevang Patel 240135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// removeDeadFunctions - Remove dead functions that are not included in 241135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// DNR (Do Not Remove) list. 242b7c6bf1e073088635951435acedff793add1cefdDevang Patelbool Inliner::removeDeadFunctions(CallGraph &CG, 243135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner SmallPtrSet<const Function *, 16> *DNR) { 244135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner SmallPtrSet<CallGraphNode*, 16> FunctionsToRemove; 2453e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 2463e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Scan for all of the functions, looking for ones that should now be removed 2473e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // from the program. Insert the dead ones in the FunctionsToRemove set. 2483e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 2493e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner CallGraphNode *CGN = I->second; 250135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CGN == 0 || CGN->getFunction() == 0) 251135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 252135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 253135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *F = CGN->getFunction(); 254135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 255135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If the only remaining users of the function are dead constants, remove 256135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // them. 257135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner F->removeDeadConstantUsers(); 258135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 259135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (DNR && DNR->count(F)) 260135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 261135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage()) 262135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 263135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!F->use_empty()) 264135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 265135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 266135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove any call graph edges from the function to its callees. 267135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CGN->removeAllCalledFunctions(); 268135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 269135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove any edges from the external node to the function's call graph 270135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // node. These edges might have been made irrelegant due to 271135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // optimization of the program. 272135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 273fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 274135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Removing the node for callee from the call graph and delete it. 275135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner FunctionsToRemove.insert(CGN); 27668d57e7ae80044401efd889270a12c71b3efb9abChris Lattner } 2773e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 2783e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Now that we know which functions to delete, do so. We didn't want to do 2793e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // this inline, because that would invalidate our CallGraph::iterator 2803e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // objects. :( 281135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // 282135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Note that it doesn't matter that we are iterating over a non-stable set 283135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // here to do this, it doesn't matter which order the functions are deleted 284135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // in. 2853e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner bool Changed = false; 286135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (SmallPtrSet<CallGraphNode*, 16>::iterator I = FunctionsToRemove.begin(), 287135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner E = FunctionsToRemove.end(); I != E; ++I) { 2881f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen resetCachedCostInfo((*I)->getFunction()); 2893e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner delete CG.removeFunctionFromModule(*I); 2903e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner ++NumDeleted; 2913e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner Changed = true; 2923e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner } 2933e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 29468d57e7ae80044401efd889270a12c71b3efb9abChris Lattner return Changed; 29568d57e7ae80044401efd889270a12c71b3efb9abChris Lattner} 296