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