[Inline] Use AssumptionCache from the right Function
[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/ADT/SmallSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/StringExtras.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/AssumptionCache.h"
22 #include "llvm/Analysis/CallGraph.h"
23 #include "llvm/Analysis/CaptureTracking.h"
24 #include "llvm/Analysis/InstructionSimplify.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/IR/Attributes.h"
27 #include "llvm/IR/CallSite.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DebugInfo.h"
32 #include "llvm/IR/DerivedTypes.h"
33 #include "llvm/IR/DIBuilder.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/IRBuilder.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/Intrinsics.h"
39 #include "llvm/IR/MDBuilder.h"
40 #include "llvm/IR/Module.h"
41 #include "llvm/Transforms/Utils/Local.h"
42 #include "llvm/Support/CommandLine.h"
43 #include <algorithm>
44 using namespace llvm;
45
46 static cl::opt<bool>
47 EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true),
48   cl::Hidden,
49   cl::desc("Convert noalias attributes to metadata during inlining."));
50
51 static cl::opt<bool>
52 PreserveAlignmentAssumptions("preserve-alignment-assumptions-during-inlining",
53   cl::init(true), cl::Hidden,
54   cl::desc("Convert align attributes to assumptions during inlining."));
55
56 bool llvm::InlineFunction(CallInst *CI, InlineFunctionInfo &IFI,
57                           AAResults *CalleeAAR, bool InsertLifetime) {
58   return InlineFunction(CallSite(CI), IFI, CalleeAAR, InsertLifetime);
59 }
60 bool llvm::InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI,
61                           AAResults *CalleeAAR, bool InsertLifetime) {
62   return InlineFunction(CallSite(II), IFI, CalleeAAR, InsertLifetime);
63 }
64
65 namespace {
66   /// A class for recording information about inlining a landing pad.
67   class LandingPadInliningInfo {
68     BasicBlock *OuterResumeDest; ///< Destination of the invoke's unwind.
69     BasicBlock *InnerResumeDest; ///< Destination for the callee's resume.
70     LandingPadInst *CallerLPad;  ///< LandingPadInst associated with the invoke.
71     PHINode *InnerEHValuesPHI;   ///< PHI for EH values from landingpad insts.
72     SmallVector<Value*, 8> UnwindDestPHIValues;
73
74   public:
75     LandingPadInliningInfo(InvokeInst *II)
76       : OuterResumeDest(II->getUnwindDest()), InnerResumeDest(nullptr),
77         CallerLPad(nullptr), InnerEHValuesPHI(nullptr) {
78       // If there are PHI nodes in the unwind destination block, we need to keep
79       // track of which values came into them from the invoke before removing
80       // the edge from this block.
81       llvm::BasicBlock *InvokeBB = II->getParent();
82       BasicBlock::iterator I = OuterResumeDest->begin();
83       for (; isa<PHINode>(I); ++I) {
84         // Save the value to use for this edge.
85         PHINode *PHI = cast<PHINode>(I);
86         UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB));
87       }
88
89       CallerLPad = cast<LandingPadInst>(I);
90     }
91
92     /// The outer unwind destination is the target of
93     /// unwind edges introduced for calls within the inlined function.
94     BasicBlock *getOuterResumeDest() const {
95       return OuterResumeDest;
96     }
97
98     BasicBlock *getInnerResumeDest();
99
100     LandingPadInst *getLandingPadInst() const { return CallerLPad; }
101
102     /// Forward the 'resume' instruction to the caller's landing pad block.
103     /// When the landing pad block has only one predecessor, this is
104     /// a simple branch. When there is more than one predecessor, we need to
105     /// split the landing pad block after the landingpad instruction and jump
106     /// to there.
107     void forwardResume(ResumeInst *RI,
108                        SmallPtrSetImpl<LandingPadInst*> &InlinedLPads);
109
110     /// Add incoming-PHI values to the unwind destination block for the given
111     /// basic block, using the values for the original invoke's source block.
112     void addIncomingPHIValuesFor(BasicBlock *BB) const {
113       addIncomingPHIValuesForInto(BB, OuterResumeDest);
114     }
115
116     void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const {
117       BasicBlock::iterator I = dest->begin();
118       for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
119         PHINode *phi = cast<PHINode>(I);
120         phi->addIncoming(UnwindDestPHIValues[i], src);
121       }
122     }
123   };
124 }
125
126 /// Get or create a target for the branch from ResumeInsts.
127 BasicBlock *LandingPadInliningInfo::getInnerResumeDest() {
128   if (InnerResumeDest) return InnerResumeDest;
129
130   // Split the landing pad.
131   BasicBlock::iterator SplitPoint = CallerLPad; ++SplitPoint;
132   InnerResumeDest =
133     OuterResumeDest->splitBasicBlock(SplitPoint,
134                                      OuterResumeDest->getName() + ".body");
135
136   // The number of incoming edges we expect to the inner landing pad.
137   const unsigned PHICapacity = 2;
138
139   // Create corresponding new PHIs for all the PHIs in the outer landing pad.
140   BasicBlock::iterator InsertPoint = InnerResumeDest->begin();
141   BasicBlock::iterator I = OuterResumeDest->begin();
142   for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
143     PHINode *OuterPHI = cast<PHINode>(I);
144     PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity,
145                                         OuterPHI->getName() + ".lpad-body",
146                                         InsertPoint);
147     OuterPHI->replaceAllUsesWith(InnerPHI);
148     InnerPHI->addIncoming(OuterPHI, OuterResumeDest);
149   }
150
151   // Create a PHI for the exception values.
152   InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity,
153                                      "eh.lpad-body", InsertPoint);
154   CallerLPad->replaceAllUsesWith(InnerEHValuesPHI);
155   InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest);
156
157   // All done.
158   return InnerResumeDest;
159 }
160
161 /// Forward the 'resume' instruction to the caller's landing pad block.
162 /// When the landing pad block has only one predecessor, this is a simple
163 /// branch. When there is more than one predecessor, we need to split the
164 /// landing pad block after the landingpad instruction and jump to there.
165 void LandingPadInliningInfo::forwardResume(
166     ResumeInst *RI, SmallPtrSetImpl<LandingPadInst *> &InlinedLPads) {
167   BasicBlock *Dest = getInnerResumeDest();
168   BasicBlock *Src = RI->getParent();
169
170   BranchInst::Create(Dest, Src);
171
172   // Update the PHIs in the destination. They were inserted in an order which
173   // makes this work.
174   addIncomingPHIValuesForInto(Src, Dest);
175
176   InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src);
177   RI->eraseFromParent();
178 }
179
180 /// When we inline a basic block into an invoke,
181 /// we have to turn all of the calls that can throw into invokes.
182 /// This function analyze BB to see if there are any calls, and if so,
183 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
184 /// nodes in that block with the values specified in InvokeDestPHIValues.
185 static BasicBlock *
186 HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, BasicBlock *UnwindEdge) {
187   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
188     Instruction *I = BBI++;
189
190     // We only need to check for function calls: inlined invoke
191     // instructions require no special handling.
192     CallInst *CI = dyn_cast<CallInst>(I);
193
194     // If this call cannot unwind, don't convert it to an invoke.
195     // Inline asm calls cannot throw.
196     if (!CI || CI->doesNotThrow() || isa<InlineAsm>(CI->getCalledValue()))
197       continue;
198
199     // Convert this function call into an invoke instruction.  First, split the
200     // basic block.
201     BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc");
202
203     // Delete the unconditional branch inserted by splitBasicBlock
204     BB->getInstList().pop_back();
205
206     // Create the new invoke instruction.
207     ImmutableCallSite CS(CI);
208     SmallVector<Value*, 8> InvokeArgs(CS.arg_begin(), CS.arg_end());
209     InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge,
210                                         InvokeArgs, CI->getName(), BB);
211     II->setDebugLoc(CI->getDebugLoc());
212     II->setCallingConv(CI->getCallingConv());
213     II->setAttributes(CI->getAttributes());
214     
215     // Make sure that anything using the call now uses the invoke!  This also
216     // updates the CallGraph if present, because it uses a WeakVH.
217     CI->replaceAllUsesWith(II);
218
219     // Delete the original call
220     Split->getInstList().pop_front();
221     return BB;
222   }
223   return nullptr;
224 }
225
226 /// If we inlined an invoke site, we need to convert calls
227 /// in the body of the inlined function into invokes.
228 ///
229 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
230 /// block of the inlined code (the last block is the end of the function),
231 /// and InlineCodeInfo is information about the code that got inlined.
232 static void HandleInlinedLandingPad(InvokeInst *II, BasicBlock *FirstNewBlock,
233                                     ClonedCodeInfo &InlinedCodeInfo) {
234   BasicBlock *InvokeDest = II->getUnwindDest();
235
236   Function *Caller = FirstNewBlock->getParent();
237
238   // The inlined code is currently at the end of the function, scan from the
239   // start of the inlined code to its end, checking for stuff we need to
240   // rewrite.
241   LandingPadInliningInfo Invoke(II);
242
243   // Get all of the inlined landing pad instructions.
244   SmallPtrSet<LandingPadInst*, 16> InlinedLPads;
245   for (Function::iterator I = FirstNewBlock, E = Caller->end(); I != E; ++I)
246     if (InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator()))
247       InlinedLPads.insert(II->getLandingPadInst());
248
249   // Append the clauses from the outer landing pad instruction into the inlined
250   // landing pad instructions.
251   LandingPadInst *OuterLPad = Invoke.getLandingPadInst();
252   for (LandingPadInst *InlinedLPad : InlinedLPads) {
253     unsigned OuterNum = OuterLPad->getNumClauses();
254     InlinedLPad->reserveClauses(OuterNum);
255     for (unsigned OuterIdx = 0; OuterIdx != OuterNum; ++OuterIdx)
256       InlinedLPad->addClause(OuterLPad->getClause(OuterIdx));
257     if (OuterLPad->isCleanup())
258       InlinedLPad->setCleanup(true);
259   }
260
261   for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; ++BB){
262     if (InlinedCodeInfo.ContainsCalls)
263       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
264               BB, Invoke.getOuterResumeDest()))
265         // Update any PHI nodes in the exceptional block to indicate that there
266         // is now a new entry in them.
267         Invoke.addIncomingPHIValuesFor(NewBB);
268
269     // Forward any resumes that are remaining here.
270     if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator()))
271       Invoke.forwardResume(RI, InlinedLPads);
272   }
273
274   // Now that everything is happy, we have one final detail.  The PHI nodes in
275   // the exception destination block still have entries due to the original
276   // invoke instruction. Eliminate these entries (which might even delete the
277   // PHI node) now.
278   InvokeDest->removePredecessor(II->getParent());
279 }
280
281 /// If we inlined an invoke site, we need to convert calls
282 /// in the body of the inlined function into invokes.
283 ///
284 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
285 /// block of the inlined code (the last block is the end of the function),
286 /// and InlineCodeInfo is information about the code that got inlined.
287 static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
288                                ClonedCodeInfo &InlinedCodeInfo) {
289   BasicBlock *UnwindDest = II->getUnwindDest();
290   Function *Caller = FirstNewBlock->getParent();
291
292   assert(UnwindDest->getFirstNonPHI()->isEHPad() && "unexpected BasicBlock!");
293
294   // If there are PHI nodes in the unwind destination block, we need to keep
295   // track of which values came into them from the invoke before removing the
296   // edge from this block.
297   SmallVector<Value *, 8> UnwindDestPHIValues;
298   llvm::BasicBlock *InvokeBB = II->getParent();
299   for (Instruction &I : *UnwindDest) {
300     // Save the value to use for this edge.
301     PHINode *PHI = dyn_cast<PHINode>(&I);
302     if (!PHI)
303       break;
304     UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB));
305   }
306
307   // Add incoming-PHI values to the unwind destination block for the given basic
308   // block, using the values for the original invoke's source block.
309   auto UpdatePHINodes = [&](BasicBlock *Src) {
310     BasicBlock::iterator I = UnwindDest->begin();
311     for (Value *V : UnwindDestPHIValues) {
312       PHINode *PHI = cast<PHINode>(I);
313       PHI->addIncoming(V, Src);
314       ++I;
315     }
316   };
317
318   // Forward EH terminator instructions to the caller's invoke destination.
319   // This is as simple as connect all the instructions which 'unwind to caller'
320   // to the invoke destination.
321   for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E;
322        ++BB) {
323     Instruction *I = BB->getFirstNonPHI();
324     if (I->isEHPad()) {
325       if (auto *CEPI = dyn_cast<CatchEndPadInst>(I)) {
326         if (CEPI->unwindsToCaller()) {
327           CatchEndPadInst::Create(CEPI->getContext(), UnwindDest, CEPI);
328           CEPI->eraseFromParent();
329           UpdatePHINodes(BB);
330         }
331       } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(I)) {
332         if (CEPI->unwindsToCaller()) {
333           CleanupEndPadInst::Create(CEPI->getCleanupPad(), UnwindDest, CEPI);
334           CEPI->eraseFromParent();
335           UpdatePHINodes(BB);
336         }
337       } else if (auto *TPI = dyn_cast<TerminatePadInst>(I)) {
338         if (TPI->unwindsToCaller()) {
339           SmallVector<Value *, 3> TerminatePadArgs;
340           for (Value *Operand : TPI->operands())
341             TerminatePadArgs.push_back(Operand);
342           TerminatePadInst::Create(TPI->getContext(), UnwindDest, TPI);
343           TPI->eraseFromParent();
344           UpdatePHINodes(BB);
345         }
346       } else {
347         assert(isa<CatchPadInst>(I) || isa<CleanupPadInst>(I));
348       }
349     }
350
351     if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) {
352       if (CRI->unwindsToCaller()) {
353         CleanupReturnInst::Create(CRI->getCleanupPad(), UnwindDest, CRI);
354         CRI->eraseFromParent();
355         UpdatePHINodes(BB);
356       }
357     }
358   }
359
360   if (InlinedCodeInfo.ContainsCalls)
361     for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E;
362          ++BB)
363       if (BasicBlock *NewBB =
364               HandleCallsInBlockInlinedThroughInvoke(BB, UnwindDest))
365         // Update any PHI nodes in the exceptional block to indicate that there
366         // is now a new entry in them.
367         UpdatePHINodes(NewBB);
368
369   // Now that everything is happy, we have one final detail.  The PHI nodes in
370   // the exception destination block still have entries due to the original
371   // invoke instruction. Eliminate these entries (which might even delete the
372   // PHI node) now.
373   UnwindDest->removePredecessor(InvokeBB);
374 }
375
376 /// When inlining a function that contains noalias scope metadata,
377 /// this metadata needs to be cloned so that the inlined blocks
378 /// have different "unqiue scopes" at every call site. Were this not done, then
379 /// aliasing scopes from a function inlined into a caller multiple times could
380 /// not be differentiated (and this would lead to miscompiles because the
381 /// non-aliasing property communicated by the metadata could have
382 /// call-site-specific control dependencies).
383 static void CloneAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap) {
384   const Function *CalledFunc = CS.getCalledFunction();
385   SetVector<const MDNode *> MD;
386
387   // Note: We could only clone the metadata if it is already used in the
388   // caller. I'm omitting that check here because it might confuse
389   // inter-procedural alias analysis passes. We can revisit this if it becomes
390   // an efficiency or overhead problem.
391
392   for (Function::const_iterator I = CalledFunc->begin(), IE = CalledFunc->end();
393        I != IE; ++I)
394     for (BasicBlock::const_iterator J = I->begin(), JE = I->end(); J != JE; ++J) {
395       if (const MDNode *M = J->getMetadata(LLVMContext::MD_alias_scope))
396         MD.insert(M);
397       if (const MDNode *M = J->getMetadata(LLVMContext::MD_noalias))
398         MD.insert(M);
399     }
400
401   if (MD.empty())
402     return;
403
404   // Walk the existing metadata, adding the complete (perhaps cyclic) chain to
405   // the set.
406   SmallVector<const Metadata *, 16> Queue(MD.begin(), MD.end());
407   while (!Queue.empty()) {
408     const MDNode *M = cast<MDNode>(Queue.pop_back_val());
409     for (unsigned i = 0, ie = M->getNumOperands(); i != ie; ++i)
410       if (const MDNode *M1 = dyn_cast<MDNode>(M->getOperand(i)))
411         if (MD.insert(M1))
412           Queue.push_back(M1);
413   }
414
415   // Now we have a complete set of all metadata in the chains used to specify
416   // the noalias scopes and the lists of those scopes.
417   SmallVector<TempMDTuple, 16> DummyNodes;
418   DenseMap<const MDNode *, TrackingMDNodeRef> MDMap;
419   for (SetVector<const MDNode *>::iterator I = MD.begin(), IE = MD.end();
420        I != IE; ++I) {
421     DummyNodes.push_back(MDTuple::getTemporary(CalledFunc->getContext(), None));
422     MDMap[*I].reset(DummyNodes.back().get());
423   }
424
425   // Create new metadata nodes to replace the dummy nodes, replacing old
426   // metadata references with either a dummy node or an already-created new
427   // node.
428   for (SetVector<const MDNode *>::iterator I = MD.begin(), IE = MD.end();
429        I != IE; ++I) {
430     SmallVector<Metadata *, 4> NewOps;
431     for (unsigned i = 0, ie = (*I)->getNumOperands(); i != ie; ++i) {
432       const Metadata *V = (*I)->getOperand(i);
433       if (const MDNode *M = dyn_cast<MDNode>(V))
434         NewOps.push_back(MDMap[M]);
435       else
436         NewOps.push_back(const_cast<Metadata *>(V));
437     }
438
439     MDNode *NewM = MDNode::get(CalledFunc->getContext(), NewOps);
440     MDTuple *TempM = cast<MDTuple>(MDMap[*I]);
441     assert(TempM->isTemporary() && "Expected temporary node");
442
443     TempM->replaceAllUsesWith(NewM);
444   }
445
446   // Now replace the metadata in the new inlined instructions with the
447   // repacements from the map.
448   for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
449        VMI != VMIE; ++VMI) {
450     if (!VMI->second)
451       continue;
452
453     Instruction *NI = dyn_cast<Instruction>(VMI->second);
454     if (!NI)
455       continue;
456
457     if (MDNode *M = NI->getMetadata(LLVMContext::MD_alias_scope)) {
458       MDNode *NewMD = MDMap[M];
459       // If the call site also had alias scope metadata (a list of scopes to
460       // which instructions inside it might belong), propagate those scopes to
461       // the inlined instructions.
462       if (MDNode *CSM =
463               CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope))
464         NewMD = MDNode::concatenate(NewMD, CSM);
465       NI->setMetadata(LLVMContext::MD_alias_scope, NewMD);
466     } else if (NI->mayReadOrWriteMemory()) {
467       if (MDNode *M =
468               CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope))
469         NI->setMetadata(LLVMContext::MD_alias_scope, M);
470     }
471
472     if (MDNode *M = NI->getMetadata(LLVMContext::MD_noalias)) {
473       MDNode *NewMD = MDMap[M];
474       // If the call site also had noalias metadata (a list of scopes with
475       // which instructions inside it don't alias), propagate those scopes to
476       // the inlined instructions.
477       if (MDNode *CSM =
478               CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))
479         NewMD = MDNode::concatenate(NewMD, CSM);
480       NI->setMetadata(LLVMContext::MD_noalias, NewMD);
481     } else if (NI->mayReadOrWriteMemory()) {
482       if (MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))
483         NI->setMetadata(LLVMContext::MD_noalias, M);
484     }
485   }
486 }
487
488 /// If the inlined function has noalias arguments,
489 /// then add new alias scopes for each noalias argument, tag the mapped noalias
490 /// parameters with noalias metadata specifying the new scope, and tag all
491 /// non-derived loads, stores and memory intrinsics with the new alias scopes.
492 static void AddAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap,
493                                   const DataLayout &DL, AAResults *CalleeAAR) {
494   if (!EnableNoAliasConversion)
495     return;
496
497   const Function *CalledFunc = CS.getCalledFunction();
498   SmallVector<const Argument *, 4> NoAliasArgs;
499
500   for (Function::const_arg_iterator I = CalledFunc->arg_begin(),
501        E = CalledFunc->arg_end(); I != E; ++I) {
502     if (I->hasNoAliasAttr() && !I->hasNUses(0))
503       NoAliasArgs.push_back(I);
504   }
505
506   if (NoAliasArgs.empty())
507     return;
508
509   // To do a good job, if a noalias variable is captured, we need to know if
510   // the capture point dominates the particular use we're considering.
511   DominatorTree DT;
512   DT.recalculate(const_cast<Function&>(*CalledFunc));
513
514   // noalias indicates that pointer values based on the argument do not alias
515   // pointer values which are not based on it. So we add a new "scope" for each
516   // noalias function argument. Accesses using pointers based on that argument
517   // become part of that alias scope, accesses using pointers not based on that
518   // argument are tagged as noalias with that scope.
519
520   DenseMap<const Argument *, MDNode *> NewScopes;
521   MDBuilder MDB(CalledFunc->getContext());
522
523   // Create a new scope domain for this function.
524   MDNode *NewDomain =
525     MDB.createAnonymousAliasScopeDomain(CalledFunc->getName());
526   for (unsigned i = 0, e = NoAliasArgs.size(); i != e; ++i) {
527     const Argument *A = NoAliasArgs[i];
528
529     std::string Name = CalledFunc->getName();
530     if (A->hasName()) {
531       Name += ": %";
532       Name += A->getName();
533     } else {
534       Name += ": argument ";
535       Name += utostr(i);
536     }
537
538     // Note: We always create a new anonymous root here. This is true regardless
539     // of the linkage of the callee because the aliasing "scope" is not just a
540     // property of the callee, but also all control dependencies in the caller.
541     MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
542     NewScopes.insert(std::make_pair(A, NewScope));
543   }
544
545   // Iterate over all new instructions in the map; for all memory-access
546   // instructions, add the alias scope metadata.
547   for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
548        VMI != VMIE; ++VMI) {
549     if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) {
550       if (!VMI->second)
551         continue;
552
553       Instruction *NI = dyn_cast<Instruction>(VMI->second);
554       if (!NI)
555         continue;
556
557       bool IsArgMemOnlyCall = false, IsFuncCall = false;
558       SmallVector<const Value *, 2> PtrArgs;
559
560       if (const LoadInst *LI = dyn_cast<LoadInst>(I))
561         PtrArgs.push_back(LI->getPointerOperand());
562       else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
563         PtrArgs.push_back(SI->getPointerOperand());
564       else if (const VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
565         PtrArgs.push_back(VAAI->getPointerOperand());
566       else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I))
567         PtrArgs.push_back(CXI->getPointerOperand());
568       else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I))
569         PtrArgs.push_back(RMWI->getPointerOperand());
570       else if (ImmutableCallSite ICS = ImmutableCallSite(I)) {
571         // If we know that the call does not access memory, then we'll still
572         // know that about the inlined clone of this call site, and we don't
573         // need to add metadata.
574         if (ICS.doesNotAccessMemory())
575           continue;
576
577         IsFuncCall = true;
578         if (CalleeAAR) {
579           FunctionModRefBehavior MRB = CalleeAAR->getModRefBehavior(ICS);
580           if (MRB == FMRB_OnlyAccessesArgumentPointees ||
581               MRB == FMRB_OnlyReadsArgumentPointees)
582             IsArgMemOnlyCall = true;
583         }
584
585         for (ImmutableCallSite::arg_iterator AI = ICS.arg_begin(),
586              AE = ICS.arg_end(); AI != AE; ++AI) {
587           // We need to check the underlying objects of all arguments, not just
588           // the pointer arguments, because we might be passing pointers as
589           // integers, etc.
590           // However, if we know that the call only accesses pointer arguments,
591           // then we only need to check the pointer arguments.
592           if (IsArgMemOnlyCall && !(*AI)->getType()->isPointerTy())
593             continue;
594
595           PtrArgs.push_back(*AI);
596         }
597       }
598
599       // If we found no pointers, then this instruction is not suitable for
600       // pairing with an instruction to receive aliasing metadata.
601       // However, if this is a call, this we might just alias with none of the
602       // noalias arguments.
603       if (PtrArgs.empty() && !IsFuncCall)
604         continue;
605
606       // It is possible that there is only one underlying object, but you
607       // need to go through several PHIs to see it, and thus could be
608       // repeated in the Objects list.
609       SmallPtrSet<const Value *, 4> ObjSet;
610       SmallVector<Metadata *, 4> Scopes, NoAliases;
611
612       SmallSetVector<const Argument *, 4> NAPtrArgs;
613       for (unsigned i = 0, ie = PtrArgs.size(); i != ie; ++i) {
614         SmallVector<Value *, 4> Objects;
615         GetUnderlyingObjects(const_cast<Value*>(PtrArgs[i]),
616                              Objects, DL, /* MaxLookup = */ 0);
617
618         for (Value *O : Objects)
619           ObjSet.insert(O);
620       }
621
622       // Figure out if we're derived from anything that is not a noalias
623       // argument.
624       bool CanDeriveViaCapture = false, UsesAliasingPtr = false;
625       for (const Value *V : ObjSet) {
626         // Is this value a constant that cannot be derived from any pointer
627         // value (we need to exclude constant expressions, for example, that
628         // are formed from arithmetic on global symbols).
629         bool IsNonPtrConst = isa<ConstantInt>(V) || isa<ConstantFP>(V) ||
630                              isa<ConstantPointerNull>(V) ||
631                              isa<ConstantDataVector>(V) || isa<UndefValue>(V);
632         if (IsNonPtrConst)
633           continue;
634
635         // If this is anything other than a noalias argument, then we cannot
636         // completely describe the aliasing properties using alias.scope
637         // metadata (and, thus, won't add any).
638         if (const Argument *A = dyn_cast<Argument>(V)) {
639           if (!A->hasNoAliasAttr())
640             UsesAliasingPtr = true;
641         } else {
642           UsesAliasingPtr = true;
643         }
644
645         // If this is not some identified function-local object (which cannot
646         // directly alias a noalias argument), or some other argument (which,
647         // by definition, also cannot alias a noalias argument), then we could
648         // alias a noalias argument that has been captured).
649         if (!isa<Argument>(V) &&
650             !isIdentifiedFunctionLocal(const_cast<Value*>(V)))
651           CanDeriveViaCapture = true;
652       }
653
654       // A function call can always get captured noalias pointers (via other
655       // parameters, globals, etc.).
656       if (IsFuncCall && !IsArgMemOnlyCall)
657         CanDeriveViaCapture = true;
658
659       // First, we want to figure out all of the sets with which we definitely
660       // don't alias. Iterate over all noalias set, and add those for which:
661       //   1. The noalias argument is not in the set of objects from which we
662       //      definitely derive.
663       //   2. The noalias argument has not yet been captured.
664       // An arbitrary function that might load pointers could see captured
665       // noalias arguments via other noalias arguments or globals, and so we
666       // must always check for prior capture.
667       for (const Argument *A : NoAliasArgs) {
668         if (!ObjSet.count(A) && (!CanDeriveViaCapture ||
669                                  // It might be tempting to skip the
670                                  // PointerMayBeCapturedBefore check if
671                                  // A->hasNoCaptureAttr() is true, but this is
672                                  // incorrect because nocapture only guarantees
673                                  // that no copies outlive the function, not
674                                  // that the value cannot be locally captured.
675                                  !PointerMayBeCapturedBefore(A,
676                                    /* ReturnCaptures */ false,
677                                    /* StoreCaptures */ false, I, &DT)))
678           NoAliases.push_back(NewScopes[A]);
679       }
680
681       if (!NoAliases.empty())
682         NI->setMetadata(LLVMContext::MD_noalias,
683                         MDNode::concatenate(
684                             NI->getMetadata(LLVMContext::MD_noalias),
685                             MDNode::get(CalledFunc->getContext(), NoAliases)));
686
687       // Next, we want to figure out all of the sets to which we might belong.
688       // We might belong to a set if the noalias argument is in the set of
689       // underlying objects. If there is some non-noalias argument in our list
690       // of underlying objects, then we cannot add a scope because the fact
691       // that some access does not alias with any set of our noalias arguments
692       // cannot itself guarantee that it does not alias with this access
693       // (because there is some pointer of unknown origin involved and the
694       // other access might also depend on this pointer). We also cannot add
695       // scopes to arbitrary functions unless we know they don't access any
696       // non-parameter pointer-values.
697       bool CanAddScopes = !UsesAliasingPtr;
698       if (CanAddScopes && IsFuncCall)
699         CanAddScopes = IsArgMemOnlyCall;
700
701       if (CanAddScopes)
702         for (const Argument *A : NoAliasArgs) {
703           if (ObjSet.count(A))
704             Scopes.push_back(NewScopes[A]);
705         }
706
707       if (!Scopes.empty())
708         NI->setMetadata(
709             LLVMContext::MD_alias_scope,
710             MDNode::concatenate(NI->getMetadata(LLVMContext::MD_alias_scope),
711                                 MDNode::get(CalledFunc->getContext(), Scopes)));
712     }
713   }
714 }
715
716 /// If the inlined function has non-byval align arguments, then
717 /// add @llvm.assume-based alignment assumptions to preserve this information.
718 static void AddAlignmentAssumptions(CallSite CS, InlineFunctionInfo &IFI) {
719   if (!PreserveAlignmentAssumptions)
720     return;
721   auto &DL = CS.getCaller()->getParent()->getDataLayout();
722
723   // To avoid inserting redundant assumptions, we should check for assumptions
724   // already in the caller. To do this, we might need a DT of the caller.
725   DominatorTree DT;
726   bool DTCalculated = false;
727
728   Function *CalledFunc = CS.getCalledFunction();
729   for (Function::arg_iterator I = CalledFunc->arg_begin(),
730                               E = CalledFunc->arg_end();
731        I != E; ++I) {
732     unsigned Align = I->getType()->isPointerTy() ? I->getParamAlignment() : 0;
733     if (Align && !I->hasByValOrInAllocaAttr() && !I->hasNUses(0)) {
734       if (!DTCalculated) {
735         DT.recalculate(const_cast<Function&>(*CS.getInstruction()->getParent()
736                                                ->getParent()));
737         DTCalculated = true;
738       }
739
740       // If we can already prove the asserted alignment in the context of the
741       // caller, then don't bother inserting the assumption.
742       Value *Arg = CS.getArgument(I->getArgNo());
743       if (getKnownAlignment(Arg, DL, CS.getInstruction(),
744                             &IFI.ACT->getAssumptionCache(*CS.getCaller()),
745                             &DT) >= Align)
746         continue;
747
748       IRBuilder<>(CS.getInstruction())
749           .CreateAlignmentAssumption(DL, Arg, Align);
750     }
751   }
752 }
753
754 /// Once we have cloned code over from a callee into the caller,
755 /// update the specified callgraph to reflect the changes we made.
756 /// Note that it's possible that not all code was copied over, so only
757 /// some edges of the callgraph may remain.
758 static void UpdateCallGraphAfterInlining(CallSite CS,
759                                          Function::iterator FirstNewBlock,
760                                          ValueToValueMapTy &VMap,
761                                          InlineFunctionInfo &IFI) {
762   CallGraph &CG = *IFI.CG;
763   const Function *Caller = CS.getInstruction()->getParent()->getParent();
764   const Function *Callee = CS.getCalledFunction();
765   CallGraphNode *CalleeNode = CG[Callee];
766   CallGraphNode *CallerNode = CG[Caller];
767
768   // Since we inlined some uninlined call sites in the callee into the caller,
769   // add edges from the caller to all of the callees of the callee.
770   CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end();
771
772   // Consider the case where CalleeNode == CallerNode.
773   CallGraphNode::CalledFunctionsVector CallCache;
774   if (CalleeNode == CallerNode) {
775     CallCache.assign(I, E);
776     I = CallCache.begin();
777     E = CallCache.end();
778   }
779
780   for (; I != E; ++I) {
781     const Value *OrigCall = I->first;
782
783     ValueToValueMapTy::iterator VMI = VMap.find(OrigCall);
784     // Only copy the edge if the call was inlined!
785     if (VMI == VMap.end() || VMI->second == nullptr)
786       continue;
787     
788     // If the call was inlined, but then constant folded, there is no edge to
789     // add.  Check for this case.
790     Instruction *NewCall = dyn_cast<Instruction>(VMI->second);
791     if (!NewCall)
792       continue;
793
794     // We do not treat intrinsic calls like real function calls because we
795     // expect them to become inline code; do not add an edge for an intrinsic.
796     CallSite CS = CallSite(NewCall);
797     if (CS && CS.getCalledFunction() && CS.getCalledFunction()->isIntrinsic())
798       continue;
799     
800     // Remember that this call site got inlined for the client of
801     // InlineFunction.
802     IFI.InlinedCalls.push_back(NewCall);
803
804     // It's possible that inlining the callsite will cause it to go from an
805     // indirect to a direct call by resolving a function pointer.  If this
806     // happens, set the callee of the new call site to a more precise
807     // destination.  This can also happen if the call graph node of the caller
808     // was just unnecessarily imprecise.
809     if (!I->second->getFunction())
810       if (Function *F = CallSite(NewCall).getCalledFunction()) {
811         // Indirect call site resolved to direct call.
812         CallerNode->addCalledFunction(CallSite(NewCall), CG[F]);
813
814         continue;
815       }
816
817     CallerNode->addCalledFunction(CallSite(NewCall), I->second);
818   }
819   
820   // Update the call graph by deleting the edge from Callee to Caller.  We must
821   // do this after the loop above in case Caller and Callee are the same.
822   CallerNode->removeCallEdgeFor(CS);
823 }
824
825 static void HandleByValArgumentInit(Value *Dst, Value *Src, Module *M,
826                                     BasicBlock *InsertBlock,
827                                     InlineFunctionInfo &IFI) {
828   Type *AggTy = cast<PointerType>(Src->getType())->getElementType();
829   IRBuilder<> Builder(InsertBlock->begin());
830
831   Value *Size = Builder.getInt64(M->getDataLayout().getTypeStoreSize(AggTy));
832
833   // Always generate a memcpy of alignment 1 here because we don't know
834   // the alignment of the src pointer.  Other optimizations can infer
835   // better alignment.
836   Builder.CreateMemCpy(Dst, Src, Size, /*Align=*/1);
837 }
838
839 /// When inlining a call site that has a byval argument,
840 /// we have to make the implicit memcpy explicit by adding it.
841 static Value *HandleByValArgument(Value *Arg, Instruction *TheCall,
842                                   const Function *CalledFunc,
843                                   InlineFunctionInfo &IFI,
844                                   unsigned ByValAlignment) {
845   PointerType *ArgTy = cast<PointerType>(Arg->getType());
846   Type *AggTy = ArgTy->getElementType();
847
848   Function *Caller = TheCall->getParent()->getParent();
849
850   // If the called function is readonly, then it could not mutate the caller's
851   // copy of the byval'd memory.  In this case, it is safe to elide the copy and
852   // temporary.
853   if (CalledFunc->onlyReadsMemory()) {
854     // If the byval argument has a specified alignment that is greater than the
855     // passed in pointer, then we either have to round up the input pointer or
856     // give up on this transformation.
857     if (ByValAlignment <= 1)  // 0 = unspecified, 1 = no particular alignment.
858       return Arg;
859
860     const DataLayout &DL = Caller->getParent()->getDataLayout();
861
862     // If the pointer is already known to be sufficiently aligned, or if we can
863     // round it up to a larger alignment, then we don't need a temporary.
864     if (getOrEnforceKnownAlignment(Arg, ByValAlignment, DL, TheCall,
865                                    &IFI.ACT->getAssumptionCache(*Caller)) >=
866         ByValAlignment)
867       return Arg;
868     
869     // Otherwise, we have to make a memcpy to get a safe alignment.  This is bad
870     // for code quality, but rarely happens and is required for correctness.
871   }
872
873   // Create the alloca.  If we have DataLayout, use nice alignment.
874   unsigned Align =
875       Caller->getParent()->getDataLayout().getPrefTypeAlignment(AggTy);
876
877   // If the byval had an alignment specified, we *must* use at least that
878   // alignment, as it is required by the byval argument (and uses of the
879   // pointer inside the callee).
880   Align = std::max(Align, ByValAlignment);
881   
882   Value *NewAlloca = new AllocaInst(AggTy, nullptr, Align, Arg->getName(), 
883                                     &*Caller->begin()->begin());
884   IFI.StaticAllocas.push_back(cast<AllocaInst>(NewAlloca));
885   
886   // Uses of the argument in the function should use our new alloca
887   // instead.
888   return NewAlloca;
889 }
890
891 // Check whether this Value is used by a lifetime intrinsic.
892 static bool isUsedByLifetimeMarker(Value *V) {
893   for (User *U : V->users()) {
894     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
895       switch (II->getIntrinsicID()) {
896       default: break;
897       case Intrinsic::lifetime_start:
898       case Intrinsic::lifetime_end:
899         return true;
900       }
901     }
902   }
903   return false;
904 }
905
906 // Check whether the given alloca already has
907 // lifetime.start or lifetime.end intrinsics.
908 static bool hasLifetimeMarkers(AllocaInst *AI) {
909   Type *Ty = AI->getType();
910   Type *Int8PtrTy = Type::getInt8PtrTy(Ty->getContext(),
911                                        Ty->getPointerAddressSpace());
912   if (Ty == Int8PtrTy)
913     return isUsedByLifetimeMarker(AI);
914
915   // Do a scan to find all the casts to i8*.
916   for (User *U : AI->users()) {
917     if (U->getType() != Int8PtrTy) continue;
918     if (U->stripPointerCasts() != AI) continue;
919     if (isUsedByLifetimeMarker(U))
920       return true;
921   }
922   return false;
923 }
924
925 /// Rebuild the entire inlined-at chain for this instruction so that the top of
926 /// the chain now is inlined-at the new call site.
927 static DebugLoc
928 updateInlinedAtInfo(DebugLoc DL, DILocation *InlinedAtNode, LLVMContext &Ctx,
929                     DenseMap<const DILocation *, DILocation *> &IANodes) {
930   SmallVector<DILocation *, 3> InlinedAtLocations;
931   DILocation *Last = InlinedAtNode;
932   DILocation *CurInlinedAt = DL;
933
934   // Gather all the inlined-at nodes
935   while (DILocation *IA = CurInlinedAt->getInlinedAt()) {
936     // Skip any we've already built nodes for
937     if (DILocation *Found = IANodes[IA]) {
938       Last = Found;
939       break;
940     }
941
942     InlinedAtLocations.push_back(IA);
943     CurInlinedAt = IA;
944   }
945
946   // Starting from the top, rebuild the nodes to point to the new inlined-at
947   // location (then rebuilding the rest of the chain behind it) and update the
948   // map of already-constructed inlined-at nodes.
949   for (const DILocation *MD : make_range(InlinedAtLocations.rbegin(),
950                                          InlinedAtLocations.rend())) {
951     Last = IANodes[MD] = DILocation::getDistinct(
952         Ctx, MD->getLine(), MD->getColumn(), MD->getScope(), Last);
953   }
954
955   // And finally create the normal location for this instruction, referring to
956   // the new inlined-at chain.
957   return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(), Last);
958 }
959
960 /// Update inlined instructions' line numbers to
961 /// to encode location where these instructions are inlined.
962 static void fixupLineNumbers(Function *Fn, Function::iterator FI,
963                              Instruction *TheCall) {
964   DebugLoc TheCallDL = TheCall->getDebugLoc();
965   if (!TheCallDL)
966     return;
967
968   auto &Ctx = Fn->getContext();
969   DILocation *InlinedAtNode = TheCallDL;
970
971   // Create a unique call site, not to be confused with any other call from the
972   // same location.
973   InlinedAtNode = DILocation::getDistinct(
974       Ctx, InlinedAtNode->getLine(), InlinedAtNode->getColumn(),
975       InlinedAtNode->getScope(), InlinedAtNode->getInlinedAt());
976
977   // Cache the inlined-at nodes as they're built so they are reused, without
978   // this every instruction's inlined-at chain would become distinct from each
979   // other.
980   DenseMap<const DILocation *, DILocation *> IANodes;
981
982   for (; FI != Fn->end(); ++FI) {
983     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
984          BI != BE; ++BI) {
985       DebugLoc DL = BI->getDebugLoc();
986       if (!DL) {
987         // If the inlined instruction has no line number, make it look as if it
988         // originates from the call location. This is important for
989         // ((__always_inline__, __nodebug__)) functions which must use caller
990         // location for all instructions in their function body.
991
992         // Don't update static allocas, as they may get moved later.
993         if (auto *AI = dyn_cast<AllocaInst>(BI))
994           if (isa<Constant>(AI->getArraySize()))
995             continue;
996
997         BI->setDebugLoc(TheCallDL);
998       } else {
999         BI->setDebugLoc(updateInlinedAtInfo(DL, InlinedAtNode, BI->getContext(), IANodes));
1000       }
1001     }
1002   }
1003 }
1004
1005 /// This function inlines the called function into the basic block of the
1006 /// caller. This returns false if it is not possible to inline this call.
1007 /// The program is still in a well defined state if this occurs though.
1008 ///
1009 /// Note that this only does one level of inlining.  For example, if the
1010 /// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
1011 /// exists in the instruction stream.  Similarly this will inline a recursive
1012 /// function by one level.
1013 bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
1014                           AAResults *CalleeAAR, bool InsertLifetime) {
1015   Instruction *TheCall = CS.getInstruction();
1016   assert(TheCall->getParent() && TheCall->getParent()->getParent() &&
1017          "Instruction not in function!");
1018
1019   // If IFI has any state in it, zap it before we fill it in.
1020   IFI.reset();
1021   
1022   const Function *CalledFunc = CS.getCalledFunction();
1023   if (!CalledFunc ||              // Can't inline external function or indirect
1024       CalledFunc->isDeclaration() || // call, or call to a vararg function!
1025       CalledFunc->getFunctionType()->isVarArg()) return false;
1026
1027   // If the call to the callee cannot throw, set the 'nounwind' flag on any
1028   // calls that we inline.
1029   bool MarkNoUnwind = CS.doesNotThrow();
1030
1031   BasicBlock *OrigBB = TheCall->getParent();
1032   Function *Caller = OrigBB->getParent();
1033
1034   // GC poses two hazards to inlining, which only occur when the callee has GC:
1035   //  1. If the caller has no GC, then the callee's GC must be propagated to the
1036   //     caller.
1037   //  2. If the caller has a differing GC, it is invalid to inline.
1038   if (CalledFunc->hasGC()) {
1039     if (!Caller->hasGC())
1040       Caller->setGC(CalledFunc->getGC());
1041     else if (CalledFunc->getGC() != Caller->getGC())
1042       return false;
1043   }
1044
1045   // Get the personality function from the callee if it contains a landing pad.
1046   Constant *CalledPersonality =
1047       CalledFunc->hasPersonalityFn() ? CalledFunc->getPersonalityFn() : nullptr;
1048
1049   // Find the personality function used by the landing pads of the caller. If it
1050   // exists, then check to see that it matches the personality function used in
1051   // the callee.
1052   Constant *CallerPersonality =
1053       Caller->hasPersonalityFn() ? Caller->getPersonalityFn() : nullptr;
1054   if (CalledPersonality) {
1055     if (!CallerPersonality)
1056       Caller->setPersonalityFn(CalledPersonality);
1057     // If the personality functions match, then we can perform the
1058     // inlining. Otherwise, we can't inline.
1059     // TODO: This isn't 100% true. Some personality functions are proper
1060     //       supersets of others and can be used in place of the other.
1061     else if (CalledPersonality != CallerPersonality)
1062       return false;
1063   }
1064
1065   // Get an iterator to the last basic block in the function, which will have
1066   // the new function inlined after it.
1067   Function::iterator LastBlock = &Caller->back();
1068
1069   // Make sure to capture all of the return instructions from the cloned
1070   // function.
1071   SmallVector<ReturnInst*, 8> Returns;
1072   ClonedCodeInfo InlinedFunctionInfo;
1073   Function::iterator FirstNewBlock;
1074
1075   { // Scope to destroy VMap after cloning.
1076     ValueToValueMapTy VMap;
1077     // Keep a list of pair (dst, src) to emit byval initializations.
1078     SmallVector<std::pair<Value*, Value*>, 4> ByValInit;
1079
1080     auto &DL = Caller->getParent()->getDataLayout();
1081
1082     assert(CalledFunc->arg_size() == CS.arg_size() &&
1083            "No varargs calls can be inlined!");
1084
1085     // Calculate the vector of arguments to pass into the function cloner, which
1086     // matches up the formal to the actual argument values.
1087     CallSite::arg_iterator AI = CS.arg_begin();
1088     unsigned ArgNo = 0;
1089     for (Function::const_arg_iterator I = CalledFunc->arg_begin(),
1090          E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) {
1091       Value *ActualArg = *AI;
1092
1093       // When byval arguments actually inlined, we need to make the copy implied
1094       // by them explicit.  However, we don't do this if the callee is readonly
1095       // or readnone, because the copy would be unneeded: the callee doesn't
1096       // modify the struct.
1097       if (CS.isByValArgument(ArgNo)) {
1098         ActualArg = HandleByValArgument(ActualArg, TheCall, CalledFunc, IFI,
1099                                         CalledFunc->getParamAlignment(ArgNo+1));
1100         if (ActualArg != *AI)
1101           ByValInit.push_back(std::make_pair(ActualArg, (Value*) *AI));
1102       }
1103
1104       VMap[I] = ActualArg;
1105     }
1106
1107     // Add alignment assumptions if necessary. We do this before the inlined
1108     // instructions are actually cloned into the caller so that we can easily
1109     // check what will be known at the start of the inlined code.
1110     AddAlignmentAssumptions(CS, IFI);
1111
1112     // We want the inliner to prune the code as it copies.  We would LOVE to
1113     // have no dead or constant instructions leftover after inlining occurs
1114     // (which can happen, e.g., because an argument was constant), but we'll be
1115     // happy with whatever the cloner can do.
1116     CloneAndPruneFunctionInto(Caller, CalledFunc, VMap,
1117                               /*ModuleLevelChanges=*/false, Returns, ".i",
1118                               &InlinedFunctionInfo, TheCall);
1119
1120     // Remember the first block that is newly cloned over.
1121     FirstNewBlock = LastBlock; ++FirstNewBlock;
1122
1123     // Inject byval arguments initialization.
1124     for (std::pair<Value*, Value*> &Init : ByValInit)
1125       HandleByValArgumentInit(Init.first, Init.second, Caller->getParent(),
1126                               FirstNewBlock, IFI);
1127
1128     // Update the callgraph if requested.
1129     if (IFI.CG)
1130       UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI);
1131
1132     // Update inlined instructions' line number information.
1133     fixupLineNumbers(Caller, FirstNewBlock, TheCall);
1134
1135     // Clone existing noalias metadata if necessary.
1136     CloneAliasScopeMetadata(CS, VMap);
1137
1138     // Add noalias metadata if necessary.
1139     AddAliasScopeMetadata(CS, VMap, DL, CalleeAAR);
1140
1141     // FIXME: We could register any cloned assumptions instead of clearing the
1142     // whole function's cache.
1143     if (IFI.ACT)
1144       IFI.ACT->getAssumptionCache(*Caller).clear();
1145   }
1146
1147   // If there are any alloca instructions in the block that used to be the entry
1148   // block for the callee, move them to the entry block of the caller.  First
1149   // calculate which instruction they should be inserted before.  We insert the
1150   // instructions at the end of the current alloca list.
1151   {
1152     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
1153     for (BasicBlock::iterator I = FirstNewBlock->begin(),
1154          E = FirstNewBlock->end(); I != E; ) {
1155       AllocaInst *AI = dyn_cast<AllocaInst>(I++);
1156       if (!AI) continue;
1157       
1158       // If the alloca is now dead, remove it.  This often occurs due to code
1159       // specialization.
1160       if (AI->use_empty()) {
1161         AI->eraseFromParent();
1162         continue;
1163       }
1164
1165       if (!isa<Constant>(AI->getArraySize()))
1166         continue;
1167       
1168       // Keep track of the static allocas that we inline into the caller.
1169       IFI.StaticAllocas.push_back(AI);
1170       
1171       // Scan for the block of allocas that we can move over, and move them
1172       // all at once.
1173       while (isa<AllocaInst>(I) &&
1174              isa<Constant>(cast<AllocaInst>(I)->getArraySize())) {
1175         IFI.StaticAllocas.push_back(cast<AllocaInst>(I));
1176         ++I;
1177       }
1178
1179       // Transfer all of the allocas over in a block.  Using splice means
1180       // that the instructions aren't removed from the symbol table, then
1181       // reinserted.
1182       Caller->getEntryBlock().getInstList().splice(InsertPoint,
1183                                                    FirstNewBlock->getInstList(),
1184                                                    AI, I);
1185     }
1186     // Move any dbg.declares describing the allocas into the entry basic block.
1187     DIBuilder DIB(*Caller->getParent());
1188     for (auto &AI : IFI.StaticAllocas)
1189       replaceDbgDeclareForAlloca(AI, AI, DIB, /*Deref=*/false);
1190   }
1191
1192   bool InlinedMustTailCalls = false;
1193   if (InlinedFunctionInfo.ContainsCalls) {
1194     CallInst::TailCallKind CallSiteTailKind = CallInst::TCK_None;
1195     if (CallInst *CI = dyn_cast<CallInst>(TheCall))
1196       CallSiteTailKind = CI->getTailCallKind();
1197
1198     for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E;
1199          ++BB) {
1200       for (Instruction &I : *BB) {
1201         CallInst *CI = dyn_cast<CallInst>(&I);
1202         if (!CI)
1203           continue;
1204
1205         // We need to reduce the strength of any inlined tail calls.  For
1206         // musttail, we have to avoid introducing potential unbounded stack
1207         // growth.  For example, if functions 'f' and 'g' are mutually recursive
1208         // with musttail, we can inline 'g' into 'f' so long as we preserve
1209         // musttail on the cloned call to 'f'.  If either the inlined call site
1210         // or the cloned call site is *not* musttail, the program already has
1211         // one frame of stack growth, so it's safe to remove musttail.  Here is
1212         // a table of example transformations:
1213         //
1214         //    f -> musttail g -> musttail f  ==>  f -> musttail f
1215         //    f -> musttail g ->     tail f  ==>  f ->     tail f
1216         //    f ->          g -> musttail f  ==>  f ->          f
1217         //    f ->          g ->     tail f  ==>  f ->          f
1218         CallInst::TailCallKind ChildTCK = CI->getTailCallKind();
1219         ChildTCK = std::min(CallSiteTailKind, ChildTCK);
1220         CI->setTailCallKind(ChildTCK);
1221         InlinedMustTailCalls |= CI->isMustTailCall();
1222
1223         // Calls inlined through a 'nounwind' call site should be marked
1224         // 'nounwind'.
1225         if (MarkNoUnwind)
1226           CI->setDoesNotThrow();
1227       }
1228     }
1229   }
1230
1231   // Leave lifetime markers for the static alloca's, scoping them to the
1232   // function we just inlined.
1233   if (InsertLifetime && !IFI.StaticAllocas.empty()) {
1234     IRBuilder<> builder(FirstNewBlock->begin());
1235     for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) {
1236       AllocaInst *AI = IFI.StaticAllocas[ai];
1237
1238       // If the alloca is already scoped to something smaller than the whole
1239       // function then there's no need to add redundant, less accurate markers.
1240       if (hasLifetimeMarkers(AI))
1241         continue;
1242
1243       // Try to determine the size of the allocation.
1244       ConstantInt *AllocaSize = nullptr;
1245       if (ConstantInt *AIArraySize =
1246           dyn_cast<ConstantInt>(AI->getArraySize())) {
1247         auto &DL = Caller->getParent()->getDataLayout();
1248         Type *AllocaType = AI->getAllocatedType();
1249         uint64_t AllocaTypeSize = DL.getTypeAllocSize(AllocaType);
1250         uint64_t AllocaArraySize = AIArraySize->getLimitedValue();
1251
1252         // Don't add markers for zero-sized allocas.
1253         if (AllocaArraySize == 0)
1254           continue;
1255
1256         // Check that array size doesn't saturate uint64_t and doesn't
1257         // overflow when it's multiplied by type size.
1258         if (AllocaArraySize != ~0ULL &&
1259             UINT64_MAX / AllocaArraySize >= AllocaTypeSize) {
1260           AllocaSize = ConstantInt::get(Type::getInt64Ty(AI->getContext()),
1261                                         AllocaArraySize * AllocaTypeSize);
1262         }
1263       }
1264
1265       builder.CreateLifetimeStart(AI, AllocaSize);
1266       for (ReturnInst *RI : Returns) {
1267         // Don't insert llvm.lifetime.end calls between a musttail call and a
1268         // return.  The return kills all local allocas.
1269         if (InlinedMustTailCalls &&
1270             RI->getParent()->getTerminatingMustTailCall())
1271           continue;
1272         IRBuilder<>(RI).CreateLifetimeEnd(AI, AllocaSize);
1273       }
1274     }
1275   }
1276
1277   // If the inlined code contained dynamic alloca instructions, wrap the inlined
1278   // code with llvm.stacksave/llvm.stackrestore intrinsics.
1279   if (InlinedFunctionInfo.ContainsDynamicAllocas) {
1280     Module *M = Caller->getParent();
1281     // Get the two intrinsics we care about.
1282     Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave);
1283     Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore);
1284
1285     // Insert the llvm.stacksave.
1286     CallInst *SavedPtr = IRBuilder<>(FirstNewBlock, FirstNewBlock->begin())
1287                              .CreateCall(StackSave, {}, "savedstack");
1288
1289     // Insert a call to llvm.stackrestore before any return instructions in the
1290     // inlined function.
1291     for (ReturnInst *RI : Returns) {
1292       // Don't insert llvm.stackrestore calls between a musttail call and a
1293       // return.  The return will restore the stack pointer.
1294       if (InlinedMustTailCalls && RI->getParent()->getTerminatingMustTailCall())
1295         continue;
1296       IRBuilder<>(RI).CreateCall(StackRestore, SavedPtr);
1297     }
1298   }
1299
1300   // If we are inlining for an invoke instruction, we must make sure to rewrite
1301   // any call instructions into invoke instructions.
1302   if (auto *II = dyn_cast<InvokeInst>(TheCall)) {
1303     BasicBlock *UnwindDest = II->getUnwindDest();
1304     Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI();
1305     if (isa<LandingPadInst>(FirstNonPHI)) {
1306       HandleInlinedLandingPad(II, FirstNewBlock, InlinedFunctionInfo);
1307     } else {
1308       HandleInlinedEHPad(II, FirstNewBlock, InlinedFunctionInfo);
1309     }
1310   }
1311
1312   // Handle any inlined musttail call sites.  In order for a new call site to be
1313   // musttail, the source of the clone and the inlined call site must have been
1314   // musttail.  Therefore it's safe to return without merging control into the
1315   // phi below.
1316   if (InlinedMustTailCalls) {
1317     // Check if we need to bitcast the result of any musttail calls.
1318     Type *NewRetTy = Caller->getReturnType();
1319     bool NeedBitCast = !TheCall->use_empty() && TheCall->getType() != NewRetTy;
1320
1321     // Handle the returns preceded by musttail calls separately.
1322     SmallVector<ReturnInst *, 8> NormalReturns;
1323     for (ReturnInst *RI : Returns) {
1324       CallInst *ReturnedMustTail =
1325           RI->getParent()->getTerminatingMustTailCall();
1326       if (!ReturnedMustTail) {
1327         NormalReturns.push_back(RI);
1328         continue;
1329       }
1330       if (!NeedBitCast)
1331         continue;
1332
1333       // Delete the old return and any preceding bitcast.
1334       BasicBlock *CurBB = RI->getParent();
1335       auto *OldCast = dyn_cast_or_null<BitCastInst>(RI->getReturnValue());
1336       RI->eraseFromParent();
1337       if (OldCast)
1338         OldCast->eraseFromParent();
1339
1340       // Insert a new bitcast and return with the right type.
1341       IRBuilder<> Builder(CurBB);
1342       Builder.CreateRet(Builder.CreateBitCast(ReturnedMustTail, NewRetTy));
1343     }
1344
1345     // Leave behind the normal returns so we can merge control flow.
1346     std::swap(Returns, NormalReturns);
1347   }
1348
1349   // If we cloned in _exactly one_ basic block, and if that block ends in a
1350   // return instruction, we splice the body of the inlined callee directly into
1351   // the calling basic block.
1352   if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) {
1353     // Move all of the instructions right before the call.
1354     OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(),
1355                                  FirstNewBlock->begin(), FirstNewBlock->end());
1356     // Remove the cloned basic block.
1357     Caller->getBasicBlockList().pop_back();
1358
1359     // If the call site was an invoke instruction, add a branch to the normal
1360     // destination.
1361     if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
1362       BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall);
1363       NewBr->setDebugLoc(Returns[0]->getDebugLoc());
1364     }
1365
1366     // If the return instruction returned a value, replace uses of the call with
1367     // uses of the returned value.
1368     if (!TheCall->use_empty()) {
1369       ReturnInst *R = Returns[0];
1370       if (TheCall == R->getReturnValue())
1371         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
1372       else
1373         TheCall->replaceAllUsesWith(R->getReturnValue());
1374     }
1375     // Since we are now done with the Call/Invoke, we can delete it.
1376     TheCall->eraseFromParent();
1377
1378     // Since we are now done with the return instruction, delete it also.
1379     Returns[0]->eraseFromParent();
1380
1381     // We are now done with the inlining.
1382     return true;
1383   }
1384
1385   // Otherwise, we have the normal case, of more than one block to inline or
1386   // multiple return sites.
1387
1388   // We want to clone the entire callee function into the hole between the
1389   // "starter" and "ender" blocks.  How we accomplish this depends on whether
1390   // this is an invoke instruction or a call instruction.
1391   BasicBlock *AfterCallBB;
1392   BranchInst *CreatedBranchToNormalDest = nullptr;
1393   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
1394
1395     // Add an unconditional branch to make this look like the CallInst case...
1396     CreatedBranchToNormalDest = BranchInst::Create(II->getNormalDest(), TheCall);
1397
1398     // Split the basic block.  This guarantees that no PHI nodes will have to be
1399     // updated due to new incoming edges, and make the invoke case more
1400     // symmetric to the call case.
1401     AfterCallBB = OrigBB->splitBasicBlock(CreatedBranchToNormalDest,
1402                                           CalledFunc->getName()+".exit");
1403
1404   } else {  // It's a call
1405     // If this is a call instruction, we need to split the basic block that
1406     // the call lives in.
1407     //
1408     AfterCallBB = OrigBB->splitBasicBlock(TheCall,
1409                                           CalledFunc->getName()+".exit");
1410   }
1411
1412   // Change the branch that used to go to AfterCallBB to branch to the first
1413   // basic block of the inlined function.
1414   //
1415   TerminatorInst *Br = OrigBB->getTerminator();
1416   assert(Br && Br->getOpcode() == Instruction::Br &&
1417          "splitBasicBlock broken!");
1418   Br->setOperand(0, FirstNewBlock);
1419
1420
1421   // Now that the function is correct, make it a little bit nicer.  In
1422   // particular, move the basic blocks inserted from the end of the function
1423   // into the space made by splitting the source basic block.
1424   Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(),
1425                                      FirstNewBlock, Caller->end());
1426
1427   // Handle all of the return instructions that we just cloned in, and eliminate
1428   // any users of the original call/invoke instruction.
1429   Type *RTy = CalledFunc->getReturnType();
1430
1431   PHINode *PHI = nullptr;
1432   if (Returns.size() > 1) {
1433     // The PHI node should go at the front of the new basic block to merge all
1434     // possible incoming values.
1435     if (!TheCall->use_empty()) {
1436       PHI = PHINode::Create(RTy, Returns.size(), TheCall->getName(),
1437                             AfterCallBB->begin());
1438       // Anything that used the result of the function call should now use the
1439       // PHI node as their operand.
1440       TheCall->replaceAllUsesWith(PHI);
1441     }
1442
1443     // Loop over all of the return instructions adding entries to the PHI node
1444     // as appropriate.
1445     if (PHI) {
1446       for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
1447         ReturnInst *RI = Returns[i];
1448         assert(RI->getReturnValue()->getType() == PHI->getType() &&
1449                "Ret value not consistent in function!");
1450         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
1451       }
1452     }
1453
1454
1455     // Add a branch to the merge points and remove return instructions.
1456     DebugLoc Loc;
1457     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
1458       ReturnInst *RI = Returns[i];
1459       BranchInst* BI = BranchInst::Create(AfterCallBB, RI);
1460       Loc = RI->getDebugLoc();
1461       BI->setDebugLoc(Loc);
1462       RI->eraseFromParent();
1463     }
1464     // We need to set the debug location to *somewhere* inside the
1465     // inlined function. The line number may be nonsensical, but the
1466     // instruction will at least be associated with the right
1467     // function.
1468     if (CreatedBranchToNormalDest)
1469       CreatedBranchToNormalDest->setDebugLoc(Loc);
1470   } else if (!Returns.empty()) {
1471     // Otherwise, if there is exactly one return value, just replace anything
1472     // using the return value of the call with the computed value.
1473     if (!TheCall->use_empty()) {
1474       if (TheCall == Returns[0]->getReturnValue())
1475         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
1476       else
1477         TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
1478     }
1479
1480     // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
1481     BasicBlock *ReturnBB = Returns[0]->getParent();
1482     ReturnBB->replaceAllUsesWith(AfterCallBB);
1483
1484     // Splice the code from the return block into the block that it will return
1485     // to, which contains the code that was after the call.
1486     AfterCallBB->getInstList().splice(AfterCallBB->begin(),
1487                                       ReturnBB->getInstList());
1488
1489     if (CreatedBranchToNormalDest)
1490       CreatedBranchToNormalDest->setDebugLoc(Returns[0]->getDebugLoc());
1491
1492     // Delete the return instruction now and empty ReturnBB now.
1493     Returns[0]->eraseFromParent();
1494     ReturnBB->eraseFromParent();
1495   } else if (!TheCall->use_empty()) {
1496     // No returns, but something is using the return value of the call.  Just
1497     // nuke the result.
1498     TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
1499   }
1500
1501   // Since we are now done with the Call/Invoke, we can delete it.
1502   TheCall->eraseFromParent();
1503
1504   // If we inlined any musttail calls and the original return is now
1505   // unreachable, delete it.  It can only contain a bitcast and ret.
1506   if (InlinedMustTailCalls && pred_begin(AfterCallBB) == pred_end(AfterCallBB))
1507     AfterCallBB->eraseFromParent();
1508
1509   // We should always be able to fold the entry block of the function into the
1510   // single predecessor of the block...
1511   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
1512   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
1513
1514   // Splice the code entry block into calling block, right before the
1515   // unconditional branch.
1516   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes
1517   OrigBB->getInstList().splice(Br, CalleeEntry->getInstList());
1518
1519   // Remove the unconditional branch.
1520   OrigBB->getInstList().erase(Br);
1521
1522   // Now we can remove the CalleeEntry block, which is now empty.
1523   Caller->getBasicBlockList().erase(CalleeEntry);
1524
1525   // If we inserted a phi node, check to see if it has a single value (e.g. all
1526   // the entries are the same or undef).  If so, remove the PHI so it doesn't
1527   // block other optimizations.
1528   if (PHI) {
1529     auto &DL = Caller->getParent()->getDataLayout();
1530     if (Value *V = SimplifyInstruction(PHI, DL, nullptr, nullptr,
1531                                        &IFI.ACT->getAssumptionCache(*Caller))) {
1532       PHI->replaceAllUsesWith(V);
1533       PHI->eraseFromParent();
1534     }
1535   }
1536
1537   return true;
1538 }