Inliner.cpp revision bb9ae1512e1179681c1774f2f1a9d8c042941a56
1237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner//===- InlineCommon.cpp - Code common to all inliners ---------------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 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. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// 10237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// This file implements the code shared between the LLVM inliners. This 11237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// implements all of the boring mechanics of the bottom-up inlining. 12237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// 13237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner//===----------------------------------------------------------------------===// 14237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 15237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "Inliner.h" 16bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner#include "llvm/Constants.h" // ConstantPointerRef should die 17237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Module.h" 18237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/iOther.h" 19237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/iTerminators.h" 20237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Analysis/CallGraph.h" 21237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Support/CallSite.h" 22237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 23237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "Support/CommandLine.h" 24237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "Support/Debug.h" 25237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "Support/Statistic.h" 26237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 27237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnernamespace { 28237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Statistic<> NumInlined("inline", "Number of functions inlined"); 29237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found"); 30237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner cl::opt<unsigned> // FIXME: 200 is VERY conservative 31237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineLimit("inline-threshold", cl::Hidden, cl::init(200), 32237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner cl::desc("Control the amount of inlining to perform (default = 200)")); 33237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 34237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 35237ef567f6764f24a47c63121cc0a599ddc8f56dChris LattnerInliner::Inliner() : InlineThreshold(InlineLimit) {} 36237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 37237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerint Inliner::getRecursiveInlineCost(CallSite CS) { 38237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return getInlineCost(CS); 39237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 40237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 41237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 42237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallGraph &CG = getAnalysis<CallGraph>(); 43237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 44237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner std::set<Function*> SCCFunctions; 45237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << "Inliner visiting SCC:"); 46237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 47237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SCCFunctions.insert(SCC[i]->getFunction()); 48237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << " " << (SCC[i]->getFunction() ? 49237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SCC[i]->getFunction()->getName() : "INDIRECTNODE")); 50237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 51237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << "\n"); 52237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 53237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner bool Changed = false; 54237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(), 55237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner E = SCCFunctions.end(); SCCI != E; ++SCCI) { 56237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Function *F = *SCCI; 57237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (F == 0 || F->isExternal()) continue; 58237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << " Inspecting function: " << F->getName() << "\n"); 59237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 60237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 61237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 62237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner bool ShouldInc = true; 63237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Found a call or invoke instruction? 64237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 65237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallSite CS = CallSite::get(I); 66237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (Function *Callee = CS.getCalledFunction()) 67237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (!Callee->isExternal()) { 68237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Determine whether this is a function IN the SCC... 69237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner bool inSCC = SCCFunctions.count(Callee); 70237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 71237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // If the policy determines that we should inline this function, 72237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // try to do so... 73237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner int InlineCost = inSCC ? getRecursiveInlineCost(CS) : 74237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner getInlineCost(CS); 75237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (InlineCost < (int)InlineThreshold) { 76237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << " Inlining: cost=" << InlineCost 77237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner << ", Call: " << *CS.getInstruction()); 78237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 79237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Save an iterator to the instruction before the call if it 80237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // exists, otherwise get an iterator at the end of the 81237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // block... because the call will be destroyed. 82237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // 83237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner BasicBlock::iterator SI; 84237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (I != BB->begin()) { 85237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SI = I; --SI; // Instruction before the call... 86237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } else { 87237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SI = BB->end(); 88237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 89237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 90237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (performInlining(CS, SCCFunctions)) { 91237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Move to instruction before the call... 92237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner I = (SI == BB->end()) ? BB->begin() : SI; 93237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner ShouldInc = false; // Don't increment iterator until next time 94237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Changed = true; 95237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 96237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 97237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 98237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 99237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (ShouldInc) ++I; 100237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 101237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 102237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return Changed; 103237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 104237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 105237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::performInlining(CallSite CS, std::set<Function*> &SCC) { 106237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Function *Callee = CS.getCalledFunction(); 107237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Function *Caller = CS.getInstruction()->getParent()->getParent(); 108237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 109237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Attempt to inline the function... 110237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (!InlineFunction(CS)) return false; 111237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner ++NumInlined; 112bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner 113bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner if (Callee->hasOneUse()) 114bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner if (ConstantPointerRef *CPR = 115bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner dyn_cast<ConstantPointerRef>(Callee->use_back())) 116bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner if (CPR->use_empty()) 117bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner CPR->destroyConstant(); 118bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner 119237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // If we inlined the last possible call site to the function, 120237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // delete the function body now. 121237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (Callee->use_empty() && Callee != Caller && 122237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner (Callee->hasInternalLinkage() || Callee->hasLinkOnceLinkage())) { 123bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner DEBUG(std::cerr << " -> Deleting dead function: " << (void*)Callee 124237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner << Callee->getName() << "\n"); 125237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner std::set<Function*>::iterator I = SCC.find(Callee); 126237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (I != SCC.end()) // Remove function from this SCC... 127237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SCC.erase(I); 128237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 129237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Callee->getParent()->getFunctionList().erase(Callee); 130237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner ++NumDeleted; 131237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 132237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return true; 133237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 134