lib/Transforms/Utils/CodeExtractor.cpp

   1 //===- CodeExtractor.cpp - Pull code region into a new function -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the interface to tear out a code region, such as an
  11 // individual loop or a parallel section, into a new function, replacing it with
  12 // a call to the new function.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Utils/CodeExtractor.h"
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/Optional.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/ADT/SetVector.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/Analysis/BlockFrequencyInfo.h"
  25 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
  26 #include "llvm/Analysis/BranchProbabilityInfo.h"
  27 #include "llvm/Analysis/LoopInfo.h"
  28 #include "llvm/IR/Argument.h"
  29 #include "llvm/IR/Attributes.h"
  30 #include "llvm/IR/BasicBlock.h"
  31 #include "llvm/IR/CFG.h"
  32 #include "llvm/IR/Constant.h"
  33 #include "llvm/IR/Constants.h"
  34 #include "llvm/IR/DataLayout.h"
  35 #include "llvm/IR/DerivedTypes.h"
  36 #include "llvm/IR/Dominators.h"
  37 #include "llvm/IR/Function.h"
  38 #include "llvm/IR/GlobalValue.h"
  39 #include "llvm/IR/InstrTypes.h"
  40 #include "llvm/IR/Instruction.h"
  41 #include "llvm/IR/Instructions.h"
  42 #include "llvm/IR/IntrinsicInst.h"
  43 #include "llvm/IR/Intrinsics.h"
  44 #include "llvm/IR/LLVMContext.h"
  45 #include "llvm/IR/MDBuilder.h"
  46 #include "llvm/IR/Module.h"
  47 #include "llvm/IR/Type.h"
  48 #include "llvm/IR/User.h"
  49 #include "llvm/IR/Value.h"
  50 #include "llvm/IR/Verifier.h"
  51 #include "llvm/Pass.h"
  52 #include "llvm/Support/BlockFrequency.h"
  53 #include "llvm/Support/BranchProbability.h"
  54 #include "llvm/Support/Casting.h"
  55 #include "llvm/Support/CommandLine.h"
  56 #include "llvm/Support/Debug.h"
  57 #include "llvm/Support/ErrorHandling.h"
  58 #include "llvm/Support/raw_ostream.h"
  59 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  60 #include <cassert>
  61 #include <cstdint>
  62 #include <iterator>
  63 #include <map>
  64 #include <set>
  65 #include <utility>
  66 #include <vector>
  67
  68 using namespace llvm;
  69 using ProfileCount = Function::ProfileCount;
  70
  71 #define DEBUG_TYPE "code-extractor"
  72
  73 // Provide a command-line option to aggregate function arguments into a struct
  74 // for functions produced by the code extractor. This is useful when converting
  75 // extracted functions to pthread-based code, as only one argument (void*) can
  76 // be passed in to pthread_create().
  77 static cl::opt<bool>
  78 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
  79                  cl::desc("Aggregate arguments to code-extracted functions"));
  80
  81 /// \brief Test whether a block is valid for extraction.
  82 bool CodeExtractor::isBlockValidForExtraction(const BasicBlock &BB,
  83                                               bool AllowVarArgs) {
  84   // Landing pads must be in the function where they were inserted for cleanup.
  85   if (BB.isEHPad())
  86     return false;
  87   // taking the address of a basic block moved to another function is illegal
  88   if (BB.hasAddressTaken())
  89     return false;
  90
  91   // don't hoist code that uses another basicblock address, as it's likely to
  92   // lead to unexpected behavior, like cross-function jumps
  93   SmallPtrSet<User const *, 16> Visited;
  94   SmallVector<User const *, 16> ToVisit;
  95
  96   for (Instruction const &Inst : BB)
  97     ToVisit.push_back(&Inst);
  98
  99   while (!ToVisit.empty()) {
 100     User const *Curr = ToVisit.pop_back_val();
 101     if (!Visited.insert(Curr).second)
 102       continue;
 103     if (isa<BlockAddress const>(Curr))
 104       return false; // even a reference to self is likely to be not compatible
 105
 106     if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)
 107       continue;
 108
 109     for (auto const &U : Curr->operands()) {
 110       if (auto *UU = dyn_cast<User>(U))
 111         ToVisit.push_back(UU);
 112     }
 113   }
 114
 115   // Don't hoist code containing allocas or invokes. If explicitly requested,
 116   // allow vastart.
 117   for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
 118     if (isa<AllocaInst>(I) || isa<InvokeInst>(I))
 119       return false;
 120     if (const CallInst *CI = dyn_cast<CallInst>(I))
 121       if (const Function *F = CI->getCalledFunction())
 122         if (F->getIntrinsicID() == Intrinsic::vastart) {
 123           if (AllowVarArgs)
 124             continue;
 125           else
 126             return false;
 127         }
 128   }
 129
 130   return true;
 131 }
 132
 133 /// \brief Build a set of blocks to extract if the input blocks are viable.
 134 static SetVector<BasicBlock *>
 135 buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
 136                         bool AllowVarArgs) {
 137   assert(!BBs.empty() && "The set of blocks to extract must be non-empty");
 138   SetVector<BasicBlock *> Result;
 139
 140   // Loop over the blocks, adding them to our set-vector, and aborting with an
 141   // empty set if we encounter invalid blocks.
 142   for (BasicBlock *BB : BBs) {
 143     // If this block is dead, don't process it.
 144     if (DT && !DT->isReachableFromEntry(BB))
 145       continue;
 146
 147     if (!Result.insert(BB))
 148       llvm_unreachable("Repeated basic blocks in extraction input");
 149     if (!CodeExtractor::isBlockValidForExtraction(*BB, AllowVarArgs)) {
 150       Result.clear();
 151       return Result;
 152     }
 153   }
 154
 155 #ifndef NDEBUG
 156   for (SetVector<BasicBlock *>::iterator I = std::next(Result.begin()),
 157                                          E = Result.end();
 158        I != E; ++I)
 159     for (pred_iterator PI = pred_begin(*I), PE = pred_end(*I);
 160          PI != PE; ++PI)
 161       assert(Result.count(*PI) &&
 162              "No blocks in this region may have entries from outside the region"
 163              " except for the first block!");
 164 #endif
 165
 166   return Result;
 167 }
 168
 169 CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
 170                              bool AggregateArgs, BlockFrequencyInfo *BFI,
 171                              BranchProbabilityInfo *BPI, bool AllowVarArgs)
 172     : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
 173       BPI(BPI), AllowVarArgs(AllowVarArgs),
 174       Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs)) {}
 175
 176 CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs,
 177                              BlockFrequencyInfo *BFI,
 178                              BranchProbabilityInfo *BPI)
 179     : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
 180       BPI(BPI), AllowVarArgs(false),
 181       Blocks(buildExtractionBlockSet(L.getBlocks(), &DT,
 182                                      /* AllowVarArgs */ false)) {}
 183
 184 /// definedInRegion - Return true if the specified value is defined in the
 185 /// extracted region.
 186 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
 187   if (Instruction *I = dyn_cast<Instruction>(V))
 188     if (Blocks.count(I->getParent()))
 189       return true;
 190   return false;
 191 }
 192
 193 /// definedInCaller - Return true if the specified value is defined in the
 194 /// function being code extracted, but not in the region being extracted.
 195 /// These values must be passed in as live-ins to the function.
 196 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
 197   if (isa<Argument>(V)) return true;
 198   if (Instruction *I = dyn_cast<Instruction>(V))
 199     if (!Blocks.count(I->getParent()))
 200       return true;
 201   return false;
 202 }
 203
 204 static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
 205   BasicBlock *CommonExitBlock = nullptr;
 206   auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
 207     for (auto *Succ : successors(Block)) {
 208       // Internal edges, ok.
 209       if (Blocks.count(Succ))
 210         continue;
 211       if (!CommonExitBlock) {
 212         CommonExitBlock = Succ;
 213         continue;
 214       }
 215       if (CommonExitBlock == Succ)
 216         continue;
 217
 218       return true;
 219     }
 220     return false;
 221   };
 222
 223   if (any_of(Blocks, hasNonCommonExitSucc))
 224     return nullptr;
 225
 226   return CommonExitBlock;
 227 }
 228
 229 bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(
 230     Instruction *Addr) const {
 231   AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
 232   Function *Func = (*Blocks.begin())->getParent();
 233   for (BasicBlock &BB : *Func) {
 234     if (Blocks.count(&BB))
 235       continue;
 236     for (Instruction &II : BB) {
 237       if (isa<DbgInfoIntrinsic>(II))
 238         continue;
 239
 240       unsigned Opcode = II.getOpcode();
 241       Value *MemAddr = nullptr;
 242       switch (Opcode) {
 243       case Instruction::Store:
 244       case Instruction::Load: {
 245         if (Opcode == Instruction::Store) {
 246           StoreInst *SI = cast<StoreInst>(&II);
 247           MemAddr = SI->getPointerOperand();
 248         } else {
 249           LoadInst *LI = cast<LoadInst>(&II);
 250           MemAddr = LI->getPointerOperand();
 251         }
 252         // Global variable can not be aliased with locals.
 253         if (dyn_cast<Constant>(MemAddr))
 254           break;
 255         Value *Base = MemAddr->stripInBoundsConstantOffsets();
 256         if (!dyn_cast<AllocaInst>(Base) || Base == AI)
 257           return false;
 258         break;
 259       }
 260       default: {
 261         IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
 262         if (IntrInst) {
 263           if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start ||
 264               IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
 265             break;
 266           return false;
 267         }
 268         // Treat all the other cases conservatively if it has side effects.
 269         if (II.mayHaveSideEffects())
 270           return false;
 271       }
 272       }
 273     }
 274   }
 275
 276   return true;
 277 }
 278
 279 BasicBlock *
 280 CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
 281   BasicBlock *SinglePredFromOutlineRegion = nullptr;
 282   assert(!Blocks.count(CommonExitBlock) &&
 283          "Expect a block outside the region!");
 284   for (auto *Pred : predecessors(CommonExitBlock)) {
 285     if (!Blocks.count(Pred))
 286       continue;
 287     if (!SinglePredFromOutlineRegion) {
 288       SinglePredFromOutlineRegion = Pred;
 289     } else if (SinglePredFromOutlineRegion != Pred) {
 290       SinglePredFromOutlineRegion = nullptr;
 291       break;
 292     }
 293   }
 294
 295   if (SinglePredFromOutlineRegion)
 296     return SinglePredFromOutlineRegion;
 297
 298 #ifndef NDEBUG
 299   auto getFirstPHI = [](BasicBlock *BB) {
 300     BasicBlock::iterator I = BB->begin();
 301     PHINode *FirstPhi = nullptr;
 302     while (I != BB->end()) {
 303       PHINode *Phi = dyn_cast<PHINode>(I);
 304       if (!Phi)
 305         break;
 306       if (!FirstPhi) {
 307         FirstPhi = Phi;
 308         break;
 309       }
 310     }
 311     return FirstPhi;
 312   };
 313   // If there are any phi nodes, the single pred either exists or has already
 314   // be created before code extraction.
 315   assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
 316 #endif
 317
 318   BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
 319       CommonExitBlock->getFirstNonPHI()->getIterator());
 320
 321   for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock);
 322        PI != PE;) {
 323     BasicBlock *Pred = *PI++;
 324     if (Blocks.count(Pred))
 325       continue;
 326     Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
 327   }
 328   // Now add the old exit block to the outline region.
 329   Blocks.insert(CommonExitBlock);
 330   return CommonExitBlock;
 331 }
 332
 333 void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
 334                                 BasicBlock *&ExitBlock) const {
 335   Function *Func = (*Blocks.begin())->getParent();
 336   ExitBlock = getCommonExitBlock(Blocks);
 337
 338   for (BasicBlock &BB : *Func) {
 339     if (Blocks.count(&BB))
 340       continue;
 341     for (Instruction &II : BB) {
 342       auto *AI = dyn_cast<AllocaInst>(&II);
 343       if (!AI)
 344         continue;
 345
 346       // Find the pair of life time markers for address 'Addr' that are either
 347       // defined inside the outline region or can legally be shrinkwrapped into
 348       // the outline region. If there are not other untracked uses of the
 349       // address, return the pair of markers if found; otherwise return a pair
 350       // of nullptr.
 351       auto GetLifeTimeMarkers =
 352           [&](Instruction *Addr, bool &SinkLifeStart,
 353               bool &HoistLifeEnd) -> std::pair<Instruction *, Instruction *> {
 354         Instruction *LifeStart = nullptr, *LifeEnd = nullptr;
 355
 356         for (User *U : Addr->users()) {
 357           IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
 358           if (IntrInst) {
 359             if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
 360               // Do not handle the case where AI has multiple start markers.
 361               if (LifeStart)
 362                 return std::make_pair<Instruction *>(nullptr, nullptr);
 363               LifeStart = IntrInst;
 364             }
 365             if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
 366               if (LifeEnd)
 367                 return std::make_pair<Instruction *>(nullptr, nullptr);
 368               LifeEnd = IntrInst;
 369             }
 370             continue;
 371           }
 372           // Find untracked uses of the address, bail.
 373           if (!definedInRegion(Blocks, U))
 374             return std::make_pair<Instruction *>(nullptr, nullptr);
 375         }
 376
 377         if (!LifeStart || !LifeEnd)
 378           return std::make_pair<Instruction *>(nullptr, nullptr);
 379
 380         SinkLifeStart = !definedInRegion(Blocks, LifeStart);
 381         HoistLifeEnd = !definedInRegion(Blocks, LifeEnd);
 382         // Do legality Check.
 383         if ((SinkLifeStart || HoistLifeEnd) &&
 384             !isLegalToShrinkwrapLifetimeMarkers(Addr))
 385           return std::make_pair<Instruction *>(nullptr, nullptr);
 386
 387         // Check to see if we have a place to do hoisting, if not, bail.
 388         if (HoistLifeEnd && !ExitBlock)
 389           return std::make_pair<Instruction *>(nullptr, nullptr);
 390
 391         return std::make_pair(LifeStart, LifeEnd);
 392       };
 393
 394       bool SinkLifeStart = false, HoistLifeEnd = false;
 395       auto Markers = GetLifeTimeMarkers(AI, SinkLifeStart, HoistLifeEnd);
 396
 397       if (Markers.first) {
 398         if (SinkLifeStart)
 399           SinkCands.insert(Markers.first);
 400         SinkCands.insert(AI);
 401         if (HoistLifeEnd)
 402           HoistCands.insert(Markers.second);
 403         continue;
 404       }
 405
 406       // Follow the bitcast.
 407       Instruction *MarkerAddr = nullptr;
 408       for (User *U : AI->users()) {
 409         if (U->stripInBoundsConstantOffsets() == AI) {
 410           SinkLifeStart = false;
 411           HoistLifeEnd = false;
 412           Instruction *Bitcast = cast<Instruction>(U);
 413           Markers = GetLifeTimeMarkers(Bitcast, SinkLifeStart, HoistLifeEnd);
 414           if (Markers.first) {
 415             MarkerAddr = Bitcast;
 416             continue;
 417           }
 418         }
 419
 420         // Found unknown use of AI.
 421         if (!definedInRegion(Blocks, U)) {
 422           MarkerAddr = nullptr;
 423           break;
 424         }
 425       }
 426
 427       if (MarkerAddr) {
 428         if (SinkLifeStart)
 429           SinkCands.insert(Markers.first);
 430         if (!definedInRegion(Blocks, MarkerAddr))
 431           SinkCands.insert(MarkerAddr);
 432         SinkCands.insert(AI);
 433         if (HoistLifeEnd)
 434           HoistCands.insert(Markers.second);
 435       }
 436     }
 437   }
 438 }
 439
 440 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
 441                                       const ValueSet &SinkCands) const {
 442   for (BasicBlock *BB : Blocks) {
 443     // If a used value is defined outside the region, it's an input.  If an
 444     // instruction is used outside the region, it's an output.
 445     for (Instruction &II : *BB) {
 446       for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE;
 447            ++OI) {
 448         Value *V = *OI;
 449         if (!SinkCands.count(V) && definedInCaller(Blocks, V))
 450           Inputs.insert(V);
 451       }
 452
 453       for (User *U : II.users())
 454         if (!definedInRegion(Blocks, U)) {
 455           Outputs.insert(&II);
 456           break;
 457         }
 458     }
 459   }
 460 }
 461
 462 /// severSplitPHINodes - If a PHI node has multiple inputs from outside of the
 463 /// region, we need to split the entry block of the region so that the PHI node
 464 /// is easier to deal with.
 465 void CodeExtractor::severSplitPHINodes(BasicBlock *&Header) {
 466   unsigned NumPredsFromRegion = 0;
 467   unsigned NumPredsOutsideRegion = 0;
 468
 469   if (Header != &Header->getParent()->getEntryBlock()) {
 470     PHINode *PN = dyn_cast<PHINode>(Header->begin());
 471     if (!PN) return;  // No PHI nodes.
 472
 473     // If the header node contains any PHI nodes, check to see if there is more
 474     // than one entry from outside the region.  If so, we need to sever the
 475     // header block into two.
 476     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 477       if (Blocks.count(PN->getIncomingBlock(i)))
 478         ++NumPredsFromRegion;
 479       else
 480         ++NumPredsOutsideRegion;
 481
 482     // If there is one (or fewer) predecessor from outside the region, we don't
 483     // need to do anything special.
 484     if (NumPredsOutsideRegion <= 1) return;
 485   }
 486
 487   // Otherwise, we need to split the header block into two pieces: one
 488   // containing PHI nodes merging values from outside of the region, and a
 489   // second that contains all of the code for the block and merges back any
 490   // incoming values from inside of the region.
 491   BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
 492
 493   // We only want to code extract the second block now, and it becomes the new
 494   // header of the region.
 495   BasicBlock *OldPred = Header;
 496   Blocks.remove(OldPred);
 497   Blocks.insert(NewBB);
 498   Header = NewBB;
 499
 500   // Okay, now we need to adjust the PHI nodes and any branches from within the
 501   // region to go to the new header block instead of the old header block.
 502   if (NumPredsFromRegion) {
 503     PHINode *PN = cast<PHINode>(OldPred->begin());
 504     // Loop over all of the predecessors of OldPred that are in the region,
 505     // changing them to branch to NewBB instead.
 506     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 507       if (Blocks.count(PN->getIncomingBlock(i))) {
 508         TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator();
 509         TI->replaceUsesOfWith(OldPred, NewBB);
 510       }
 511
 512     // Okay, everything within the region is now branching to the right block, we
 513     // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
 514     BasicBlock::iterator AfterPHIs;
 515     for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
 516       PHINode *PN = cast<PHINode>(AfterPHIs);
 517       // Create a new PHI node in the new region, which has an incoming value
 518       // from OldPred of PN.
 519       PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
 520                                        PN->getName() + ".ce", &NewBB->front());
 521       PN->replaceAllUsesWith(NewPN);
 522       NewPN->addIncoming(PN, OldPred);
 523
 524       // Loop over all of the incoming value in PN, moving them to NewPN if they
 525       // are from the extracted region.
 526       for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
 527         if (Blocks.count(PN->getIncomingBlock(i))) {
 528           NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
 529           PN->removeIncomingValue(i);
 530           --i;
 531         }
 532       }
 533     }
 534   }
 535 }
 536
 537 void CodeExtractor::splitReturnBlocks() {
 538   for (BasicBlock *Block : Blocks)
 539     if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
 540       BasicBlock *New =
 541           Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
 542       if (DT) {
 543         // Old dominates New. New node dominates all other nodes dominated
 544         // by Old.
 545         DomTreeNode *OldNode = DT->getNode(Block);
 546         SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
 547                                                OldNode->end());
 548
 549         DomTreeNode *NewNode = DT->addNewBlock(New, Block);
 550
 551         for (DomTreeNode *I : Children)
 552           DT->changeImmediateDominator(I, NewNode);
 553       }
 554     }
 555 }
 556
 557 /// constructFunction - make a function based on inputs and outputs, as follows:
 558 /// f(in0, ..., inN, out0, ..., outN)
 559 Function *CodeExtractor::constructFunction(const ValueSet &inputs,
 560                                            const ValueSet &outputs,
 561                                            BasicBlock *header,
 562                                            BasicBlock *newRootNode,
 563                                            BasicBlock *newHeader,
 564                                            Function *oldFunction,
 565                                            Module *M) {
 566   DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
 567   DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
 568
 569   // This function returns unsigned, outputs will go back by reference.
 570   switch (NumExitBlocks) {
 571   case 0:
 572   case 1: RetTy = Type::getVoidTy(header->getContext()); break;
 573   case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
 574   default: RetTy = Type::getInt16Ty(header->getContext()); break;
 575   }
 576
 577   std::vector<Type *> paramTy;
 578
 579   // Add the types of the input values to the function's argument list
 580   for (Value *value : inputs) {
 581     DEBUG(dbgs() << "value used in func: " << *value << "\n");
 582     paramTy.push_back(value->getType());
 583   }
 584
 585   // Add the types of the output values to the function's argument list.
 586   for (Value *output : outputs) {
 587     DEBUG(dbgs() << "instr used in func: " << *output << "\n");
 588     if (AggregateArgs)
 589       paramTy.push_back(output->getType());
 590     else
 591       paramTy.push_back(PointerType::getUnqual(output->getType()));
 592   }
 593
 594   DEBUG({
 595     dbgs() << "Function type: " << *RetTy << " f(";
 596     for (Type *i : paramTy)
 597       dbgs() << *i << ", ";
 598     dbgs() << ")\n";
 599   });
 600
 601   StructType *StructTy;
 602   if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
 603     StructTy = StructType::get(M->getContext(), paramTy);
 604     paramTy.clear();
 605     paramTy.push_back(PointerType::getUnqual(StructTy));
 606   }
 607   FunctionType *funcType =
 608                   FunctionType::get(RetTy, paramTy,
 609                                     AllowVarArgs && oldFunction->isVarArg());
 610
 611   // Create the new function
 612   Function *newFunction = Function::Create(funcType,
 613                                            GlobalValue::InternalLinkage,
 614                                            oldFunction->getName() + "_" +
 615                                            header->getName(), M);
 616   // If the old function is no-throw, so is the new one.
 617   if (oldFunction->doesNotThrow())
 618     newFunction->setDoesNotThrow();
 619
 620   // Inherit the uwtable attribute if we need to.
 621   if (oldFunction->hasUWTable())
 622     newFunction->setHasUWTable();
 623
 624   // Inherit all of the target dependent attributes and white-listed
 625   // target independent attributes.
 626   //  (e.g. If the extracted region contains a call to an x86.sse
 627   //  instruction we need to make sure that the extracted region has the
 628   //  "target-features" attribute allowing it to be lowered.
 629   // FIXME: This should be changed to check to see if a specific
 630   //           attribute can not be inherited.
 631   for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) {
 632     if (Attr.isStringAttribute()) {
 633       if (Attr.getKindAsString() == "thunk")
 634         continue;
 635     } else
 636       switch (Attr.getKindAsEnum()) {
 637       // Those attributes cannot be propagated safely. Explicitly list them
 638       // here so we get a warning if new attributes are added. This list also
 639       // includes non-function attributes.
 640       case Attribute::Alignment:
 641       case Attribute::AllocSize:
 642       case Attribute::ArgMemOnly:
 643       case Attribute::Builtin:
 644       case Attribute::ByVal:
 645       case Attribute::Convergent:
 646       case Attribute::Dereferenceable:
 647       case Attribute::DereferenceableOrNull:
 648       case Attribute::InAlloca:
 649       case Attribute::InReg:
 650       case Attribute::InaccessibleMemOnly:
 651       case Attribute::InaccessibleMemOrArgMemOnly:
 652       case Attribute::JumpTable:
 653       case Attribute::Naked:
 654       case Attribute::Nest:
 655       case Attribute::NoAlias:
 656       case Attribute::NoBuiltin:
 657       case Attribute::NoCapture:
 658       case Attribute::NoReturn:
 659       case Attribute::None:
 660       case Attribute::NonNull:
 661       case Attribute::ReadNone:
 662       case Attribute::ReadOnly:
 663       case Attribute::Returned:
 664       case Attribute::ReturnsTwice:
 665       case Attribute::SExt:
 666       case Attribute::Speculatable:
 667       case Attribute::StackAlignment:
 668       case Attribute::StructRet:
 669       case Attribute::SwiftError:
 670       case Attribute::SwiftSelf:
 671       case Attribute::WriteOnly:
 672       case Attribute::ZExt:
 673       case Attribute::EndAttrKinds:
 674         continue;
 675       // Those attributes should be safe to propagate to the extracted function.
 676       case Attribute::AlwaysInline:
 677       case Attribute::Cold:
 678       case Attribute::NoRecurse:
 679       case Attribute::InlineHint:
 680       case Attribute::MinSize:
 681       case Attribute::NoDuplicate:
 682       case Attribute::NoImplicitFloat:
 683       case Attribute::NoInline:
 684       case Attribute::NonLazyBind:
 685       case Attribute::NoRedZone:
 686       case Attribute::NoUnwind:
 687       case Attribute::OptimizeNone:
 688       case Attribute::OptimizeForSize:
 689       case Attribute::SafeStack:
 690       case Attribute::SanitizeAddress:
 691       case Attribute::SanitizeMemory:
 692       case Attribute::SanitizeThread:
 693       case Attribute::SanitizeHWAddress:
 694       case Attribute::StackProtect:
 695       case Attribute::StackProtectReq:
 696       case Attribute::StackProtectStrong:
 697       case Attribute::StrictFP:
 698       case Attribute::UWTable:
 699         break;
 700       }
 701
 702     newFunction->addFnAttr(Attr);
 703   }
 704   newFunction->getBasicBlockList().push_back(newRootNode);
 705
 706   // Create an iterator to name all of the arguments we inserted.
 707   Function::arg_iterator AI = newFunction->arg_begin();
 708
 709   // Rewrite all users of the inputs in the extracted region to use the
 710   // arguments (or appropriate addressing into struct) instead.
 711   for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
 712     Value *RewriteVal;
 713     if (AggregateArgs) {
 714       Value *Idx[2];
 715       Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
 716       Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
 717       TerminatorInst *TI = newFunction->begin()->getTerminator();
 718       GetElementPtrInst *GEP = GetElementPtrInst::Create(
 719           StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
 720       RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI);
 721     } else
 722       RewriteVal = &*AI++;
 723
 724     std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
 725     for (User *use : Users)
 726       if (Instruction *inst = dyn_cast<Instruction>(use))
 727         if (Blocks.count(inst->getParent()))
 728           inst->replaceUsesOfWith(inputs[i], RewriteVal);
 729   }
 730
 731   // Set names for input and output arguments.
 732   if (!AggregateArgs) {
 733     AI = newFunction->arg_begin();
 734     for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
 735       AI->setName(inputs[i]->getName());
 736     for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
 737       AI->setName(outputs[i]->getName()+".out");
 738   }
 739
 740   // Rewrite branches to basic blocks outside of the loop to new dummy blocks
 741   // within the new function. This must be done before we lose track of which
 742   // blocks were originally in the code region.
 743   std::vector<User *> Users(header->user_begin(), header->user_end());
 744   for (unsigned i = 0, e = Users.size(); i != e; ++i)
 745     // The BasicBlock which contains the branch is not in the region
 746     // modify the branch target to a new block
 747     if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i]))
 748       if (!Blocks.count(TI->getParent()) &&
 749           TI->getParent()->getParent() == oldFunction)
 750         TI->replaceUsesOfWith(header, newHeader);
 751
 752   return newFunction;
 753 }
 754
 755 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
 756 /// the call instruction, splitting any PHI nodes in the header block as
 757 /// necessary.
 758 void CodeExtractor::
 759 emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer,
 760                            ValueSet &inputs, ValueSet &outputs) {
 761   // Emit a call to the new function, passing in: *pointer to struct (if
 762   // aggregating parameters), or plan inputs and allocated memory for outputs
 763   std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
 764
 765   Module *M = newFunction->getParent();
 766   LLVMContext &Context = M->getContext();
 767   const DataLayout &DL = M->getDataLayout();
 768
 769   // Add inputs as params, or to be filled into the struct
 770   for (Value *input : inputs)
 771     if (AggregateArgs)
 772       StructValues.push_back(input);
 773     else
 774       params.push_back(input);
 775
 776   // Create allocas for the outputs
 777   for (Value *output : outputs) {
 778     if (AggregateArgs) {
 779       StructValues.push_back(output);
 780     } else {
 781       AllocaInst *alloca =
 782         new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
 783                        nullptr, output->getName() + ".loc",
 784                        &codeReplacer->getParent()->front().front());
 785       ReloadOutputs.push_back(alloca);
 786       params.push_back(alloca);
 787     }
 788   }
 789
 790   StructType *StructArgTy = nullptr;
 791   AllocaInst *Struct = nullptr;
 792   if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
 793     std::vector<Type *> ArgTypes;
 794     for (ValueSet::iterator v = StructValues.begin(),
 795            ve = StructValues.end(); v != ve; ++v)
 796       ArgTypes.push_back((*v)->getType());
 797
 798     // Allocate a struct at the beginning of this function
 799     StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
 800     Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
 801                             "structArg",
 802                             &codeReplacer->getParent()->front().front());
 803     params.push_back(Struct);
 804
 805     for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
 806       Value *Idx[2];
 807       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
 808       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
 809       GetElementPtrInst *GEP = GetElementPtrInst::Create(
 810           StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
 811       codeReplacer->getInstList().push_back(GEP);
 812       StoreInst *SI = new StoreInst(StructValues[i], GEP);
 813       codeReplacer->getInstList().push_back(SI);
 814     }
 815   }
 816
 817   // Emit the call to the function
 818   CallInst *call = CallInst::Create(newFunction, params,
 819                                     NumExitBlocks > 1 ? "targetBlock" : "");
 820   // Add debug location to the new call, if the original function has debug
 821   // info. In that case, the terminator of the entry block of the extracted
 822   // function contains the first debug location of the extracted function,
 823   // set in extractCodeRegion.
 824   if (codeReplacer->getParent()->getSubprogram()) {
 825     if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
 826       call->setDebugLoc(DL);
 827   }
 828   codeReplacer->getInstList().push_back(call);
 829
 830   Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
 831   unsigned FirstOut = inputs.size();
 832   if (!AggregateArgs)
 833     std::advance(OutputArgBegin, inputs.size());
 834
 835   // Reload the outputs passed in by reference.
 836   Function::arg_iterator OAI = OutputArgBegin;
 837   for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
 838     Value *Output = nullptr;
 839     if (AggregateArgs) {
 840       Value *Idx[2];
 841       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
 842       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
 843       GetElementPtrInst *GEP = GetElementPtrInst::Create(
 844           StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
 845       codeReplacer->getInstList().push_back(GEP);
 846       Output = GEP;
 847     } else {
 848       Output = ReloadOutputs[i];
 849     }
 850     LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload");
 851     Reloads.push_back(load);
 852     codeReplacer->getInstList().push_back(load);
 853     std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
 854     for (unsigned u = 0, e = Users.size(); u != e; ++u) {
 855       Instruction *inst = cast<Instruction>(Users[u]);
 856       if (!Blocks.count(inst->getParent()))
 857         inst->replaceUsesOfWith(outputs[i], load);
 858     }
 859
 860     // Store to argument right after the definition of output value.
 861     auto *OutI = dyn_cast<Instruction>(outputs[i]);
 862     if (!OutI)
 863       continue;
 864     // Find proper insertion point.
 865     Instruction *InsertPt = OutI->getNextNode();
 866     // Let's assume that there is no other guy interleave non-PHI in PHIs.
 867     if (isa<PHINode>(InsertPt))
 868       InsertPt = InsertPt->getParent()->getFirstNonPHI();
 869
 870     assert(OAI != newFunction->arg_end() &&
 871            "Number of output arguments should match "
 872            "the amount of defined values");
 873     if (AggregateArgs) {
 874       Value *Idx[2];
 875       Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
 876       Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
 877       GetElementPtrInst *GEP = GetElementPtrInst::Create(
 878           StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), InsertPt);
 879       new StoreInst(outputs[i], GEP, InsertPt);
 880       // Since there should be only one struct argument aggregating
 881       // all the output values, we shouldn't increment OAI, which always
 882       // points to the struct argument, in this case.
 883     } else {
 884       new StoreInst(outputs[i], &*OAI, InsertPt);
 885       ++OAI;
 886     }
 887   }
 888
 889   // Now we can emit a switch statement using the call as a value.
 890   SwitchInst *TheSwitch =
 891       SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
 892                          codeReplacer, 0, codeReplacer);
 893
 894   // Since there may be multiple exits from the original region, make the new
 895   // function return an unsigned, switch on that number.  This loop iterates
 896   // over all of the blocks in the extracted region, updating any terminator
 897   // instructions in the to-be-extracted region that branch to blocks that are
 898   // not in the region to be extracted.
 899   std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
 900
 901   unsigned switchVal = 0;
 902   for (BasicBlock *Block : Blocks) {
 903     TerminatorInst *TI = Block->getTerminator();
 904     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 905       if (!Blocks.count(TI->getSuccessor(i))) {
 906         BasicBlock *OldTarget = TI->getSuccessor(i);
 907         // add a new basic block which returns the appropriate value
 908         BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
 909         if (!NewTarget) {
 910           // If we don't already have an exit stub for this non-extracted
 911           // destination, create one now!
 912           NewTarget = BasicBlock::Create(Context,
 913                                          OldTarget->getName() + ".exitStub",
 914                                          newFunction);
 915           unsigned SuccNum = switchVal++;
 916
 917           Value *brVal = nullptr;
 918           switch (NumExitBlocks) {
 919           case 0:
 920           case 1: break;  // No value needed.
 921           case 2:         // Conditional branch, return a bool
 922             brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
 923             break;
 924           default:
 925             brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
 926             break;
 927           }
 928
 929           ReturnInst::Create(Context, brVal, NewTarget);
 930
 931           // Update the switch instruction.
 932           TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
 933                                               SuccNum),
 934                              OldTarget);
 935         }
 936
 937         // rewrite the original branch instruction with this new target
 938         TI->setSuccessor(i, NewTarget);
 939       }
 940   }
 941
 942   // Now that we've done the deed, simplify the switch instruction.
 943   Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
 944   switch (NumExitBlocks) {
 945   case 0:
 946     // There are no successors (the block containing the switch itself), which
 947     // means that previously this was the last part of the function, and hence
 948     // this should be rewritten as a `ret'
 949
 950     // Check if the function should return a value
 951     if (OldFnRetTy->isVoidTy()) {
 952       ReturnInst::Create(Context, nullptr, TheSwitch);  // Return void
 953     } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
 954       // return what we have
 955       ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
 956     } else {
 957       // Otherwise we must have code extracted an unwind or something, just
 958       // return whatever we want.
 959       ReturnInst::Create(Context,
 960                          Constant::getNullValue(OldFnRetTy), TheSwitch);
 961     }
 962
 963     TheSwitch->eraseFromParent();
 964     break;
 965   case 1:
 966     // Only a single destination, change the switch into an unconditional
 967     // branch.
 968     BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
 969     TheSwitch->eraseFromParent();
 970     break;
 971   case 2:
 972     BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
 973                        call, TheSwitch);
 974     TheSwitch->eraseFromParent();
 975     break;
 976   default:
 977     // Otherwise, make the default destination of the switch instruction be one
 978     // of the other successors.
 979     TheSwitch->setCondition(call);
 980     TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
 981     // Remove redundant case
 982     TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
 983     break;
 984   }
 985 }
 986
 987 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
 988   Function *oldFunc = (*Blocks.begin())->getParent();
 989   Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
 990   Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
 991
 992   for (BasicBlock *Block : Blocks) {
 993     // Delete the basic block from the old function, and the list of blocks
 994     oldBlocks.remove(Block);
 995
 996     // Insert this basic block into the new function
 997     newBlocks.push_back(Block);
 998   }
 999 }
1000
1001 void CodeExtractor::calculateNewCallTerminatorWeights(
1002     BasicBlock *CodeReplacer,
1003     DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
1004     BranchProbabilityInfo *BPI) {
1005   using Distribution = BlockFrequencyInfoImplBase::Distribution;
1006   using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1007
1008   // Update the branch weights for the exit block.
1009   TerminatorInst *TI = CodeReplacer->getTerminator();
1010   SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1011
1012   // Block Frequency distribution with dummy node.
1013   Distribution BranchDist;
1014
1015   // Add each of the frequencies of the successors.
1016   for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1017     BlockNode ExitNode(i);
1018     uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1019     if (ExitFreq != 0)
1020       BranchDist.addExit(ExitNode, ExitFreq);
1021     else
1022       BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero());
1023   }
1024
1025   // Check for no total weight.
1026   if (BranchDist.Total == 0)
1027     return;
1028
1029   // Normalize the distribution so that they can fit in unsigned.
1030   BranchDist.normalize();
1031
1032   // Create normalized branch weights and set the metadata.
1033   for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1034     const auto &Weight = BranchDist.Weights[I];
1035
1036     // Get the weight and update the current BFI.
1037     BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1038     BranchProbability BP(Weight.Amount, BranchDist.Total);
1039     BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP);
1040   }
1041   TI->setMetadata(
1042       LLVMContext::MD_prof,
1043       MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1044 }
1045
1046 Function *CodeExtractor::extractCodeRegion() {
1047   if (!isEligible())
1048     return nullptr;
1049
1050   // Assumption: this is a single-entry code region, and the header is the first
1051   // block in the region.
1052   BasicBlock *header = *Blocks.begin();
1053   Function *oldFunction = header->getParent();
1054
1055   // For functions with varargs, check that varargs handling is only done in the
1056   // outlined function, i.e vastart and vaend are only used in outlined blocks.
1057   if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) {
1058     auto containsVarArgIntrinsic = [](Instruction &I) {
1059       if (const CallInst *CI = dyn_cast<CallInst>(&I))
1060         if (const Function *F = CI->getCalledFunction())
1061           return F->getIntrinsicID() == Intrinsic::vastart ||
1062                  F->getIntrinsicID() == Intrinsic::vaend;
1063       return false;
1064     };
1065
1066     for (auto &BB : *oldFunction) {
1067       if (Blocks.count(&BB))
1068         continue;
1069       if (llvm::any_of(BB, containsVarArgIntrinsic))
1070         return nullptr;
1071     }
1072   }
1073   ValueSet inputs, outputs, SinkingCands, HoistingCands;
1074   BasicBlock *CommonExit = nullptr;
1075
1076   // Calculate the entry frequency of the new function before we change the root
1077   //   block.
1078   BlockFrequency EntryFreq;
1079   if (BFI) {
1080     assert(BPI && "Both BPI and BFI are required to preserve profile info");
1081     for (BasicBlock *Pred : predecessors(header)) {
1082       if (Blocks.count(Pred))
1083         continue;
1084       EntryFreq +=
1085           BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1086     }
1087   }
1088
1089   // If we have to split PHI nodes or the entry block, do so now.
1090   severSplitPHINodes(header);
1091
1092   // If we have any return instructions in the region, split those blocks so
1093   // that the return is not in the region.
1094   splitReturnBlocks();
1095
1096   // This takes place of the original loop
1097   BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1098                                                 "codeRepl", oldFunction,
1099                                                 header);
1100
1101   // The new function needs a root node because other nodes can branch to the
1102   // head of the region, but the entry node of a function cannot have preds.
1103   BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1104                                                "newFuncRoot");
1105   auto *BranchI = BranchInst::Create(header);
1106   // If the original function has debug info, we have to add a debug location
1107   // to the new branch instruction from the artificial entry block.
1108   // We use the debug location of the first instruction in the extracted
1109   // blocks, as there is no other equivalent line in the source code.
1110   if (oldFunction->getSubprogram()) {
1111     any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1112       return any_of(*BB, [&BranchI](const Instruction &I) {
1113         if (!I.getDebugLoc())
1114           return false;
1115         BranchI->setDebugLoc(I.getDebugLoc());
1116         return true;
1117       });
1118     });
1119   }
1120   newFuncRoot->getInstList().push_back(BranchI);
1121
1122   findAllocas(SinkingCands, HoistingCands, CommonExit);
1123   assert(HoistingCands.empty() || CommonExit);
1124
1125   // Find inputs to, outputs from the code region.
1126   findInputsOutputs(inputs, outputs, SinkingCands);
1127
1128   // Now sink all instructions which only have non-phi uses inside the region
1129   for (auto *II : SinkingCands)
1130     cast<Instruction>(II)->moveBefore(*newFuncRoot,
1131                                       newFuncRoot->getFirstInsertionPt());
1132
1133   if (!HoistingCands.empty()) {
1134     auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1135     Instruction *TI = HoistToBlock->getTerminator();
1136     for (auto *II : HoistingCands)
1137       cast<Instruction>(II)->moveBefore(TI);
1138   }
1139
1140   // Calculate the exit blocks for the extracted region and the total exit
1141   // weights for each of those blocks.
1142   DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
1143   SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1144   for (BasicBlock *Block : Blocks) {
1145     for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
1146          ++SI) {
1147       if (!Blocks.count(*SI)) {
1148         // Update the branch weight for this successor.
1149         if (BFI) {
1150           BlockFrequency &BF = ExitWeights[*SI];
1151           BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
1152         }
1153         ExitBlocks.insert(*SI);
1154       }
1155     }
1156   }
1157   NumExitBlocks = ExitBlocks.size();
1158
1159   // Construct new function based on inputs/outputs & add allocas for all defs.
1160   Function *newFunction = constructFunction(inputs, outputs, header,
1161                                             newFuncRoot,
1162                                             codeReplacer, oldFunction,
1163                                             oldFunction->getParent());
1164
1165   // Update the entry count of the function.
1166   if (BFI) {
1167     auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1168     if (Count.hasValue())
1169       newFunction->setEntryCount(
1170           ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1171     BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1172   }
1173
1174   emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1175
1176   moveCodeToFunction(newFunction);
1177
1178   // Update the branch weights for the exit block.
1179   if (BFI && NumExitBlocks > 1)
1180     calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1181
1182   // Loop over all of the PHI nodes in the header block, and change any
1183   // references to the old incoming edge to be the new incoming edge.
1184   for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1185     PHINode *PN = cast<PHINode>(I);
1186     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1187       if (!Blocks.count(PN->getIncomingBlock(i)))
1188         PN->setIncomingBlock(i, newFuncRoot);
1189   }
1190
1191   // Look at all successors of the codeReplacer block.  If any of these blocks
1192   // had PHI nodes in them, we need to update the "from" block to be the code
1193   // replacer, not the original block in the extracted region.
1194   std::vector<BasicBlock *> Succs(succ_begin(codeReplacer),
1195                                   succ_end(codeReplacer));
1196   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
1197     for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) {
1198       PHINode *PN = cast<PHINode>(I);
1199       std::set<BasicBlock*> ProcessedPreds;
1200       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1201         if (Blocks.count(PN->getIncomingBlock(i))) {
1202           if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second)
1203             PN->setIncomingBlock(i, codeReplacer);
1204           else {
1205             // There were multiple entries in the PHI for this block, now there
1206             // is only one, so remove the duplicated entries.
1207             PN->removeIncomingValue(i, false);
1208             --i; --e;
1209           }
1210         }
1211     }
1212
1213   DEBUG(if (verifyFunction(*newFunction))
1214         report_fatal_error("verifyFunction failed!"));
1215   return newFunction;
1216 }