xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/Utils/InlineFunction.cpp (revision e8d8bef961a50d4dc22501cde4fb9fb0be1b2532)
1 //===- InlineFunction.cpp - Code to perform function inlining -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements inlining of a function into a call site, resolving
10 // parameters and the return value as appropriate.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/None.h"
16 #include "llvm/ADT/Optional.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringExtras.h"
22 #include "llvm/ADT/iterator_range.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/AssumptionCache.h"
25 #include "llvm/Analysis/BlockFrequencyInfo.h"
26 #include "llvm/Analysis/CallGraph.h"
27 #include "llvm/Analysis/CaptureTracking.h"
28 #include "llvm/Analysis/EHPersonalities.h"
29 #include "llvm/Analysis/InstructionSimplify.h"
30 #include "llvm/Analysis/ProfileSummaryInfo.h"
31 #include "llvm/Transforms/Utils/Local.h"
32 #include "llvm/Analysis/ValueTracking.h"
33 #include "llvm/Analysis/VectorUtils.h"
34 #include "llvm/IR/Argument.h"
35 #include "llvm/IR/BasicBlock.h"
36 #include "llvm/IR/CFG.h"
37 #include "llvm/IR/Constant.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/DIBuilder.h"
40 #include "llvm/IR/DataLayout.h"
41 #include "llvm/IR/DebugInfoMetadata.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/IR/DerivedTypes.h"
44 #include "llvm/IR/Dominators.h"
45 #include "llvm/IR/Function.h"
46 #include "llvm/IR/IRBuilder.h"
47 #include "llvm/IR/InstrTypes.h"
48 #include "llvm/IR/Instruction.h"
49 #include "llvm/IR/Instructions.h"
50 #include "llvm/IR/IntrinsicInst.h"
51 #include "llvm/IR/Intrinsics.h"
52 #include "llvm/IR/LLVMContext.h"
53 #include "llvm/IR/MDBuilder.h"
54 #include "llvm/IR/Metadata.h"
55 #include "llvm/IR/Module.h"
56 #include "llvm/IR/Type.h"
57 #include "llvm/IR/User.h"
58 #include "llvm/IR/Value.h"
59 #include "llvm/Support/Casting.h"
60 #include "llvm/Support/CommandLine.h"
61 #include "llvm/Support/ErrorHandling.h"
62 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
63 #include "llvm/Transforms/Utils/Cloning.h"
64 #include "llvm/Transforms/Utils/ValueMapper.h"
65 #include <algorithm>
66 #include <cassert>
67 #include <cstdint>
68 #include <iterator>
69 #include <limits>
70 #include <string>
71 #include <utility>
72 #include <vector>
73 
74 using namespace llvm;
75 using ProfileCount = Function::ProfileCount;
76 
77 static cl::opt<bool>
78 EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true),
79   cl::Hidden,
80   cl::desc("Convert noalias attributes to metadata during inlining."));
81 
82 static cl::opt<bool>
83     UseNoAliasIntrinsic("use-noalias-intrinsic-during-inlining", cl::Hidden,
84                         cl::ZeroOrMore, cl::init(true),
85                         cl::desc("Use the llvm.experimental.noalias.scope.decl "
86                                  "intrinsic during inlining."));
87 
88 // Disabled by default, because the added alignment assumptions may increase
89 // compile-time and block optimizations. This option is not suitable for use
90 // with frontends that emit comprehensive parameter alignment annotations.
91 static cl::opt<bool>
92 PreserveAlignmentAssumptions("preserve-alignment-assumptions-during-inlining",
93   cl::init(false), cl::Hidden,
94   cl::desc("Convert align attributes to assumptions during inlining."));
95 
96 static cl::opt<bool> UpdateReturnAttributes(
97         "update-return-attrs", cl::init(true), cl::Hidden,
98             cl::desc("Update return attributes on calls within inlined body"));
99 
100 static cl::opt<unsigned> InlinerAttributeWindow(
101     "max-inst-checked-for-throw-during-inlining", cl::Hidden,
102     cl::desc("the maximum number of instructions analyzed for may throw during "
103              "attribute inference in inlined body"),
104     cl::init(4));
105 
106 namespace {
107 
108   /// A class for recording information about inlining a landing pad.
109   class LandingPadInliningInfo {
110     /// Destination of the invoke's unwind.
111     BasicBlock *OuterResumeDest;
112 
113     /// Destination for the callee's resume.
114     BasicBlock *InnerResumeDest = nullptr;
115 
116     /// LandingPadInst associated with the invoke.
117     LandingPadInst *CallerLPad = nullptr;
118 
119     /// PHI for EH values from landingpad insts.
120     PHINode *InnerEHValuesPHI = nullptr;
121 
122     SmallVector<Value*, 8> UnwindDestPHIValues;
123 
124   public:
125     LandingPadInliningInfo(InvokeInst *II)
126         : OuterResumeDest(II->getUnwindDest()) {
127       // If there are PHI nodes in the unwind destination block, we need to keep
128       // track of which values came into them from the invoke before removing
129       // the edge from this block.
130       BasicBlock *InvokeBB = II->getParent();
131       BasicBlock::iterator I = OuterResumeDest->begin();
132       for (; isa<PHINode>(I); ++I) {
133         // Save the value to use for this edge.
134         PHINode *PHI = cast<PHINode>(I);
135         UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB));
136       }
137 
138       CallerLPad = cast<LandingPadInst>(I);
139     }
140 
141     /// The outer unwind destination is the target of
142     /// unwind edges introduced for calls within the inlined function.
143     BasicBlock *getOuterResumeDest() const {
144       return OuterResumeDest;
145     }
146 
147     BasicBlock *getInnerResumeDest();
148 
149     LandingPadInst *getLandingPadInst() const { return CallerLPad; }
150 
151     /// Forward the 'resume' instruction to the caller's landing pad block.
152     /// When the landing pad block has only one predecessor, this is
153     /// a simple branch. When there is more than one predecessor, we need to
154     /// split the landing pad block after the landingpad instruction and jump
155     /// to there.
156     void forwardResume(ResumeInst *RI,
157                        SmallPtrSetImpl<LandingPadInst*> &InlinedLPads);
158 
159     /// Add incoming-PHI values to the unwind destination block for the given
160     /// basic block, using the values for the original invoke's source block.
161     void addIncomingPHIValuesFor(BasicBlock *BB) const {
162       addIncomingPHIValuesForInto(BB, OuterResumeDest);
163     }
164 
165     void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const {
166       BasicBlock::iterator I = dest->begin();
167       for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
168         PHINode *phi = cast<PHINode>(I);
169         phi->addIncoming(UnwindDestPHIValues[i], src);
170       }
171     }
172   };
173 
174 } // end anonymous namespace
175 
176 /// Get or create a target for the branch from ResumeInsts.
177 BasicBlock *LandingPadInliningInfo::getInnerResumeDest() {
178   if (InnerResumeDest) return InnerResumeDest;
179 
180   // Split the landing pad.
181   BasicBlock::iterator SplitPoint = ++CallerLPad->getIterator();
182   InnerResumeDest =
183     OuterResumeDest->splitBasicBlock(SplitPoint,
184                                      OuterResumeDest->getName() + ".body");
185 
186   // The number of incoming edges we expect to the inner landing pad.
187   const unsigned PHICapacity = 2;
188 
189   // Create corresponding new PHIs for all the PHIs in the outer landing pad.
190   Instruction *InsertPoint = &InnerResumeDest->front();
191   BasicBlock::iterator I = OuterResumeDest->begin();
192   for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
193     PHINode *OuterPHI = cast<PHINode>(I);
194     PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity,
195                                         OuterPHI->getName() + ".lpad-body",
196                                         InsertPoint);
197     OuterPHI->replaceAllUsesWith(InnerPHI);
198     InnerPHI->addIncoming(OuterPHI, OuterResumeDest);
199   }
200 
201   // Create a PHI for the exception values.
202   InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity,
203                                      "eh.lpad-body", InsertPoint);
204   CallerLPad->replaceAllUsesWith(InnerEHValuesPHI);
205   InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest);
206 
207   // All done.
208   return InnerResumeDest;
209 }
210 
211 /// Forward the 'resume' instruction to the caller's landing pad block.
212 /// When the landing pad block has only one predecessor, this is a simple
213 /// branch. When there is more than one predecessor, we need to split the
214 /// landing pad block after the landingpad instruction and jump to there.
215 void LandingPadInliningInfo::forwardResume(
216     ResumeInst *RI, SmallPtrSetImpl<LandingPadInst *> &InlinedLPads) {
217   BasicBlock *Dest = getInnerResumeDest();
218   BasicBlock *Src = RI->getParent();
219 
220   BranchInst::Create(Dest, Src);
221 
222   // Update the PHIs in the destination. They were inserted in an order which
223   // makes this work.
224   addIncomingPHIValuesForInto(Src, Dest);
225 
226   InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src);
227   RI->eraseFromParent();
228 }
229 
230 /// Helper for getUnwindDestToken/getUnwindDestTokenHelper.
231 static Value *getParentPad(Value *EHPad) {
232   if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad))
233     return FPI->getParentPad();
234   return cast<CatchSwitchInst>(EHPad)->getParentPad();
235 }
236 
237 using UnwindDestMemoTy = DenseMap<Instruction *, Value *>;
238 
239 /// Helper for getUnwindDestToken that does the descendant-ward part of
240 /// the search.
241 static Value *getUnwindDestTokenHelper(Instruction *EHPad,
242                                        UnwindDestMemoTy &MemoMap) {
243   SmallVector<Instruction *, 8> Worklist(1, EHPad);
244 
245   while (!Worklist.empty()) {
246     Instruction *CurrentPad = Worklist.pop_back_val();
247     // We only put pads on the worklist that aren't in the MemoMap.  When
248     // we find an unwind dest for a pad we may update its ancestors, but
249     // the queue only ever contains uncles/great-uncles/etc. of CurrentPad,
250     // so they should never get updated while queued on the worklist.
251     assert(!MemoMap.count(CurrentPad));
252     Value *UnwindDestToken = nullptr;
253     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentPad)) {
254       if (CatchSwitch->hasUnwindDest()) {
255         UnwindDestToken = CatchSwitch->getUnwindDest()->getFirstNonPHI();
256       } else {
257         // Catchswitch doesn't have a 'nounwind' variant, and one might be
258         // annotated as "unwinds to caller" when really it's nounwind (see
259         // e.g. SimplifyCFGOpt::SimplifyUnreachable), so we can't infer the
260         // parent's unwind dest from this.  We can check its catchpads'
261         // descendants, since they might include a cleanuppad with an
262         // "unwinds to caller" cleanupret, which can be trusted.
263         for (auto HI = CatchSwitch->handler_begin(),
264                   HE = CatchSwitch->handler_end();
265              HI != HE && !UnwindDestToken; ++HI) {
266           BasicBlock *HandlerBlock = *HI;
267           auto *CatchPad = cast<CatchPadInst>(HandlerBlock->getFirstNonPHI());
268           for (User *Child : CatchPad->users()) {
269             // Intentionally ignore invokes here -- since the catchswitch is
270             // marked "unwind to caller", it would be a verifier error if it
271             // contained an invoke which unwinds out of it, so any invoke we'd
272             // encounter must unwind to some child of the catch.
273             if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child))
274               continue;
275 
276             Instruction *ChildPad = cast<Instruction>(Child);
277             auto Memo = MemoMap.find(ChildPad);
278             if (Memo == MemoMap.end()) {
279               // Haven't figured out this child pad yet; queue it.
280               Worklist.push_back(ChildPad);
281               continue;
282             }
283             // We've already checked this child, but might have found that
284             // it offers no proof either way.
285             Value *ChildUnwindDestToken = Memo->second;
286             if (!ChildUnwindDestToken)
287               continue;
288             // We already know the child's unwind dest, which can either
289             // be ConstantTokenNone to indicate unwind to caller, or can
290             // be another child of the catchpad.  Only the former indicates
291             // the unwind dest of the catchswitch.
292             if (isa<ConstantTokenNone>(ChildUnwindDestToken)) {
293               UnwindDestToken = ChildUnwindDestToken;
294               break;
295             }
296             assert(getParentPad(ChildUnwindDestToken) == CatchPad);
297           }
298         }
299       }
300     } else {
301       auto *CleanupPad = cast<CleanupPadInst>(CurrentPad);
302       for (User *U : CleanupPad->users()) {
303         if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
304           if (BasicBlock *RetUnwindDest = CleanupRet->getUnwindDest())
305             UnwindDestToken = RetUnwindDest->getFirstNonPHI();
306           else
307             UnwindDestToken = ConstantTokenNone::get(CleanupPad->getContext());
308           break;
309         }
310         Value *ChildUnwindDestToken;
311         if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
312           ChildUnwindDestToken = Invoke->getUnwindDest()->getFirstNonPHI();
313         } else if (isa<CleanupPadInst>(U) || isa<CatchSwitchInst>(U)) {
314           Instruction *ChildPad = cast<Instruction>(U);
315           auto Memo = MemoMap.find(ChildPad);
316           if (Memo == MemoMap.end()) {
317             // Haven't resolved this child yet; queue it and keep searching.
318             Worklist.push_back(ChildPad);
319             continue;
320           }
321           // We've checked this child, but still need to ignore it if it
322           // had no proof either way.
323           ChildUnwindDestToken = Memo->second;
324           if (!ChildUnwindDestToken)
325             continue;
326         } else {
327           // Not a relevant user of the cleanuppad
328           continue;
329         }
330         // In a well-formed program, the child/invoke must either unwind to
331         // an(other) child of the cleanup, or exit the cleanup.  In the
332         // first case, continue searching.
333         if (isa<Instruction>(ChildUnwindDestToken) &&
334             getParentPad(ChildUnwindDestToken) == CleanupPad)
335           continue;
336         UnwindDestToken = ChildUnwindDestToken;
337         break;
338       }
339     }
340     // If we haven't found an unwind dest for CurrentPad, we may have queued its
341     // children, so move on to the next in the worklist.
342     if (!UnwindDestToken)
343       continue;
344 
345     // Now we know that CurrentPad unwinds to UnwindDestToken.  It also exits
346     // any ancestors of CurrentPad up to but not including UnwindDestToken's
347     // parent pad.  Record this in the memo map, and check to see if the
348     // original EHPad being queried is one of the ones exited.
349     Value *UnwindParent;
350     if (auto *UnwindPad = dyn_cast<Instruction>(UnwindDestToken))
351       UnwindParent = getParentPad(UnwindPad);
352     else
353       UnwindParent = nullptr;
354     bool ExitedOriginalPad = false;
355     for (Instruction *ExitedPad = CurrentPad;
356          ExitedPad && ExitedPad != UnwindParent;
357          ExitedPad = dyn_cast<Instruction>(getParentPad(ExitedPad))) {
358       // Skip over catchpads since they just follow their catchswitches.
359       if (isa<CatchPadInst>(ExitedPad))
360         continue;
361       MemoMap[ExitedPad] = UnwindDestToken;
362       ExitedOriginalPad |= (ExitedPad == EHPad);
363     }
364 
365     if (ExitedOriginalPad)
366       return UnwindDestToken;
367 
368     // Continue the search.
369   }
370 
371   // No definitive information is contained within this funclet.
372   return nullptr;
373 }
374 
375 /// Given an EH pad, find where it unwinds.  If it unwinds to an EH pad,
376 /// return that pad instruction.  If it unwinds to caller, return
377 /// ConstantTokenNone.  If it does not have a definitive unwind destination,
378 /// return nullptr.
379 ///
380 /// This routine gets invoked for calls in funclets in inlinees when inlining
381 /// an invoke.  Since many funclets don't have calls inside them, it's queried
382 /// on-demand rather than building a map of pads to unwind dests up front.
383 /// Determining a funclet's unwind dest may require recursively searching its
384 /// descendants, and also ancestors and cousins if the descendants don't provide
385 /// an answer.  Since most funclets will have their unwind dest immediately
386 /// available as the unwind dest of a catchswitch or cleanupret, this routine
387 /// searches top-down from the given pad and then up. To avoid worst-case
388 /// quadratic run-time given that approach, it uses a memo map to avoid
389 /// re-processing funclet trees.  The callers that rewrite the IR as they go
390 /// take advantage of this, for correctness, by checking/forcing rewritten
391 /// pads' entries to match the original callee view.
392 static Value *getUnwindDestToken(Instruction *EHPad,
393                                  UnwindDestMemoTy &MemoMap) {
394   // Catchpads unwind to the same place as their catchswitch;
395   // redirct any queries on catchpads so the code below can
396   // deal with just catchswitches and cleanuppads.
397   if (auto *CPI = dyn_cast<CatchPadInst>(EHPad))
398     EHPad = CPI->getCatchSwitch();
399 
400   // Check if we've already determined the unwind dest for this pad.
401   auto Memo = MemoMap.find(EHPad);
402   if (Memo != MemoMap.end())
403     return Memo->second;
404 
405   // Search EHPad and, if necessary, its descendants.
406   Value *UnwindDestToken = getUnwindDestTokenHelper(EHPad, MemoMap);
407   assert((UnwindDestToken == nullptr) != (MemoMap.count(EHPad) != 0));
408   if (UnwindDestToken)
409     return UnwindDestToken;
410 
411   // No information is available for this EHPad from itself or any of its
412   // descendants.  An unwind all the way out to a pad in the caller would
413   // need also to agree with the unwind dest of the parent funclet, so
414   // search up the chain to try to find a funclet with information.  Put
415   // null entries in the memo map to avoid re-processing as we go up.
416   MemoMap[EHPad] = nullptr;
417 #ifndef NDEBUG
418   SmallPtrSet<Instruction *, 4> TempMemos;
419   TempMemos.insert(EHPad);
420 #endif
421   Instruction *LastUselessPad = EHPad;
422   Value *AncestorToken;
423   for (AncestorToken = getParentPad(EHPad);
424        auto *AncestorPad = dyn_cast<Instruction>(AncestorToken);
425        AncestorToken = getParentPad(AncestorToken)) {
426     // Skip over catchpads since they just follow their catchswitches.
427     if (isa<CatchPadInst>(AncestorPad))
428       continue;
429     // If the MemoMap had an entry mapping AncestorPad to nullptr, since we
430     // haven't yet called getUnwindDestTokenHelper for AncestorPad in this
431     // call to getUnwindDestToken, that would mean that AncestorPad had no
432     // information in itself, its descendants, or its ancestors.  If that
433     // were the case, then we should also have recorded the lack of information
434     // for the descendant that we're coming from.  So assert that we don't
435     // find a null entry in the MemoMap for AncestorPad.
436     assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]);
437     auto AncestorMemo = MemoMap.find(AncestorPad);
438     if (AncestorMemo == MemoMap.end()) {
439       UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap);
440     } else {
441       UnwindDestToken = AncestorMemo->second;
442     }
443     if (UnwindDestToken)
444       break;
445     LastUselessPad = AncestorPad;
446     MemoMap[LastUselessPad] = nullptr;
447 #ifndef NDEBUG
448     TempMemos.insert(LastUselessPad);
449 #endif
450   }
451 
452   // We know that getUnwindDestTokenHelper was called on LastUselessPad and
453   // returned nullptr (and likewise for EHPad and any of its ancestors up to
454   // LastUselessPad), so LastUselessPad has no information from below.  Since
455   // getUnwindDestTokenHelper must investigate all downward paths through
456   // no-information nodes to prove that a node has no information like this,
457   // and since any time it finds information it records it in the MemoMap for
458   // not just the immediately-containing funclet but also any ancestors also
459   // exited, it must be the case that, walking downward from LastUselessPad,
460   // visiting just those nodes which have not been mapped to an unwind dest
461   // by getUnwindDestTokenHelper (the nullptr TempMemos notwithstanding, since
462   // they are just used to keep getUnwindDestTokenHelper from repeating work),
463   // any node visited must have been exhaustively searched with no information
464   // for it found.
465   SmallVector<Instruction *, 8> Worklist(1, LastUselessPad);
466   while (!Worklist.empty()) {
467     Instruction *UselessPad = Worklist.pop_back_val();
468     auto Memo = MemoMap.find(UselessPad);
469     if (Memo != MemoMap.end() && Memo->second) {
470       // Here the name 'UselessPad' is a bit of a misnomer, because we've found
471       // that it is a funclet that does have information about unwinding to
472       // a particular destination; its parent was a useless pad.
473       // Since its parent has no information, the unwind edge must not escape
474       // the parent, and must target a sibling of this pad.  This local unwind
475       // gives us no information about EHPad.  Leave it and the subtree rooted
476       // at it alone.
477       assert(getParentPad(Memo->second) == getParentPad(UselessPad));
478       continue;
479     }
480     // We know we don't have information for UselesPad.  If it has an entry in
481     // the MemoMap (mapping it to nullptr), it must be one of the TempMemos
482     // added on this invocation of getUnwindDestToken; if a previous invocation
483     // recorded nullptr, it would have had to prove that the ancestors of
484     // UselessPad, which include LastUselessPad, had no information, and that
485     // in turn would have required proving that the descendants of
486     // LastUselesPad, which include EHPad, have no information about
487     // LastUselessPad, which would imply that EHPad was mapped to nullptr in
488     // the MemoMap on that invocation, which isn't the case if we got here.
489     assert(!MemoMap.count(UselessPad) || TempMemos.count(UselessPad));
490     // Assert as we enumerate users that 'UselessPad' doesn't have any unwind
491     // information that we'd be contradicting by making a map entry for it
492     // (which is something that getUnwindDestTokenHelper must have proved for
493     // us to get here).  Just assert on is direct users here; the checks in
494     // this downward walk at its descendants will verify that they don't have
495     // any unwind edges that exit 'UselessPad' either (i.e. they either have no
496     // unwind edges or unwind to a sibling).
497     MemoMap[UselessPad] = UnwindDestToken;
498     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) {
499       assert(CatchSwitch->getUnwindDest() == nullptr && "Expected useless pad");
500       for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) {
501         auto *CatchPad = HandlerBlock->getFirstNonPHI();
502         for (User *U : CatchPad->users()) {
503           assert(
504               (!isa<InvokeInst>(U) ||
505                (getParentPad(
506                     cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) ==
507                 CatchPad)) &&
508               "Expected useless pad");
509           if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
510             Worklist.push_back(cast<Instruction>(U));
511         }
512       }
513     } else {
514       assert(isa<CleanupPadInst>(UselessPad));
515       for (User *U : UselessPad->users()) {
516         assert(!isa<CleanupReturnInst>(U) && "Expected useless pad");
517         assert((!isa<InvokeInst>(U) ||
518                 (getParentPad(
519                      cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) ==
520                  UselessPad)) &&
521                "Expected useless pad");
522         if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
523           Worklist.push_back(cast<Instruction>(U));
524       }
525     }
526   }
527 
528   return UnwindDestToken;
529 }
530 
531 /// When we inline a basic block into an invoke,
532 /// we have to turn all of the calls that can throw into invokes.
533 /// This function analyze BB to see if there are any calls, and if so,
534 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
535 /// nodes in that block with the values specified in InvokeDestPHIValues.
536 static BasicBlock *HandleCallsInBlockInlinedThroughInvoke(
537     BasicBlock *BB, BasicBlock *UnwindEdge,
538     UnwindDestMemoTy *FuncletUnwindMap = nullptr) {
539   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
540     Instruction *I = &*BBI++;
541 
542     // We only need to check for function calls: inlined invoke
543     // instructions require no special handling.
544     CallInst *CI = dyn_cast<CallInst>(I);
545 
546     if (!CI || CI->doesNotThrow() || CI->isInlineAsm())
547       continue;
548 
549     // We do not need to (and in fact, cannot) convert possibly throwing calls
550     // to @llvm.experimental_deoptimize (resp. @llvm.experimental.guard) into
551     // invokes.  The caller's "segment" of the deoptimization continuation
552     // attached to the newly inlined @llvm.experimental_deoptimize
553     // (resp. @llvm.experimental.guard) call should contain the exception
554     // handling logic, if any.
555     if (auto *F = CI->getCalledFunction())
556       if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize ||
557           F->getIntrinsicID() == Intrinsic::experimental_guard)
558         continue;
559 
560     if (auto FuncletBundle = CI->getOperandBundle(LLVMContext::OB_funclet)) {
561       // This call is nested inside a funclet.  If that funclet has an unwind
562       // destination within the inlinee, then unwinding out of this call would
563       // be UB.  Rewriting this call to an invoke which targets the inlined
564       // invoke's unwind dest would give the call's parent funclet multiple
565       // unwind destinations, which is something that subsequent EH table
566       // generation can't handle and that the veirifer rejects.  So when we
567       // see such a call, leave it as a call.
568       auto *FuncletPad = cast<Instruction>(FuncletBundle->Inputs[0]);
569       Value *UnwindDestToken =
570           getUnwindDestToken(FuncletPad, *FuncletUnwindMap);
571       if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken))
572         continue;
573 #ifndef NDEBUG
574       Instruction *MemoKey;
575       if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
576         MemoKey = CatchPad->getCatchSwitch();
577       else
578         MemoKey = FuncletPad;
579       assert(FuncletUnwindMap->count(MemoKey) &&
580              (*FuncletUnwindMap)[MemoKey] == UnwindDestToken &&
581              "must get memoized to avoid confusing later searches");
582 #endif // NDEBUG
583     }
584 
585     changeToInvokeAndSplitBasicBlock(CI, UnwindEdge);
586     return BB;
587   }
588   return nullptr;
589 }
590 
591 /// If we inlined an invoke site, we need to convert calls
592 /// in the body of the inlined function into invokes.
593 ///
594 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
595 /// block of the inlined code (the last block is the end of the function),
596 /// and InlineCodeInfo is information about the code that got inlined.
597 static void HandleInlinedLandingPad(InvokeInst *II, BasicBlock *FirstNewBlock,
598                                     ClonedCodeInfo &InlinedCodeInfo) {
599   BasicBlock *InvokeDest = II->getUnwindDest();
600 
601   Function *Caller = FirstNewBlock->getParent();
602 
603   // The inlined code is currently at the end of the function, scan from the
604   // start of the inlined code to its end, checking for stuff we need to
605   // rewrite.
606   LandingPadInliningInfo Invoke(II);
607 
608   // Get all of the inlined landing pad instructions.
609   SmallPtrSet<LandingPadInst*, 16> InlinedLPads;
610   for (Function::iterator I = FirstNewBlock->getIterator(), E = Caller->end();
611        I != E; ++I)
612     if (InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator()))
613       InlinedLPads.insert(II->getLandingPadInst());
614 
615   // Append the clauses from the outer landing pad instruction into the inlined
616   // landing pad instructions.
617   LandingPadInst *OuterLPad = Invoke.getLandingPadInst();
618   for (LandingPadInst *InlinedLPad : InlinedLPads) {
619     unsigned OuterNum = OuterLPad->getNumClauses();
620     InlinedLPad->reserveClauses(OuterNum);
621     for (unsigned OuterIdx = 0; OuterIdx != OuterNum; ++OuterIdx)
622       InlinedLPad->addClause(OuterLPad->getClause(OuterIdx));
623     if (OuterLPad->isCleanup())
624       InlinedLPad->setCleanup(true);
625   }
626 
627   for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
628        BB != E; ++BB) {
629     if (InlinedCodeInfo.ContainsCalls)
630       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
631               &*BB, Invoke.getOuterResumeDest()))
632         // Update any PHI nodes in the exceptional block to indicate that there
633         // is now a new entry in them.
634         Invoke.addIncomingPHIValuesFor(NewBB);
635 
636     // Forward any resumes that are remaining here.
637     if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator()))
638       Invoke.forwardResume(RI, InlinedLPads);
639   }
640 
641   // Now that everything is happy, we have one final detail.  The PHI nodes in
642   // the exception destination block still have entries due to the original
643   // invoke instruction. Eliminate these entries (which might even delete the
644   // PHI node) now.
645   InvokeDest->removePredecessor(II->getParent());
646 }
647 
648 /// If we inlined an invoke site, we need to convert calls
649 /// in the body of the inlined function into invokes.
650 ///
651 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
652 /// block of the inlined code (the last block is the end of the function),
653 /// and InlineCodeInfo is information about the code that got inlined.
654 static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
655                                ClonedCodeInfo &InlinedCodeInfo) {
656   BasicBlock *UnwindDest = II->getUnwindDest();
657   Function *Caller = FirstNewBlock->getParent();
658 
659   assert(UnwindDest->getFirstNonPHI()->isEHPad() && "unexpected BasicBlock!");
660 
661   // If there are PHI nodes in the unwind destination block, we need to keep
662   // track of which values came into them from the invoke before removing the
663   // edge from this block.
664   SmallVector<Value *, 8> UnwindDestPHIValues;
665   BasicBlock *InvokeBB = II->getParent();
666   for (Instruction &I : *UnwindDest) {
667     // Save the value to use for this edge.
668     PHINode *PHI = dyn_cast<PHINode>(&I);
669     if (!PHI)
670       break;
671     UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB));
672   }
673 
674   // Add incoming-PHI values to the unwind destination block for the given basic
675   // block, using the values for the original invoke's source block.
676   auto UpdatePHINodes = [&](BasicBlock *Src) {
677     BasicBlock::iterator I = UnwindDest->begin();
678     for (Value *V : UnwindDestPHIValues) {
679       PHINode *PHI = cast<PHINode>(I);
680       PHI->addIncoming(V, Src);
681       ++I;
682     }
683   };
684 
685   // This connects all the instructions which 'unwind to caller' to the invoke
686   // destination.
687   UnwindDestMemoTy FuncletUnwindMap;
688   for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
689        BB != E; ++BB) {
690     if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) {
691       if (CRI->unwindsToCaller()) {
692         auto *CleanupPad = CRI->getCleanupPad();
693         CleanupReturnInst::Create(CleanupPad, UnwindDest, CRI);
694         CRI->eraseFromParent();
695         UpdatePHINodes(&*BB);
696         // Finding a cleanupret with an unwind destination would confuse
697         // subsequent calls to getUnwindDestToken, so map the cleanuppad
698         // to short-circuit any such calls and recognize this as an "unwind
699         // to caller" cleanup.
700         assert(!FuncletUnwindMap.count(CleanupPad) ||
701                isa<ConstantTokenNone>(FuncletUnwindMap[CleanupPad]));
702         FuncletUnwindMap[CleanupPad] =
703             ConstantTokenNone::get(Caller->getContext());
704       }
705     }
706 
707     Instruction *I = BB->getFirstNonPHI();
708     if (!I->isEHPad())
709       continue;
710 
711     Instruction *Replacement = nullptr;
712     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) {
713       if (CatchSwitch->unwindsToCaller()) {
714         Value *UnwindDestToken;
715         if (auto *ParentPad =
716                 dyn_cast<Instruction>(CatchSwitch->getParentPad())) {
717           // This catchswitch is nested inside another funclet.  If that
718           // funclet has an unwind destination within the inlinee, then
719           // unwinding out of this catchswitch would be UB.  Rewriting this
720           // catchswitch to unwind to the inlined invoke's unwind dest would
721           // give the parent funclet multiple unwind destinations, which is
722           // something that subsequent EH table generation can't handle and
723           // that the veirifer rejects.  So when we see such a call, leave it
724           // as "unwind to caller".
725           UnwindDestToken = getUnwindDestToken(ParentPad, FuncletUnwindMap);
726           if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken))
727             continue;
728         } else {
729           // This catchswitch has no parent to inherit constraints from, and
730           // none of its descendants can have an unwind edge that exits it and
731           // targets another funclet in the inlinee.  It may or may not have a
732           // descendant that definitively has an unwind to caller.  In either
733           // case, we'll have to assume that any unwinds out of it may need to
734           // be routed to the caller, so treat it as though it has a definitive
735           // unwind to caller.
736           UnwindDestToken = ConstantTokenNone::get(Caller->getContext());
737         }
738         auto *NewCatchSwitch = CatchSwitchInst::Create(
739             CatchSwitch->getParentPad(), UnwindDest,
740             CatchSwitch->getNumHandlers(), CatchSwitch->getName(),
741             CatchSwitch);
742         for (BasicBlock *PadBB : CatchSwitch->handlers())
743           NewCatchSwitch->addHandler(PadBB);
744         // Propagate info for the old catchswitch over to the new one in
745         // the unwind map.  This also serves to short-circuit any subsequent
746         // checks for the unwind dest of this catchswitch, which would get
747         // confused if they found the outer handler in the callee.
748         FuncletUnwindMap[NewCatchSwitch] = UnwindDestToken;
749         Replacement = NewCatchSwitch;
750       }
751     } else if (!isa<FuncletPadInst>(I)) {
752       llvm_unreachable("unexpected EHPad!");
753     }
754 
755     if (Replacement) {
756       Replacement->takeName(I);
757       I->replaceAllUsesWith(Replacement);
758       I->eraseFromParent();
759       UpdatePHINodes(&*BB);
760     }
761   }
762 
763   if (InlinedCodeInfo.ContainsCalls)
764     for (Function::iterator BB = FirstNewBlock->getIterator(),
765                             E = Caller->end();
766          BB != E; ++BB)
767       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
768               &*BB, UnwindDest, &FuncletUnwindMap))
769         // Update any PHI nodes in the exceptional block to indicate that there
770         // is now a new entry in them.
771         UpdatePHINodes(NewBB);
772 
773   // Now that everything is happy, we have one final detail.  The PHI nodes in
774   // the exception destination block still have entries due to the original
775   // invoke instruction. Eliminate these entries (which might even delete the
776   // PHI node) now.
777   UnwindDest->removePredecessor(InvokeBB);
778 }
779 
780 /// When inlining a call site that has !llvm.mem.parallel_loop_access,
781 /// !llvm.access.group, !alias.scope or !noalias metadata, that metadata should
782 /// be propagated to all memory-accessing cloned instructions.
783 static void PropagateCallSiteMetadata(CallBase &CB, ValueToValueMapTy &VMap) {
784   MDNode *MemParallelLoopAccess =
785       CB.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
786   MDNode *AccessGroup = CB.getMetadata(LLVMContext::MD_access_group);
787   MDNode *AliasScope = CB.getMetadata(LLVMContext::MD_alias_scope);
788   MDNode *NoAlias = CB.getMetadata(LLVMContext::MD_noalias);
789   if (!MemParallelLoopAccess && !AccessGroup && !AliasScope && !NoAlias)
790     return;
791 
792   for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
793        VMI != VMIE; ++VMI) {
794     // Check that key is an instruction, to skip the Argument mapping, which
795     // points to an instruction in the original function, not the inlined one.
796     if (!VMI->second || !isa<Instruction>(VMI->first))
797       continue;
798 
799     Instruction *NI = dyn_cast<Instruction>(VMI->second);
800     if (!NI)
801       continue;
802 
803     // This metadata is only relevant for instructions that access memory.
804     if (!NI->mayReadOrWriteMemory())
805       continue;
806 
807     if (MemParallelLoopAccess) {
808       // TODO: This probably should not overwrite MemParalleLoopAccess.
809       MemParallelLoopAccess = MDNode::concatenate(
810           NI->getMetadata(LLVMContext::MD_mem_parallel_loop_access),
811           MemParallelLoopAccess);
812       NI->setMetadata(LLVMContext::MD_mem_parallel_loop_access,
813                       MemParallelLoopAccess);
814     }
815 
816     if (AccessGroup)
817       NI->setMetadata(LLVMContext::MD_access_group, uniteAccessGroups(
818           NI->getMetadata(LLVMContext::MD_access_group), AccessGroup));
819 
820     if (AliasScope)
821       NI->setMetadata(LLVMContext::MD_alias_scope, MDNode::concatenate(
822           NI->getMetadata(LLVMContext::MD_alias_scope), AliasScope));
823 
824     if (NoAlias)
825       NI->setMetadata(LLVMContext::MD_noalias, MDNode::concatenate(
826           NI->getMetadata(LLVMContext::MD_noalias), NoAlias));
827   }
828 }
829 
830 /// Utility for cloning !noalias and !alias.scope metadata. When a code region
831 /// using scoped alias metadata is inlined, the aliasing relationships may not
832 /// hold between the two version. It is necessary to create a deep clone of the
833 /// metadata, putting the two versions in separate scope domains.
834 class ScopedAliasMetadataDeepCloner {
835   using MetadataMap = DenseMap<const MDNode *, TrackingMDNodeRef>;
836   SetVector<const MDNode *> MD;
837   MetadataMap MDMap;
838   void addRecursiveMetadataUses();
839 
840 public:
841   ScopedAliasMetadataDeepCloner(const Function *F);
842 
843   /// Create a new clone of the scoped alias metadata, which will be used by
844   /// subsequent remap() calls.
845   void clone();
846 
847   /// Remap instructions in the given VMap from the original to the cloned
848   /// metadata.
849   void remap(ValueToValueMapTy &VMap);
850 };
851 
852 ScopedAliasMetadataDeepCloner::ScopedAliasMetadataDeepCloner(
853     const Function *F) {
854   for (const BasicBlock &BB : *F) {
855     for (const Instruction &I : BB) {
856       if (const MDNode *M = I.getMetadata(LLVMContext::MD_alias_scope))
857         MD.insert(M);
858       if (const MDNode *M = I.getMetadata(LLVMContext::MD_noalias))
859         MD.insert(M);
860 
861       // We also need to clone the metadata in noalias intrinsics.
862       if (const auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
863         MD.insert(Decl->getScopeList());
864     }
865   }
866   addRecursiveMetadataUses();
867 }
868 
869 void ScopedAliasMetadataDeepCloner::addRecursiveMetadataUses() {
870   SmallVector<const Metadata *, 16> Queue(MD.begin(), MD.end());
871   while (!Queue.empty()) {
872     const MDNode *M = cast<MDNode>(Queue.pop_back_val());
873     for (const Metadata *Op : M->operands())
874       if (const MDNode *OpMD = dyn_cast<MDNode>(Op))
875         if (MD.insert(OpMD))
876           Queue.push_back(OpMD);
877   }
878 }
879 
880 void ScopedAliasMetadataDeepCloner::clone() {
881   assert(MDMap.empty() && "clone() already called ?");
882 
883   SmallVector<TempMDTuple, 16> DummyNodes;
884   for (const MDNode *I : MD) {
885     DummyNodes.push_back(MDTuple::getTemporary(I->getContext(), None));
886     MDMap[I].reset(DummyNodes.back().get());
887   }
888 
889   // Create new metadata nodes to replace the dummy nodes, replacing old
890   // metadata references with either a dummy node or an already-created new
891   // node.
892   SmallVector<Metadata *, 4> NewOps;
893   for (const MDNode *I : MD) {
894     for (const Metadata *Op : I->operands()) {
895       if (const MDNode *M = dyn_cast<MDNode>(Op))
896         NewOps.push_back(MDMap[M]);
897       else
898         NewOps.push_back(const_cast<Metadata *>(Op));
899     }
900 
901     MDNode *NewM = MDNode::get(I->getContext(), NewOps);
902     MDTuple *TempM = cast<MDTuple>(MDMap[I]);
903     assert(TempM->isTemporary() && "Expected temporary node");
904 
905     TempM->replaceAllUsesWith(NewM);
906     NewOps.clear();
907   }
908 }
909 
910 void ScopedAliasMetadataDeepCloner::remap(ValueToValueMapTy &VMap) {
911   if (MDMap.empty())
912     return; // Nothing to do.
913 
914   for (auto Entry : VMap) {
915     // Check that key is an instruction, to skip the Argument mapping, which
916     // points to an instruction in the original function, not the inlined one.
917     if (!Entry->second || !isa<Instruction>(Entry->first))
918       continue;
919 
920     Instruction *I = dyn_cast<Instruction>(Entry->second);
921     if (!I)
922       continue;
923 
924     if (MDNode *M = I->getMetadata(LLVMContext::MD_alias_scope))
925       I->setMetadata(LLVMContext::MD_alias_scope, MDMap[M]);
926 
927     if (MDNode *M = I->getMetadata(LLVMContext::MD_noalias))
928       I->setMetadata(LLVMContext::MD_noalias, MDMap[M]);
929 
930     if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(I))
931       Decl->setScopeList(MDMap[Decl->getScopeList()]);
932   }
933 }
934 
935 /// If the inlined function has noalias arguments,
936 /// then add new alias scopes for each noalias argument, tag the mapped noalias
937 /// parameters with noalias metadata specifying the new scope, and tag all
938 /// non-derived loads, stores and memory intrinsics with the new alias scopes.
939 static void AddAliasScopeMetadata(CallBase &CB, ValueToValueMapTy &VMap,
940                                   const DataLayout &DL, AAResults *CalleeAAR) {
941   if (!EnableNoAliasConversion)
942     return;
943 
944   const Function *CalledFunc = CB.getCalledFunction();
945   SmallVector<const Argument *, 4> NoAliasArgs;
946 
947   for (const Argument &Arg : CalledFunc->args())
948     if (CB.paramHasAttr(Arg.getArgNo(), Attribute::NoAlias) && !Arg.use_empty())
949       NoAliasArgs.push_back(&Arg);
950 
951   if (NoAliasArgs.empty())
952     return;
953 
954   // To do a good job, if a noalias variable is captured, we need to know if
955   // the capture point dominates the particular use we're considering.
956   DominatorTree DT;
957   DT.recalculate(const_cast<Function&>(*CalledFunc));
958 
959   // noalias indicates that pointer values based on the argument do not alias
960   // pointer values which are not based on it. So we add a new "scope" for each
961   // noalias function argument. Accesses using pointers based on that argument
962   // become part of that alias scope, accesses using pointers not based on that
963   // argument are tagged as noalias with that scope.
964 
965   DenseMap<const Argument *, MDNode *> NewScopes;
966   MDBuilder MDB(CalledFunc->getContext());
967 
968   // Create a new scope domain for this function.
969   MDNode *NewDomain =
970     MDB.createAnonymousAliasScopeDomain(CalledFunc->getName());
971   for (unsigned i = 0, e = NoAliasArgs.size(); i != e; ++i) {
972     const Argument *A = NoAliasArgs[i];
973 
974     std::string Name = std::string(CalledFunc->getName());
975     if (A->hasName()) {
976       Name += ": %";
977       Name += A->getName();
978     } else {
979       Name += ": argument ";
980       Name += utostr(i);
981     }
982 
983     // Note: We always create a new anonymous root here. This is true regardless
984     // of the linkage of the callee because the aliasing "scope" is not just a
985     // property of the callee, but also all control dependencies in the caller.
986     MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
987     NewScopes.insert(std::make_pair(A, NewScope));
988 
989     if (UseNoAliasIntrinsic) {
990       // Introduce a llvm.experimental.noalias.scope.decl for the noalias
991       // argument.
992       MDNode *AScopeList = MDNode::get(CalledFunc->getContext(), NewScope);
993       auto *NoAliasDecl =
994           IRBuilder<>(&CB).CreateNoAliasScopeDeclaration(AScopeList);
995       // Ignore the result for now. The result will be used when the
996       // llvm.noalias intrinsic is introduced.
997       (void)NoAliasDecl;
998     }
999   }
1000 
1001   // Iterate over all new instructions in the map; for all memory-access
1002   // instructions, add the alias scope metadata.
1003   for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
1004        VMI != VMIE; ++VMI) {
1005     if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) {
1006       if (!VMI->second)
1007         continue;
1008 
1009       Instruction *NI = dyn_cast<Instruction>(VMI->second);
1010       if (!NI)
1011         continue;
1012 
1013       bool IsArgMemOnlyCall = false, IsFuncCall = false;
1014       SmallVector<const Value *, 2> PtrArgs;
1015 
1016       if (const LoadInst *LI = dyn_cast<LoadInst>(I))
1017         PtrArgs.push_back(LI->getPointerOperand());
1018       else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
1019         PtrArgs.push_back(SI->getPointerOperand());
1020       else if (const VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
1021         PtrArgs.push_back(VAAI->getPointerOperand());
1022       else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I))
1023         PtrArgs.push_back(CXI->getPointerOperand());
1024       else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I))
1025         PtrArgs.push_back(RMWI->getPointerOperand());
1026       else if (const auto *Call = dyn_cast<CallBase>(I)) {
1027         // If we know that the call does not access memory, then we'll still
1028         // know that about the inlined clone of this call site, and we don't
1029         // need to add metadata.
1030         if (Call->doesNotAccessMemory())
1031           continue;
1032 
1033         IsFuncCall = true;
1034         if (CalleeAAR) {
1035           FunctionModRefBehavior MRB = CalleeAAR->getModRefBehavior(Call);
1036           if (AAResults::onlyAccessesArgPointees(MRB))
1037             IsArgMemOnlyCall = true;
1038         }
1039 
1040         for (Value *Arg : Call->args()) {
1041           // We need to check the underlying objects of all arguments, not just
1042           // the pointer arguments, because we might be passing pointers as
1043           // integers, etc.
1044           // However, if we know that the call only accesses pointer arguments,
1045           // then we only need to check the pointer arguments.
1046           if (IsArgMemOnlyCall && !Arg->getType()->isPointerTy())
1047             continue;
1048 
1049           PtrArgs.push_back(Arg);
1050         }
1051       }
1052 
1053       // If we found no pointers, then this instruction is not suitable for
1054       // pairing with an instruction to receive aliasing metadata.
1055       // However, if this is a call, this we might just alias with none of the
1056       // noalias arguments.
1057       if (PtrArgs.empty() && !IsFuncCall)
1058         continue;
1059 
1060       // It is possible that there is only one underlying object, but you
1061       // need to go through several PHIs to see it, and thus could be
1062       // repeated in the Objects list.
1063       SmallPtrSet<const Value *, 4> ObjSet;
1064       SmallVector<Metadata *, 4> Scopes, NoAliases;
1065 
1066       SmallSetVector<const Argument *, 4> NAPtrArgs;
1067       for (const Value *V : PtrArgs) {
1068         SmallVector<const Value *, 4> Objects;
1069         getUnderlyingObjects(V, Objects, /* LI = */ nullptr);
1070 
1071         for (const Value *O : Objects)
1072           ObjSet.insert(O);
1073       }
1074 
1075       // Figure out if we're derived from anything that is not a noalias
1076       // argument.
1077       bool CanDeriveViaCapture = false, UsesAliasingPtr = false;
1078       for (const Value *V : ObjSet) {
1079         // Is this value a constant that cannot be derived from any pointer
1080         // value (we need to exclude constant expressions, for example, that
1081         // are formed from arithmetic on global symbols).
1082         bool IsNonPtrConst = isa<ConstantInt>(V) || isa<ConstantFP>(V) ||
1083                              isa<ConstantPointerNull>(V) ||
1084                              isa<ConstantDataVector>(V) || isa<UndefValue>(V);
1085         if (IsNonPtrConst)
1086           continue;
1087 
1088         // If this is anything other than a noalias argument, then we cannot
1089         // completely describe the aliasing properties using alias.scope
1090         // metadata (and, thus, won't add any).
1091         if (const Argument *A = dyn_cast<Argument>(V)) {
1092           if (!CB.paramHasAttr(A->getArgNo(), Attribute::NoAlias))
1093             UsesAliasingPtr = true;
1094         } else {
1095           UsesAliasingPtr = true;
1096         }
1097 
1098         // If this is not some identified function-local object (which cannot
1099         // directly alias a noalias argument), or some other argument (which,
1100         // by definition, also cannot alias a noalias argument), then we could
1101         // alias a noalias argument that has been captured).
1102         if (!isa<Argument>(V) &&
1103             !isIdentifiedFunctionLocal(const_cast<Value*>(V)))
1104           CanDeriveViaCapture = true;
1105       }
1106 
1107       // A function call can always get captured noalias pointers (via other
1108       // parameters, globals, etc.).
1109       if (IsFuncCall && !IsArgMemOnlyCall)
1110         CanDeriveViaCapture = true;
1111 
1112       // First, we want to figure out all of the sets with which we definitely
1113       // don't alias. Iterate over all noalias set, and add those for which:
1114       //   1. The noalias argument is not in the set of objects from which we
1115       //      definitely derive.
1116       //   2. The noalias argument has not yet been captured.
1117       // An arbitrary function that might load pointers could see captured
1118       // noalias arguments via other noalias arguments or globals, and so we
1119       // must always check for prior capture.
1120       for (const Argument *A : NoAliasArgs) {
1121         if (!ObjSet.count(A) && (!CanDeriveViaCapture ||
1122                                  // It might be tempting to skip the
1123                                  // PointerMayBeCapturedBefore check if
1124                                  // A->hasNoCaptureAttr() is true, but this is
1125                                  // incorrect because nocapture only guarantees
1126                                  // that no copies outlive the function, not
1127                                  // that the value cannot be locally captured.
1128                                  !PointerMayBeCapturedBefore(A,
1129                                    /* ReturnCaptures */ false,
1130                                    /* StoreCaptures */ false, I, &DT)))
1131           NoAliases.push_back(NewScopes[A]);
1132       }
1133 
1134       if (!NoAliases.empty())
1135         NI->setMetadata(LLVMContext::MD_noalias,
1136                         MDNode::concatenate(
1137                             NI->getMetadata(LLVMContext::MD_noalias),
1138                             MDNode::get(CalledFunc->getContext(), NoAliases)));
1139 
1140       // Next, we want to figure out all of the sets to which we might belong.
1141       // We might belong to a set if the noalias argument is in the set of
1142       // underlying objects. If there is some non-noalias argument in our list
1143       // of underlying objects, then we cannot add a scope because the fact
1144       // that some access does not alias with any set of our noalias arguments
1145       // cannot itself guarantee that it does not alias with this access
1146       // (because there is some pointer of unknown origin involved and the
1147       // other access might also depend on this pointer). We also cannot add
1148       // scopes to arbitrary functions unless we know they don't access any
1149       // non-parameter pointer-values.
1150       bool CanAddScopes = !UsesAliasingPtr;
1151       if (CanAddScopes && IsFuncCall)
1152         CanAddScopes = IsArgMemOnlyCall;
1153 
1154       if (CanAddScopes)
1155         for (const Argument *A : NoAliasArgs) {
1156           if (ObjSet.count(A))
1157             Scopes.push_back(NewScopes[A]);
1158         }
1159 
1160       if (!Scopes.empty())
1161         NI->setMetadata(
1162             LLVMContext::MD_alias_scope,
1163             MDNode::concatenate(NI->getMetadata(LLVMContext::MD_alias_scope),
1164                                 MDNode::get(CalledFunc->getContext(), Scopes)));
1165     }
1166   }
1167 }
1168 
1169 static bool MayContainThrowingOrExitingCall(Instruction *Begin,
1170                                             Instruction *End) {
1171 
1172   assert(Begin->getParent() == End->getParent() &&
1173          "Expected to be in same basic block!");
1174   unsigned NumInstChecked = 0;
1175   // Check that all instructions in the range [Begin, End) are guaranteed to
1176   // transfer execution to successor.
1177   for (auto &I : make_range(Begin->getIterator(), End->getIterator()))
1178     if (NumInstChecked++ > InlinerAttributeWindow ||
1179         !isGuaranteedToTransferExecutionToSuccessor(&I))
1180       return true;
1181   return false;
1182 }
1183 
1184 static AttrBuilder IdentifyValidAttributes(CallBase &CB) {
1185 
1186   AttrBuilder AB(CB.getAttributes(), AttributeList::ReturnIndex);
1187   if (AB.empty())
1188     return AB;
1189   AttrBuilder Valid;
1190   // Only allow these white listed attributes to be propagated back to the
1191   // callee. This is because other attributes may only be valid on the call
1192   // itself, i.e. attributes such as signext and zeroext.
1193   if (auto DerefBytes = AB.getDereferenceableBytes())
1194     Valid.addDereferenceableAttr(DerefBytes);
1195   if (auto DerefOrNullBytes = AB.getDereferenceableOrNullBytes())
1196     Valid.addDereferenceableOrNullAttr(DerefOrNullBytes);
1197   if (AB.contains(Attribute::NoAlias))
1198     Valid.addAttribute(Attribute::NoAlias);
1199   if (AB.contains(Attribute::NonNull))
1200     Valid.addAttribute(Attribute::NonNull);
1201   return Valid;
1202 }
1203 
1204 static void AddReturnAttributes(CallBase &CB, ValueToValueMapTy &VMap) {
1205   if (!UpdateReturnAttributes)
1206     return;
1207 
1208   AttrBuilder Valid = IdentifyValidAttributes(CB);
1209   if (Valid.empty())
1210     return;
1211   auto *CalledFunction = CB.getCalledFunction();
1212   auto &Context = CalledFunction->getContext();
1213 
1214   for (auto &BB : *CalledFunction) {
1215     auto *RI = dyn_cast<ReturnInst>(BB.getTerminator());
1216     if (!RI || !isa<CallBase>(RI->getOperand(0)))
1217       continue;
1218     auto *RetVal = cast<CallBase>(RI->getOperand(0));
1219     // Sanity check that the cloned RetVal exists and is a call, otherwise we
1220     // cannot add the attributes on the cloned RetVal.
1221     // Simplification during inlining could have transformed the cloned
1222     // instruction.
1223     auto *NewRetVal = dyn_cast_or_null<CallBase>(VMap.lookup(RetVal));
1224     if (!NewRetVal)
1225       continue;
1226     // Backward propagation of attributes to the returned value may be incorrect
1227     // if it is control flow dependent.
1228     // Consider:
1229     // @callee {
1230     //  %rv = call @foo()
1231     //  %rv2 = call @bar()
1232     //  if (%rv2 != null)
1233     //    return %rv2
1234     //  if (%rv == null)
1235     //    exit()
1236     //  return %rv
1237     // }
1238     // caller() {
1239     //   %val = call nonnull @callee()
1240     // }
1241     // Here we cannot add the nonnull attribute on either foo or bar. So, we
1242     // limit the check to both RetVal and RI are in the same basic block and
1243     // there are no throwing/exiting instructions between these instructions.
1244     if (RI->getParent() != RetVal->getParent() ||
1245         MayContainThrowingOrExitingCall(RetVal, RI))
1246       continue;
1247     // Add to the existing attributes of NewRetVal, i.e. the cloned call
1248     // instruction.
1249     // NB! When we have the same attribute already existing on NewRetVal, but
1250     // with a differing value, the AttributeList's merge API honours the already
1251     // existing attribute value (i.e. attributes such as dereferenceable,
1252     // dereferenceable_or_null etc). See AttrBuilder::merge for more details.
1253     AttributeList AL = NewRetVal->getAttributes();
1254     AttributeList NewAL =
1255         AL.addAttributes(Context, AttributeList::ReturnIndex, Valid);
1256     NewRetVal->setAttributes(NewAL);
1257   }
1258 }
1259 
1260 /// If the inlined function has non-byval align arguments, then
1261 /// add @llvm.assume-based alignment assumptions to preserve this information.
1262 static void AddAlignmentAssumptions(CallBase &CB, InlineFunctionInfo &IFI) {
1263   if (!PreserveAlignmentAssumptions || !IFI.GetAssumptionCache)
1264     return;
1265 
1266   AssumptionCache *AC = &IFI.GetAssumptionCache(*CB.getCaller());
1267   auto &DL = CB.getCaller()->getParent()->getDataLayout();
1268 
1269   // To avoid inserting redundant assumptions, we should check for assumptions
1270   // already in the caller. To do this, we might need a DT of the caller.
1271   DominatorTree DT;
1272   bool DTCalculated = false;
1273 
1274   Function *CalledFunc = CB.getCalledFunction();
1275   for (Argument &Arg : CalledFunc->args()) {
1276     unsigned Align = Arg.getType()->isPointerTy() ? Arg.getParamAlignment() : 0;
1277     if (Align && !Arg.hasPassPointeeByValueCopyAttr() && !Arg.hasNUses(0)) {
1278       if (!DTCalculated) {
1279         DT.recalculate(*CB.getCaller());
1280         DTCalculated = true;
1281       }
1282 
1283       // If we can already prove the asserted alignment in the context of the
1284       // caller, then don't bother inserting the assumption.
1285       Value *ArgVal = CB.getArgOperand(Arg.getArgNo());
1286       if (getKnownAlignment(ArgVal, DL, &CB, AC, &DT) >= Align)
1287         continue;
1288 
1289       CallInst *NewAsmp =
1290           IRBuilder<>(&CB).CreateAlignmentAssumption(DL, ArgVal, Align);
1291       AC->registerAssumption(NewAsmp);
1292     }
1293   }
1294 }
1295 
1296 /// Once we have cloned code over from a callee into the caller,
1297 /// update the specified callgraph to reflect the changes we made.
1298 /// Note that it's possible that not all code was copied over, so only
1299 /// some edges of the callgraph may remain.
1300 static void UpdateCallGraphAfterInlining(CallBase &CB,
1301                                          Function::iterator FirstNewBlock,
1302                                          ValueToValueMapTy &VMap,
1303                                          InlineFunctionInfo &IFI) {
1304   CallGraph &CG = *IFI.CG;
1305   const Function *Caller = CB.getCaller();
1306   const Function *Callee = CB.getCalledFunction();
1307   CallGraphNode *CalleeNode = CG[Callee];
1308   CallGraphNode *CallerNode = CG[Caller];
1309 
1310   // Since we inlined some uninlined call sites in the callee into the caller,
1311   // add edges from the caller to all of the callees of the callee.
1312   CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end();
1313 
1314   // Consider the case where CalleeNode == CallerNode.
1315   CallGraphNode::CalledFunctionsVector CallCache;
1316   if (CalleeNode == CallerNode) {
1317     CallCache.assign(I, E);
1318     I = CallCache.begin();
1319     E = CallCache.end();
1320   }
1321 
1322   for (; I != E; ++I) {
1323     // Skip 'refererence' call records.
1324     if (!I->first)
1325       continue;
1326 
1327     const Value *OrigCall = *I->first;
1328 
1329     ValueToValueMapTy::iterator VMI = VMap.find(OrigCall);
1330     // Only copy the edge if the call was inlined!
1331     if (VMI == VMap.end() || VMI->second == nullptr)
1332       continue;
1333 
1334     // If the call was inlined, but then constant folded, there is no edge to
1335     // add.  Check for this case.
1336     auto *NewCall = dyn_cast<CallBase>(VMI->second);
1337     if (!NewCall)
1338       continue;
1339 
1340     // We do not treat intrinsic calls like real function calls because we
1341     // expect them to become inline code; do not add an edge for an intrinsic.
1342     if (NewCall->getCalledFunction() &&
1343         NewCall->getCalledFunction()->isIntrinsic())
1344       continue;
1345 
1346     // Remember that this call site got inlined for the client of
1347     // InlineFunction.
1348     IFI.InlinedCalls.push_back(NewCall);
1349 
1350     // It's possible that inlining the callsite will cause it to go from an
1351     // indirect to a direct call by resolving a function pointer.  If this
1352     // happens, set the callee of the new call site to a more precise
1353     // destination.  This can also happen if the call graph node of the caller
1354     // was just unnecessarily imprecise.
1355     if (!I->second->getFunction())
1356       if (Function *F = NewCall->getCalledFunction()) {
1357         // Indirect call site resolved to direct call.
1358         CallerNode->addCalledFunction(NewCall, CG[F]);
1359 
1360         continue;
1361       }
1362 
1363     CallerNode->addCalledFunction(NewCall, I->second);
1364   }
1365 
1366   // Update the call graph by deleting the edge from Callee to Caller.  We must
1367   // do this after the loop above in case Caller and Callee are the same.
1368   CallerNode->removeCallEdgeFor(*cast<CallBase>(&CB));
1369 }
1370 
1371 static void HandleByValArgumentInit(Value *Dst, Value *Src, Module *M,
1372                                     BasicBlock *InsertBlock,
1373                                     InlineFunctionInfo &IFI) {
1374   Type *AggTy = cast<PointerType>(Src->getType())->getElementType();
1375   IRBuilder<> Builder(InsertBlock, InsertBlock->begin());
1376 
1377   Value *Size = Builder.getInt64(M->getDataLayout().getTypeStoreSize(AggTy));
1378 
1379   // Always generate a memcpy of alignment 1 here because we don't know
1380   // the alignment of the src pointer.  Other optimizations can infer
1381   // better alignment.
1382   Builder.CreateMemCpy(Dst, /*DstAlign*/ Align(1), Src,
1383                        /*SrcAlign*/ Align(1), Size);
1384 }
1385 
1386 /// When inlining a call site that has a byval argument,
1387 /// we have to make the implicit memcpy explicit by adding it.
1388 static Value *HandleByValArgument(Value *Arg, Instruction *TheCall,
1389                                   const Function *CalledFunc,
1390                                   InlineFunctionInfo &IFI,
1391                                   unsigned ByValAlignment) {
1392   PointerType *ArgTy = cast<PointerType>(Arg->getType());
1393   Type *AggTy = ArgTy->getElementType();
1394 
1395   Function *Caller = TheCall->getFunction();
1396   const DataLayout &DL = Caller->getParent()->getDataLayout();
1397 
1398   // If the called function is readonly, then it could not mutate the caller's
1399   // copy of the byval'd memory.  In this case, it is safe to elide the copy and
1400   // temporary.
1401   if (CalledFunc->onlyReadsMemory()) {
1402     // If the byval argument has a specified alignment that is greater than the
1403     // passed in pointer, then we either have to round up the input pointer or
1404     // give up on this transformation.
1405     if (ByValAlignment <= 1)  // 0 = unspecified, 1 = no particular alignment.
1406       return Arg;
1407 
1408     AssumptionCache *AC =
1409         IFI.GetAssumptionCache ? &IFI.GetAssumptionCache(*Caller) : nullptr;
1410 
1411     // If the pointer is already known to be sufficiently aligned, or if we can
1412     // round it up to a larger alignment, then we don't need a temporary.
1413     if (getOrEnforceKnownAlignment(Arg, Align(ByValAlignment), DL, TheCall,
1414                                    AC) >= ByValAlignment)
1415       return Arg;
1416 
1417     // Otherwise, we have to make a memcpy to get a safe alignment.  This is bad
1418     // for code quality, but rarely happens and is required for correctness.
1419   }
1420 
1421   // Create the alloca.  If we have DataLayout, use nice alignment.
1422   Align Alignment(DL.getPrefTypeAlignment(AggTy));
1423 
1424   // If the byval had an alignment specified, we *must* use at least that
1425   // alignment, as it is required by the byval argument (and uses of the
1426   // pointer inside the callee).
1427   Alignment = max(Alignment, MaybeAlign(ByValAlignment));
1428 
1429   Value *NewAlloca =
1430       new AllocaInst(AggTy, DL.getAllocaAddrSpace(), nullptr, Alignment,
1431                      Arg->getName(), &*Caller->begin()->begin());
1432   IFI.StaticAllocas.push_back(cast<AllocaInst>(NewAlloca));
1433 
1434   // Uses of the argument in the function should use our new alloca
1435   // instead.
1436   return NewAlloca;
1437 }
1438 
1439 // Check whether this Value is used by a lifetime intrinsic.
1440 static bool isUsedByLifetimeMarker(Value *V) {
1441   for (User *U : V->users())
1442     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U))
1443       if (II->isLifetimeStartOrEnd())
1444         return true;
1445   return false;
1446 }
1447 
1448 // Check whether the given alloca already has
1449 // lifetime.start or lifetime.end intrinsics.
1450 static bool hasLifetimeMarkers(AllocaInst *AI) {
1451   Type *Ty = AI->getType();
1452   Type *Int8PtrTy = Type::getInt8PtrTy(Ty->getContext(),
1453                                        Ty->getPointerAddressSpace());
1454   if (Ty == Int8PtrTy)
1455     return isUsedByLifetimeMarker(AI);
1456 
1457   // Do a scan to find all the casts to i8*.
1458   for (User *U : AI->users()) {
1459     if (U->getType() != Int8PtrTy) continue;
1460     if (U->stripPointerCasts() != AI) continue;
1461     if (isUsedByLifetimeMarker(U))
1462       return true;
1463   }
1464   return false;
1465 }
1466 
1467 /// Return the result of AI->isStaticAlloca() if AI were moved to the entry
1468 /// block. Allocas used in inalloca calls and allocas of dynamic array size
1469 /// cannot be static.
1470 static bool allocaWouldBeStaticInEntry(const AllocaInst *AI ) {
1471   return isa<Constant>(AI->getArraySize()) && !AI->isUsedWithInAlloca();
1472 }
1473 
1474 /// Returns a DebugLoc for a new DILocation which is a clone of \p OrigDL
1475 /// inlined at \p InlinedAt. \p IANodes is an inlined-at cache.
1476 static DebugLoc inlineDebugLoc(DebugLoc OrigDL, DILocation *InlinedAt,
1477                                LLVMContext &Ctx,
1478                                DenseMap<const MDNode *, MDNode *> &IANodes) {
1479   auto IA = DebugLoc::appendInlinedAt(OrigDL, InlinedAt, Ctx, IANodes);
1480   return DILocation::get(Ctx, OrigDL.getLine(), OrigDL.getCol(),
1481                          OrigDL.getScope(), IA);
1482 }
1483 
1484 /// Update inlined instructions' line numbers to
1485 /// to encode location where these instructions are inlined.
1486 static void fixupLineNumbers(Function *Fn, Function::iterator FI,
1487                              Instruction *TheCall, bool CalleeHasDebugInfo) {
1488   const DebugLoc &TheCallDL = TheCall->getDebugLoc();
1489   if (!TheCallDL)
1490     return;
1491 
1492   auto &Ctx = Fn->getContext();
1493   DILocation *InlinedAtNode = TheCallDL;
1494 
1495   // Create a unique call site, not to be confused with any other call from the
1496   // same location.
1497   InlinedAtNode = DILocation::getDistinct(
1498       Ctx, InlinedAtNode->getLine(), InlinedAtNode->getColumn(),
1499       InlinedAtNode->getScope(), InlinedAtNode->getInlinedAt());
1500 
1501   // Cache the inlined-at nodes as they're built so they are reused, without
1502   // this every instruction's inlined-at chain would become distinct from each
1503   // other.
1504   DenseMap<const MDNode *, MDNode *> IANodes;
1505 
1506   // Check if we are not generating inline line tables and want to use
1507   // the call site location instead.
1508   bool NoInlineLineTables = Fn->hasFnAttribute("no-inline-line-tables");
1509 
1510   for (; FI != Fn->end(); ++FI) {
1511     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
1512          BI != BE; ++BI) {
1513       // Loop metadata needs to be updated so that the start and end locs
1514       // reference inlined-at locations.
1515       auto updateLoopInfoLoc = [&Ctx, &InlinedAtNode, &IANodes](
1516                                    const DILocation &Loc) -> DILocation * {
1517         return inlineDebugLoc(&Loc, InlinedAtNode, Ctx, IANodes).get();
1518       };
1519       updateLoopMetadataDebugLocations(*BI, updateLoopInfoLoc);
1520 
1521       if (!NoInlineLineTables)
1522         if (DebugLoc DL = BI->getDebugLoc()) {
1523           DebugLoc IDL =
1524               inlineDebugLoc(DL, InlinedAtNode, BI->getContext(), IANodes);
1525           BI->setDebugLoc(IDL);
1526           continue;
1527         }
1528 
1529       if (CalleeHasDebugInfo && !NoInlineLineTables)
1530         continue;
1531 
1532       // If the inlined instruction has no line number, or if inline info
1533       // is not being generated, make it look as if it originates from the call
1534       // location. This is important for ((__always_inline, __nodebug__))
1535       // functions which must use caller location for all instructions in their
1536       // function body.
1537 
1538       // Don't update static allocas, as they may get moved later.
1539       if (auto *AI = dyn_cast<AllocaInst>(BI))
1540         if (allocaWouldBeStaticInEntry(AI))
1541           continue;
1542 
1543       BI->setDebugLoc(TheCallDL);
1544     }
1545 
1546     // Remove debug info intrinsics if we're not keeping inline info.
1547     if (NoInlineLineTables) {
1548       BasicBlock::iterator BI = FI->begin();
1549       while (BI != FI->end()) {
1550         if (isa<DbgInfoIntrinsic>(BI)) {
1551           BI = BI->eraseFromParent();
1552           continue;
1553         }
1554         ++BI;
1555       }
1556     }
1557 
1558   }
1559 }
1560 
1561 /// Update the block frequencies of the caller after a callee has been inlined.
1562 ///
1563 /// Each block cloned into the caller has its block frequency scaled by the
1564 /// ratio of CallSiteFreq/CalleeEntryFreq. This ensures that the cloned copy of
1565 /// callee's entry block gets the same frequency as the callsite block and the
1566 /// relative frequencies of all cloned blocks remain the same after cloning.
1567 static void updateCallerBFI(BasicBlock *CallSiteBlock,
1568                             const ValueToValueMapTy &VMap,
1569                             BlockFrequencyInfo *CallerBFI,
1570                             BlockFrequencyInfo *CalleeBFI,
1571                             const BasicBlock &CalleeEntryBlock) {
1572   SmallPtrSet<BasicBlock *, 16> ClonedBBs;
1573   for (auto Entry : VMap) {
1574     if (!isa<BasicBlock>(Entry.first) || !Entry.second)
1575       continue;
1576     auto *OrigBB = cast<BasicBlock>(Entry.first);
1577     auto *ClonedBB = cast<BasicBlock>(Entry.second);
1578     uint64_t Freq = CalleeBFI->getBlockFreq(OrigBB).getFrequency();
1579     if (!ClonedBBs.insert(ClonedBB).second) {
1580       // Multiple blocks in the callee might get mapped to one cloned block in
1581       // the caller since we prune the callee as we clone it. When that happens,
1582       // we want to use the maximum among the original blocks' frequencies.
1583       uint64_t NewFreq = CallerBFI->getBlockFreq(ClonedBB).getFrequency();
1584       if (NewFreq > Freq)
1585         Freq = NewFreq;
1586     }
1587     CallerBFI->setBlockFreq(ClonedBB, Freq);
1588   }
1589   BasicBlock *EntryClone = cast<BasicBlock>(VMap.lookup(&CalleeEntryBlock));
1590   CallerBFI->setBlockFreqAndScale(
1591       EntryClone, CallerBFI->getBlockFreq(CallSiteBlock).getFrequency(),
1592       ClonedBBs);
1593 }
1594 
1595 /// Update the branch metadata for cloned call instructions.
1596 static void updateCallProfile(Function *Callee, const ValueToValueMapTy &VMap,
1597                               const ProfileCount &CalleeEntryCount,
1598                               const CallBase &TheCall, ProfileSummaryInfo *PSI,
1599                               BlockFrequencyInfo *CallerBFI) {
1600   if (!CalleeEntryCount.hasValue() || CalleeEntryCount.isSynthetic() ||
1601       CalleeEntryCount.getCount() < 1)
1602     return;
1603   auto CallSiteCount = PSI ? PSI->getProfileCount(TheCall, CallerBFI) : None;
1604   int64_t CallCount =
1605       std::min(CallSiteCount.getValueOr(0), CalleeEntryCount.getCount());
1606   updateProfileCallee(Callee, -CallCount, &VMap);
1607 }
1608 
1609 void llvm::updateProfileCallee(
1610     Function *Callee, int64_t entryDelta,
1611     const ValueMap<const Value *, WeakTrackingVH> *VMap) {
1612   auto CalleeCount = Callee->getEntryCount();
1613   if (!CalleeCount.hasValue())
1614     return;
1615 
1616   uint64_t priorEntryCount = CalleeCount.getCount();
1617   uint64_t newEntryCount;
1618 
1619   // Since CallSiteCount is an estimate, it could exceed the original callee
1620   // count and has to be set to 0 so guard against underflow.
1621   if (entryDelta < 0 && static_cast<uint64_t>(-entryDelta) > priorEntryCount)
1622     newEntryCount = 0;
1623   else
1624     newEntryCount = priorEntryCount + entryDelta;
1625 
1626   // During inlining ?
1627   if (VMap) {
1628     uint64_t cloneEntryCount = priorEntryCount - newEntryCount;
1629     for (auto Entry : *VMap)
1630       if (isa<CallInst>(Entry.first))
1631         if (auto *CI = dyn_cast_or_null<CallInst>(Entry.second))
1632           CI->updateProfWeight(cloneEntryCount, priorEntryCount);
1633   }
1634 
1635   if (entryDelta) {
1636     Callee->setEntryCount(newEntryCount);
1637 
1638     for (BasicBlock &BB : *Callee)
1639       // No need to update the callsite if it is pruned during inlining.
1640       if (!VMap || VMap->count(&BB))
1641         for (Instruction &I : BB)
1642           if (CallInst *CI = dyn_cast<CallInst>(&I))
1643             CI->updateProfWeight(newEntryCount, priorEntryCount);
1644   }
1645 }
1646 
1647 /// This function inlines the called function into the basic block of the
1648 /// caller. This returns false if it is not possible to inline this call.
1649 /// The program is still in a well defined state if this occurs though.
1650 ///
1651 /// Note that this only does one level of inlining.  For example, if the
1652 /// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
1653 /// exists in the instruction stream.  Similarly this will inline a recursive
1654 /// function by one level.
1655 llvm::InlineResult llvm::InlineFunction(CallBase &CB, InlineFunctionInfo &IFI,
1656                                         AAResults *CalleeAAR,
1657                                         bool InsertLifetime,
1658                                         Function *ForwardVarArgsTo) {
1659   assert(CB.getParent() && CB.getFunction() && "Instruction not in function!");
1660 
1661   // FIXME: we don't inline callbr yet.
1662   if (isa<CallBrInst>(CB))
1663     return InlineResult::failure("We don't inline callbr yet.");
1664 
1665   // If IFI has any state in it, zap it before we fill it in.
1666   IFI.reset();
1667 
1668   Function *CalledFunc = CB.getCalledFunction();
1669   if (!CalledFunc ||               // Can't inline external function or indirect
1670       CalledFunc->isDeclaration()) // call!
1671     return InlineResult::failure("external or indirect");
1672 
1673   // The inliner does not know how to inline through calls with operand bundles
1674   // in general ...
1675   if (CB.hasOperandBundles()) {
1676     for (int i = 0, e = CB.getNumOperandBundles(); i != e; ++i) {
1677       uint32_t Tag = CB.getOperandBundleAt(i).getTagID();
1678       // ... but it knows how to inline through "deopt" operand bundles ...
1679       if (Tag == LLVMContext::OB_deopt)
1680         continue;
1681       // ... and "funclet" operand bundles.
1682       if (Tag == LLVMContext::OB_funclet)
1683         continue;
1684 
1685       return InlineResult::failure("unsupported operand bundle");
1686     }
1687   }
1688 
1689   // If the call to the callee cannot throw, set the 'nounwind' flag on any
1690   // calls that we inline.
1691   bool MarkNoUnwind = CB.doesNotThrow();
1692 
1693   BasicBlock *OrigBB = CB.getParent();
1694   Function *Caller = OrigBB->getParent();
1695 
1696   // GC poses two hazards to inlining, which only occur when the callee has GC:
1697   //  1. If the caller has no GC, then the callee's GC must be propagated to the
1698   //     caller.
1699   //  2. If the caller has a differing GC, it is invalid to inline.
1700   if (CalledFunc->hasGC()) {
1701     if (!Caller->hasGC())
1702       Caller->setGC(CalledFunc->getGC());
1703     else if (CalledFunc->getGC() != Caller->getGC())
1704       return InlineResult::failure("incompatible GC");
1705   }
1706 
1707   // Get the personality function from the callee if it contains a landing pad.
1708   Constant *CalledPersonality =
1709       CalledFunc->hasPersonalityFn()
1710           ? CalledFunc->getPersonalityFn()->stripPointerCasts()
1711           : nullptr;
1712 
1713   // Find the personality function used by the landing pads of the caller. If it
1714   // exists, then check to see that it matches the personality function used in
1715   // the callee.
1716   Constant *CallerPersonality =
1717       Caller->hasPersonalityFn()
1718           ? Caller->getPersonalityFn()->stripPointerCasts()
1719           : nullptr;
1720   if (CalledPersonality) {
1721     if (!CallerPersonality)
1722       Caller->setPersonalityFn(CalledPersonality);
1723     // If the personality functions match, then we can perform the
1724     // inlining. Otherwise, we can't inline.
1725     // TODO: This isn't 100% true. Some personality functions are proper
1726     //       supersets of others and can be used in place of the other.
1727     else if (CalledPersonality != CallerPersonality)
1728       return InlineResult::failure("incompatible personality");
1729   }
1730 
1731   // We need to figure out which funclet the callsite was in so that we may
1732   // properly nest the callee.
1733   Instruction *CallSiteEHPad = nullptr;
1734   if (CallerPersonality) {
1735     EHPersonality Personality = classifyEHPersonality(CallerPersonality);
1736     if (isScopedEHPersonality(Personality)) {
1737       Optional<OperandBundleUse> ParentFunclet =
1738           CB.getOperandBundle(LLVMContext::OB_funclet);
1739       if (ParentFunclet)
1740         CallSiteEHPad = cast<FuncletPadInst>(ParentFunclet->Inputs.front());
1741 
1742       // OK, the inlining site is legal.  What about the target function?
1743 
1744       if (CallSiteEHPad) {
1745         if (Personality == EHPersonality::MSVC_CXX) {
1746           // The MSVC personality cannot tolerate catches getting inlined into
1747           // cleanup funclets.
1748           if (isa<CleanupPadInst>(CallSiteEHPad)) {
1749             // Ok, the call site is within a cleanuppad.  Let's check the callee
1750             // for catchpads.
1751             for (const BasicBlock &CalledBB : *CalledFunc) {
1752               if (isa<CatchSwitchInst>(CalledBB.getFirstNonPHI()))
1753                 return InlineResult::failure("catch in cleanup funclet");
1754             }
1755           }
1756         } else if (isAsynchronousEHPersonality(Personality)) {
1757           // SEH is even less tolerant, there may not be any sort of exceptional
1758           // funclet in the callee.
1759           for (const BasicBlock &CalledBB : *CalledFunc) {
1760             if (CalledBB.isEHPad())
1761               return InlineResult::failure("SEH in cleanup funclet");
1762           }
1763         }
1764       }
1765     }
1766   }
1767 
1768   // Determine if we are dealing with a call in an EHPad which does not unwind
1769   // to caller.
1770   bool EHPadForCallUnwindsLocally = false;
1771   if (CallSiteEHPad && isa<CallInst>(CB)) {
1772     UnwindDestMemoTy FuncletUnwindMap;
1773     Value *CallSiteUnwindDestToken =
1774         getUnwindDestToken(CallSiteEHPad, FuncletUnwindMap);
1775 
1776     EHPadForCallUnwindsLocally =
1777         CallSiteUnwindDestToken &&
1778         !isa<ConstantTokenNone>(CallSiteUnwindDestToken);
1779   }
1780 
1781   // Get an iterator to the last basic block in the function, which will have
1782   // the new function inlined after it.
1783   Function::iterator LastBlock = --Caller->end();
1784 
1785   // Make sure to capture all of the return instructions from the cloned
1786   // function.
1787   SmallVector<ReturnInst*, 8> Returns;
1788   ClonedCodeInfo InlinedFunctionInfo;
1789   Function::iterator FirstNewBlock;
1790 
1791   { // Scope to destroy VMap after cloning.
1792     ValueToValueMapTy VMap;
1793     // Keep a list of pair (dst, src) to emit byval initializations.
1794     SmallVector<std::pair<Value*, Value*>, 4> ByValInit;
1795 
1796     // When inlining a function that contains noalias scope metadata,
1797     // this metadata needs to be cloned so that the inlined blocks
1798     // have different "unique scopes" at every call site.
1799     // Track the metadata that must be cloned. Do this before other changes to
1800     // the function, so that we do not get in trouble when inlining caller ==
1801     // callee.
1802     ScopedAliasMetadataDeepCloner SAMetadataCloner(CB.getCalledFunction());
1803 
1804     auto &DL = Caller->getParent()->getDataLayout();
1805 
1806     // Calculate the vector of arguments to pass into the function cloner, which
1807     // matches up the formal to the actual argument values.
1808     auto AI = CB.arg_begin();
1809     unsigned ArgNo = 0;
1810     for (Function::arg_iterator I = CalledFunc->arg_begin(),
1811          E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) {
1812       Value *ActualArg = *AI;
1813 
1814       // When byval arguments actually inlined, we need to make the copy implied
1815       // by them explicit.  However, we don't do this if the callee is readonly
1816       // or readnone, because the copy would be unneeded: the callee doesn't
1817       // modify the struct.
1818       if (CB.isByValArgument(ArgNo)) {
1819         ActualArg = HandleByValArgument(ActualArg, &CB, CalledFunc, IFI,
1820                                         CalledFunc->getParamAlignment(ArgNo));
1821         if (ActualArg != *AI)
1822           ByValInit.push_back(std::make_pair(ActualArg, (Value*) *AI));
1823       }
1824 
1825       VMap[&*I] = ActualArg;
1826     }
1827 
1828     // TODO: Remove this when users have been updated to the assume bundles.
1829     // Add alignment assumptions if necessary. We do this before the inlined
1830     // instructions are actually cloned into the caller so that we can easily
1831     // check what will be known at the start of the inlined code.
1832     AddAlignmentAssumptions(CB, IFI);
1833 
1834     AssumptionCache *AC =
1835         IFI.GetAssumptionCache ? &IFI.GetAssumptionCache(*Caller) : nullptr;
1836 
1837     /// Preserve all attributes on of the call and its parameters.
1838     salvageKnowledge(&CB, AC);
1839 
1840     // We want the inliner to prune the code as it copies.  We would LOVE to
1841     // have no dead or constant instructions leftover after inlining occurs
1842     // (which can happen, e.g., because an argument was constant), but we'll be
1843     // happy with whatever the cloner can do.
1844     CloneAndPruneFunctionInto(Caller, CalledFunc, VMap,
1845                               /*ModuleLevelChanges=*/false, Returns, ".i",
1846                               &InlinedFunctionInfo, &CB);
1847     // Remember the first block that is newly cloned over.
1848     FirstNewBlock = LastBlock; ++FirstNewBlock;
1849 
1850     if (IFI.CallerBFI != nullptr && IFI.CalleeBFI != nullptr)
1851       // Update the BFI of blocks cloned into the caller.
1852       updateCallerBFI(OrigBB, VMap, IFI.CallerBFI, IFI.CalleeBFI,
1853                       CalledFunc->front());
1854 
1855     updateCallProfile(CalledFunc, VMap, CalledFunc->getEntryCount(), CB,
1856                       IFI.PSI, IFI.CallerBFI);
1857 
1858     // Inject byval arguments initialization.
1859     for (std::pair<Value*, Value*> &Init : ByValInit)
1860       HandleByValArgumentInit(Init.first, Init.second, Caller->getParent(),
1861                               &*FirstNewBlock, IFI);
1862 
1863     Optional<OperandBundleUse> ParentDeopt =
1864         CB.getOperandBundle(LLVMContext::OB_deopt);
1865     if (ParentDeopt) {
1866       SmallVector<OperandBundleDef, 2> OpDefs;
1867 
1868       for (auto &VH : InlinedFunctionInfo.OperandBundleCallSites) {
1869         CallBase *ICS = dyn_cast_or_null<CallBase>(VH);
1870         if (!ICS)
1871           continue; // instruction was DCE'd or RAUW'ed to undef
1872 
1873         OpDefs.clear();
1874 
1875         OpDefs.reserve(ICS->getNumOperandBundles());
1876 
1877         for (unsigned COBi = 0, COBe = ICS->getNumOperandBundles(); COBi < COBe;
1878              ++COBi) {
1879           auto ChildOB = ICS->getOperandBundleAt(COBi);
1880           if (ChildOB.getTagID() != LLVMContext::OB_deopt) {
1881             // If the inlined call has other operand bundles, let them be
1882             OpDefs.emplace_back(ChildOB);
1883             continue;
1884           }
1885 
1886           // It may be useful to separate this logic (of handling operand
1887           // bundles) out to a separate "policy" component if this gets crowded.
1888           // Prepend the parent's deoptimization continuation to the newly
1889           // inlined call's deoptimization continuation.
1890           std::vector<Value *> MergedDeoptArgs;
1891           MergedDeoptArgs.reserve(ParentDeopt->Inputs.size() +
1892                                   ChildOB.Inputs.size());
1893 
1894           llvm::append_range(MergedDeoptArgs, ParentDeopt->Inputs);
1895           llvm::append_range(MergedDeoptArgs, ChildOB.Inputs);
1896 
1897           OpDefs.emplace_back("deopt", std::move(MergedDeoptArgs));
1898         }
1899 
1900         Instruction *NewI = CallBase::Create(ICS, OpDefs, ICS);
1901 
1902         // Note: the RAUW does the appropriate fixup in VMap, so we need to do
1903         // this even if the call returns void.
1904         ICS->replaceAllUsesWith(NewI);
1905 
1906         VH = nullptr;
1907         ICS->eraseFromParent();
1908       }
1909     }
1910 
1911     // Update the callgraph if requested.
1912     if (IFI.CG)
1913       UpdateCallGraphAfterInlining(CB, FirstNewBlock, VMap, IFI);
1914 
1915     // For 'nodebug' functions, the associated DISubprogram is always null.
1916     // Conservatively avoid propagating the callsite debug location to
1917     // instructions inlined from a function whose DISubprogram is not null.
1918     fixupLineNumbers(Caller, FirstNewBlock, &CB,
1919                      CalledFunc->getSubprogram() != nullptr);
1920 
1921     // Now clone the inlined noalias scope metadata.
1922     SAMetadataCloner.clone();
1923     SAMetadataCloner.remap(VMap);
1924 
1925     // Add noalias metadata if necessary.
1926     AddAliasScopeMetadata(CB, VMap, DL, CalleeAAR);
1927 
1928     // Clone return attributes on the callsite into the calls within the inlined
1929     // function which feed into its return value.
1930     AddReturnAttributes(CB, VMap);
1931 
1932     // Propagate metadata on the callsite if necessary.
1933     PropagateCallSiteMetadata(CB, VMap);
1934 
1935     // Register any cloned assumptions.
1936     if (IFI.GetAssumptionCache)
1937       for (BasicBlock &NewBlock :
1938            make_range(FirstNewBlock->getIterator(), Caller->end()))
1939         for (Instruction &I : NewBlock)
1940           if (auto *II = dyn_cast<IntrinsicInst>(&I))
1941             if (II->getIntrinsicID() == Intrinsic::assume)
1942               IFI.GetAssumptionCache(*Caller).registerAssumption(II);
1943   }
1944 
1945   // If there are any alloca instructions in the block that used to be the entry
1946   // block for the callee, move them to the entry block of the caller.  First
1947   // calculate which instruction they should be inserted before.  We insert the
1948   // instructions at the end of the current alloca list.
1949   {
1950     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
1951     for (BasicBlock::iterator I = FirstNewBlock->begin(),
1952          E = FirstNewBlock->end(); I != E; ) {
1953       AllocaInst *AI = dyn_cast<AllocaInst>(I++);
1954       if (!AI) continue;
1955 
1956       // If the alloca is now dead, remove it.  This often occurs due to code
1957       // specialization.
1958       if (AI->use_empty()) {
1959         AI->eraseFromParent();
1960         continue;
1961       }
1962 
1963       if (!allocaWouldBeStaticInEntry(AI))
1964         continue;
1965 
1966       // Keep track of the static allocas that we inline into the caller.
1967       IFI.StaticAllocas.push_back(AI);
1968 
1969       // Scan for the block of allocas that we can move over, and move them
1970       // all at once.
1971       while (isa<AllocaInst>(I) &&
1972              !cast<AllocaInst>(I)->use_empty() &&
1973              allocaWouldBeStaticInEntry(cast<AllocaInst>(I))) {
1974         IFI.StaticAllocas.push_back(cast<AllocaInst>(I));
1975         ++I;
1976       }
1977 
1978       // Transfer all of the allocas over in a block.  Using splice means
1979       // that the instructions aren't removed from the symbol table, then
1980       // reinserted.
1981       Caller->getEntryBlock().getInstList().splice(
1982           InsertPoint, FirstNewBlock->getInstList(), AI->getIterator(), I);
1983     }
1984   }
1985 
1986   SmallVector<Value*,4> VarArgsToForward;
1987   SmallVector<AttributeSet, 4> VarArgsAttrs;
1988   for (unsigned i = CalledFunc->getFunctionType()->getNumParams();
1989        i < CB.getNumArgOperands(); i++) {
1990     VarArgsToForward.push_back(CB.getArgOperand(i));
1991     VarArgsAttrs.push_back(CB.getAttributes().getParamAttributes(i));
1992   }
1993 
1994   bool InlinedMustTailCalls = false, InlinedDeoptimizeCalls = false;
1995   if (InlinedFunctionInfo.ContainsCalls) {
1996     CallInst::TailCallKind CallSiteTailKind = CallInst::TCK_None;
1997     if (CallInst *CI = dyn_cast<CallInst>(&CB))
1998       CallSiteTailKind = CI->getTailCallKind();
1999 
2000     // For inlining purposes, the "notail" marker is the same as no marker.
2001     if (CallSiteTailKind == CallInst::TCK_NoTail)
2002       CallSiteTailKind = CallInst::TCK_None;
2003 
2004     for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E;
2005          ++BB) {
2006       for (auto II = BB->begin(); II != BB->end();) {
2007         Instruction &I = *II++;
2008         CallInst *CI = dyn_cast<CallInst>(&I);
2009         if (!CI)
2010           continue;
2011 
2012         // Forward varargs from inlined call site to calls to the
2013         // ForwardVarArgsTo function, if requested, and to musttail calls.
2014         if (!VarArgsToForward.empty() &&
2015             ((ForwardVarArgsTo &&
2016               CI->getCalledFunction() == ForwardVarArgsTo) ||
2017              CI->isMustTailCall())) {
2018           // Collect attributes for non-vararg parameters.
2019           AttributeList Attrs = CI->getAttributes();
2020           SmallVector<AttributeSet, 8> ArgAttrs;
2021           if (!Attrs.isEmpty() || !VarArgsAttrs.empty()) {
2022             for (unsigned ArgNo = 0;
2023                  ArgNo < CI->getFunctionType()->getNumParams(); ++ArgNo)
2024               ArgAttrs.push_back(Attrs.getParamAttributes(ArgNo));
2025           }
2026 
2027           // Add VarArg attributes.
2028           ArgAttrs.append(VarArgsAttrs.begin(), VarArgsAttrs.end());
2029           Attrs = AttributeList::get(CI->getContext(), Attrs.getFnAttributes(),
2030                                      Attrs.getRetAttributes(), ArgAttrs);
2031           // Add VarArgs to existing parameters.
2032           SmallVector<Value *, 6> Params(CI->arg_operands());
2033           Params.append(VarArgsToForward.begin(), VarArgsToForward.end());
2034           CallInst *NewCI = CallInst::Create(
2035               CI->getFunctionType(), CI->getCalledOperand(), Params, "", CI);
2036           NewCI->setDebugLoc(CI->getDebugLoc());
2037           NewCI->setAttributes(Attrs);
2038           NewCI->setCallingConv(CI->getCallingConv());
2039           CI->replaceAllUsesWith(NewCI);
2040           CI->eraseFromParent();
2041           CI = NewCI;
2042         }
2043 
2044         if (Function *F = CI->getCalledFunction())
2045           InlinedDeoptimizeCalls |=
2046               F->getIntrinsicID() == Intrinsic::experimental_deoptimize;
2047 
2048         // We need to reduce the strength of any inlined tail calls.  For
2049         // musttail, we have to avoid introducing potential unbounded stack
2050         // growth.  For example, if functions 'f' and 'g' are mutually recursive
2051         // with musttail, we can inline 'g' into 'f' so long as we preserve
2052         // musttail on the cloned call to 'f'.  If either the inlined call site
2053         // or the cloned call site is *not* musttail, the program already has
2054         // one frame of stack growth, so it's safe to remove musttail.  Here is
2055         // a table of example transformations:
2056         //
2057         //    f -> musttail g -> musttail f  ==>  f -> musttail f
2058         //    f -> musttail g ->     tail f  ==>  f ->     tail f
2059         //    f ->          g -> musttail f  ==>  f ->          f
2060         //    f ->          g ->     tail f  ==>  f ->          f
2061         //
2062         // Inlined notail calls should remain notail calls.
2063         CallInst::TailCallKind ChildTCK = CI->getTailCallKind();
2064         if (ChildTCK != CallInst::TCK_NoTail)
2065           ChildTCK = std::min(CallSiteTailKind, ChildTCK);
2066         CI->setTailCallKind(ChildTCK);
2067         InlinedMustTailCalls |= CI->isMustTailCall();
2068 
2069         // Calls inlined through a 'nounwind' call site should be marked
2070         // 'nounwind'.
2071         if (MarkNoUnwind)
2072           CI->setDoesNotThrow();
2073       }
2074     }
2075   }
2076 
2077   // Leave lifetime markers for the static alloca's, scoping them to the
2078   // function we just inlined.
2079   if (InsertLifetime && !IFI.StaticAllocas.empty()) {
2080     IRBuilder<> builder(&FirstNewBlock->front());
2081     for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) {
2082       AllocaInst *AI = IFI.StaticAllocas[ai];
2083       // Don't mark swifterror allocas. They can't have bitcast uses.
2084       if (AI->isSwiftError())
2085         continue;
2086 
2087       // If the alloca is already scoped to something smaller than the whole
2088       // function then there's no need to add redundant, less accurate markers.
2089       if (hasLifetimeMarkers(AI))
2090         continue;
2091 
2092       // Try to determine the size of the allocation.
2093       ConstantInt *AllocaSize = nullptr;
2094       if (ConstantInt *AIArraySize =
2095           dyn_cast<ConstantInt>(AI->getArraySize())) {
2096         auto &DL = Caller->getParent()->getDataLayout();
2097         Type *AllocaType = AI->getAllocatedType();
2098         TypeSize AllocaTypeSize = DL.getTypeAllocSize(AllocaType);
2099         uint64_t AllocaArraySize = AIArraySize->getLimitedValue();
2100 
2101         // Don't add markers for zero-sized allocas.
2102         if (AllocaArraySize == 0)
2103           continue;
2104 
2105         // Check that array size doesn't saturate uint64_t and doesn't
2106         // overflow when it's multiplied by type size.
2107         if (!AllocaTypeSize.isScalable() &&
2108             AllocaArraySize != std::numeric_limits<uint64_t>::max() &&
2109             std::numeric_limits<uint64_t>::max() / AllocaArraySize >=
2110                 AllocaTypeSize.getFixedSize()) {
2111           AllocaSize = ConstantInt::get(Type::getInt64Ty(AI->getContext()),
2112                                         AllocaArraySize * AllocaTypeSize);
2113         }
2114       }
2115 
2116       builder.CreateLifetimeStart(AI, AllocaSize);
2117       for (ReturnInst *RI : Returns) {
2118         // Don't insert llvm.lifetime.end calls between a musttail or deoptimize
2119         // call and a return.  The return kills all local allocas.
2120         if (InlinedMustTailCalls &&
2121             RI->getParent()->getTerminatingMustTailCall())
2122           continue;
2123         if (InlinedDeoptimizeCalls &&
2124             RI->getParent()->getTerminatingDeoptimizeCall())
2125           continue;
2126         IRBuilder<>(RI).CreateLifetimeEnd(AI, AllocaSize);
2127       }
2128     }
2129   }
2130 
2131   // If the inlined code contained dynamic alloca instructions, wrap the inlined
2132   // code with llvm.stacksave/llvm.stackrestore intrinsics.
2133   if (InlinedFunctionInfo.ContainsDynamicAllocas) {
2134     Module *M = Caller->getParent();
2135     // Get the two intrinsics we care about.
2136     Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave);
2137     Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore);
2138 
2139     // Insert the llvm.stacksave.
2140     CallInst *SavedPtr = IRBuilder<>(&*FirstNewBlock, FirstNewBlock->begin())
2141                              .CreateCall(StackSave, {}, "savedstack");
2142 
2143     // Insert a call to llvm.stackrestore before any return instructions in the
2144     // inlined function.
2145     for (ReturnInst *RI : Returns) {
2146       // Don't insert llvm.stackrestore calls between a musttail or deoptimize
2147       // call and a return.  The return will restore the stack pointer.
2148       if (InlinedMustTailCalls && RI->getParent()->getTerminatingMustTailCall())
2149         continue;
2150       if (InlinedDeoptimizeCalls && RI->getParent()->getTerminatingDeoptimizeCall())
2151         continue;
2152       IRBuilder<>(RI).CreateCall(StackRestore, SavedPtr);
2153     }
2154   }
2155 
2156   // If we are inlining for an invoke instruction, we must make sure to rewrite
2157   // any call instructions into invoke instructions.  This is sensitive to which
2158   // funclet pads were top-level in the inlinee, so must be done before
2159   // rewriting the "parent pad" links.
2160   if (auto *II = dyn_cast<InvokeInst>(&CB)) {
2161     BasicBlock *UnwindDest = II->getUnwindDest();
2162     Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI();
2163     if (isa<LandingPadInst>(FirstNonPHI)) {
2164       HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo);
2165     } else {
2166       HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo);
2167     }
2168   }
2169 
2170   // Update the lexical scopes of the new funclets and callsites.
2171   // Anything that had 'none' as its parent is now nested inside the callsite's
2172   // EHPad.
2173 
2174   if (CallSiteEHPad) {
2175     for (Function::iterator BB = FirstNewBlock->getIterator(),
2176                             E = Caller->end();
2177          BB != E; ++BB) {
2178       // Add bundle operands to any top-level call sites.
2179       SmallVector<OperandBundleDef, 1> OpBundles;
2180       for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;) {
2181         CallBase *I = dyn_cast<CallBase>(&*BBI++);
2182         if (!I)
2183           continue;
2184 
2185         // Skip call sites which are nounwind intrinsics.
2186         auto *CalledFn =
2187             dyn_cast<Function>(I->getCalledOperand()->stripPointerCasts());
2188         if (CalledFn && CalledFn->isIntrinsic() && I->doesNotThrow())
2189           continue;
2190 
2191         // Skip call sites which already have a "funclet" bundle.
2192         if (I->getOperandBundle(LLVMContext::OB_funclet))
2193           continue;
2194 
2195         I->getOperandBundlesAsDefs(OpBundles);
2196         OpBundles.emplace_back("funclet", CallSiteEHPad);
2197 
2198         Instruction *NewInst = CallBase::Create(I, OpBundles, I);
2199         NewInst->takeName(I);
2200         I->replaceAllUsesWith(NewInst);
2201         I->eraseFromParent();
2202 
2203         OpBundles.clear();
2204       }
2205 
2206       // It is problematic if the inlinee has a cleanupret which unwinds to
2207       // caller and we inline it into a call site which doesn't unwind but into
2208       // an EH pad that does.  Such an edge must be dynamically unreachable.
2209       // As such, we replace the cleanupret with unreachable.
2210       if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(BB->getTerminator()))
2211         if (CleanupRet->unwindsToCaller() && EHPadForCallUnwindsLocally)
2212           changeToUnreachable(CleanupRet, /*UseLLVMTrap=*/false);
2213 
2214       Instruction *I = BB->getFirstNonPHI();
2215       if (!I->isEHPad())
2216         continue;
2217 
2218       if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) {
2219         if (isa<ConstantTokenNone>(CatchSwitch->getParentPad()))
2220           CatchSwitch->setParentPad(CallSiteEHPad);
2221       } else {
2222         auto *FPI = cast<FuncletPadInst>(I);
2223         if (isa<ConstantTokenNone>(FPI->getParentPad()))
2224           FPI->setParentPad(CallSiteEHPad);
2225       }
2226     }
2227   }
2228 
2229   if (InlinedDeoptimizeCalls) {
2230     // We need to at least remove the deoptimizing returns from the Return set,
2231     // so that the control flow from those returns does not get merged into the
2232     // caller (but terminate it instead).  If the caller's return type does not
2233     // match the callee's return type, we also need to change the return type of
2234     // the intrinsic.
2235     if (Caller->getReturnType() == CB.getType()) {
2236       llvm::erase_if(Returns, [](ReturnInst *RI) {
2237         return RI->getParent()->getTerminatingDeoptimizeCall() != nullptr;
2238       });
2239     } else {
2240       SmallVector<ReturnInst *, 8> NormalReturns;
2241       Function *NewDeoptIntrinsic = Intrinsic::getDeclaration(
2242           Caller->getParent(), Intrinsic::experimental_deoptimize,
2243           {Caller->getReturnType()});
2244 
2245       for (ReturnInst *RI : Returns) {
2246         CallInst *DeoptCall = RI->getParent()->getTerminatingDeoptimizeCall();
2247         if (!DeoptCall) {
2248           NormalReturns.push_back(RI);
2249           continue;
2250         }
2251 
2252         // The calling convention on the deoptimize call itself may be bogus,
2253         // since the code we're inlining may have undefined behavior (and may
2254         // never actually execute at runtime); but all
2255         // @llvm.experimental.deoptimize declarations have to have the same
2256         // calling convention in a well-formed module.
2257         auto CallingConv = DeoptCall->getCalledFunction()->getCallingConv();
2258         NewDeoptIntrinsic->setCallingConv(CallingConv);
2259         auto *CurBB = RI->getParent();
2260         RI->eraseFromParent();
2261 
2262         SmallVector<Value *, 4> CallArgs(DeoptCall->args());
2263 
2264         SmallVector<OperandBundleDef, 1> OpBundles;
2265         DeoptCall->getOperandBundlesAsDefs(OpBundles);
2266         DeoptCall->eraseFromParent();
2267         assert(!OpBundles.empty() &&
2268                "Expected at least the deopt operand bundle");
2269 
2270         IRBuilder<> Builder(CurBB);
2271         CallInst *NewDeoptCall =
2272             Builder.CreateCall(NewDeoptIntrinsic, CallArgs, OpBundles);
2273         NewDeoptCall->setCallingConv(CallingConv);
2274         if (NewDeoptCall->getType()->isVoidTy())
2275           Builder.CreateRetVoid();
2276         else
2277           Builder.CreateRet(NewDeoptCall);
2278       }
2279 
2280       // Leave behind the normal returns so we can merge control flow.
2281       std::swap(Returns, NormalReturns);
2282     }
2283   }
2284 
2285   // Handle any inlined musttail call sites.  In order for a new call site to be
2286   // musttail, the source of the clone and the inlined call site must have been
2287   // musttail.  Therefore it's safe to return without merging control into the
2288   // phi below.
2289   if (InlinedMustTailCalls) {
2290     // Check if we need to bitcast the result of any musttail calls.
2291     Type *NewRetTy = Caller->getReturnType();
2292     bool NeedBitCast = !CB.use_empty() && CB.getType() != NewRetTy;
2293 
2294     // Handle the returns preceded by musttail calls separately.
2295     SmallVector<ReturnInst *, 8> NormalReturns;
2296     for (ReturnInst *RI : Returns) {
2297       CallInst *ReturnedMustTail =
2298           RI->getParent()->getTerminatingMustTailCall();
2299       if (!ReturnedMustTail) {
2300         NormalReturns.push_back(RI);
2301         continue;
2302       }
2303       if (!NeedBitCast)
2304         continue;
2305 
2306       // Delete the old return and any preceding bitcast.
2307       BasicBlock *CurBB = RI->getParent();
2308       auto *OldCast = dyn_cast_or_null<BitCastInst>(RI->getReturnValue());
2309       RI->eraseFromParent();
2310       if (OldCast)
2311         OldCast->eraseFromParent();
2312 
2313       // Insert a new bitcast and return with the right type.
2314       IRBuilder<> Builder(CurBB);
2315       Builder.CreateRet(Builder.CreateBitCast(ReturnedMustTail, NewRetTy));
2316     }
2317 
2318     // Leave behind the normal returns so we can merge control flow.
2319     std::swap(Returns, NormalReturns);
2320   }
2321 
2322   // Now that all of the transforms on the inlined code have taken place but
2323   // before we splice the inlined code into the CFG and lose track of which
2324   // blocks were actually inlined, collect the call sites. We only do this if
2325   // call graph updates weren't requested, as those provide value handle based
2326   // tracking of inlined call sites instead.
2327   if (InlinedFunctionInfo.ContainsCalls && !IFI.CG) {
2328     // Otherwise just collect the raw call sites that were inlined.
2329     for (BasicBlock &NewBB :
2330          make_range(FirstNewBlock->getIterator(), Caller->end()))
2331       for (Instruction &I : NewBB)
2332         if (auto *CB = dyn_cast<CallBase>(&I))
2333           IFI.InlinedCallSites.push_back(CB);
2334   }
2335 
2336   // If we cloned in _exactly one_ basic block, and if that block ends in a
2337   // return instruction, we splice the body of the inlined callee directly into
2338   // the calling basic block.
2339   if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) {
2340     // Move all of the instructions right before the call.
2341     OrigBB->getInstList().splice(CB.getIterator(), FirstNewBlock->getInstList(),
2342                                  FirstNewBlock->begin(), FirstNewBlock->end());
2343     // Remove the cloned basic block.
2344     Caller->getBasicBlockList().pop_back();
2345 
2346     // If the call site was an invoke instruction, add a branch to the normal
2347     // destination.
2348     if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {
2349       BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), &CB);
2350       NewBr->setDebugLoc(Returns[0]->getDebugLoc());
2351     }
2352 
2353     // If the return instruction returned a value, replace uses of the call with
2354     // uses of the returned value.
2355     if (!CB.use_empty()) {
2356       ReturnInst *R = Returns[0];
2357       if (&CB == R->getReturnValue())
2358         CB.replaceAllUsesWith(UndefValue::get(CB.getType()));
2359       else
2360         CB.replaceAllUsesWith(R->getReturnValue());
2361     }
2362     // Since we are now done with the Call/Invoke, we can delete it.
2363     CB.eraseFromParent();
2364 
2365     // Since we are now done with the return instruction, delete it also.
2366     Returns[0]->eraseFromParent();
2367 
2368     // We are now done with the inlining.
2369     return InlineResult::success();
2370   }
2371 
2372   // Otherwise, we have the normal case, of more than one block to inline or
2373   // multiple return sites.
2374 
2375   // We want to clone the entire callee function into the hole between the
2376   // "starter" and "ender" blocks.  How we accomplish this depends on whether
2377   // this is an invoke instruction or a call instruction.
2378   BasicBlock *AfterCallBB;
2379   BranchInst *CreatedBranchToNormalDest = nullptr;
2380   if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {
2381 
2382     // Add an unconditional branch to make this look like the CallInst case...
2383     CreatedBranchToNormalDest = BranchInst::Create(II->getNormalDest(), &CB);
2384 
2385     // Split the basic block.  This guarantees that no PHI nodes will have to be
2386     // updated due to new incoming edges, and make the invoke case more
2387     // symmetric to the call case.
2388     AfterCallBB =
2389         OrigBB->splitBasicBlock(CreatedBranchToNormalDest->getIterator(),
2390                                 CalledFunc->getName() + ".exit");
2391 
2392   } else { // It's a call
2393     // If this is a call instruction, we need to split the basic block that
2394     // the call lives in.
2395     //
2396     AfterCallBB = OrigBB->splitBasicBlock(CB.getIterator(),
2397                                           CalledFunc->getName() + ".exit");
2398   }
2399 
2400   if (IFI.CallerBFI) {
2401     // Copy original BB's block frequency to AfterCallBB
2402     IFI.CallerBFI->setBlockFreq(
2403         AfterCallBB, IFI.CallerBFI->getBlockFreq(OrigBB).getFrequency());
2404   }
2405 
2406   // Change the branch that used to go to AfterCallBB to branch to the first
2407   // basic block of the inlined function.
2408   //
2409   Instruction *Br = OrigBB->getTerminator();
2410   assert(Br && Br->getOpcode() == Instruction::Br &&
2411          "splitBasicBlock broken!");
2412   Br->setOperand(0, &*FirstNewBlock);
2413 
2414   // Now that the function is correct, make it a little bit nicer.  In
2415   // particular, move the basic blocks inserted from the end of the function
2416   // into the space made by splitting the source basic block.
2417   Caller->getBasicBlockList().splice(AfterCallBB->getIterator(),
2418                                      Caller->getBasicBlockList(), FirstNewBlock,
2419                                      Caller->end());
2420 
2421   // Handle all of the return instructions that we just cloned in, and eliminate
2422   // any users of the original call/invoke instruction.
2423   Type *RTy = CalledFunc->getReturnType();
2424 
2425   PHINode *PHI = nullptr;
2426   if (Returns.size() > 1) {
2427     // The PHI node should go at the front of the new basic block to merge all
2428     // possible incoming values.
2429     if (!CB.use_empty()) {
2430       PHI = PHINode::Create(RTy, Returns.size(), CB.getName(),
2431                             &AfterCallBB->front());
2432       // Anything that used the result of the function call should now use the
2433       // PHI node as their operand.
2434       CB.replaceAllUsesWith(PHI);
2435     }
2436 
2437     // Loop over all of the return instructions adding entries to the PHI node
2438     // as appropriate.
2439     if (PHI) {
2440       for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
2441         ReturnInst *RI = Returns[i];
2442         assert(RI->getReturnValue()->getType() == PHI->getType() &&
2443                "Ret value not consistent in function!");
2444         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
2445       }
2446     }
2447 
2448     // Add a branch to the merge points and remove return instructions.
2449     DebugLoc Loc;
2450     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
2451       ReturnInst *RI = Returns[i];
2452       BranchInst* BI = BranchInst::Create(AfterCallBB, RI);
2453       Loc = RI->getDebugLoc();
2454       BI->setDebugLoc(Loc);
2455       RI->eraseFromParent();
2456     }
2457     // We need to set the debug location to *somewhere* inside the
2458     // inlined function. The line number may be nonsensical, but the
2459     // instruction will at least be associated with the right
2460     // function.
2461     if (CreatedBranchToNormalDest)
2462       CreatedBranchToNormalDest->setDebugLoc(Loc);
2463   } else if (!Returns.empty()) {
2464     // Otherwise, if there is exactly one return value, just replace anything
2465     // using the return value of the call with the computed value.
2466     if (!CB.use_empty()) {
2467       if (&CB == Returns[0]->getReturnValue())
2468         CB.replaceAllUsesWith(UndefValue::get(CB.getType()));
2469       else
2470         CB.replaceAllUsesWith(Returns[0]->getReturnValue());
2471     }
2472 
2473     // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
2474     BasicBlock *ReturnBB = Returns[0]->getParent();
2475     ReturnBB->replaceAllUsesWith(AfterCallBB);
2476 
2477     // Splice the code from the return block into the block that it will return
2478     // to, which contains the code that was after the call.
2479     AfterCallBB->getInstList().splice(AfterCallBB->begin(),
2480                                       ReturnBB->getInstList());
2481 
2482     if (CreatedBranchToNormalDest)
2483       CreatedBranchToNormalDest->setDebugLoc(Returns[0]->getDebugLoc());
2484 
2485     // Delete the return instruction now and empty ReturnBB now.
2486     Returns[0]->eraseFromParent();
2487     ReturnBB->eraseFromParent();
2488   } else if (!CB.use_empty()) {
2489     // No returns, but something is using the return value of the call.  Just
2490     // nuke the result.
2491     CB.replaceAllUsesWith(UndefValue::get(CB.getType()));
2492   }
2493 
2494   // Since we are now done with the Call/Invoke, we can delete it.
2495   CB.eraseFromParent();
2496 
2497   // If we inlined any musttail calls and the original return is now
2498   // unreachable, delete it.  It can only contain a bitcast and ret.
2499   if (InlinedMustTailCalls && pred_empty(AfterCallBB))
2500     AfterCallBB->eraseFromParent();
2501 
2502   // We should always be able to fold the entry block of the function into the
2503   // single predecessor of the block...
2504   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
2505   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
2506 
2507   // Splice the code entry block into calling block, right before the
2508   // unconditional branch.
2509   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes
2510   OrigBB->getInstList().splice(Br->getIterator(), CalleeEntry->getInstList());
2511 
2512   // Remove the unconditional branch.
2513   OrigBB->getInstList().erase(Br);
2514 
2515   // Now we can remove the CalleeEntry block, which is now empty.
2516   Caller->getBasicBlockList().erase(CalleeEntry);
2517 
2518   // If we inserted a phi node, check to see if it has a single value (e.g. all
2519   // the entries are the same or undef).  If so, remove the PHI so it doesn't
2520   // block other optimizations.
2521   if (PHI) {
2522     AssumptionCache *AC =
2523         IFI.GetAssumptionCache ? &IFI.GetAssumptionCache(*Caller) : nullptr;
2524     auto &DL = Caller->getParent()->getDataLayout();
2525     if (Value *V = SimplifyInstruction(PHI, {DL, nullptr, nullptr, AC})) {
2526       PHI->replaceAllUsesWith(V);
2527       PHI->eraseFromParent();
2528     }
2529   }
2530 
2531   return InlineResult::success();
2532 }
2533