contrib/llvm-project/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::NoUndef:
 881       case Attribute::None:
 882       case Attribute::NonNull:
 883       case Attribute::Preallocated:
 884       case Attribute::ReadNone:
 885       case Attribute::ReadOnly:
 886       case Attribute::Returned:
 887       case Attribute::ReturnsTwice:
 888       case Attribute::SExt:
 889       case Attribute::Speculatable:
 890       case Attribute::StackAlignment:
 891       case Attribute::StructRet:
 892       case Attribute::SwiftError:
 893       case Attribute::SwiftSelf:
 894       case Attribute::WillReturn:
 895       case Attribute::WriteOnly:
 896       case Attribute::ZExt:
 897       case Attribute::ImmArg:
 898       case Attribute::EndAttrKinds:
 899       case Attribute::EmptyKey:
 900       case Attribute::TombstoneKey:
 901         continue;
 902       // Those attributes should be safe to propagate to the extracted function.
 903       case Attribute::AlwaysInline:
 904       case Attribute::Cold:
 905       case Attribute::NoRecurse:
 906       case Attribute::InlineHint:
 907       case Attribute::MinSize:
 908       case Attribute::NoDuplicate:
 909       case Attribute::NoFree:
 910       case Attribute::NoImplicitFloat:
 911       case Attribute::NoInline:
 912       case Attribute::NonLazyBind:
 913       case Attribute::NoRedZone:
 914       case Attribute::NoUnwind:
 915       case Attribute::NullPointerIsValid:
 916       case Attribute::OptForFuzzing:
 917       case Attribute::OptimizeNone:
 918       case Attribute::OptimizeForSize:
 919       case Attribute::SafeStack:
 920       case Attribute::ShadowCallStack:
 921       case Attribute::SanitizeAddress:
 922       case Attribute::SanitizeMemory:
 923       case Attribute::SanitizeThread:
 924       case Attribute::SanitizeHWAddress:
 925       case Attribute::SanitizeMemTag:
 926       case Attribute::SpeculativeLoadHardening:
 927       case Attribute::StackProtect:
 928       case Attribute::StackProtectReq:
 929       case Attribute::StackProtectStrong:
 930       case Attribute::StrictFP:
 931       case Attribute::UWTable:
 932       case Attribute::NoCfCheck:
 933         break;
 934       }
 935
 936     newFunction->addFnAttr(Attr);
 937   }
 938   newFunction->getBasicBlockList().push_back(newRootNode);
 939
 940   // Create an iterator to name all of the arguments we inserted.
 941   Function::arg_iterator AI = newFunction->arg_begin();
 942
 943   // Rewrite all users of the inputs in the extracted region to use the
 944   // arguments (or appropriate addressing into struct) instead.
 945   for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
 946     Value *RewriteVal;
 947     if (AggregateArgs) {
 948       Value *Idx[2];
 949       Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
 950       Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
 951       Instruction *TI = newFunction->begin()->getTerminator();
 952       GetElementPtrInst *GEP = GetElementPtrInst::Create(
 953           StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
 954       RewriteVal = new LoadInst(StructTy->getElementType(i), GEP,
 955                                 "loadgep_" + inputs[i]->getName(), TI);
 956     } else
 957       RewriteVal = &*AI++;
 958
 959     std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
 960     for (User *use : Users)
 961       if (Instruction *inst = dyn_cast<Instruction>(use))
 962         if (Blocks.count(inst->getParent()))
 963           inst->replaceUsesOfWith(inputs[i], RewriteVal);
 964   }
 965
 966   // Set names for input and output arguments.
 967   if (!AggregateArgs) {
 968     AI = newFunction->arg_begin();
 969     for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
 970       AI->setName(inputs[i]->getName());
 971     for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
 972       AI->setName(outputs[i]->getName()+".out");
 973   }
 974
 975   // Rewrite branches to basic blocks outside of the loop to new dummy blocks
 976   // within the new function. This must be done before we lose track of which
 977   // blocks were originally in the code region.
 978   std::vector<User *> Users(header->user_begin(), header->user_end());
 979   for (auto &U : Users)
 980     // The BasicBlock which contains the branch is not in the region
 981     // modify the branch target to a new block
 982     if (Instruction *I = dyn_cast<Instruction>(U))
 983       if (I->isTerminator() && I->getFunction() == oldFunction &&
 984           !Blocks.count(I->getParent()))
 985         I->replaceUsesOfWith(header, newHeader);
 986
 987   return newFunction;
 988 }
 989
 990 /// Erase lifetime.start markers which reference inputs to the extraction
 991 /// region, and insert the referenced memory into \p LifetimesStart.
 992 ///
 993 /// The extraction region is defined by a set of blocks (\p Blocks), and a set
 994 /// of allocas which will be moved from the caller function into the extracted
 995 /// function (\p SunkAllocas).
 996 static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks,
 997                                          const SetVector<Value *> &SunkAllocas,
 998                                          SetVector<Value *> &LifetimesStart) {
 999   for (BasicBlock *BB : Blocks) {
1000     for (auto It = BB->begin(), End = BB->end(); It != End;) {
1001       auto *II = dyn_cast<IntrinsicInst>(&*It);
1002       ++It;
1003       if (!II || !II->isLifetimeStartOrEnd())
1004         continue;
1005
1006       // Get the memory operand of the lifetime marker. If the underlying
1007       // object is a sunk alloca, or is otherwise defined in the extraction
1008       // region, the lifetime marker must not be erased.
1009       Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1010       if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1011         continue;
1012
1013       if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1014         LifetimesStart.insert(Mem);
1015       II->eraseFromParent();
1016     }
1017   }
1018 }
1019
1020 /// Insert lifetime start/end markers surrounding the call to the new function
1021 /// for objects defined in the caller.
1022 static void insertLifetimeMarkersSurroundingCall(
1023     Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1024     CallInst *TheCall) {
1025   LLVMContext &Ctx = M->getContext();
1026   auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
1027   auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1028   Instruction *Term = TheCall->getParent()->getTerminator();
1029
1030   // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
1031   // needed to satisfy this requirement so they may be reused.
1032   DenseMap<Value *, Value *> Bitcasts;
1033
1034   // Emit lifetime markers for the pointers given in \p Objects. Insert the
1035   // markers before the call if \p InsertBefore, and after the call otherwise.
1036   auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
1037                            bool InsertBefore) {
1038     for (Value *Mem : Objects) {
1039       assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1040                                             TheCall->getFunction()) &&
1041              "Input memory not defined in original function");
1042       Value *&MemAsI8Ptr = Bitcasts[Mem];
1043       if (!MemAsI8Ptr) {
1044         if (Mem->getType() == Int8PtrTy)
1045           MemAsI8Ptr = Mem;
1046         else
1047           MemAsI8Ptr =
1048               CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
1049       }
1050
1051       auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
1052       if (InsertBefore)
1053         Marker->insertBefore(TheCall);
1054       else
1055         Marker->insertBefore(Term);
1056     }
1057   };
1058
1059   if (!LifetimesStart.empty()) {
1060     auto StartFn = llvm::Intrinsic::getDeclaration(
1061         M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
1062     insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
1063   }
1064
1065   if (!LifetimesEnd.empty()) {
1066     auto EndFn = llvm::Intrinsic::getDeclaration(
1067         M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
1068     insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
1069   }
1070 }
1071
1072 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
1073 /// the call instruction, splitting any PHI nodes in the header block as
1074 /// necessary.
1075 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1076                                                     BasicBlock *codeReplacer,
1077                                                     ValueSet &inputs,
1078                                                     ValueSet &outputs) {
1079   // Emit a call to the new function, passing in: *pointer to struct (if
1080   // aggregating parameters), or plan inputs and allocated memory for outputs
1081   std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
1082
1083   Module *M = newFunction->getParent();
1084   LLVMContext &Context = M->getContext();
1085   const DataLayout &DL = M->getDataLayout();
1086   CallInst *call = nullptr;
1087
1088   // Add inputs as params, or to be filled into the struct
1089   unsigned ArgNo = 0;
1090   SmallVector<unsigned, 1> SwiftErrorArgs;
1091   for (Value *input : inputs) {
1092     if (AggregateArgs)
1093       StructValues.push_back(input);
1094     else {
1095       params.push_back(input);
1096       if (input->isSwiftError())
1097         SwiftErrorArgs.push_back(ArgNo);
1098     }
1099     ++ArgNo;
1100   }
1101
1102   // Create allocas for the outputs
1103   for (Value *output : outputs) {
1104     if (AggregateArgs) {
1105       StructValues.push_back(output);
1106     } else {
1107       AllocaInst *alloca =
1108         new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1109                        nullptr, output->getName() + ".loc",
1110                        &codeReplacer->getParent()->front().front());
1111       ReloadOutputs.push_back(alloca);
1112       params.push_back(alloca);
1113     }
1114   }
1115
1116   StructType *StructArgTy = nullptr;
1117   AllocaInst *Struct = nullptr;
1118   if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
1119     std::vector<Type *> ArgTypes;
1120     for (ValueSet::iterator v = StructValues.begin(),
1121            ve = StructValues.end(); v != ve; ++v)
1122       ArgTypes.push_back((*v)->getType());
1123
1124     // Allocate a struct at the beginning of this function
1125     StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1126     Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
1127                             "structArg",
1128                             &codeReplacer->getParent()->front().front());
1129     params.push_back(Struct);
1130
1131     for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
1132       Value *Idx[2];
1133       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1134       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
1135       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1136           StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1137       codeReplacer->getInstList().push_back(GEP);
1138       new StoreInst(StructValues[i], GEP, codeReplacer);
1139     }
1140   }
1141
1142   // Emit the call to the function
1143   call = CallInst::Create(newFunction, params,
1144                           NumExitBlocks > 1 ? "targetBlock" : "");
1145   // Add debug location to the new call, if the original function has debug
1146   // info. In that case, the terminator of the entry block of the extracted
1147   // function contains the first debug location of the extracted function,
1148   // set in extractCodeRegion.
1149   if (codeReplacer->getParent()->getSubprogram()) {
1150     if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1151       call->setDebugLoc(DL);
1152   }
1153   codeReplacer->getInstList().push_back(call);
1154
1155   // Set swifterror parameter attributes.
1156   for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1157     call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1158     newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1159   }
1160
1161   Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
1162   unsigned FirstOut = inputs.size();
1163   if (!AggregateArgs)
1164     std::advance(OutputArgBegin, inputs.size());
1165
1166   // Reload the outputs passed in by reference.
1167   for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1168     Value *Output = nullptr;
1169     if (AggregateArgs) {
1170       Value *Idx[2];
1171       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1172       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1173       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1174           StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1175       codeReplacer->getInstList().push_back(GEP);
1176       Output = GEP;
1177     } else {
1178       Output = ReloadOutputs[i];
1179     }
1180     LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1181                                   outputs[i]->getName() + ".reload",
1182                                   codeReplacer);
1183     Reloads.push_back(load);
1184     std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1185     for (unsigned u = 0, e = Users.size(); u != e; ++u) {
1186       Instruction *inst = cast<Instruction>(Users[u]);
1187       if (!Blocks.count(inst->getParent()))
1188         inst->replaceUsesOfWith(outputs[i], load);
1189     }
1190   }
1191
1192   // Now we can emit a switch statement using the call as a value.
1193   SwitchInst *TheSwitch =
1194       SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
1195                          codeReplacer, 0, codeReplacer);
1196
1197   // Since there may be multiple exits from the original region, make the new
1198   // function return an unsigned, switch on that number.  This loop iterates
1199   // over all of the blocks in the extracted region, updating any terminator
1200   // instructions in the to-be-extracted region that branch to blocks that are
1201   // not in the region to be extracted.
1202   std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1203
1204   unsigned switchVal = 0;
1205   for (BasicBlock *Block : Blocks) {
1206     Instruction *TI = Block->getTerminator();
1207     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
1208       if (!Blocks.count(TI->getSuccessor(i))) {
1209         BasicBlock *OldTarget = TI->getSuccessor(i);
1210         // add a new basic block which returns the appropriate value
1211         BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1212         if (!NewTarget) {
1213           // If we don't already have an exit stub for this non-extracted
1214           // destination, create one now!
1215           NewTarget = BasicBlock::Create(Context,
1216                                          OldTarget->getName() + ".exitStub",
1217                                          newFunction);
1218           unsigned SuccNum = switchVal++;
1219
1220           Value *brVal = nullptr;
1221           switch (NumExitBlocks) {
1222           case 0:
1223           case 1: break;  // No value needed.
1224           case 2:         // Conditional branch, return a bool
1225             brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1226             break;
1227           default:
1228             brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1229             break;
1230           }
1231
1232           ReturnInst::Create(Context, brVal, NewTarget);
1233
1234           // Update the switch instruction.
1235           TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
1236                                               SuccNum),
1237                              OldTarget);
1238         }
1239
1240         // rewrite the original branch instruction with this new target
1241         TI->setSuccessor(i, NewTarget);
1242       }
1243   }
1244
1245   // Store the arguments right after the definition of output value.
1246   // This should be proceeded after creating exit stubs to be ensure that invoke
1247   // result restore will be placed in the outlined function.
1248   Function::arg_iterator OAI = OutputArgBegin;
1249   for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1250     auto *OutI = dyn_cast<Instruction>(outputs[i]);
1251     if (!OutI)
1252       continue;
1253
1254     // Find proper insertion point.
1255     BasicBlock::iterator InsertPt;
1256     // In case OutI is an invoke, we insert the store at the beginning in the
1257     // 'normal destination' BB. Otherwise we insert the store right after OutI.
1258     if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1259       InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1260     else if (auto *Phi = dyn_cast<PHINode>(OutI))
1261       InsertPt = Phi->getParent()->getFirstInsertionPt();
1262     else
1263       InsertPt = std::next(OutI->getIterator());
1264
1265     Instruction *InsertBefore = &*InsertPt;
1266     assert((InsertBefore->getFunction() == newFunction ||
1267             Blocks.count(InsertBefore->getParent())) &&
1268            "InsertPt should be in new function");
1269     assert(OAI != newFunction->arg_end() &&
1270            "Number of output arguments should match "
1271            "the amount of defined values");
1272     if (AggregateArgs) {
1273       Value *Idx[2];
1274       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1275       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1276       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1277           StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(),
1278           InsertBefore);
1279       new StoreInst(outputs[i], GEP, InsertBefore);
1280       // Since there should be only one struct argument aggregating
1281       // all the output values, we shouldn't increment OAI, which always
1282       // points to the struct argument, in this case.
1283     } else {
1284       new StoreInst(outputs[i], &*OAI, InsertBefore);
1285       ++OAI;
1286     }
1287   }
1288
1289   // Now that we've done the deed, simplify the switch instruction.
1290   Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1291   switch (NumExitBlocks) {
1292   case 0:
1293     // There are no successors (the block containing the switch itself), which
1294     // means that previously this was the last part of the function, and hence
1295     // this should be rewritten as a `ret'
1296
1297     // Check if the function should return a value
1298     if (OldFnRetTy->isVoidTy()) {
1299       ReturnInst::Create(Context, nullptr, TheSwitch);  // Return void
1300     } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1301       // return what we have
1302       ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1303     } else {
1304       // Otherwise we must have code extracted an unwind or something, just
1305       // return whatever we want.
1306       ReturnInst::Create(Context,
1307                          Constant::getNullValue(OldFnRetTy), TheSwitch);
1308     }
1309
1310     TheSwitch->eraseFromParent();
1311     break;
1312   case 1:
1313     // Only a single destination, change the switch into an unconditional
1314     // branch.
1315     BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1316     TheSwitch->eraseFromParent();
1317     break;
1318   case 2:
1319     BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1320                        call, TheSwitch);
1321     TheSwitch->eraseFromParent();
1322     break;
1323   default:
1324     // Otherwise, make the default destination of the switch instruction be one
1325     // of the other successors.
1326     TheSwitch->setCondition(call);
1327     TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1328     // Remove redundant case
1329     TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1330     break;
1331   }
1332
1333   // Insert lifetime markers around the reloads of any output values. The
1334   // allocas output values are stored in are only in-use in the codeRepl block.
1335   insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1336
1337   return call;
1338 }
1339
1340 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1341   Function *oldFunc = (*Blocks.begin())->getParent();
1342   Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1343   Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1344
1345   for (BasicBlock *Block : Blocks) {
1346     // Delete the basic block from the old function, and the list of blocks
1347     oldBlocks.remove(Block);
1348
1349     // Insert this basic block into the new function
1350     newBlocks.push_back(Block);
1351   }
1352 }
1353
1354 void CodeExtractor::calculateNewCallTerminatorWeights(
1355     BasicBlock *CodeReplacer,
1356     DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
1357     BranchProbabilityInfo *BPI) {
1358   using Distribution = BlockFrequencyInfoImplBase::Distribution;
1359   using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1360
1361   // Update the branch weights for the exit block.
1362   Instruction *TI = CodeReplacer->getTerminator();
1363   SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1364
1365   // Block Frequency distribution with dummy node.
1366   Distribution BranchDist;
1367
1368   SmallVector<BranchProbability, 4> EdgeProbabilities(
1369       TI->getNumSuccessors(), BranchProbability::getUnknown());
1370
1371   // Add each of the frequencies of the successors.
1372   for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1373     BlockNode ExitNode(i);
1374     uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1375     if (ExitFreq != 0)
1376       BranchDist.addExit(ExitNode, ExitFreq);
1377     else
1378       EdgeProbabilities[i] = BranchProbability::getZero();
1379   }
1380
1381   // Check for no total weight.
1382   if (BranchDist.Total == 0) {
1383     BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1384     return;
1385   }
1386
1387   // Normalize the distribution so that they can fit in unsigned.
1388   BranchDist.normalize();
1389
1390   // Create normalized branch weights and set the metadata.
1391   for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1392     const auto &Weight = BranchDist.Weights[I];
1393
1394     // Get the weight and update the current BFI.
1395     BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1396     BranchProbability BP(Weight.Amount, BranchDist.Total);
1397     EdgeProbabilities[Weight.TargetNode.Index] = BP;
1398   }
1399   BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1400   TI->setMetadata(
1401       LLVMContext::MD_prof,
1402       MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1403 }
1404
1405 /// Erase debug info intrinsics which refer to values in \p F but aren't in
1406 /// \p F.
1407 static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F) {
1408   for (Instruction &I : instructions(F)) {
1409     SmallVector<DbgVariableIntrinsic *, 4> DbgUsers;
1410     findDbgUsers(DbgUsers, &I);
1411     for (DbgVariableIntrinsic *DVI : DbgUsers)
1412       if (DVI->getFunction() != &F)
1413         DVI->eraseFromParent();
1414   }
1415 }
1416
1417 /// Fix up the debug info in the old and new functions by pointing line
1418 /// locations and debug intrinsics to the new subprogram scope, and by deleting
1419 /// intrinsics which point to values outside of the new function.
1420 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1421                                          CallInst &TheCall) {
1422   DISubprogram *OldSP = OldFunc.getSubprogram();
1423   LLVMContext &Ctx = OldFunc.getContext();
1424
1425   if (!OldSP) {
1426     // Erase any debug info the new function contains.
1427     stripDebugInfo(NewFunc);
1428     // Make sure the old function doesn't contain any non-local metadata refs.
1429     eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1430     return;
1431   }
1432
1433   // Create a subprogram for the new function. Leave out a description of the
1434   // function arguments, as the parameters don't correspond to anything at the
1435   // source level.
1436   assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1437   DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolvedNodes=*/false,
1438                 OldSP->getUnit());
1439   auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
1440   DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1441                                     DISubprogram::SPFlagOptimized |
1442                                     DISubprogram::SPFlagLocalToUnit;
1443   auto NewSP = DIB.createFunction(
1444       OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1445       /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1446   NewFunc.setSubprogram(NewSP);
1447
1448   // Debug intrinsics in the new function need to be updated in one of two
1449   // ways:
1450   //  1) They need to be deleted, because they describe a value in the old
1451   //     function.
1452   //  2) They need to point to fresh metadata, e.g. because they currently
1453   //     point to a variable in the wrong scope.
1454   SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1455   SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1456   for (Instruction &I : instructions(NewFunc)) {
1457     auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1458     if (!DII)
1459       continue;
1460
1461     // Point the intrinsic to a fresh label within the new function.
1462     if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1463       DILabel *OldLabel = DLI->getLabel();
1464       DINode *&NewLabel = RemappedMetadata[OldLabel];
1465       if (!NewLabel)
1466         NewLabel = DILabel::get(Ctx, NewSP, OldLabel->getName(),
1467                                 OldLabel->getFile(), OldLabel->getLine());
1468       DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
1469       continue;
1470     }
1471
1472     // If the location isn't a constant or an instruction, delete the
1473     // intrinsic.
1474     auto *DVI = cast<DbgVariableIntrinsic>(DII);
1475     Value *Location = DVI->getVariableLocation();
1476     if (!Location ||
1477         (!isa<Constant>(Location) && !isa<Instruction>(Location))) {
1478       DebugIntrinsicsToDelete.push_back(DVI);
1479       continue;
1480     }
1481
1482     // If the variable location is an instruction but isn't in the new
1483     // function, delete the intrinsic.
1484     Instruction *LocationInst = dyn_cast<Instruction>(Location);
1485     if (LocationInst && LocationInst->getFunction() != &NewFunc) {
1486       DebugIntrinsicsToDelete.push_back(DVI);
1487       continue;
1488     }
1489
1490     // Point the intrinsic to a fresh variable within the new function.
1491     DILocalVariable *OldVar = DVI->getVariable();
1492     DINode *&NewVar = RemappedMetadata[OldVar];
1493     if (!NewVar)
1494       NewVar = DIB.createAutoVariable(
1495           NewSP, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1496           OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1497           OldVar->getAlignInBits());
1498     DVI->setArgOperand(1, MetadataAsValue::get(Ctx, NewVar));
1499   }
1500   for (auto *DII : DebugIntrinsicsToDelete)
1501     DII->eraseFromParent();
1502   DIB.finalizeSubprogram(NewSP);
1503
1504   // Fix up the scope information attached to the line locations in the new
1505   // function.
1506   for (Instruction &I : instructions(NewFunc)) {
1507     if (const DebugLoc &DL = I.getDebugLoc())
1508       I.setDebugLoc(DebugLoc::get(DL.getLine(), DL.getCol(), NewSP));
1509
1510     // Loop info metadata may contain line locations. Fix them up.
1511     auto updateLoopInfoLoc = [&Ctx,
1512                               NewSP](const DILocation &Loc) -> DILocation * {
1513       return DILocation::get(Ctx, Loc.getLine(), Loc.getColumn(), NewSP,
1514                              nullptr);
1515     };
1516     updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1517   }
1518   if (!TheCall.getDebugLoc())
1519     TheCall.setDebugLoc(DebugLoc::get(0, 0, OldSP));
1520
1521   eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1522 }
1523
1524 Function *
1525 CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) {
1526   if (!isEligible())
1527     return nullptr;
1528
1529   // Assumption: this is a single-entry code region, and the header is the first
1530   // block in the region.
1531   BasicBlock *header = *Blocks.begin();
1532   Function *oldFunction = header->getParent();
1533
1534   // Calculate the entry frequency of the new function before we change the root
1535   //   block.
1536   BlockFrequency EntryFreq;
1537   if (BFI) {
1538     assert(BPI && "Both BPI and BFI are required to preserve profile info");
1539     for (BasicBlock *Pred : predecessors(header)) {
1540       if (Blocks.count(Pred))
1541         continue;
1542       EntryFreq +=
1543           BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1544     }
1545   }
1546
1547   // Remove @llvm.assume calls that will be moved to the new function from the
1548   // old function's assumption cache.
1549   for (BasicBlock *Block : Blocks) {
1550     for (auto It = Block->begin(), End = Block->end(); It != End;) {
1551       Instruction *I = &*It;
1552       ++It;
1553
1554       if (match(I, m_Intrinsic<Intrinsic::assume>())) {
1555         if (AC)
1556           AC->unregisterAssumption(cast<CallInst>(I));
1557         I->eraseFromParent();
1558       }
1559     }
1560   }
1561
1562   // If we have any return instructions in the region, split those blocks so
1563   // that the return is not in the region.
1564   splitReturnBlocks();
1565
1566   // Calculate the exit blocks for the extracted region and the total exit
1567   // weights for each of those blocks.
1568   DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
1569   SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1570   for (BasicBlock *Block : Blocks) {
1571     for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
1572          ++SI) {
1573       if (!Blocks.count(*SI)) {
1574         // Update the branch weight for this successor.
1575         if (BFI) {
1576           BlockFrequency &BF = ExitWeights[*SI];
1577           BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
1578         }
1579         ExitBlocks.insert(*SI);
1580       }
1581     }
1582   }
1583   NumExitBlocks = ExitBlocks.size();
1584
1585   // If we have to split PHI nodes of the entry or exit blocks, do so now.
1586   severSplitPHINodesOfEntry(header);
1587   severSplitPHINodesOfExits(ExitBlocks);
1588
1589   // This takes place of the original loop
1590   BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1591                                                 "codeRepl", oldFunction,
1592                                                 header);
1593
1594   // The new function needs a root node because other nodes can branch to the
1595   // head of the region, but the entry node of a function cannot have preds.
1596   BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1597                                                "newFuncRoot");
1598   auto *BranchI = BranchInst::Create(header);
1599   // If the original function has debug info, we have to add a debug location
1600   // to the new branch instruction from the artificial entry block.
1601   // We use the debug location of the first instruction in the extracted
1602   // blocks, as there is no other equivalent line in the source code.
1603   if (oldFunction->getSubprogram()) {
1604     any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1605       return any_of(*BB, [&BranchI](const Instruction &I) {
1606         if (!I.getDebugLoc())
1607           return false;
1608         BranchI->setDebugLoc(I.getDebugLoc());
1609         return true;
1610       });
1611     });
1612   }
1613   newFuncRoot->getInstList().push_back(BranchI);
1614
1615   ValueSet inputs, outputs, SinkingCands, HoistingCands;
1616   BasicBlock *CommonExit = nullptr;
1617   findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1618   assert(HoistingCands.empty() || CommonExit);
1619
1620   // Find inputs to, outputs from the code region.
1621   findInputsOutputs(inputs, outputs, SinkingCands);
1622
1623   // Now sink all instructions which only have non-phi uses inside the region.
1624   // Group the allocas at the start of the block, so that any bitcast uses of
1625   // the allocas are well-defined.
1626   AllocaInst *FirstSunkAlloca = nullptr;
1627   for (auto *II : SinkingCands) {
1628     if (auto *AI = dyn_cast<AllocaInst>(II)) {
1629       AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1630       if (!FirstSunkAlloca)
1631         FirstSunkAlloca = AI;
1632     }
1633   }
1634   assert((SinkingCands.empty() || FirstSunkAlloca) &&
1635          "Did not expect a sink candidate without any allocas");
1636   for (auto *II : SinkingCands) {
1637     if (!isa<AllocaInst>(II)) {
1638       cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1639     }
1640   }
1641
1642   if (!HoistingCands.empty()) {
1643     auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1644     Instruction *TI = HoistToBlock->getTerminator();
1645     for (auto *II : HoistingCands)
1646       cast<Instruction>(II)->moveBefore(TI);
1647   }
1648
1649   // Collect objects which are inputs to the extraction region and also
1650   // referenced by lifetime start markers within it. The effects of these
1651   // markers must be replicated in the calling function to prevent the stack
1652   // coloring pass from merging slots which store input objects.
1653   ValueSet LifetimesStart;
1654   eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1655
1656   // Construct new function based on inputs/outputs & add allocas for all defs.
1657   Function *newFunction =
1658       constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1659                         oldFunction, oldFunction->getParent());
1660
1661   // Update the entry count of the function.
1662   if (BFI) {
1663     auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1664     if (Count.hasValue())
1665       newFunction->setEntryCount(
1666           ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1667     BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1668   }
1669
1670   CallInst *TheCall =
1671       emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1672
1673   moveCodeToFunction(newFunction);
1674
1675   // Replicate the effects of any lifetime start/end markers which referenced
1676   // input objects in the extraction region by placing markers around the call.
1677   insertLifetimeMarkersSurroundingCall(
1678       oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1679
1680   // Propagate personality info to the new function if there is one.
1681   if (oldFunction->hasPersonalityFn())
1682     newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1683
1684   // Update the branch weights for the exit block.
1685   if (BFI && NumExitBlocks > 1)
1686     calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1687
1688   // Loop over all of the PHI nodes in the header and exit blocks, and change
1689   // any references to the old incoming edge to be the new incoming edge.
1690   for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1691     PHINode *PN = cast<PHINode>(I);
1692     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1693       if (!Blocks.count(PN->getIncomingBlock(i)))
1694         PN->setIncomingBlock(i, newFuncRoot);
1695   }
1696
1697   for (BasicBlock *ExitBB : ExitBlocks)
1698     for (PHINode &PN : ExitBB->phis()) {
1699       Value *IncomingCodeReplacerVal = nullptr;
1700       for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1701         // Ignore incoming values from outside of the extracted region.
1702         if (!Blocks.count(PN.getIncomingBlock(i)))
1703           continue;
1704
1705         // Ensure that there is only one incoming value from codeReplacer.
1706         if (!IncomingCodeReplacerVal) {
1707           PN.setIncomingBlock(i, codeReplacer);
1708           IncomingCodeReplacerVal = PN.getIncomingValue(i);
1709         } else
1710           assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1711                  "PHI has two incompatbile incoming values from codeRepl");
1712       }
1713     }
1714
1715   fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1716
1717   // Mark the new function `noreturn` if applicable. Terminators which resume
1718   // exception propagation are treated as returning instructions. This is to
1719   // avoid inserting traps after calls to outlined functions which unwind.
1720   bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1721     const Instruction *Term = BB.getTerminator();
1722     return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1723   });
1724   if (doesNotReturn)
1725     newFunction->setDoesNotReturn();
1726
1727   LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1728     newFunction->dump();
1729     report_fatal_error("verification of newFunction failed!");
1730   });
1731   LLVM_DEBUG(if (verifyFunction(*oldFunction))
1732              report_fatal_error("verification of oldFunction failed!"));
1733   LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1734                  report_fatal_error("Stale Asumption cache for old Function!"));
1735   return newFunction;
1736 }
1737
1738 bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc,
1739                                           const Function &NewFunc,
1740                                           AssumptionCache *AC) {
1741   for (auto AssumeVH : AC->assumptions()) {
1742     CallInst *I = dyn_cast_or_null<CallInst>(AssumeVH);
1743     if (!I)
1744       continue;
1745
1746     // There shouldn't be any llvm.assume intrinsics in the new function.
1747     if (I->getFunction() != &OldFunc)
1748       return true;
1749
1750     // There shouldn't be any stale affected values in the assumption cache
1751     // that were previously in the old function, but that have now been moved
1752     // to the new function.
1753     for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1754       CallInst *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1755       if (!AffectedCI)
1756         continue;
1757       if (AffectedCI->getFunction() != &OldFunc)
1758         return true;
1759       auto *AssumedInst = dyn_cast<Instruction>(AffectedCI->getOperand(0));
1760       if (AssumedInst->getFunction() != &OldFunc)
1761         return true;
1762     }
1763   }
1764   return false;
1765 }