Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/CodeExtractor.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CodeExtractor.cpp - Pull code region into a new function -----------===//
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 the interface to tear out a code region, such as an
10
// individual loop or a parallel section, into a new function, replacing it with
11
// a call to the new function.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/Transforms/Utils/CodeExtractor.h"
16
#include "llvm/ADT/ArrayRef.h"
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/Optional.h"
19
#include "llvm/ADT/STLExtras.h"
20
#include "llvm/ADT/SetVector.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/Analysis/AssumptionCache.h"
24
#include "llvm/Analysis/BlockFrequencyInfo.h"
25
#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
26
#include "llvm/Analysis/BranchProbabilityInfo.h"
27
#include "llvm/Analysis/LoopInfo.h"
28
#include "llvm/IR/Argument.h"
29
#include "llvm/IR/Attributes.h"
30
#include "llvm/IR/BasicBlock.h"
31
#include "llvm/IR/CFG.h"
32
#include "llvm/IR/Constant.h"
33
#include "llvm/IR/Constants.h"
34
#include "llvm/IR/DataLayout.h"
35
#include "llvm/IR/DerivedTypes.h"
36
#include "llvm/IR/Dominators.h"
37
#include "llvm/IR/Function.h"
38
#include "llvm/IR/GlobalValue.h"
39
#include "llvm/IR/InstrTypes.h"
40
#include "llvm/IR/Instruction.h"
41
#include "llvm/IR/Instructions.h"
42
#include "llvm/IR/IntrinsicInst.h"
43
#include "llvm/IR/Intrinsics.h"
44
#include "llvm/IR/LLVMContext.h"
45
#include "llvm/IR/MDBuilder.h"
46
#include "llvm/IR/Module.h"
47
#include "llvm/IR/PatternMatch.h"
48
#include "llvm/IR/Type.h"
49
#include "llvm/IR/User.h"
50
#include "llvm/IR/Value.h"
51
#include "llvm/IR/Verifier.h"
52
#include "llvm/Pass.h"
53
#include "llvm/Support/BlockFrequency.h"
54
#include "llvm/Support/BranchProbability.h"
55
#include "llvm/Support/Casting.h"
56
#include "llvm/Support/CommandLine.h"
57
#include "llvm/Support/Debug.h"
58
#include "llvm/Support/ErrorHandling.h"
59
#include "llvm/Support/raw_ostream.h"
60
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
61
#include "llvm/Transforms/Utils/Local.h"
62
#include <cassert>
63
#include <cstdint>
64
#include <iterator>
65
#include <map>
66
#include <set>
67
#include <utility>
68
#include <vector>
69
70
using namespace llvm;
71
using namespace llvm::PatternMatch;
72
using ProfileCount = Function::ProfileCount;
73
74
#define DEBUG_TYPE "code-extractor"
75
76
// Provide a command-line option to aggregate function arguments into a struct
77
// for functions produced by the code extractor. This is useful when converting
78
// extracted functions to pthread-based code, as only one argument (void*) can
79
// be passed in to pthread_create().
80
static cl::opt<bool>
81
AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
82
                 cl::desc("Aggregate arguments to code-extracted functions"));
83
84
/// Test whether a block is valid for extraction.
85
static bool isBlockValidForExtraction(const BasicBlock &BB,
86
                                      const SetVector<BasicBlock *> &Result,
87
328
                                      bool AllowVarArgs, bool AllowAlloca) {
88
328
  // taking the address of a basic block moved to another function is illegal
89
328
  if (BB.hasAddressTaken())
90
2
    return false;
91
326
92
326
  // don't hoist code that uses another basicblock address, as it's likely to
93
326
  // lead to unexpected behavior, like cross-function jumps
94
326
  SmallPtrSet<User const *, 16> Visited;
95
326
  SmallVector<User const *, 16> ToVisit;
96
326
97
326
  for (Instruction const &Inst : BB)
98
1.05k
    ToVisit.push_back(&Inst);
99
326
100
2.48k
  while (!ToVisit.empty()) {
101
2.15k
    User const *Curr = ToVisit.pop_back_val();
102
2.15k
    if (!Visited.insert(Curr).second)
103
539
      continue;
104
1.61k
    if (isa<BlockAddress const>(Curr))
105
0
      return false; // even a reference to self is likely to be not compatible
106
1.61k
107
1.61k
    if (isa<Instruction>(Curr) && 
cast<Instruction>(Curr)->getParent() != &BB1.15k
)
108
96
      continue;
109
1.52k
110
1.60k
    
for (auto const &U : Curr->operands())1.52k
{
111
1.60k
      if (auto *UU = dyn_cast<User>(U))
112
1.09k
        ToVisit.push_back(UU);
113
1.60k
    }
114
1.52k
  }
115
326
116
326
  // If explicitly requested, allow vastart and alloca. For invoke instructions
117
326
  // verify that extraction is valid.
118
1.38k
  
for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); 326
I != E;
++I1.05k
) {
119
1.05k
    if (isa<AllocaInst>(I)) {
120
0
       if (!AllowAlloca)
121
0
         return false;
122
0
       continue;
123
0
    }
124
1.05k
125
1.05k
    if (const auto *II = dyn_cast<InvokeInst>(I)) {
126
10
      // Unwind destination (either a landingpad, catchswitch, or cleanuppad)
127
10
      // must be a part of the subgraph which is being extracted.
128
10
      if (auto *UBB = II->getUnwindDest())
129
10
        if (!Result.count(UBB))
130
0
          return false;
131
10
      continue;
132
10
    }
133
1.04k
134
1.04k
    // All catch handlers of a catchswitch instruction as well as the unwind
135
1.04k
    // destination must be in the subgraph.
136
1.04k
    if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) {
137
2
      if (auto *UBB = CSI->getUnwindDest())
138
0
        if (!Result.count(UBB))
139
0
          return false;
140
2
      for (auto *HBB : CSI->handlers())
141
2
        if (!Result.count(const_cast<BasicBlock*>(HBB)))
142
0
          return false;
143
2
      continue;
144
1.04k
    }
145
1.04k
146
1.04k
    // Make sure that entire catch handler is within subgraph. It is sufficient
147
1.04k
    // to check that catch return's block is in the list.
148
1.04k
    if (const auto *CPI = dyn_cast<CatchPadInst>(I)) {
149
2
      for (const auto *U : CPI->users())
150
2
        if (const auto *CRI = dyn_cast<CatchReturnInst>(U))
151
2
          if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
152
0
            return false;
153
2
      continue;
154
1.04k
    }
155
1.04k
156
1.04k
    // And do similar checks for cleanup handler - the entire handler must be
157
1.04k
    // in subgraph which is going to be extracted. For cleanup return should
158
1.04k
    // additionally check that the unwind destination is also in the subgraph.
159
1.04k
    if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) {
160
2
      for (const auto *U : CPI->users())
161
2
        if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
162
2
          if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
163
0
            return false;
164
2
      continue;
165
1.04k
    }
166
1.04k
    if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) {
167
2
      if (auto *UBB = CRI->getUnwindDest())
168
2
        if (!Result.count(UBB))
169
0
          return false;
170
2
      continue;
171
2
    }
172
1.03k
173
1.03k
    if (const CallInst *CI = dyn_cast<CallInst>(I)) {
174
473
      if (const Function *F = CI->getCalledFunction()) {
175
472
        auto IID = F->getIntrinsicID();
176
472
        if (IID == Intrinsic::vastart) {
177
4
          if (AllowVarArgs)
178
4
            continue;
179
0
          else
180
0
            return false;
181
468
        }
182
468
183
468
        // Currently, we miscompile outlined copies of eh_typid_for. There are
184
468
        // proposals for fixing this in llvm.org/PR39545.
185
468
        if (IID == Intrinsic::eh_typeid_for)
186
1
          return false;
187
468
      }
188
473
    }
189
1.03k
  }
190
326
191
326
  
return true325
;
192
326
}
193
194
/// Build a set of blocks to extract if the input blocks are viable.
195
static SetVector<BasicBlock *>
196
buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
197
168
                        bool AllowVarArgs, bool AllowAlloca) {
198
168
  assert(!BBs.empty() && "The set of blocks to extract must be non-empty");
199
168
  SetVector<BasicBlock *> Result;
200
168
201
168
  // Loop over the blocks, adding them to our set-vector, and aborting with an
202
168
  // empty set if we encounter invalid blocks.
203
333
  for (BasicBlock *BB : BBs) {
204
333
    // If this block is dead, don't process it.
205
333
    if (DT && 
!DT->isReachableFromEntry(BB)304
)
206
1
      continue;
207
332
208
332
    if (!Result.insert(BB))
209
332
      
llvm_unreachable0
("Repeated basic blocks in extraction input");
210
332
  }
211
168
212
168
  LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName()
213
168
                    << '\n');
214
168
215
328
  for (auto *BB : Result) {
216
328
    if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca))
217
3
      return {};
218
325
219
325
    // Make sure that the first block is not a landing pad.
220
325
    if (BB == Result.front()) {
221
167
      if (BB->isEHPad()) {
222
0
        LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n");
223
0
        return {};
224
0
      }
225
167
      continue;
226
167
    }
227
158
228
158
    // All blocks other than the first must not have predecessors outside of
229
158
    // the subgraph which is being extracted.
230
158
    for (auto *PBB : predecessors(BB))
231
196
      if (!Result.count(PBB)) {
232
0
        LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from "
233
0
                             "outside the region except for the first block!\n"
234
0
                          << "Problematic source BB: " << BB->getName() << "\n"
235
0
                          << "Problematic destination BB: " << PBB->getName()
236
0
                          << "\n");
237
0
        return {};
238
0
      }
239
158
  }
240
168
241
168
  
return Result165
;
242
168
}
243
244
CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
245
                             bool AggregateArgs, BlockFrequencyInfo *BFI,
246
                             BranchProbabilityInfo *BPI, AssumptionCache *AC,
247
                             bool AllowVarArgs, bool AllowAlloca,
248
                             std::string Suffix)
249
    : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
250
      BPI(BPI), AC(AC), AllowVarArgs(AllowVarArgs),
251
      Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)),
252
159
      Suffix(Suffix) {}
253
254
CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs,
255
                             BlockFrequencyInfo *BFI,
256
                             BranchProbabilityInfo *BPI, AssumptionCache *AC,
257
                             std::string Suffix)
258
    : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
259
      BPI(BPI), AC(AC), AllowVarArgs(false),
260
      Blocks(buildExtractionBlockSet(L.getBlocks(), &DT,
261
                                     /* AllowVarArgs */ false,
262
                                     /* AllowAlloca */ false)),
263
9
      Suffix(Suffix) {}
264
265
/// definedInRegion - Return true if the specified value is defined in the
266
/// extracted region.
267
577
static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
268
577
  if (Instruction *I = dyn_cast<Instruction>(V))
269
577
    if (Blocks.count(I->getParent()))
270
339
      return true;
271
238
  return false;
272
238
}
273
274
/// definedInCaller - Return true if the specified value is defined in the
275
/// function being code extracted, but not in the region being extracted.
276
/// These values must be passed in as live-ins to the function.
277
1.90k
static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
278
1.90k
  if (isa<Argument>(V)) 
return true132
;
279
1.76k
  if (Instruction *I = dyn_cast<Instruction>(V))
280
378
    if (!Blocks.count(I->getParent()))
281
126
      return true;
282
1.64k
  return false;
283
1.64k
}
284
285
157
static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
286
157
  BasicBlock *CommonExitBlock = nullptr;
287
315
  auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
288
375
    for (auto *Succ : successors(Block)) {
289
375
      // Internal edges, ok.
290
375
      if (Blocks.count(Succ))
291
210
        continue;
292
165
      if (!CommonExitBlock) {
293
147
        CommonExitBlock = Succ;
294
147
        continue;
295
147
      }
296
18
      if (CommonExitBlock == Succ)
297
3
        continue;
298
15
299
15
      return true;
300
15
    }
301
315
    
return false300
;
302
315
  };
303
157
304
157
  if (any_of(Blocks, hasNonCommonExitSucc))
305
15
    return nullptr;
306
142
307
142
  return CommonExitBlock;
308
142
}
309
310
bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(
311
20
    Instruction *Addr) const {
312
20
  AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
313
20
  Function *Func = (*Blocks.begin())->getParent();
314
62
  for (BasicBlock &BB : *Func) {
315
62
    if (Blocks.count(&BB))
316
15
      continue;
317
165
    
for (Instruction &II : BB)47
{
318
165
      if (isa<DbgInfoIntrinsic>(II))
319
0
        continue;
320
165
321
165
      unsigned Opcode = II.getOpcode();
322
165
      Value *MemAddr = nullptr;
323
165
      switch (Opcode) {
324
165
      case Instruction::Store:
325
18
      case Instruction::Load: {
326
18
        if (Opcode == Instruction::Store) {
327
0
          StoreInst *SI = cast<StoreInst>(&II);
328
0
          MemAddr = SI->getPointerOperand();
329
18
        } else {
330
18
          LoadInst *LI = cast<LoadInst>(&II);
331
18
          MemAddr = LI->getPointerOperand();
332
18
        }
333
18
        // Global variable can not be aliased with locals.
334
18
        if (dyn_cast<Constant>(MemAddr))
335
14
          break;
336
4
        Value *Base = MemAddr->stripInBoundsConstantOffsets();
337
4
        if (!isa<AllocaInst>(Base) || 
Base == AI0
)
338
4
          return false;
339
0
        break;
340
0
      }
341
147
      default: {
342
147
        IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
343
147
        if (IntrInst) {
344
42
          if (IntrInst->isLifetimeStartOrEnd())
345
42
            break;
346
0
          return false;
347
0
        }
348
105
        // Treat all the other cases conservatively if it has side effects.
349
105
        if (II.mayHaveSideEffects())
350
5
          return false;
351
105
      }
352
165
      }
353
165
    }
354
47
  }
355
20
356
20
  
return true11
;
357
20
}
358
359
BasicBlock *
360
8
CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
361
8
  BasicBlock *SinglePredFromOutlineRegion = nullptr;
362
8
  assert(!Blocks.count(CommonExitBlock) &&
363
8
         "Expect a block outside the region!");
364
16
  for (auto *Pred : predecessors(CommonExitBlock)) {
365
16
    if (!Blocks.count(Pred))
366
6
      continue;
367
10
    if (!SinglePredFromOutlineRegion) {
368
8
      SinglePredFromOutlineRegion = Pred;
369
8
    } else 
if (2
SinglePredFromOutlineRegion != Pred2
) {
370
2
      SinglePredFromOutlineRegion = nullptr;
371
2
      break;
372
2
    }
373
10
  }
374
8
375
8
  if (SinglePredFromOutlineRegion)
376
6
    return SinglePredFromOutlineRegion;
377
2
378
#ifndef NDEBUG
379
  auto getFirstPHI = [](BasicBlock *BB) {
380
    BasicBlock::iterator I = BB->begin();
381
    PHINode *FirstPhi = nullptr;
382
    while (I != BB->end()) {
383
      PHINode *Phi = dyn_cast<PHINode>(I);
384
      if (!Phi)
385
        break;
386
      if (!FirstPhi) {
387
        FirstPhi = Phi;
388
        break;
389
      }
390
    }
391
    return FirstPhi;
392
  };
393
  // If there are any phi nodes, the single pred either exists or has already
394
  // be created before code extraction.
395
  assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
396
#endif
397
398
2
  BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
399
2
      CommonExitBlock->getFirstNonPHI()->getIterator());
400
2
401
2
  for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock);
402
10
       PI != PE;) {
403
8
    BasicBlock *Pred = *PI++;
404
8
    if (Blocks.count(Pred))
405
5
      continue;
406
3
    Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
407
3
  }
408
2
  // Now add the old exit block to the outline region.
409
2
  Blocks.insert(CommonExitBlock);
410
2
  return CommonExitBlock;
411
2
}
412
413
// Find the pair of life time markers for address 'Addr' that are either
414
// defined inside the outline region or can legally be shrinkwrapped into the
415
// outline region. If there are not other untracked uses of the address, return
416
// the pair of markers if found; otherwise return a pair of nullptr.
417
CodeExtractor::LifetimeMarkerInfo
418
CodeExtractor::getLifetimeMarkers(Instruction *Addr,
419
111
                                  BasicBlock *ExitBlock) const {
420
111
  LifetimeMarkerInfo Info;
421
111
422
179
  for (User *U : Addr->users()) {
423
179
    IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
424
179
    if (IntrInst) {
425
60
      if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
426
25
        // Do not handle the case where Addr has multiple start markers.
427
25
        if (Info.LifeStart)
428
0
          return {};
429
25
        Info.LifeStart = IntrInst;
430
25
      }
431
60
      if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
432
30
        if (Info.LifeEnd)
433
2
          return {};
434
28
        Info.LifeEnd = IntrInst;
435
28
      }
436
60
      
continue58
;
437
119
    }
438
119
    // Find untracked uses of the address, bail.
439
119
    if (!definedInRegion(Blocks, U))
440
73
      return {};
441
119
  }
442
111
443
111
  
if (36
!Info.LifeStart36
||
!Info.LifeEnd24
)
444
12
    return {};
445
24
446
24
  Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart);
447
24
  Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd);
448
24
  // Do legality check.
449
24
  if ((Info.SinkLifeStart || 
Info.HoistLifeEnd5
) &&
450
24
      
!isLegalToShrinkwrapLifetimeMarkers(Addr)20
)
451
9
    return {};
452
15
453
15
  // Check to see if we have a place to do hoisting, if not, bail.
454
15
  if (Info.HoistLifeEnd && 
!ExitBlock11
)
455
1
    return {};
456
14
457
14
  return Info;
458
14
}
459
460
void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
461
157
                                BasicBlock *&ExitBlock) const {
462
157
  Function *Func = (*Blocks.begin())->getParent();
463
157
  ExitBlock = getCommonExitBlock(Blocks);
464
157
465
157
  auto moveOrIgnoreLifetimeMarkers =
466
157
      [&](const LifetimeMarkerInfo &LMI) -> bool {
467
87
    if (!LMI.LifeStart)
468
73
      return false;
469
14
    if (LMI.SinkLifeStart) {
470
10
      LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart
471
10
                        << "\n");
472
10
      SinkCands.insert(LMI.LifeStart);
473
10
    }
474
14
    if (LMI.HoistLifeEnd) {
475
10
      LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n");
476
10
      HoistCands.insert(LMI.LifeEnd);
477
10
    }
478
14
    return true;
479
14
  };
480
157
481
1.03k
  for (BasicBlock &BB : *Func) {
482
1.03k
    if (Blocks.count(&BB))
483
323
      continue;
484
1.30k
    
for (Instruction &II : BB)715
{
485
1.30k
      auto *AI = dyn_cast<AllocaInst>(&II);
486
1.30k
      if (!AI)
487
1.22k
        continue;
488
75
489
75
      LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(AI, ExitBlock);
490
75
      bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);
491
75
      if (Moved) {
492
2
        LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n");
493
2
        SinkCands.insert(AI);
494
2
        continue;
495
2
      }
496
73
497
73
      // Follow any bitcasts.
498
73
      SmallVector<Instruction *, 2> Bitcasts;
499
73
      SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo;
500
102
      for (User *U : AI->users()) {
501
102
        if (U->stripInBoundsConstantOffsets() == AI) {
502
36
          Instruction *Bitcast = cast<Instruction>(U);
503
36
          LifetimeMarkerInfo LMI = getLifetimeMarkers(Bitcast, ExitBlock);
504
36
          if (LMI.LifeStart) {
505
12
            Bitcasts.push_back(Bitcast);
506
12
            BitcastLifetimeInfo.push_back(LMI);
507
12
            continue;
508
12
          }
509
90
        }
510
90
511
90
        // Found unknown use of AI.
512
90
        if (!definedInRegion(Blocks, U)) {
513
58
          Bitcasts.clear();
514
58
          break;
515
58
        }
516
90
      }
517
73
518
73
      // Either no bitcasts reference the alloca or there are unknown uses.
519
73
      if (Bitcasts.empty())
520
61
        continue;
521
12
522
12
      LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n");
523
12
      SinkCands.insert(AI);
524
24
      for (unsigned I = 0, E = Bitcasts.size(); I != E; 
++I12
) {
525
12
        Instruction *BitcastAddr = Bitcasts[I];
526
12
        const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I];
527
12
        assert(LMI.LifeStart &&
528
12
               "Unsafe to sink bitcast without lifetime markers");
529
12
        moveOrIgnoreLifetimeMarkers(LMI);
530
12
        if (!definedInRegion(Blocks, BitcastAddr)) {
531
12
          LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr
532
12
                            << "\n");
533
12
          SinkCands.insert(BitcastAddr);
534
12
        }
535
12
      }
536
12
    }
537
715
  }
538
157
}
539
540
void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
541
208
                                      const ValueSet &SinkCands) const {
542
424
  for (BasicBlock *BB : Blocks) {
543
424
    // If a used value is defined outside the region, it's an input.  If an
544
424
    // instruction is used outside the region, it's an output.
545
1.26k
    for (Instruction &II : *BB) {
546
3.19k
      for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE;
547
1.92k
           ++OI) {
548
1.92k
        Value *V = *OI;
549
1.92k
        if (!SinkCands.count(V) && 
definedInCaller(Blocks, V)1.90k
)
550
258
          Inputs.insert(V);
551
1.92k
      }
552
1.26k
553
1.26k
      for (User *U : II.users())
554
291
        if (!definedInRegion(Blocks, U)) {
555
39
          Outputs.insert(&II);
556
39
          break;
557
39
        }
558
1.26k
    }
559
424
  }
560
208
}
561
562
/// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside
563
/// of the region, we need to split the entry block of the region so that the
564
/// PHI node is easier to deal with.
565
157
void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {
566
157
  unsigned NumPredsFromRegion = 0;
567
157
  unsigned NumPredsOutsideRegion = 0;
568
157
569
157
  if (Header != &Header->getParent()->getEntryBlock()) {
570
153
    PHINode *PN = dyn_cast<PHINode>(Header->begin());
571
153
    if (!PN) 
return150
; // No PHI nodes.
572
3
573
3
    // If the header node contains any PHI nodes, check to see if there is more
574
3
    // than one entry from outside the region.  If so, we need to sever the
575
3
    // header block into two.
576
8
    
for (unsigned i = 0, e = PN->getNumIncomingValues(); 3
i != e;
++i5
)
577
5
      if (Blocks.count(PN->getIncomingBlock(i)))
578
0
        ++NumPredsFromRegion;
579
5
      else
580
5
        ++NumPredsOutsideRegion;
581
3
582
3
    // If there is one (or fewer) predecessor from outside the region, we don't
583
3
    // need to do anything special.
584
3
    if (NumPredsOutsideRegion <= 1) 
return1
;
585
6
  }
586
6
587
6
  // Otherwise, we need to split the header block into two pieces: one
588
6
  // containing PHI nodes merging values from outside of the region, and a
589
6
  // second that contains all of the code for the block and merges back any
590
6
  // incoming values from inside of the region.
591
6
  BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
592
6
593
6
  // We only want to code extract the second block now, and it becomes the new
594
6
  // header of the region.
595
6
  BasicBlock *OldPred = Header;
596
6
  Blocks.remove(OldPred);
597
6
  Blocks.insert(NewBB);
598
6
  Header = NewBB;
599
6
600
6
  // Okay, now we need to adjust the PHI nodes and any branches from within the
601
6
  // region to go to the new header block instead of the old header block.
602
6
  if (NumPredsFromRegion) {
603
0
    PHINode *PN = cast<PHINode>(OldPred->begin());
604
0
    // Loop over all of the predecessors of OldPred that are in the region,
605
0
    // changing them to branch to NewBB instead.
606
0
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
607
0
      if (Blocks.count(PN->getIncomingBlock(i))) {
608
0
        Instruction *TI = PN->getIncomingBlock(i)->getTerminator();
609
0
        TI->replaceUsesOfWith(OldPred, NewBB);
610
0
      }
611
0
612
0
    // Okay, everything within the region is now branching to the right block, we
613
0
    // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
614
0
    BasicBlock::iterator AfterPHIs;
615
0
    for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
616
0
      PHINode *PN = cast<PHINode>(AfterPHIs);
617
0
      // Create a new PHI node in the new region, which has an incoming value
618
0
      // from OldPred of PN.
619
0
      PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
620
0
                                       PN->getName() + ".ce", &NewBB->front());
621
0
      PN->replaceAllUsesWith(NewPN);
622
0
      NewPN->addIncoming(PN, OldPred);
623
0
624
0
      // Loop over all of the incoming value in PN, moving them to NewPN if they
625
0
      // are from the extracted region.
626
0
      for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
627
0
        if (Blocks.count(PN->getIncomingBlock(i))) {
628
0
          NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
629
0
          PN->removeIncomingValue(i);
630
0
          --i;
631
0
        }
632
0
      }
633
0
    }
634
0
  }
635
6
}
636
637
/// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
638
/// outlined region, we split these PHIs on two: one with inputs from region
639
/// and other with remaining incoming blocks; then first PHIs are placed in
640
/// outlined region.
641
void CodeExtractor::severSplitPHINodesOfExits(
642
157
    const SmallPtrSetImpl<BasicBlock *> &Exits) {
643
163
  for (BasicBlock *ExitBB : Exits) {
644
163
    BasicBlock *NewBB = nullptr;
645
163
646
163
    for (PHINode &PN : ExitBB->phis()) {
647
78
      // Find all incoming values from the outlining region.
648
78
      SmallVector<unsigned, 2> IncomingVals;
649
253
      for (unsigned i = 0; i < PN.getNumIncomingValues(); 
++i175
)
650
175
        if (Blocks.count(PN.getIncomingBlock(i)))
651
86
          IncomingVals.push_back(i);
652
78
653
78
      // Do not process PHI if there is one (or fewer) predecessor from region.
654
78
      // If PHI has exactly one predecessor from region, only this one incoming
655
78
      // will be replaced on codeRepl block, so it should be safe to skip PHI.
656
78
      if (IncomingVals.size() <= 1)
657
70
        continue;
658
8
659
8
      // Create block for new PHIs and add it to the list of outlined if it
660
8
      // wasn't done before.
661
8
      if (!NewBB) {
662
8
        NewBB = BasicBlock::Create(ExitBB->getContext(),
663
8
                                   ExitBB->getName() + ".split",
664
8
                                   ExitBB->getParent(), ExitBB);
665
8
        SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB),
666
8
                                           pred_end(ExitBB));
667
8
        for (BasicBlock *PredBB : Preds)
668
23
          if (Blocks.count(PredBB))
669
16
            PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
670
8
        BranchInst::Create(ExitBB, NewBB);
671
8
        Blocks.insert(NewBB);
672
8
      }
673
8
674
8
      // Split this PHI.
675
8
      PHINode *NewPN =
676
8
          PHINode::Create(PN.getType(), IncomingVals.size(),
677
8
                          PN.getName() + ".ce", NewBB->getFirstNonPHI());
678
8
      for (unsigned i : IncomingVals)
679
16
        NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));
680
8
      for (unsigned i : reverse(IncomingVals))
681
16
        PN.removeIncomingValue(i, false);
682
8
      PN.addIncoming(NewPN, NewBB);
683
8
    }
684
163
  }
685
157
}
686
687
157
void CodeExtractor::splitReturnBlocks() {
688
157
  for (BasicBlock *Block : Blocks)
689
315
    if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
690
16
      BasicBlock *New =
691
16
          Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
692
16
      if (DT) {
693
16
        // Old dominates New. New node dominates all other nodes dominated
694
16
        // by Old.
695
16
        DomTreeNode *OldNode = DT->getNode(Block);
696
16
        SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
697
16
                                               OldNode->end());
698
16
699
16
        DomTreeNode *NewNode = DT->addNewBlock(New, Block);
700
16
701
16
        for (DomTreeNode *I : Children)
702
0
          DT->changeImmediateDominator(I, NewNode);
703
16
      }
704
16
    }
705
157
}
706
707
/// constructFunction - make a function based on inputs and outputs, as follows:
708
/// f(in0, ..., inN, out0, ..., outN)
709
Function *CodeExtractor::constructFunction(const ValueSet &inputs,
710
                                           const ValueSet &outputs,
711
                                           BasicBlock *header,
712
                                           BasicBlock *newRootNode,
713
                                           BasicBlock *newHeader,
714
                                           Function *oldFunction,
715
157
                                           Module *M) {
716
157
  LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
717
157
  LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
718
157
719
157
  // This function returns unsigned, outputs will go back by reference.
720
157
  switch (NumExitBlocks) {
721
157
  case 0:
722
142
  case 1: RetTy = Type::getVoidTy(header->getContext()); break;
723
142
  
case 2: RetTy = Type::getInt1Ty(header->getContext()); break14
;
724
142
  
default: RetTy = Type::getInt16Ty(header->getContext()); break1
;
725
157
  }
726
157
727
157
  std::vector<Type *> paramTy;
728
157
729
157
  // Add the types of the input values to the function's argument list
730
157
  for (Value *value : inputs) {
731
126
    LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
732
126
    paramTy.push_back(value->getType());
733
126
  }
734
157
735
157
  // Add the types of the output values to the function's argument list.
736
157
  for (Value *output : outputs) {
737
38
    LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
738
38
    if (AggregateArgs)
739
0
      paramTy.push_back(output->getType());
740
38
    else
741
38
      paramTy.push_back(PointerType::getUnqual(output->getType()));
742
38
  }
743
157
744
157
  LLVM_DEBUG({
745
157
    dbgs() << "Function type: " << *RetTy << " f(";
746
157
    for (Type *i : paramTy)
747
157
      dbgs() << *i << ", ";
748
157
    dbgs() << ")\n";
749
157
  });
750
157
751
157
  StructType *StructTy;
752
157
  if (AggregateArgs && 
(inputs.size() + outputs.size() > 0)0
) {
753
0
    StructTy = StructType::get(M->getContext(), paramTy);
754
0
    paramTy.clear();
755
0
    paramTy.push_back(PointerType::getUnqual(StructTy));
756
0
  }
757
157
  FunctionType *funcType =
758
157
                  FunctionType::get(RetTy, paramTy,
759
157
                                    AllowVarArgs && 
oldFunction->isVarArg()88
);
760
157
761
157
  std::string SuffixToUse =
762
157
      Suffix.empty()
763
157
          ? 
(header->getName().empty() 117
?
"extracted"1
:
header->getName().str()116
)
764
157
          : 
Suffix40
;
765
157
  // Create the new function
766
157
  Function *newFunction = Function::Create(
767
157
      funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
768
157
      oldFunction->getName() + "." + SuffixToUse, M);
769
157
  // If the old function is no-throw, so is the new one.
770
157
  if (oldFunction->doesNotThrow())
771
46
    newFunction->setDoesNotThrow();
772
157
773
157
  // Inherit the uwtable attribute if we need to.
774
157
  if (oldFunction->hasUWTable())
775
19
    newFunction->setHasUWTable();
776
157
777
157
  // Inherit all of the target dependent attributes and white-listed
778
157
  // target independent attributes.
779
157
  //  (e.g. If the extracted region contains a call to an x86.sse
780
157
  //  instruction we need to make sure that the extracted region has the
781
157
  //  "target-features" attribute allowing it to be lowered.
782
157
  // FIXME: This should be changed to check to see if a specific
783
157
  //           attribute can not be inherited.
784
157
  for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) {
785
102
    if (Attr.isStringAttribute()) {
786
9
      if (Attr.getKindAsString() == "thunk")
787
1
        continue;
788
93
    } else
789
93
      switch (Attr.getKindAsEnum()) {
790
93
      // Those attributes cannot be propagated safely. Explicitly list them
791
93
      // here so we get a warning if new attributes are added. This list also
792
93
      // includes non-function attributes.
793
93
      case Attribute::Alignment:
794
11
      case Attribute::AllocSize:
795
11
      case Attribute::ArgMemOnly:
796
11
      case Attribute::Builtin:
797
11
      case Attribute::ByVal:
798
11
      case Attribute::Convergent:
799
11
      case Attribute::Dereferenceable:
800
11
      case Attribute::DereferenceableOrNull:
801
11
      case Attribute::InAlloca:
802
11
      case Attribute::InReg:
803
11
      case Attribute::InaccessibleMemOnly:
804
11
      case Attribute::InaccessibleMemOrArgMemOnly:
805
11
      case Attribute::JumpTable:
806
11
      case Attribute::Naked:
807
11
      case Attribute::Nest:
808
11
      case Attribute::NoAlias:
809
11
      case Attribute::NoBuiltin:
810
11
      case Attribute::NoCapture:
811
11
      case Attribute::NoReturn:
812
11
      case Attribute::NoSync:
813
11
      case Attribute::None:
814
11
      case Attribute::NonNull:
815
11
      case Attribute::ReadNone:
816
11
      case Attribute::ReadOnly:
817
11
      case Attribute::Returned:
818
11
      case Attribute::ReturnsTwice:
819
11
      case Attribute::SExt:
820
11
      case Attribute::Speculatable:
821
11
      case Attribute::StackAlignment:
822
11
      case Attribute::StructRet:
823
11
      case Attribute::SwiftError:
824
11
      case Attribute::SwiftSelf:
825
11
      case Attribute::WillReturn:
826
11
      case Attribute::WriteOnly:
827
11
      case Attribute::ZExt:
828
11
      case Attribute::ImmArg:
829
11
      case Attribute::EndAttrKinds:
830
11
        continue;
831
11
      // Those attributes should be safe to propagate to the extracted function.
832
82
      case Attribute::AlwaysInline:
833
82
      case Attribute::Cold:
834
82
      case Attribute::NoRecurse:
835
82
      case Attribute::InlineHint:
836
82
      case Attribute::MinSize:
837
82
      case Attribute::NoDuplicate:
838
82
      case Attribute::NoFree:
839
82
      case Attribute::NoImplicitFloat:
840
82
      case Attribute::NoInline:
841
82
      case Attribute::NonLazyBind:
842
82
      case Attribute::NoRedZone:
843
82
      case Attribute::NoUnwind:
844
82
      case Attribute::OptForFuzzing:
845
82
      case Attribute::OptimizeNone:
846
82
      case Attribute::OptimizeForSize:
847
82
      case Attribute::SafeStack:
848
82
      case Attribute::ShadowCallStack:
849
82
      case Attribute::SanitizeAddress:
850
82
      case Attribute::SanitizeMemory:
851
82
      case Attribute::SanitizeThread:
852
82
      case Attribute::SanitizeHWAddress:
853
82
      case Attribute::SanitizeMemTag:
854
82
      case Attribute::SpeculativeLoadHardening:
855
82
      case Attribute::StackProtect:
856
82
      case Attribute::StackProtectReq:
857
82
      case Attribute::StackProtectStrong:
858
82
      case Attribute::StrictFP:
859
82
      case Attribute::UWTable:
860
82
      case Attribute::NoCfCheck:
861
82
        break;
862
90
      }
863
90
864
90
    newFunction->addFnAttr(Attr);
865
90
  }
866
157
  newFunction->getBasicBlockList().push_back(newRootNode);
867
157
868
157
  // Create an iterator to name all of the arguments we inserted.
869
157
  Function::arg_iterator AI = newFunction->arg_begin();
870
157
871
157
  // Rewrite all users of the inputs in the extracted region to use the
872
157
  // arguments (or appropriate addressing into struct) instead.
873
283
  for (unsigned i = 0, e = inputs.size(); i != e; 
++i126
) {
874
126
    Value *RewriteVal;
875
126
    if (AggregateArgs) {
876
0
      Value *Idx[2];
877
0
      Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
878
0
      Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
879
0
      Instruction *TI = newFunction->begin()->getTerminator();
880
0
      GetElementPtrInst *GEP = GetElementPtrInst::Create(
881
0
          StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
882
0
      RewriteVal = new LoadInst(StructTy->getElementType(i), GEP,
883
0
                                "loadgep_" + inputs[i]->getName(), TI);
884
0
    } else
885
126
      RewriteVal = &*AI++;
886
126
887
126
    std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
888
126
    for (User *use : Users)
889
440
      if (Instruction *inst = dyn_cast<Instruction>(use))
890
440
        if (Blocks.count(inst->getParent()))
891
191
          inst->replaceUsesOfWith(inputs[i], RewriteVal);
892
126
  }
893
157
894
157
  // Set names for input and output arguments.
895
157
  if (!AggregateArgs) {
896
157
    AI = newFunction->arg_begin();
897
283
    for (unsigned i = 0, e = inputs.size(); i != e; 
++i, ++AI126
)
898
126
      AI->setName(inputs[i]->getName());
899
195
    for (unsigned i = 0, e = outputs.size(); i != e; 
++i, ++AI38
)
900
38
      AI->setName(outputs[i]->getName()+".out");
901
157
  }
902
157
903
157
  // Rewrite branches to basic blocks outside of the loop to new dummy blocks
904
157
  // within the new function. This must be done before we lose track of which
905
157
  // blocks were originally in the code region.
906
157
  std::vector<User *> Users(header->user_begin(), header->user_end());
907
489
  for (unsigned i = 0, e = Users.size(); i != e; 
++i332
)
908
332
    // The BasicBlock which contains the branch is not in the region
909
332
    // modify the branch target to a new block
910
332
    if (Instruction *I = dyn_cast<Instruction>(Users[i]))
911
332
      if (I->isTerminator() && !Blocks.count(I->getParent()) &&
912
332
          
I->getParent()->getParent() == oldFunction323
)
913
166
        I->replaceUsesOfWith(header, newHeader);
914
157
915
157
  return newFunction;
916
157
}
917
918
/// Erase lifetime.start markers which reference inputs to the extraction
919
/// region, and insert the referenced memory into \p LifetimesStart.
920
///
921
/// The extraction region is defined by a set of blocks (\p Blocks), and a set
922
/// of allocas which will be moved from the caller function into the extracted
923
/// function (\p SunkAllocas).
924
static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks,
925
                                         const SetVector<Value *> &SunkAllocas,
926
157
                                         SetVector<Value *> &LifetimesStart) {
927
325
  for (BasicBlock *BB : Blocks) {
928
1.36k
    for (auto It = BB->begin(), End = BB->end(); It != End;) {
929
1.03k
      auto *II = dyn_cast<IntrinsicInst>(&*It);
930
1.03k
      ++It;
931
1.03k
      if (!II || 
!II->isLifetimeStartOrEnd()44
)
932
1.00k
        continue;
933
35
934
35
      // Get the memory operand of the lifetime marker. If the underlying
935
35
      // object is a sunk alloca, or is otherwise defined in the extraction
936
35
      // region, the lifetime marker must not be erased.
937
35
      Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
938
35
      if (SunkAllocas.count(Mem) || 
definedInRegion(Blocks, Mem)17
)
939
18
        continue;
940
17
941
17
      if (II->getIntrinsicID() == Intrinsic::lifetime_start)
942
8
        LifetimesStart.insert(Mem);
943
17
      II->eraseFromParent();
944
17
    }
945
325
  }
946
157
}
947
948
/// Insert lifetime start/end markers surrounding the call to the new function
949
/// for objects defined in the caller.
950
static void insertLifetimeMarkersSurroundingCall(
951
    Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
952
314
    CallInst *TheCall) {
953
314
  LLVMContext &Ctx = M->getContext();
954
314
  auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
955
314
  auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
956
314
  Instruction *Term = TheCall->getParent()->getTerminator();
957
314
958
314
  // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
959
314
  // needed to satisfy this requirement so they may be reused.
960
314
  DenseMap<Value *, Value *> Bitcasts;
961
314
962
314
  // Emit lifetime markers for the pointers given in \p Objects. Insert the
963
314
  // markers before the call if \p InsertBefore, and after the call otherwise.
964
314
  auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
965
314
                           bool InsertBefore) {
966
83
    for (Value *Mem : Objects) {
967
83
      assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
968
83
                                            TheCall->getFunction()) &&
969
83
             "Input memory not defined in original function");
970
83
      Value *&MemAsI8Ptr = Bitcasts[Mem];
971
83
      if (!MemAsI8Ptr) {
972
45
        if (Mem->getType() == Int8PtrTy)
973
2
          MemAsI8Ptr = Mem;
974
43
        else
975
43
          MemAsI8Ptr =
976
43
              CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
977
45
      }
978
83
979
83
      auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
980
83
      if (InsertBefore)
981
45
        Marker->insertBefore(TheCall);
982
38
      else
983
38
        Marker->insertBefore(Term);
984
83
    }
985
82
  };
986
314
987
314
  if (!LifetimesStart.empty()) {
988
44
    auto StartFn = llvm::Intrinsic::getDeclaration(
989
44
        M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
990
44
    insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
991
44
  }
992
314
993
314
  if (!LifetimesEnd.empty()) {
994
38
    auto EndFn = llvm::Intrinsic::getDeclaration(
995
38
        M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
996
38
    insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
997
38
  }
998
314
}
999
1000
/// emitCallAndSwitchStatement - This method sets up the caller side by adding
1001
/// the call instruction, splitting any PHI nodes in the header block as
1002
/// necessary.
1003
CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1004
                                                    BasicBlock *codeReplacer,
1005
                                                    ValueSet &inputs,
1006
157
                                                    ValueSet &outputs) {
1007
157
  // Emit a call to the new function, passing in: *pointer to struct (if
1008
157
  // aggregating parameters), or plan inputs and allocated memory for outputs
1009
157
  std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
1010
157
1011
157
  Module *M = newFunction->getParent();
1012
157
  LLVMContext &Context = M->getContext();
1013
157
  const DataLayout &DL = M->getDataLayout();
1014
157
  CallInst *call = nullptr;
1015
157
1016
157
  // Add inputs as params, or to be filled into the struct
1017
157
  unsigned ArgNo = 0;
1018
157
  SmallVector<unsigned, 1> SwiftErrorArgs;
1019
157
  for (Value *input : inputs) {
1020
126
    if (AggregateArgs)
1021
0
      StructValues.push_back(input);
1022
126
    else {
1023
126
      params.push_back(input);
1024
126
      if (input->isSwiftError())
1025
2
        SwiftErrorArgs.push_back(ArgNo);
1026
126
    }
1027
126
    ++ArgNo;
1028
126
  }
1029
157
1030
157
  // Create allocas for the outputs
1031
157
  for (Value *output : outputs) {
1032
38
    if (AggregateArgs) {
1033
0
      StructValues.push_back(output);
1034
38
    } else {
1035
38
      AllocaInst *alloca =
1036
38
        new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1037
38
                       nullptr, output->getName() + ".loc",
1038
38
                       &codeReplacer->getParent()->front().front());
1039
38
      ReloadOutputs.push_back(alloca);
1040
38
      params.push_back(alloca);
1041
38
    }
1042
38
  }
1043
157
1044
157
  StructType *StructArgTy = nullptr;
1045
157
  AllocaInst *Struct = nullptr;
1046
157
  if (AggregateArgs && 
(inputs.size() + outputs.size() > 0)0
) {
1047
0
    std::vector<Type *> ArgTypes;
1048
0
    for (ValueSet::iterator v = StructValues.begin(),
1049
0
           ve = StructValues.end(); v != ve; ++v)
1050
0
      ArgTypes.push_back((*v)->getType());
1051
0
1052
0
    // Allocate a struct at the beginning of this function
1053
0
    StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1054
0
    Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
1055
0
                            "structArg",
1056
0
                            &codeReplacer->getParent()->front().front());
1057
0
    params.push_back(Struct);
1058
0
1059
0
    for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
1060
0
      Value *Idx[2];
1061
0
      Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1062
0
      Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
1063
0
      GetElementPtrInst *GEP = GetElementPtrInst::Create(
1064
0
          StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1065
0
      codeReplacer->getInstList().push_back(GEP);
1066
0
      StoreInst *SI = new StoreInst(StructValues[i], GEP);
1067
0
      codeReplacer->getInstList().push_back(SI);
1068
0
    }
1069
0
  }
1070
157
1071
157
  // Emit the call to the function
1072
157
  call = CallInst::Create(newFunction, params,
1073
157
                          NumExitBlocks > 1 ? 
"targetBlock"15
:
""142
);
1074
157
  // Add debug location to the new call, if the original function has debug
1075
157
  // info. In that case, the terminator of the entry block of the extracted
1076
157
  // function contains the first debug location of the extracted function,
1077
157
  // set in extractCodeRegion.
1078
157
  if (codeReplacer->getParent()->getSubprogram()) {
1079
13
    if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1080
13
      call->setDebugLoc(DL);
1081
13
  }
1082
157
  codeReplacer->getInstList().push_back(call);
1083
157
1084
157
  // Set swifterror parameter attributes.
1085
157
  for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1086
2
    call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1087
2
    newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1088
2
  }
1089
157
1090
157
  Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
1091
157
  unsigned FirstOut = inputs.size();
1092
157
  if (!AggregateArgs)
1093
157
    std::advance(OutputArgBegin, inputs.size());
1094
157
1095
157
  // Reload the outputs passed in by reference.
1096
195
  for (unsigned i = 0, e = outputs.size(); i != e; 
++i38
) {
1097
38
    Value *Output = nullptr;
1098
38
    if (AggregateArgs) {
1099
0
      Value *Idx[2];
1100
0
      Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1101
0
      Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1102
0
      GetElementPtrInst *GEP = GetElementPtrInst::Create(
1103
0
          StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1104
0
      codeReplacer->getInstList().push_back(GEP);
1105
0
      Output = GEP;
1106
38
    } else {
1107
38
      Output = ReloadOutputs[i];
1108
38
    }
1109
38
    LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1110
38
                                  outputs[i]->getName() + ".reload");
1111
38
    Reloads.push_back(load);
1112
38
    codeReplacer->getInstList().push_back(load);
1113
38
    std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1114
76
    for (unsigned u = 0, e = Users.size(); u != e; 
++u38
) {
1115
38
      Instruction *inst = cast<Instruction>(Users[u]);
1116
38
      if (!Blocks.count(inst->getParent()))
1117
38
        inst->replaceUsesOfWith(outputs[i], load);
1118
38
    }
1119
38
  }
1120
157
1121
157
  // Now we can emit a switch statement using the call as a value.
1122
157
  SwitchInst *TheSwitch =
1123
157
      SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
1124
157
                         codeReplacer, 0, codeReplacer);
1125
157
1126
157
  // Since there may be multiple exits from the original region, make the new
1127
157
  // function return an unsigned, switch on that number.  This loop iterates
1128
157
  // over all of the blocks in the extracted region, updating any terminator
1129
157
  // instructions in the to-be-extracted region that branch to blocks that are
1130
157
  // not in the region to be extracted.
1131
157
  std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1132
157
1133
157
  unsigned switchVal = 0;
1134
325
  for (BasicBlock *Block : Blocks) {
1135
325
    Instruction *TI = Block->getTerminator();
1136
714
    for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; 
++i389
)
1137
389
      if (!Blocks.count(TI->getSuccessor(i))) {
1138
163
        BasicBlock *OldTarget = TI->getSuccessor(i);
1139
163
        // add a new basic block which returns the appropriate value
1140
163
        BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1141
163
        if (!NewTarget) {
1142
163
          // If we don't already have an exit stub for this non-extracted
1143
163
          // destination, create one now!
1144
163
          NewTarget = BasicBlock::Create(Context,
1145
163
                                         OldTarget->getName() + ".exitStub",
1146
163
                                         newFunction);
1147
163
          unsigned SuccNum = switchVal++;
1148
163
1149
163
          Value *brVal = nullptr;
1150
163
          switch (NumExitBlocks) {
1151
163
          case 0:
1152
132
          case 1: break;  // No value needed.
1153
132
          case 2:         // Conditional branch, return a bool
1154
28
            brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1155
28
            break;
1156
132
          default:
1157
3
            brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1158
3
            break;
1159
163
          }
1160
163
1161
163
          ReturnInst::Create(Context, brVal, NewTarget);
1162
163
1163
163
          // Update the switch instruction.
1164
163
          TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
1165
163
                                              SuccNum),
1166
163
                             OldTarget);
1167
163
        }
1168
163
1169
163
        // rewrite the original branch instruction with this new target
1170
163
        TI->setSuccessor(i, NewTarget);
1171
163
      }
1172
325
  }
1173
157
1174
157
  // Store the arguments right after the definition of output value.
1175
157
  // This should be proceeded after creating exit stubs to be ensure that invoke
1176
157
  // result restore will be placed in the outlined function.
1177
157
  Function::arg_iterator OAI = OutputArgBegin;
1178
195
  for (unsigned i = 0, e = outputs.size(); i != e; 
++i38
) {
1179
38
    auto *OutI = dyn_cast<Instruction>(outputs[i]);
1180
38
    if (!OutI)
1181
0
      continue;
1182
38
1183
38
    // Find proper insertion point.
1184
38
    BasicBlock::iterator InsertPt;
1185
38
    // In case OutI is an invoke, we insert the store at the beginning in the
1186
38
    // 'normal destination' BB. Otherwise we insert the store right after OutI.
1187
38
    if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1188
2
      InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1189
36
    else if (auto *Phi = dyn_cast<PHINode>(OutI))
1190
21
      InsertPt = Phi->getParent()->getFirstInsertionPt();
1191
15
    else
1192
15
      InsertPt = std::next(OutI->getIterator());
1193
38
1194
38
    Instruction *InsertBefore = &*InsertPt;
1195
38
    assert((InsertBefore->getFunction() == newFunction ||
1196
38
            Blocks.count(InsertBefore->getParent())) &&
1197
38
           "InsertPt should be in new function");
1198
38
    assert(OAI != newFunction->arg_end() &&
1199
38
           "Number of output arguments should match "
1200
38
           "the amount of defined values");
1201
38
    if (AggregateArgs) {
1202
0
      Value *Idx[2];
1203
0
      Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1204
0
      Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1205
0
      GetElementPtrInst *GEP = GetElementPtrInst::Create(
1206
0
          StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(),
1207
0
          InsertBefore);
1208
0
      new StoreInst(outputs[i], GEP, InsertBefore);
1209
0
      // Since there should be only one struct argument aggregating
1210
0
      // all the output values, we shouldn't increment OAI, which always
1211
0
      // points to the struct argument, in this case.
1212
38
    } else {
1213
38
      new StoreInst(outputs[i], &*OAI, InsertBefore);
1214
38
      ++OAI;
1215
38
    }
1216
38
  }
1217
157
1218
157
  // Now that we've done the deed, simplify the switch instruction.
1219
157
  Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1220
157
  switch (NumExitBlocks) {
1221
157
  case 0:
1222
10
    // There are no successors (the block containing the switch itself), which
1223
10
    // means that previously this was the last part of the function, and hence
1224
10
    // this should be rewritten as a `ret'
1225
10
1226
10
    // Check if the function should return a value
1227
10
    if (OldFnRetTy->isVoidTy()) {
1228
8
      ReturnInst::Create(Context, nullptr, TheSwitch);  // Return void
1229
8
    } else 
if (2
OldFnRetTy == TheSwitch->getCondition()->getType()2
) {
1230
0
      // return what we have
1231
0
      ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1232
2
    } else {
1233
2
      // Otherwise we must have code extracted an unwind or something, just
1234
2
      // return whatever we want.
1235
2
      ReturnInst::Create(Context,
1236
2
                         Constant::getNullValue(OldFnRetTy), TheSwitch);
1237
2
    }
1238
10
1239
10
    TheSwitch->eraseFromParent();
1240
10
    break;
1241
157
  case 1:
1242
132
    // Only a single destination, change the switch into an unconditional
1243
132
    // branch.
1244
132
    BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1245
132
    TheSwitch->eraseFromParent();
1246
132
    break;
1247
157
  case 2:
1248
14
    BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1249
14
                       call, TheSwitch);
1250
14
    TheSwitch->eraseFromParent();
1251
14
    break;
1252
157
  default:
1253
1
    // Otherwise, make the default destination of the switch instruction be one
1254
1
    // of the other successors.
1255
1
    TheSwitch->setCondition(call);
1256
1
    TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1257
1
    // Remove redundant case
1258
1
    TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1259
1
    break;
1260
157
  }
1261
157
1262
157
  // Insert lifetime markers around the reloads of any output values. The
1263
157
  // allocas output values are stored in are only in-use in the codeRepl block.
1264
157
  insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1265
157
1266
157
  return call;
1267
157
}
1268
1269
157
void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1270
157
  Function *oldFunc = (*Blocks.begin())->getParent();
1271
157
  Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1272
157
  Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1273
157
1274
325
  for (BasicBlock *Block : Blocks) {
1275
325
    // Delete the basic block from the old function, and the list of blocks
1276
325
    oldBlocks.remove(Block);
1277
325
1278
325
    // Insert this basic block into the new function
1279
325
    newBlocks.push_back(Block);
1280
325
1281
325
    // Remove @llvm.assume calls that were moved to the new function from the
1282
325
    // old function's assumption cache.
1283
325
    if (AC)
1284
33
      for (auto &I : *Block)
1285
39
        if (match(&I, m_Intrinsic<Intrinsic::assume>()))
1286
1
          AC->unregisterAssumption(cast<CallInst>(&I));
1287
325
  }
1288
157
}
1289
1290
void CodeExtractor::calculateNewCallTerminatorWeights(
1291
    BasicBlock *CodeReplacer,
1292
    DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
1293
3
    BranchProbabilityInfo *BPI) {
1294
3
  using Distribution = BlockFrequencyInfoImplBase::Distribution;
1295
3
  using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1296
3
1297
3
  // Update the branch weights for the exit block.
1298
3
  Instruction *TI = CodeReplacer->getTerminator();
1299
3
  SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1300
3
1301
3
  // Block Frequency distribution with dummy node.
1302
3
  Distribution BranchDist;
1303
3
1304
3
  // Add each of the frequencies of the successors.
1305
9
  for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; 
++i6
) {
1306
6
    BlockNode ExitNode(i);
1307
6
    uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1308
6
    if (ExitFreq != 0)
1309
6
      BranchDist.addExit(ExitNode, ExitFreq);
1310
0
    else
1311
0
      BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero());
1312
6
  }
1313
3
1314
3
  // Check for no total weight.
1315
3
  if (BranchDist.Total == 0)
1316
0
    return;
1317
3
1318
3
  // Normalize the distribution so that they can fit in unsigned.
1319
3
  BranchDist.normalize();
1320
3
1321
3
  // Create normalized branch weights and set the metadata.
1322
9
  for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; 
++I6
) {
1323
6
    const auto &Weight = BranchDist.Weights[I];
1324
6
1325
6
    // Get the weight and update the current BFI.
1326
6
    BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1327
6
    BranchProbability BP(Weight.Amount, BranchDist.Total);
1328
6
    BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP);
1329
6
  }
1330
3
  TI->setMetadata(
1331
3
      LLVMContext::MD_prof,
1332
3
      MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1333
3
}
1334
1335
164
Function *CodeExtractor::extractCodeRegion() {
1336
164
  if (!isEligible())
1337
3
    return nullptr;
1338
161
1339
161
  // Assumption: this is a single-entry code region, and the header is the first
1340
161
  // block in the region.
1341
161
  BasicBlock *header = *Blocks.begin();
1342
161
  Function *oldFunction = header->getParent();
1343
161
1344
161
  // For functions with varargs, check that varargs handling is only done in the
1345
161
  // outlined function, i.e vastart and vaend are only used in outlined blocks.
1346
161
  if (AllowVarArgs && 
oldFunction->getFunctionType()->isVarArg()92
) {
1347
43
    auto containsVarArgIntrinsic = [](Instruction &I) {
1348
43
      if (const CallInst *CI = dyn_cast<CallInst>(&I))
1349
4
        if (const Function *F = CI->getCalledFunction())
1350
4
          return F->getIntrinsicID() == Intrinsic::vastart ||
1351
4
                 
F->getIntrinsicID() == Intrinsic::vaend2
;
1352
39
      return false;
1353
39
    };
1354
9
1355
23
    for (auto &BB : *oldFunction) {
1356
23
      if (Blocks.count(&BB))
1357
7
        continue;
1358
16
      if (llvm::any_of(BB, containsVarArgIntrinsic))
1359
4
        return nullptr;
1360
16
    }
1361
9
  }
1362
161
  ValueSet inputs, outputs, SinkingCands, HoistingCands;
1363
157
  BasicBlock *CommonExit = nullptr;
1364
157
1365
157
  // Calculate the entry frequency of the new function before we change the root
1366
157
  //   block.
1367
157
  BlockFrequency EntryFreq;
1368
157
  if (BFI) {
1369
94
    assert(BPI && "Both BPI and BFI are required to preserve profile info");
1370
103
    for (BasicBlock *Pred : predecessors(header)) {
1371
103
      if (Blocks.count(Pred))
1372
1
        continue;
1373
102
      EntryFreq +=
1374
102
          BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1375
102
    }
1376
94
  }
1377
157
1378
157
  // If we have any return instructions in the region, split those blocks so
1379
157
  // that the return is not in the region.
1380
157
  splitReturnBlocks();
1381
157
1382
157
  // Calculate the exit blocks for the extracted region and the total exit
1383
157
  // weights for each of those blocks.
1384
157
  DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
1385
157
  SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1386
315
  for (BasicBlock *Block : Blocks) {
1387
694
    for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
1388
379
         ++SI) {
1389
379
      if (!Blocks.count(*SI)) {
1390
174
        // Update the branch weight for this successor.
1391
174
        if (BFI) {
1392
98
          BlockFrequency &BF = ExitWeights[*SI];
1393
98
          BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
1394
98
        }
1395
174
        ExitBlocks.insert(*SI);
1396
174
      }
1397
379
    }
1398
315
  }
1399
157
  NumExitBlocks = ExitBlocks.size();
1400
157
1401
157
  // If we have to split PHI nodes of the entry or exit blocks, do so now.
1402
157
  severSplitPHINodesOfEntry(header);
1403
157
  severSplitPHINodesOfExits(ExitBlocks);
1404
157
1405
157
  // This takes place of the original loop
1406
157
  BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1407
157
                                                "codeRepl", oldFunction,
1408
157
                                                header);
1409
157
1410
157
  // The new function needs a root node because other nodes can branch to the
1411
157
  // head of the region, but the entry node of a function cannot have preds.
1412
157
  BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1413
157
                                               "newFuncRoot");
1414
157
  auto *BranchI = BranchInst::Create(header);
1415
157
  // If the original function has debug info, we have to add a debug location
1416
157
  // to the new branch instruction from the artificial entry block.
1417
157
  // We use the debug location of the first instruction in the extracted
1418
157
  // blocks, as there is no other equivalent line in the source code.
1419
157
  if (oldFunction->getSubprogram()) {
1420
14
    any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1421
14
      return any_of(*BB, [&BranchI](const Instruction &I) {
1422
14
        if (!I.getDebugLoc())
1423
1
          return false;
1424
13
        BranchI->setDebugLoc(I.getDebugLoc());
1425
13
        return true;
1426
13
      });
1427
14
    });
1428
13
  }
1429
157
  newFuncRoot->getInstList().push_back(BranchI);
1430
157
1431
157
  findAllocas(SinkingCands, HoistingCands, CommonExit);
1432
157
  assert(HoistingCands.empty() || CommonExit);
1433
157
1434
157
  // Find inputs to, outputs from the code region.
1435
157
  findInputsOutputs(inputs, outputs, SinkingCands);
1436
157
1437
157
  // Now sink all instructions which only have non-phi uses inside the region.
1438
157
  // Group the allocas at the start of the block, so that any bitcast uses of
1439
157
  // the allocas are well-defined.
1440
157
  AllocaInst *FirstSunkAlloca = nullptr;
1441
157
  for (auto *II : SinkingCands) {
1442
36
    if (auto *AI = dyn_cast<AllocaInst>(II)) {
1443
14
      AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1444
14
      if (!FirstSunkAlloca)
1445
12
        FirstSunkAlloca = AI;
1446
14
    }
1447
36
  }
1448
157
  assert((SinkingCands.empty() || FirstSunkAlloca) &&
1449
157
         "Did not expect a sink candidate without any allocas");
1450
157
  for (auto *II : SinkingCands) {
1451
36
    if (!isa<AllocaInst>(II)) {
1452
22
      cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1453
22
    }
1454
36
  }
1455
157
1456
157
  if (!HoistingCands.empty()) {
1457
8
    auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1458
8
    Instruction *TI = HoistToBlock->getTerminator();
1459
8
    for (auto *II : HoistingCands)
1460
10
      cast<Instruction>(II)->moveBefore(TI);
1461
8
  }
1462
157
1463
157
  // Collect objects which are inputs to the extraction region and also
1464
157
  // referenced by lifetime start markers within it. The effects of these
1465
157
  // markers must be replicated in the calling function to prevent the stack
1466
157
  // coloring pass from merging slots which store input objects.
1467
157
  ValueSet LifetimesStart;
1468
157
  eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1469
157
1470
157
  // Construct new function based on inputs/outputs & add allocas for all defs.
1471
157
  Function *newFunction =
1472
157
      constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1473
157
                        oldFunction, oldFunction->getParent());
1474
157
1475
157
  // Update the entry count of the function.
1476
157
  if (BFI) {
1477
94
    auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1478
94
    if (Count.hasValue())
1479
11
      newFunction->setEntryCount(
1480
11
          ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1481
94
    BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1482
94
  }
1483
157
1484
157
  CallInst *TheCall =
1485
157
      emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1486
157
1487
157
  moveCodeToFunction(newFunction);
1488
157
1489
157
  // Replicate the effects of any lifetime start/end markers which referenced
1490
157
  // input objects in the extraction region by placing markers around the call.
1491
157
  insertLifetimeMarkersSurroundingCall(
1492
157
      oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1493
157
1494
157
  // Propagate personality info to the new function if there is one.
1495
157
  if (oldFunction->hasPersonalityFn())
1496
15
    newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1497
157
1498
157
  // Update the branch weights for the exit block.
1499
157
  if (BFI && 
NumExitBlocks > 194
)
1500
3
    calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1501
157
1502
157
  // Loop over all of the PHI nodes in the header and exit blocks, and change
1503
157
  // any references to the old incoming edge to be the new incoming edge.
1504
158
  for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); 
++I1
) {
1505
1
    PHINode *PN = cast<PHINode>(I);
1506
2
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; 
++i1
)
1507
1
      if (!Blocks.count(PN->getIncomingBlock(i)))
1508
1
        PN->setIncomingBlock(i, newFuncRoot);
1509
1
  }
1510
157
1511
157
  for (BasicBlock *ExitBB : ExitBlocks)
1512
163
    for (PHINode &PN : ExitBB->phis()) {
1513
78
      Value *IncomingCodeReplacerVal = nullptr;
1514
245
      for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; 
++i167
) {
1515
167
        // Ignore incoming values from outside of the extracted region.
1516
167
        if (!Blocks.count(PN.getIncomingBlock(i)))
1517
89
          continue;
1518
78
1519
78
        // Ensure that there is only one incoming value from codeReplacer.
1520
78
        if (!IncomingCodeReplacerVal) {
1521
78
          PN.setIncomingBlock(i, codeReplacer);
1522
78
          IncomingCodeReplacerVal = PN.getIncomingValue(i);
1523
78
        } else
1524
78
          assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1525
78
                 "PHI has two incompatbile incoming values from codeRepl");
1526
78
      }
1527
78
    }
1528
157
1529
157
  // Erase debug info intrinsics. Variable updates within the new function are
1530
157
  // invisible to debuggers. This could be improved by defining a DISubprogram
1531
157
  // for the new function.
1532
645
  for (BasicBlock &BB : *newFunction) {
1533
645
    auto BlockIt = BB.begin();
1534
645
    // Remove debug info intrinsics from the new function.
1535
2.06k
    while (BlockIt != BB.end()) {
1536
1.41k
      Instruction *Inst = &*BlockIt;
1537
1.41k
      ++BlockIt;
1538
1.41k
      if (isa<DbgInfoIntrinsic>(Inst))
1539
1
        Inst->eraseFromParent();
1540
1.41k
    }
1541
645
    // Remove debug info intrinsics which refer to values in the new function
1542
645
    // from the old function.
1543
645
    SmallVector<DbgVariableIntrinsic *, 4> DbgUsers;
1544
645
    for (Instruction &I : BB)
1545
1.41k
      findDbgUsers(DbgUsers, &I);
1546
645
    for (DbgVariableIntrinsic *DVI : DbgUsers)
1547
1
      DVI->eraseFromParent();
1548
645
  }
1549
157
1550
157
  // Mark the new function `noreturn` if applicable. Terminators which resume
1551
157
  // exception propagation are treated as returning instructions. This is to
1552
157
  // avoid inserting traps after calls to outlined functions which unwind.
1553
330
  bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1554
330
    const Instruction *Term = BB.getTerminator();
1555
330
    return isa<ReturnInst>(Term) || 
isa<ResumeInst>(Term)183
;
1556
330
  });
1557
157
  if (doesNotReturn)
1558
10
    newFunction->setDoesNotReturn();
1559
157
1560
157
  LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1561
157
    newFunction->dump();
1562
157
    report_fatal_error("verification of newFunction failed!");
1563
157
  });
1564
157
  LLVM_DEBUG(if (verifyFunction(*oldFunction))
1565
157
             report_fatal_error("verification of oldFunction failed!"));
1566
157
  return newFunction;
1567
161
}