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