contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp

   1 //===- CloneFunction.cpp - Clone a function into another 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 CloneFunctionInto interface, which is used as the
  11 // low-level function cloner.  This is used by the CloneFunction and function
  12 // inliner to do the dirty work of copying the body of a function around.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Utils/Cloning.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/Analysis/ConstantFolding.h"
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/IR/CFG.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/DebugInfo.h"
  25 #include "llvm/IR/DerivedTypes.h"
  26 #include "llvm/IR/Function.h"
  27 #include "llvm/IR/GlobalVariable.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/IR/LLVMContext.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/Module.h"
  33 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  34 #include "llvm/Transforms/Utils/Local.h"
  35 #include "llvm/Transforms/Utils/ValueMapper.h"
  36 #include <map>
  37 using namespace llvm;
  38
  39 /// See comments in Cloning.h.
  40 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
  41                                   ValueToValueMapTy &VMap,
  42                                   const Twine &NameSuffix, Function *F,
  43                                   ClonedCodeInfo *CodeInfo) {
  44   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
  45   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
  46
  47   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
  48
  49   // Loop over all instructions, and copy them over.
  50   for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
  51        II != IE; ++II) {
  52     Instruction *NewInst = II->clone();
  53     if (II->hasName())
  54       NewInst->setName(II->getName()+NameSuffix);
  55     NewBB->getInstList().push_back(NewInst);
  56     VMap[&*II] = NewInst; // Add instruction map to value.
  57
  58     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
  59     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
  60       if (isa<ConstantInt>(AI->getArraySize()))
  61         hasStaticAllocas = true;
  62       else
  63         hasDynamicAllocas = true;
  64     }
  65   }
  66
  67   if (CodeInfo) {
  68     CodeInfo->ContainsCalls          |= hasCalls;
  69     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
  70     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
  71                                         BB != &BB->getParent()->getEntryBlock();
  72   }
  73   return NewBB;
  74 }
  75
  76 // Clone OldFunc into NewFunc, transforming the old arguments into references to
  77 // VMap values.
  78 //
  79 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
  80                              ValueToValueMapTy &VMap,
  81                              bool ModuleLevelChanges,
  82                              SmallVectorImpl<ReturnInst*> &Returns,
  83                              const char *NameSuffix, ClonedCodeInfo *CodeInfo,
  84                              ValueMapTypeRemapper *TypeMapper,
  85                              ValueMaterializer *Materializer) {
  86   assert(NameSuffix && "NameSuffix cannot be null!");
  87
  88 #ifndef NDEBUG
  89   for (const Argument &I : OldFunc->args())
  90     assert(VMap.count(&I) && "No mapping from source argument specified!");
  91 #endif
  92
  93   // Copy all attributes other than those stored in the AttributeList.  We need
  94   // to remap the parameter indices of the AttributeList.
  95   AttributeList NewAttrs = NewFunc->getAttributes();
  96   NewFunc->copyAttributesFrom(OldFunc);
  97   NewFunc->setAttributes(NewAttrs);
  98
  99   // Fix up the personality function that got copied over.
 100   if (OldFunc->hasPersonalityFn())
 101     NewFunc->setPersonalityFn(
 102         MapValue(OldFunc->getPersonalityFn(), VMap,
 103                  ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
 104                  TypeMapper, Materializer));
 105
 106   SmallVector<AttributeSet, 4> NewArgAttrs(NewFunc->arg_size());
 107   AttributeList OldAttrs = OldFunc->getAttributes();
 108
 109   // Clone any argument attributes that are present in the VMap.
 110   for (const Argument &OldArg : OldFunc->args()) {
 111     if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
 112       NewArgAttrs[NewArg->getArgNo()] =
 113           OldAttrs.getParamAttributes(OldArg.getArgNo());
 114     }
 115   }
 116
 117   NewFunc->setAttributes(
 118       AttributeList::get(NewFunc->getContext(), OldAttrs.getFnAttributes(),
 119                          OldAttrs.getRetAttributes(), NewArgAttrs));
 120
 121   SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
 122   OldFunc->getAllMetadata(MDs);
 123   for (auto MD : MDs)
 124     NewFunc->addMetadata(
 125         MD.first,
 126         *MapMetadata(MD.second, VMap,
 127                      ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
 128                      TypeMapper, Materializer));
 129
 130   // Loop over all of the basic blocks in the function, cloning them as
 131   // appropriate.  Note that we save BE this way in order to handle cloning of
 132   // recursive functions into themselves.
 133   //
 134   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
 135        BI != BE; ++BI) {
 136     const BasicBlock &BB = *BI;
 137
 138     // Create a new basic block and copy instructions into it!
 139     BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo);
 140
 141     // Add basic block mapping.
 142     VMap[&BB] = CBB;
 143
 144     // It is only legal to clone a function if a block address within that
 145     // function is never referenced outside of the function.  Given that, we
 146     // want to map block addresses from the old function to block addresses in
 147     // the clone. (This is different from the generic ValueMapper
 148     // implementation, which generates an invalid blockaddress when
 149     // cloning a function.)
 150     if (BB.hasAddressTaken()) {
 151       Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
 152                                               const_cast<BasicBlock*>(&BB));
 153       VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB);
 154     }
 155
 156     // Note return instructions for the caller.
 157     if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
 158       Returns.push_back(RI);
 159   }
 160
 161   // Loop over all of the instructions in the function, fixing up operand
 162   // references as we go.  This uses VMap to do all the hard work.
 163   for (Function::iterator BB =
 164            cast<BasicBlock>(VMap[&OldFunc->front()])->getIterator(),
 165                           BE = NewFunc->end();
 166        BB != BE; ++BB)
 167     // Loop over all instructions, fixing each one as we find it...
 168     for (Instruction &II : *BB)
 169       RemapInstruction(&II, VMap,
 170                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
 171                        TypeMapper, Materializer);
 172 }
 173
 174 /// Return a copy of the specified function and add it to that function's
 175 /// module.  Also, any references specified in the VMap are changed to refer to
 176 /// their mapped value instead of the original one.  If any of the arguments to
 177 /// the function are in the VMap, the arguments are deleted from the resultant
 178 /// function.  The VMap is updated to include mappings from all of the
 179 /// instructions and basicblocks in the function from their old to new values.
 180 ///
 181 Function *llvm::CloneFunction(Function *F, ValueToValueMapTy &VMap,
 182                               ClonedCodeInfo *CodeInfo) {
 183   std::vector<Type*> ArgTypes;
 184
 185   // The user might be deleting arguments to the function by specifying them in
 186   // the VMap.  If so, we need to not add the arguments to the arg ty vector
 187   //
 188   for (const Argument &I : F->args())
 189     if (VMap.count(&I) == 0) // Haven't mapped the argument to anything yet?
 190       ArgTypes.push_back(I.getType());
 191
 192   // Create a new function type...
 193   FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
 194                                     ArgTypes, F->getFunctionType()->isVarArg());
 195
 196   // Create the new function...
 197   Function *NewF =
 198       Function::Create(FTy, F->getLinkage(), F->getName(), F->getParent());
 199
 200   // Loop over the arguments, copying the names of the mapped arguments over...
 201   Function::arg_iterator DestI = NewF->arg_begin();
 202   for (const Argument & I : F->args())
 203     if (VMap.count(&I) == 0) {     // Is this argument preserved?
 204       DestI->setName(I.getName()); // Copy the name over...
 205       VMap[&I] = &*DestI++;        // Add mapping to VMap
 206     }
 207
 208   SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
 209   CloneFunctionInto(NewF, F, VMap, /*ModuleLevelChanges=*/false, Returns, "",
 210                     CodeInfo);
 211
 212   return NewF;
 213 }
 214
 215
 216
 217 namespace {
 218   /// This is a private class used to implement CloneAndPruneFunctionInto.
 219   struct PruningFunctionCloner {
 220     Function *NewFunc;
 221     const Function *OldFunc;
 222     ValueToValueMapTy &VMap;
 223     bool ModuleLevelChanges;
 224     const char *NameSuffix;
 225     ClonedCodeInfo *CodeInfo;
 226
 227   public:
 228     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
 229                           ValueToValueMapTy &valueMap, bool moduleLevelChanges,
 230                           const char *nameSuffix, ClonedCodeInfo *codeInfo)
 231         : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap),
 232           ModuleLevelChanges(moduleLevelChanges), NameSuffix(nameSuffix),
 233           CodeInfo(codeInfo) {}
 234
 235     /// The specified block is found to be reachable, clone it and
 236     /// anything that it can reach.
 237     void CloneBlock(const BasicBlock *BB,
 238                     BasicBlock::const_iterator StartingInst,
 239                     std::vector<const BasicBlock*> &ToClone);
 240   };
 241 }
 242
 243 /// The specified block is found to be reachable, clone it and
 244 /// anything that it can reach.
 245 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
 246                                        BasicBlock::const_iterator StartingInst,
 247                                        std::vector<const BasicBlock*> &ToClone){
 248   WeakTrackingVH &BBEntry = VMap[BB];
 249
 250   // Have we already cloned this block?
 251   if (BBEntry) return;
 252
 253   // Nope, clone it now.
 254   BasicBlock *NewBB;
 255   BBEntry = NewBB = BasicBlock::Create(BB->getContext());
 256   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
 257
 258   // It is only legal to clone a function if a block address within that
 259   // function is never referenced outside of the function.  Given that, we
 260   // want to map block addresses from the old function to block addresses in
 261   // the clone. (This is different from the generic ValueMapper
 262   // implementation, which generates an invalid blockaddress when
 263   // cloning a function.)
 264   //
 265   // Note that we don't need to fix the mapping for unreachable blocks;
 266   // the default mapping there is safe.
 267   if (BB->hasAddressTaken()) {
 268     Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
 269                                             const_cast<BasicBlock*>(BB));
 270     VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
 271   }
 272
 273   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
 274
 275   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
 276   // loop doesn't include the terminator.
 277   for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end();
 278        II != IE; ++II) {
 279
 280     Instruction *NewInst = II->clone();
 281
 282     // Eagerly remap operands to the newly cloned instruction, except for PHI
 283     // nodes for which we defer processing until we update the CFG.
 284     if (!isa<PHINode>(NewInst)) {
 285       RemapInstruction(NewInst, VMap,
 286                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
 287
 288       // If we can simplify this instruction to some other value, simply add
 289       // a mapping to that value rather than inserting a new instruction into
 290       // the basic block.
 291       if (Value *V =
 292               SimplifyInstruction(NewInst, BB->getModule()->getDataLayout())) {
 293         // On the off-chance that this simplifies to an instruction in the old
 294         // function, map it back into the new function.
 295         if (Value *MappedV = VMap.lookup(V))
 296           V = MappedV;
 297
 298         if (!NewInst->mayHaveSideEffects()) {
 299           VMap[&*II] = V;
 300           delete NewInst;
 301           continue;
 302         }
 303       }
 304     }
 305
 306     if (II->hasName())
 307       NewInst->setName(II->getName()+NameSuffix);
 308     VMap[&*II] = NewInst; // Add instruction map to value.
 309     NewBB->getInstList().push_back(NewInst);
 310     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
 311
 312     if (CodeInfo)
 313       if (auto CS = ImmutableCallSite(&*II))
 314         if (CS.hasOperandBundles())
 315           CodeInfo->OperandBundleCallSites.push_back(NewInst);
 316
 317     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
 318       if (isa<ConstantInt>(AI->getArraySize()))
 319         hasStaticAllocas = true;
 320       else
 321         hasDynamicAllocas = true;
 322     }
 323   }
 324
 325   // Finally, clone over the terminator.
 326   const TerminatorInst *OldTI = BB->getTerminator();
 327   bool TerminatorDone = false;
 328   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
 329     if (BI->isConditional()) {
 330       // If the condition was a known constant in the callee...
 331       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
 332       // Or is a known constant in the caller...
 333       if (!Cond) {
 334         Value *V = VMap.lookup(BI->getCondition());
 335         Cond = dyn_cast_or_null<ConstantInt>(V);
 336       }
 337
 338       // Constant fold to uncond branch!
 339       if (Cond) {
 340         BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
 341         VMap[OldTI] = BranchInst::Create(Dest, NewBB);
 342         ToClone.push_back(Dest);
 343         TerminatorDone = true;
 344       }
 345     }
 346   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
 347     // If switching on a value known constant in the caller.
 348     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
 349     if (!Cond) { // Or known constant after constant prop in the callee...
 350       Value *V = VMap.lookup(SI->getCondition());
 351       Cond = dyn_cast_or_null<ConstantInt>(V);
 352     }
 353     if (Cond) {     // Constant fold to uncond branch!
 354       SwitchInst::ConstCaseHandle Case = *SI->findCaseValue(Cond);
 355       BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor());
 356       VMap[OldTI] = BranchInst::Create(Dest, NewBB);
 357       ToClone.push_back(Dest);
 358       TerminatorDone = true;
 359     }
 360   }
 361
 362   if (!TerminatorDone) {
 363     Instruction *NewInst = OldTI->clone();
 364     if (OldTI->hasName())
 365       NewInst->setName(OldTI->getName()+NameSuffix);
 366     NewBB->getInstList().push_back(NewInst);
 367     VMap[OldTI] = NewInst;             // Add instruction map to value.
 368
 369     if (CodeInfo)
 370       if (auto CS = ImmutableCallSite(OldTI))
 371         if (CS.hasOperandBundles())
 372           CodeInfo->OperandBundleCallSites.push_back(NewInst);
 373
 374     // Recursively clone any reachable successor blocks.
 375     const TerminatorInst *TI = BB->getTerminator();
 376     for (const BasicBlock *Succ : TI->successors())
 377       ToClone.push_back(Succ);
 378   }
 379
 380   if (CodeInfo) {
 381     CodeInfo->ContainsCalls          |= hasCalls;
 382     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
 383     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
 384       BB != &BB->getParent()->front();
 385   }
 386 }
 387
 388 /// This works like CloneAndPruneFunctionInto, except that it does not clone the
 389 /// entire function. Instead it starts at an instruction provided by the caller
 390 /// and copies (and prunes) only the code reachable from that instruction.
 391 void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
 392                                      const Instruction *StartingInst,
 393                                      ValueToValueMapTy &VMap,
 394                                      bool ModuleLevelChanges,
 395                                      SmallVectorImpl<ReturnInst *> &Returns,
 396                                      const char *NameSuffix,
 397                                      ClonedCodeInfo *CodeInfo) {
 398   assert(NameSuffix && "NameSuffix cannot be null!");
 399
 400   ValueMapTypeRemapper *TypeMapper = nullptr;
 401   ValueMaterializer *Materializer = nullptr;
 402
 403 #ifndef NDEBUG
 404   // If the cloning starts at the beginning of the function, verify that
 405   // the function arguments are mapped.
 406   if (!StartingInst)
 407     for (const Argument &II : OldFunc->args())
 408       assert(VMap.count(&II) && "No mapping from source argument specified!");
 409 #endif
 410
 411   PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
 412                             NameSuffix, CodeInfo);
 413   const BasicBlock *StartingBB;
 414   if (StartingInst)
 415     StartingBB = StartingInst->getParent();
 416   else {
 417     StartingBB = &OldFunc->getEntryBlock();
 418     StartingInst = &StartingBB->front();
 419   }
 420
 421   // Clone the entry block, and anything recursively reachable from it.
 422   std::vector<const BasicBlock*> CloneWorklist;
 423   PFC.CloneBlock(StartingBB, StartingInst->getIterator(), CloneWorklist);
 424   while (!CloneWorklist.empty()) {
 425     const BasicBlock *BB = CloneWorklist.back();
 426     CloneWorklist.pop_back();
 427     PFC.CloneBlock(BB, BB->begin(), CloneWorklist);
 428   }
 429
 430   // Loop over all of the basic blocks in the old function.  If the block was
 431   // reachable, we have cloned it and the old block is now in the value map:
 432   // insert it into the new function in the right order.  If not, ignore it.
 433   //
 434   // Defer PHI resolution until rest of function is resolved.
 435   SmallVector<const PHINode*, 16> PHIToResolve;
 436   for (const BasicBlock &BI : *OldFunc) {
 437     Value *V = VMap.lookup(&BI);
 438     BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
 439     if (!NewBB) continue;  // Dead block.
 440
 441     // Add the new block to the new function.
 442     NewFunc->getBasicBlockList().push_back(NewBB);
 443
 444     // Handle PHI nodes specially, as we have to remove references to dead
 445     // blocks.
 446     for (BasicBlock::const_iterator I = BI.begin(), E = BI.end(); I != E; ++I) {
 447       // PHI nodes may have been remapped to non-PHI nodes by the caller or
 448       // during the cloning process.
 449       if (const PHINode *PN = dyn_cast<PHINode>(I)) {
 450         if (isa<PHINode>(VMap[PN]))
 451           PHIToResolve.push_back(PN);
 452         else
 453           break;
 454       } else {
 455         break;
 456       }
 457     }
 458
 459     // Finally, remap the terminator instructions, as those can't be remapped
 460     // until all BBs are mapped.
 461     RemapInstruction(NewBB->getTerminator(), VMap,
 462                      ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
 463                      TypeMapper, Materializer);
 464   }
 465
 466   // Defer PHI resolution until rest of function is resolved, PHI resolution
 467   // requires the CFG to be up-to-date.
 468   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
 469     const PHINode *OPN = PHIToResolve[phino];
 470     unsigned NumPreds = OPN->getNumIncomingValues();
 471     const BasicBlock *OldBB = OPN->getParent();
 472     BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);
 473
 474     // Map operands for blocks that are live and remove operands for blocks
 475     // that are dead.
 476     for (; phino != PHIToResolve.size() &&
 477          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
 478       OPN = PHIToResolve[phino];
 479       PHINode *PN = cast<PHINode>(VMap[OPN]);
 480       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
 481         Value *V = VMap.lookup(PN->getIncomingBlock(pred));
 482         if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
 483           Value *InVal = MapValue(PN->getIncomingValue(pred),
 484                                   VMap,
 485                         ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
 486           assert(InVal && "Unknown input value?");
 487           PN->setIncomingValue(pred, InVal);
 488           PN->setIncomingBlock(pred, MappedBlock);
 489         } else {
 490           PN->removeIncomingValue(pred, false);
 491           --pred;  // Revisit the next entry.
 492           --e;
 493         }
 494       }
 495     }
 496
 497     // The loop above has removed PHI entries for those blocks that are dead
 498     // and has updated others.  However, if a block is live (i.e. copied over)
 499     // but its terminator has been changed to not go to this block, then our
 500     // phi nodes will have invalid entries.  Update the PHI nodes in this
 501     // case.
 502     PHINode *PN = cast<PHINode>(NewBB->begin());
 503     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
 504     if (NumPreds != PN->getNumIncomingValues()) {
 505       assert(NumPreds < PN->getNumIncomingValues());
 506       // Count how many times each predecessor comes to this block.
 507       std::map<BasicBlock*, unsigned> PredCount;
 508       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
 509            PI != E; ++PI)
 510         --PredCount[*PI];
 511
 512       // Figure out how many entries to remove from each PHI.
 513       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 514         ++PredCount[PN->getIncomingBlock(i)];
 515
 516       // At this point, the excess predecessor entries are positive in the
 517       // map.  Loop over all of the PHIs and remove excess predecessor
 518       // entries.
 519       BasicBlock::iterator I = NewBB->begin();
 520       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
 521         for (const auto &PCI : PredCount) {
 522           BasicBlock *Pred = PCI.first;
 523           for (unsigned NumToRemove = PCI.second; NumToRemove; --NumToRemove)
 524             PN->removeIncomingValue(Pred, false);
 525         }
 526       }
 527     }
 528
 529     // If the loops above have made these phi nodes have 0 or 1 operand,
 530     // replace them with undef or the input value.  We must do this for
 531     // correctness, because 0-operand phis are not valid.
 532     PN = cast<PHINode>(NewBB->begin());
 533     if (PN->getNumIncomingValues() == 0) {
 534       BasicBlock::iterator I = NewBB->begin();
 535       BasicBlock::const_iterator OldI = OldBB->begin();
 536       while ((PN = dyn_cast<PHINode>(I++))) {
 537         Value *NV = UndefValue::get(PN->getType());
 538         PN->replaceAllUsesWith(NV);
 539         assert(VMap[&*OldI] == PN && "VMap mismatch");
 540         VMap[&*OldI] = NV;
 541         PN->eraseFromParent();
 542         ++OldI;
 543       }
 544     }
 545   }
 546
 547   // Make a second pass over the PHINodes now that all of them have been
 548   // remapped into the new function, simplifying the PHINode and performing any
 549   // recursive simplifications exposed. This will transparently update the
 550   // WeakTrackingVH in the VMap. Notably, we rely on that so that if we coalesce
 551   // two PHINodes, the iteration over the old PHIs remains valid, and the
 552   // mapping will just map us to the new node (which may not even be a PHI
 553   // node).
 554   const DataLayout &DL = NewFunc->getParent()->getDataLayout();
 555   SmallSetVector<const Value *, 8> Worklist;
 556   for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
 557     if (isa<PHINode>(VMap[PHIToResolve[Idx]]))
 558       Worklist.insert(PHIToResolve[Idx]);
 559
 560   // Note that we must test the size on each iteration, the worklist can grow.
 561   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
 562     const Value *OrigV = Worklist[Idx];
 563     auto *I = dyn_cast_or_null<Instruction>(VMap.lookup(OrigV));
 564     if (!I)
 565       continue;
 566
 567     // Skip over non-intrinsic callsites, we don't want to remove any nodes from
 568     // the CGSCC.
 569     CallSite CS = CallSite(I);
 570     if (CS && CS.getCalledFunction() && !CS.getCalledFunction()->isIntrinsic())
 571       continue;
 572
 573     // See if this instruction simplifies.
 574     Value *SimpleV = SimplifyInstruction(I, DL);
 575     if (!SimpleV)
 576       continue;
 577
 578     // Stash away all the uses of the old instruction so we can check them for
 579     // recursive simplifications after a RAUW. This is cheaper than checking all
 580     // uses of To on the recursive step in most cases.
 581     for (const User *U : OrigV->users())
 582       Worklist.insert(cast<Instruction>(U));
 583
 584     // Replace the instruction with its simplified value.
 585     I->replaceAllUsesWith(SimpleV);
 586
 587     // If the original instruction had no side effects, remove it.
 588     if (isInstructionTriviallyDead(I))
 589       I->eraseFromParent();
 590     else
 591       VMap[OrigV] = I;
 592   }
 593
 594   // Now that the inlined function body has been fully constructed, go through
 595   // and zap unconditional fall-through branches. This happens all the time when
 596   // specializing code: code specialization turns conditional branches into
 597   // uncond branches, and this code folds them.
 598   Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB])->getIterator();
 599   Function::iterator I = Begin;
 600   while (I != NewFunc->end()) {
 601     // Check if this block has become dead during inlining or other
 602     // simplifications. Note that the first block will appear dead, as it has
 603     // not yet been wired up properly.
 604     if (I != Begin && (pred_begin(&*I) == pred_end(&*I) ||
 605                        I->getSinglePredecessor() == &*I)) {
 606       BasicBlock *DeadBB = &*I++;
 607       DeleteDeadBlock(DeadBB);
 608       continue;
 609     }
 610
 611     // We need to simplify conditional branches and switches with a constant
 612     // operand. We try to prune these out when cloning, but if the
 613     // simplification required looking through PHI nodes, those are only
 614     // available after forming the full basic block. That may leave some here,
 615     // and we still want to prune the dead code as early as possible.
 616     ConstantFoldTerminator(&*I);
 617
 618     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
 619     if (!BI || BI->isConditional()) { ++I; continue; }
 620
 621     BasicBlock *Dest = BI->getSuccessor(0);
 622     if (!Dest->getSinglePredecessor()) {
 623       ++I; continue;
 624     }
 625
 626     // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
 627     // above should have zapped all of them..
 628     assert(!isa<PHINode>(Dest->begin()));
 629
 630     // We know all single-entry PHI nodes in the inlined function have been
 631     // removed, so we just need to splice the blocks.
 632     BI->eraseFromParent();
 633
 634     // Make all PHI nodes that referred to Dest now refer to I as their source.
 635     Dest->replaceAllUsesWith(&*I);
 636
 637     // Move all the instructions in the succ to the pred.
 638     I->getInstList().splice(I->end(), Dest->getInstList());
 639
 640     // Remove the dest block.
 641     Dest->eraseFromParent();
 642
 643     // Do not increment I, iteratively merge all things this block branches to.
 644   }
 645
 646   // Make a final pass over the basic blocks from the old function to gather
 647   // any return instructions which survived folding. We have to do this here
 648   // because we can iteratively remove and merge returns above.
 649   for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB])->getIterator(),
 650                           E = NewFunc->end();
 651        I != E; ++I)
 652     if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
 653       Returns.push_back(RI);
 654 }
 655
 656
 657 /// This works exactly like CloneFunctionInto,
 658 /// except that it does some simple constant prop and DCE on the fly.  The
 659 /// effect of this is to copy significantly less code in cases where (for
 660 /// example) a function call with constant arguments is inlined, and those
 661 /// constant arguments cause a significant amount of code in the callee to be
 662 /// dead.  Since this doesn't produce an exact copy of the input, it can't be
 663 /// used for things like CloneFunction or CloneModule.
 664 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
 665                                      ValueToValueMapTy &VMap,
 666                                      bool ModuleLevelChanges,
 667                                      SmallVectorImpl<ReturnInst*> &Returns,
 668                                      const char *NameSuffix,
 669                                      ClonedCodeInfo *CodeInfo,
 670                                      Instruction *TheCall) {
 671   CloneAndPruneIntoFromInst(NewFunc, OldFunc, &OldFunc->front().front(), VMap,
 672                             ModuleLevelChanges, Returns, NameSuffix, CodeInfo);
 673 }
 674
 675 /// \brief Remaps instructions in \p Blocks using the mapping in \p VMap.
 676 void llvm::remapInstructionsInBlocks(
 677     const SmallVectorImpl<BasicBlock *> &Blocks, ValueToValueMapTy &VMap) {
 678   // Rewrite the code to refer to itself.
 679   for (auto *BB : Blocks)
 680     for (auto &Inst : *BB)
 681       RemapInstruction(&Inst, VMap,
 682                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
 683 }
 684
 685 /// \brief Clones a loop \p OrigLoop.  Returns the loop and the blocks in \p
 686 /// Blocks.
 687 ///
 688 /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
 689 /// \p LoopDomBB.  Insert the new blocks before block specified in \p Before.
 690 Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
 691                                    Loop *OrigLoop, ValueToValueMapTy &VMap,
 692                                    const Twine &NameSuffix, LoopInfo *LI,
 693                                    DominatorTree *DT,
 694                                    SmallVectorImpl<BasicBlock *> &Blocks) {
 695   assert(OrigLoop->getSubLoops().empty() &&
 696          "Loop to be cloned cannot have inner loop");
 697   Function *F = OrigLoop->getHeader()->getParent();
 698   Loop *ParentLoop = OrigLoop->getParentLoop();
 699
 700   Loop *NewLoop = new Loop();
 701   if (ParentLoop)
 702     ParentLoop->addChildLoop(NewLoop);
 703   else
 704     LI->addTopLevelLoop(NewLoop);
 705
 706   BasicBlock *OrigPH = OrigLoop->getLoopPreheader();
 707   assert(OrigPH && "No preheader");
 708   BasicBlock *NewPH = CloneBasicBlock(OrigPH, VMap, NameSuffix, F);
 709   // To rename the loop PHIs.
 710   VMap[OrigPH] = NewPH;
 711   Blocks.push_back(NewPH);
 712
 713   // Update LoopInfo.
 714   if (ParentLoop)
 715     ParentLoop->addBasicBlockToLoop(NewPH, *LI);
 716
 717   // Update DominatorTree.
 718   DT->addNewBlock(NewPH, LoopDomBB);
 719
 720   for (BasicBlock *BB : OrigLoop->getBlocks()) {
 721     BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F);
 722     VMap[BB] = NewBB;
 723
 724     // Update LoopInfo.
 725     NewLoop->addBasicBlockToLoop(NewBB, *LI);
 726
 727     // Add DominatorTree node. After seeing all blocks, update to correct IDom.
 728     DT->addNewBlock(NewBB, NewPH);
 729
 730     Blocks.push_back(NewBB);
 731   }
 732
 733   for (BasicBlock *BB : OrigLoop->getBlocks()) {
 734     // Update DominatorTree.
 735     BasicBlock *IDomBB = DT->getNode(BB)->getIDom()->getBlock();
 736     DT->changeImmediateDominator(cast<BasicBlock>(VMap[BB]),
 737                                  cast<BasicBlock>(VMap[IDomBB]));
 738   }
 739
 740   // Move them physically from the end of the block list.
 741   F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
 742                                 NewPH);
 743   F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
 744                                 NewLoop->getHeader()->getIterator(), F->end());
 745
 746   return NewLoop;
 747 }
 748
 749 /// \brief Duplicate non-Phi instructions from the beginning of block up to
 750 /// StopAt instruction into a split block between BB and its predecessor.
 751 BasicBlock *
 752 llvm::DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB,
 753                                           Instruction *StopAt,
 754                                           ValueToValueMapTy &ValueMapping) {
 755   // We are going to have to map operands from the original BB block to the new
 756   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
 757   // account for entry from PredBB.
 758   BasicBlock::iterator BI = BB->begin();
 759   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
 760     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
 761
 762   BasicBlock *NewBB = SplitEdge(PredBB, BB);
 763   NewBB->setName(PredBB->getName() + ".split");
 764   Instruction *NewTerm = NewBB->getTerminator();
 765
 766   // Clone the non-phi instructions of BB into NewBB, keeping track of the
 767   // mapping and using it to remap operands in the cloned instructions.
 768   for (; StopAt != &*BI; ++BI) {
 769     Instruction *New = BI->clone();
 770     New->setName(BI->getName());
 771     New->insertBefore(NewTerm);
 772     ValueMapping[&*BI] = New;
 773
 774     // Remap operands to patch up intra-block references.
 775     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
 776       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
 777         auto I = ValueMapping.find(Inst);
 778         if (I != ValueMapping.end())
 779           New->setOperand(i, I->second);
 780       }
 781   }
 782
 783   return NewBB;
 784 }