InlineFunction.cpp revision aeb2a1d70807aa626f335fb23d47bc604ffeaa15
1ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner//===- InlineFunction.cpp - Code to perform function inlining -------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 10ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// This file implements inlining of a function into a call site, resolving 11ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// parameters and the return value as appropriate. 12ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 13ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// FIXME: This pass should transform alloca instructions in the called function 145052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner// into alloca/dealloca pairs! Or perhaps it should refuse to inline them! 15ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 16ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner//===----------------------------------------------------------------------===// 17ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 18ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 1980a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Constant.h" 207152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner#include "llvm/DerivedTypes.h" 21ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner#include "llvm/Module.h" 2280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Instructions.h" 2380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Intrinsics.h" 2480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Support/CallSite.h" 257152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner#include "llvm/Transforms/Utils/Local.h" 26f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 27ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 28f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::InlineFunction(CallInst *CI) { return InlineFunction(CallSite(CI)); } 29f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::InlineFunction(InvokeInst *II) {return InlineFunction(CallSite(II));} 3080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner 31ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// InlineFunction - This function inlines the called function into the basic 32ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// block of the caller. This returns false if it is not possible to inline this 33ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// call. The program is still in a well defined state if this occurs though. 34ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 35ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// Note that this only does one level of inlining. For example, if the 36ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 37ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// exists in the instruction stream. Similiarly this will inline a recursive 38ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// function by one level. 39ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 40f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::InlineFunction(CallSite CS) { 4180a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner Instruction *TheCall = CS.getInstruction(); 4280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner assert(TheCall->getParent() && TheCall->getParent()->getParent() && 4380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner "Instruction not in function!"); 44ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 4580a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner const Function *CalledFunc = CS.getCalledFunction(); 46ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner if (CalledFunc == 0 || // Can't inline external function or indirect 47ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner CalledFunc->isExternal() || // call, or call to a vararg function! 48ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner CalledFunc->getFunctionType()->isVarArg()) return false; 49ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 5080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner BasicBlock *OrigBB = TheCall->getParent(); 51ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner Function *Caller = OrigBB->getParent(); 52ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 535052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // Get an iterator to the last basic block in the function, which will have 545052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // the new function inlined after it. 555052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // 565052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner Function::iterator LastBlock = &Caller->back(); 575052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner 585e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Make sure to capture all of the return instructions from the cloned 595e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // function. 605052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner std::vector<ReturnInst*> Returns; 615e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner { // Scope to destroy ValueMap after cloning. 625e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Calculate the vector of arguments to pass into the function cloner... 635e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner std::map<const Value*, Value*> ValueMap; 645e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner assert(std::distance(CalledFunc->abegin(), CalledFunc->aend()) == 655e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner std::distance(CS.arg_begin(), CS.arg_end()) && 665e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner "No varargs calls can be inlined!"); 675e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 685e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CallSite::arg_iterator AI = CS.arg_begin(); 695e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (Function::const_aiterator I = CalledFunc->abegin(), 705e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner E = CalledFunc->aend(); I != E; ++I, ++AI) 715e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner ValueMap[I] = *AI; 725e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 735e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Clone the entire body of the callee into the caller. 745e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CloneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i"); 755e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 76c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner 775e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Remember the first block that is newly cloned over. 785e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner Function::iterator FirstNewBlock = LastBlock; ++FirstNewBlock; 79ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 80ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // If there are any alloca instructions in the block that used to be the entry 81ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // block for the callee, move them to the entry block of the caller. First 82ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // calculate which instruction they should be inserted before. We insert the 83ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // instructions at the end of the current alloca list. 84ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // 855e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (isa<AllocaInst>(FirstNewBlock->begin())) { 8680a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 875e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (BasicBlock::iterator I = FirstNewBlock->begin(), 885e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner E = FirstNewBlock->end(); I != E; ) 89f775f95369ba7d88a5cb8b6f1900241699d79351Chris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I++)) 90f775f95369ba7d88a5cb8b6f1900241699d79351Chris Lattner if (isa<Constant>(AI->getArraySize())) { 91c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // Scan for the block of allocas that we can move over. 92c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner while (isa<AllocaInst>(I) && 93c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner isa<Constant>(cast<AllocaInst>(I)->getArraySize())) 94c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner ++I; 95c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner 96c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // Transfer all of the allocas over in a block. Using splice means 97c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // that they instructions aren't removed from the symbol table, then 98c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // reinserted. 99c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner Caller->front().getInstList().splice(InsertPoint, 100c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner FirstNewBlock->getInstList(), 101c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner AI, I); 102f775f95369ba7d88a5cb8b6f1900241699d79351Chris Lattner } 10380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 10480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner 1055e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // If we are inlining for an invoke instruction, we must make sure to rewrite 1065e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // any inlined 'unwind' instructions into branches to the invoke exception 1075e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // destination, and call instructions into invoke instructions. 1085e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 109aeb2a1d70807aa626f335fb23d47bc604ffeaa15Chris Lattner BasicBlock *InvokeDest = II->getUnwindDest(); 1105e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner std::vector<Value*> InvokeDestPHIValues; 1115e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 1125e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // If there are PHI nodes in the exceptional destination block, we need to 1135e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // keep track of which values came into them from this invoke, then remove 1145e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // the entry for this block. 1155e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (BasicBlock::iterator I = InvokeDest->begin(); 1165e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) 1175e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Save the value to use for this edge... 1185e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(OrigBB)); 1195e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 1205e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 1215e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BB != E; ++BB) { 12280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 12380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner // We only need to check for function calls: inlined invoke instructions 12480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner // require no special handling... 12580a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner if (CallInst *CI = dyn_cast<CallInst>(I)) { 126e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner // Convert this function call into an invoke instruction... 127e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner 128e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner // First, split the basic block... 129e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc"); 130e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner 131e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner // Next, create the new invoke instruction, inserting it at the end 132e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner // of the old basic block. 133e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner InvokeInst *II = 134e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner new InvokeInst(CI->getCalledValue(), Split, InvokeDest, 135e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner std::vector<Value*>(CI->op_begin()+1, CI->op_end()), 136e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner CI->getName(), BB->getTerminator()); 137e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner 138e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner // Make sure that anything using the call now uses the invoke! 139e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner CI->replaceAllUsesWith(II); 140e07007c2bd0dcb775ff3eecabb4c31ce8dc5fab0Chris Lattner 141e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner // Delete the unconditional branch inserted by splitBasicBlock 142e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner BB->getInstList().pop_back(); 143e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner Split->getInstList().pop_front(); // Delete the original call 144e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner 14551d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // Update any PHI nodes in the exceptional block to indicate that 14651d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // there is now a new entry in them. 14751d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner unsigned i = 0; 14851d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner for (BasicBlock::iterator I = InvokeDest->begin(); 14951d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I, ++i) 15051d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner PN->addIncoming(InvokeDestPHIValues[i], BB); 15151d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner 152e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner // This basic block is now complete, start scanning the next one. 153e4d90964096c240c9e29ae414792ed1246db4ee8Chris Lattner break; 15480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } else { 15580a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner ++I; 15680a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 15780a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 158ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 159ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 160ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // An UnwindInst requires special handling when it gets inlined into an 161ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // invoke site. Once this happens, we know that the unwind would cause 162ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // a control transfer to the invoke exception destination, so we can 163ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // transform it into a direct branch to the exception destination. 164f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner new BranchInst(InvokeDest, UI); 165ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner 166ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // Delete the unwind instruction! 167ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner UI->getParent()->getInstList().pop_back(); 168198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner 169198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner // Update any PHI nodes in the exceptional block to indicate that 170198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner // there is now a new entry in them. 171198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner unsigned i = 0; 172198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner for (BasicBlock::iterator I = InvokeDest->begin(); 173198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I, ++i) 174198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner PN->addIncoming(InvokeDestPHIValues[i], BB); 175ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner } 176ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner } 177ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner 17851d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // Now that everything is happy, we have one final detail. The PHI nodes in 17951d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // the exception destination block still have entries due to the original 18051d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // invoke instruction. Eliminate these entries (which might even delete the 18151d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // PHI node) now. 1825e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner InvokeDest->removePredecessor(II->getParent()); 18351d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner } 1845e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 18544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If we cloned in _exactly one_ basic block, and if that block ends in a 18644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // return instruction, we splice the body of the inlined callee directly into 18744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // the calling basic block. 18844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) { 18944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Move all of the instructions right before the call. 19044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(), 19144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner FirstNewBlock->begin(), FirstNewBlock->end()); 19244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Remove the cloned basic block. 19344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Caller->getBasicBlockList().pop_back(); 19444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 19544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If the call site was an invoke instruction, add a branch to the normal 19644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // destination. 19744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) 19844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner new BranchInst(II->getNormalDest(), TheCall); 19944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 20044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If the return instruction returned a value, replace uses of the call with 20144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // uses of the returned value. 20244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (!TheCall->use_empty()) 20344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 20444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 20544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Since we are now done with the Call/Invoke, we can delete it. 20644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TheCall->getParent()->getInstList().erase(TheCall); 20744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 20844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Since we are now done with the return instruction, delete it also. 20944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Returns[0]->getParent()->getInstList().erase(Returns[0]); 21044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 21144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // We are now done with the inlining. 21244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner return true; 21344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner } 21444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 21544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Otherwise, we have the normal case, of more than one block to inline or 21644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // multiple return sites. 21744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2185e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // We want to clone the entire callee function into the hole between the 2195e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // "starter" and "ender" blocks. How we accomplish this depends on whether 2205e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // this is an invoke instruction or a call instruction. 2215e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BasicBlock *AfterCallBB; 2225e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 22344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2245e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Add an unconditional branch to make this look like the CallInst case... 2255e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BranchInst *NewBr = new BranchInst(II->getNormalDest(), TheCall); 22644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2275e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Split the basic block. This guarantees that no PHI nodes will have to be 2285e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // updated due to new incoming edges, and make the invoke case more 2295e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // symmetric to the call case. 2305e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner AfterCallBB = OrigBB->splitBasicBlock(NewBr, 2315e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CalledFunc->getName()+".entry"); 23244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2335e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } else { // It's a call 23444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If this is a call instruction, we need to split the basic block that 23544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // the call lives in. 2365e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 2375e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner AfterCallBB = OrigBB->splitBasicBlock(TheCall, 2385e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CalledFunc->getName()+".entry"); 2395e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 2405e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 24144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Change the branch that used to go to AfterCallBB to branch to the first 24244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // basic block of the inlined function. 24344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // 24444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TerminatorInst *Br = OrigBB->getTerminator(); 24544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner assert(Br && Br->getOpcode() == Instruction::Br && 24644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner "splitBasicBlock broken!"); 24744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Br->setOperand(0, FirstNewBlock); 24844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 24944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 25044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Now that the function is correct, make it a little bit nicer. In 25144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // particular, move the basic blocks inserted from the end of the function 25244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // into the space made by splitting the source basic block. 25344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // 25444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(), 25544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner FirstNewBlock, Caller->end()); 25644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2575e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Handle all of the return instructions that we just cloned in, and eliminate 2585e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // any users of the original call/invoke instruction. 2595e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (Returns.size() > 1) { 2605e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // The PHI node should go at the front of the new basic block to merge all 2615e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // possible incoming values. 2625e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 2635e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHINode *PHI = 0; 2645e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (!TheCall->use_empty()) { 2655e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHI = new PHINode(CalledFunc->getReturnType(), 2665e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner TheCall->getName(), AfterCallBB->begin()); 26744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2685e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Anything that used the result of the function call should now use the 2695e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // PHI node as their operand. 2705e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 2715e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner TheCall->replaceAllUsesWith(PHI); 2725e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 27344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2745e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Loop over all of the return instructions, turning them into unconditional 2755e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // branches to the merge point now, and adding entries to the PHI node as 2765e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // appropriate. 2775e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 2785e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner ReturnInst *RI = Returns[i]; 27944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2805e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (PHI) { 2815e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner assert(RI->getReturnValue() && "Ret should have value!"); 2825e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner assert(RI->getReturnValue()->getType() == PHI->getType() && 2835e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner "Ret value not consistent in function!"); 2845e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHI->addIncoming(RI->getReturnValue(), RI->getParent()); 2855e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 28644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2875e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Add a branch to the merge point where the PHI node lives if it exists. 2885e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner new BranchInst(AfterCallBB, RI); 28944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2905e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Delete the return instruction now 2915e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner RI->getParent()->getInstList().erase(RI); 2925e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 29344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2945e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } else if (!Returns.empty()) { 2955e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Otherwise, if there is exactly one return value, just replace anything 2965e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // using the return value of the call with the computed value. 2975e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (!TheCall->use_empty()) 2985e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 29944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 3005e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Add a branch to the merge point where the PHI node lives if it exists. 3015e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner new BranchInst(AfterCallBB, Returns[0]); 30244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 3035e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Delete the return instruction now 3045e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner Returns[0]->getParent()->getInstList().erase(Returns[0]); 3055e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 30644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 3075e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Since we are now done with the Call/Invoke, we can delete it. 30844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TheCall->getParent()->getInstList().erase(TheCall); 309ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 3107152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // We should always be able to fold the entry block of the function into the 3117152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // single predecessor of the block... 31244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner assert(cast<BranchInst>(Br)->isUnconditional() &&"splitBasicBlock broken!"); 3137152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 3147152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner SimplifyCFG(CalleeEntry); 31544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 3167152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // Okay, continue the CFG cleanup. It's often the case that there is only a 3177152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // single return instruction in the callee function. If this is the case, 31880a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner // then we have an unconditional branch from the return block to the 31980a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner // 'AfterCallBB'. Check for this case, and eliminate the branch is possible. 32080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner SimplifyCFG(AfterCallBB); 32144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 322ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner return true; 323ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner} 324