InlineFunction.cpp revision adfd32f8eefc804dce24d14450c10f592e643e2d
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" 25f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 26ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 27f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::InlineFunction(CallInst *CI) { return InlineFunction(CallSite(CI)); } 28f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::InlineFunction(InvokeInst *II) {return InlineFunction(CallSite(II));} 2980a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner 30ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// InlineFunction - This function inlines the called function into the basic 31ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// block of the caller. This returns false if it is not possible to inline this 32ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// call. The program is still in a well defined state if this occurs though. 33ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 34ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// Note that this only does one level of inlining. For example, if the 35ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 36ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// exists in the instruction stream. Similiarly this will inline a recursive 37ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// function by one level. 38ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 39f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::InlineFunction(CallSite CS) { 4080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner Instruction *TheCall = CS.getInstruction(); 4180a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner assert(TheCall->getParent() && TheCall->getParent()->getParent() && 4280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner "Instruction not in function!"); 43ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 4480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner const Function *CalledFunc = CS.getCalledFunction(); 45ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner if (CalledFunc == 0 || // Can't inline external function or indirect 46ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner CalledFunc->isExternal() || // call, or call to a vararg function! 47ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner CalledFunc->getFunctionType()->isVarArg()) return false; 48ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 4980a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner BasicBlock *OrigBB = TheCall->getParent(); 50ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner Function *Caller = OrigBB->getParent(); 51ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 525052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // Get an iterator to the last basic block in the function, which will have 535052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // the new function inlined after it. 545052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // 555052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner Function::iterator LastBlock = &Caller->back(); 565052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner 575e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Make sure to capture all of the return instructions from the cloned 585e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // function. 595052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner std::vector<ReturnInst*> Returns; 605e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner { // Scope to destroy ValueMap after cloning. 615e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Calculate the vector of arguments to pass into the function cloner... 625e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner std::map<const Value*, Value*> ValueMap; 635e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner assert(std::distance(CalledFunc->abegin(), CalledFunc->aend()) == 645e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner std::distance(CS.arg_begin(), CS.arg_end()) && 655e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner "No varargs calls can be inlined!"); 665e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 675e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CallSite::arg_iterator AI = CS.arg_begin(); 685e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (Function::const_aiterator I = CalledFunc->abegin(), 695e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner E = CalledFunc->aend(); I != E; ++I, ++AI) 705e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner ValueMap[I] = *AI; 715e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 725e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Clone the entire body of the callee into the caller. 735e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CloneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i"); 745e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 75c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner 765e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Remember the first block that is newly cloned over. 775e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner Function::iterator FirstNewBlock = LastBlock; ++FirstNewBlock; 78ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 79ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // If there are any alloca instructions in the block that used to be the entry 80ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // block for the callee, move them to the entry block of the caller. First 81ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // calculate which instruction they should be inserted before. We insert the 82ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // instructions at the end of the current alloca list. 83ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // 845e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (isa<AllocaInst>(FirstNewBlock->begin())) { 8580a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 865e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (BasicBlock::iterator I = FirstNewBlock->begin(), 875e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner E = FirstNewBlock->end(); I != E; ) 88f775f95369ba7d88a5cb8b6f1900241699d79351Chris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I++)) 89f775f95369ba7d88a5cb8b6f1900241699d79351Chris Lattner if (isa<Constant>(AI->getArraySize())) { 90c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // Scan for the block of allocas that we can move over. 91c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner while (isa<AllocaInst>(I) && 92c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner isa<Constant>(cast<AllocaInst>(I)->getArraySize())) 93c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner ++I; 94c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner 95c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // Transfer all of the allocas over in a block. Using splice means 96c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // that they instructions aren't removed from the symbol table, then 97c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner // reinserted. 98c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner Caller->front().getInstList().splice(InsertPoint, 99c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner FirstNewBlock->getInstList(), 100c1df7e1799a7a97602bdedec818f7ab1dc514b4eChris Lattner AI, I); 101f775f95369ba7d88a5cb8b6f1900241699d79351Chris Lattner } 10280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 10380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner 1045e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // If we are inlining for an invoke instruction, we must make sure to rewrite 1055e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // any inlined 'unwind' instructions into branches to the invoke exception 1065e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // destination, and call instructions into invoke instructions. 1075e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 108aeb2a1d70807aa626f335fb23d47bc604ffeaa15Chris Lattner BasicBlock *InvokeDest = II->getUnwindDest(); 1095e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner std::vector<Value*> InvokeDestPHIValues; 1105e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 1115e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // If there are PHI nodes in the exceptional destination block, we need to 1125e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // keep track of which values came into them from this invoke, then remove 1135e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // the entry for this block. 1145e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (BasicBlock::iterator I = InvokeDest->begin(); 1155e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) 1165e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Save the value to use for this edge... 1175e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(OrigBB)); 1185e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 1195e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 1205e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BB != E; ++BB) { 12180a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 12280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner // We only need to check for function calls: inlined invoke instructions 12380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner // require no special handling... 12480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner if (CallInst *CI = dyn_cast<CallInst>(I)) { 125494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // Convert this function call into an invoke instruction... if it's 126494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // not an intrinsic function call (which are known to not throw). 127494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner if (CI->getCalledFunction() && 128494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner CI->getCalledFunction()->getIntrinsicID()) { 129494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner ++I; 130494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner } else { 131494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // First, split the basic block... 132494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc"); 133494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner 134494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // Next, create the new invoke instruction, inserting it at the end 135494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // of the old basic block. 136494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner InvokeInst *II = 137494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner new InvokeInst(CI->getCalledValue(), Split, InvokeDest, 138494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner std::vector<Value*>(CI->op_begin()+1, CI->op_end()), 139494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner CI->getName(), BB->getTerminator()); 140494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner 141494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // Make sure that anything using the call now uses the invoke! 142494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner CI->replaceAllUsesWith(II); 143494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner 144494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // Delete the unconditional branch inserted by splitBasicBlock 145494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner BB->getInstList().pop_back(); 146494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner Split->getInstList().pop_front(); // Delete the original call 147494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner 148494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // Update any PHI nodes in the exceptional block to indicate that 149494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // there is now a new entry in them. 150494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner unsigned i = 0; 151494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner for (BasicBlock::iterator I = InvokeDest->begin(); 152494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I, ++i) 153494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner PN->addIncoming(InvokeDestPHIValues[i], BB); 154494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner 155494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner // This basic block is now complete, start scanning the next one. 156494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner break; 157494b6920b067ec663b28c644f151fe61ef8b4e71Chris Lattner } 15880a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } else { 15980a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner ++I; 16080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 16180a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 162ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 163ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 164ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // An UnwindInst requires special handling when it gets inlined into an 165ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // invoke site. Once this happens, we know that the unwind would cause 166ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // a control transfer to the invoke exception destination, so we can 167ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // transform it into a direct branch to the exception destination. 168f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner new BranchInst(InvokeDest, UI); 169ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner 170ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // Delete the unwind instruction! 171ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner UI->getParent()->getInstList().pop_back(); 172198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner 173198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner // Update any PHI nodes in the exceptional block to indicate that 174198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner // there is now a new entry in them. 175198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner unsigned i = 0; 176198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner for (BasicBlock::iterator I = InvokeDest->begin(); 177198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I, ++i) 178198f4507e2ff934a8ac3aa0a82526fa6a153b70bChris Lattner PN->addIncoming(InvokeDestPHIValues[i], BB); 179ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner } 180ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner } 181ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner 18251d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // Now that everything is happy, we have one final detail. The PHI nodes in 18351d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // the exception destination block still have entries due to the original 18451d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // invoke instruction. Eliminate these entries (which might even delete the 18551d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner // PHI node) now. 1865e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner InvokeDest->removePredecessor(II->getParent()); 18751d6816089a66c171dc23b50d62989ac6bb5c491Chris Lattner } 1885e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 18944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If we cloned in _exactly one_ basic block, and if that block ends in a 19044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // return instruction, we splice the body of the inlined callee directly into 19144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // the calling basic block. 19244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) { 19344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Move all of the instructions right before the call. 19444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(), 19544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner FirstNewBlock->begin(), FirstNewBlock->end()); 19644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Remove the cloned basic block. 19744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Caller->getBasicBlockList().pop_back(); 19844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 19944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If the call site was an invoke instruction, add a branch to the normal 20044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // destination. 20144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) 20244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner new BranchInst(II->getNormalDest(), TheCall); 20344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 20444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If the return instruction returned a value, replace uses of the call with 20544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // uses of the returned value. 20644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (!TheCall->use_empty()) 20744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 20844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 20944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Since we are now done with the Call/Invoke, we can delete it. 21044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TheCall->getParent()->getInstList().erase(TheCall); 21144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 21244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Since we are now done with the return instruction, delete it also. 21344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Returns[0]->getParent()->getInstList().erase(Returns[0]); 21444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 21544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // We are now done with the inlining. 21644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner return true; 21744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner } 21844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 21944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Otherwise, we have the normal case, of more than one block to inline or 22044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // multiple return sites. 22144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2225e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // We want to clone the entire callee function into the hole between the 2235e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // "starter" and "ender" blocks. How we accomplish this depends on whether 2245e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // this is an invoke instruction or a call instruction. 2255e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BasicBlock *AfterCallBB; 2265e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 22744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2285e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Add an unconditional branch to make this look like the CallInst case... 2295e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BranchInst *NewBr = new BranchInst(II->getNormalDest(), TheCall); 23044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2315e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Split the basic block. This guarantees that no PHI nodes will have to be 2325e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // updated due to new incoming edges, and make the invoke case more 2335e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // symmetric to the call case. 2345e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner AfterCallBB = OrigBB->splitBasicBlock(NewBr, 2355e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CalledFunc->getName()+".entry"); 23644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2375e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } else { // It's a call 23844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If this is a call instruction, we need to split the basic block that 23944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // the call lives in. 2405e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 2415e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner AfterCallBB = OrigBB->splitBasicBlock(TheCall, 2425e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CalledFunc->getName()+".entry"); 2435e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 2445e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 24544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Change the branch that used to go to AfterCallBB to branch to the first 24644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // basic block of the inlined function. 24744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // 24844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TerminatorInst *Br = OrigBB->getTerminator(); 24944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner assert(Br && Br->getOpcode() == Instruction::Br && 25044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner "splitBasicBlock broken!"); 25144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Br->setOperand(0, FirstNewBlock); 25244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 25344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 25444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Now that the function is correct, make it a little bit nicer. In 25544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // particular, move the basic blocks inserted from the end of the function 25644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // into the space made by splitting the source basic block. 25744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // 25844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(), 25944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner FirstNewBlock, Caller->end()); 26044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2615e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Handle all of the return instructions that we just cloned in, and eliminate 2625e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // any users of the original call/invoke instruction. 2635e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (Returns.size() > 1) { 2645e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // The PHI node should go at the front of the new basic block to merge all 2655e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // possible incoming values. 2665e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 2675e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHINode *PHI = 0; 2685e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (!TheCall->use_empty()) { 2695e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHI = new PHINode(CalledFunc->getReturnType(), 2705e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner TheCall->getName(), AfterCallBB->begin()); 27144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2725e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Anything that used the result of the function call should now use the 2735e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // PHI node as their operand. 2745e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 2755e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner TheCall->replaceAllUsesWith(PHI); 2765e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 27744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2785e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Loop over all of the return instructions, turning them into unconditional 2795e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // branches to the merge point now, and adding entries to the PHI node as 2805e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // appropriate. 2815e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 2825e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner ReturnInst *RI = Returns[i]; 28344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2845e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (PHI) { 2855e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner assert(RI->getReturnValue() && "Ret should have value!"); 2865e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner assert(RI->getReturnValue()->getType() == PHI->getType() && 2875e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner "Ret value not consistent in function!"); 2885e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner PHI->addIncoming(RI->getReturnValue(), RI->getParent()); 2895e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 29044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2915e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Add a branch to the merge point where the PHI node lives if it exists. 2925e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner new BranchInst(AfterCallBB, RI); 29344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2945e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Delete the return instruction now 2955e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner RI->getParent()->getInstList().erase(RI); 2965e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 29744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 2985e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } else if (!Returns.empty()) { 2995e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Otherwise, if there is exactly one return value, just replace anything 3005e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // using the return value of the call with the computed value. 3015e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (!TheCall->use_empty()) 3025e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 30344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 304cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Splice the code from the return block into the block that it will return 305cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // to, which contains the code that was after the call. 306cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner BasicBlock *ReturnBB = Returns[0]->getParent(); 307adfd32f8eefc804dce24d14450c10f592e643e2dChris Lattner AfterCallBB->getInstList().splice(AfterCallBB->begin(), 308adfd32f8eefc804dce24d14450c10f592e643e2dChris Lattner ReturnBB->getInstList()); 309cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner 310adfd32f8eefc804dce24d14450c10f592e643e2dChris Lattner // Update PHI nodes that use the ReturnBB to use the AfterCallBB. 311adfd32f8eefc804dce24d14450c10f592e643e2dChris Lattner ReturnBB->replaceAllUsesWith(AfterCallBB); 31244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 313adfd32f8eefc804dce24d14450c10f592e643e2dChris Lattner // Delete the return instruction now and empty ReturnBB now. 3145e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner Returns[0]->getParent()->getInstList().erase(Returns[0]); 315adfd32f8eefc804dce24d14450c10f592e643e2dChris Lattner Caller->getBasicBlockList().erase(ReturnBB); 3165e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 31744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 3185e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Since we are now done with the Call/Invoke, we can delete it. 31944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TheCall->getParent()->getInstList().erase(TheCall); 320ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 3217152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // We should always be able to fold the entry block of the function into the 3227152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // single predecessor of the block... 323cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!"); 3247152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 32544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 326cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Splice the code entry block into calling block, right before the 327cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // unconditional branch. 328cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); 329cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes 330cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner 331cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Remove the unconditional branch. 332cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner OrigBB->getInstList().erase(Br); 333cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner 334cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Now we can remove the CalleeEntry block, which is now empty. 335cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner Caller->getBasicBlockList().erase(CalleeEntry); 336ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner return true; 337ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner} 338