Inliner.cpp revision 12f0babca4459c253675700e1d707652d5b6ba17
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" 2412f0babca4459c253675700e1d707652d5b6ba17Chris Lattner#include "llvm/Transforms/Utils/InlineCost.h" 25237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 27551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 28ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 2912f0babca4459c253675700e1d707652d5b6ba17Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 31befa499d45ffcc32bd9902518aec18589464e47cChris Lattner#include <set> 32a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattnerusing namespace llvm; 33d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3486453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumInlined, "Number of functions inlined"); 3586453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 3686453c52ba02e743d29c08456e51006500041456Chris Lattner 37844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> 385fee49eff92c2ae2f70eb84d136c31a706560750Dale JohannesenInlineLimit("inline-threshold", cl::Hidden, cl::init(200), cl::ZeroOrMore, 39cbfdf9644ce38fd3404469c26ac3c8466c940b6eDale Johannesen cl::desc("Control the amount of inlining to perform (default = 200)")); 40237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 41ae73dc1448d25b02cabc7c64c86c64371453dda8Dan GohmanInliner::Inliner(void *ID) 42ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {} 43237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 44ae73dc1448d25b02cabc7c64c86c64371453dda8Dan GohmanInliner::Inliner(void *ID, int Threshold) 45ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : CallGraphSCCPass(ID), InlineThreshold(Threshold) {} 46120d053e3ba810b44047fbcb719824bed5673ca9Chris Lattner 47ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// getAnalysisUsage - For this class, we declare that we require and preserve 48ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// the call graph. If the derived class implements this method, it should 49ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// always explicitly call the implementation here. 50ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattnervoid Inliner::getAnalysisUsage(AnalysisUsage &Info) const { 51ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner CallGraphSCCPass::getAnalysisUsage(Info); 52ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner} 53ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner 54befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// InlineCallIfPossible - If it is possible to inline the specified call site, 55befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// do so and update the CallGraph for this operation. 561f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesenbool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, 5716581bf931c0ccf2f8993397acfa4e1d509a68dcDale Johannesen const SmallPtrSet<Function*, 8> &SCCFunctions, 5802a436c48ecff9e34d50ce0a2f861e5acdd9bf3fDan Gohman const TargetData *TD) { 59befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *Callee = CS.getCalledFunction(); 6066c75aaa028683c389c55b377ee2411b61081677Bill Wendling Function *Caller = CS.getCaller(); 6166c75aaa028683c389c55b377ee2411b61081677Bill Wendling 6212f0babca4459c253675700e1d707652d5b6ba17Chris Lattner if (!InlineFunction(CS, &CG, TD)) 6312f0babca4459c253675700e1d707652d5b6ba17Chris Lattner return false; 64fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 658c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling // If the inlined function had a higher stack protection level than the 668c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling // calling function, then bump up the caller's stack protection level. 678c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling if (Callee->hasFnAttr(Attribute::StackProtectReq)) 688c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling Caller->addFnAttr(Attribute::StackProtectReq); 698c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling else if (Callee->hasFnAttr(Attribute::StackProtect) && 708c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling !Caller->hasFnAttr(Attribute::StackProtectReq)) 718c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling Caller->addFnAttr(Attribute::StackProtect); 728c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling 7354970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // If we inlined the last possible call site to the function, delete the 7454970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // function body now. 75135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (Callee->use_empty() && 76135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner (Callee->hasLocalLinkage() || Callee->hasAvailableExternallyLinkage()) && 77befa499d45ffcc32bd9902518aec18589464e47cChris Lattner !SCCFunctions.count(Callee)) { 78ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar DEBUG(errs() << " -> Deleting dead function: " 79ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << Callee->getName() << "\n"); 806f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CallGraphNode *CalleeNode = CG[Callee]; 81fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 82befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Remove any call graph edges from the callee to its callees. 836f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CalleeNode->removeAllCalledFunctions(); 84fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 851f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen resetCachedCostInfo(CalleeNode->getFunction()); 861f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen 87befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Removing the node for callee from the call graph and delete it. 88befa499d45ffcc32bd9902518aec18589464e47cChris Lattner delete CG.removeFunctionFromModule(CalleeNode); 89befa499d45ffcc32bd9902518aec18589464e47cChris Lattner ++NumDeleted; 90befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 91befa499d45ffcc32bd9902518aec18589464e47cChris Lattner return true; 92237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 931a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 941a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar/// shouldInline - Return true if the inliner should attempt to inline 951a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar/// at the given CallSite. 961a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbarbool Inliner::shouldInline(CallSite CS) { 97c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar InlineCost IC = getInlineCost(CS); 981a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 99c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar if (IC.isAlways()) { 10084a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << " Inlining: cost=always" 10184a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling << ", Call: " << *CS.getInstruction() << "\n"); 102c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar return true; 103c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar } 104c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar 105c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar if (IC.isNever()) { 10684a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << " NOT Inlining: cost=never" 10784a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling << ", Call: " << *CS.getInstruction() << "\n"); 108c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar return false; 109c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar } 110c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar 111c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar int Cost = IC.getValue(); 1121a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar int CurrentThreshold = InlineThreshold; 1131a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar Function *Fn = CS.getCaller(); 11484a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling if (Fn && !Fn->isDeclaration() && 11584a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling Fn->hasFnAttr(Attribute::OptimizeForSize) && 11684a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling InlineThreshold != 50) 1171a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar CurrentThreshold = 50; 1181a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 119135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner float FudgeFactor = getInlineFudgeFactor(CS); 1201a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar if (Cost >= (int)(CurrentThreshold * FudgeFactor)) { 12184a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << " NOT Inlining: cost=" << Cost 12284a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling << ", Call: " << *CS.getInstruction() << "\n"); 1231a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar return false; 1241a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar } 125135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 126135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner DEBUG(errs() << " Inlining: cost=" << Cost 127135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner << ", Call: " << *CS.getInstruction() << "\n"); 128135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner return true; 1291a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar} 130237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 131237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 132237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallGraph &CG = getAnalysis<CallGraph>(); 13302a436c48ecff9e34d50ce0a2f861e5acdd9bf3fDan Gohman const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 134237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 13516581bf931c0ccf2f8993397acfa4e1d509a68dcDale Johannesen SmallPtrSet<Function*, 8> SCCFunctions; 13684a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << "Inliner visiting SCC:"); 137237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 138befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *F = SCC[i]->getFunction(); 139befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (F) SCCFunctions.insert(F); 140ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar DEBUG(errs() << " " << (F ? F->getName() : "INDIRECTNODE")); 141237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 142237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 143befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Scan through and identify all call sites ahead of time so that we only 144befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // inline call sites in the original functions, not call sites that result 145befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // from inlining other functions. 146befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::vector<CallSite> CallSites; 147befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 148135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 149135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *F = SCC[i]->getFunction(); 150135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!F) continue; 151135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 152135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 153135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 154135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSite CS = CallSite::get(I); 155135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CS.getInstruction() == 0 || isa<DbgInfoIntrinsic>(I)) 156135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 157135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 158135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CS.getCalledFunction() == 0 || 159135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner !CS.getCalledFunction()->isDeclaration()) 160135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.push_back(CS); 161135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 162135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 163237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 16484a832f9272ed7f1a47c3e019c770b62e373cc6cBill Wendling DEBUG(errs() << ": " << CallSites.size() << " call sites.\n"); 165fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 166befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, move the ones to functions in the 167befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // current SCC to the end of the list. 168befa499d45ffcc32bd9902518aec18589464e47cChris Lattner unsigned FirstCallInSCC = CallSites.size(); 169befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (unsigned i = 0; i < FirstCallInSCC; ++i) 170befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Function *F = CallSites[i].getCalledFunction()) 171befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (SCCFunctions.count(F)) 172befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); 173fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 174befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, loop over them and inline them if 175befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // it looks profitable to do so. 176befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool Changed = false; 177befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool LocalChange; 178befa499d45ffcc32bd9902518aec18589464e47cChris Lattner do { 179befa499d45ffcc32bd9902518aec18589464e47cChris Lattner LocalChange = false; 180befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Iterate over the outer loop because inlining functions can cause indirect 181befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // calls to become direct calls. 182135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) { 183135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // We can only inline direct calls. 184135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *Callee = CallSites[CSi].getCalledFunction(); 185135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!Callee) continue; 186135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 187135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Calls to external functions are never inlinable. 188135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (Callee->isDeclaration()) { 189135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (SCC.size() == 1) { 190135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner std::swap(CallSites[CSi], CallSites.back()); 191135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.pop_back(); 192135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } else { 193135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Keep the 'in SCC / not in SCC' boundary correct. 194135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.erase(CallSites.begin()+CSi); 195befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 196135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner --CSi; 197135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 198135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 199befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 200135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If the policy determines that we should inline this function, 201135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // try to do so. 202135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSite CS = CallSites[CSi]; 203135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!shouldInline(CS)) 204135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 205135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 206135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *Caller = CS.getCaller(); 207135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Attempt to inline the function... 208135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!InlineCallIfPossible(CS, CG, SCCFunctions, TD)) 209135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 210135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 211135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove any cached cost info for this caller, as inlining the 212135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // callee has increased the size of the caller (which may be the 213135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // same as the callee). 214135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner resetCachedCostInfo(Caller); 215135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 216135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove this call site from the list. If possible, use 217135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // swap/pop_back for efficiency, but do not use it if doing so would 218135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // move a call site to a function in this SCC before the 219135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // 'FirstCallInSCC' barrier. 220135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (SCC.size() == 1) { 221135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner std::swap(CallSites[CSi], CallSites.back()); 222135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.pop_back(); 223135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } else { 224135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallSites.erase(CallSites.begin()+CSi); 225237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 226135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner --CSi; 227135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 228135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner ++NumInlined; 229135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Changed = true; 230135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner LocalChange = true; 231135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 232befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } while (LocalChange); 233237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 234775cbdd51a3b33dd5eb343689f65ab5cc8ac7118Chris Lattner return Changed; 235237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 236d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 23768d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// doFinalization - Remove now-dead linkonce functions at the end of 23868d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// processing to avoid breaking the SCC traversal. 23968d57e7ae80044401efd889270a12c71b3efb9abChris Lattnerbool Inliner::doFinalization(CallGraph &CG) { 240b7c6bf1e073088635951435acedff793add1cefdDevang Patel return removeDeadFunctions(CG); 241b7c6bf1e073088635951435acedff793add1cefdDevang Patel} 242b7c6bf1e073088635951435acedff793add1cefdDevang Patel 243135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// removeDeadFunctions - Remove dead functions that are not included in 244135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// DNR (Do Not Remove) list. 245b7c6bf1e073088635951435acedff793add1cefdDevang Patelbool Inliner::removeDeadFunctions(CallGraph &CG, 246135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner SmallPtrSet<const Function *, 16> *DNR) { 247135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner SmallPtrSet<CallGraphNode*, 16> FunctionsToRemove; 2483e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 2493e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Scan for all of the functions, looking for ones that should now be removed 2503e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // from the program. Insert the dead ones in the FunctionsToRemove set. 2513e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 2523e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner CallGraphNode *CGN = I->second; 253135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CGN == 0 || CGN->getFunction() == 0) 254135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 255135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 256135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Function *F = CGN->getFunction(); 257135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 258135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If the only remaining users of the function are dead constants, remove 259135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // them. 260135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner F->removeDeadConstantUsers(); 261135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 262135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (DNR && DNR->count(F)) 263135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 264135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage()) 265135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 266135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!F->use_empty()) 267135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 268135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 269135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove any call graph edges from the function to its callees. 270135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CGN->removeAllCalledFunctions(); 271135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 272135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Remove any edges from the external node to the function's call graph 273135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // node. These edges might have been made irrelegant due to 274135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // optimization of the program. 275135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 276fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 277135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Removing the node for callee from the call graph and delete it. 278135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner FunctionsToRemove.insert(CGN); 27968d57e7ae80044401efd889270a12c71b3efb9abChris Lattner } 2803e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 2813e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Now that we know which functions to delete, do so. We didn't want to do 2823e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // this inline, because that would invalidate our CallGraph::iterator 2833e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // objects. :( 284135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // 285135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Note that it doesn't matter that we are iterating over a non-stable set 286135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // here to do this, it doesn't matter which order the functions are deleted 287135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // in. 2883e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner bool Changed = false; 289135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (SmallPtrSet<CallGraphNode*, 16>::iterator I = FunctionsToRemove.begin(), 290135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner E = FunctionsToRemove.end(); I != E; ++I) { 2911f67ce4aa3f65619f54c8a3072539da5b0022841Dale Johannesen resetCachedCostInfo((*I)->getFunction()); 2923e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner delete CG.removeFunctionFromModule(*I); 2933e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner ++NumDeleted; 2943e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner Changed = true; 2953e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner } 2963e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 29768d57e7ae80044401efd889270a12c71b3efb9abChris Lattner return Changed; 29868d57e7ae80044401efd889270a12c71b3efb9abChris Lattner} 299