InlineSimple.cpp revision 6a67393e19632a9829c7ba0d3e7446db322612d9
1//===- FunctionInlining.cpp - Code to perform function inlining -----------===// 2// 3// This file implements bottom-up inlining of functions into callees. 4// 5//===----------------------------------------------------------------------===// 6 7#include "llvm/Transforms/IPO.h" 8#include "llvm/Transforms/Utils/Cloning.h" 9#include "llvm/Module.h" 10#include "llvm/Pass.h" 11#include "llvm/iOther.h" 12#include "llvm/iMemory.h" 13#include "Support/CommandLine.h" 14#include "Support/Debug.h" 15#include "Support/Statistic.h" 16#include <set> 17 18namespace { 19 Statistic<> NumInlined("inline", "Number of functions inlined"); 20 Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found"); 21 cl::opt<unsigned> // FIXME: 200 is VERY conservative 22 InlineLimit("inline-threshold", cl::Hidden, cl::init(200), 23 cl::desc("Control the amount of inlining to perform (default = 200)")); 24 25 struct FunctionInlining : public Pass { 26 virtual bool run(Module &M) { 27 bool Changed = false; 28 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 29 Changed |= doInlining(I); 30 ProcessedFunctions.clear(); 31 return Changed; 32 } 33 34 private: 35 std::set<Function*> ProcessedFunctions; // Prevent infinite recursion 36 bool doInlining(Function *F); 37 }; 38 RegisterOpt<FunctionInlining> X("inline", "Function Integration/Inlining"); 39} 40 41Pass *createFunctionInliningPass() { return new FunctionInlining(); } 42 43 44// ShouldInlineFunction - The heuristic used to determine if we should inline 45// the function call or not. 46// 47static inline bool ShouldInlineFunction(const CallInst *CI) { 48 assert(CI->getParent() && CI->getParent()->getParent() && 49 "Call not embedded into a function!"); 50 51 const Function *Callee = CI->getCalledFunction(); 52 if (Callee == 0 || Callee->isExternal()) 53 return false; // Cannot inline an indirect call... or external function. 54 55 // Don't inline a recursive call. 56 const Function *Caller = CI->getParent()->getParent(); 57 if (Caller == Callee) return false; 58 59 // InlineQuality - This value measures how good of an inline candidate this 60 // call site is to inline. The initial value determines how aggressive the 61 // inliner is. If this value is negative after the final computation, 62 // inlining is not performed. 63 // 64 int InlineQuality = InlineLimit; 65 66 // If there is only one call of the function, and it has internal linkage, 67 // make it almost guaranteed to be inlined. 68 // 69 if (Callee->use_size() == 1 && Callee->hasInternalLinkage()) 70 InlineQuality += 30000; 71 72 // Add to the inline quality for properties that make the call valueable to 73 // inline. This includes factors that indicate that the result of inlining 74 // the function will be optimizable. Currently this just looks at arguments 75 // passed into the function. 76 // 77 for (User::const_op_iterator I = CI->op_begin()+1, E = CI->op_end(); 78 I != E; ++I){ 79 // Each argument passed in has a cost at both the caller and the callee 80 // sides. This favors functions that take many arguments over functions 81 // that take few arguments. 82 InlineQuality += 20; 83 84 // If this is a function being passed in, it is very likely that we will be 85 // able to turn an indirect function call into a direct function call. 86 if (isa<Function>(I)) 87 InlineQuality += 100; 88 89 // If a constant, global variable or alloca is passed in, inlining this 90 // function is likely to allow significant future optimization possibilities 91 // (constant propagation, scalar promotion, and scalarization), so encourage 92 // the inlining of the function. 93 // 94 else if (isa<Constant>(I) || isa<GlobalVariable>(I) || isa<AllocaInst>(I)) 95 InlineQuality += 60; 96 } 97 98 // Now that we have considered all of the factors that make the call site more 99 // likely to be inlined, look at factors that make us not want to inline it. 100 // As soon as the inline quality gets negative, bail out. 101 102 // Look at the size of the callee. Each basic block counts as 20 units, and 103 // each instruction counts as 10. 104 for (Function::const_iterator BB = Callee->begin(), E = Callee->end(); 105 BB != E; ++BB) { 106 InlineQuality -= BB->size()*10 + 20; 107 if (InlineQuality < 0) return false; 108 } 109 110 // Don't inline into something too big, which would make it bigger. Here, we 111 // count each basic block as a single unit. 112 for (Function::const_iterator BB = Caller->begin(), E = Caller->end(); 113 BB != E; ++BB) { 114 --InlineQuality; 115 if (InlineQuality < 0) return false; 116 } 117 118 // If we get here, this call site is high enough "quality" to inline. 119 DEBUG(std::cerr << "Inlining in '" << Caller->getName() 120 << "', quality = " << InlineQuality << ": " << *CI); 121 return true; 122} 123 124 125// doInlining - Use a heuristic based approach to inline functions that seem to 126// look good. 127// 128bool FunctionInlining::doInlining(Function *F) { 129 // If we have already processed this function (ie, it is recursive) don't 130 // revisit. 131 std::set<Function*>::iterator PFI = ProcessedFunctions.lower_bound(F); 132 if (PFI != ProcessedFunctions.end() && *PFI == F) return false; 133 134 // Insert the function in the set so it doesn't get revisited. 135 ProcessedFunctions.insert(PFI, F); 136 137 bool Changed = false; 138 for (Function::iterator BB = F->begin(); BB != F->end(); ++BB) 139 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 140 bool ShouldInc = true; 141 // Found a call instruction? FIXME: This should also handle INVOKEs 142 if (CallInst *CI = dyn_cast<CallInst>(I)) { 143 if (Function *Callee = CI->getCalledFunction()) { 144 doInlining(Callee); // Inline in callees before callers! 145 146 // Decide whether we should inline this function... 147 if (ShouldInlineFunction(CI)) { 148 // Save an iterator to the instruction before the call if it exists, 149 // otherwise get an iterator at the end of the block... because the 150 // call will be destroyed. 151 // 152 BasicBlock::iterator SI; 153 if (I != BB->begin()) { 154 SI = I; --SI; // Instruction before the call... 155 } else { 156 SI = BB->end(); 157 } 158 159 // Attempt to inline the function... 160 if (InlineFunction(CI)) { 161 ++NumInlined; 162 Changed = true; 163 // Move to instruction before the call... 164 I = (SI == BB->end()) ? BB->begin() : SI; 165 ShouldInc = false; // Don't increment iterator until next time 166 167 // If we inlined the last possible call site to the function, 168 // delete the function body now. 169 if (Callee->use_empty() && 170 (Callee->hasInternalLinkage()||Callee->hasLinkOnceLinkage())){ 171 F->getParent()->getFunctionList().erase(Callee); 172 ++NumDeleted; 173 if (Callee == F) return true; 174 } 175 } 176 } 177 } 178 } 179 if (ShouldInc) ++I; 180 } 181 182 return Changed; 183} 184 185