Inliner.cpp revision a51bcb50b0c74adc741361824ef81dbefb715c53
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" 26a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattnerusing namespace llvm; 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 28237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnernamespace { 29237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Statistic<> NumInlined("inline", "Number of functions inlined"); 30237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found"); 31237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner cl::opt<unsigned> // FIXME: 200 is VERY conservative 32237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineLimit("inline-threshold", cl::Hidden, cl::init(200), 33237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner cl::desc("Control the amount of inlining to perform (default = 200)")); 34237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 35237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 36237ef567f6764f24a47c63121cc0a599ddc8f56dChris LattnerInliner::Inliner() : InlineThreshold(InlineLimit) {} 37237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 38237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerint Inliner::getRecursiveInlineCost(CallSite CS) { 39237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return getInlineCost(CS); 40237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 41237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 42237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 43237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallGraph &CG = getAnalysis<CallGraph>(); 44237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 45237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner std::set<Function*> SCCFunctions; 46237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << "Inliner visiting SCC:"); 47237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 48237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SCCFunctions.insert(SCC[i]->getFunction()); 49237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << " " << (SCC[i]->getFunction() ? 50237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SCC[i]->getFunction()->getName() : "INDIRECTNODE")); 51237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 52237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << "\n"); 53237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 54237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner bool Changed = false; 55237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(), 56237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner E = SCCFunctions.end(); SCCI != E; ++SCCI) { 57237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Function *F = *SCCI; 58237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (F == 0 || F->isExternal()) continue; 59237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << " Inspecting function: " << F->getName() << "\n"); 60237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 61237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 62237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 63237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner bool ShouldInc = true; 64237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Found a call or invoke instruction? 65237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 66237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner CallSite CS = CallSite::get(I); 67237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (Function *Callee = CS.getCalledFunction()) 68d77922f1a2ed9290544ded8a50d52fd24065556fChris Lattner if (!Callee->isExternal() && !IsRecursiveFunction.count(Callee)) { 69237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Determine whether this is a function IN the SCC... 70237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner bool inSCC = SCCFunctions.count(Callee); 71237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 72d77922f1a2ed9290544ded8a50d52fd24065556fChris Lattner // Keep track of whether this is a directly recursive function. 73d77922f1a2ed9290544ded8a50d52fd24065556fChris Lattner if (Callee == F) IsRecursiveFunction.insert(F); 74d77922f1a2ed9290544ded8a50d52fd24065556fChris Lattner 75237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // If the policy determines that we should inline this function, 76237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // try to do so... 77237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner int InlineCost = inSCC ? getRecursiveInlineCost(CS) : 78237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner getInlineCost(CS); 79a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattner if (InlineCost >= (int)InlineThreshold) { 80a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattner DEBUG(std::cerr << " NOT Inlining: cost=" << InlineCost 81a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattner << ", Call: " << *CS.getInstruction()); 82a51bcb50b0c74adc741361824ef81dbefb715c53Chris Lattner } else { 83237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner DEBUG(std::cerr << " Inlining: cost=" << InlineCost 84237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner << ", Call: " << *CS.getInstruction()); 85237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 86237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Save an iterator to the instruction before the call if it 87237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // exists, otherwise get an iterator at the end of the 88237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // block... because the call will be destroyed. 89237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // 90237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner BasicBlock::iterator SI; 91237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (I != BB->begin()) { 92237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SI = I; --SI; // Instruction before the call... 93237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } else { 94237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SI = BB->end(); 95237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 96237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 97237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (performInlining(CS, SCCFunctions)) { 98237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Move to instruction before the call... 99237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner I = (SI == BB->end()) ? BB->begin() : SI; 100237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner ShouldInc = false; // Don't increment iterator until next time 101237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Changed = true; 102237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 103237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 104237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 105237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 106237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (ShouldInc) ++I; 107237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 108237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 109237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return Changed; 110237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 111237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 112237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerbool Inliner::performInlining(CallSite CS, std::set<Function*> &SCC) { 113237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Function *Callee = CS.getCalledFunction(); 114237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Function *Caller = CS.getInstruction()->getParent()->getParent(); 115237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 116237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Attempt to inline the function... 117237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (!InlineFunction(CS)) return false; 118237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner ++NumInlined; 119bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner 120bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner if (Callee->hasOneUse()) 121bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner if (ConstantPointerRef *CPR = 122bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner dyn_cast<ConstantPointerRef>(Callee->use_back())) 123bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner if (CPR->use_empty()) 124bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner CPR->destroyConstant(); 125bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner 126237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // If we inlined the last possible call site to the function, 127237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // delete the function body now. 128237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (Callee->use_empty() && Callee != Caller && 129237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner (Callee->hasInternalLinkage() || Callee->hasLinkOnceLinkage())) { 130bb9ae1512e1179681c1774f2f1a9d8c042941a56Chris Lattner DEBUG(std::cerr << " -> Deleting dead function: " << (void*)Callee 131237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner << Callee->getName() << "\n"); 132237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner std::set<Function*>::iterator I = SCC.find(Callee); 133237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (I != SCC.end()) // Remove function from this SCC... 134237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner SCC.erase(I); 135237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 136237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner Callee->getParent()->getFunctionList().erase(Callee); 137237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner ++NumDeleted; 138237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner } 139237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return true; 140237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner} 141d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 142