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