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