xref: /llvm-project/llvm/lib/Transforms/Utils/CodeExtractor.cpp (revision e17a39bc314f97231e440c9e68d9f46a9c07af6d)
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/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Analysis/AssumptionCache.h"
23 #include "llvm/Analysis/BlockFrequencyInfo.h"
24 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
25 #include "llvm/Analysis/BranchProbabilityInfo.h"
26 #include "llvm/IR/Argument.h"
27 #include "llvm/IR/Attributes.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/CFG.h"
30 #include "llvm/IR/Constant.h"
31 #include "llvm/IR/Constants.h"
32 #include "llvm/IR/DIBuilder.h"
33 #include "llvm/IR/DataLayout.h"
34 #include "llvm/IR/DebugInfo.h"
35 #include "llvm/IR/DebugInfoMetadata.h"
36 #include "llvm/IR/DerivedTypes.h"
37 #include "llvm/IR/Dominators.h"
38 #include "llvm/IR/Function.h"
39 #include "llvm/IR/GlobalValue.h"
40 #include "llvm/IR/InstIterator.h"
41 #include "llvm/IR/InstrTypes.h"
42 #include "llvm/IR/Instruction.h"
43 #include "llvm/IR/Instructions.h"
44 #include "llvm/IR/IntrinsicInst.h"
45 #include "llvm/IR/Intrinsics.h"
46 #include "llvm/IR/LLVMContext.h"
47 #include "llvm/IR/MDBuilder.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/IR/PatternMatch.h"
50 #include "llvm/IR/Type.h"
51 #include "llvm/IR/User.h"
52 #include "llvm/IR/Value.h"
53 #include "llvm/IR/Verifier.h"
54 #include "llvm/Support/BlockFrequency.h"
55 #include "llvm/Support/BranchProbability.h"
56 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/CommandLine.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/ErrorHandling.h"
60 #include "llvm/Support/raw_ostream.h"
61 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
62 #include <cassert>
63 #include <cstdint>
64 #include <iterator>
65 #include <map>
66 #include <utility>
67 #include <vector>
68 
69 using namespace llvm;
70 using namespace llvm::PatternMatch;
71 using ProfileCount = Function::ProfileCount;
72 
73 #define DEBUG_TYPE "code-extractor"
74 
75 // Provide a command-line option to aggregate function arguments into a struct
76 // for functions produced by the code extractor. This is useful when converting
77 // extracted functions to pthread-based code, as only one argument (void*) can
78 // be passed in to pthread_create().
79 static cl::opt<bool>
80 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
81                  cl::desc("Aggregate arguments to code-extracted functions"));
82 
83 /// Test whether a block is valid for extraction.
84 static bool isBlockValidForExtraction(const BasicBlock &BB,
85                                       const SetVector<BasicBlock *> &Result,
86                                       bool AllowVarArgs, bool AllowAlloca) {
87   // taking the address of a basic block moved to another function is illegal
88   if (BB.hasAddressTaken())
89     return false;
90 
91   // don't hoist code that uses another basicblock address, as it's likely to
92   // lead to unexpected behavior, like cross-function jumps
93   SmallPtrSet<User const *, 16> Visited;
94   SmallVector<User const *, 16> ToVisit;
95 
96   for (Instruction const &Inst : BB)
97     ToVisit.push_back(&Inst);
98 
99   while (!ToVisit.empty()) {
100     User const *Curr = ToVisit.pop_back_val();
101     if (!Visited.insert(Curr).second)
102       continue;
103     if (isa<BlockAddress const>(Curr))
104       return false; // even a reference to self is likely to be not compatible
105 
106     if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)
107       continue;
108 
109     for (auto const &U : Curr->operands()) {
110       if (auto *UU = dyn_cast<User>(U))
111         ToVisit.push_back(UU);
112     }
113   }
114 
115   // If explicitly requested, allow vastart and alloca. For invoke instructions
116   // verify that extraction is valid.
117   for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
118     if (isa<AllocaInst>(I)) {
119        if (!AllowAlloca)
120          return false;
121        continue;
122     }
123 
124     if (const auto *II = dyn_cast<InvokeInst>(I)) {
125       // Unwind destination (either a landingpad, catchswitch, or cleanuppad)
126       // must be a part of the subgraph which is being extracted.
127       if (auto *UBB = II->getUnwindDest())
128         if (!Result.count(UBB))
129           return false;
130       continue;
131     }
132 
133     // All catch handlers of a catchswitch instruction as well as the unwind
134     // destination must be in the subgraph.
135     if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) {
136       if (auto *UBB = CSI->getUnwindDest())
137         if (!Result.count(UBB))
138           return false;
139       for (const auto *HBB : CSI->handlers())
140         if (!Result.count(const_cast<BasicBlock*>(HBB)))
141           return false;
142       continue;
143     }
144 
145     // Make sure that entire catch handler is within subgraph. It is sufficient
146     // to check that catch return's block is in the list.
147     if (const auto *CPI = dyn_cast<CatchPadInst>(I)) {
148       for (const auto *U : CPI->users())
149         if (const auto *CRI = dyn_cast<CatchReturnInst>(U))
150           if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
151             return false;
152       continue;
153     }
154 
155     // And do similar checks for cleanup handler - the entire handler must be
156     // in subgraph which is going to be extracted. For cleanup return should
157     // additionally check that the unwind destination is also in the subgraph.
158     if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) {
159       for (const auto *U : CPI->users())
160         if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
161           if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
162             return false;
163       continue;
164     }
165     if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) {
166       if (auto *UBB = CRI->getUnwindDest())
167         if (!Result.count(UBB))
168           return false;
169       continue;
170     }
171 
172     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
173       if (const Function *F = CI->getCalledFunction()) {
174         auto IID = F->getIntrinsicID();
175         if (IID == Intrinsic::vastart) {
176           if (AllowVarArgs)
177             continue;
178           else
179             return false;
180         }
181 
182         // Currently, we miscompile outlined copies of eh_typid_for. There are
183         // proposals for fixing this in llvm.org/PR39545.
184         if (IID == Intrinsic::eh_typeid_for)
185           return false;
186       }
187     }
188   }
189 
190   return true;
191 }
192 
193 /// Build a set of blocks to extract if the input blocks are viable.
194 static SetVector<BasicBlock *>
195 buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
196                         bool AllowVarArgs, bool AllowAlloca) {
197   assert(!BBs.empty() && "The set of blocks to extract must be non-empty");
198   SetVector<BasicBlock *> Result;
199 
200   // Loop over the blocks, adding them to our set-vector, and aborting with an
201   // empty set if we encounter invalid blocks.
202   for (BasicBlock *BB : BBs) {
203     // If this block is dead, don't process it.
204     if (DT && !DT->isReachableFromEntry(BB))
205       continue;
206 
207     if (!Result.insert(BB))
208       llvm_unreachable("Repeated basic blocks in extraction input");
209   }
210 
211   LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName()
212                     << '\n');
213 
214   for (auto *BB : Result) {
215     if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca))
216       return {};
217 
218     // Make sure that the first block is not a landing pad.
219     if (BB == Result.front()) {
220       if (BB->isEHPad()) {
221         LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n");
222         return {};
223       }
224       continue;
225     }
226 
227     // All blocks other than the first must not have predecessors outside of
228     // the subgraph which is being extracted.
229     for (auto *PBB : predecessors(BB))
230       if (!Result.count(PBB)) {
231         LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from "
232                              "outside the region except for the first block!\n"
233                           << "Problematic source BB: " << BB->getName() << "\n"
234                           << "Problematic destination BB: " << PBB->getName()
235                           << "\n");
236         return {};
237       }
238   }
239 
240   return Result;
241 }
242 
243 CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
244                              bool AggregateArgs, BlockFrequencyInfo *BFI,
245                              BranchProbabilityInfo *BPI, AssumptionCache *AC,
246                              bool AllowVarArgs, bool AllowAlloca,
247                              BasicBlock *AllocationBlock, std::string Suffix,
248                              bool ArgsInZeroAddressSpace)
249     : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
250       BPI(BPI), AC(AC), AllocationBlock(AllocationBlock),
251       AllowVarArgs(AllowVarArgs),
252       Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)),
253       Suffix(Suffix), ArgsInZeroAddressSpace(ArgsInZeroAddressSpace) {}
254 
255 /// definedInRegion - Return true if the specified value is defined in the
256 /// extracted region.
257 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
258   if (Instruction *I = dyn_cast<Instruction>(V))
259     if (Blocks.count(I->getParent()))
260       return true;
261   return false;
262 }
263 
264 /// definedInCaller - Return true if the specified value is defined in the
265 /// function being code extracted, but not in the region being extracted.
266 /// These values must be passed in as live-ins to the function.
267 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
268   if (isa<Argument>(V)) return true;
269   if (Instruction *I = dyn_cast<Instruction>(V))
270     if (!Blocks.count(I->getParent()))
271       return true;
272   return false;
273 }
274 
275 static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
276   BasicBlock *CommonExitBlock = nullptr;
277   auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
278     for (auto *Succ : successors(Block)) {
279       // Internal edges, ok.
280       if (Blocks.count(Succ))
281         continue;
282       if (!CommonExitBlock) {
283         CommonExitBlock = Succ;
284         continue;
285       }
286       if (CommonExitBlock != Succ)
287         return true;
288     }
289     return false;
290   };
291 
292   if (any_of(Blocks, hasNonCommonExitSucc))
293     return nullptr;
294 
295   return CommonExitBlock;
296 }
297 
298 CodeExtractorAnalysisCache::CodeExtractorAnalysisCache(Function &F) {
299   for (BasicBlock &BB : F) {
300     for (Instruction &II : BB.instructionsWithoutDebug())
301       if (auto *AI = dyn_cast<AllocaInst>(&II))
302         Allocas.push_back(AI);
303 
304     findSideEffectInfoForBlock(BB);
305   }
306 }
307 
308 void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) {
309   for (Instruction &II : BB.instructionsWithoutDebug()) {
310     unsigned Opcode = II.getOpcode();
311     Value *MemAddr = nullptr;
312     switch (Opcode) {
313     case Instruction::Store:
314     case Instruction::Load: {
315       if (Opcode == Instruction::Store) {
316         StoreInst *SI = cast<StoreInst>(&II);
317         MemAddr = SI->getPointerOperand();
318       } else {
319         LoadInst *LI = cast<LoadInst>(&II);
320         MemAddr = LI->getPointerOperand();
321       }
322       // Global variable can not be aliased with locals.
323       if (isa<Constant>(MemAddr))
324         break;
325       Value *Base = MemAddr->stripInBoundsConstantOffsets();
326       if (!isa<AllocaInst>(Base)) {
327         SideEffectingBlocks.insert(&BB);
328         return;
329       }
330       BaseMemAddrs[&BB].insert(Base);
331       break;
332     }
333     default: {
334       IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
335       if (IntrInst) {
336         if (IntrInst->isLifetimeStartOrEnd())
337           break;
338         SideEffectingBlocks.insert(&BB);
339         return;
340       }
341       // Treat all the other cases conservatively if it has side effects.
342       if (II.mayHaveSideEffects()) {
343         SideEffectingBlocks.insert(&BB);
344         return;
345       }
346     }
347     }
348   }
349 }
350 
351 bool CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr(
352     BasicBlock &BB, AllocaInst *Addr) const {
353   if (SideEffectingBlocks.count(&BB))
354     return true;
355   auto It = BaseMemAddrs.find(&BB);
356   if (It != BaseMemAddrs.end())
357     return It->second.count(Addr);
358   return false;
359 }
360 
361 bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(
362     const CodeExtractorAnalysisCache &CEAC, Instruction *Addr) const {
363   AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
364   Function *Func = (*Blocks.begin())->getParent();
365   for (BasicBlock &BB : *Func) {
366     if (Blocks.count(&BB))
367       continue;
368     if (CEAC.doesBlockContainClobberOfAddr(BB, AI))
369       return false;
370   }
371   return true;
372 }
373 
374 BasicBlock *
375 CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
376   BasicBlock *SinglePredFromOutlineRegion = nullptr;
377   assert(!Blocks.count(CommonExitBlock) &&
378          "Expect a block outside the region!");
379   for (auto *Pred : predecessors(CommonExitBlock)) {
380     if (!Blocks.count(Pred))
381       continue;
382     if (!SinglePredFromOutlineRegion) {
383       SinglePredFromOutlineRegion = Pred;
384     } else if (SinglePredFromOutlineRegion != Pred) {
385       SinglePredFromOutlineRegion = nullptr;
386       break;
387     }
388   }
389 
390   if (SinglePredFromOutlineRegion)
391     return SinglePredFromOutlineRegion;
392 
393 #ifndef NDEBUG
394   auto getFirstPHI = [](BasicBlock *BB) {
395     BasicBlock::iterator I = BB->begin();
396     PHINode *FirstPhi = nullptr;
397     while (I != BB->end()) {
398       PHINode *Phi = dyn_cast<PHINode>(I);
399       if (!Phi)
400         break;
401       if (!FirstPhi) {
402         FirstPhi = Phi;
403         break;
404       }
405     }
406     return FirstPhi;
407   };
408   // If there are any phi nodes, the single pred either exists or has already
409   // be created before code extraction.
410   assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
411 #endif
412 
413   BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
414       CommonExitBlock->getFirstNonPHI()->getIterator());
415 
416   for (BasicBlock *Pred :
417        llvm::make_early_inc_range(predecessors(CommonExitBlock))) {
418     if (Blocks.count(Pred))
419       continue;
420     Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
421   }
422   // Now add the old exit block to the outline region.
423   Blocks.insert(CommonExitBlock);
424   OldTargets.push_back(NewExitBlock);
425   return CommonExitBlock;
426 }
427 
428 // Find the pair of life time markers for address 'Addr' that are either
429 // defined inside the outline region or can legally be shrinkwrapped into the
430 // outline region. If there are not other untracked uses of the address, return
431 // the pair of markers if found; otherwise return a pair of nullptr.
432 CodeExtractor::LifetimeMarkerInfo
433 CodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
434                                   Instruction *Addr,
435                                   BasicBlock *ExitBlock) const {
436   LifetimeMarkerInfo Info;
437 
438   for (User *U : Addr->users()) {
439     IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
440     if (IntrInst) {
441       // We don't model addresses with multiple start/end markers, but the
442       // markers do not need to be in the region.
443       if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
444         if (Info.LifeStart)
445           return {};
446         Info.LifeStart = IntrInst;
447         continue;
448       }
449       if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
450         if (Info.LifeEnd)
451           return {};
452         Info.LifeEnd = IntrInst;
453         continue;
454       }
455       // At this point, permit debug uses outside of the region.
456       // This is fixed in a later call to fixupDebugInfoPostExtraction().
457       if (isa<DbgInfoIntrinsic>(IntrInst))
458         continue;
459     }
460     // Find untracked uses of the address, bail.
461     if (!definedInRegion(Blocks, U))
462       return {};
463   }
464 
465   if (!Info.LifeStart || !Info.LifeEnd)
466     return {};
467 
468   Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart);
469   Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd);
470   // Do legality check.
471   if ((Info.SinkLifeStart || Info.HoistLifeEnd) &&
472       !isLegalToShrinkwrapLifetimeMarkers(CEAC, Addr))
473     return {};
474 
475   // Check to see if we have a place to do hoisting, if not, bail.
476   if (Info.HoistLifeEnd && !ExitBlock)
477     return {};
478 
479   return Info;
480 }
481 
482 void CodeExtractor::findAllocas(const CodeExtractorAnalysisCache &CEAC,
483                                 ValueSet &SinkCands, ValueSet &HoistCands,
484                                 BasicBlock *&ExitBlock) const {
485   Function *Func = (*Blocks.begin())->getParent();
486   ExitBlock = getCommonExitBlock(Blocks);
487 
488   auto moveOrIgnoreLifetimeMarkers =
489       [&](const LifetimeMarkerInfo &LMI) -> bool {
490     if (!LMI.LifeStart)
491       return false;
492     if (LMI.SinkLifeStart) {
493       LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart
494                         << "\n");
495       SinkCands.insert(LMI.LifeStart);
496     }
497     if (LMI.HoistLifeEnd) {
498       LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n");
499       HoistCands.insert(LMI.LifeEnd);
500     }
501     return true;
502   };
503 
504   // Look up allocas in the original function in CodeExtractorAnalysisCache, as
505   // this is much faster than walking all the instructions.
506   for (AllocaInst *AI : CEAC.getAllocas()) {
507     BasicBlock *BB = AI->getParent();
508     if (Blocks.count(BB))
509       continue;
510 
511     // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca,
512     // check whether it is actually still in the original function.
513     Function *AIFunc = BB->getParent();
514     if (AIFunc != Func)
515       continue;
516 
517     LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock);
518     bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);
519     if (Moved) {
520       LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n");
521       SinkCands.insert(AI);
522       continue;
523     }
524 
525     // Find bitcasts in the outlined region that have lifetime marker users
526     // outside that region. Replace the lifetime marker use with an
527     // outside region bitcast to avoid unnecessary alloca/reload instructions
528     // and extra lifetime markers.
529     SmallVector<Instruction *, 2> LifetimeBitcastUsers;
530     for (User *U : AI->users()) {
531       if (!definedInRegion(Blocks, U))
532         continue;
533 
534       if (U->stripInBoundsConstantOffsets() != AI)
535         continue;
536 
537       Instruction *Bitcast = cast<Instruction>(U);
538       for (User *BU : Bitcast->users()) {
539         IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(BU);
540         if (!IntrInst)
541           continue;
542 
543         if (!IntrInst->isLifetimeStartOrEnd())
544           continue;
545 
546         if (definedInRegion(Blocks, IntrInst))
547           continue;
548 
549         LLVM_DEBUG(dbgs() << "Replace use of extracted region bitcast"
550                           << *Bitcast << " in out-of-region lifetime marker "
551                           << *IntrInst << "\n");
552         LifetimeBitcastUsers.push_back(IntrInst);
553       }
554     }
555 
556     for (Instruction *I : LifetimeBitcastUsers) {
557       Module *M = AIFunc->getParent();
558       LLVMContext &Ctx = M->getContext();
559       auto *Int8PtrTy = PointerType::getUnqual(Ctx);
560       CastInst *CastI =
561           CastInst::CreatePointerCast(AI, Int8PtrTy, "lt.cast", I->getIterator());
562       I->replaceUsesOfWith(I->getOperand(1), CastI);
563     }
564 
565     // Follow any bitcasts.
566     SmallVector<Instruction *, 2> Bitcasts;
567     SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo;
568     for (User *U : AI->users()) {
569       if (U->stripInBoundsConstantOffsets() == AI) {
570         Instruction *Bitcast = cast<Instruction>(U);
571         LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock);
572         if (LMI.LifeStart) {
573           Bitcasts.push_back(Bitcast);
574           BitcastLifetimeInfo.push_back(LMI);
575           continue;
576         }
577       }
578 
579       // Found unknown use of AI.
580       if (!definedInRegion(Blocks, U)) {
581         Bitcasts.clear();
582         break;
583       }
584     }
585 
586     // Either no bitcasts reference the alloca or there are unknown uses.
587     if (Bitcasts.empty())
588       continue;
589 
590     LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n");
591     SinkCands.insert(AI);
592     for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) {
593       Instruction *BitcastAddr = Bitcasts[I];
594       const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I];
595       assert(LMI.LifeStart &&
596              "Unsafe to sink bitcast without lifetime markers");
597       moveOrIgnoreLifetimeMarkers(LMI);
598       if (!definedInRegion(Blocks, BitcastAddr)) {
599         LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr
600                           << "\n");
601         SinkCands.insert(BitcastAddr);
602       }
603     }
604   }
605 }
606 
607 bool CodeExtractor::isEligible() const {
608   if (Blocks.empty())
609     return false;
610   BasicBlock *Header = *Blocks.begin();
611   Function *F = Header->getParent();
612 
613   // For functions with varargs, check that varargs handling is only done in the
614   // outlined function, i.e vastart and vaend are only used in outlined blocks.
615   if (AllowVarArgs && F->getFunctionType()->isVarArg()) {
616     auto containsVarArgIntrinsic = [](const Instruction &I) {
617       if (const CallInst *CI = dyn_cast<CallInst>(&I))
618         if (const Function *Callee = CI->getCalledFunction())
619           return Callee->getIntrinsicID() == Intrinsic::vastart ||
620                  Callee->getIntrinsicID() == Intrinsic::vaend;
621       return false;
622     };
623 
624     for (auto &BB : *F) {
625       if (Blocks.count(&BB))
626         continue;
627       if (llvm::any_of(BB, containsVarArgIntrinsic))
628         return false;
629     }
630   }
631   return true;
632 }
633 
634 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
635                                       const ValueSet &SinkCands,
636                                       bool CollectGlobalInputs) const {
637   for (BasicBlock *BB : Blocks) {
638     // If a used value is defined outside the region, it's an input.  If an
639     // instruction is used outside the region, it's an output.
640     for (Instruction &II : *BB) {
641       for (auto &OI : II.operands()) {
642         Value *V = OI;
643         if (!SinkCands.count(V) &&
644             (definedInCaller(Blocks, V) ||
645              (CollectGlobalInputs && llvm::isa<llvm::GlobalVariable>(V))))
646           Inputs.insert(V);
647       }
648 
649       for (User *U : II.users())
650         if (!definedInRegion(Blocks, U)) {
651           Outputs.insert(&II);
652           break;
653         }
654     }
655   }
656 }
657 
658 /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside
659 /// of the region, we need to split the entry block of the region so that the
660 /// PHI node is easier to deal with.
661 void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {
662   unsigned NumPredsFromRegion = 0;
663   unsigned NumPredsOutsideRegion = 0;
664 
665   if (Header != &Header->getParent()->getEntryBlock()) {
666     PHINode *PN = dyn_cast<PHINode>(Header->begin());
667     if (!PN) return;  // No PHI nodes.
668 
669     // If the header node contains any PHI nodes, check to see if there is more
670     // than one entry from outside the region.  If so, we need to sever the
671     // header block into two.
672     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
673       if (Blocks.count(PN->getIncomingBlock(i)))
674         ++NumPredsFromRegion;
675       else
676         ++NumPredsOutsideRegion;
677 
678     // If there is one (or fewer) predecessor from outside the region, we don't
679     // need to do anything special.
680     if (NumPredsOutsideRegion <= 1) return;
681   }
682 
683   // Otherwise, we need to split the header block into two pieces: one
684   // containing PHI nodes merging values from outside of the region, and a
685   // second that contains all of the code for the block and merges back any
686   // incoming values from inside of the region.
687   BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
688 
689   // We only want to code extract the second block now, and it becomes the new
690   // header of the region.
691   BasicBlock *OldPred = Header;
692   Blocks.remove(OldPred);
693   Blocks.insert(NewBB);
694   Header = NewBB;
695 
696   // Okay, now we need to adjust the PHI nodes and any branches from within the
697   // region to go to the new header block instead of the old header block.
698   if (NumPredsFromRegion) {
699     PHINode *PN = cast<PHINode>(OldPred->begin());
700     // Loop over all of the predecessors of OldPred that are in the region,
701     // changing them to branch to NewBB instead.
702     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
703       if (Blocks.count(PN->getIncomingBlock(i))) {
704         Instruction *TI = PN->getIncomingBlock(i)->getTerminator();
705         TI->replaceUsesOfWith(OldPred, NewBB);
706       }
707 
708     // Okay, everything within the region is now branching to the right block, we
709     // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
710     BasicBlock::iterator AfterPHIs;
711     for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
712       PHINode *PN = cast<PHINode>(AfterPHIs);
713       // Create a new PHI node in the new region, which has an incoming value
714       // from OldPred of PN.
715       PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
716                                        PN->getName() + ".ce");
717       NewPN->insertBefore(NewBB->begin());
718       PN->replaceAllUsesWith(NewPN);
719       NewPN->addIncoming(PN, OldPred);
720 
721       // Loop over all of the incoming value in PN, moving them to NewPN if they
722       // are from the extracted region.
723       for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
724         if (Blocks.count(PN->getIncomingBlock(i))) {
725           NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
726           PN->removeIncomingValue(i);
727           --i;
728         }
729       }
730     }
731   }
732 }
733 
734 /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
735 /// outlined region, we split these PHIs on two: one with inputs from region
736 /// and other with remaining incoming blocks; then first PHIs are placed in
737 /// outlined region.
738 void CodeExtractor::severSplitPHINodesOfExits(
739     const SetVector<BasicBlock *> &Exits) {
740   for (BasicBlock *ExitBB : Exits) {
741     BasicBlock *NewBB = nullptr;
742 
743     for (PHINode &PN : ExitBB->phis()) {
744       // Find all incoming values from the outlining region.
745       SmallVector<unsigned, 2> IncomingVals;
746       for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
747         if (Blocks.count(PN.getIncomingBlock(i)))
748           IncomingVals.push_back(i);
749 
750       // Do not process PHI if there is one (or fewer) predecessor from region.
751       // If PHI has exactly one predecessor from region, only this one incoming
752       // will be replaced on codeRepl block, so it should be safe to skip PHI.
753       if (IncomingVals.size() <= 1)
754         continue;
755 
756       // Create block for new PHIs and add it to the list of outlined if it
757       // wasn't done before.
758       if (!NewBB) {
759         NewBB = BasicBlock::Create(ExitBB->getContext(),
760                                    ExitBB->getName() + ".split",
761                                    ExitBB->getParent(), ExitBB);
762         NewBB->IsNewDbgInfoFormat = ExitBB->IsNewDbgInfoFormat;
763         SmallVector<BasicBlock *, 4> Preds(predecessors(ExitBB));
764         for (BasicBlock *PredBB : Preds)
765           if (Blocks.count(PredBB))
766             PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
767         BranchInst::Create(ExitBB, NewBB);
768         Blocks.insert(NewBB);
769       }
770 
771       // Split this PHI.
772       PHINode *NewPN = PHINode::Create(PN.getType(), IncomingVals.size(),
773                                        PN.getName() + ".ce");
774       NewPN->insertBefore(NewBB->getFirstNonPHIIt());
775       for (unsigned i : IncomingVals)
776         NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));
777       for (unsigned i : reverse(IncomingVals))
778         PN.removeIncomingValue(i, false);
779       PN.addIncoming(NewPN, NewBB);
780     }
781   }
782 }
783 
784 void CodeExtractor::splitReturnBlocks() {
785   for (BasicBlock *Block : Blocks)
786     if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
787       BasicBlock *New =
788           Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
789       if (DT) {
790         // Old dominates New. New node dominates all other nodes dominated
791         // by Old.
792         DomTreeNode *OldNode = DT->getNode(Block);
793         SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
794                                                OldNode->end());
795 
796         DomTreeNode *NewNode = DT->addNewBlock(New, Block);
797 
798         for (DomTreeNode *I : Children)
799           DT->changeImmediateDominator(I, NewNode);
800       }
801     }
802 }
803 
804 /// constructFunction - make a function based on inputs and outputs, as follows:
805 /// f(in0, ..., inN, out0, ..., outN)
806 Function *CodeExtractor::constructFunction(const ValueSet &inputs,
807                                            const ValueSet &outputs,
808                                            BasicBlock *header,
809                                            BasicBlock *newRootNode,
810                                            BasicBlock *newHeader,
811                                            Function *oldFunction,
812                                            Module *M) {
813   LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
814   LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
815 
816   // This function returns unsigned, outputs will go back by reference.
817   switch (NumExitBlocks) {
818   case 0:
819   case 1: RetTy = Type::getVoidTy(header->getContext()); break;
820   case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
821   default: RetTy = Type::getInt16Ty(header->getContext()); break;
822   }
823 
824   std::vector<Type *> ParamTy;
825   std::vector<Type *> AggParamTy;
826   ValueSet StructValues;
827   const DataLayout &DL = M->getDataLayout();
828 
829   // Add the types of the input values to the function's argument list
830   for (Value *value : inputs) {
831     LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
832     if (AggregateArgs && !ExcludeArgsFromAggregate.contains(value)) {
833       AggParamTy.push_back(value->getType());
834       StructValues.insert(value);
835     } else
836       ParamTy.push_back(value->getType());
837   }
838 
839   // Add the types of the output values to the function's argument list.
840   for (Value *output : outputs) {
841     LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
842     if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {
843       AggParamTy.push_back(output->getType());
844       StructValues.insert(output);
845     } else
846       ParamTy.push_back(
847           PointerType::get(output->getType(), DL.getAllocaAddrSpace()));
848   }
849 
850   assert(
851       (ParamTy.size() + AggParamTy.size()) ==
852           (inputs.size() + outputs.size()) &&
853       "Number of scalar and aggregate params does not match inputs, outputs");
854   assert((StructValues.empty() || AggregateArgs) &&
855          "Expeced StructValues only with AggregateArgs set");
856 
857   // Concatenate scalar and aggregate params in ParamTy.
858   size_t NumScalarParams = ParamTy.size();
859   StructType *StructTy = nullptr;
860   if (AggregateArgs && !AggParamTy.empty()) {
861     StructTy = StructType::get(M->getContext(), AggParamTy);
862     ParamTy.push_back(PointerType::get(
863         StructTy, ArgsInZeroAddressSpace ? 0 : DL.getAllocaAddrSpace()));
864   }
865 
866   LLVM_DEBUG({
867     dbgs() << "Function type: " << *RetTy << " f(";
868     for (Type *i : ParamTy)
869       dbgs() << *i << ", ";
870     dbgs() << ")\n";
871   });
872 
873   FunctionType *funcType = FunctionType::get(
874       RetTy, ParamTy, AllowVarArgs && oldFunction->isVarArg());
875 
876   std::string SuffixToUse =
877       Suffix.empty()
878           ? (header->getName().empty() ? "extracted" : header->getName().str())
879           : Suffix;
880   // Create the new function
881   Function *newFunction = Function::Create(
882       funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
883       oldFunction->getName() + "." + SuffixToUse, M);
884   newFunction->IsNewDbgInfoFormat = oldFunction->IsNewDbgInfoFormat;
885 
886   // Inherit all of the target dependent attributes and white-listed
887   // target independent attributes.
888   //  (e.g. If the extracted region contains a call to an x86.sse
889   //  instruction we need to make sure that the extracted region has the
890   //  "target-features" attribute allowing it to be lowered.
891   // FIXME: This should be changed to check to see if a specific
892   //           attribute can not be inherited.
893   for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) {
894     if (Attr.isStringAttribute()) {
895       if (Attr.getKindAsString() == "thunk")
896         continue;
897     } else
898       switch (Attr.getKindAsEnum()) {
899       // Those attributes cannot be propagated safely. Explicitly list them
900       // here so we get a warning if new attributes are added.
901       case Attribute::AllocSize:
902       case Attribute::Builtin:
903       case Attribute::Convergent:
904       case Attribute::JumpTable:
905       case Attribute::Naked:
906       case Attribute::NoBuiltin:
907       case Attribute::NoMerge:
908       case Attribute::NoReturn:
909       case Attribute::NoSync:
910       case Attribute::ReturnsTwice:
911       case Attribute::Speculatable:
912       case Attribute::StackAlignment:
913       case Attribute::WillReturn:
914       case Attribute::AllocKind:
915       case Attribute::PresplitCoroutine:
916       case Attribute::Memory:
917       case Attribute::NoFPClass:
918       case Attribute::CoroDestroyOnlyWhenComplete:
919       case Attribute::CoroElideSafe:
920         continue;
921       // Those attributes should be safe to propagate to the extracted function.
922       case Attribute::AlwaysInline:
923       case Attribute::Cold:
924       case Attribute::DisableSanitizerInstrumentation:
925       case Attribute::FnRetThunkExtern:
926       case Attribute::Hot:
927       case Attribute::HybridPatchable:
928       case Attribute::NoRecurse:
929       case Attribute::InlineHint:
930       case Attribute::MinSize:
931       case Attribute::NoCallback:
932       case Attribute::NoDuplicate:
933       case Attribute::NoFree:
934       case Attribute::NoImplicitFloat:
935       case Attribute::NoInline:
936       case Attribute::NonLazyBind:
937       case Attribute::NoRedZone:
938       case Attribute::NoUnwind:
939       case Attribute::NoSanitizeBounds:
940       case Attribute::NoSanitizeCoverage:
941       case Attribute::NullPointerIsValid:
942       case Attribute::OptimizeForDebugging:
943       case Attribute::OptForFuzzing:
944       case Attribute::OptimizeNone:
945       case Attribute::OptimizeForSize:
946       case Attribute::SafeStack:
947       case Attribute::ShadowCallStack:
948       case Attribute::SanitizeAddress:
949       case Attribute::SanitizeMemory:
950       case Attribute::SanitizeNumericalStability:
951       case Attribute::SanitizeThread:
952       case Attribute::SanitizeHWAddress:
953       case Attribute::SanitizeMemTag:
954       case Attribute::SanitizeRealtime:
955       case Attribute::SpeculativeLoadHardening:
956       case Attribute::StackProtect:
957       case Attribute::StackProtectReq:
958       case Attribute::StackProtectStrong:
959       case Attribute::StrictFP:
960       case Attribute::UWTable:
961       case Attribute::VScaleRange:
962       case Attribute::NoCfCheck:
963       case Attribute::MustProgress:
964       case Attribute::NoProfile:
965       case Attribute::SkipProfile:
966         break;
967       // These attributes cannot be applied to functions.
968       case Attribute::Alignment:
969       case Attribute::AllocatedPointer:
970       case Attribute::AllocAlign:
971       case Attribute::ByVal:
972       case Attribute::Dereferenceable:
973       case Attribute::DereferenceableOrNull:
974       case Attribute::ElementType:
975       case Attribute::InAlloca:
976       case Attribute::InReg:
977       case Attribute::Nest:
978       case Attribute::NoAlias:
979       case Attribute::NoCapture:
980       case Attribute::NoUndef:
981       case Attribute::NonNull:
982       case Attribute::Preallocated:
983       case Attribute::ReadNone:
984       case Attribute::ReadOnly:
985       case Attribute::Returned:
986       case Attribute::SExt:
987       case Attribute::StructRet:
988       case Attribute::SwiftError:
989       case Attribute::SwiftSelf:
990       case Attribute::SwiftAsync:
991       case Attribute::ZExt:
992       case Attribute::ImmArg:
993       case Attribute::ByRef:
994       case Attribute::WriteOnly:
995       case Attribute::Writable:
996       case Attribute::DeadOnUnwind:
997       case Attribute::Range:
998       case Attribute::Initializes:
999       //  These are not really attributes.
1000       case Attribute::None:
1001       case Attribute::EndAttrKinds:
1002       case Attribute::EmptyKey:
1003       case Attribute::TombstoneKey:
1004         llvm_unreachable("Not a function attribute");
1005       }
1006 
1007     newFunction->addFnAttr(Attr);
1008   }
1009 
1010   if (NumExitBlocks == 0) {
1011     // Mark the new function `noreturn` if applicable. Terminators which resume
1012     // exception propagation are treated as returning instructions. This is to
1013     // avoid inserting traps after calls to outlined functions which unwind.
1014     if (none_of(Blocks, [](const BasicBlock *BB) {
1015           const Instruction *Term = BB->getTerminator();
1016           return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1017         }))
1018       newFunction->setDoesNotReturn();
1019   }
1020 
1021   newFunction->insert(newFunction->end(), newRootNode);
1022 
1023   // Create scalar and aggregate iterators to name all of the arguments we
1024   // inserted.
1025   Function::arg_iterator ScalarAI = newFunction->arg_begin();
1026   Function::arg_iterator AggAI = std::next(ScalarAI, NumScalarParams);
1027 
1028   // Rewrite all users of the inputs in the extracted region to use the
1029   // arguments (or appropriate addressing into struct) instead.
1030   for (unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) {
1031     Value *RewriteVal;
1032     if (AggregateArgs && StructValues.contains(inputs[i])) {
1033       Value *Idx[2];
1034       Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
1035       Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), aggIdx);
1036       BasicBlock::iterator TI = newFunction->begin()->getTerminator()->getIterator();
1037       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1038           StructTy, &*AggAI, Idx, "gep_" + inputs[i]->getName(), TI);
1039       RewriteVal = new LoadInst(StructTy->getElementType(aggIdx), GEP,
1040                                 "loadgep_" + inputs[i]->getName(), TI);
1041       ++aggIdx;
1042     } else
1043       RewriteVal = &*ScalarAI++;
1044 
1045     std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
1046     for (User *use : Users)
1047       if (Instruction *inst = dyn_cast<Instruction>(use))
1048         if (Blocks.count(inst->getParent()))
1049           inst->replaceUsesOfWith(inputs[i], RewriteVal);
1050   }
1051 
1052   // Set names for input and output arguments.
1053   if (NumScalarParams) {
1054     ScalarAI = newFunction->arg_begin();
1055     for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++ScalarAI)
1056       if (!StructValues.contains(inputs[i]))
1057         ScalarAI->setName(inputs[i]->getName());
1058     for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++ScalarAI)
1059       if (!StructValues.contains(outputs[i]))
1060         ScalarAI->setName(outputs[i]->getName() + ".out");
1061   }
1062 
1063   // Rewrite branches to basic blocks outside of the loop to new dummy blocks
1064   // within the new function. This must be done before we lose track of which
1065   // blocks were originally in the code region.
1066   std::vector<User *> Users(header->user_begin(), header->user_end());
1067   for (auto &U : Users)
1068     // The BasicBlock which contains the branch is not in the region
1069     // modify the branch target to a new block
1070     if (Instruction *I = dyn_cast<Instruction>(U))
1071       if (I->isTerminator() && I->getFunction() == oldFunction &&
1072           !Blocks.count(I->getParent()))
1073         I->replaceUsesOfWith(header, newHeader);
1074 
1075   return newFunction;
1076 }
1077 
1078 /// Erase lifetime.start markers which reference inputs to the extraction
1079 /// region, and insert the referenced memory into \p LifetimesStart.
1080 ///
1081 /// The extraction region is defined by a set of blocks (\p Blocks), and a set
1082 /// of allocas which will be moved from the caller function into the extracted
1083 /// function (\p SunkAllocas).
1084 static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks,
1085                                          const SetVector<Value *> &SunkAllocas,
1086                                          SetVector<Value *> &LifetimesStart) {
1087   for (BasicBlock *BB : Blocks) {
1088     for (Instruction &I : llvm::make_early_inc_range(*BB)) {
1089       auto *II = dyn_cast<IntrinsicInst>(&I);
1090       if (!II || !II->isLifetimeStartOrEnd())
1091         continue;
1092 
1093       // Get the memory operand of the lifetime marker. If the underlying
1094       // object is a sunk alloca, or is otherwise defined in the extraction
1095       // region, the lifetime marker must not be erased.
1096       Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1097       if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1098         continue;
1099 
1100       if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1101         LifetimesStart.insert(Mem);
1102       II->eraseFromParent();
1103     }
1104   }
1105 }
1106 
1107 /// Insert lifetime start/end markers surrounding the call to the new function
1108 /// for objects defined in the caller.
1109 static void insertLifetimeMarkersSurroundingCall(
1110     Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1111     CallInst *TheCall) {
1112   LLVMContext &Ctx = M->getContext();
1113   auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1114   Instruction *Term = TheCall->getParent()->getTerminator();
1115 
1116   // Emit lifetime markers for the pointers given in \p Objects. Insert the
1117   // markers before the call if \p InsertBefore, and after the call otherwise.
1118   auto insertMarkers = [&](Intrinsic::ID MarkerFunc, ArrayRef<Value *> Objects,
1119                            bool InsertBefore) {
1120     for (Value *Mem : Objects) {
1121       assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1122                                             TheCall->getFunction()) &&
1123              "Input memory not defined in original function");
1124 
1125       Function *Func = Intrinsic::getDeclaration(M, MarkerFunc, Mem->getType());
1126       auto Marker = CallInst::Create(Func, {NegativeOne, Mem});
1127       if (InsertBefore)
1128         Marker->insertBefore(TheCall);
1129       else
1130         Marker->insertBefore(Term);
1131     }
1132   };
1133 
1134   if (!LifetimesStart.empty()) {
1135     insertMarkers(Intrinsic::lifetime_start, LifetimesStart,
1136                   /*InsertBefore=*/true);
1137   }
1138 
1139   if (!LifetimesEnd.empty()) {
1140     insertMarkers(Intrinsic::lifetime_end, LifetimesEnd,
1141                   /*InsertBefore=*/false);
1142   }
1143 }
1144 
1145 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
1146 /// the call instruction, splitting any PHI nodes in the header block as
1147 /// necessary.
1148 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1149                                                     BasicBlock *codeReplacer,
1150                                                     ValueSet &inputs,
1151                                                     ValueSet &outputs) {
1152   // Emit a call to the new function, passing in: *pointer to struct (if
1153   // aggregating parameters), or plan inputs and allocated memory for outputs
1154   std::vector<Value *> params, ReloadOutputs, Reloads;
1155   ValueSet StructValues;
1156 
1157   Module *M = newFunction->getParent();
1158   LLVMContext &Context = M->getContext();
1159   const DataLayout &DL = M->getDataLayout();
1160   CallInst *call = nullptr;
1161 
1162   // Add inputs as params, or to be filled into the struct
1163   unsigned ScalarInputArgNo = 0;
1164   SmallVector<unsigned, 1> SwiftErrorArgs;
1165   for (Value *input : inputs) {
1166     if (AggregateArgs && !ExcludeArgsFromAggregate.contains(input))
1167       StructValues.insert(input);
1168     else {
1169       params.push_back(input);
1170       if (input->isSwiftError())
1171         SwiftErrorArgs.push_back(ScalarInputArgNo);
1172     }
1173     ++ScalarInputArgNo;
1174   }
1175 
1176   // Create allocas for the outputs
1177   unsigned ScalarOutputArgNo = 0;
1178   for (Value *output : outputs) {
1179     if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {
1180       StructValues.insert(output);
1181     } else {
1182       AllocaInst *alloca =
1183         new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1184                        nullptr, output->getName() + ".loc",
1185                        codeReplacer->getParent()->front().begin());
1186       ReloadOutputs.push_back(alloca);
1187       params.push_back(alloca);
1188       ++ScalarOutputArgNo;
1189     }
1190   }
1191 
1192   StructType *StructArgTy = nullptr;
1193   AllocaInst *Struct = nullptr;
1194   unsigned NumAggregatedInputs = 0;
1195   if (AggregateArgs && !StructValues.empty()) {
1196     std::vector<Type *> ArgTypes;
1197     for (Value *V : StructValues)
1198       ArgTypes.push_back(V->getType());
1199 
1200     // Allocate a struct at the beginning of this function
1201     StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1202     Struct = new AllocaInst(
1203         StructArgTy, DL.getAllocaAddrSpace(), nullptr, "structArg",
1204         AllocationBlock ? AllocationBlock->getFirstInsertionPt()
1205                         : codeReplacer->getParent()->front().begin());
1206 
1207     if (ArgsInZeroAddressSpace && DL.getAllocaAddrSpace() != 0) {
1208       auto *StructSpaceCast = new AddrSpaceCastInst(
1209           Struct, PointerType ::get(Context, 0), "structArg.ascast");
1210       StructSpaceCast->insertAfter(Struct);
1211       params.push_back(StructSpaceCast);
1212     } else {
1213       params.push_back(Struct);
1214     }
1215     // Store aggregated inputs in the struct.
1216     for (unsigned i = 0, e = StructValues.size(); i != e; ++i) {
1217       if (inputs.contains(StructValues[i])) {
1218         Value *Idx[2];
1219         Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1220         Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
1221         GetElementPtrInst *GEP = GetElementPtrInst::Create(
1222             StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1223         GEP->insertInto(codeReplacer, codeReplacer->end());
1224         new StoreInst(StructValues[i], GEP, codeReplacer);
1225         NumAggregatedInputs++;
1226       }
1227     }
1228   }
1229 
1230   // Emit the call to the function
1231   call = CallInst::Create(newFunction, params,
1232                           NumExitBlocks > 1 ? "targetBlock" : "");
1233   // Add debug location to the new call, if the original function has debug
1234   // info. In that case, the terminator of the entry block of the extracted
1235   // function contains the first debug location of the extracted function,
1236   // set in extractCodeRegion.
1237   if (codeReplacer->getParent()->getSubprogram()) {
1238     if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1239       call->setDebugLoc(DL);
1240   }
1241   call->insertInto(codeReplacer, codeReplacer->end());
1242 
1243   // Set swifterror parameter attributes.
1244   for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1245     call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1246     newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1247   }
1248 
1249   // Reload the outputs passed in by reference, use the struct if output is in
1250   // the aggregate or reload from the scalar argument.
1251   for (unsigned i = 0, e = outputs.size(), scalarIdx = 0,
1252                 aggIdx = NumAggregatedInputs;
1253        i != e; ++i) {
1254     Value *Output = nullptr;
1255     if (AggregateArgs && StructValues.contains(outputs[i])) {
1256       Value *Idx[2];
1257       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1258       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx);
1259       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1260           StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1261       GEP->insertInto(codeReplacer, codeReplacer->end());
1262       Output = GEP;
1263       ++aggIdx;
1264     } else {
1265       Output = ReloadOutputs[scalarIdx];
1266       ++scalarIdx;
1267     }
1268     LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1269                                   outputs[i]->getName() + ".reload",
1270                                   codeReplacer);
1271     Reloads.push_back(load);
1272     std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1273     for (User *U : Users) {
1274       Instruction *inst = cast<Instruction>(U);
1275       if (!Blocks.count(inst->getParent()))
1276         inst->replaceUsesOfWith(outputs[i], load);
1277     }
1278   }
1279 
1280   // Now we can emit a switch statement using the call as a value.
1281   SwitchInst *TheSwitch =
1282       SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
1283                          codeReplacer, 0, codeReplacer);
1284 
1285   // Since there may be multiple exits from the original region, make the new
1286   // function return an unsigned, switch on that number.  This loop iterates
1287   // over all of the blocks in the extracted region, updating any terminator
1288   // instructions in the to-be-extracted region that branch to blocks that are
1289   // not in the region to be extracted.
1290   std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1291 
1292   // Iterate over the previously collected targets, and create new blocks inside
1293   // the function to branch to.
1294   unsigned switchVal = 0;
1295   for (BasicBlock *OldTarget : OldTargets) {
1296     if (Blocks.count(OldTarget))
1297       continue;
1298     BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1299     if (NewTarget)
1300       continue;
1301 
1302     // If we don't already have an exit stub for this non-extracted
1303     // destination, create one now!
1304     NewTarget = BasicBlock::Create(Context,
1305                                     OldTarget->getName() + ".exitStub",
1306                                     newFunction);
1307     unsigned SuccNum = switchVal++;
1308 
1309     Value *brVal = nullptr;
1310     assert(NumExitBlocks < 0xffff && "too many exit blocks for switch");
1311     switch (NumExitBlocks) {
1312     case 0:
1313     case 1: break;  // No value needed.
1314     case 2:         // Conditional branch, return a bool
1315       brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1316       break;
1317     default:
1318       brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1319       break;
1320     }
1321 
1322     ReturnInst::Create(Context, brVal, NewTarget);
1323 
1324     // Update the switch instruction.
1325     TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
1326                                         SuccNum),
1327                         OldTarget);
1328   }
1329 
1330   for (BasicBlock *Block : Blocks) {
1331     Instruction *TI = Block->getTerminator();
1332     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1333       if (Blocks.count(TI->getSuccessor(i)))
1334         continue;
1335       BasicBlock *OldTarget = TI->getSuccessor(i);
1336       // add a new basic block which returns the appropriate value
1337       BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1338       assert(NewTarget && "Unknown target block!");
1339 
1340       // rewrite the original branch instruction with this new target
1341       TI->setSuccessor(i, NewTarget);
1342    }
1343   }
1344 
1345   // Store the arguments right after the definition of output value.
1346   // This should be proceeded after creating exit stubs to be ensure that invoke
1347   // result restore will be placed in the outlined function.
1348   Function::arg_iterator ScalarOutputArgBegin = newFunction->arg_begin();
1349   std::advance(ScalarOutputArgBegin, ScalarInputArgNo);
1350   Function::arg_iterator AggOutputArgBegin = newFunction->arg_begin();
1351   std::advance(AggOutputArgBegin, ScalarInputArgNo + ScalarOutputArgNo);
1352 
1353   for (unsigned i = 0, e = outputs.size(), aggIdx = NumAggregatedInputs; i != e;
1354        ++i) {
1355     auto *OutI = dyn_cast<Instruction>(outputs[i]);
1356     if (!OutI)
1357       continue;
1358 
1359     // Find proper insertion point.
1360     BasicBlock::iterator InsertPt;
1361     // In case OutI is an invoke, we insert the store at the beginning in the
1362     // 'normal destination' BB. Otherwise we insert the store right after OutI.
1363     if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1364       InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1365     else if (auto *Phi = dyn_cast<PHINode>(OutI))
1366       InsertPt = Phi->getParent()->getFirstInsertionPt();
1367     else
1368       InsertPt = std::next(OutI->getIterator());
1369 
1370     assert((InsertPt->getFunction() == newFunction ||
1371             Blocks.count(InsertPt->getParent())) &&
1372            "InsertPt should be in new function");
1373     if (AggregateArgs && StructValues.contains(outputs[i])) {
1374       assert(AggOutputArgBegin != newFunction->arg_end() &&
1375              "Number of aggregate output arguments should match "
1376              "the number of defined values");
1377       Value *Idx[2];
1378       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1379       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx);
1380       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1381           StructArgTy, &*AggOutputArgBegin, Idx, "gep_" + outputs[i]->getName(),
1382           InsertPt);
1383       new StoreInst(outputs[i], GEP, InsertPt);
1384       ++aggIdx;
1385       // Since there should be only one struct argument aggregating
1386       // all the output values, we shouldn't increment AggOutputArgBegin, which
1387       // always points to the struct argument, in this case.
1388     } else {
1389       assert(ScalarOutputArgBegin != newFunction->arg_end() &&
1390              "Number of scalar output arguments should match "
1391              "the number of defined values");
1392       new StoreInst(outputs[i], &*ScalarOutputArgBegin, InsertPt);
1393       ++ScalarOutputArgBegin;
1394     }
1395   }
1396 
1397   // Now that we've done the deed, simplify the switch instruction.
1398   Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1399   switch (NumExitBlocks) {
1400   case 0:
1401     // There are no successors (the block containing the switch itself), which
1402     // means that previously this was the last part of the function, and hence
1403     // this should be rewritten as a `ret` or `unreachable`.
1404     if (newFunction->doesNotReturn()) {
1405       // If fn is no return, end with an unreachable terminator.
1406       (void)new UnreachableInst(Context, TheSwitch->getIterator());
1407     } else if (OldFnRetTy->isVoidTy()) {
1408       // We have no return value.
1409       ReturnInst::Create(Context, nullptr,
1410                          TheSwitch->getIterator()); // Return void
1411     } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1412       // return what we have
1413       ReturnInst::Create(Context, TheSwitch->getCondition(),
1414                          TheSwitch->getIterator());
1415     } else {
1416       // Otherwise we must have code extracted an unwind or something, just
1417       // return whatever we want.
1418       ReturnInst::Create(Context, Constant::getNullValue(OldFnRetTy),
1419                          TheSwitch->getIterator());
1420     }
1421 
1422     TheSwitch->eraseFromParent();
1423     break;
1424   case 1:
1425     // Only a single destination, change the switch into an unconditional
1426     // branch.
1427     BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getIterator());
1428     TheSwitch->eraseFromParent();
1429     break;
1430   case 2:
1431     BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1432                        call, TheSwitch->getIterator());
1433     TheSwitch->eraseFromParent();
1434     break;
1435   default:
1436     // Otherwise, make the default destination of the switch instruction be one
1437     // of the other successors.
1438     TheSwitch->setCondition(call);
1439     TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1440     // Remove redundant case
1441     TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1442     break;
1443   }
1444 
1445   // Insert lifetime markers around the reloads of any output values. The
1446   // allocas output values are stored in are only in-use in the codeRepl block.
1447   insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1448 
1449   return call;
1450 }
1451 
1452 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1453   auto newFuncIt = newFunction->front().getIterator();
1454   for (BasicBlock *Block : Blocks) {
1455     // Delete the basic block from the old function, and the list of blocks
1456     Block->removeFromParent();
1457 
1458     // Insert this basic block into the new function
1459     // Insert the original blocks after the entry block created
1460     // for the new function. The entry block may be followed
1461     // by a set of exit blocks at this point, but these exit
1462     // blocks better be placed at the end of the new function.
1463     newFuncIt = newFunction->insert(std::next(newFuncIt), Block);
1464   }
1465 }
1466 
1467 void CodeExtractor::calculateNewCallTerminatorWeights(
1468     BasicBlock *CodeReplacer,
1469     DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
1470     BranchProbabilityInfo *BPI) {
1471   using Distribution = BlockFrequencyInfoImplBase::Distribution;
1472   using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1473 
1474   // Update the branch weights for the exit block.
1475   Instruction *TI = CodeReplacer->getTerminator();
1476   SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1477 
1478   // Block Frequency distribution with dummy node.
1479   Distribution BranchDist;
1480 
1481   SmallVector<BranchProbability, 4> EdgeProbabilities(
1482       TI->getNumSuccessors(), BranchProbability::getUnknown());
1483 
1484   // Add each of the frequencies of the successors.
1485   for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1486     BlockNode ExitNode(i);
1487     uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1488     if (ExitFreq != 0)
1489       BranchDist.addExit(ExitNode, ExitFreq);
1490     else
1491       EdgeProbabilities[i] = BranchProbability::getZero();
1492   }
1493 
1494   // Check for no total weight.
1495   if (BranchDist.Total == 0) {
1496     BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1497     return;
1498   }
1499 
1500   // Normalize the distribution so that they can fit in unsigned.
1501   BranchDist.normalize();
1502 
1503   // Create normalized branch weights and set the metadata.
1504   for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1505     const auto &Weight = BranchDist.Weights[I];
1506 
1507     // Get the weight and update the current BFI.
1508     BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1509     BranchProbability BP(Weight.Amount, BranchDist.Total);
1510     EdgeProbabilities[Weight.TargetNode.Index] = BP;
1511   }
1512   BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1513   TI->setMetadata(
1514       LLVMContext::MD_prof,
1515       MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1516 }
1517 
1518 /// Erase debug info intrinsics which refer to values in \p F but aren't in
1519 /// \p F.
1520 static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F) {
1521   for (Instruction &I : instructions(F)) {
1522     SmallVector<DbgVariableIntrinsic *, 4> DbgUsers;
1523     SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;
1524     findDbgUsers(DbgUsers, &I, &DbgVariableRecords);
1525     for (DbgVariableIntrinsic *DVI : DbgUsers)
1526       if (DVI->getFunction() != &F)
1527         DVI->eraseFromParent();
1528     for (DbgVariableRecord *DVR : DbgVariableRecords)
1529       if (DVR->getFunction() != &F)
1530         DVR->eraseFromParent();
1531   }
1532 }
1533 
1534 /// Fix up the debug info in the old and new functions by pointing line
1535 /// locations and debug intrinsics to the new subprogram scope, and by deleting
1536 /// intrinsics which point to values outside of the new function.
1537 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1538                                          CallInst &TheCall) {
1539   DISubprogram *OldSP = OldFunc.getSubprogram();
1540   LLVMContext &Ctx = OldFunc.getContext();
1541 
1542   if (!OldSP) {
1543     // Erase any debug info the new function contains.
1544     stripDebugInfo(NewFunc);
1545     // Make sure the old function doesn't contain any non-local metadata refs.
1546     eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1547     return;
1548   }
1549 
1550   // Create a subprogram for the new function. Leave out a description of the
1551   // function arguments, as the parameters don't correspond to anything at the
1552   // source level.
1553   assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1554   DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,
1555                 OldSP->getUnit());
1556   auto SPType =
1557       DIB.createSubroutineType(DIB.getOrCreateTypeArray(std::nullopt));
1558   DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1559                                     DISubprogram::SPFlagOptimized |
1560                                     DISubprogram::SPFlagLocalToUnit;
1561   auto NewSP = DIB.createFunction(
1562       OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1563       /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1564   NewFunc.setSubprogram(NewSP);
1565 
1566   auto IsInvalidLocation = [&NewFunc](Value *Location) {
1567     // Location is invalid if it isn't a constant or an instruction, or is an
1568     // instruction but isn't in the new function.
1569     if (!Location ||
1570         (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1571       return true;
1572     Instruction *LocationInst = dyn_cast<Instruction>(Location);
1573     return LocationInst && LocationInst->getFunction() != &NewFunc;
1574   };
1575 
1576   // Debug intrinsics in the new function need to be updated in one of two
1577   // ways:
1578   //  1) They need to be deleted, because they describe a value in the old
1579   //     function.
1580   //  2) They need to point to fresh metadata, e.g. because they currently
1581   //     point to a variable in the wrong scope.
1582   SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1583   SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1584   SmallVector<DbgVariableRecord *, 4> DVRsToDelete;
1585   DenseMap<const MDNode *, MDNode *> Cache;
1586 
1587   auto GetUpdatedDIVariable = [&](DILocalVariable *OldVar) {
1588     DINode *&NewVar = RemappedMetadata[OldVar];
1589     if (!NewVar) {
1590       DILocalScope *NewScope = DILocalScope::cloneScopeForSubprogram(
1591           *OldVar->getScope(), *NewSP, Ctx, Cache);
1592       NewVar = DIB.createAutoVariable(
1593           NewScope, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1594           OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1595           OldVar->getAlignInBits());
1596     }
1597     return cast<DILocalVariable>(NewVar);
1598   };
1599 
1600   auto UpdateDbgLabel = [&](auto *LabelRecord) {
1601     // Point the label record to a fresh label within the new function if
1602     // the record was not inlined from some other function.
1603     if (LabelRecord->getDebugLoc().getInlinedAt())
1604       return;
1605     DILabel *OldLabel = LabelRecord->getLabel();
1606     DINode *&NewLabel = RemappedMetadata[OldLabel];
1607     if (!NewLabel) {
1608       DILocalScope *NewScope = DILocalScope::cloneScopeForSubprogram(
1609           *OldLabel->getScope(), *NewSP, Ctx, Cache);
1610       NewLabel = DILabel::get(Ctx, NewScope, OldLabel->getName(),
1611                               OldLabel->getFile(), OldLabel->getLine());
1612     }
1613     LabelRecord->setLabel(cast<DILabel>(NewLabel));
1614   };
1615 
1616   auto UpdateDbgRecordsOnInst = [&](Instruction &I) -> void {
1617     for (DbgRecord &DR : I.getDbgRecordRange()) {
1618       if (DbgLabelRecord *DLR = dyn_cast<DbgLabelRecord>(&DR)) {
1619         UpdateDbgLabel(DLR);
1620         continue;
1621       }
1622 
1623       DbgVariableRecord &DVR = cast<DbgVariableRecord>(DR);
1624       // Apply the two updates that dbg.values get: invalid operands, and
1625       // variable metadata fixup.
1626       if (any_of(DVR.location_ops(), IsInvalidLocation)) {
1627         DVRsToDelete.push_back(&DVR);
1628         continue;
1629       }
1630       if (DVR.isDbgAssign() && IsInvalidLocation(DVR.getAddress())) {
1631         DVRsToDelete.push_back(&DVR);
1632         continue;
1633       }
1634       if (!DVR.getDebugLoc().getInlinedAt())
1635         DVR.setVariable(GetUpdatedDIVariable(DVR.getVariable()));
1636     }
1637   };
1638 
1639   for (Instruction &I : instructions(NewFunc)) {
1640     UpdateDbgRecordsOnInst(I);
1641 
1642     auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1643     if (!DII)
1644       continue;
1645 
1646     // Point the intrinsic to a fresh label within the new function if the
1647     // intrinsic was not inlined from some other function.
1648     if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1649       UpdateDbgLabel(DLI);
1650       continue;
1651     }
1652 
1653     auto *DVI = cast<DbgVariableIntrinsic>(DII);
1654     // If any of the used locations are invalid, delete the intrinsic.
1655     if (any_of(DVI->location_ops(), IsInvalidLocation)) {
1656       DebugIntrinsicsToDelete.push_back(DVI);
1657       continue;
1658     }
1659     // DbgAssign intrinsics have an extra Value argument:
1660     if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
1661         DAI && IsInvalidLocation(DAI->getAddress())) {
1662       DebugIntrinsicsToDelete.push_back(DVI);
1663       continue;
1664     }
1665     // If the variable was in the scope of the old function, i.e. it was not
1666     // inlined, point the intrinsic to a fresh variable within the new function.
1667     if (!DVI->getDebugLoc().getInlinedAt())
1668       DVI->setVariable(GetUpdatedDIVariable(DVI->getVariable()));
1669   }
1670 
1671   for (auto *DII : DebugIntrinsicsToDelete)
1672     DII->eraseFromParent();
1673   for (auto *DVR : DVRsToDelete)
1674     DVR->getMarker()->MarkedInstr->dropOneDbgRecord(DVR);
1675   DIB.finalizeSubprogram(NewSP);
1676 
1677   // Fix up the scope information attached to the line locations and the
1678   // debug assignment metadata in the new function.
1679   DenseMap<DIAssignID *, DIAssignID *> AssignmentIDMap;
1680   for (Instruction &I : instructions(NewFunc)) {
1681     if (const DebugLoc &DL = I.getDebugLoc())
1682       I.setDebugLoc(
1683           DebugLoc::replaceInlinedAtSubprogram(DL, *NewSP, Ctx, Cache));
1684     for (DbgRecord &DR : I.getDbgRecordRange())
1685       DR.setDebugLoc(DebugLoc::replaceInlinedAtSubprogram(DR.getDebugLoc(),
1686                                                           *NewSP, Ctx, Cache));
1687 
1688     // Loop info metadata may contain line locations. Fix them up.
1689     auto updateLoopInfoLoc = [&Ctx, &Cache, NewSP](Metadata *MD) -> Metadata * {
1690       if (auto *Loc = dyn_cast_or_null<DILocation>(MD))
1691         return DebugLoc::replaceInlinedAtSubprogram(Loc, *NewSP, Ctx, Cache);
1692       return MD;
1693     };
1694     updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1695     at::remapAssignID(AssignmentIDMap, I);
1696   }
1697   if (!TheCall.getDebugLoc())
1698     TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP));
1699 
1700   eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1701 }
1702 
1703 Function *
1704 CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) {
1705   ValueSet Inputs, Outputs;
1706   return extractCodeRegion(CEAC, Inputs, Outputs);
1707 }
1708 
1709 Function *
1710 CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC,
1711                                  ValueSet &inputs, ValueSet &outputs) {
1712   if (!isEligible())
1713     return nullptr;
1714 
1715   // Assumption: this is a single-entry code region, and the header is the first
1716   // block in the region.
1717   BasicBlock *header = *Blocks.begin();
1718   Function *oldFunction = header->getParent();
1719 
1720   // Calculate the entry frequency of the new function before we change the root
1721   //   block.
1722   BlockFrequency EntryFreq;
1723   if (BFI) {
1724     assert(BPI && "Both BPI and BFI are required to preserve profile info");
1725     for (BasicBlock *Pred : predecessors(header)) {
1726       if (Blocks.count(Pred))
1727         continue;
1728       EntryFreq +=
1729           BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1730     }
1731   }
1732 
1733   // Remove @llvm.assume calls that will be moved to the new function from the
1734   // old function's assumption cache.
1735   for (BasicBlock *Block : Blocks) {
1736     for (Instruction &I : llvm::make_early_inc_range(*Block)) {
1737       if (auto *AI = dyn_cast<AssumeInst>(&I)) {
1738         if (AC)
1739           AC->unregisterAssumption(AI);
1740         AI->eraseFromParent();
1741       }
1742     }
1743   }
1744 
1745   // If we have any return instructions in the region, split those blocks so
1746   // that the return is not in the region.
1747   splitReturnBlocks();
1748 
1749   // Calculate the exit blocks for the extracted region and the total exit
1750   // weights for each of those blocks.
1751   DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
1752   SetVector<BasicBlock *> ExitBlocks;
1753   for (BasicBlock *Block : Blocks) {
1754     for (BasicBlock *Succ : successors(Block)) {
1755       if (!Blocks.count(Succ)) {
1756         // Update the branch weight for this successor.
1757         if (BFI) {
1758           BlockFrequency &BF = ExitWeights[Succ];
1759           BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ);
1760         }
1761         ExitBlocks.insert(Succ);
1762       }
1763     }
1764   }
1765   NumExitBlocks = ExitBlocks.size();
1766 
1767   for (BasicBlock *Block : Blocks) {
1768     for (BasicBlock *OldTarget : successors(Block))
1769       if (!Blocks.contains(OldTarget))
1770         OldTargets.push_back(OldTarget);
1771   }
1772 
1773   // If we have to split PHI nodes of the entry or exit blocks, do so now.
1774   severSplitPHINodesOfEntry(header);
1775   severSplitPHINodesOfExits(ExitBlocks);
1776 
1777   // This takes place of the original loop
1778   BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1779                                                 "codeRepl", oldFunction,
1780                                                 header);
1781   codeReplacer->IsNewDbgInfoFormat = oldFunction->IsNewDbgInfoFormat;
1782 
1783   // The new function needs a root node because other nodes can branch to the
1784   // head of the region, but the entry node of a function cannot have preds.
1785   BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1786                                                "newFuncRoot");
1787   newFuncRoot->IsNewDbgInfoFormat = oldFunction->IsNewDbgInfoFormat;
1788 
1789   auto *BranchI = BranchInst::Create(header);
1790   // If the original function has debug info, we have to add a debug location
1791   // to the new branch instruction from the artificial entry block.
1792   // We use the debug location of the first instruction in the extracted
1793   // blocks, as there is no other equivalent line in the source code.
1794   if (oldFunction->getSubprogram()) {
1795     any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1796       return any_of(*BB, [&BranchI](const Instruction &I) {
1797         if (!I.getDebugLoc())
1798           return false;
1799         // Don't use source locations attached to debug-intrinsics: they could
1800         // be from completely unrelated scopes.
1801         if (isa<DbgInfoIntrinsic>(I))
1802           return false;
1803         BranchI->setDebugLoc(I.getDebugLoc());
1804         return true;
1805       });
1806     });
1807   }
1808   BranchI->insertInto(newFuncRoot, newFuncRoot->end());
1809 
1810   ValueSet SinkingCands, HoistingCands;
1811   BasicBlock *CommonExit = nullptr;
1812   findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1813   assert(HoistingCands.empty() || CommonExit);
1814 
1815   // Find inputs to, outputs from the code region.
1816   findInputsOutputs(inputs, outputs, SinkingCands);
1817 
1818   // Now sink all instructions which only have non-phi uses inside the region.
1819   // Group the allocas at the start of the block, so that any bitcast uses of
1820   // the allocas are well-defined.
1821   AllocaInst *FirstSunkAlloca = nullptr;
1822   for (auto *II : SinkingCands) {
1823     if (auto *AI = dyn_cast<AllocaInst>(II)) {
1824       AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1825       if (!FirstSunkAlloca)
1826         FirstSunkAlloca = AI;
1827     }
1828   }
1829   assert((SinkingCands.empty() || FirstSunkAlloca) &&
1830          "Did not expect a sink candidate without any allocas");
1831   for (auto *II : SinkingCands) {
1832     if (!isa<AllocaInst>(II)) {
1833       cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1834     }
1835   }
1836 
1837   if (!HoistingCands.empty()) {
1838     auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1839     Instruction *TI = HoistToBlock->getTerminator();
1840     for (auto *II : HoistingCands)
1841       cast<Instruction>(II)->moveBefore(TI);
1842   }
1843 
1844   // Collect objects which are inputs to the extraction region and also
1845   // referenced by lifetime start markers within it. The effects of these
1846   // markers must be replicated in the calling function to prevent the stack
1847   // coloring pass from merging slots which store input objects.
1848   ValueSet LifetimesStart;
1849   eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1850 
1851   // Construct new function based on inputs/outputs & add allocas for all defs.
1852   Function *newFunction =
1853       constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1854                         oldFunction, oldFunction->getParent());
1855 
1856   // Update the entry count of the function.
1857   if (BFI) {
1858     auto Count = BFI->getProfileCountFromFreq(EntryFreq);
1859     if (Count)
1860       newFunction->setEntryCount(
1861           ProfileCount(*Count, Function::PCT_Real)); // FIXME
1862     BFI->setBlockFreq(codeReplacer, EntryFreq);
1863   }
1864 
1865   CallInst *TheCall =
1866       emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1867 
1868   moveCodeToFunction(newFunction);
1869 
1870   // Replicate the effects of any lifetime start/end markers which referenced
1871   // input objects in the extraction region by placing markers around the call.
1872   insertLifetimeMarkersSurroundingCall(
1873       oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1874 
1875   // Propagate personality info to the new function if there is one.
1876   if (oldFunction->hasPersonalityFn())
1877     newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1878 
1879   // Update the branch weights for the exit block.
1880   if (BFI && NumExitBlocks > 1)
1881     calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1882 
1883   // Loop over all of the PHI nodes in the header and exit blocks, and change
1884   // any references to the old incoming edge to be the new incoming edge.
1885   for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1886     PHINode *PN = cast<PHINode>(I);
1887     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1888       if (!Blocks.count(PN->getIncomingBlock(i)))
1889         PN->setIncomingBlock(i, newFuncRoot);
1890   }
1891 
1892   for (BasicBlock *ExitBB : ExitBlocks)
1893     for (PHINode &PN : ExitBB->phis()) {
1894       Value *IncomingCodeReplacerVal = nullptr;
1895       for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1896         // Ignore incoming values from outside of the extracted region.
1897         if (!Blocks.count(PN.getIncomingBlock(i)))
1898           continue;
1899 
1900         // Ensure that there is only one incoming value from codeReplacer.
1901         if (!IncomingCodeReplacerVal) {
1902           PN.setIncomingBlock(i, codeReplacer);
1903           IncomingCodeReplacerVal = PN.getIncomingValue(i);
1904         } else
1905           assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1906                  "PHI has two incompatbile incoming values from codeRepl");
1907       }
1908     }
1909 
1910   fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1911 
1912   LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1913     newFunction->dump();
1914     report_fatal_error("verification of newFunction failed!");
1915   });
1916   LLVM_DEBUG(if (verifyFunction(*oldFunction))
1917              report_fatal_error("verification of oldFunction failed!"));
1918   LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1919                  report_fatal_error("Stale Asumption cache for old Function!"));
1920   return newFunction;
1921 }
1922 
1923 bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc,
1924                                           const Function &NewFunc,
1925                                           AssumptionCache *AC) {
1926   for (auto AssumeVH : AC->assumptions()) {
1927     auto *I = dyn_cast_or_null<CallInst>(AssumeVH);
1928     if (!I)
1929       continue;
1930 
1931     // There shouldn't be any llvm.assume intrinsics in the new function.
1932     if (I->getFunction() != &OldFunc)
1933       return true;
1934 
1935     // There shouldn't be any stale affected values in the assumption cache
1936     // that were previously in the old function, but that have now been moved
1937     // to the new function.
1938     for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1939       auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1940       if (!AffectedCI)
1941         continue;
1942       if (AffectedCI->getFunction() != &OldFunc)
1943         return true;
1944       auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1945       if (AssumedInst->getFunction() != &OldFunc)
1946         return true;
1947     }
1948   }
1949   return false;
1950 }
1951 
1952 void CodeExtractor::excludeArgFromAggregate(Value *Arg) {
1953   ExcludeArgsFromAggregate.insert(Arg);
1954 }
1955