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