InlineFunction.cpp revision 51d6816089a66c171dc23b50d62989ac6bb5c491
1//===- InlineFunction.cpp - Code to perform function inlining -------------===// 2// 3// This file implements inlining of a function into a call site, resolving 4// parameters and the return value as appropriate. 5// 6// FIXME: This pass should transform alloca instructions in the called function 7// into malloc/free pairs! Or perhaps it should refuse to inline them! 8// 9//===----------------------------------------------------------------------===// 10 11#include "llvm/Transforms/Utils/Cloning.h" 12#include "llvm/Constant.h" 13#include "llvm/DerivedTypes.h" 14#include "llvm/Module.h" 15#include "llvm/Instructions.h" 16#include "llvm/Intrinsics.h" 17#include "llvm/Support/CallSite.h" 18#include "llvm/Transforms/Utils/Local.h" 19 20bool InlineFunction(CallInst *CI) { return InlineFunction(CallSite(CI)); } 21bool InlineFunction(InvokeInst *II) { return InlineFunction(CallSite(II)); } 22 23// InlineFunction - This function inlines the called function into the basic 24// block of the caller. This returns false if it is not possible to inline this 25// call. The program is still in a well defined state if this occurs though. 26// 27// Note that this only does one level of inlining. For example, if the 28// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 29// exists in the instruction stream. Similiarly this will inline a recursive 30// function by one level. 31// 32bool InlineFunction(CallSite CS) { 33 Instruction *TheCall = CS.getInstruction(); 34 assert(TheCall->getParent() && TheCall->getParent()->getParent() && 35 "Instruction not in function!"); 36 37 const Function *CalledFunc = CS.getCalledFunction(); 38 if (CalledFunc == 0 || // Can't inline external function or indirect 39 CalledFunc->isExternal() || // call, or call to a vararg function! 40 CalledFunc->getFunctionType()->isVarArg()) return false; 41 42 BasicBlock *OrigBB = TheCall->getParent(); 43 Function *Caller = OrigBB->getParent(); 44 45 // We want to clone the entire callee function into the whole between the 46 // "starter" and "ender" blocks. How we accomplish this depends on whether 47 // this is an invoke instruction or a call instruction. 48 49 BasicBlock *InvokeDest = 0; // Exception handling destination 50 std::vector<Value*> InvokeDestPHIValues; // Values for PHI nodes in InvokeDest 51 BasicBlock *AfterCallBB; 52 53 if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 54 AfterCallBB = II->getNormalDest(); 55 InvokeDest = II->getExceptionalDest(); 56 57 // Add an unconditional branch to make this look like the CallInst case... 58 new BranchInst(AfterCallBB, TheCall); 59 60 // If there are PHI nodes in the exceptional destination block, we need to 61 // keep track of which values came into them from this invoke, then remove 62 // the entry for this block. 63 for (BasicBlock::iterator I = InvokeDest->begin(); 64 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 65 // Save the value to use for this edge... 66 InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(OrigBB)); 67 } 68 69 // Remove (unlink) the InvokeInst from the function... 70 OrigBB->getInstList().remove(TheCall); 71 72 } else { // It's a call 73 // If this is a call instruction, we need to split the basic block that the 74 // call lives in. 75 // 76 AfterCallBB = OrigBB->splitBasicBlock(TheCall, 77 CalledFunc->getName()+".entry"); 78 // Remove (unlink) the CallInst from the function... 79 AfterCallBB->getInstList().remove(TheCall); 80 } 81 82 // If we have a return value generated by this call, convert it into a PHI 83 // node that gets values from each of the old RET instructions in the original 84 // function. 85 // 86 PHINode *PHI = 0; 87 if (!TheCall->use_empty()) { 88 // The PHI node should go at the front of the new basic block to merge all 89 // possible incoming values. 90 // 91 PHI = new PHINode(CalledFunc->getReturnType(), TheCall->getName(), 92 AfterCallBB->begin()); 93 94 // Anything that used the result of the function call should now use the PHI 95 // node as their operand. 96 // 97 TheCall->replaceAllUsesWith(PHI); 98 } 99 100 // Get an iterator to the last basic block in the function, which will have 101 // the new function inlined after it. 102 // 103 Function::iterator LastBlock = &Caller->back(); 104 105 // Calculate the vector of arguments to pass into the function cloner... 106 std::map<const Value*, Value*> ValueMap; 107 assert(std::distance(CalledFunc->abegin(), CalledFunc->aend()) == 108 std::distance(CS.arg_begin(), CS.arg_end()) && 109 "No varargs calls can be inlined!"); 110 111 CallSite::arg_iterator AI = CS.arg_begin(); 112 for (Function::const_aiterator I = CalledFunc->abegin(), E=CalledFunc->aend(); 113 I != E; ++I, ++AI) 114 ValueMap[I] = *AI; 115 116 // Since we are now done with the Call/Invoke, we can delete it. 117 delete TheCall; 118 119 // Make a vector to capture the return instructions in the cloned function... 120 std::vector<ReturnInst*> Returns; 121 122 // Populate the value map with all of the globals in the program. 123 // FIXME: This should be the default for CloneFunctionInto! 124 Module &M = *Caller->getParent(); 125 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 126 ValueMap[I] = I; 127 for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) 128 ValueMap[I] = I; 129 130 // Do all of the hard part of cloning the callee into the caller... 131 CloneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i"); 132 133 // Loop over all of the return instructions, turning them into unconditional 134 // branches to the merge point now... 135 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 136 ReturnInst *RI = Returns[i]; 137 BasicBlock *BB = RI->getParent(); 138 139 // Add a branch to the merge point where the PHI node lives if it exists. 140 new BranchInst(AfterCallBB, RI); 141 142 if (PHI) { // The PHI node should include this value! 143 assert(RI->getReturnValue() && "Ret should have value!"); 144 assert(RI->getReturnValue()->getType() == PHI->getType() && 145 "Ret value not consistent in function!"); 146 PHI->addIncoming(RI->getReturnValue(), BB); 147 } 148 149 // Delete the return instruction now 150 BB->getInstList().erase(RI); 151 } 152 153 // Check to see if the PHI node only has one argument. This is a common 154 // case resulting from there only being a single return instruction in the 155 // function call. Because this is so common, eliminate the PHI node. 156 // 157 if (PHI && PHI->getNumIncomingValues() == 1) { 158 PHI->replaceAllUsesWith(PHI->getIncomingValue(0)); 159 PHI->getParent()->getInstList().erase(PHI); 160 } 161 162 // Change the branch that used to go to AfterCallBB to branch to the first 163 // basic block of the inlined function. 164 // 165 TerminatorInst *Br = OrigBB->getTerminator(); 166 assert(Br && Br->getOpcode() == Instruction::Br && 167 "splitBasicBlock broken!"); 168 Br->setOperand(0, ++LastBlock); 169 170 // If there are any alloca instructions in the block that used to be the entry 171 // block for the callee, move them to the entry block of the caller. First 172 // calculate which instruction they should be inserted before. We insert the 173 // instructions at the end of the current alloca list. 174 // 175 if (isa<AllocaInst>(LastBlock->begin())) { 176 BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 177 while (isa<AllocaInst>(InsertPoint)) ++InsertPoint; 178 179 for (BasicBlock::iterator I = LastBlock->begin(), E = LastBlock->end(); 180 I != E; ) 181 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) { 182 ++I; // Move to the next instruction 183 LastBlock->getInstList().remove(AI); 184 Caller->front().getInstList().insert(InsertPoint, AI); 185 } else { 186 ++I; 187 } 188 } 189 190 // If we just inlined a call due to an invoke instruction, scan the inlined 191 // function checking for function calls that should now be made into invoke 192 // instructions, and for unwind's which should be turned into branches. 193 if (InvokeDest) { 194 for (Function::iterator BB = LastBlock, E = Caller->end(); BB != E; ++BB) { 195 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 196 // We only need to check for function calls: inlined invoke instructions 197 // require no special handling... 198 if (CallInst *CI = dyn_cast<CallInst>(I)) { 199 // Convert this function call into an invoke instruction... 200 201 // First, split the basic block... 202 BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc"); 203 204 // Next, create the new invoke instruction, inserting it at the end 205 // of the old basic block. 206 InvokeInst *II = 207 new InvokeInst(CI->getCalledValue(), Split, InvokeDest, 208 std::vector<Value*>(CI->op_begin()+1, CI->op_end()), 209 CI->getName(), BB->getTerminator()); 210 211 // Make sure that anything using the call now uses the invoke! 212 CI->replaceAllUsesWith(II); 213 214 // Delete the unconditional branch inserted by splitBasicBlock 215 BB->getInstList().pop_back(); 216 Split->getInstList().pop_front(); // Delete the original call 217 218 // Update any PHI nodes in the exceptional block to indicate that 219 // there is now a new entry in them. 220 unsigned i = 0; 221 for (BasicBlock::iterator I = InvokeDest->begin(); 222 PHINode *PN = dyn_cast<PHINode>(I); ++I, ++i) 223 PN->addIncoming(InvokeDestPHIValues[i], BB); 224 225 // This basic block is now complete, start scanning the next one. 226 break; 227 } else { 228 ++I; 229 } 230 } 231 232 if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 233 // An UnwindInst requires special handling when it gets inlined into an 234 // invoke site. Once this happens, we know that the unwind would cause 235 // a control transfer to the invoke exception destination, so we can 236 // transform it into a direct branch to the exception destination. 237 BranchInst *BI = new BranchInst(InvokeDest, UI); 238 239 // Delete the unwind instruction! 240 UI->getParent()->getInstList().pop_back(); 241 } 242 } 243 244 // Now that everything is happy, we have one final detail. The PHI nodes in 245 // the exception destination block still have entries due to the original 246 // invoke instruction. Eliminate these entries (which might even delete the 247 // PHI node) now. 248 for (BasicBlock::iterator I = InvokeDest->begin(); 249 PHINode *PN = dyn_cast<PHINode>(I); ++I) 250 PN->removeIncomingValue(OrigBB); 251 } 252 // Now that the function is correct, make it a little bit nicer. In 253 // particular, move the basic blocks inserted from the end of the function 254 // into the space made by splitting the source basic block. 255 // 256 Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(), 257 LastBlock, Caller->end()); 258 259 // We should always be able to fold the entry block of the function into the 260 // single predecessor of the block... 261 assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!"); 262 BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 263 SimplifyCFG(CalleeEntry); 264 265 // Okay, continue the CFG cleanup. It's often the case that there is only a 266 // single return instruction in the callee function. If this is the case, 267 // then we have an unconditional branch from the return block to the 268 // 'AfterCallBB'. Check for this case, and eliminate the branch is possible. 269 SimplifyCFG(AfterCallBB); 270 return true; 271} 272