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