Initial stab at getting inlining working with the EH rewrite.
[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 // The code in this file for handling inlines through invoke
14 // instructions preserves semantics only under some assumptions about
15 // the behavior of unwinders which correspond to gcc-style libUnwind
16 // exception personality functions.  Eventually the IR will be
17 // improved to make this unnecessary, but until then, this code is
18 // marked [LIBUNWIND].
19 //
20 //===----------------------------------------------------------------------===//
21
22 #include "llvm/Transforms/Utils/Cloning.h"
23 #include "llvm/Constants.h"
24 #include "llvm/DerivedTypes.h"
25 #include "llvm/Module.h"
26 #include "llvm/Instructions.h"
27 #include "llvm/IntrinsicInst.h"
28 #include "llvm/Intrinsics.h"
29 #include "llvm/Attributes.h"
30 #include "llvm/Analysis/CallGraph.h"
31 #include "llvm/Analysis/DebugInfo.h"
32 #include "llvm/Analysis/InstructionSimplify.h"
33 #include "llvm/Target/TargetData.h"
34 #include "llvm/Transforms/Utils/Local.h"
35 #include "llvm/ADT/SmallVector.h"
36 #include "llvm/ADT/StringExtras.h"
37 #include "llvm/Support/CallSite.h"
38 #include "llvm/Support/IRBuilder.h"
39 using namespace llvm;
40
41 bool llvm::InlineFunction(CallInst *CI, InlineFunctionInfo &IFI) {
42   return InlineFunction(CallSite(CI), IFI);
43 }
44 bool llvm::InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI) {
45   return InlineFunction(CallSite(II), IFI);
46 }
47
48 /// [LIBUNWIND] Look for an llvm.eh.exception call in the given block.
49 static EHExceptionInst *findExceptionInBlock(BasicBlock *bb) {
50   for (BasicBlock::iterator i = bb->begin(), e = bb->end(); i != e; i++) {
51     EHExceptionInst *exn = dyn_cast<EHExceptionInst>(i);
52     if (exn) return exn;
53   }
54
55   return 0;
56 }
57
58 /// [LIBUNWIND] Look for the 'best' llvm.eh.selector instruction for
59 /// the given llvm.eh.exception call.
60 static EHSelectorInst *findSelectorForException(EHExceptionInst *exn) {
61   BasicBlock *exnBlock = exn->getParent();
62
63   EHSelectorInst *outOfBlockSelector = 0;
64   for (Instruction::use_iterator
65          ui = exn->use_begin(), ue = exn->use_end(); ui != ue; ++ui) {
66     EHSelectorInst *sel = dyn_cast<EHSelectorInst>(*ui);
67     if (!sel) continue;
68
69     // Immediately accept an eh.selector in the same block as the
70     // excepton call.
71     if (sel->getParent() == exnBlock) return sel;
72
73     // Otherwise, use the first selector we see.
74     if (!outOfBlockSelector) outOfBlockSelector = sel;
75   }
76
77   return outOfBlockSelector;
78 }
79
80 /// [LIBUNWIND] Find the (possibly absent) call to @llvm.eh.selector
81 /// in the given landing pad.  In principle, llvm.eh.exception is
82 /// required to be in the landing pad; in practice, SplitCriticalEdge
83 /// can break that invariant, and then inlining can break it further.
84 /// There's a real need for a reliable solution here, but until that
85 /// happens, we have some fragile workarounds here.
86 static EHSelectorInst *findSelectorForLandingPad(BasicBlock *lpad) {
87   // Look for an exception call in the actual landing pad.
88   EHExceptionInst *exn = findExceptionInBlock(lpad);
89   if (exn) return findSelectorForException(exn);
90
91   // Okay, if that failed, look for one in an obvious successor.  If
92   // we find one, we'll fix the IR by moving things back to the
93   // landing pad.
94
95   bool dominates = true; // does the lpad dominate the exn call
96   BasicBlock *nonDominated = 0; // if not, the first non-dominated block
97   BasicBlock *lastDominated = 0; // and the block which branched to it
98
99   BasicBlock *exnBlock = lpad;
100
101   // We need to protect against lpads that lead into infinite loops.
102   SmallPtrSet<BasicBlock*,4> visited;
103   visited.insert(exnBlock);
104
105   do {
106     // We're not going to apply this hack to anything more complicated
107     // than a series of unconditional branches, so if the block
108     // doesn't terminate in an unconditional branch, just fail.  More
109     // complicated cases can arise when, say, sinking a call into a
110     // split unwind edge and then inlining it; but that can do almost
111     // *anything* to the CFG, including leaving the selector
112     // completely unreachable.  The only way to fix that properly is
113     // to (1) prohibit transforms which move the exception or selector
114     // values away from the landing pad, e.g. by producing them with
115     // instructions that are pinned to an edge like a phi, or
116     // producing them with not-really-instructions, and (2) making
117     // transforms which split edges deal with that.
118     BranchInst *branch = dyn_cast<BranchInst>(&exnBlock->back());
119     if (!branch || branch->isConditional()) return 0;
120
121     BasicBlock *successor = branch->getSuccessor(0);
122
123     // Fail if we found an infinite loop.
124     if (!visited.insert(successor)) return 0;
125
126     // If the successor isn't dominated by exnBlock:
127     if (!successor->getSinglePredecessor()) {
128       // We don't want to have to deal with threading the exception
129       // through multiple levels of phi, so give up if we've already
130       // followed a non-dominating edge.
131       if (!dominates) return 0;
132
133       // Otherwise, remember this as a non-dominating edge.
134       dominates = false;
135       nonDominated = successor;
136       lastDominated = exnBlock;
137     }
138
139     exnBlock = successor;
140
141     // Can we stop here?
142     exn = findExceptionInBlock(exnBlock);
143   } while (!exn);
144
145   // Look for a selector call for the exception we found.
146   EHSelectorInst *selector = findSelectorForException(exn);
147   if (!selector) return 0;
148
149   // The easy case is when the landing pad still dominates the
150   // exception call, in which case we can just move both calls back to
151   // the landing pad.
152   if (dominates) {
153     selector->moveBefore(lpad->getFirstNonPHI());
154     exn->moveBefore(selector);
155     return selector;
156   }
157
158   // Otherwise, we have to split at the first non-dominating block.
159   // The CFG looks basically like this:
160   //    lpad:
161   //      phis_0
162   //      insnsAndBranches_1
163   //      br label %nonDominated
164   //    nonDominated:
165   //      phis_2
166   //      insns_3
167   //      %exn = call i8* @llvm.eh.exception()
168   //      insnsAndBranches_4
169   //      %selector = call @llvm.eh.selector(i8* %exn, ...
170   // We need to turn this into:
171   //    lpad:
172   //      phis_0
173   //      %exn0 = call i8* @llvm.eh.exception()
174   //      %selector0 = call @llvm.eh.selector(i8* %exn0, ...
175   //      insnsAndBranches_1
176   //      br label %split // from lastDominated
177   //    nonDominated:
178   //      phis_2 (without edge from lastDominated)
179   //      %exn1 = call i8* @llvm.eh.exception()
180   //      %selector1 = call i8* @llvm.eh.selector(i8* %exn1, ...
181   //      br label %split
182   //    split:
183   //      phis_2 (edge from lastDominated, edge from split)
184   //      %exn = phi ...
185   //      %selector = phi ...
186   //      insns_3
187   //      insnsAndBranches_4
188
189   assert(nonDominated);
190   assert(lastDominated);
191
192   // First, make clones of the intrinsics to go in lpad.
193   EHExceptionInst *lpadExn = cast<EHExceptionInst>(exn->clone());
194   EHSelectorInst *lpadSelector = cast<EHSelectorInst>(selector->clone());
195   lpadSelector->setArgOperand(0, lpadExn);
196   lpadSelector->insertBefore(lpad->getFirstNonPHI());
197   lpadExn->insertBefore(lpadSelector);
198
199   // Split the non-dominated block.
200   BasicBlock *split =
201     nonDominated->splitBasicBlock(nonDominated->getFirstNonPHI(),
202                                   nonDominated->getName() + ".lpad-fix");
203
204   // Redirect the last dominated branch there.
205   cast<BranchInst>(lastDominated->back()).setSuccessor(0, split);
206
207   // Move the existing intrinsics to the end of the old block.
208   selector->moveBefore(&nonDominated->back());
209   exn->moveBefore(selector);
210
211   Instruction *splitIP = &split->front();
212
213   // For all the phis in nonDominated, make a new phi in split to join
214   // that phi with the edge from lastDominated.
215   for (BasicBlock::iterator
216          i = nonDominated->begin(), e = nonDominated->end(); i != e; ++i) {
217     PHINode *phi = dyn_cast<PHINode>(i);
218     if (!phi) break;
219
220     PHINode *splitPhi = PHINode::Create(phi->getType(), 2, phi->getName(),
221                                         splitIP);
222     phi->replaceAllUsesWith(splitPhi);
223     splitPhi->addIncoming(phi, nonDominated);
224     splitPhi->addIncoming(phi->removeIncomingValue(lastDominated),
225                           lastDominated);
226   }
227
228   // Make new phis for the exception and selector.
229   PHINode *exnPhi = PHINode::Create(exn->getType(), 2, "", splitIP);
230   exn->replaceAllUsesWith(exnPhi);
231   selector->setArgOperand(0, exn); // except for this use
232   exnPhi->addIncoming(exn, nonDominated);
233   exnPhi->addIncoming(lpadExn, lastDominated);
234
235   PHINode *selectorPhi = PHINode::Create(selector->getType(), 2, "", splitIP);
236   selector->replaceAllUsesWith(selectorPhi);
237   selectorPhi->addIncoming(selector, nonDominated);
238   selectorPhi->addIncoming(lpadSelector, lastDominated);
239
240   return lpadSelector;
241 }
242
243 namespace {
244   /// A class for recording information about inlining through an invoke.
245   class InvokeInliningInfo {
246     BasicBlock *OuterUnwindDest;
247     EHSelectorInst *OuterSelector;
248     BasicBlock *InnerUnwindDest;
249     PHINode *InnerExceptionPHI;
250     PHINode *InnerSelectorPHI;
251     SmallVector<Value*, 8> UnwindDestPHIValues;
252
253     SmallVector<LandingPadInst*, 16> CalleeLPads;
254     LandingPadInst *CallerLPad;
255     BasicBlock *SplitLPad;
256
257   public:
258     InvokeInliningInfo(InvokeInst *II)
259       : OuterUnwindDest(II->getUnwindDest()), OuterSelector(0),
260         InnerUnwindDest(0), InnerExceptionPHI(0), InnerSelectorPHI(0),
261         CallerLPad(0), SplitLPad(0) {
262       // If there are PHI nodes in the unwind destination block, we
263       // need to keep track of which values came into them from the
264       // invoke before removing the edge from this block.
265       llvm::BasicBlock *invokeBB = II->getParent();
266       BasicBlock::iterator I = OuterUnwindDest->begin();
267       for (; isa<PHINode>(I); ++I) {
268         // Save the value to use for this edge.
269         PHINode *phi = cast<PHINode>(I);
270         UnwindDestPHIValues.push_back(phi->getIncomingValueForBlock(invokeBB));
271       }
272
273       // FIXME: With the new EH, this if/dyn_cast should be a 'cast'.
274       if (LandingPadInst *LPI = dyn_cast<LandingPadInst>(I))
275         CallerLPad = LPI;
276     }
277
278     /// The outer unwind destination is the target of unwind edges
279     /// introduced for calls within the inlined function.
280     BasicBlock *getOuterUnwindDest() const {
281       return OuterUnwindDest;
282     }
283
284     EHSelectorInst *getOuterSelector() {
285       if (!OuterSelector)
286         OuterSelector = findSelectorForLandingPad(OuterUnwindDest);
287       return OuterSelector;
288     }
289
290     BasicBlock *getInnerUnwindDest();
291
292     void addCalleeLandingPad(LandingPadInst *LPI) {
293       CalleeLPads.push_back(LPI);
294     }
295
296     LandingPadInst *getLandingPadInst() const { return CallerLPad; }
297     BasicBlock *getSplitLandingPad() {
298       if (SplitLPad) return SplitLPad;
299       assert(CallerLPad && "Trying to split a block that isn't a landing pad!");
300       BasicBlock::iterator I = CallerLPad; ++I;
301       SplitLPad = CallerLPad->getParent()->splitBasicBlock(I, "split.lpad");
302       return SplitLPad;
303     }
304
305     bool forwardEHResume(CallInst *call, BasicBlock *src);
306
307     /// forwardResume - Forward the 'resume' instruction to the caller's landing
308     /// pad block. When the landing pad block has only one predecessor, this is
309     /// a simple branch. When there is more than one predecessor, we need to
310     /// split the landing pad block after the landingpad instruction and jump
311     /// to there.
312     void forwardResume(ResumeInst *RI);
313
314     /// mergeLandingPadClauses - Visit all of the landing pad instructions which
315     /// supply the value for the ResumeInst, and merge the clauses from the new
316     /// destination (the caller's landing pad).
317     void mergeLandingPadClauses(ResumeInst *RI);
318
319     /// addIncomingPHIValuesFor - Add incoming-PHI values to the unwind
320     /// destination block for the given basic block, using the values for the
321     /// original invoke's source block.
322     void addIncomingPHIValuesFor(BasicBlock *BB) const {
323       addIncomingPHIValuesForInto(BB, OuterUnwindDest);
324     }
325     void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const {
326       BasicBlock::iterator I = dest->begin();
327       for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
328         PHINode *phi = cast<PHINode>(I);
329         phi->addIncoming(UnwindDestPHIValues[i], src);
330       }
331     }
332   };
333 }
334
335 /// Get or create a target for the branch out of rewritten calls to
336 /// llvm.eh.resume.
337 BasicBlock *InvokeInliningInfo::getInnerUnwindDest() {
338   if (InnerUnwindDest) return InnerUnwindDest;
339
340   // Find and hoist the llvm.eh.exception and llvm.eh.selector calls
341   // in the outer landing pad to immediately following the phis.
342   EHSelectorInst *selector = getOuterSelector();
343   if (!selector) return 0;
344
345   // The call to llvm.eh.exception *must* be in the landing pad.
346   Instruction *exn = cast<Instruction>(selector->getArgOperand(0));
347   assert(exn->getParent() == OuterUnwindDest);
348
349   // TODO: recognize when we've already done this, so that we don't
350   // get a linear number of these when inlining calls into lots of
351   // invokes with the same landing pad.
352
353   // Do the hoisting.
354   Instruction *splitPoint = exn->getParent()->getFirstNonPHI();
355   assert(splitPoint != selector && "selector-on-exception dominance broken!");
356   if (splitPoint == exn) {
357     selector->removeFromParent();
358     selector->insertAfter(exn);
359     splitPoint = selector->getNextNode();
360   } else {
361     exn->moveBefore(splitPoint);
362     selector->moveBefore(splitPoint);
363   }
364
365   // Split the landing pad.
366   InnerUnwindDest = OuterUnwindDest->splitBasicBlock(splitPoint,
367                                         OuterUnwindDest->getName() + ".body");
368
369   // The number of incoming edges we expect to the inner landing pad.
370   const unsigned phiCapacity = 2;
371
372   // Create corresponding new phis for all the phis in the outer landing pad.
373   BasicBlock::iterator insertPoint = InnerUnwindDest->begin();
374   BasicBlock::iterator I = OuterUnwindDest->begin();
375   for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
376     PHINode *outerPhi = cast<PHINode>(I);
377     PHINode *innerPhi = PHINode::Create(outerPhi->getType(), phiCapacity,
378                                         outerPhi->getName() + ".lpad-body",
379                                         insertPoint);
380     outerPhi->replaceAllUsesWith(innerPhi);
381     innerPhi->addIncoming(outerPhi, OuterUnwindDest);
382   }
383
384   // Create a phi for the exception value...
385   InnerExceptionPHI = PHINode::Create(exn->getType(), phiCapacity,
386                                       "exn.lpad-body", insertPoint);
387   exn->replaceAllUsesWith(InnerExceptionPHI);
388   selector->setArgOperand(0, exn); // restore this use
389   InnerExceptionPHI->addIncoming(exn, OuterUnwindDest);
390
391   // ...and the selector.
392   InnerSelectorPHI = PHINode::Create(selector->getType(), phiCapacity,
393                                      "selector.lpad-body", insertPoint);
394   selector->replaceAllUsesWith(InnerSelectorPHI);
395   InnerSelectorPHI->addIncoming(selector, OuterUnwindDest);
396
397   // All done.
398   return InnerUnwindDest;
399 }
400
401 /// [LIBUNWIND] Try to forward the given call, which logically occurs
402 /// at the end of the given block, as a branch to the inner unwind
403 /// block.  Returns true if the call was forwarded.
404 bool InvokeInliningInfo::forwardEHResume(CallInst *call, BasicBlock *src) {
405   // First, check whether this is a call to the intrinsic.
406   Function *fn = dyn_cast<Function>(call->getCalledValue());
407   if (!fn || fn->getName() != "llvm.eh.resume")
408     return false;
409   
410   // At this point, we need to return true on all paths, because
411   // otherwise we'll construct an invoke of the intrinsic, which is
412   // not well-formed.
413
414   // Try to find or make an inner unwind dest, which will fail if we
415   // can't find a selector call for the outer unwind dest.
416   BasicBlock *dest = getInnerUnwindDest();
417   bool hasSelector = (dest != 0);
418
419   // If we failed, just use the outer unwind dest, dropping the
420   // exception and selector on the floor.
421   if (!hasSelector)
422     dest = OuterUnwindDest;
423
424   // Make a branch.
425   BranchInst::Create(dest, src);
426
427   // Update the phis in the destination.  They were inserted in an
428   // order which makes this work.
429   addIncomingPHIValuesForInto(src, dest);
430
431   if (hasSelector) {
432     InnerExceptionPHI->addIncoming(call->getArgOperand(0), src);
433     InnerSelectorPHI->addIncoming(call->getArgOperand(1), src);
434   }
435
436   return true;
437 }
438
439 /// mergeLandingPadClauses - Visit all of the landing pad instructions merge the
440 /// clauses from the new destination (the caller's landing pad).
441 void InvokeInliningInfo::mergeLandingPadClauses(ResumeInst *RI) {
442   for (SmallVectorImpl<LandingPadInst*>::iterator
443          I = CalleeLPads.begin(), E = CalleeLPads.end(); I != E; ++I)
444     for (unsigned i = 0, e = CallerLPad->getNumClauses(); i != e; ++i)
445       (*I)->addClause(CallerLPad->getClauseType(i),
446                       CallerLPad->getClauseValue(i));
447 }
448
449 /// forwardResume - Forward the 'resume' instruction to the caller's landing pad
450 /// block. When the landing pad block has only one predecessor, this is a simple
451 /// branch. When there is more than one predecessor, we need to split the
452 /// landing pad block after the landingpad instruction and jump to there.
453 void InvokeInliningInfo::forwardResume(ResumeInst *RI) {
454   BasicBlock *LPadBB = CallerLPad->getParent();
455   Value *ResumeOp = RI->getOperand(0);
456
457   if (!LPadBB->getSinglePredecessor()) {
458     // There are multiple predecessors to this landing pad block. Split this
459     // landing pad block and jump to the new BB.
460     BasicBlock *SplitLPad = getSplitLandingPad();
461     BranchInst::Create(SplitLPad, RI->getParent());
462
463     if (CallerLPad->hasOneUse() && isa<PHINode>(CallerLPad->use_back())) {
464       PHINode *PN = cast<PHINode>(CallerLPad->use_back());
465       PN->addIncoming(ResumeOp, RI->getParent());
466     } else {
467       PHINode *PN = PHINode::Create(ResumeOp->getType(), 0, "lpad.phi",
468                                     &SplitLPad->front());
469       CallerLPad->replaceAllUsesWith(PN);
470       PN->addIncoming(ResumeOp, RI->getParent());
471       PN->addIncoming(CallerLPad, LPadBB);
472     }
473
474     RI->eraseFromParent();
475     return;
476   }
477
478   BranchInst::Create(LPadBB, RI->getParent());
479   CallerLPad->replaceAllUsesWith(ResumeOp);
480   CallerLPad->eraseFromParent();
481   RI->eraseFromParent();
482 }
483
484 /// [LIBUNWIND] Check whether this selector is "only cleanups":
485 ///   call i32 @llvm.eh.selector(blah, blah, i32 0)
486 static bool isCleanupOnlySelector(EHSelectorInst *selector) {
487   if (selector->getNumArgOperands() != 3) return false;
488   ConstantInt *val = dyn_cast<ConstantInt>(selector->getArgOperand(2));
489   return (val && val->isZero());
490 }
491
492 /// HandleCallsInBlockInlinedThroughInvoke - When we inline a basic block into
493 /// an invoke, we have to turn all of the calls that can throw into
494 /// invokes.  This function analyze BB to see if there are any calls, and if so,
495 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
496 /// nodes in that block with the values specified in InvokeDestPHIValues.
497 ///
498 /// Returns true to indicate that the next block should be skipped.
499 static bool HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB,
500                                                    InvokeInliningInfo &Invoke) {
501   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
502     Instruction *I = BBI++;
503
504     // Collect the callee's landingpad instructions.
505     if (LandingPadInst *LPI = dyn_cast<LandingPadInst>(I)) {
506       Invoke.addCalleeLandingPad(LPI);
507       continue;
508     }
509     
510     // We only need to check for function calls: inlined invoke
511     // instructions require no special handling.
512     CallInst *CI = dyn_cast<CallInst>(I);
513     if (CI == 0) continue;
514
515     // LIBUNWIND: merge selector instructions.
516     if (EHSelectorInst *Inner = dyn_cast<EHSelectorInst>(CI)) {
517       EHSelectorInst *Outer = Invoke.getOuterSelector();
518       if (!Outer) continue;
519
520       bool innerIsOnlyCleanup = isCleanupOnlySelector(Inner);
521       bool outerIsOnlyCleanup = isCleanupOnlySelector(Outer);
522
523       // If both selectors contain only cleanups, we don't need to do
524       // anything.  TODO: this is really just a very specific instance
525       // of a much more general optimization.
526       if (innerIsOnlyCleanup && outerIsOnlyCleanup) continue;
527
528       // Otherwise, we just append the outer selector to the inner selector.
529       SmallVector<Value*, 16> NewSelector;
530       for (unsigned i = 0, e = Inner->getNumArgOperands(); i != e; ++i)
531         NewSelector.push_back(Inner->getArgOperand(i));
532       for (unsigned i = 2, e = Outer->getNumArgOperands(); i != e; ++i)
533         NewSelector.push_back(Outer->getArgOperand(i));
534
535       CallInst *NewInner =
536         IRBuilder<>(Inner).CreateCall(Inner->getCalledValue(), NewSelector);
537       // No need to copy attributes, calling convention, etc.
538       NewInner->takeName(Inner);
539       Inner->replaceAllUsesWith(NewInner);
540       Inner->eraseFromParent();
541       continue;
542     }
543     
544     // If this call cannot unwind, don't convert it to an invoke.
545     if (CI->doesNotThrow())
546       continue;
547     
548     // Convert this function call into an invoke instruction.
549     // First, split the basic block.
550     BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc");
551
552     // Delete the unconditional branch inserted by splitBasicBlock
553     BB->getInstList().pop_back();
554
555     // LIBUNWIND: If this is a call to @llvm.eh.resume, just branch
556     // directly to the new landing pad.
557     if (Invoke.forwardEHResume(CI, BB)) {
558       // TODO: 'Split' is now unreachable; clean it up.
559
560       // We want to leave the original call intact so that the call
561       // graph and other structures won't get misled.  We also have to
562       // avoid processing the next block, or we'll iterate here forever.
563       return true;
564     }
565
566     // Otherwise, create the new invoke instruction.
567     ImmutableCallSite CS(CI);
568     SmallVector<Value*, 8> InvokeArgs(CS.arg_begin(), CS.arg_end());
569     InvokeInst *II =
570       InvokeInst::Create(CI->getCalledValue(), Split,
571                          Invoke.getOuterUnwindDest(),
572                          InvokeArgs, CI->getName(), BB);
573     II->setCallingConv(CI->getCallingConv());
574     II->setAttributes(CI->getAttributes());
575     
576     // Make sure that anything using the call now uses the invoke!  This also
577     // updates the CallGraph if present, because it uses a WeakVH.
578     CI->replaceAllUsesWith(II);
579
580     Split->getInstList().pop_front();  // Delete the original call
581
582     // Update any PHI nodes in the exceptional block to indicate that
583     // there is now a new entry in them.
584     Invoke.addIncomingPHIValuesFor(BB);
585     return false;
586   }
587
588   return false;
589 }
590   
591
592 /// HandleInlinedInvoke - If we inlined an invoke site, we need to convert calls
593 /// in the body of the inlined function into invokes and turn unwind
594 /// instructions into branches to the invoke unwind dest.
595 ///
596 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
597 /// block of the inlined code (the last block is the end of the function),
598 /// and InlineCodeInfo is information about the code that got inlined.
599 static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock,
600                                 ClonedCodeInfo &InlinedCodeInfo) {
601   BasicBlock *InvokeDest = II->getUnwindDest();
602
603   Function *Caller = FirstNewBlock->getParent();
604
605   // The inlined code is currently at the end of the function, scan from the
606   // start of the inlined code to its end, checking for stuff we need to
607   // rewrite.  If the code doesn't have calls or unwinds, we know there is
608   // nothing to rewrite.
609   if (!InlinedCodeInfo.ContainsCalls && !InlinedCodeInfo.ContainsUnwinds) {
610     // Now that everything is happy, we have one final detail.  The PHI nodes in
611     // the exception destination block still have entries due to the original
612     // invoke instruction.  Eliminate these entries (which might even delete the
613     // PHI node) now.
614     InvokeDest->removePredecessor(II->getParent());
615     return;
616   }
617
618   InvokeInliningInfo Invoke(II);
619   
620   for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; ++BB){
621     if (InlinedCodeInfo.ContainsCalls)
622       if (HandleCallsInBlockInlinedThroughInvoke(BB, Invoke)) {
623         // Honor a request to skip the next block.  We don't need to
624         // consider UnwindInsts in this case either.
625         ++BB;
626         continue;
627       }
628
629     if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
630       // An UnwindInst requires special handling when it gets inlined into an
631       // invoke site.  Once this happens, we know that the unwind would cause
632       // a control transfer to the invoke exception destination, so we can
633       // transform it into a direct branch to the exception destination.
634       BranchInst::Create(InvokeDest, UI);
635
636       // Delete the unwind instruction!
637       UI->eraseFromParent();
638
639       // Update any PHI nodes in the exceptional block to indicate that
640       // there is now a new entry in them.
641       Invoke.addIncomingPHIValuesFor(BB);
642     }
643
644     if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) {
645       Invoke.mergeLandingPadClauses(RI);
646       Invoke.forwardResume(RI);
647     }
648   }
649
650   // Now that everything is happy, we have one final detail.  The PHI nodes in
651   // the exception destination block still have entries due to the original
652   // invoke instruction.  Eliminate these entries (which might even delete the
653   // PHI node) now.
654   InvokeDest->removePredecessor(II->getParent());
655 }
656
657 /// UpdateCallGraphAfterInlining - Once we have cloned code over from a callee
658 /// into the caller, update the specified callgraph to reflect the changes we
659 /// made.  Note that it's possible that not all code was copied over, so only
660 /// some edges of the callgraph may remain.
661 static void UpdateCallGraphAfterInlining(CallSite CS,
662                                          Function::iterator FirstNewBlock,
663                                          ValueToValueMapTy &VMap,
664                                          InlineFunctionInfo &IFI) {
665   CallGraph &CG = *IFI.CG;
666   const Function *Caller = CS.getInstruction()->getParent()->getParent();
667   const Function *Callee = CS.getCalledFunction();
668   CallGraphNode *CalleeNode = CG[Callee];
669   CallGraphNode *CallerNode = CG[Caller];
670
671   // Since we inlined some uninlined call sites in the callee into the caller,
672   // add edges from the caller to all of the callees of the callee.
673   CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end();
674
675   // Consider the case where CalleeNode == CallerNode.
676   CallGraphNode::CalledFunctionsVector CallCache;
677   if (CalleeNode == CallerNode) {
678     CallCache.assign(I, E);
679     I = CallCache.begin();
680     E = CallCache.end();
681   }
682
683   for (; I != E; ++I) {
684     const Value *OrigCall = I->first;
685
686     ValueToValueMapTy::iterator VMI = VMap.find(OrigCall);
687     // Only copy the edge if the call was inlined!
688     if (VMI == VMap.end() || VMI->second == 0)
689       continue;
690     
691     // If the call was inlined, but then constant folded, there is no edge to
692     // add.  Check for this case.
693     Instruction *NewCall = dyn_cast<Instruction>(VMI->second);
694     if (NewCall == 0) continue;
695
696     // Remember that this call site got inlined for the client of
697     // InlineFunction.
698     IFI.InlinedCalls.push_back(NewCall);
699
700     // It's possible that inlining the callsite will cause it to go from an
701     // indirect to a direct call by resolving a function pointer.  If this
702     // happens, set the callee of the new call site to a more precise
703     // destination.  This can also happen if the call graph node of the caller
704     // was just unnecessarily imprecise.
705     if (I->second->getFunction() == 0)
706       if (Function *F = CallSite(NewCall).getCalledFunction()) {
707         // Indirect call site resolved to direct call.
708         CallerNode->addCalledFunction(CallSite(NewCall), CG[F]);
709
710         continue;
711       }
712
713     CallerNode->addCalledFunction(CallSite(NewCall), I->second);
714   }
715   
716   // Update the call graph by deleting the edge from Callee to Caller.  We must
717   // do this after the loop above in case Caller and Callee are the same.
718   CallerNode->removeCallEdgeFor(CS);
719 }
720
721 /// HandleByValArgument - When inlining a call site that has a byval argument,
722 /// we have to make the implicit memcpy explicit by adding it.
723 static Value *HandleByValArgument(Value *Arg, Instruction *TheCall,
724                                   const Function *CalledFunc,
725                                   InlineFunctionInfo &IFI,
726                                   unsigned ByValAlignment) {
727   Type *AggTy = cast<PointerType>(Arg->getType())->getElementType();
728
729   // If the called function is readonly, then it could not mutate the caller's
730   // copy of the byval'd memory.  In this case, it is safe to elide the copy and
731   // temporary.
732   if (CalledFunc->onlyReadsMemory()) {
733     // If the byval argument has a specified alignment that is greater than the
734     // passed in pointer, then we either have to round up the input pointer or
735     // give up on this transformation.
736     if (ByValAlignment <= 1)  // 0 = unspecified, 1 = no particular alignment.
737       return Arg;
738
739     // If the pointer is already known to be sufficiently aligned, or if we can
740     // round it up to a larger alignment, then we don't need a temporary.
741     if (getOrEnforceKnownAlignment(Arg, ByValAlignment,
742                                    IFI.TD) >= ByValAlignment)
743       return Arg;
744     
745     // Otherwise, we have to make a memcpy to get a safe alignment.  This is bad
746     // for code quality, but rarely happens and is required for correctness.
747   }
748   
749   LLVMContext &Context = Arg->getContext();
750
751   Type *VoidPtrTy = Type::getInt8PtrTy(Context);
752   
753   // Create the alloca.  If we have TargetData, use nice alignment.
754   unsigned Align = 1;
755   if (IFI.TD)
756     Align = IFI.TD->getPrefTypeAlignment(AggTy);
757   
758   // If the byval had an alignment specified, we *must* use at least that
759   // alignment, as it is required by the byval argument (and uses of the
760   // pointer inside the callee).
761   Align = std::max(Align, ByValAlignment);
762   
763   Function *Caller = TheCall->getParent()->getParent(); 
764   
765   Value *NewAlloca = new AllocaInst(AggTy, 0, Align, Arg->getName(), 
766                                     &*Caller->begin()->begin());
767   // Emit a memcpy.
768   Type *Tys[3] = {VoidPtrTy, VoidPtrTy, Type::getInt64Ty(Context)};
769   Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(),
770                                                  Intrinsic::memcpy, 
771                                                  Tys);
772   Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall);
773   Value *SrcCast = new BitCastInst(Arg, VoidPtrTy, "tmp", TheCall);
774   
775   Value *Size;
776   if (IFI.TD == 0)
777     Size = ConstantExpr::getSizeOf(AggTy);
778   else
779     Size = ConstantInt::get(Type::getInt64Ty(Context),
780                             IFI.TD->getTypeStoreSize(AggTy));
781   
782   // Always generate a memcpy of alignment 1 here because we don't know
783   // the alignment of the src pointer.  Other optimizations can infer
784   // better alignment.
785   Value *CallArgs[] = {
786     DestCast, SrcCast, Size,
787     ConstantInt::get(Type::getInt32Ty(Context), 1),
788     ConstantInt::getFalse(Context) // isVolatile
789   };
790   IRBuilder<>(TheCall).CreateCall(MemCpyFn, CallArgs);
791   
792   // Uses of the argument in the function should use our new alloca
793   // instead.
794   return NewAlloca;
795 }
796
797 // isUsedByLifetimeMarker - Check whether this Value is used by a lifetime
798 // intrinsic.
799 static bool isUsedByLifetimeMarker(Value *V) {
800   for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;
801        ++UI) {
802     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*UI)) {
803       switch (II->getIntrinsicID()) {
804       default: break;
805       case Intrinsic::lifetime_start:
806       case Intrinsic::lifetime_end:
807         return true;
808       }
809     }
810   }
811   return false;
812 }
813
814 // hasLifetimeMarkers - Check whether the given alloca already has
815 // lifetime.start or lifetime.end intrinsics.
816 static bool hasLifetimeMarkers(AllocaInst *AI) {
817   Type *Int8PtrTy = Type::getInt8PtrTy(AI->getType()->getContext());
818   if (AI->getType() == Int8PtrTy)
819     return isUsedByLifetimeMarker(AI);
820
821   // Do a scan to find all the casts to i8*.
822   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); I != E;
823        ++I) {
824     if (I->getType() != Int8PtrTy) continue;
825     if (I->stripPointerCasts() != AI) continue;
826     if (isUsedByLifetimeMarker(*I))
827       return true;
828   }
829   return false;
830 }
831
832 /// updateInlinedAtInfo - Helper function used by fixupLineNumbers to recursively
833 /// update InlinedAtEntry of a DebugLoc.
834 static DebugLoc updateInlinedAtInfo(const DebugLoc &DL, 
835                                     const DebugLoc &InlinedAtDL,
836                                     LLVMContext &Ctx) {
837   if (MDNode *IA = DL.getInlinedAt(Ctx)) {
838     DebugLoc NewInlinedAtDL 
839       = updateInlinedAtInfo(DebugLoc::getFromDILocation(IA), InlinedAtDL, Ctx);
840     return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(Ctx),
841                          NewInlinedAtDL.getAsMDNode(Ctx));
842   }
843                                              
844   return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(Ctx),
845                        InlinedAtDL.getAsMDNode(Ctx));
846 }
847
848
849 /// fixupLineNumbers - Update inlined instructions' line numbers to 
850 /// to encode location where these instructions are inlined.
851 static void fixupLineNumbers(Function *Fn, Function::iterator FI,
852                               Instruction *TheCall) {
853   DebugLoc TheCallDL = TheCall->getDebugLoc();
854   if (TheCallDL.isUnknown())
855     return;
856
857   for (; FI != Fn->end(); ++FI) {
858     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
859          BI != BE; ++BI) {
860       DebugLoc DL = BI->getDebugLoc();
861       if (!DL.isUnknown()) {
862         BI->setDebugLoc(updateInlinedAtInfo(DL, TheCallDL, BI->getContext()));
863         if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(BI)) {
864           LLVMContext &Ctx = BI->getContext();
865           MDNode *InlinedAt = BI->getDebugLoc().getInlinedAt(Ctx);
866           DVI->setOperand(2, createInlinedVariable(DVI->getVariable(), 
867                                                    InlinedAt, Ctx));
868         }
869       }
870     }
871   }
872 }
873
874 // InlineFunction - This function inlines the called function into the basic
875 // block of the caller.  This returns false if it is not possible to inline this
876 // call.  The program is still in a well defined state if this occurs though.
877 //
878 // Note that this only does one level of inlining.  For example, if the
879 // instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
880 // exists in the instruction stream.  Similarly this will inline a recursive
881 // function by one level.
882 //
883 bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) {
884   Instruction *TheCall = CS.getInstruction();
885   LLVMContext &Context = TheCall->getContext();
886   assert(TheCall->getParent() && TheCall->getParent()->getParent() &&
887          "Instruction not in function!");
888
889   // If IFI has any state in it, zap it before we fill it in.
890   IFI.reset();
891   
892   const Function *CalledFunc = CS.getCalledFunction();
893   if (CalledFunc == 0 ||          // Can't inline external function or indirect
894       CalledFunc->isDeclaration() || // call, or call to a vararg function!
895       CalledFunc->getFunctionType()->isVarArg()) return false;
896
897   // If the call to the callee is not a tail call, we must clear the 'tail'
898   // flags on any calls that we inline.
899   bool MustClearTailCallFlags =
900     !(isa<CallInst>(TheCall) && cast<CallInst>(TheCall)->isTailCall());
901
902   // If the call to the callee cannot throw, set the 'nounwind' flag on any
903   // calls that we inline.
904   bool MarkNoUnwind = CS.doesNotThrow();
905
906   BasicBlock *OrigBB = TheCall->getParent();
907   Function *Caller = OrigBB->getParent();
908
909   // GC poses two hazards to inlining, which only occur when the callee has GC:
910   //  1. If the caller has no GC, then the callee's GC must be propagated to the
911   //     caller.
912   //  2. If the caller has a differing GC, it is invalid to inline.
913   if (CalledFunc->hasGC()) {
914     if (!Caller->hasGC())
915       Caller->setGC(CalledFunc->getGC());
916     else if (CalledFunc->getGC() != Caller->getGC())
917       return false;
918   }
919
920   // Find the personality function used by the landing pads of the caller. If it
921   // exists, then check to see that it matches the personality function used in
922   // the callee.
923   for (Function::const_iterator
924          I = Caller->begin(), E = Caller->end(); I != E; ++I)
925     if (const InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) {
926       const BasicBlock *BB = II->getUnwindDest();
927       // FIXME: This 'isa' here should become go away once the new EH system is
928       // in place.
929       if (!isa<LandingPadInst>(BB->getFirstNonPHI()))
930         continue;
931       const LandingPadInst *LP = cast<LandingPadInst>(BB->getFirstNonPHI());
932       const Value *CallerPersFn = LP->getPersonalityFn();
933
934       // If the personality functions match, then we can perform the
935       // inlining. Otherwise, we can't inline.
936       // TODO: This isn't 100% true. Some personality functions are proper
937       //       supersets of others and can be used in place of the other.
938       for (Function::const_iterator
939              I = CalledFunc->begin(), E = CalledFunc->end(); I != E; ++I)
940         if (const InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) {
941           const BasicBlock *BB = II->getUnwindDest();
942           // FIXME: This 'if/dyn_cast' here should become a normal 'cast' once
943           // the new EH system is in place.
944           if (const LandingPadInst *LP =
945               dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
946             if (CallerPersFn != LP->getPersonalityFn())
947               return false;
948           break;
949         }
950
951       break;
952     }
953
954   // Get an iterator to the last basic block in the function, which will have
955   // the new function inlined after it.
956   //
957   Function::iterator LastBlock = &Caller->back();
958
959   // Make sure to capture all of the return instructions from the cloned
960   // function.
961   SmallVector<ReturnInst*, 8> Returns;
962   ClonedCodeInfo InlinedFunctionInfo;
963   Function::iterator FirstNewBlock;
964
965   { // Scope to destroy VMap after cloning.
966     ValueToValueMapTy VMap;
967
968     assert(CalledFunc->arg_size() == CS.arg_size() &&
969            "No varargs calls can be inlined!");
970
971     // Calculate the vector of arguments to pass into the function cloner, which
972     // matches up the formal to the actual argument values.
973     CallSite::arg_iterator AI = CS.arg_begin();
974     unsigned ArgNo = 0;
975     for (Function::const_arg_iterator I = CalledFunc->arg_begin(),
976          E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) {
977       Value *ActualArg = *AI;
978
979       // When byval arguments actually inlined, we need to make the copy implied
980       // by them explicit.  However, we don't do this if the callee is readonly
981       // or readnone, because the copy would be unneeded: the callee doesn't
982       // modify the struct.
983       if (CalledFunc->paramHasAttr(ArgNo+1, Attribute::ByVal)) {
984         ActualArg = HandleByValArgument(ActualArg, TheCall, CalledFunc, IFI,
985                                         CalledFunc->getParamAlignment(ArgNo+1));
986  
987         // Calls that we inline may use the new alloca, so we need to clear
988         // their 'tail' flags if HandleByValArgument introduced a new alloca and
989         // the callee has calls.
990         MustClearTailCallFlags |= ActualArg != *AI;
991       }
992
993       VMap[I] = ActualArg;
994     }
995
996     // We want the inliner to prune the code as it copies.  We would LOVE to
997     // have no dead or constant instructions leftover after inlining occurs
998     // (which can happen, e.g., because an argument was constant), but we'll be
999     // happy with whatever the cloner can do.
1000     CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, 
1001                               /*ModuleLevelChanges=*/false, Returns, ".i",
1002                               &InlinedFunctionInfo, IFI.TD, TheCall);
1003
1004     // Remember the first block that is newly cloned over.
1005     FirstNewBlock = LastBlock; ++FirstNewBlock;
1006
1007     // Update the callgraph if requested.
1008     if (IFI.CG)
1009       UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI);
1010
1011     // Update inlined instructions' line number information.
1012     fixupLineNumbers(Caller, FirstNewBlock, TheCall);
1013   }
1014
1015   // If there are any alloca instructions in the block that used to be the entry
1016   // block for the callee, move them to the entry block of the caller.  First
1017   // calculate which instruction they should be inserted before.  We insert the
1018   // instructions at the end of the current alloca list.
1019   //
1020   {
1021     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
1022     for (BasicBlock::iterator I = FirstNewBlock->begin(),
1023          E = FirstNewBlock->end(); I != E; ) {
1024       AllocaInst *AI = dyn_cast<AllocaInst>(I++);
1025       if (AI == 0) continue;
1026       
1027       // If the alloca is now dead, remove it.  This often occurs due to code
1028       // specialization.
1029       if (AI->use_empty()) {
1030         AI->eraseFromParent();
1031         continue;
1032       }
1033
1034       if (!isa<Constant>(AI->getArraySize()))
1035         continue;
1036       
1037       // Keep track of the static allocas that we inline into the caller.
1038       IFI.StaticAllocas.push_back(AI);
1039       
1040       // Scan for the block of allocas that we can move over, and move them
1041       // all at once.
1042       while (isa<AllocaInst>(I) &&
1043              isa<Constant>(cast<AllocaInst>(I)->getArraySize())) {
1044         IFI.StaticAllocas.push_back(cast<AllocaInst>(I));
1045         ++I;
1046       }
1047
1048       // Transfer all of the allocas over in a block.  Using splice means
1049       // that the instructions aren't removed from the symbol table, then
1050       // reinserted.
1051       Caller->getEntryBlock().getInstList().splice(InsertPoint,
1052                                                    FirstNewBlock->getInstList(),
1053                                                    AI, I);
1054     }
1055   }
1056
1057   // Leave lifetime markers for the static alloca's, scoping them to the
1058   // function we just inlined.
1059   if (!IFI.StaticAllocas.empty()) {
1060     IRBuilder<> builder(FirstNewBlock->begin());
1061     for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) {
1062       AllocaInst *AI = IFI.StaticAllocas[ai];
1063
1064       // If the alloca is already scoped to something smaller than the whole
1065       // function then there's no need to add redundant, less accurate markers.
1066       if (hasLifetimeMarkers(AI))
1067         continue;
1068
1069       builder.CreateLifetimeStart(AI);
1070       for (unsigned ri = 0, re = Returns.size(); ri != re; ++ri) {
1071         IRBuilder<> builder(Returns[ri]);
1072         builder.CreateLifetimeEnd(AI);
1073       }
1074     }
1075   }
1076
1077   // If the inlined code contained dynamic alloca instructions, wrap the inlined
1078   // code with llvm.stacksave/llvm.stackrestore intrinsics.
1079   if (InlinedFunctionInfo.ContainsDynamicAllocas) {
1080     Module *M = Caller->getParent();
1081     // Get the two intrinsics we care about.
1082     Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave);
1083     Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore);
1084
1085     // Insert the llvm.stacksave.
1086     CallInst *SavedPtr = IRBuilder<>(FirstNewBlock, FirstNewBlock->begin())
1087       .CreateCall(StackSave, "savedstack");
1088
1089     // Insert a call to llvm.stackrestore before any return instructions in the
1090     // inlined function.
1091     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
1092       IRBuilder<>(Returns[i]).CreateCall(StackRestore, SavedPtr);
1093     }
1094
1095     // Count the number of StackRestore calls we insert.
1096     unsigned NumStackRestores = Returns.size();
1097
1098     // If we are inlining an invoke instruction, insert restores before each
1099     // unwind.  These unwinds will be rewritten into branches later.
1100     if (InlinedFunctionInfo.ContainsUnwinds && isa<InvokeInst>(TheCall)) {
1101       for (Function::iterator BB = FirstNewBlock, E = Caller->end();
1102            BB != E; ++BB)
1103         if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
1104           IRBuilder<>(UI).CreateCall(StackRestore, SavedPtr);
1105           ++NumStackRestores;
1106         }
1107     }
1108   }
1109
1110   // If we are inlining tail call instruction through a call site that isn't
1111   // marked 'tail', we must remove the tail marker for any calls in the inlined
1112   // code.  Also, calls inlined through a 'nounwind' call site should be marked
1113   // 'nounwind'.
1114   if (InlinedFunctionInfo.ContainsCalls &&
1115       (MustClearTailCallFlags || MarkNoUnwind)) {
1116     for (Function::iterator BB = FirstNewBlock, E = Caller->end();
1117          BB != E; ++BB)
1118       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
1119         if (CallInst *CI = dyn_cast<CallInst>(I)) {
1120           if (MustClearTailCallFlags)
1121             CI->setTailCall(false);
1122           if (MarkNoUnwind)
1123             CI->setDoesNotThrow();
1124         }
1125   }
1126
1127   // If we are inlining through a 'nounwind' call site then any inlined 'unwind'
1128   // instructions are unreachable.
1129   if (InlinedFunctionInfo.ContainsUnwinds && MarkNoUnwind)
1130     for (Function::iterator BB = FirstNewBlock, E = Caller->end();
1131          BB != E; ++BB) {
1132       TerminatorInst *Term = BB->getTerminator();
1133       if (isa<UnwindInst>(Term)) {
1134         new UnreachableInst(Context, Term);
1135         BB->getInstList().erase(Term);
1136       }
1137     }
1138
1139   // If we are inlining for an invoke instruction, we must make sure to rewrite
1140   // any inlined 'unwind' instructions into branches to the invoke exception
1141   // destination, and call instructions into invoke instructions.
1142   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall))
1143     HandleInlinedInvoke(II, FirstNewBlock, InlinedFunctionInfo);
1144
1145   // If we cloned in _exactly one_ basic block, and if that block ends in a
1146   // return instruction, we splice the body of the inlined callee directly into
1147   // the calling basic block.
1148   if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) {
1149     // Move all of the instructions right before the call.
1150     OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(),
1151                                  FirstNewBlock->begin(), FirstNewBlock->end());
1152     // Remove the cloned basic block.
1153     Caller->getBasicBlockList().pop_back();
1154
1155     // If the call site was an invoke instruction, add a branch to the normal
1156     // destination.
1157     if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall))
1158       BranchInst::Create(II->getNormalDest(), TheCall);
1159
1160     // If the return instruction returned a value, replace uses of the call with
1161     // uses of the returned value.
1162     if (!TheCall->use_empty()) {
1163       ReturnInst *R = Returns[0];
1164       if (TheCall == R->getReturnValue())
1165         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
1166       else
1167         TheCall->replaceAllUsesWith(R->getReturnValue());
1168     }
1169     // Since we are now done with the Call/Invoke, we can delete it.
1170     TheCall->eraseFromParent();
1171
1172     // Since we are now done with the return instruction, delete it also.
1173     Returns[0]->eraseFromParent();
1174
1175     // We are now done with the inlining.
1176     return true;
1177   }
1178
1179   // Otherwise, we have the normal case, of more than one block to inline or
1180   // multiple return sites.
1181
1182   // We want to clone the entire callee function into the hole between the
1183   // "starter" and "ender" blocks.  How we accomplish this depends on whether
1184   // this is an invoke instruction or a call instruction.
1185   BasicBlock *AfterCallBB;
1186   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
1187
1188     // Add an unconditional branch to make this look like the CallInst case...
1189     BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall);
1190
1191     // Split the basic block.  This guarantees that no PHI nodes will have to be
1192     // updated due to new incoming edges, and make the invoke case more
1193     // symmetric to the call case.
1194     AfterCallBB = OrigBB->splitBasicBlock(NewBr,
1195                                           CalledFunc->getName()+".exit");
1196
1197   } else {  // It's a call
1198     // If this is a call instruction, we need to split the basic block that
1199     // the call lives in.
1200     //
1201     AfterCallBB = OrigBB->splitBasicBlock(TheCall,
1202                                           CalledFunc->getName()+".exit");
1203   }
1204
1205   // Change the branch that used to go to AfterCallBB to branch to the first
1206   // basic block of the inlined function.
1207   //
1208   TerminatorInst *Br = OrigBB->getTerminator();
1209   assert(Br && Br->getOpcode() == Instruction::Br &&
1210          "splitBasicBlock broken!");
1211   Br->setOperand(0, FirstNewBlock);
1212
1213
1214   // Now that the function is correct, make it a little bit nicer.  In
1215   // particular, move the basic blocks inserted from the end of the function
1216   // into the space made by splitting the source basic block.
1217   Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(),
1218                                      FirstNewBlock, Caller->end());
1219
1220   // Handle all of the return instructions that we just cloned in, and eliminate
1221   // any users of the original call/invoke instruction.
1222   Type *RTy = CalledFunc->getReturnType();
1223
1224   PHINode *PHI = 0;
1225   if (Returns.size() > 1) {
1226     // The PHI node should go at the front of the new basic block to merge all
1227     // possible incoming values.
1228     if (!TheCall->use_empty()) {
1229       PHI = PHINode::Create(RTy, Returns.size(), TheCall->getName(),
1230                             AfterCallBB->begin());
1231       // Anything that used the result of the function call should now use the
1232       // PHI node as their operand.
1233       TheCall->replaceAllUsesWith(PHI);
1234     }
1235
1236     // Loop over all of the return instructions adding entries to the PHI node
1237     // as appropriate.
1238     if (PHI) {
1239       for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
1240         ReturnInst *RI = Returns[i];
1241         assert(RI->getReturnValue()->getType() == PHI->getType() &&
1242                "Ret value not consistent in function!");
1243         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
1244       }
1245     }
1246
1247
1248     // Add a branch to the merge points and remove return instructions.
1249     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
1250       ReturnInst *RI = Returns[i];
1251       BranchInst::Create(AfterCallBB, RI);
1252       RI->eraseFromParent();
1253     }
1254   } else if (!Returns.empty()) {
1255     // Otherwise, if there is exactly one return value, just replace anything
1256     // using the return value of the call with the computed value.
1257     if (!TheCall->use_empty()) {
1258       if (TheCall == Returns[0]->getReturnValue())
1259         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
1260       else
1261         TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
1262     }
1263
1264     // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
1265     BasicBlock *ReturnBB = Returns[0]->getParent();
1266     ReturnBB->replaceAllUsesWith(AfterCallBB);
1267
1268     // Splice the code from the return block into the block that it will return
1269     // to, which contains the code that was after the call.
1270     AfterCallBB->getInstList().splice(AfterCallBB->begin(),
1271                                       ReturnBB->getInstList());
1272
1273     // Delete the return instruction now and empty ReturnBB now.
1274     Returns[0]->eraseFromParent();
1275     ReturnBB->eraseFromParent();
1276   } else if (!TheCall->use_empty()) {
1277     // No returns, but something is using the return value of the call.  Just
1278     // nuke the result.
1279     TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
1280   }
1281
1282   // Since we are now done with the Call/Invoke, we can delete it.
1283   TheCall->eraseFromParent();
1284
1285   // We should always be able to fold the entry block of the function into the
1286   // single predecessor of the block...
1287   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
1288   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
1289
1290   // Splice the code entry block into calling block, right before the
1291   // unconditional branch.
1292   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes
1293   OrigBB->getInstList().splice(Br, CalleeEntry->getInstList());
1294
1295   // Remove the unconditional branch.
1296   OrigBB->getInstList().erase(Br);
1297
1298   // Now we can remove the CalleeEntry block, which is now empty.
1299   Caller->getBasicBlockList().erase(CalleeEntry);
1300
1301   // If we inserted a phi node, check to see if it has a single value (e.g. all
1302   // the entries are the same or undef).  If so, remove the PHI so it doesn't
1303   // block other optimizations.
1304   if (PHI)
1305     if (Value *V = SimplifyInstruction(PHI, IFI.TD)) {
1306       PHI->replaceAllUsesWith(V);
1307       PHI->eraseFromParent();
1308     }
1309
1310   return true;
1311 }