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