Push LLVMContexts through the IntegerType APIs.
[oota-llvm.git] / lib / Transforms / Utils / InlineFunction.cpp
1 //===- InlineFunction.cpp - Code to perform function inlining -------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements inlining of a function into a call site, resolving
11 // parameters and the return value as appropriate.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/Transforms/Utils/Cloning.h"
16 #include "llvm/Constants.h"
17 #include "llvm/DerivedTypes.h"
18 #include "llvm/LLVMContext.h"
19 #include "llvm/Module.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/IntrinsicInst.h"
22 #include "llvm/Intrinsics.h"
23 #include "llvm/Attributes.h"
24 #include "llvm/Analysis/CallGraph.h"
25 #include "llvm/Analysis/DebugInfo.h"
26 #include "llvm/Target/TargetData.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/StringExtras.h"
29 #include "llvm/Support/CallSite.h"
30 using namespace llvm;
31
32 bool llvm::InlineFunction(CallInst *CI, CallGraph *CG, const TargetData *TD) {
33   return InlineFunction(CallSite(CI), CG, TD);
34 }
35 bool llvm::InlineFunction(InvokeInst *II, CallGraph *CG, const TargetData *TD) {
36   return InlineFunction(CallSite(II), CG, TD);
37 }
38
39 /// HandleInlinedInvoke - If we inlined an invoke site, we need to convert calls
40 /// in the body of the inlined function into invokes and turn unwind
41 /// instructions into branches to the invoke unwind dest.
42 ///
43 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
44 /// block of the inlined code (the last block is the end of the function),
45 /// and InlineCodeInfo is information about the code that got inlined.
46 static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock,
47                                 ClonedCodeInfo &InlinedCodeInfo,
48                                 CallGraph *CG) {
49   BasicBlock *InvokeDest = II->getUnwindDest();
50   std::vector<Value*> InvokeDestPHIValues;
51
52   // If there are PHI nodes in the unwind destination block, we need to
53   // keep track of which values came into them from this invoke, then remove
54   // the entry for this block.
55   BasicBlock *InvokeBlock = II->getParent();
56   for (BasicBlock::iterator I = InvokeDest->begin(); isa<PHINode>(I); ++I) {
57     PHINode *PN = cast<PHINode>(I);
58     // Save the value to use for this edge.
59     InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(InvokeBlock));
60   }
61
62   Function *Caller = FirstNewBlock->getParent();
63
64   // The inlined code is currently at the end of the function, scan from the
65   // start of the inlined code to its end, checking for stuff we need to
66   // rewrite.
67   if (InlinedCodeInfo.ContainsCalls || InlinedCodeInfo.ContainsUnwinds) {
68     for (Function::iterator BB = FirstNewBlock, E = Caller->end();
69          BB != E; ++BB) {
70       if (InlinedCodeInfo.ContainsCalls) {
71         for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ){
72           Instruction *I = BBI++;
73
74           // We only need to check for function calls: inlined invoke
75           // instructions require no special handling.
76           if (!isa<CallInst>(I)) continue;
77           CallInst *CI = cast<CallInst>(I);
78
79           // If this call cannot unwind, don't convert it to an invoke.
80           if (CI->doesNotThrow())
81             continue;
82
83           // Convert this function call into an invoke instruction.
84           // First, split the basic block.
85           BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc");
86
87           // Next, create the new invoke instruction, inserting it at the end
88           // of the old basic block.
89           SmallVector<Value*, 8> InvokeArgs(CI->op_begin()+1, CI->op_end());
90           InvokeInst *II =
91             InvokeInst::Create(CI->getCalledValue(), Split, InvokeDest,
92                                InvokeArgs.begin(), InvokeArgs.end(),
93                                CI->getName(), BB->getTerminator());
94           II->setCallingConv(CI->getCallingConv());
95           II->setAttributes(CI->getAttributes());
96
97           // Make sure that anything using the call now uses the invoke!
98           CI->replaceAllUsesWith(II);
99
100           // Update the callgraph.
101           if (CG) {
102             // We should be able to do this:
103             //   (*CG)[Caller]->replaceCallSite(CI, II);
104             // but that fails if the old call site isn't in the call graph,
105             // which, because of LLVM bug 3601, it sometimes isn't.
106             CallGraphNode *CGN = (*CG)[Caller];
107             for (CallGraphNode::iterator NI = CGN->begin(), NE = CGN->end();
108                  NI != NE; ++NI) {
109               if (NI->first == CI) {
110                 NI->first = II;
111                 break;
112               }
113             }
114           }
115
116           // Delete the unconditional branch inserted by splitBasicBlock
117           BB->getInstList().pop_back();
118           Split->getInstList().pop_front();  // Delete the original call
119
120           // Update any PHI nodes in the exceptional block to indicate that
121           // there is now a new entry in them.
122           unsigned i = 0;
123           for (BasicBlock::iterator I = InvokeDest->begin();
124                isa<PHINode>(I); ++I, ++i) {
125             PHINode *PN = cast<PHINode>(I);
126             PN->addIncoming(InvokeDestPHIValues[i], BB);
127           }
128
129           // This basic block is now complete, start scanning the next one.
130           break;
131         }
132       }
133
134       if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
135         // An UnwindInst requires special handling when it gets inlined into an
136         // invoke site.  Once this happens, we know that the unwind would cause
137         // a control transfer to the invoke exception destination, so we can
138         // transform it into a direct branch to the exception destination.
139         BranchInst::Create(InvokeDest, UI);
140
141         // Delete the unwind instruction!
142         UI->eraseFromParent();
143
144         // Update any PHI nodes in the exceptional block to indicate that
145         // there is now a new entry in them.
146         unsigned i = 0;
147         for (BasicBlock::iterator I = InvokeDest->begin();
148              isa<PHINode>(I); ++I, ++i) {
149           PHINode *PN = cast<PHINode>(I);
150           PN->addIncoming(InvokeDestPHIValues[i], BB);
151         }
152       }
153     }
154   }
155
156   // Now that everything is happy, we have one final detail.  The PHI nodes in
157   // the exception destination block still have entries due to the original
158   // invoke instruction.  Eliminate these entries (which might even delete the
159   // PHI node) now.
160   InvokeDest->removePredecessor(II->getParent());
161 }
162
163 /// UpdateCallGraphAfterInlining - Once we have cloned code over from a callee
164 /// into the caller, update the specified callgraph to reflect the changes we
165 /// made.  Note that it's possible that not all code was copied over, so only
166 /// some edges of the callgraph may remain.
167 static void UpdateCallGraphAfterInlining(CallSite CS,
168                                          Function::iterator FirstNewBlock,
169                                        DenseMap<const Value*, Value*> &ValueMap,
170                                          CallGraph &CG) {
171   const Function *Caller = CS.getInstruction()->getParent()->getParent();
172   const Function *Callee = CS.getCalledFunction();
173   CallGraphNode *CalleeNode = CG[Callee];
174   CallGraphNode *CallerNode = CG[Caller];
175
176   // Since we inlined some uninlined call sites in the callee into the caller,
177   // add edges from the caller to all of the callees of the callee.
178   CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end();
179
180   // Consider the case where CalleeNode == CallerNode.
181   CallGraphNode::CalledFunctionsVector CallCache;
182   if (CalleeNode == CallerNode) {
183     CallCache.assign(I, E);
184     I = CallCache.begin();
185     E = CallCache.end();
186   }
187
188   for (; I != E; ++I) {
189     const Instruction *OrigCall = I->first.getInstruction();
190
191     DenseMap<const Value*, Value*>::iterator VMI = ValueMap.find(OrigCall);
192     // Only copy the edge if the call was inlined!
193     if (VMI != ValueMap.end() && VMI->second) {
194       // If the call was inlined, but then constant folded, there is no edge to
195       // add.  Check for this case.
196       if (Instruction *NewCall = dyn_cast<Instruction>(VMI->second))
197         CallerNode->addCalledFunction(CallSite::get(NewCall), I->second);
198     }
199   }
200   // Update the call graph by deleting the edge from Callee to Caller.  We must
201   // do this after the loop above in case Caller and Callee are the same.
202   CallerNode->removeCallEdgeFor(CS);
203 }
204
205 /// findFnRegionEndMarker - This is a utility routine that is used by
206 /// InlineFunction. Return llvm.dbg.region.end intrinsic that corresponds
207 /// to the llvm.dbg.func.start of the function F. Otherwise return NULL.
208 static const DbgRegionEndInst *findFnRegionEndMarker(const Function *F) {
209
210   GlobalVariable *FnStart = NULL;
211   const DbgRegionEndInst *FnEnd = NULL;
212   for (Function::const_iterator FI = F->begin(), FE =F->end(); FI != FE; ++FI) 
213     for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end(); BI != BE;
214          ++BI) {
215       if (FnStart == NULL)  {
216         if (const DbgFuncStartInst *FSI = dyn_cast<DbgFuncStartInst>(BI)) {
217           DISubprogram SP(cast<GlobalVariable>(FSI->getSubprogram()));
218           assert (SP.isNull() == false && "Invalid llvm.dbg.func.start");
219           if (SP.describes(F))
220             FnStart = SP.getGV();
221         }
222       } else {
223         if (const DbgRegionEndInst *REI = dyn_cast<DbgRegionEndInst>(BI))
224           if (REI->getContext() == FnStart)
225             FnEnd = REI;
226       }
227     }
228   return FnEnd;
229 }
230
231 // InlineFunction - This function inlines the called function into the basic
232 // block of the caller.  This returns false if it is not possible to inline this
233 // call.  The program is still in a well defined state if this occurs though.
234 //
235 // Note that this only does one level of inlining.  For example, if the
236 // instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
237 // exists in the instruction stream.  Similiarly this will inline a recursive
238 // function by one level.
239 //
240 bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD) {
241   Instruction *TheCall = CS.getInstruction();
242   LLVMContext &Context = TheCall->getContext();
243   assert(TheCall->getParent() && TheCall->getParent()->getParent() &&
244          "Instruction not in function!");
245
246   const Function *CalledFunc = CS.getCalledFunction();
247   if (CalledFunc == 0 ||          // Can't inline external function or indirect
248       CalledFunc->isDeclaration() || // call, or call to a vararg function!
249       CalledFunc->getFunctionType()->isVarArg()) return false;
250
251
252   // If the call to the callee is not a tail call, we must clear the 'tail'
253   // flags on any calls that we inline.
254   bool MustClearTailCallFlags =
255     !(isa<CallInst>(TheCall) && cast<CallInst>(TheCall)->isTailCall());
256
257   // If the call to the callee cannot throw, set the 'nounwind' flag on any
258   // calls that we inline.
259   bool MarkNoUnwind = CS.doesNotThrow();
260
261   BasicBlock *OrigBB = TheCall->getParent();
262   Function *Caller = OrigBB->getParent();
263
264   // GC poses two hazards to inlining, which only occur when the callee has GC:
265   //  1. If the caller has no GC, then the callee's GC must be propagated to the
266   //     caller.
267   //  2. If the caller has a differing GC, it is invalid to inline.
268   if (CalledFunc->hasGC()) {
269     if (!Caller->hasGC())
270       Caller->setGC(CalledFunc->getGC());
271     else if (CalledFunc->getGC() != Caller->getGC())
272       return false;
273   }
274
275   // Get an iterator to the last basic block in the function, which will have
276   // the new function inlined after it.
277   //
278   Function::iterator LastBlock = &Caller->back();
279
280   // Make sure to capture all of the return instructions from the cloned
281   // function.
282   std::vector<ReturnInst*> Returns;
283   ClonedCodeInfo InlinedFunctionInfo;
284   Function::iterator FirstNewBlock;
285
286   { // Scope to destroy ValueMap after cloning.
287     DenseMap<const Value*, Value*> ValueMap;
288
289     assert(CalledFunc->arg_size() == CS.arg_size() &&
290            "No varargs calls can be inlined!");
291
292     // Calculate the vector of arguments to pass into the function cloner, which
293     // matches up the formal to the actual argument values.
294     CallSite::arg_iterator AI = CS.arg_begin();
295     unsigned ArgNo = 0;
296     for (Function::const_arg_iterator I = CalledFunc->arg_begin(),
297          E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) {
298       Value *ActualArg = *AI;
299
300       // When byval arguments actually inlined, we need to make the copy implied
301       // by them explicit.  However, we don't do this if the callee is readonly
302       // or readnone, because the copy would be unneeded: the callee doesn't
303       // modify the struct.
304       if (CalledFunc->paramHasAttr(ArgNo+1, Attribute::ByVal) &&
305           !CalledFunc->onlyReadsMemory()) {
306         const Type *AggTy = cast<PointerType>(I->getType())->getElementType();
307         const Type *VoidPtrTy = 
308             PointerType::getUnqual(Type::getInt8Ty(Context));
309
310         // Create the alloca.  If we have TargetData, use nice alignment.
311         unsigned Align = 1;
312         if (TD) Align = TD->getPrefTypeAlignment(AggTy);
313         Value *NewAlloca = new AllocaInst(AggTy, 0, Align, 
314                                           I->getName(), 
315                                           &*Caller->begin()->begin());
316         // Emit a memcpy.
317         const Type *Tys[] = { Type::getInt64Ty(Context) };
318         Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(),
319                                                        Intrinsic::memcpy, 
320                                                        Tys, 1);
321         Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall);
322         Value *SrcCast = new BitCastInst(*AI, VoidPtrTy, "tmp", TheCall);
323
324         Value *Size;
325         if (TD == 0)
326           Size = ConstantExpr::getSizeOf(AggTy);
327         else
328           Size = ConstantInt::get(Type::getInt64Ty(Context),
329                                          TD->getTypeStoreSize(AggTy));
330
331         // Always generate a memcpy of alignment 1 here because we don't know
332         // the alignment of the src pointer.  Other optimizations can infer
333         // better alignment.
334         Value *CallArgs[] = {
335           DestCast, SrcCast, Size,
336           ConstantInt::get(Type::getInt32Ty(Context), 1)
337         };
338         CallInst *TheMemCpy =
339           CallInst::Create(MemCpyFn, CallArgs, CallArgs+4, "", TheCall);
340
341         // If we have a call graph, update it.
342         if (CG) {
343           CallGraphNode *MemCpyCGN = CG->getOrInsertFunction(MemCpyFn);
344           CallGraphNode *CallerNode = (*CG)[Caller];
345           CallerNode->addCalledFunction(TheMemCpy, MemCpyCGN);
346         }
347
348         // Uses of the argument in the function should use our new alloca
349         // instead.
350         ActualArg = NewAlloca;
351       }
352
353       ValueMap[I] = ActualArg;
354     }
355
356     // Adjust llvm.dbg.region.end. If the CalledFunc has region end
357     // marker then clone that marker after next stop point at the 
358     // call site. The function body cloner does not clone original
359     // region end marker from the CalledFunc. This will ensure that
360     // inlined function's scope ends at the right place. 
361     const DbgRegionEndInst *DREI = findFnRegionEndMarker(CalledFunc);
362     if (DREI) {
363       for (BasicBlock::iterator BI = TheCall, 
364              BE = TheCall->getParent()->end(); BI != BE; ++BI) {
365         if (DbgStopPointInst *DSPI = dyn_cast<DbgStopPointInst>(BI)) {
366           if (DbgRegionEndInst *NewDREI = 
367               dyn_cast<DbgRegionEndInst>(DREI->clone(Context)))
368             NewDREI->insertAfter(DSPI);
369           break;
370         }
371       }
372     }
373
374     // We want the inliner to prune the code as it copies.  We would LOVE to
375     // have no dead or constant instructions leftover after inlining occurs
376     // (which can happen, e.g., because an argument was constant), but we'll be
377     // happy with whatever the cloner can do.
378     CloneAndPruneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i",
379                               &InlinedFunctionInfo, TD);
380
381     // Remember the first block that is newly cloned over.
382     FirstNewBlock = LastBlock; ++FirstNewBlock;
383
384     // Update the callgraph if requested.
385     if (CG)
386       UpdateCallGraphAfterInlining(CS, FirstNewBlock, ValueMap, *CG);
387   }
388
389   // If there are any alloca instructions in the block that used to be the entry
390   // block for the callee, move them to the entry block of the caller.  First
391   // calculate which instruction they should be inserted before.  We insert the
392   // instructions at the end of the current alloca list.
393   //
394   {
395     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
396     for (BasicBlock::iterator I = FirstNewBlock->begin(),
397            E = FirstNewBlock->end(); I != E; )
398       if (AllocaInst *AI = dyn_cast<AllocaInst>(I++)) {
399         // If the alloca is now dead, remove it.  This often occurs due to code
400         // specialization.
401         if (AI->use_empty()) {
402           AI->eraseFromParent();
403           continue;
404         }
405
406         if (isa<Constant>(AI->getArraySize())) {
407           // Scan for the block of allocas that we can move over, and move them
408           // all at once.
409           while (isa<AllocaInst>(I) &&
410                  isa<Constant>(cast<AllocaInst>(I)->getArraySize()))
411             ++I;
412
413           // Transfer all of the allocas over in a block.  Using splice means
414           // that the instructions aren't removed from the symbol table, then
415           // reinserted.
416           Caller->getEntryBlock().getInstList().splice(
417               InsertPoint,
418               FirstNewBlock->getInstList(),
419               AI, I);
420         }
421       }
422   }
423
424   // If the inlined code contained dynamic alloca instructions, wrap the inlined
425   // code with llvm.stacksave/llvm.stackrestore intrinsics.
426   if (InlinedFunctionInfo.ContainsDynamicAllocas) {
427     Module *M = Caller->getParent();
428     // Get the two intrinsics we care about.
429     Constant *StackSave, *StackRestore;
430     StackSave    = Intrinsic::getDeclaration(M, Intrinsic::stacksave);
431     StackRestore = Intrinsic::getDeclaration(M, Intrinsic::stackrestore);
432
433     // If we are preserving the callgraph, add edges to the stacksave/restore
434     // functions for the calls we insert.
435     CallGraphNode *StackSaveCGN = 0, *StackRestoreCGN = 0, *CallerNode = 0;
436     if (CG) {
437       // We know that StackSave/StackRestore are Function*'s, because they are
438       // intrinsics which must have the right types.
439       StackSaveCGN    = CG->getOrInsertFunction(cast<Function>(StackSave));
440       StackRestoreCGN = CG->getOrInsertFunction(cast<Function>(StackRestore));
441       CallerNode = (*CG)[Caller];
442     }
443
444     // Insert the llvm.stacksave.
445     CallInst *SavedPtr = CallInst::Create(StackSave, "savedstack",
446                                           FirstNewBlock->begin());
447     if (CG) CallerNode->addCalledFunction(SavedPtr, StackSaveCGN);
448
449     // Insert a call to llvm.stackrestore before any return instructions in the
450     // inlined function.
451     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
452       CallInst *CI = CallInst::Create(StackRestore, SavedPtr, "", Returns[i]);
453       if (CG) CallerNode->addCalledFunction(CI, StackRestoreCGN);
454     }
455
456     // Count the number of StackRestore calls we insert.
457     unsigned NumStackRestores = Returns.size();
458
459     // If we are inlining an invoke instruction, insert restores before each
460     // unwind.  These unwinds will be rewritten into branches later.
461     if (InlinedFunctionInfo.ContainsUnwinds && isa<InvokeInst>(TheCall)) {
462       for (Function::iterator BB = FirstNewBlock, E = Caller->end();
463            BB != E; ++BB)
464         if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
465           CallInst::Create(StackRestore, SavedPtr, "", UI);
466           ++NumStackRestores;
467         }
468     }
469   }
470
471   // If we are inlining tail call instruction through a call site that isn't
472   // marked 'tail', we must remove the tail marker for any calls in the inlined
473   // code.  Also, calls inlined through a 'nounwind' call site should be marked
474   // 'nounwind'.
475   if (InlinedFunctionInfo.ContainsCalls &&
476       (MustClearTailCallFlags || MarkNoUnwind)) {
477     for (Function::iterator BB = FirstNewBlock, E = Caller->end();
478          BB != E; ++BB)
479       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
480         if (CallInst *CI = dyn_cast<CallInst>(I)) {
481           if (MustClearTailCallFlags)
482             CI->setTailCall(false);
483           if (MarkNoUnwind)
484             CI->setDoesNotThrow();
485         }
486   }
487
488   // If we are inlining through a 'nounwind' call site then any inlined 'unwind'
489   // instructions are unreachable.
490   if (InlinedFunctionInfo.ContainsUnwinds && MarkNoUnwind)
491     for (Function::iterator BB = FirstNewBlock, E = Caller->end();
492          BB != E; ++BB) {
493       TerminatorInst *Term = BB->getTerminator();
494       if (isa<UnwindInst>(Term)) {
495         new UnreachableInst(Context, Term);
496         BB->getInstList().erase(Term);
497       }
498     }
499
500   // If we are inlining for an invoke instruction, we must make sure to rewrite
501   // any inlined 'unwind' instructions into branches to the invoke exception
502   // destination, and call instructions into invoke instructions.
503   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall))
504     HandleInlinedInvoke(II, FirstNewBlock, InlinedFunctionInfo, CG);
505
506   // If we cloned in _exactly one_ basic block, and if that block ends in a
507   // return instruction, we splice the body of the inlined callee directly into
508   // the calling basic block.
509   if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) {
510     // Move all of the instructions right before the call.
511     OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(),
512                                  FirstNewBlock->begin(), FirstNewBlock->end());
513     // Remove the cloned basic block.
514     Caller->getBasicBlockList().pop_back();
515
516     // If the call site was an invoke instruction, add a branch to the normal
517     // destination.
518     if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall))
519       BranchInst::Create(II->getNormalDest(), TheCall);
520
521     // If the return instruction returned a value, replace uses of the call with
522     // uses of the returned value.
523     if (!TheCall->use_empty()) {
524       ReturnInst *R = Returns[0];
525       if (TheCall == R->getReturnValue())
526         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
527       else
528         TheCall->replaceAllUsesWith(R->getReturnValue());
529     }
530     // Since we are now done with the Call/Invoke, we can delete it.
531     TheCall->eraseFromParent();
532
533     // Since we are now done with the return instruction, delete it also.
534     Returns[0]->eraseFromParent();
535
536     // We are now done with the inlining.
537     return true;
538   }
539
540   // Otherwise, we have the normal case, of more than one block to inline or
541   // multiple return sites.
542
543   // We want to clone the entire callee function into the hole between the
544   // "starter" and "ender" blocks.  How we accomplish this depends on whether
545   // this is an invoke instruction or a call instruction.
546   BasicBlock *AfterCallBB;
547   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
548
549     // Add an unconditional branch to make this look like the CallInst case...
550     BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall);
551
552     // Split the basic block.  This guarantees that no PHI nodes will have to be
553     // updated due to new incoming edges, and make the invoke case more
554     // symmetric to the call case.
555     AfterCallBB = OrigBB->splitBasicBlock(NewBr,
556                                           CalledFunc->getName()+".exit");
557
558   } else {  // It's a call
559     // If this is a call instruction, we need to split the basic block that
560     // the call lives in.
561     //
562     AfterCallBB = OrigBB->splitBasicBlock(TheCall,
563                                           CalledFunc->getName()+".exit");
564   }
565
566   // Change the branch that used to go to AfterCallBB to branch to the first
567   // basic block of the inlined function.
568   //
569   TerminatorInst *Br = OrigBB->getTerminator();
570   assert(Br && Br->getOpcode() == Instruction::Br &&
571          "splitBasicBlock broken!");
572   Br->setOperand(0, FirstNewBlock);
573
574
575   // Now that the function is correct, make it a little bit nicer.  In
576   // particular, move the basic blocks inserted from the end of the function
577   // into the space made by splitting the source basic block.
578   Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(),
579                                      FirstNewBlock, Caller->end());
580
581   // Handle all of the return instructions that we just cloned in, and eliminate
582   // any users of the original call/invoke instruction.
583   const Type *RTy = CalledFunc->getReturnType();
584
585   if (Returns.size() > 1) {
586     // The PHI node should go at the front of the new basic block to merge all
587     // possible incoming values.
588     PHINode *PHI = 0;
589     if (!TheCall->use_empty()) {
590       PHI = PHINode::Create(RTy, TheCall->getName(),
591                             AfterCallBB->begin());
592       // Anything that used the result of the function call should now use the
593       // PHI node as their operand.
594       TheCall->replaceAllUsesWith(PHI);
595     }
596
597     // Loop over all of the return instructions adding entries to the PHI node
598     // as appropriate.
599     if (PHI) {
600       for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
601         ReturnInst *RI = Returns[i];
602         assert(RI->getReturnValue()->getType() == PHI->getType() &&
603                "Ret value not consistent in function!");
604         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
605       }
606     }
607
608     // Add a branch to the merge points and remove return instructions.
609     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
610       ReturnInst *RI = Returns[i];
611       BranchInst::Create(AfterCallBB, RI);
612       RI->eraseFromParent();
613     }
614   } else if (!Returns.empty()) {
615     // Otherwise, if there is exactly one return value, just replace anything
616     // using the return value of the call with the computed value.
617     if (!TheCall->use_empty()) {
618       if (TheCall == Returns[0]->getReturnValue())
619         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
620       else
621         TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
622     }
623
624     // Splice the code from the return block into the block that it will return
625     // to, which contains the code that was after the call.
626     BasicBlock *ReturnBB = Returns[0]->getParent();
627     AfterCallBB->getInstList().splice(AfterCallBB->begin(),
628                                       ReturnBB->getInstList());
629
630     // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
631     ReturnBB->replaceAllUsesWith(AfterCallBB);
632
633     // Delete the return instruction now and empty ReturnBB now.
634     Returns[0]->eraseFromParent();
635     ReturnBB->eraseFromParent();
636   } else if (!TheCall->use_empty()) {
637     // No returns, but something is using the return value of the call.  Just
638     // nuke the result.
639     TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
640   }
641
642   // Since we are now done with the Call/Invoke, we can delete it.
643   TheCall->eraseFromParent();
644
645   // We should always be able to fold the entry block of the function into the
646   // single predecessor of the block...
647   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
648   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
649
650   // Splice the code entry block into calling block, right before the
651   // unconditional branch.
652   OrigBB->getInstList().splice(Br, CalleeEntry->getInstList());
653   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes
654
655   // Remove the unconditional branch.
656   OrigBB->getInstList().erase(Br);
657
658   // Now we can remove the CalleeEntry block, which is now empty.
659   Caller->getBasicBlockList().erase(CalleeEntry);
660
661   return true;
662 }