LLVM API Documentation

CloneFunction.cpp
Go to the documentation of this file.
00001 //===- CloneFunction.cpp - Clone a function into another function ---------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the CloneFunctionInto interface, which is used as the
00011 // low-level function cloner.  This is used by the CloneFunction and function
00012 // inliner to do the dirty work of copying the body of a function around.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/Utils/Cloning.h"
00017 #include "llvm/ADT/SmallVector.h"
00018 #include "llvm/Analysis/ConstantFolding.h"
00019 #include "llvm/Analysis/InstructionSimplify.h"
00020 #include "llvm/IR/CFG.h"
00021 #include "llvm/IR/Constants.h"
00022 #include "llvm/IR/DebugInfo.h"
00023 #include "llvm/IR/DerivedTypes.h"
00024 #include "llvm/IR/Function.h"
00025 #include "llvm/IR/GlobalVariable.h"
00026 #include "llvm/IR/Instructions.h"
00027 #include "llvm/IR/IntrinsicInst.h"
00028 #include "llvm/IR/LLVMContext.h"
00029 #include "llvm/IR/Metadata.h"
00030 #include "llvm/IR/Module.h"
00031 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00032 #include "llvm/Transforms/Utils/Local.h"
00033 #include "llvm/Transforms/Utils/ValueMapper.h"
00034 #include <map>
00035 using namespace llvm;
00036 
00037 // CloneBasicBlock - See comments in Cloning.h
00038 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
00039                                   ValueToValueMapTy &VMap,
00040                                   const Twine &NameSuffix, Function *F,
00041                                   ClonedCodeInfo *CodeInfo) {
00042   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
00043   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00044 
00045   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00046   
00047   // Loop over all instructions, and copy them over.
00048   for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
00049        II != IE; ++II) {
00050     Instruction *NewInst = II->clone();
00051     if (II->hasName())
00052       NewInst->setName(II->getName()+NameSuffix);
00053     NewBB->getInstList().push_back(NewInst);
00054     VMap[II] = NewInst;                // Add instruction map to value.
00055     
00056     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
00057     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00058       if (isa<ConstantInt>(AI->getArraySize()))
00059         hasStaticAllocas = true;
00060       else
00061         hasDynamicAllocas = true;
00062     }
00063   }
00064   
00065   if (CodeInfo) {
00066     CodeInfo->ContainsCalls          |= hasCalls;
00067     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00068     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00069                                         BB != &BB->getParent()->getEntryBlock();
00070   }
00071   return NewBB;
00072 }
00073 
00074 // Clone OldFunc into NewFunc, transforming the old arguments into references to
00075 // VMap values.
00076 //
00077 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
00078                              ValueToValueMapTy &VMap,
00079                              bool ModuleLevelChanges,
00080                              SmallVectorImpl<ReturnInst*> &Returns,
00081                              const char *NameSuffix, ClonedCodeInfo *CodeInfo,
00082                              ValueMapTypeRemapper *TypeMapper,
00083                              ValueMaterializer *Materializer) {
00084   assert(NameSuffix && "NameSuffix cannot be null!");
00085 
00086 #ifndef NDEBUG
00087   for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
00088        E = OldFunc->arg_end(); I != E; ++I)
00089     assert(VMap.count(I) && "No mapping from source argument specified!");
00090 #endif
00091 
00092   // Copy all attributes other than those stored in the AttributeSet.  We need
00093   // to remap the parameter indices of the AttributeSet.
00094   AttributeSet NewAttrs = NewFunc->getAttributes();
00095   NewFunc->copyAttributesFrom(OldFunc);
00096   NewFunc->setAttributes(NewAttrs);
00097 
00098   AttributeSet OldAttrs = OldFunc->getAttributes();
00099   // Clone any argument attributes that are present in the VMap.
00100   for (const Argument &OldArg : OldFunc->args())
00101     if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
00102       AttributeSet attrs =
00103           OldAttrs.getParamAttributes(OldArg.getArgNo() + 1);
00104       if (attrs.getNumSlots() > 0)
00105         NewArg->addAttr(attrs);
00106     }
00107 
00108   NewFunc->setAttributes(
00109       NewFunc->getAttributes()
00110           .addAttributes(NewFunc->getContext(), AttributeSet::ReturnIndex,
00111                          OldAttrs.getRetAttributes())
00112           .addAttributes(NewFunc->getContext(), AttributeSet::FunctionIndex,
00113                          OldAttrs.getFnAttributes()));
00114 
00115   // Loop over all of the basic blocks in the function, cloning them as
00116   // appropriate.  Note that we save BE this way in order to handle cloning of
00117   // recursive functions into themselves.
00118   //
00119   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00120        BI != BE; ++BI) {
00121     const BasicBlock &BB = *BI;
00122 
00123     // Create a new basic block and copy instructions into it!
00124     BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo);
00125 
00126     // Add basic block mapping.
00127     VMap[&BB] = CBB;
00128 
00129     // It is only legal to clone a function if a block address within that
00130     // function is never referenced outside of the function.  Given that, we
00131     // want to map block addresses from the old function to block addresses in
00132     // the clone. (This is different from the generic ValueMapper
00133     // implementation, which generates an invalid blockaddress when
00134     // cloning a function.)
00135     if (BB.hasAddressTaken()) {
00136       Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
00137                                               const_cast<BasicBlock*>(&BB));
00138       VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB);                                         
00139     }
00140 
00141     // Note return instructions for the caller.
00142     if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
00143       Returns.push_back(RI);
00144   }
00145 
00146   // Loop over all of the instructions in the function, fixing up operand
00147   // references as we go.  This uses VMap to do all the hard work.
00148   for (Function::iterator BB = cast<BasicBlock>(VMap[OldFunc->begin()]),
00149          BE = NewFunc->end(); BB != BE; ++BB)
00150     // Loop over all instructions, fixing each one as we find it...
00151     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
00152       RemapInstruction(II, VMap,
00153                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
00154                        TypeMapper, Materializer);
00155 }
00156 
00157 // Find the MDNode which corresponds to the DISubprogram data that described F.
00158 static MDNode* FindSubprogram(const Function *F, DebugInfoFinder &Finder) {
00159   for (DISubprogram Subprogram : Finder.subprograms()) {
00160     if (Subprogram.describes(F)) return Subprogram;
00161   }
00162   return NULL;
00163 }
00164 
00165 // Add an operand to an existing MDNode. The new operand will be added at the
00166 // back of the operand list.
00167 static void AddOperand(MDNode *Node, Value *Operand) {
00168   SmallVector<Value*, 16> Operands;
00169   for (unsigned i = 0; i < Node->getNumOperands(); i++) {
00170     Operands.push_back(Node->getOperand(i));
00171   }
00172   Operands.push_back(Operand);
00173   MDNode *NewNode = MDNode::get(Node->getContext(), Operands);
00174   Node->replaceAllUsesWith(NewNode);
00175 }
00176 
00177 // Clone the module-level debug info associated with OldFunc. The cloned data
00178 // will point to NewFunc instead.
00179 static void CloneDebugInfoMetadata(Function *NewFunc, const Function *OldFunc,
00180                             ValueToValueMapTy &VMap) {
00181   DebugInfoFinder Finder;
00182   Finder.processModule(*OldFunc->getParent());
00183 
00184   const MDNode *OldSubprogramMDNode = FindSubprogram(OldFunc, Finder);
00185   if (!OldSubprogramMDNode) return;
00186 
00187   // Ensure that OldFunc appears in the map.
00188   // (if it's already there it must point to NewFunc anyway)
00189   VMap[OldFunc] = NewFunc;
00190   DISubprogram NewSubprogram(MapValue(OldSubprogramMDNode, VMap));
00191 
00192   for (DICompileUnit CU : Finder.compile_units()) {
00193     DIArray Subprograms(CU.getSubprograms());
00194 
00195     // If the compile unit's function list contains the old function, it should
00196     // also contain the new one.
00197     for (unsigned i = 0; i < Subprograms.getNumElements(); i++) {
00198       if ((MDNode*)Subprograms.getElement(i) == OldSubprogramMDNode) {
00199         AddOperand(Subprograms, NewSubprogram);
00200       }
00201     }
00202   }
00203 }
00204 
00205 /// CloneFunction - Return a copy of the specified function, but without
00206 /// embedding the function into another module.  Also, any references specified
00207 /// in the VMap are changed to refer to their mapped value instead of the
00208 /// original one.  If any of the arguments to the function are in the VMap,
00209 /// the arguments are deleted from the resultant function.  The VMap is
00210 /// updated to include mappings from all of the instructions and basicblocks in
00211 /// the function from their old to new values.
00212 ///
00213 Function *llvm::CloneFunction(const Function *F, ValueToValueMapTy &VMap,
00214                               bool ModuleLevelChanges,
00215                               ClonedCodeInfo *CodeInfo) {
00216   std::vector<Type*> ArgTypes;
00217 
00218   // The user might be deleting arguments to the function by specifying them in
00219   // the VMap.  If so, we need to not add the arguments to the arg ty vector
00220   //
00221   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00222        I != E; ++I)
00223     if (VMap.count(I) == 0)  // Haven't mapped the argument to anything yet?
00224       ArgTypes.push_back(I->getType());
00225 
00226   // Create a new function type...
00227   FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
00228                                     ArgTypes, F->getFunctionType()->isVarArg());
00229 
00230   // Create the new function...
00231   Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName());
00232 
00233   // Loop over the arguments, copying the names of the mapped arguments over...
00234   Function::arg_iterator DestI = NewF->arg_begin();
00235   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00236        I != E; ++I)
00237     if (VMap.count(I) == 0) {   // Is this argument preserved?
00238       DestI->setName(I->getName()); // Copy the name over...
00239       VMap[I] = DestI++;        // Add mapping to VMap
00240     }
00241 
00242   if (ModuleLevelChanges)
00243     CloneDebugInfoMetadata(NewF, F, VMap);
00244 
00245   SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
00246   CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo);
00247   return NewF;
00248 }
00249 
00250 
00251 
00252 namespace {
00253   /// PruningFunctionCloner - This class is a private class used to implement
00254   /// the CloneAndPruneFunctionInto method.
00255   struct PruningFunctionCloner {
00256     Function *NewFunc;
00257     const Function *OldFunc;
00258     ValueToValueMapTy &VMap;
00259     bool ModuleLevelChanges;
00260     const char *NameSuffix;
00261     ClonedCodeInfo *CodeInfo;
00262     const DataLayout *DL;
00263   public:
00264     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
00265                           ValueToValueMapTy &valueMap,
00266                           bool moduleLevelChanges,
00267                           const char *nameSuffix, 
00268                           ClonedCodeInfo *codeInfo,
00269                           const DataLayout *DL)
00270     : NewFunc(newFunc), OldFunc(oldFunc),
00271       VMap(valueMap), ModuleLevelChanges(moduleLevelChanges),
00272       NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL) {
00273     }
00274 
00275     /// CloneBlock - The specified block is found to be reachable, clone it and
00276     /// anything that it can reach.
00277     void CloneBlock(const BasicBlock *BB,
00278                     std::vector<const BasicBlock*> &ToClone);
00279   };
00280 }
00281 
00282 /// CloneBlock - The specified block is found to be reachable, clone it and
00283 /// anything that it can reach.
00284 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
00285                                        std::vector<const BasicBlock*> &ToClone){
00286   WeakVH &BBEntry = VMap[BB];
00287 
00288   // Have we already cloned this block?
00289   if (BBEntry) return;
00290   
00291   // Nope, clone it now.
00292   BasicBlock *NewBB;
00293   BBEntry = NewBB = BasicBlock::Create(BB->getContext());
00294   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00295 
00296   // It is only legal to clone a function if a block address within that
00297   // function is never referenced outside of the function.  Given that, we
00298   // want to map block addresses from the old function to block addresses in
00299   // the clone. (This is different from the generic ValueMapper
00300   // implementation, which generates an invalid blockaddress when
00301   // cloning a function.)
00302   //
00303   // Note that we don't need to fix the mapping for unreachable blocks;
00304   // the default mapping there is safe.
00305   if (BB->hasAddressTaken()) {
00306     Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
00307                                             const_cast<BasicBlock*>(BB));
00308     VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
00309   }
00310     
00311 
00312   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00313   
00314   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
00315   // loop doesn't include the terminator.
00316   for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
00317        II != IE; ++II) {
00318     Instruction *NewInst = II->clone();
00319 
00320     // Eagerly remap operands to the newly cloned instruction, except for PHI
00321     // nodes for which we defer processing until we update the CFG.
00322     if (!isa<PHINode>(NewInst)) {
00323       RemapInstruction(NewInst, VMap,
00324                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
00325 
00326       // If we can simplify this instruction to some other value, simply add
00327       // a mapping to that value rather than inserting a new instruction into
00328       // the basic block.
00329       if (Value *V = SimplifyInstruction(NewInst, DL)) {
00330         // On the off-chance that this simplifies to an instruction in the old
00331         // function, map it back into the new function.
00332         if (Value *MappedV = VMap.lookup(V))
00333           V = MappedV;
00334 
00335         VMap[II] = V;
00336         delete NewInst;
00337         continue;
00338       }
00339     }
00340 
00341     if (II->hasName())
00342       NewInst->setName(II->getName()+NameSuffix);
00343     VMap[II] = NewInst;                // Add instruction map to value.
00344     NewBB->getInstList().push_back(NewInst);
00345     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
00346     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00347       if (isa<ConstantInt>(AI->getArraySize()))
00348         hasStaticAllocas = true;
00349       else
00350         hasDynamicAllocas = true;
00351     }
00352   }
00353   
00354   // Finally, clone over the terminator.
00355   const TerminatorInst *OldTI = BB->getTerminator();
00356   bool TerminatorDone = false;
00357   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
00358     if (BI->isConditional()) {
00359       // If the condition was a known constant in the callee...
00360       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
00361       // Or is a known constant in the caller...
00362       if (Cond == 0) {
00363         Value *V = VMap[BI->getCondition()];
00364         Cond = dyn_cast_or_null<ConstantInt>(V);
00365       }
00366 
00367       // Constant fold to uncond branch!
00368       if (Cond) {
00369         BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
00370         VMap[OldTI] = BranchInst::Create(Dest, NewBB);
00371         ToClone.push_back(Dest);
00372         TerminatorDone = true;
00373       }
00374     }
00375   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
00376     // If switching on a value known constant in the caller.
00377     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
00378     if (Cond == 0) { // Or known constant after constant prop in the callee...
00379       Value *V = VMap[SI->getCondition()];
00380       Cond = dyn_cast_or_null<ConstantInt>(V);
00381     }
00382     if (Cond) {     // Constant fold to uncond branch!
00383       SwitchInst::ConstCaseIt Case = SI->findCaseValue(Cond);
00384       BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor());
00385       VMap[OldTI] = BranchInst::Create(Dest, NewBB);
00386       ToClone.push_back(Dest);
00387       TerminatorDone = true;
00388     }
00389   }
00390   
00391   if (!TerminatorDone) {
00392     Instruction *NewInst = OldTI->clone();
00393     if (OldTI->hasName())
00394       NewInst->setName(OldTI->getName()+NameSuffix);
00395     NewBB->getInstList().push_back(NewInst);
00396     VMap[OldTI] = NewInst;             // Add instruction map to value.
00397     
00398     // Recursively clone any reachable successor blocks.
00399     const TerminatorInst *TI = BB->getTerminator();
00400     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00401       ToClone.push_back(TI->getSuccessor(i));
00402   }
00403   
00404   if (CodeInfo) {
00405     CodeInfo->ContainsCalls          |= hasCalls;
00406     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00407     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00408       BB != &BB->getParent()->front();
00409   }
00410 }
00411 
00412 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
00413 /// except that it does some simple constant prop and DCE on the fly.  The
00414 /// effect of this is to copy significantly less code in cases where (for
00415 /// example) a function call with constant arguments is inlined, and those
00416 /// constant arguments cause a significant amount of code in the callee to be
00417 /// dead.  Since this doesn't produce an exact copy of the input, it can't be
00418 /// used for things like CloneFunction or CloneModule.
00419 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
00420                                      ValueToValueMapTy &VMap,
00421                                      bool ModuleLevelChanges,
00422                                      SmallVectorImpl<ReturnInst*> &Returns,
00423                                      const char *NameSuffix, 
00424                                      ClonedCodeInfo *CodeInfo,
00425                                      const DataLayout *DL,
00426                                      Instruction *TheCall) {
00427   assert(NameSuffix && "NameSuffix cannot be null!");
00428   
00429 #ifndef NDEBUG
00430   for (Function::const_arg_iterator II = OldFunc->arg_begin(), 
00431        E = OldFunc->arg_end(); II != E; ++II)
00432     assert(VMap.count(II) && "No mapping from source argument specified!");
00433 #endif
00434 
00435   PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
00436                             NameSuffix, CodeInfo, DL);
00437 
00438   // Clone the entry block, and anything recursively reachable from it.
00439   std::vector<const BasicBlock*> CloneWorklist;
00440   CloneWorklist.push_back(&OldFunc->getEntryBlock());
00441   while (!CloneWorklist.empty()) {
00442     const BasicBlock *BB = CloneWorklist.back();
00443     CloneWorklist.pop_back();
00444     PFC.CloneBlock(BB, CloneWorklist);
00445   }
00446   
00447   // Loop over all of the basic blocks in the old function.  If the block was
00448   // reachable, we have cloned it and the old block is now in the value map:
00449   // insert it into the new function in the right order.  If not, ignore it.
00450   //
00451   // Defer PHI resolution until rest of function is resolved.
00452   SmallVector<const PHINode*, 16> PHIToResolve;
00453   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00454        BI != BE; ++BI) {
00455     Value *V = VMap[BI];
00456     BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
00457     if (NewBB == 0) continue;  // Dead block.
00458 
00459     // Add the new block to the new function.
00460     NewFunc->getBasicBlockList().push_back(NewBB);
00461 
00462     // Handle PHI nodes specially, as we have to remove references to dead
00463     // blocks.
00464     for (BasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I)
00465       if (const PHINode *PN = dyn_cast<PHINode>(I))
00466         PHIToResolve.push_back(PN);
00467       else
00468         break;
00469 
00470     // Finally, remap the terminator instructions, as those can't be remapped
00471     // until all BBs are mapped.
00472     RemapInstruction(NewBB->getTerminator(), VMap,
00473                      ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
00474   }
00475   
00476   // Defer PHI resolution until rest of function is resolved, PHI resolution
00477   // requires the CFG to be up-to-date.
00478   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
00479     const PHINode *OPN = PHIToResolve[phino];
00480     unsigned NumPreds = OPN->getNumIncomingValues();
00481     const BasicBlock *OldBB = OPN->getParent();
00482     BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);
00483 
00484     // Map operands for blocks that are live and remove operands for blocks
00485     // that are dead.
00486     for (; phino != PHIToResolve.size() &&
00487          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
00488       OPN = PHIToResolve[phino];
00489       PHINode *PN = cast<PHINode>(VMap[OPN]);
00490       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
00491         Value *V = VMap[PN->getIncomingBlock(pred)];
00492         if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
00493           Value *InVal = MapValue(PN->getIncomingValue(pred),
00494                                   VMap, 
00495                         ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
00496           assert(InVal && "Unknown input value?");
00497           PN->setIncomingValue(pred, InVal);
00498           PN->setIncomingBlock(pred, MappedBlock);
00499         } else {
00500           PN->removeIncomingValue(pred, false);
00501           --pred, --e;  // Revisit the next entry.
00502         }
00503       } 
00504     }
00505     
00506     // The loop above has removed PHI entries for those blocks that are dead
00507     // and has updated others.  However, if a block is live (i.e. copied over)
00508     // but its terminator has been changed to not go to this block, then our
00509     // phi nodes will have invalid entries.  Update the PHI nodes in this
00510     // case.
00511     PHINode *PN = cast<PHINode>(NewBB->begin());
00512     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
00513     if (NumPreds != PN->getNumIncomingValues()) {
00514       assert(NumPreds < PN->getNumIncomingValues());
00515       // Count how many times each predecessor comes to this block.
00516       std::map<BasicBlock*, unsigned> PredCount;
00517       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
00518            PI != E; ++PI)
00519         --PredCount[*PI];
00520       
00521       // Figure out how many entries to remove from each PHI.
00522       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00523         ++PredCount[PN->getIncomingBlock(i)];
00524       
00525       // At this point, the excess predecessor entries are positive in the
00526       // map.  Loop over all of the PHIs and remove excess predecessor
00527       // entries.
00528       BasicBlock::iterator I = NewBB->begin();
00529       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
00530         for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
00531              E = PredCount.end(); PCI != E; ++PCI) {
00532           BasicBlock *Pred     = PCI->first;
00533           for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
00534             PN->removeIncomingValue(Pred, false);
00535         }
00536       }
00537     }
00538     
00539     // If the loops above have made these phi nodes have 0 or 1 operand,
00540     // replace them with undef or the input value.  We must do this for
00541     // correctness, because 0-operand phis are not valid.
00542     PN = cast<PHINode>(NewBB->begin());
00543     if (PN->getNumIncomingValues() == 0) {
00544       BasicBlock::iterator I = NewBB->begin();
00545       BasicBlock::const_iterator OldI = OldBB->begin();
00546       while ((PN = dyn_cast<PHINode>(I++))) {
00547         Value *NV = UndefValue::get(PN->getType());
00548         PN->replaceAllUsesWith(NV);
00549         assert(VMap[OldI] == PN && "VMap mismatch");
00550         VMap[OldI] = NV;
00551         PN->eraseFromParent();
00552         ++OldI;
00553       }
00554     }
00555   }
00556 
00557   // Make a second pass over the PHINodes now that all of them have been
00558   // remapped into the new function, simplifying the PHINode and performing any
00559   // recursive simplifications exposed. This will transparently update the
00560   // WeakVH in the VMap. Notably, we rely on that so that if we coalesce
00561   // two PHINodes, the iteration over the old PHIs remains valid, and the
00562   // mapping will just map us to the new node (which may not even be a PHI
00563   // node).
00564   for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
00565     if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]]))
00566       recursivelySimplifyInstruction(PN, DL);
00567 
00568   // Now that the inlined function body has been fully constructed, go through
00569   // and zap unconditional fall-through branches.  This happen all the time when
00570   // specializing code: code specialization turns conditional branches into
00571   // uncond branches, and this code folds them.
00572   Function::iterator Begin = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]);
00573   Function::iterator I = Begin;
00574   while (I != NewFunc->end()) {
00575     // Check if this block has become dead during inlining or other
00576     // simplifications. Note that the first block will appear dead, as it has
00577     // not yet been wired up properly.
00578     if (I != Begin && (pred_begin(I) == pred_end(I) ||
00579                        I->getSinglePredecessor() == I)) {
00580       BasicBlock *DeadBB = I++;
00581       DeleteDeadBlock(DeadBB);
00582       continue;
00583     }
00584 
00585     // We need to simplify conditional branches and switches with a constant
00586     // operand. We try to prune these out when cloning, but if the
00587     // simplification required looking through PHI nodes, those are only
00588     // available after forming the full basic block. That may leave some here,
00589     // and we still want to prune the dead code as early as possible.
00590     ConstantFoldTerminator(I);
00591 
00592     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
00593     if (!BI || BI->isConditional()) { ++I; continue; }
00594     
00595     BasicBlock *Dest = BI->getSuccessor(0);
00596     if (!Dest->getSinglePredecessor()) {
00597       ++I; continue;
00598     }
00599 
00600     // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
00601     // above should have zapped all of them..
00602     assert(!isa<PHINode>(Dest->begin()));
00603 
00604     // We know all single-entry PHI nodes in the inlined function have been
00605     // removed, so we just need to splice the blocks.
00606     BI->eraseFromParent();
00607     
00608     // Make all PHI nodes that referred to Dest now refer to I as their source.
00609     Dest->replaceAllUsesWith(I);
00610 
00611     // Move all the instructions in the succ to the pred.
00612     I->getInstList().splice(I->end(), Dest->getInstList());
00613     
00614     // Remove the dest block.
00615     Dest->eraseFromParent();
00616     
00617     // Do not increment I, iteratively merge all things this block branches to.
00618   }
00619 
00620   // Make a final pass over the basic blocks from theh old function to gather
00621   // any return instructions which survived folding. We have to do this here
00622   // because we can iteratively remove and merge returns above.
00623   for (Function::iterator I = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]),
00624                           E = NewFunc->end();
00625        I != E; ++I)
00626     if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
00627       Returns.push_back(RI);
00628 }