Coverage Report

Created: 2019-07-24 05:18

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