Inliner.cpp revision e345566f8eaeeda45e29e3709114a42209a360cc
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" 19237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Analysis/CallGraph.h" 20237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Support/CallSite.h" 21ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner#include "llvm/Target/TargetData.h" 226f7426ec2e46bb19cc9f9e75f1c355b35cf12d7dTanya Lattner#include "llvm/Transforms/IPO/InlinerPass.h" 23237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 24551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 25551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 27befa499d45ffcc32bd9902518aec18589464e47cChris Lattner#include <set> 28a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattnerusing namespace llvm; 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3086453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumInlined, "Number of functions inlined"); 3186453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 3286453c52ba02e743d29c08456e51006500041456Chris Lattner 33844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> 34844731a7f1909f55935e3514c9e713a62d67662eDan GohmanInlineLimit("inline-threshold", cl::Hidden, cl::init(200), 357c3becd9d729b976d79b18e6165e74390e613bb5Evan Cheng cl::desc("Control the amount of inlining to perform (default = 200)")); 36237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 37ae73dc1448d25b02cabc7c64c86c64371453dda8Dan GohmanInliner::Inliner(void *ID) 38ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {} 39237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 40ae73dc1448d25b02cabc7c64c86c64371453dda8Dan GohmanInliner::Inliner(void *ID, int Threshold) 41ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman : CallGraphSCCPass(ID), InlineThreshold(Threshold) {} 42120d053e3ba810b44047fbcb719824bed5673ca9Chris Lattner 43ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// getAnalysisUsage - For this class, we declare that we require and preserve 44ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// the call graph. If the derived class implements this method, it should 45ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner/// always explicitly call the implementation here. 46ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattnervoid Inliner::getAnalysisUsage(AnalysisUsage &Info) const { 47ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner Info.addRequired<TargetData>(); 48ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner CallGraphSCCPass::getAnalysisUsage(Info); 49ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner} 50ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner 51befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// InlineCallIfPossible - If it is possible to inline the specified call site, 52befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// do so and update the CallGraph for this operation. 53befa499d45ffcc32bd9902518aec18589464e47cChris Lattnerstatic bool InlineCallIfPossible(CallSite CS, CallGraph &CG, 54ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner const std::set<Function*> &SCCFunctions, 55ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner const TargetData &TD) { 56befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *Callee = CS.getCalledFunction(); 5766c75aaa028683c389c55b377ee2411b61081677Bill Wendling Function *Caller = CS.getCaller(); 5866c75aaa028683c389c55b377ee2411b61081677Bill Wendling 59ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner if (!InlineFunction(CS, &CG, &TD)) return false; 60fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 618c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling // If the inlined function had a higher stack protection level than the 628c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling // calling function, then bump up the caller's stack protection level. 638c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling if (Callee->hasFnAttr(Attribute::StackProtectReq)) 648c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling Caller->addFnAttr(Attribute::StackProtectReq); 658c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling else if (Callee->hasFnAttr(Attribute::StackProtect) && 668c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling !Caller->hasFnAttr(Attribute::StackProtectReq)) 678c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling Caller->addFnAttr(Attribute::StackProtect); 688c1604e7d617622cb391f1c679ddf70ea03baedcBill Wendling 6954970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // If we inlined the last possible call site to the function, delete the 7054970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // function body now. 71befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Callee->use_empty() && Callee->hasInternalLinkage() && 72befa499d45ffcc32bd9902518aec18589464e47cChris Lattner !SCCFunctions.count(Callee)) { 730a81aac4b46eed130d20714af5a1c01b05d0275eBill Wendling DOUT << " -> Deleting dead function: " << Callee->getName() << "\n"; 746f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CallGraphNode *CalleeNode = CG[Callee]; 75fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 76befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Remove any call graph edges from the callee to its callees. 776f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CalleeNode->removeAllCalledFunctions(); 78fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 79befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Removing the node for callee from the call graph and delete it. 80befa499d45ffcc32bd9902518aec18589464e47cChris Lattner delete CG.removeFunctionFromModule(CalleeNode); 81befa499d45ffcc32bd9902518aec18589464e47cChris Lattner ++NumDeleted; 82befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 83befa499d45ffcc32bd9902518aec18589464e47cChris Lattner return true; 84237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 851a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 861a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar/// shouldInline - Return true if the inliner should attempt to inline 871a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar/// at the given CallSite. 881a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbarbool Inliner::shouldInline(CallSite CS) { 89c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar InlineCost IC = getInlineCost(CS); 901a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar float FudgeFactor = getInlineFudgeFactor(CS); 911a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 92c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar if (IC.isAlways()) { 93c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar DOUT << " Inlining: cost=always" 94c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar << ", Call: " << *CS.getInstruction(); 95c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar return true; 96c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar } 97c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar 98c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar if (IC.isNever()) { 99c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar DOUT << " NOT Inlining: cost=never" 100c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar << ", Call: " << *CS.getInstruction(); 101c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar return false; 102c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar } 103c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar 104c5e1ec47c719806fcc882470595960512edc7441Daniel Dunbar int Cost = IC.getValue(); 1051a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar int CurrentThreshold = InlineThreshold; 1061a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar Function *Fn = CS.getCaller(); 1071a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar if (Fn && !Fn->isDeclaration() 1081a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar && Fn->hasFnAttr(Attribute::OptimizeForSize) 1091a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar && InlineThreshold != 50) { 1101a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar CurrentThreshold = 50; 1111a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar } 1121a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar 1131a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar if (Cost >= (int)(CurrentThreshold * FudgeFactor)) { 1141a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar DOUT << " NOT Inlining: cost=" << Cost 1151a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar << ", Call: " << *CS.getInstruction(); 1161a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar return false; 1171a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar } else { 1181a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar DOUT << " Inlining: cost=" << Cost 1191a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar << ", Call: " << *CS.getInstruction(); 1201a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar return true; 1211a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar } 1221a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar} 123237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 124237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 125237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallGraph &CG = getAnalysis<CallGraph>(); 126237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 127237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner std::set<Function*> SCCFunctions; 1280a81aac4b46eed130d20714af5a1c01b05d0275eBill Wendling DOUT << "Inliner visiting SCC:"; 129237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 130befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *F = SCC[i]->getFunction(); 131befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (F) SCCFunctions.insert(F); 1320a81aac4b46eed130d20714af5a1c01b05d0275eBill Wendling DOUT << " " << (F ? F->getName() : "INDIRECTNODE"); 133237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 134237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 135befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Scan through and identify all call sites ahead of time so that we only 136befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // inline call sites in the original functions, not call sites that result 137befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // from inlining other functions. 138befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::vector<CallSite> CallSites; 139befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 140cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51Chris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) 141cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51Chris Lattner if (Function *F = SCC[i]->getFunction()) 142befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 143befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 144befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSite CS = CallSite::get(I); 145befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (CS.getInstruction() && (!CS.getCalledFunction() || 1465cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer !CS.getCalledFunction()->isDeclaration())) 147befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSites.push_back(CS); 148befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 149237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 1500a81aac4b46eed130d20714af5a1c01b05d0275eBill Wendling DOUT << ": " << CallSites.size() << " call sites.\n"; 151fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 152befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, move the ones to functions in the 153befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // current SCC to the end of the list. 154befa499d45ffcc32bd9902518aec18589464e47cChris Lattner unsigned FirstCallInSCC = CallSites.size(); 155befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (unsigned i = 0; i < FirstCallInSCC; ++i) 156befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Function *F = CallSites[i].getCalledFunction()) 157befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (SCCFunctions.count(F)) 158befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); 159fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 160befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, loop over them and inline them if 161befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // it looks profitable to do so. 162befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool Changed = false; 163befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool LocalChange; 164befa499d45ffcc32bd9902518aec18589464e47cChris Lattner do { 165befa499d45ffcc32bd9902518aec18589464e47cChris Lattner LocalChange = false; 166befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Iterate over the outer loop because inlining functions can cause indirect 167befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // calls to become direct calls. 168befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) 169befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Function *Callee = CallSites[CSi].getCalledFunction()) { 170befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Calls to external functions are never inlinable. 1715cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer if (Callee->isDeclaration() || 172befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSites[CSi].getInstruction()->getParent()->getParent() ==Callee){ 17308ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner if (SCC.size() == 1) { 17408ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner std::swap(CallSites[CSi], CallSites.back()); 17508ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.pop_back(); 17608ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } else { 17708ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // Keep the 'in SCC / not in SCC' boundary correct. 17808ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.erase(CallSites.begin()+CSi); 17908ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } 180befa499d45ffcc32bd9902518aec18589464e47cChris Lattner --CSi; 181befa499d45ffcc32bd9902518aec18589464e47cChris Lattner continue; 182befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 183befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 184befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // If the policy determines that we should inline this function, 185befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // try to do so. 186befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSite CS = CallSites[CSi]; 1871a99dbfe3b70c83d3f3e4648b5868c04697cd77cDaniel Dunbar if (shouldInline(CS)) { 188e345566f8eaeeda45e29e3709114a42209a360ccDale Johannesen Function *Caller = CS.getCaller(); 189befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Attempt to inline the function... 190ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner if (InlineCallIfPossible(CS, CG, SCCFunctions, 191ff2dad312883e5da91fb9f4e3619b7d095867f3bChris Lattner getAnalysis<TargetData>())) { 192e345566f8eaeeda45e29e3709114a42209a360ccDale Johannesen // Remove any cached cost info for this caller, as inlining the callee 193e345566f8eaeeda45e29e3709114a42209a360ccDale Johannesen // has increased the size of the caller. 194e345566f8eaeeda45e29e3709114a42209a360ccDale Johannesen resetCachedCostInfo(Caller); 195e345566f8eaeeda45e29e3709114a42209a360ccDale Johannesen 19608ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // Remove this call site from the list. If possible, use 19708ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // swap/pop_back for efficiency, but do not use it if doing so would 19808ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // move a call site to a function in this SCC before the 19908ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // 'FirstCallInSCC' barrier. 20008ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner if (SCC.size() == 1) { 20108ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner std::swap(CallSites[CSi], CallSites.back()); 20208ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.pop_back(); 20308ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } else { 20408ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.erase(CallSites.begin()+CSi); 20508ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } 206befa499d45ffcc32bd9902518aec18589464e47cChris Lattner --CSi; 207befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 208befa499d45ffcc32bd9902518aec18589464e47cChris Lattner ++NumInlined; 209befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Changed = true; 210befa499d45ffcc32bd9902518aec18589464e47cChris Lattner LocalChange = true; 211775cbdd51a3b33dd5eb343689f65ab5cc8ac7118Chris Lattner } 212237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 213237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 214befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } while (LocalChange); 215237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 216775cbdd51a3b33dd5eb343689f65ab5cc8ac7118Chris Lattner return Changed; 217237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 218d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 21968d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// doFinalization - Remove now-dead linkonce functions at the end of 22068d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// processing to avoid breaking the SCC traversal. 22168d57e7ae80044401efd889270a12c71b3efb9abChris Lattnerbool Inliner::doFinalization(CallGraph &CG) { 222b7c6bf1e073088635951435acedff793add1cefdDevang Patel return removeDeadFunctions(CG); 223b7c6bf1e073088635951435acedff793add1cefdDevang Patel} 224b7c6bf1e073088635951435acedff793add1cefdDevang Patel 225b7c6bf1e073088635951435acedff793add1cefdDevang Patel /// removeDeadFunctions - Remove dead functions that are not included in 226b7c6bf1e073088635951435acedff793add1cefdDevang Patel /// DNR (Do Not Remove) list. 227b7c6bf1e073088635951435acedff793add1cefdDevang Patelbool Inliner::removeDeadFunctions(CallGraph &CG, 228b7c6bf1e073088635951435acedff793add1cefdDevang Patel SmallPtrSet<const Function *, 16> *DNR) { 2293e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner std::set<CallGraphNode*> FunctionsToRemove; 2303e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 2313e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Scan for all of the functions, looking for ones that should now be removed 2323e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // from the program. Insert the dead ones in the FunctionsToRemove set. 2333e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 2343e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner CallGraphNode *CGN = I->second; 23554970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner if (Function *F = CGN ? CGN->getFunction() : 0) { 2360c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // If the only remaining users of the function are dead constants, remove 2370c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // them. 23854970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner F->removeDeadConstantUsers(); 23954970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner 240b7c6bf1e073088635951435acedff793add1cefdDevang Patel if (DNR && DNR->count(F)) 241b7c6bf1e073088635951435acedff793add1cefdDevang Patel continue; 242b7c6bf1e073088635951435acedff793add1cefdDevang Patel 24354970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner if ((F->hasLinkOnceLinkage() || F->hasInternalLinkage()) && 24454970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner F->use_empty()) { 2450c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner 24654970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // Remove any call graph edges from the function to its callees. 2476f0a7687ab9a0509e847279fae27554ce7da0ba1Duncan Sands CGN->removeAllCalledFunctions(); 248fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 2490c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // Remove any edges from the external node to the function's call graph 2500c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // node. These edges might have been made irrelegant due to 2510c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // optimization of the program. 2520c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 253fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 25454970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // Removing the node for callee from the call graph and delete it. 25554970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner FunctionsToRemove.insert(CGN); 25654970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner } 25768d57e7ae80044401efd889270a12c71b3efb9abChris Lattner } 25868d57e7ae80044401efd889270a12c71b3efb9abChris Lattner } 2593e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 2603e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Now that we know which functions to delete, do so. We didn't want to do 2613e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // this inline, because that would invalidate our CallGraph::iterator 2623e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // objects. :( 2633e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner bool Changed = false; 2643e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(), 2653e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner E = FunctionsToRemove.end(); I != E; ++I) { 2663e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner delete CG.removeFunctionFromModule(*I); 2673e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner ++NumDeleted; 2683e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner Changed = true; 2693e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner } 2703e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 27168d57e7ae80044401efd889270a12c71b3efb9abChris Lattner return Changed; 27268d57e7ae80044401efd889270a12c71b3efb9abChris Lattner} 273