LLVM API Documentation
00001 //===- InlineFunction.cpp - Code to perform function inlining -------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements inlining of a function into a call site, resolving 00011 // parameters and the return value as appropriate. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Transforms/Utils/Cloning.h" 00016 #include "llvm/Constants.h" 00017 #include "llvm/DerivedTypes.h" 00018 #include "llvm/LLVMContext.h" 00019 #include "llvm/Module.h" 00020 #include "llvm/Instructions.h" 00021 #include "llvm/IntrinsicInst.h" 00022 #include "llvm/Intrinsics.h" 00023 #include "llvm/Attributes.h" 00024 #include "llvm/Analysis/CallGraph.h" 00025 #include "llvm/Analysis/DebugInfo.h" 00026 #include "llvm/Target/TargetData.h" 00027 #include "llvm/ADT/SmallVector.h" 00028 #include "llvm/ADT/StringExtras.h" 00029 #include "llvm/Support/CallSite.h" 00030 using namespace llvm; 00031 00032 bool llvm::InlineFunction(CallInst *CI, CallGraph *CG, const TargetData *TD) { 00033 return InlineFunction(CallSite(CI), CG, TD); 00034 } 00035 bool llvm::InlineFunction(InvokeInst *II, CallGraph *CG, const TargetData *TD) { 00036 return InlineFunction(CallSite(II), CG, TD); 00037 } 00038 00039 /// HandleInlinedInvoke - If we inlined an invoke site, we need to convert calls 00040 /// in the body of the inlined function into invokes and turn unwind 00041 /// instructions into branches to the invoke unwind dest. 00042 /// 00043 /// II is the invoke instruction being inlined. FirstNewBlock is the first 00044 /// block of the inlined code (the last block is the end of the function), 00045 /// and InlineCodeInfo is information about the code that got inlined. 00046 static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock, 00047 ClonedCodeInfo &InlinedCodeInfo, 00048 CallGraph *CG) { 00049 BasicBlock *InvokeDest = II->getUnwindDest(); 00050 std::vector<Value*> InvokeDestPHIValues; 00051 00052 // If there are PHI nodes in the unwind destination block, we need to 00053 // keep track of which values came into them from this invoke, then remove 00054 // the entry for this block. 00055 BasicBlock *InvokeBlock = II->getParent(); 00056 for (BasicBlock::iterator I = InvokeDest->begin(); isa<PHINode>(I); ++I) { 00057 PHINode *PN = cast<PHINode>(I); 00058 // Save the value to use for this edge. 00059 InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(InvokeBlock)); 00060 } 00061 00062 Function *Caller = FirstNewBlock->getParent(); 00063 00064 // The inlined code is currently at the end of the function, scan from the 00065 // start of the inlined code to its end, checking for stuff we need to 00066 // rewrite. 00067 if (InlinedCodeInfo.ContainsCalls || InlinedCodeInfo.ContainsUnwinds) { 00068 for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 00069 BB != E; ++BB) { 00070 if (InlinedCodeInfo.ContainsCalls) { 00071 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ){ 00072 Instruction *I = BBI++; 00073 00074 // We only need to check for function calls: inlined invoke 00075 // instructions require no special handling. 00076 if (!isa<CallInst>(I)) continue; 00077 CallInst *CI = cast<CallInst>(I); 00078 00079 // If this call cannot unwind, don't convert it to an invoke. 00080 if (CI->doesNotThrow()) 00081 continue; 00082 00083 // Convert this function call into an invoke instruction. 00084 // First, split the basic block. 00085 BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc"); 00086 00087 // Next, create the new invoke instruction, inserting it at the end 00088 // of the old basic block. 00089 SmallVector<Value*, 8> InvokeArgs(CI->op_begin()+1, CI->op_end()); 00090 InvokeInst *II = 00091 InvokeInst::Create(CI->getCalledValue(), Split, InvokeDest, 00092 InvokeArgs.begin(), InvokeArgs.end(), 00093 CI->getName(), BB->getTerminator()); 00094 II->setCallingConv(CI->getCallingConv()); 00095 II->setAttributes(CI->getAttributes()); 00096 00097 // Make sure that anything using the call now uses the invoke! 00098 CI->replaceAllUsesWith(II); 00099 00100 // Update the callgraph. 00101 if (CG) { 00102 // We should be able to do this: 00103 // (*CG)[Caller]->replaceCallSite(CI, II); 00104 // but that fails if the old call site isn't in the call graph, 00105 // which, because of LLVM bug 3601, it sometimes isn't. 00106 CallGraphNode *CGN = (*CG)[Caller]; 00107 for (CallGraphNode::iterator NI = CGN->begin(), NE = CGN->end(); 00108 NI != NE; ++NI) { 00109 if (NI->first == CI) { 00110 NI->first = II; 00111 break; 00112 } 00113 } 00114 } 00115 00116 // Delete the unconditional branch inserted by splitBasicBlock 00117 BB->getInstList().pop_back(); 00118 Split->getInstList().pop_front(); // Delete the original call 00119 00120 // Update any PHI nodes in the exceptional block to indicate that 00121 // there is now a new entry in them. 00122 unsigned i = 0; 00123 for (BasicBlock::iterator I = InvokeDest->begin(); 00124 isa<PHINode>(I); ++I, ++i) { 00125 PHINode *PN = cast<PHINode>(I); 00126 PN->addIncoming(InvokeDestPHIValues[i], BB); 00127 } 00128 00129 // This basic block is now complete, start scanning the next one. 00130 break; 00131 } 00132 } 00133 00134 if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 00135 // An UnwindInst requires special handling when it gets inlined into an 00136 // invoke site. Once this happens, we know that the unwind would cause 00137 // a control transfer to the invoke exception destination, so we can 00138 // transform it into a direct branch to the exception destination. 00139 BranchInst::Create(InvokeDest, UI); 00140 00141 // Delete the unwind instruction! 00142 UI->eraseFromParent(); 00143 00144 // Update any PHI nodes in the exceptional block to indicate that 00145 // there is now a new entry in them. 00146 unsigned i = 0; 00147 for (BasicBlock::iterator I = InvokeDest->begin(); 00148 isa<PHINode>(I); ++I, ++i) { 00149 PHINode *PN = cast<PHINode>(I); 00150 PN->addIncoming(InvokeDestPHIValues[i], BB); 00151 } 00152 } 00153 } 00154 } 00155 00156 // Now that everything is happy, we have one final detail. The PHI nodes in 00157 // the exception destination block still have entries due to the original 00158 // invoke instruction. Eliminate these entries (which might even delete the 00159 // PHI node) now. 00160 InvokeDest->removePredecessor(II->getParent()); 00161 } 00162 00163 /// UpdateCallGraphAfterInlining - Once we have cloned code over from a callee 00164 /// into the caller, update the specified callgraph to reflect the changes we 00165 /// made. Note that it's possible that not all code was copied over, so only 00166 /// some edges of the callgraph may remain. 00167 static void UpdateCallGraphAfterInlining(CallSite CS, 00168 Function::iterator FirstNewBlock, 00169 DenseMap<const Value*, Value*> &ValueMap, 00170 CallGraph &CG) { 00171 const Function *Caller = CS.getInstruction()->getParent()->getParent(); 00172 const Function *Callee = CS.getCalledFunction(); 00173 CallGraphNode *CalleeNode = CG[Callee]; 00174 CallGraphNode *CallerNode = CG[Caller]; 00175 00176 // Since we inlined some uninlined call sites in the callee into the caller, 00177 // add edges from the caller to all of the callees of the callee. 00178 CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end(); 00179 00180 // Consider the case where CalleeNode == CallerNode. 00181 CallGraphNode::CalledFunctionsVector CallCache; 00182 if (CalleeNode == CallerNode) { 00183 CallCache.assign(I, E); 00184 I = CallCache.begin(); 00185 E = CallCache.end(); 00186 } 00187 00188 for (; I != E; ++I) { 00189 const Instruction *OrigCall = I->first.getInstruction(); 00190 00191 DenseMap<const Value*, Value*>::iterator VMI = ValueMap.find(OrigCall); 00192 // Only copy the edge if the call was inlined! 00193 if (VMI != ValueMap.end() && VMI->second) { 00194 // If the call was inlined, but then constant folded, there is no edge to 00195 // add. Check for this case. 00196 if (Instruction *NewCall = dyn_cast<Instruction>(VMI->second)) 00197 CallerNode->addCalledFunction(CallSite::get(NewCall), I->second); 00198 } 00199 } 00200 // Update the call graph by deleting the edge from Callee to Caller. We must 00201 // do this after the loop above in case Caller and Callee are the same. 00202 CallerNode->removeCallEdgeFor(CS); 00203 } 00204 00205 /// findFnRegionEndMarker - This is a utility routine that is used by 00206 /// InlineFunction. Return llvm.dbg.region.end intrinsic that corresponds 00207 /// to the llvm.dbg.func.start of the function F. Otherwise return NULL. 00208 static const DbgRegionEndInst *findFnRegionEndMarker(const Function *F) { 00209 00210 GlobalVariable *FnStart = NULL; 00211 const DbgRegionEndInst *FnEnd = NULL; 00212 for (Function::const_iterator FI = F->begin(), FE =F->end(); FI != FE; ++FI) 00213 for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end(); BI != BE; 00214 ++BI) { 00215 if (FnStart == NULL) { 00216 if (const DbgFuncStartInst *FSI = dyn_cast<DbgFuncStartInst>(BI)) { 00217 DISubprogram SP(cast<GlobalVariable>(FSI->getSubprogram())); 00218 assert (SP.isNull() == false && "Invalid llvm.dbg.func.start"); 00219 if (SP.describes(F)) 00220 FnStart = SP.getGV(); 00221 } 00222 } else { 00223 if (const DbgRegionEndInst *REI = dyn_cast<DbgRegionEndInst>(BI)) 00224 if (REI->getContext() == FnStart) 00225 FnEnd = REI; 00226 } 00227 } 00228 return FnEnd; 00229 } 00230 00231 // InlineFunction - This function inlines the called function into the basic 00232 // block of the caller. This returns false if it is not possible to inline this 00233 // call. The program is still in a well defined state if this occurs though. 00234 // 00235 // Note that this only does one level of inlining. For example, if the 00236 // instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 00237 // exists in the instruction stream. Similiarly this will inline a recursive 00238 // function by one level. 00239 // 00240 bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD) { 00241 Instruction *TheCall = CS.getInstruction(); 00242 LLVMContext &Context = TheCall->getContext(); 00243 assert(TheCall->getParent() && TheCall->getParent()->getParent() && 00244 "Instruction not in function!"); 00245 00246 const Function *CalledFunc = CS.getCalledFunction(); 00247 if (CalledFunc == 0 || // Can't inline external function or indirect 00248 CalledFunc->isDeclaration() || // call, or call to a vararg function! 00249 CalledFunc->getFunctionType()->isVarArg()) return false; 00250 00251 00252 // If the call to the callee is not a tail call, we must clear the 'tail' 00253 // flags on any calls that we inline. 00254 bool MustClearTailCallFlags = 00255 !(isa<CallInst>(TheCall) && cast<CallInst>(TheCall)->isTailCall()); 00256 00257 // If the call to the callee cannot throw, set the 'nounwind' flag on any 00258 // calls that we inline. 00259 bool MarkNoUnwind = CS.doesNotThrow(); 00260 00261 BasicBlock *OrigBB = TheCall->getParent(); 00262 Function *Caller = OrigBB->getParent(); 00263 00264 // GC poses two hazards to inlining, which only occur when the callee has GC: 00265 // 1. If the caller has no GC, then the callee's GC must be propagated to the 00266 // caller. 00267 // 2. If the caller has a differing GC, it is invalid to inline. 00268 if (CalledFunc->hasGC()) { 00269 if (!Caller->hasGC()) 00270 Caller->setGC(CalledFunc->getGC()); 00271 else if (CalledFunc->getGC() != Caller->getGC()) 00272 return false; 00273 } 00274 00275 // Get an iterator to the last basic block in the function, which will have 00276 // the new function inlined after it. 00277 // 00278 Function::iterator LastBlock = &Caller->back(); 00279 00280 // Make sure to capture all of the return instructions from the cloned 00281 // function. 00282 std::vector<ReturnInst*> Returns; 00283 ClonedCodeInfo InlinedFunctionInfo; 00284 Function::iterator FirstNewBlock; 00285 00286 { // Scope to destroy ValueMap after cloning. 00287 DenseMap<const Value*, Value*> ValueMap; 00288 00289 assert(CalledFunc->arg_size() == CS.arg_size() && 00290 "No varargs calls can be inlined!"); 00291 00292 // Calculate the vector of arguments to pass into the function cloner, which 00293 // matches up the formal to the actual argument values. 00294 CallSite::arg_iterator AI = CS.arg_begin(); 00295 unsigned ArgNo = 0; 00296 for (Function::const_arg_iterator I = CalledFunc->arg_begin(), 00297 E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) { 00298 Value *ActualArg = *AI; 00299 00300 // When byval arguments actually inlined, we need to make the copy implied 00301 // by them explicit. However, we don't do this if the callee is readonly 00302 // or readnone, because the copy would be unneeded: the callee doesn't 00303 // modify the struct. 00304 if (CalledFunc->paramHasAttr(ArgNo+1, Attribute::ByVal) && 00305 !CalledFunc->onlyReadsMemory()) { 00306 const Type *AggTy = cast<PointerType>(I->getType())->getElementType(); 00307 const Type *VoidPtrTy = 00308 PointerType::getUnqual(Type::getInt8Ty(Context)); 00309 00310 // Create the alloca. If we have TargetData, use nice alignment. 00311 unsigned Align = 1; 00312 if (TD) Align = TD->getPrefTypeAlignment(AggTy); 00313 Value *NewAlloca = new AllocaInst(AggTy, 0, Align, 00314 I->getName(), 00315 &*Caller->begin()->begin()); 00316 // Emit a memcpy. 00317 const Type *Tys[] = { Type::getInt64Ty(Context) }; 00318 Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(), 00319 Intrinsic::memcpy, 00320 Tys, 1); 00321 Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall); 00322 Value *SrcCast = new BitCastInst(*AI, VoidPtrTy, "tmp", TheCall); 00323 00324 Value *Size; 00325 if (TD == 0) 00326 Size = ConstantExpr::getSizeOf(AggTy); 00327 else 00328 Size = ConstantInt::get(Type::getInt64Ty(Context), 00329 TD->getTypeStoreSize(AggTy)); 00330 00331 // Always generate a memcpy of alignment 1 here because we don't know 00332 // the alignment of the src pointer. Other optimizations can infer 00333 // better alignment. 00334 Value *CallArgs[] = { 00335 DestCast, SrcCast, Size, 00336 ConstantInt::get(Type::getInt32Ty(Context), 1) 00337 }; 00338 CallInst *TheMemCpy = 00339 CallInst::Create(MemCpyFn, CallArgs, CallArgs+4, "", TheCall); 00340 00341 // If we have a call graph, update it. 00342 if (CG) { 00343 CallGraphNode *MemCpyCGN = CG->getOrInsertFunction(MemCpyFn); 00344 CallGraphNode *CallerNode = (*CG)[Caller]; 00345 CallerNode->addCalledFunction(TheMemCpy, MemCpyCGN); 00346 } 00347 00348 // Uses of the argument in the function should use our new alloca 00349 // instead. 00350 ActualArg = NewAlloca; 00351 } 00352 00353 ValueMap[I] = ActualArg; 00354 } 00355 00356 // Adjust llvm.dbg.region.end. If the CalledFunc has region end 00357 // marker then clone that marker after next stop point at the 00358 // call site. The function body cloner does not clone original 00359 // region end marker from the CalledFunc. This will ensure that 00360 // inlined function's scope ends at the right place. 00361 const DbgRegionEndInst *DREI = findFnRegionEndMarker(CalledFunc); 00362 if (DREI) { 00363 for (BasicBlock::iterator BI = TheCall, 00364 BE = TheCall->getParent()->end(); BI != BE; ++BI) { 00365 if (DbgStopPointInst *DSPI = dyn_cast<DbgStopPointInst>(BI)) { 00366 if (DbgRegionEndInst *NewDREI = 00367 dyn_cast<DbgRegionEndInst>(DREI->clone(Context))) 00368 NewDREI->insertAfter(DSPI); 00369 break; 00370 } 00371 } 00372 } 00373 00374 // We want the inliner to prune the code as it copies. We would LOVE to 00375 // have no dead or constant instructions leftover after inlining occurs 00376 // (which can happen, e.g., because an argument was constant), but we'll be 00377 // happy with whatever the cloner can do. 00378 CloneAndPruneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i", 00379 &InlinedFunctionInfo, TD); 00380 00381 // Remember the first block that is newly cloned over. 00382 FirstNewBlock = LastBlock; ++FirstNewBlock; 00383 00384 // Update the callgraph if requested. 00385 if (CG) 00386 UpdateCallGraphAfterInlining(CS, FirstNewBlock, ValueMap, *CG); 00387 } 00388 00389 // If there are any alloca instructions in the block that used to be the entry 00390 // block for the callee, move them to the entry block of the caller. First 00391 // calculate which instruction they should be inserted before. We insert the 00392 // instructions at the end of the current alloca list. 00393 // 00394 { 00395 BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 00396 for (BasicBlock::iterator I = FirstNewBlock->begin(), 00397 E = FirstNewBlock->end(); I != E; ) 00398 if (AllocaInst *AI = dyn_cast<AllocaInst>(I++)) { 00399 // If the alloca is now dead, remove it. This often occurs due to code 00400 // specialization. 00401 if (AI->use_empty()) { 00402 AI->eraseFromParent(); 00403 continue; 00404 } 00405 00406 if (isa<Constant>(AI->getArraySize())) { 00407 // Scan for the block of allocas that we can move over, and move them 00408 // all at once. 00409 while (isa<AllocaInst>(I) && 00410 isa<Constant>(cast<AllocaInst>(I)->getArraySize())) 00411 ++I; 00412 00413 // Transfer all of the allocas over in a block. Using splice means 00414 // that the instructions aren't removed from the symbol table, then 00415 // reinserted. 00416 Caller->getEntryBlock().getInstList().splice( 00417 InsertPoint, 00418 FirstNewBlock->getInstList(), 00419 AI, I); 00420 } 00421 } 00422 } 00423 00424 // If the inlined code contained dynamic alloca instructions, wrap the inlined 00425 // code with llvm.stacksave/llvm.stackrestore intrinsics. 00426 if (InlinedFunctionInfo.ContainsDynamicAllocas) { 00427 Module *M = Caller->getParent(); 00428 // Get the two intrinsics we care about. 00429 Constant *StackSave, *StackRestore; 00430 StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave); 00431 StackRestore = Intrinsic::getDeclaration(M, Intrinsic::stackrestore); 00432 00433 // If we are preserving the callgraph, add edges to the stacksave/restore 00434 // functions for the calls we insert. 00435 CallGraphNode *StackSaveCGN = 0, *StackRestoreCGN = 0, *CallerNode = 0; 00436 if (CG) { 00437 // We know that StackSave/StackRestore are Function*'s, because they are 00438 // intrinsics which must have the right types. 00439 StackSaveCGN = CG->getOrInsertFunction(cast<Function>(StackSave)); 00440 StackRestoreCGN = CG->getOrInsertFunction(cast<Function>(StackRestore)); 00441 CallerNode = (*CG)[Caller]; 00442 } 00443 00444 // Insert the llvm.stacksave. 00445 CallInst *SavedPtr = CallInst::Create(StackSave, "savedstack", 00446 FirstNewBlock->begin()); 00447 if (CG) CallerNode->addCalledFunction(SavedPtr, StackSaveCGN); 00448 00449 // Insert a call to llvm.stackrestore before any return instructions in the 00450 // inlined function. 00451 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 00452 CallInst *CI = CallInst::Create(StackRestore, SavedPtr, "", Returns[i]); 00453 if (CG) CallerNode->addCalledFunction(CI, StackRestoreCGN); 00454 } 00455 00456 // Count the number of StackRestore calls we insert. 00457 unsigned NumStackRestores = Returns.size(); 00458 00459 // If we are inlining an invoke instruction, insert restores before each 00460 // unwind. These unwinds will be rewritten into branches later. 00461 if (InlinedFunctionInfo.ContainsUnwinds && isa<InvokeInst>(TheCall)) { 00462 for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 00463 BB != E; ++BB) 00464 if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 00465 CallInst::Create(StackRestore, SavedPtr, "", UI); 00466 ++NumStackRestores; 00467 } 00468 } 00469 } 00470 00471 // If we are inlining tail call instruction through a call site that isn't 00472 // marked 'tail', we must remove the tail marker for any calls in the inlined 00473 // code. Also, calls inlined through a 'nounwind' call site should be marked 00474 // 'nounwind'. 00475 if (InlinedFunctionInfo.ContainsCalls && 00476 (MustClearTailCallFlags || MarkNoUnwind)) { 00477 for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 00478 BB != E; ++BB) 00479 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00480 if (CallInst *CI = dyn_cast<CallInst>(I)) { 00481 if (MustClearTailCallFlags) 00482 CI->setTailCall(false); 00483 if (MarkNoUnwind) 00484 CI->setDoesNotThrow(); 00485 } 00486 } 00487 00488 // If we are inlining through a 'nounwind' call site then any inlined 'unwind' 00489 // instructions are unreachable. 00490 if (InlinedFunctionInfo.ContainsUnwinds && MarkNoUnwind) 00491 for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 00492 BB != E; ++BB) { 00493 TerminatorInst *Term = BB->getTerminator(); 00494 if (isa<UnwindInst>(Term)) { 00495 new UnreachableInst(Context, Term); 00496 BB->getInstList().erase(Term); 00497 } 00498 } 00499 00500 // If we are inlining for an invoke instruction, we must make sure to rewrite 00501 // any inlined 'unwind' instructions into branches to the invoke exception 00502 // destination, and call instructions into invoke instructions. 00503 if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) 00504 HandleInlinedInvoke(II, FirstNewBlock, InlinedFunctionInfo, CG); 00505 00506 // If we cloned in _exactly one_ basic block, and if that block ends in a 00507 // return instruction, we splice the body of the inlined callee directly into 00508 // the calling basic block. 00509 if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) { 00510 // Move all of the instructions right before the call. 00511 OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(), 00512 FirstNewBlock->begin(), FirstNewBlock->end()); 00513 // Remove the cloned basic block. 00514 Caller->getBasicBlockList().pop_back(); 00515 00516 // If the call site was an invoke instruction, add a branch to the normal 00517 // destination. 00518 if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) 00519 BranchInst::Create(II->getNormalDest(), TheCall); 00520 00521 // If the return instruction returned a value, replace uses of the call with 00522 // uses of the returned value. 00523 if (!TheCall->use_empty()) { 00524 ReturnInst *R = Returns[0]; 00525 if (TheCall == R->getReturnValue()) 00526 TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 00527 else 00528 TheCall->replaceAllUsesWith(R->getReturnValue()); 00529 } 00530 // Since we are now done with the Call/Invoke, we can delete it. 00531 TheCall->eraseFromParent(); 00532 00533 // Since we are now done with the return instruction, delete it also. 00534 Returns[0]->eraseFromParent(); 00535 00536 // We are now done with the inlining. 00537 return true; 00538 } 00539 00540 // Otherwise, we have the normal case, of more than one block to inline or 00541 // multiple return sites. 00542 00543 // We want to clone the entire callee function into the hole between the 00544 // "starter" and "ender" blocks. How we accomplish this depends on whether 00545 // this is an invoke instruction or a call instruction. 00546 BasicBlock *AfterCallBB; 00547 if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 00548 00549 // Add an unconditional branch to make this look like the CallInst case... 00550 BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall); 00551 00552 // Split the basic block. This guarantees that no PHI nodes will have to be 00553 // updated due to new incoming edges, and make the invoke case more 00554 // symmetric to the call case. 00555 AfterCallBB = OrigBB->splitBasicBlock(NewBr, 00556 CalledFunc->getName()+".exit"); 00557 00558 } else { // It's a call 00559 // If this is a call instruction, we need to split the basic block that 00560 // the call lives in. 00561 // 00562 AfterCallBB = OrigBB->splitBasicBlock(TheCall, 00563 CalledFunc->getName()+".exit"); 00564 } 00565 00566 // Change the branch that used to go to AfterCallBB to branch to the first 00567 // basic block of the inlined function. 00568 // 00569 TerminatorInst *Br = OrigBB->getTerminator(); 00570 assert(Br && Br->getOpcode() == Instruction::Br && 00571 "splitBasicBlock broken!"); 00572 Br->setOperand(0, FirstNewBlock); 00573 00574 00575 // Now that the function is correct, make it a little bit nicer. In 00576 // particular, move the basic blocks inserted from the end of the function 00577 // into the space made by splitting the source basic block. 00578 Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(), 00579 FirstNewBlock, Caller->end()); 00580 00581 // Handle all of the return instructions that we just cloned in, and eliminate 00582 // any users of the original call/invoke instruction. 00583 const Type *RTy = CalledFunc->getReturnType(); 00584 00585 if (Returns.size() > 1) { 00586 // The PHI node should go at the front of the new basic block to merge all 00587 // possible incoming values. 00588 PHINode *PHI = 0; 00589 if (!TheCall->use_empty()) { 00590 PHI = PHINode::Create(RTy, TheCall->getName(), 00591 AfterCallBB->begin()); 00592 // Anything that used the result of the function call should now use the 00593 // PHI node as their operand. 00594 TheCall->replaceAllUsesWith(PHI); 00595 } 00596 00597 // Loop over all of the return instructions adding entries to the PHI node 00598 // as appropriate. 00599 if (PHI) { 00600 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 00601 ReturnInst *RI = Returns[i]; 00602 assert(RI->getReturnValue()->getType() == PHI->getType() && 00603 "Ret value not consistent in function!"); 00604 PHI->addIncoming(RI->getReturnValue(), RI->getParent()); 00605 } 00606 } 00607 00608 // Add a branch to the merge points and remove return instructions. 00609 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 00610 ReturnInst *RI = Returns[i]; 00611 BranchInst::Create(AfterCallBB, RI); 00612 RI->eraseFromParent(); 00613 } 00614 } else if (!Returns.empty()) { 00615 // Otherwise, if there is exactly one return value, just replace anything 00616 // using the return value of the call with the computed value. 00617 if (!TheCall->use_empty()) { 00618 if (TheCall == Returns[0]->getReturnValue()) 00619 TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 00620 else 00621 TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 00622 } 00623 00624 // Splice the code from the return block into the block that it will return 00625 // to, which contains the code that was after the call. 00626 BasicBlock *ReturnBB = Returns[0]->getParent(); 00627 AfterCallBB->getInstList().splice(AfterCallBB->begin(), 00628 ReturnBB->getInstList()); 00629 00630 // Update PHI nodes that use the ReturnBB to use the AfterCallBB. 00631 ReturnBB->replaceAllUsesWith(AfterCallBB); 00632 00633 // Delete the return instruction now and empty ReturnBB now. 00634 Returns[0]->eraseFromParent(); 00635 ReturnBB->eraseFromParent(); 00636 } else if (!TheCall->use_empty()) { 00637 // No returns, but something is using the return value of the call. Just 00638 // nuke the result. 00639 TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 00640 } 00641 00642 // Since we are now done with the Call/Invoke, we can delete it. 00643 TheCall->eraseFromParent(); 00644 00645 // We should always be able to fold the entry block of the function into the 00646 // single predecessor of the block... 00647 assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!"); 00648 BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 00649 00650 // Splice the code entry block into calling block, right before the 00651 // unconditional branch. 00652 OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); 00653 CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes 00654 00655 // Remove the unconditional branch. 00656 OrigBB->getInstList().erase(Br); 00657 00658 // Now we can remove the CalleeEntry block, which is now empty. 00659 Caller->getBasicBlockList().erase(CalleeEntry); 00660 00661 return true; 00662 }