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/Constants.h"
00018 #include "llvm/DerivedTypes.h"
00019 #include "llvm/Instructions.h"
00020 #include "llvm/IntrinsicInst.h"
00021 #include "llvm/GlobalVariable.h"
00022 #include "llvm/Function.h"
00023 #include "llvm/LLVMContext.h"
00024 #include "llvm/Support/CFG.h"
00025 #include "llvm/Support/Compiler.h"
00026 #include "llvm/Transforms/Utils/ValueMapper.h"
00027 #include "llvm/Analysis/ConstantFolding.h"
00028 #include "llvm/Analysis/DebugInfo.h"
00029 #include "llvm/ADT/SmallVector.h"
00030 #include <map>
00031 using namespace llvm;
00032 
00033 // CloneBasicBlock - See comments in Cloning.h
00034 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
00035                                   DenseMap<const Value*, Value*> &ValueMap,
00036                                   const char *NameSuffix, Function *F,
00037                                   ClonedCodeInfo *CodeInfo) {
00038   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
00039   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00040 
00041   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00042   
00043   // Loop over all instructions, and copy them over.
00044   for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
00045        II != IE; ++II) {
00046     Instruction *NewInst = II->clone(BB->getContext());
00047     if (II->hasName())
00048       NewInst->setName(II->getName()+NameSuffix);
00049     NewBB->getInstList().push_back(NewInst);
00050     ValueMap[II] = NewInst;                // Add instruction map to value.
00051     
00052     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
00053     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00054       if (isa<ConstantInt>(AI->getArraySize()))
00055         hasStaticAllocas = true;
00056       else
00057         hasDynamicAllocas = true;
00058     }
00059   }
00060   
00061   if (CodeInfo) {
00062     CodeInfo->ContainsCalls          |= hasCalls;
00063     CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(BB->getTerminator());
00064     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00065     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00066                                         BB != &BB->getParent()->getEntryBlock();
00067   }
00068   return NewBB;
00069 }
00070 
00071 // Clone OldFunc into NewFunc, transforming the old arguments into references to
00072 // ArgMap values.
00073 //
00074 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
00075                              DenseMap<const Value*, Value*> &ValueMap,
00076                              std::vector<ReturnInst*> &Returns,
00077                              const char *NameSuffix, ClonedCodeInfo *CodeInfo) {
00078   assert(NameSuffix && "NameSuffix cannot be null!");
00079 
00080 #ifndef NDEBUG
00081   for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
00082        E = OldFunc->arg_end(); I != E; ++I)
00083     assert(ValueMap.count(I) && "No mapping from source argument specified!");
00084 #endif
00085 
00086   // Clone any attributes.
00087   if (NewFunc->arg_size() == OldFunc->arg_size())
00088     NewFunc->copyAttributesFrom(OldFunc);
00089   else {
00090     //Some arguments were deleted with the ValueMap. Copy arguments one by one
00091     for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
00092            E = OldFunc->arg_end(); I != E; ++I)
00093       if (Argument* Anew = dyn_cast<Argument>(ValueMap[I]))
00094         Anew->addAttr( OldFunc->getAttributes()
00095                        .getParamAttributes(I->getArgNo() + 1));
00096     NewFunc->setAttributes(NewFunc->getAttributes()
00097                            .addAttr(0, OldFunc->getAttributes()
00098                                      .getRetAttributes()));
00099     NewFunc->setAttributes(NewFunc->getAttributes()
00100                            .addAttr(~0, OldFunc->getAttributes()
00101                                      .getFnAttributes()));
00102 
00103   }
00104 
00105   // Loop over all of the basic blocks in the function, cloning them as
00106   // appropriate.  Note that we save BE this way in order to handle cloning of
00107   // recursive functions into themselves.
00108   //
00109   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00110        BI != BE; ++BI) {
00111     const BasicBlock &BB = *BI;
00112 
00113     // Create a new basic block and copy instructions into it!
00114     BasicBlock *CBB = CloneBasicBlock(&BB, ValueMap, NameSuffix, NewFunc,
00115                                       CodeInfo);
00116     ValueMap[&BB] = CBB;                       // Add basic block mapping.
00117 
00118     if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
00119       Returns.push_back(RI);
00120   }
00121 
00122   // Loop over all of the instructions in the function, fixing up operand
00123   // references as we go.  This uses ValueMap to do all the hard work.
00124   //
00125   for (Function::iterator BB = cast<BasicBlock>(ValueMap[OldFunc->begin()]),
00126          BE = NewFunc->end(); BB != BE; ++BB)
00127     // Loop over all instructions, fixing each one as we find it...
00128     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
00129       RemapInstruction(II, ValueMap);
00130 }
00131 
00132 /// CloneFunction - Return a copy of the specified function, but without
00133 /// embedding the function into another module.  Also, any references specified
00134 /// in the ValueMap are changed to refer to their mapped value instead of the
00135 /// original one.  If any of the arguments to the function are in the ValueMap,
00136 /// the arguments are deleted from the resultant function.  The ValueMap is
00137 /// updated to include mappings from all of the instructions and basicblocks in
00138 /// the function from their old to new values.
00139 ///
00140 Function *llvm::CloneFunction(const Function *F,
00141                               DenseMap<const Value*, Value*> &ValueMap,
00142                               ClonedCodeInfo *CodeInfo) {
00143   std::vector<const Type*> ArgTypes;
00144 
00145   // The user might be deleting arguments to the function by specifying them in
00146   // the ValueMap.  If so, we need to not add the arguments to the arg ty vector
00147   //
00148   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00149        I != E; ++I)
00150     if (ValueMap.count(I) == 0)  // Haven't mapped the argument to anything yet?
00151       ArgTypes.push_back(I->getType());
00152 
00153   // Create a new function type...
00154   FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
00155                                     ArgTypes, F->getFunctionType()->isVarArg());
00156 
00157   // Create the new function...
00158   Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName());
00159 
00160   // Loop over the arguments, copying the names of the mapped arguments over...
00161   Function::arg_iterator DestI = NewF->arg_begin();
00162   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00163        I != E; ++I)
00164     if (ValueMap.count(I) == 0) {   // Is this argument preserved?
00165       DestI->setName(I->getName()); // Copy the name over...
00166       ValueMap[I] = DestI++;        // Add mapping to ValueMap
00167     }
00168 
00169   std::vector<ReturnInst*> Returns;  // Ignore returns cloned...
00170   CloneFunctionInto(NewF, F, ValueMap, Returns, "", CodeInfo);
00171   return NewF;
00172 }
00173 
00174 
00175 
00176 namespace {
00177   /// PruningFunctionCloner - This class is a private class used to implement
00178   /// the CloneAndPruneFunctionInto method.
00179   struct VISIBILITY_HIDDEN PruningFunctionCloner {
00180     Function *NewFunc;
00181     const Function *OldFunc;
00182     DenseMap<const Value*, Value*> &ValueMap;
00183     std::vector<ReturnInst*> &Returns;
00184     const char *NameSuffix;
00185     ClonedCodeInfo *CodeInfo;
00186     const TargetData *TD;
00187     Value *DbgFnStart;
00188   public:
00189     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
00190                           DenseMap<const Value*, Value*> &valueMap,
00191                           std::vector<ReturnInst*> &returns,
00192                           const char *nameSuffix, 
00193                           ClonedCodeInfo *codeInfo,
00194                           const TargetData *td)
00195     : NewFunc(newFunc), OldFunc(oldFunc), ValueMap(valueMap), Returns(returns),
00196       NameSuffix(nameSuffix), CodeInfo(codeInfo), TD(td), DbgFnStart(NULL) {
00197     }
00198 
00199     /// CloneBlock - The specified block is found to be reachable, clone it and
00200     /// anything that it can reach.
00201     void CloneBlock(const BasicBlock *BB,
00202                     std::vector<const BasicBlock*> &ToClone);
00203     
00204   public:
00205     /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
00206     /// mapping its operands through ValueMap if they are available.
00207     Constant *ConstantFoldMappedInstruction(const Instruction *I);
00208   };
00209 }
00210 
00211 /// CloneBlock - The specified block is found to be reachable, clone it and
00212 /// anything that it can reach.
00213 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
00214                                        std::vector<const BasicBlock*> &ToClone){
00215   Value *&BBEntry = ValueMap[BB];
00216 
00217   // Have we already cloned this block?
00218   if (BBEntry) return;
00219   
00220   // Nope, clone it now.
00221   BasicBlock *NewBB;
00222   BBEntry = NewBB = BasicBlock::Create(BB->getContext());
00223   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00224 
00225   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00226   
00227   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
00228   // loop doesn't include the terminator.
00229   for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
00230        II != IE; ++II) {
00231     // If this instruction constant folds, don't bother cloning the instruction,
00232     // instead, just add the constant to the value map.
00233     if (Constant *C = ConstantFoldMappedInstruction(II)) {
00234       ValueMap[II] = C;
00235       continue;
00236     }
00237 
00238     // Do not clone llvm.dbg.region.end. It will be adjusted by the inliner.
00239     if (const DbgFuncStartInst *DFSI = dyn_cast<DbgFuncStartInst>(II)) {
00240       if (DbgFnStart == NULL) {
00241         DISubprogram SP(cast<GlobalVariable>(DFSI->getSubprogram()));
00242         if (SP.describes(BB->getParent()))
00243           DbgFnStart = DFSI->getSubprogram();
00244       }
00245     } 
00246     if (const DbgRegionEndInst *DREIS = dyn_cast<DbgRegionEndInst>(II)) {
00247       if (DREIS->getContext() == DbgFnStart)
00248         continue;
00249     }
00250       
00251     Instruction *NewInst = II->clone(BB->getContext());
00252     if (II->hasName())
00253       NewInst->setName(II->getName()+NameSuffix);
00254     NewBB->getInstList().push_back(NewInst);
00255     ValueMap[II] = NewInst;                // Add instruction map to value.
00256     
00257     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
00258     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00259       if (isa<ConstantInt>(AI->getArraySize()))
00260         hasStaticAllocas = true;
00261       else
00262         hasDynamicAllocas = true;
00263     }
00264   }
00265   
00266   // Finally, clone over the terminator.
00267   const TerminatorInst *OldTI = BB->getTerminator();
00268   bool TerminatorDone = false;
00269   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
00270     if (BI->isConditional()) {
00271       // If the condition was a known constant in the callee...
00272       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
00273       // Or is a known constant in the caller...
00274       if (Cond == 0)  
00275         Cond = dyn_cast_or_null<ConstantInt>(ValueMap[BI->getCondition()]);
00276 
00277       // Constant fold to uncond branch!
00278       if (Cond) {
00279         BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
00280         ValueMap[OldTI] = BranchInst::Create(Dest, NewBB);
00281         ToClone.push_back(Dest);
00282         TerminatorDone = true;
00283       }
00284     }
00285   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
00286     // If switching on a value known constant in the caller.
00287     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
00288     if (Cond == 0)  // Or known constant after constant prop in the callee...
00289       Cond = dyn_cast_or_null<ConstantInt>(ValueMap[SI->getCondition()]);
00290     if (Cond) {     // Constant fold to uncond branch!
00291       BasicBlock *Dest = SI->getSuccessor(SI->findCaseValue(Cond));
00292       ValueMap[OldTI] = BranchInst::Create(Dest, NewBB);
00293       ToClone.push_back(Dest);
00294       TerminatorDone = true;
00295     }
00296   }
00297   
00298   if (!TerminatorDone) {
00299     Instruction *NewInst = OldTI->clone(BB->getContext());
00300     if (OldTI->hasName())
00301       NewInst->setName(OldTI->getName()+NameSuffix);
00302     NewBB->getInstList().push_back(NewInst);
00303     ValueMap[OldTI] = NewInst;             // Add instruction map to value.
00304     
00305     // Recursively clone any reachable successor blocks.
00306     const TerminatorInst *TI = BB->getTerminator();
00307     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00308       ToClone.push_back(TI->getSuccessor(i));
00309   }
00310   
00311   if (CodeInfo) {
00312     CodeInfo->ContainsCalls          |= hasCalls;
00313     CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(OldTI);
00314     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00315     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00316       BB != &BB->getParent()->front();
00317   }
00318   
00319   if (ReturnInst *RI = dyn_cast<ReturnInst>(NewBB->getTerminator()))
00320     Returns.push_back(RI);
00321 }
00322 
00323 /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
00324 /// mapping its operands through ValueMap if they are available.
00325 Constant *PruningFunctionCloner::
00326 ConstantFoldMappedInstruction(const Instruction *I) {
00327   LLVMContext &Context = I->getContext();
00328   
00329   SmallVector<Constant*, 8> Ops;
00330   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00331     if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i),
00332                                                            ValueMap,
00333                                                            Context)))
00334       Ops.push_back(Op);
00335     else
00336       return 0;  // All operands not constant!
00337 
00338   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
00339     return ConstantFoldCompareInstOperands(CI->getPredicate(),
00340                                            &Ops[0], Ops.size(), 
00341                                            Context, TD);
00342 
00343   if (const LoadInst *LI = dyn_cast<LoadInst>(I))
00344     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0]))
00345       if (!LI->isVolatile() && CE->getOpcode() == Instruction::GetElementPtr)
00346         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
00347           if (GV->isConstant() && GV->hasDefinitiveInitializer())
00348             return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(),
00349                                                           CE, Context);
00350 
00351   return ConstantFoldInstOperands(I->getOpcode(), I->getType(), &Ops[0],
00352                                   Ops.size(), Context, TD);
00353 }
00354 
00355 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
00356 /// except that it does some simple constant prop and DCE on the fly.  The
00357 /// effect of this is to copy significantly less code in cases where (for
00358 /// example) a function call with constant arguments is inlined, and those
00359 /// constant arguments cause a significant amount of code in the callee to be
00360 /// dead.  Since this doesn't produce an exact copy of the input, it can't be
00361 /// used for things like CloneFunction or CloneModule.
00362 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
00363                                      DenseMap<const Value*, Value*> &ValueMap,
00364                                      std::vector<ReturnInst*> &Returns,
00365                                      const char *NameSuffix, 
00366                                      ClonedCodeInfo *CodeInfo,
00367                                      const TargetData *TD) {
00368   assert(NameSuffix && "NameSuffix cannot be null!");
00369   LLVMContext &Context = OldFunc->getContext();
00370   
00371 #ifndef NDEBUG
00372   for (Function::const_arg_iterator II = OldFunc->arg_begin(), 
00373        E = OldFunc->arg_end(); II != E; ++II)
00374     assert(ValueMap.count(II) && "No mapping from source argument specified!");
00375 #endif
00376 
00377   PruningFunctionCloner PFC(NewFunc, OldFunc, ValueMap, Returns,
00378                             NameSuffix, CodeInfo, TD);
00379 
00380   // Clone the entry block, and anything recursively reachable from it.
00381   std::vector<const BasicBlock*> CloneWorklist;
00382   CloneWorklist.push_back(&OldFunc->getEntryBlock());
00383   while (!CloneWorklist.empty()) {
00384     const BasicBlock *BB = CloneWorklist.back();
00385     CloneWorklist.pop_back();
00386     PFC.CloneBlock(BB, CloneWorklist);
00387   }
00388   
00389   // Loop over all of the basic blocks in the old function.  If the block was
00390   // reachable, we have cloned it and the old block is now in the value map:
00391   // insert it into the new function in the right order.  If not, ignore it.
00392   //
00393   // Defer PHI resolution until rest of function is resolved.
00394   std::vector<const PHINode*> PHIToResolve;
00395   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00396        BI != BE; ++BI) {
00397     BasicBlock *NewBB = cast_or_null<BasicBlock>(ValueMap[BI]);
00398     if (NewBB == 0) continue;  // Dead block.
00399 
00400     // Add the new block to the new function.
00401     NewFunc->getBasicBlockList().push_back(NewBB);
00402     
00403     // Loop over all of the instructions in the block, fixing up operand
00404     // references as we go.  This uses ValueMap to do all the hard work.
00405     //
00406     BasicBlock::iterator I = NewBB->begin();
00407     
00408     // Handle PHI nodes specially, as we have to remove references to dead
00409     // blocks.
00410     if (PHINode *PN = dyn_cast<PHINode>(I)) {
00411       // Skip over all PHI nodes, remembering them for later.
00412       BasicBlock::const_iterator OldI = BI->begin();
00413       for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI)
00414         PHIToResolve.push_back(cast<PHINode>(OldI));
00415     }
00416     
00417     // Otherwise, remap the rest of the instructions normally.
00418     for (; I != NewBB->end(); ++I)
00419       RemapInstruction(I, ValueMap);
00420   }
00421   
00422   // Defer PHI resolution until rest of function is resolved, PHI resolution
00423   // requires the CFG to be up-to-date.
00424   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
00425     const PHINode *OPN = PHIToResolve[phino];
00426     unsigned NumPreds = OPN->getNumIncomingValues();
00427     const BasicBlock *OldBB = OPN->getParent();
00428     BasicBlock *NewBB = cast<BasicBlock>(ValueMap[OldBB]);
00429 
00430     // Map operands for blocks that are live and remove operands for blocks
00431     // that are dead.
00432     for (; phino != PHIToResolve.size() &&
00433          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
00434       OPN = PHIToResolve[phino];
00435       PHINode *PN = cast<PHINode>(ValueMap[OPN]);
00436       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
00437         if (BasicBlock *MappedBlock = 
00438             cast_or_null<BasicBlock>(ValueMap[PN->getIncomingBlock(pred)])) {
00439           Value *InVal = MapValue(PN->getIncomingValue(pred),
00440                                   ValueMap, Context);
00441           assert(InVal && "Unknown input value?");
00442           PN->setIncomingValue(pred, InVal);
00443           PN->setIncomingBlock(pred, MappedBlock);
00444         } else {
00445           PN->removeIncomingValue(pred, false);
00446           --pred, --e;  // Revisit the next entry.
00447         }
00448       } 
00449     }
00450     
00451     // The loop above has removed PHI entries for those blocks that are dead
00452     // and has updated others.  However, if a block is live (i.e. copied over)
00453     // but its terminator has been changed to not go to this block, then our
00454     // phi nodes will have invalid entries.  Update the PHI nodes in this
00455     // case.
00456     PHINode *PN = cast<PHINode>(NewBB->begin());
00457     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
00458     if (NumPreds != PN->getNumIncomingValues()) {
00459       assert(NumPreds < PN->getNumIncomingValues());
00460       // Count how many times each predecessor comes to this block.
00461       std::map<BasicBlock*, unsigned> PredCount;
00462       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
00463            PI != E; ++PI)
00464         --PredCount[*PI];
00465       
00466       // Figure out how many entries to remove from each PHI.
00467       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00468         ++PredCount[PN->getIncomingBlock(i)];
00469       
00470       // At this point, the excess predecessor entries are positive in the
00471       // map.  Loop over all of the PHIs and remove excess predecessor
00472       // entries.
00473       BasicBlock::iterator I = NewBB->begin();
00474       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
00475         for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
00476              E = PredCount.end(); PCI != E; ++PCI) {
00477           BasicBlock *Pred     = PCI->first;
00478           for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
00479             PN->removeIncomingValue(Pred, false);
00480         }
00481       }
00482     }
00483     
00484     // If the loops above have made these phi nodes have 0 or 1 operand,
00485     // replace them with undef or the input value.  We must do this for
00486     // correctness, because 0-operand phis are not valid.
00487     PN = cast<PHINode>(NewBB->begin());
00488     if (PN->getNumIncomingValues() == 0) {
00489       BasicBlock::iterator I = NewBB->begin();
00490       BasicBlock::const_iterator OldI = OldBB->begin();
00491       while ((PN = dyn_cast<PHINode>(I++))) {
00492         Value *NV = UndefValue::get(PN->getType());
00493         PN->replaceAllUsesWith(NV);
00494         assert(ValueMap[OldI] == PN && "ValueMap mismatch");
00495         ValueMap[OldI] = NV;
00496         PN->eraseFromParent();
00497         ++OldI;
00498       }
00499     }
00500     // NOTE: We cannot eliminate single entry phi nodes here, because of
00501     // ValueMap.  Single entry phi nodes can have multiple ValueMap entries
00502     // pointing at them.  Thus, deleting one would require scanning the ValueMap
00503     // to update any entries in it that would require that.  This would be
00504     // really slow.
00505   }
00506   
00507   // Now that the inlined function body has been fully constructed, go through
00508   // and zap unconditional fall-through branches.  This happen all the time when
00509   // specializing code: code specialization turns conditional branches into
00510   // uncond branches, and this code folds them.
00511   Function::iterator I = cast<BasicBlock>(ValueMap[&OldFunc->getEntryBlock()]);
00512   while (I != NewFunc->end()) {
00513     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
00514     if (!BI || BI->isConditional()) { ++I; continue; }
00515     
00516     // Note that we can't eliminate uncond branches if the destination has
00517     // single-entry PHI nodes.  Eliminating the single-entry phi nodes would
00518     // require scanning the ValueMap to update any entries that point to the phi
00519     // node.
00520     BasicBlock *Dest = BI->getSuccessor(0);
00521     if (!Dest->getSinglePredecessor() || isa<PHINode>(Dest->begin())) {
00522       ++I; continue;
00523     }
00524     
00525     // We know all single-entry PHI nodes in the inlined function have been
00526     // removed, so we just need to splice the blocks.
00527     BI->eraseFromParent();
00528     
00529     // Move all the instructions in the succ to the pred.
00530     I->getInstList().splice(I->end(), Dest->getInstList());
00531     
00532     // Make all PHI nodes that referred to Dest now refer to I as their source.
00533     Dest->replaceAllUsesWith(I);
00534 
00535     // Remove the dest block.
00536     Dest->eraseFromParent();
00537     
00538     // Do not increment I, iteratively merge all things this block branches to.
00539   }
00540 }