Inliner.cpp revision 08ff1480ffcb22e946c7bb6c7d66c5d977ae3d6e
1cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51Chris Lattner//===- Inliner.cpp - Code common to all inliners --------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source 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 16237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "Inliner.h" 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" 21237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 22551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 23551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 24551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 25dac58ad983c62b49629e1f2969f4e0a621167d63Chris Lattner#include <iostream> 26befa499d45ffcc32bd9902518aec18589464e47cChris Lattner#include <set> 27a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattnerusing namespace llvm; 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 29237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnernamespace { 30237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Statistic<> NumInlined("inline", "Number of functions inlined"); 318acb249725e3304aafe91d5357f69722957c51b1Chris Lattner Statistic<> NumDeleted("inline", 328acb249725e3304aafe91d5357f69722957c51b1Chris Lattner "Number of functions deleted because all callers found"); 33237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner cl::opt<unsigned> // FIXME: 200 is VERY conservative 34237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineLimit("inline-threshold", cl::Hidden, cl::init(200), 358acb249725e3304aafe91d5357f69722957c51b1Chris Lattner cl::desc("Control the amount of inlining to perform (default = 200)")); 36237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 37237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 38237ef567f6764f24a47c63121cc0a599ddc8f56dChris LattnerInliner::Inliner() : InlineThreshold(InlineLimit) {} 39237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 40befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// InlineCallIfPossible - If it is possible to inline the specified call site, 41befa499d45ffcc32bd9902518aec18589464e47cChris Lattner// do so and update the CallGraph for this operation. 42befa499d45ffcc32bd9902518aec18589464e47cChris Lattnerstatic bool InlineCallIfPossible(CallSite CS, CallGraph &CG, 43befa499d45ffcc32bd9902518aec18589464e47cChris Lattner const std::set<Function*> &SCCFunctions) { 44befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *Callee = CS.getCalledFunction(); 45432a205769d22e7744dd8b0b45efd687aa6998e3Chris Lattner if (!InlineFunction(CS, &CG)) return false; 46fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 4754970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // If we inlined the last possible call site to the function, delete the 4854970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // function body now. 49befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Callee->use_empty() && Callee->hasInternalLinkage() && 50befa499d45ffcc32bd9902518aec18589464e47cChris Lattner !SCCFunctions.count(Callee)) { 51befa499d45ffcc32bd9902518aec18589464e47cChris Lattner DEBUG(std::cerr << " -> Deleting dead function: " 52befa499d45ffcc32bd9902518aec18589464e47cChris Lattner << Callee->getName() << "\n"); 53fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 54befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Remove any call graph edges from the callee to its callees. 55432a205769d22e7744dd8b0b45efd687aa6998e3Chris Lattner CallGraphNode *CalleeNode = CG[Callee]; 56befa499d45ffcc32bd9902518aec18589464e47cChris Lattner while (CalleeNode->begin() != CalleeNode->end()) 57d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner CalleeNode->removeCallEdgeTo((CalleeNode->end()-1)->second); 58fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 59befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Removing the node for callee from the call graph and delete it. 60befa499d45ffcc32bd9902518aec18589464e47cChris Lattner delete CG.removeFunctionFromModule(CalleeNode); 61befa499d45ffcc32bd9902518aec18589464e47cChris Lattner ++NumDeleted; 62befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 63befa499d45ffcc32bd9902518aec18589464e47cChris Lattner return true; 64237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 65237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 66237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 67237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallGraph &CG = getAnalysis<CallGraph>(); 68237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 69237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner std::set<Function*> SCCFunctions; 70237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << "Inliner visiting SCC:"); 71237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 72befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Function *F = SCC[i]->getFunction(); 73befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (F) SCCFunctions.insert(F); 74befa499d45ffcc32bd9902518aec18589464e47cChris Lattner DEBUG(std::cerr << " " << (F ? F->getName() : "INDIRECTNODE")); 75237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 76237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 77befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Scan through and identify all call sites ahead of time so that we only 78befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // inline call sites in the original functions, not call sites that result 79befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // from inlining other functions. 80befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::vector<CallSite> CallSites; 81befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 82cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51Chris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) 83cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51Chris Lattner if (Function *F = SCC[i]->getFunction()) 84befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 85befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 86befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSite CS = CallSite::get(I); 87befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (CS.getInstruction() && (!CS.getCalledFunction() || 88befa499d45ffcc32bd9902518aec18589464e47cChris Lattner !CS.getCalledFunction()->isExternal())) 89befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSites.push_back(CS); 90befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 91237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 92befa499d45ffcc32bd9902518aec18589464e47cChris Lattner DEBUG(std::cerr << ": " << CallSites.size() << " call sites.\n"); 93fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 94befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, move the ones to functions in the 95befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // current SCC to the end of the list. 96befa499d45ffcc32bd9902518aec18589464e47cChris Lattner unsigned FirstCallInSCC = CallSites.size(); 97befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (unsigned i = 0; i < FirstCallInSCC; ++i) 98befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Function *F = CallSites[i].getCalledFunction()) 99befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (SCCFunctions.count(F)) 100befa499d45ffcc32bd9902518aec18589464e47cChris Lattner std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); 101fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 102befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Now that we have all of the call sites, loop over them and inline them if 103befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // it looks profitable to do so. 104befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool Changed = false; 105befa499d45ffcc32bd9902518aec18589464e47cChris Lattner bool LocalChange; 106befa499d45ffcc32bd9902518aec18589464e47cChris Lattner do { 107befa499d45ffcc32bd9902518aec18589464e47cChris Lattner LocalChange = false; 108befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Iterate over the outer loop because inlining functions can cause indirect 109befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // calls to become direct calls. 110befa499d45ffcc32bd9902518aec18589464e47cChris Lattner for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) 111befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Function *Callee = CallSites[CSi].getCalledFunction()) { 112befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Calls to external functions are never inlinable. 113befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (Callee->isExternal() || 114befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSites[CSi].getInstruction()->getParent()->getParent() ==Callee){ 11508ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner if (SCC.size() == 1) { 11608ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner std::swap(CallSites[CSi], CallSites.back()); 11708ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.pop_back(); 11808ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } else { 11908ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // Keep the 'in SCC / not in SCC' boundary correct. 12008ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.erase(CallSites.begin()+CSi); 12108ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } 122befa499d45ffcc32bd9902518aec18589464e47cChris Lattner --CSi; 123befa499d45ffcc32bd9902518aec18589464e47cChris Lattner continue; 124befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } 125befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 126befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // If the policy determines that we should inline this function, 127befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // try to do so. 128befa499d45ffcc32bd9902518aec18589464e47cChris Lattner CallSite CS = CallSites[CSi]; 129befa499d45ffcc32bd9902518aec18589464e47cChris Lattner int InlineCost = getInlineCost(CS); 130befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (InlineCost >= (int)InlineThreshold) { 131befa499d45ffcc32bd9902518aec18589464e47cChris Lattner DEBUG(std::cerr << " NOT Inlining: cost=" << InlineCost 132befa499d45ffcc32bd9902518aec18589464e47cChris Lattner << ", Call: " << *CS.getInstruction()); 133befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } else { 134befa499d45ffcc32bd9902518aec18589464e47cChris Lattner DEBUG(std::cerr << " Inlining: cost=" << InlineCost 135befa499d45ffcc32bd9902518aec18589464e47cChris Lattner << ", Call: " << *CS.getInstruction()); 136fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 137befa499d45ffcc32bd9902518aec18589464e47cChris Lattner // Attempt to inline the function... 138befa499d45ffcc32bd9902518aec18589464e47cChris Lattner if (InlineCallIfPossible(CS, CG, SCCFunctions)) { 13908ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // Remove this call site from the list. If possible, use 14008ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // swap/pop_back for efficiency, but do not use it if doing so would 14108ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // move a call site to a function in this SCC before the 14208ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner // 'FirstCallInSCC' barrier. 14308ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner if (SCC.size() == 1) { 14408ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner std::swap(CallSites[CSi], CallSites.back()); 14508ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.pop_back(); 14608ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } else { 14708ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner CallSites.erase(CallSites.begin()+CSi); 14808ff1480ffcb22e946c7bb6c7d66c5d977ae3d6eChris Lattner } 149befa499d45ffcc32bd9902518aec18589464e47cChris Lattner --CSi; 150befa499d45ffcc32bd9902518aec18589464e47cChris Lattner 151befa499d45ffcc32bd9902518aec18589464e47cChris Lattner ++NumInlined; 152befa499d45ffcc32bd9902518aec18589464e47cChris Lattner Changed = true; 153befa499d45ffcc32bd9902518aec18589464e47cChris Lattner LocalChange = true; 154775cbdd51a3b33dd5eb343689f65ab5cc8ac7118Chris Lattner } 155237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 156237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 157befa499d45ffcc32bd9902518aec18589464e47cChris Lattner } while (LocalChange); 158237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 159775cbdd51a3b33dd5eb343689f65ab5cc8ac7118Chris Lattner return Changed; 160237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 161d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 16268d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// doFinalization - Remove now-dead linkonce functions at the end of 16368d57e7ae80044401efd889270a12c71b3efb9abChris Lattner// processing to avoid breaking the SCC traversal. 16468d57e7ae80044401efd889270a12c71b3efb9abChris Lattnerbool Inliner::doFinalization(CallGraph &CG) { 1653e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner std::set<CallGraphNode*> FunctionsToRemove; 1663e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 1673e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Scan for all of the functions, looking for ones that should now be removed 1683e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // from the program. Insert the dead ones in the FunctionsToRemove set. 1693e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 1703e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner CallGraphNode *CGN = I->second; 17154970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner if (Function *F = CGN ? CGN->getFunction() : 0) { 1720c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // If the only remaining users of the function are dead constants, remove 1730c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // them. 17454970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner F->removeDeadConstantUsers(); 17554970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner 17654970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner if ((F->hasLinkOnceLinkage() || F->hasInternalLinkage()) && 17754970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner F->use_empty()) { 1780c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner 17954970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // Remove any call graph edges from the function to its callees. 18054970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner while (CGN->begin() != CGN->end()) 181d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner CGN->removeCallEdgeTo((CGN->end()-1)->second); 182fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1830c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // Remove any edges from the external node to the function's call graph 1840c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // node. These edges might have been made irrelegant due to 1850c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner // optimization of the program. 1860c0aa711b8a0550c21f032125c4663ff45864f81Chris Lattner CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 187fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18854970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner // Removing the node for callee from the call graph and delete it. 18954970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner FunctionsToRemove.insert(CGN); 19054970c032815edadb1b2988ea33f5a1173e5b29cChris Lattner } 19168d57e7ae80044401efd889270a12c71b3efb9abChris Lattner } 19268d57e7ae80044401efd889270a12c71b3efb9abChris Lattner } 1933e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 1943e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // Now that we know which functions to delete, do so. We didn't want to do 1953e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // this inline, because that would invalidate our CallGraph::iterator 1963e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner // objects. :( 1973e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner bool Changed = false; 1983e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(), 1993e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner E = FunctionsToRemove.end(); I != E; ++I) { 2003e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner delete CG.removeFunctionFromModule(*I); 2013e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner ++NumDeleted; 2023e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner Changed = true; 2033e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner } 2043e1358a9fa1ebd3f51c94eb69da55d693895fe7cChris Lattner 20568d57e7ae80044401efd889270a12c71b3efb9abChris Lattner return Changed; 20668d57e7ae80044401efd889270a12c71b3efb9abChris Lattner} 207