Home | History | Annotate | Download | only in Utils
      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/SmallVector.h"
     18 #include "llvm/Analysis/ConstantFolding.h"
     19 #include "llvm/Analysis/InstructionSimplify.h"
     20 #include "llvm/DebugInfo.h"
     21 #include "llvm/IR/Constants.h"
     22 #include "llvm/IR/DerivedTypes.h"
     23 #include "llvm/IR/Function.h"
     24 #include "llvm/IR/GlobalVariable.h"
     25 #include "llvm/IR/Instructions.h"
     26 #include "llvm/IR/IntrinsicInst.h"
     27 #include "llvm/IR/LLVMContext.h"
     28 #include "llvm/IR/Metadata.h"
     29 #include "llvm/Support/CFG.h"
     30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
     31 #include "llvm/Transforms/Utils/Local.h"
     32 #include "llvm/Transforms/Utils/ValueMapper.h"
     33 #include <map>
     34 using namespace llvm;
     35 
     36 // CloneBasicBlock - See comments in Cloning.h
     37 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
     38                                   ValueToValueMapTy &VMap,
     39                                   const Twine &NameSuffix, Function *F,
     40                                   ClonedCodeInfo *CodeInfo) {
     41   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
     42   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
     43 
     44   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
     45 
     46   // Loop over all instructions, and copy them over.
     47   for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
     48        II != IE; ++II) {
     49     Instruction *NewInst = II->clone();
     50     if (II->hasName())
     51       NewInst->setName(II->getName()+NameSuffix);
     52     NewBB->getInstList().push_back(NewInst);
     53     VMap[II] = NewInst;                // Add instruction map to value.
     54 
     55     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
     56     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
     57       if (isa<ConstantInt>(AI->getArraySize()))
     58         hasStaticAllocas = true;
     59       else
     60         hasDynamicAllocas = true;
     61     }
     62   }
     63 
     64   if (CodeInfo) {
     65     CodeInfo->ContainsCalls          |= hasCalls;
     66     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
     67     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
     68                                         BB != &BB->getParent()->getEntryBlock();
     69   }
     70   return NewBB;
     71 }
     72 
     73 // Clone OldFunc into NewFunc, transforming the old arguments into references to
     74 // VMap values.
     75 //
     76 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
     77                              ValueToValueMapTy &VMap,
     78                              bool ModuleLevelChanges,
     79                              SmallVectorImpl<ReturnInst*> &Returns,
     80                              const char *NameSuffix, ClonedCodeInfo *CodeInfo,
     81                              ValueMapTypeRemapper *TypeMapper) {
     82   assert(NameSuffix && "NameSuffix cannot be null!");
     83 
     84 #ifndef NDEBUG
     85   for (Function::const_arg_iterator I = OldFunc->arg_begin(),
     86        E = OldFunc->arg_end(); I != E; ++I)
     87     assert(VMap.count(I) && "No mapping from source argument specified!");
     88 #endif
     89 
     90   AttributeSet OldAttrs = OldFunc->getAttributes();
     91   // Clone any argument attributes that are present in the VMap.
     92   for (Function::const_arg_iterator I = OldFunc->arg_begin(),
     93                                     E = OldFunc->arg_end();
     94        I != E; ++I)
     95     if (Argument *Anew = dyn_cast<Argument>(VMap[I])) {
     96       AttributeSet attrs =
     97           OldAttrs.getParamAttributes(I->getArgNo() + 1);
     98       if (attrs.getNumSlots() > 0)
     99         Anew->addAttr(attrs);
    100     }
    101 
    102   NewFunc->setAttributes(NewFunc->getAttributes()
    103                          .addAttributes(NewFunc->getContext(),
    104                                         AttributeSet::ReturnIndex,
    105                                         OldAttrs.getRetAttributes()));
    106   NewFunc->setAttributes(NewFunc->getAttributes()
    107                          .addAttributes(NewFunc->getContext(),
    108                                         AttributeSet::FunctionIndex,
    109                                         OldAttrs.getFnAttributes()));
    110 
    111   // Loop over all of the basic blocks in the function, cloning them as
    112   // appropriate.  Note that we save BE this way in order to handle cloning of
    113   // recursive functions into themselves.
    114   //
    115   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
    116        BI != BE; ++BI) {
    117     const BasicBlock &BB = *BI;
    118 
    119     // Create a new basic block and copy instructions into it!
    120     BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo);
    121 
    122     // Add basic block mapping.
    123     VMap[&BB] = CBB;
    124 
    125     // It is only legal to clone a function if a block address within that
    126     // function is never referenced outside of the function.  Given that, we
    127     // want to map block addresses from the old function to block addresses in
    128     // the clone. (This is different from the generic ValueMapper
    129     // implementation, which generates an invalid blockaddress when
    130     // cloning a function.)
    131     if (BB.hasAddressTaken()) {
    132       Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
    133                                               const_cast<BasicBlock*>(&BB));
    134       VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB);
    135     }
    136 
    137     // Note return instructions for the caller.
    138     if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
    139       Returns.push_back(RI);
    140   }
    141 
    142   // Loop over all of the instructions in the function, fixing up operand
    143   // references as we go.  This uses VMap to do all the hard work.
    144   for (Function::iterator BB = cast<BasicBlock>(VMap[OldFunc->begin()]),
    145          BE = NewFunc->end(); BB != BE; ++BB)
    146     // Loop over all instructions, fixing each one as we find it...
    147     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
    148       RemapInstruction(II, VMap,
    149                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
    150                        TypeMapper);
    151 }
    152 
    153 /// CloneFunction - Return a copy of the specified function, but without
    154 /// embedding the function into another module.  Also, any references specified
    155 /// in the VMap are changed to refer to their mapped value instead of the
    156 /// original one.  If any of the arguments to the function are in the VMap,
    157 /// the arguments are deleted from the resultant function.  The VMap is
    158 /// updated to include mappings from all of the instructions and basicblocks in
    159 /// the function from their old to new values.
    160 ///
    161 Function *llvm::CloneFunction(const Function *F, ValueToValueMapTy &VMap,
    162                               bool ModuleLevelChanges,
    163                               ClonedCodeInfo *CodeInfo) {
    164   std::vector<Type*> ArgTypes;
    165 
    166   // The user might be deleting arguments to the function by specifying them in
    167   // the VMap.  If so, we need to not add the arguments to the arg ty vector
    168   //
    169   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
    170        I != E; ++I)
    171     if (VMap.count(I) == 0)  // Haven't mapped the argument to anything yet?
    172       ArgTypes.push_back(I->getType());
    173 
    174   // Create a new function type...
    175   FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
    176                                     ArgTypes, F->getFunctionType()->isVarArg());
    177 
    178   // Create the new function...
    179   Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName());
    180 
    181   // Loop over the arguments, copying the names of the mapped arguments over...
    182   Function::arg_iterator DestI = NewF->arg_begin();
    183   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
    184        I != E; ++I)
    185     if (VMap.count(I) == 0) {   // Is this argument preserved?
    186       DestI->setName(I->getName()); // Copy the name over...
    187       VMap[I] = DestI++;        // Add mapping to VMap
    188     }
    189 
    190   SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
    191   CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo);
    192   return NewF;
    193 }
    194 
    195 
    196 
    197 namespace {
    198   /// PruningFunctionCloner - This class is a private class used to implement
    199   /// the CloneAndPruneFunctionInto method.
    200   struct PruningFunctionCloner {
    201     Function *NewFunc;
    202     const Function *OldFunc;
    203     ValueToValueMapTy &VMap;
    204     bool ModuleLevelChanges;
    205     const char *NameSuffix;
    206     ClonedCodeInfo *CodeInfo;
    207     const DataLayout *TD;
    208   public:
    209     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
    210                           ValueToValueMapTy &valueMap,
    211                           bool moduleLevelChanges,
    212                           const char *nameSuffix,
    213                           ClonedCodeInfo *codeInfo,
    214                           const DataLayout *td)
    215     : NewFunc(newFunc), OldFunc(oldFunc),
    216       VMap(valueMap), ModuleLevelChanges(moduleLevelChanges),
    217       NameSuffix(nameSuffix), CodeInfo(codeInfo), TD(td) {
    218     }
    219 
    220     /// CloneBlock - The specified block is found to be reachable, clone it and
    221     /// anything that it can reach.
    222     void CloneBlock(const BasicBlock *BB,
    223                     std::vector<const BasicBlock*> &ToClone);
    224   };
    225 }
    226 
    227 /// CloneBlock - The specified block is found to be reachable, clone it and
    228 /// anything that it can reach.
    229 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
    230                                        std::vector<const BasicBlock*> &ToClone){
    231   WeakVH &BBEntry = VMap[BB];
    232 
    233   // Have we already cloned this block?
    234   if (BBEntry) return;
    235 
    236   // Nope, clone it now.
    237   BasicBlock *NewBB;
    238   BBEntry = NewBB = BasicBlock::Create(BB->getContext());
    239   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
    240 
    241   // It is only legal to clone a function if a block address within that
    242   // function is never referenced outside of the function.  Given that, we
    243   // want to map block addresses from the old function to block addresses in
    244   // the clone. (This is different from the generic ValueMapper
    245   // implementation, which generates an invalid blockaddress when
    246   // cloning a function.)
    247   //
    248   // Note that we don't need to fix the mapping for unreachable blocks;
    249   // the default mapping there is safe.
    250   if (BB->hasAddressTaken()) {
    251     Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
    252                                             const_cast<BasicBlock*>(BB));
    253     VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
    254   }
    255 
    256 
    257   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
    258 
    259   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
    260   // loop doesn't include the terminator.
    261   for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
    262        II != IE; ++II) {
    263     Instruction *NewInst = II->clone();
    264 
    265     // Eagerly remap operands to the newly cloned instruction, except for PHI
    266     // nodes for which we defer processing until we update the CFG.
    267     if (!isa<PHINode>(NewInst)) {
    268       RemapInstruction(NewInst, VMap,
    269                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
    270 
    271       // If we can simplify this instruction to some other value, simply add
    272       // a mapping to that value rather than inserting a new instruction into
    273       // the basic block.
    274       if (Value *V = SimplifyInstruction(NewInst, TD)) {
    275         // On the off-chance that this simplifies to an instruction in the old
    276         // function, map it back into the new function.
    277         if (Value *MappedV = VMap.lookup(V))
    278           V = MappedV;
    279 
    280         VMap[II] = V;
    281         delete NewInst;
    282         continue;
    283       }
    284     }
    285 
    286     if (II->hasName())
    287       NewInst->setName(II->getName()+NameSuffix);
    288     VMap[II] = NewInst;                // Add instruction map to value.
    289     NewBB->getInstList().push_back(NewInst);
    290     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
    291     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
    292       if (isa<ConstantInt>(AI->getArraySize()))
    293         hasStaticAllocas = true;
    294       else
    295         hasDynamicAllocas = true;
    296     }
    297   }
    298 
    299   // Finally, clone over the terminator.
    300   const TerminatorInst *OldTI = BB->getTerminator();
    301   bool TerminatorDone = false;
    302   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
    303     if (BI->isConditional()) {
    304       // If the condition was a known constant in the callee...
    305       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
    306       // Or is a known constant in the caller...
    307       if (Cond == 0) {
    308         Value *V = VMap[BI->getCondition()];
    309         Cond = dyn_cast_or_null<ConstantInt>(V);
    310       }
    311 
    312       // Constant fold to uncond branch!
    313       if (Cond) {
    314         BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
    315         VMap[OldTI] = BranchInst::Create(Dest, NewBB);
    316         ToClone.push_back(Dest);
    317         TerminatorDone = true;
    318       }
    319     }
    320   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
    321     // If switching on a value known constant in the caller.
    322     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
    323     if (Cond == 0) { // Or known constant after constant prop in the callee...
    324       Value *V = VMap[SI->getCondition()];
    325       Cond = dyn_cast_or_null<ConstantInt>(V);
    326     }
    327     if (Cond) {     // Constant fold to uncond branch!
    328       SwitchInst::ConstCaseIt Case = SI->findCaseValue(Cond);
    329       BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor());
    330       VMap[OldTI] = BranchInst::Create(Dest, NewBB);
    331       ToClone.push_back(Dest);
    332       TerminatorDone = true;
    333     }
    334   }
    335 
    336   if (!TerminatorDone) {
    337     Instruction *NewInst = OldTI->clone();
    338     if (OldTI->hasName())
    339       NewInst->setName(OldTI->getName()+NameSuffix);
    340     NewBB->getInstList().push_back(NewInst);
    341     VMap[OldTI] = NewInst;             // Add instruction map to value.
    342 
    343     // Recursively clone any reachable successor blocks.
    344     const TerminatorInst *TI = BB->getTerminator();
    345     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
    346       ToClone.push_back(TI->getSuccessor(i));
    347   }
    348 
    349   if (CodeInfo) {
    350     CodeInfo->ContainsCalls          |= hasCalls;
    351     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
    352     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
    353       BB != &BB->getParent()->front();
    354   }
    355 }
    356 
    357 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
    358 /// except that it does some simple constant prop and DCE on the fly.  The
    359 /// effect of this is to copy significantly less code in cases where (for
    360 /// example) a function call with constant arguments is inlined, and those
    361 /// constant arguments cause a significant amount of code in the callee to be
    362 /// dead.  Since this doesn't produce an exact copy of the input, it can't be
    363 /// used for things like CloneFunction or CloneModule.
    364 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
    365                                      ValueToValueMapTy &VMap,
    366                                      bool ModuleLevelChanges,
    367                                      SmallVectorImpl<ReturnInst*> &Returns,
    368                                      const char *NameSuffix,
    369                                      ClonedCodeInfo *CodeInfo,
    370                                      const DataLayout *TD,
    371                                      Instruction *TheCall) {
    372   assert(NameSuffix && "NameSuffix cannot be null!");
    373 
    374 #ifndef NDEBUG
    375   for (Function::const_arg_iterator II = OldFunc->arg_begin(),
    376        E = OldFunc->arg_end(); II != E; ++II)
    377     assert(VMap.count(II) && "No mapping from source argument specified!");
    378 #endif
    379 
    380   PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
    381                             NameSuffix, CodeInfo, TD);
    382 
    383   // Clone the entry block, and anything recursively reachable from it.
    384   std::vector<const BasicBlock*> CloneWorklist;
    385   CloneWorklist.push_back(&OldFunc->getEntryBlock());
    386   while (!CloneWorklist.empty()) {
    387     const BasicBlock *BB = CloneWorklist.back();
    388     CloneWorklist.pop_back();
    389     PFC.CloneBlock(BB, CloneWorklist);
    390   }
    391 
    392   // Loop over all of the basic blocks in the old function.  If the block was
    393   // reachable, we have cloned it and the old block is now in the value map:
    394   // insert it into the new function in the right order.  If not, ignore it.
    395   //
    396   // Defer PHI resolution until rest of function is resolved.
    397   SmallVector<const PHINode*, 16> PHIToResolve;
    398   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
    399        BI != BE; ++BI) {
    400     Value *V = VMap[BI];
    401     BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
    402     if (NewBB == 0) continue;  // Dead block.
    403 
    404     // Add the new block to the new function.
    405     NewFunc->getBasicBlockList().push_back(NewBB);
    406 
    407     // Handle PHI nodes specially, as we have to remove references to dead
    408     // blocks.
    409     for (BasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I)
    410       if (const PHINode *PN = dyn_cast<PHINode>(I))
    411         PHIToResolve.push_back(PN);
    412       else
    413         break;
    414 
    415     // Finally, remap the terminator instructions, as those can't be remapped
    416     // until all BBs are mapped.
    417     RemapInstruction(NewBB->getTerminator(), VMap,
    418                      ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
    419   }
    420 
    421   // Defer PHI resolution until rest of function is resolved, PHI resolution
    422   // requires the CFG to be up-to-date.
    423   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
    424     const PHINode *OPN = PHIToResolve[phino];
    425     unsigned NumPreds = OPN->getNumIncomingValues();
    426     const BasicBlock *OldBB = OPN->getParent();
    427     BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);
    428 
    429     // Map operands for blocks that are live and remove operands for blocks
    430     // that are dead.
    431     for (; phino != PHIToResolve.size() &&
    432          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
    433       OPN = PHIToResolve[phino];
    434       PHINode *PN = cast<PHINode>(VMap[OPN]);
    435       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
    436         Value *V = VMap[PN->getIncomingBlock(pred)];
    437         if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
    438           Value *InVal = MapValue(PN->getIncomingValue(pred),
    439                                   VMap,
    440                         ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
    441           assert(InVal && "Unknown input value?");
    442           PN->setIncomingValue(pred, InVal);
    443           PN->setIncomingBlock(pred, MappedBlock);
    444         } else {
    445           PN->removeIncomingValue(pred, false);
    446           --pred, --e;  // Revisit the next entry.
    447         }
    448       }
    449     }
    450 
    451     // The loop above has removed PHI entries for those blocks that are dead
    452     // and has updated others.  However, if a block is live (i.e. copied over)
    453     // but its terminator has been changed to not go to this block, then our
    454     // phi nodes will have invalid entries.  Update the PHI nodes in this
    455     // case.
    456     PHINode *PN = cast<PHINode>(NewBB->begin());
    457     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
    458     if (NumPreds != PN->getNumIncomingValues()) {
    459       assert(NumPreds < PN->getNumIncomingValues());
    460       // Count how many times each predecessor comes to this block.
    461       std::map<BasicBlock*, unsigned> PredCount;
    462       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
    463            PI != E; ++PI)
    464         --PredCount[*PI];
    465 
    466       // Figure out how many entries to remove from each PHI.
    467       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
    468         ++PredCount[PN->getIncomingBlock(i)];
    469 
    470       // At this point, the excess predecessor entries are positive in the
    471       // map.  Loop over all of the PHIs and remove excess predecessor
    472       // entries.
    473       BasicBlock::iterator I = NewBB->begin();
    474       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
    475         for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
    476              E = PredCount.end(); PCI != E; ++PCI) {
    477           BasicBlock *Pred     = PCI->first;
    478           for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
    479             PN->removeIncomingValue(Pred, false);
    480         }
    481       }
    482     }
    483 
    484     // If the loops above have made these phi nodes have 0 or 1 operand,
    485     // replace them with undef or the input value.  We must do this for
    486     // correctness, because 0-operand phis are not valid.
    487     PN = cast<PHINode>(NewBB->begin());
    488     if (PN->getNumIncomingValues() == 0) {
    489       BasicBlock::iterator I = NewBB->begin();
    490       BasicBlock::const_iterator OldI = OldBB->begin();
    491       while ((PN = dyn_cast<PHINode>(I++))) {
    492         Value *NV = UndefValue::get(PN->getType());
    493         PN->replaceAllUsesWith(NV);
    494         assert(VMap[OldI] == PN && "VMap mismatch");
    495         VMap[OldI] = NV;
    496         PN->eraseFromParent();
    497         ++OldI;
    498       }
    499     }
    500   }
    501 
    502   // Make a second pass over the PHINodes now that all of them have been
    503   // remapped into the new function, simplifying the PHINode and performing any
    504   // recursive simplifications exposed. This will transparently update the
    505   // WeakVH in the VMap. Notably, we rely on that so that if we coalesce
    506   // two PHINodes, the iteration over the old PHIs remains valid, and the
    507   // mapping will just map us to the new node (which may not even be a PHI
    508   // node).
    509   for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
    510     if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]]))
    511       recursivelySimplifyInstruction(PN, TD);
    512 
    513   // Now that the inlined function body has been fully constructed, go through
    514   // and zap unconditional fall-through branches.  This happen all the time when
    515   // specializing code: code specialization turns conditional branches into
    516   // uncond branches, and this code folds them.
    517   Function::iterator Begin = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]);
    518   Function::iterator I = Begin;
    519   while (I != NewFunc->end()) {
    520     // Check if this block has become dead during inlining or other
    521     // simplifications. Note that the first block will appear dead, as it has
    522     // not yet been wired up properly.
    523     if (I != Begin && (pred_begin(I) == pred_end(I) ||
    524                        I->getSinglePredecessor() == I)) {
    525       BasicBlock *DeadBB = I++;
    526       DeleteDeadBlock(DeadBB);
    527       continue;
    528     }
    529 
    530     // We need to simplify conditional branches and switches with a constant
    531     // operand. We try to prune these out when cloning, but if the
    532     // simplification required looking through PHI nodes, those are only
    533     // available after forming the full basic block. That may leave some here,
    534     // and we still want to prune the dead code as early as possible.
    535     ConstantFoldTerminator(I);
    536 
    537     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
    538     if (!BI || BI->isConditional()) { ++I; continue; }
    539 
    540     BasicBlock *Dest = BI->getSuccessor(0);
    541     if (!Dest->getSinglePredecessor()) {
    542       ++I; continue;
    543     }
    544 
    545     // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
    546     // above should have zapped all of them..
    547     assert(!isa<PHINode>(Dest->begin()));
    548 
    549     // We know all single-entry PHI nodes in the inlined function have been
    550     // removed, so we just need to splice the blocks.
    551     BI->eraseFromParent();
    552 
    553     // Make all PHI nodes that referred to Dest now refer to I as their source.
    554     Dest->replaceAllUsesWith(I);
    555 
    556     // Move all the instructions in the succ to the pred.
    557     I->getInstList().splice(I->end(), Dest->getInstList());
    558 
    559     // Remove the dest block.
    560     Dest->eraseFromParent();
    561 
    562     // Do not increment I, iteratively merge all things this block branches to.
    563   }
    564 
    565   // Make a final pass over the basic blocks from theh old function to gather
    566   // any return instructions which survived folding. We have to do this here
    567   // because we can iteratively remove and merge returns above.
    568   for (Function::iterator I = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]),
    569                           E = NewFunc->end();
    570        I != E; ++I)
    571     if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
    572       Returns.push_back(RI);
    573 }
    574