LLVM API Documentation

InlineFunction.cpp

Go to the documentation of this file.
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 }