InlineSimple.cpp revision d18015599cbe09dd327b5f73501581a865bf27da
1//===- FunctionInlining.cpp - Code to perform function inlining -----------===// 2// 3// This file implements inlining of functions. 4// 5// Specifically, this: 6// * Exports functionality to inline any function call 7// * Inlines functions that consist of a single basic block 8// * Is able to inline ANY function call 9// . Has a smart heuristic for when to inline a function 10// 11// Notice that: 12// * This pass opens up a lot of opportunities for constant propogation. It 13// is a good idea to to run a constant propogation pass, then a DCE pass 14// sometime after running this pass. 15// 16// FIXME: This pass should transform alloca instructions in the called function 17// into malloc/free pairs! 18// 19//===----------------------------------------------------------------------===// 20 21#include "llvm/Transforms/IPO.h" 22#include "llvm/Transforms/Utils/Cloning.h" 23#include "llvm/Module.h" 24#include "llvm/Pass.h" 25#include "llvm/iTerminators.h" 26#include "llvm/iPHINode.h" 27#include "llvm/iOther.h" 28#include "llvm/Type.h" 29#include "Support/Statistic.h" 30#include <algorithm> 31 32static Statistic<> NumInlined("inline", "Number of functions inlined"); 33using std::cerr; 34 35// InlineFunction - This function forcibly inlines the called function into the 36// basic block of the caller. This returns false if it is not possible to 37// inline this call. The program is still in a well defined state if this 38// occurs though. 39// 40// Note that this only does one level of inlining. For example, if the 41// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 42// exists in the instruction stream. Similiarly this will inline a recursive 43// function by one level. 44// 45bool InlineFunction(CallInst *CI) { 46 assert(isa<CallInst>(CI) && "InlineFunction only works on CallInst nodes"); 47 assert(CI->getParent() && "Instruction not embedded in basic block!"); 48 assert(CI->getParent()->getParent() && "Instruction not in function!"); 49 50 const Function *CalledFunc = CI->getCalledFunction(); 51 if (CalledFunc == 0 || // Can't inline external function or indirect call! 52 CalledFunc->isExternal()) return false; 53 54 //cerr << "Inlining " << CalledFunc->getName() << " into " 55 // << CurrentMeth->getName() << "\n"; 56 57 BasicBlock *OrigBB = CI->getParent(); 58 59 // Call splitBasicBlock - The original basic block now ends at the instruction 60 // immediately before the call. The original basic block now ends with an 61 // unconditional branch to NewBB, and NewBB starts with the call instruction. 62 // 63 BasicBlock *NewBB = OrigBB->splitBasicBlock(CI); 64 NewBB->setName("InlinedFunctionReturnNode"); 65 66 // Remove (unlink) the CallInst from the start of the new basic block. 67 NewBB->getInstList().remove(CI); 68 69 // If we have a return value generated by this call, convert it into a PHI 70 // node that gets values from each of the old RET instructions in the original 71 // function. 72 // 73 PHINode *PHI = 0; 74 if (!CI->use_empty()) { 75 // The PHI node should go at the front of the new basic block to merge all 76 // possible incoming values. 77 // 78 PHI = new PHINode(CalledFunc->getReturnType(), CI->getName(), 79 NewBB->begin()); 80 81 // Anything that used the result of the function call should now use the PHI 82 // node as their operand. 83 // 84 CI->replaceAllUsesWith(PHI); 85 } 86 87 // Get a pointer to the last basic block in the function, which will have the 88 // new function inlined after it. 89 // 90 Function::iterator LastBlock = &OrigBB->getParent()->back(); 91 92 // Calculate the vector of arguments to pass into the function cloner... 93 std::map<const Value*, Value*> ValueMap; 94 assert((unsigned)std::distance(CalledFunc->abegin(), CalledFunc->aend()) == 95 CI->getNumOperands()-1 && "No varargs calls can be inlined yet!"); 96 97 unsigned i = 1; 98 for (Function::const_aiterator I = CalledFunc->abegin(), E=CalledFunc->aend(); 99 I != E; ++I, ++i) 100 ValueMap[I] = CI->getOperand(i); 101 102 // Since we are now done with the CallInst, we can delete it. 103 delete CI; 104 105 // Make a vector to capture the return instructions in the cloned function... 106 std::vector<ReturnInst*> Returns; 107 108 // Do all of the hard part of cloning the callee into the caller... 109 CloneFunctionInto(OrigBB->getParent(), CalledFunc, ValueMap, Returns, ".i"); 110 111 // Loop over all of the return instructions, turning them into unconditional 112 // branches to the merge point now... 113 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 114 ReturnInst *RI = Returns[i]; 115 BasicBlock *BB = RI->getParent(); 116 117 // Add a branch to the merge point where the PHI node would live... 118 new BranchInst(NewBB, RI); 119 120 if (PHI) { // The PHI node should include this value! 121 assert(RI->getReturnValue() && "Ret should have value!"); 122 assert(RI->getReturnValue()->getType() == PHI->getType() && 123 "Ret value not consistent in function!"); 124 PHI->addIncoming(RI->getReturnValue(), BB); 125 } 126 127 // Delete the return instruction now 128 BB->getInstList().erase(RI); 129 } 130 131 // Check to see if the PHI node only has one argument. This is a common 132 // case resulting from there only being a single return instruction in the 133 // function call. Because this is so common, eliminate the PHI node. 134 // 135 if (PHI && PHI->getNumIncomingValues() == 1) { 136 PHI->replaceAllUsesWith(PHI->getIncomingValue(0)); 137 PHI->getParent()->getInstList().erase(PHI); 138 } 139 140 // Change the branch that used to go to NewBB to branch to the first basic 141 // block of the inlined function. 142 // 143 TerminatorInst *Br = OrigBB->getTerminator(); 144 assert(Br && Br->getOpcode() == Instruction::Br && 145 "splitBasicBlock broken!"); 146 Br->setOperand(0, ++LastBlock); 147 return true; 148} 149 150static inline bool ShouldInlineFunction(const CallInst *CI, const Function *F) { 151 assert(CI->getParent() && CI->getParent()->getParent() && 152 "Call not embedded into a function!"); 153 154 // Don't inline a recursive call. 155 if (CI->getParent()->getParent() == F) return false; 156 157 // Don't inline something too big. This is a really crappy heuristic 158 if (F->size() > 3) return false; 159 160 // Don't inline into something too big. This is a **really** crappy heuristic 161 if (CI->getParent()->getParent()->size() > 10) return false; 162 163 // Go ahead and try just about anything else. 164 return true; 165} 166 167 168static inline bool DoFunctionInlining(BasicBlock *BB) { 169 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 170 if (CallInst *CI = dyn_cast<CallInst>(&*I)) { 171 // Check to see if we should inline this function 172 Function *F = CI->getCalledFunction(); 173 if (F && ShouldInlineFunction(CI, F)) { 174 return InlineFunction(CI); 175 } 176 } 177 } 178 return false; 179} 180 181// doFunctionInlining - Use a heuristic based approach to inline functions that 182// seem to look good. 183// 184static bool doFunctionInlining(Function &F) { 185 bool Changed = false; 186 187 // Loop through now and inline instructions a basic block at a time... 188 for (Function::iterator I = F.begin(); I != F.end(); ) 189 if (DoFunctionInlining(I)) { 190 ++NumInlined; 191 Changed = true; 192 } else { 193 ++I; 194 } 195 196 return Changed; 197} 198 199namespace { 200 struct FunctionInlining : public FunctionPass { 201 virtual bool runOnFunction(Function &F) { 202 return doFunctionInlining(F); 203 } 204 }; 205 RegisterOpt<FunctionInlining> X("inline", "Function Integration/Inlining"); 206} 207 208Pass *createFunctionInliningPass() { return new FunctionInlining(); } 209