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 nullptr;
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(DICompileUnit CU, DIArray SPs, Metadata *NewSP) {
00168   SmallVector<Metadata *, 16> NewSPs;
00169   NewSPs.reserve(SPs->getNumOperands() + 1);
00170   for (unsigned I = 0, E = SPs->getNumOperands(); I != E; ++I)
00171     NewSPs.push_back(SPs->getOperand(I));
00172   NewSPs.push_back(NewSP);
00173   CU.replaceSubprograms(DIArray(MDNode::get(CU->getContext(), NewSPs)));
00174 }
00175 
00176 // Clone the module-level debug info associated with OldFunc. The cloned data
00177 // will point to NewFunc instead.
00178 static void CloneDebugInfoMetadata(Function *NewFunc, const Function *OldFunc,
00179                             ValueToValueMapTy &VMap) {
00180   DebugInfoFinder Finder;
00181   Finder.processModule(*OldFunc->getParent());
00182 
00183   const MDNode *OldSubprogramMDNode = FindSubprogram(OldFunc, Finder);
00184   if (!OldSubprogramMDNode) return;
00185 
00186   // Ensure that OldFunc appears in the map.
00187   // (if it's already there it must point to NewFunc anyway)
00188   VMap[OldFunc] = NewFunc;
00189   DISubprogram NewSubprogram(MapMetadata(OldSubprogramMDNode, VMap));
00190 
00191   for (DICompileUnit CU : Finder.compile_units()) {
00192     DIArray Subprograms(CU.getSubprograms());
00193 
00194     // If the compile unit's function list contains the old function, it should
00195     // also contain the new one.
00196     for (unsigned i = 0; i < Subprograms.getNumElements(); i++) {
00197       if ((MDNode*)Subprograms.getElement(i) == OldSubprogramMDNode) {
00198         AddOperand(CU, Subprograms, NewSubprogram);
00199         break;
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     CloningDirector *Director;
00264     ValueMapTypeRemapper *TypeMapper;
00265     ValueMaterializer *Materializer;
00266 
00267   public:
00268     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
00269                           ValueToValueMapTy &valueMap,
00270                           bool moduleLevelChanges,
00271                           const char *nameSuffix, 
00272                           ClonedCodeInfo *codeInfo,
00273                           const DataLayout *DL,
00274                           CloningDirector *Director)
00275     : NewFunc(newFunc), OldFunc(oldFunc),
00276       VMap(valueMap), ModuleLevelChanges(moduleLevelChanges),
00277       NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL),
00278       Director(Director) {
00279       // These are optional components.  The Director may return null.
00280       if (Director) {
00281         TypeMapper = Director->getTypeRemapper();
00282         Materializer = Director->getValueMaterializer();
00283       } else {
00284         TypeMapper = nullptr;
00285         Materializer = nullptr;
00286       }
00287     }
00288 
00289     /// CloneBlock - The specified block is found to be reachable, clone it and
00290     /// anything that it can reach.
00291     void CloneBlock(const BasicBlock *BB, 
00292                     BasicBlock::const_iterator StartingInst,
00293                     std::vector<const BasicBlock*> &ToClone);
00294   };
00295 }
00296 
00297 /// CloneBlock - The specified block is found to be reachable, clone it and
00298 /// anything that it can reach.
00299 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
00300                                        BasicBlock::const_iterator StartingInst,
00301                                        std::vector<const BasicBlock*> &ToClone){
00302   WeakVH &BBEntry = VMap[BB];
00303 
00304   // Have we already cloned this block?
00305   if (BBEntry) return;
00306   
00307   // Nope, clone it now.
00308   BasicBlock *NewBB;
00309   BBEntry = NewBB = BasicBlock::Create(BB->getContext());
00310   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00311 
00312   // It is only legal to clone a function if a block address within that
00313   // function is never referenced outside of the function.  Given that, we
00314   // want to map block addresses from the old function to block addresses in
00315   // the clone. (This is different from the generic ValueMapper
00316   // implementation, which generates an invalid blockaddress when
00317   // cloning a function.)
00318   //
00319   // Note that we don't need to fix the mapping for unreachable blocks;
00320   // the default mapping there is safe.
00321   if (BB->hasAddressTaken()) {
00322     Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
00323                                             const_cast<BasicBlock*>(BB));
00324     VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
00325   }
00326 
00327   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00328 
00329   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
00330   // loop doesn't include the terminator.
00331   for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end();
00332        II != IE; ++II) {
00333     // If the "Director" remaps the instruction, don't clone it.
00334     if (Director) {
00335       CloningDirector::CloningAction Action 
00336                               = Director->handleInstruction(VMap, II, NewBB);
00337       // If the cloning director says stop, we want to stop everything, not
00338       // just break out of the loop (which would cause the terminator to be
00339       // cloned).  The cloning director is responsible for inserting a proper
00340       // terminator into the new basic block in this case.
00341       if (Action == CloningDirector::StopCloningBB)
00342         return;
00343       // If the cloning director says skip, continue to the next instruction.
00344       // In this case, the cloning director is responsible for mapping the
00345       // skipped instruction to some value that is defined in the new
00346       // basic block.
00347       if (Action == CloningDirector::SkipInstruction)
00348         continue;
00349     }
00350 
00351     Instruction *NewInst = II->clone();
00352 
00353     // Eagerly remap operands to the newly cloned instruction, except for PHI
00354     // nodes for which we defer processing until we update the CFG.
00355     if (!isa<PHINode>(NewInst)) {
00356       RemapInstruction(NewInst, VMap,
00357                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
00358                        TypeMapper, Materializer);
00359 
00360       // If we can simplify this instruction to some other value, simply add
00361       // a mapping to that value rather than inserting a new instruction into
00362       // the basic block.
00363       if (Value *V = SimplifyInstruction(NewInst, DL)) {
00364         // On the off-chance that this simplifies to an instruction in the old
00365         // function, map it back into the new function.
00366         if (Value *MappedV = VMap.lookup(V))
00367           V = MappedV;
00368 
00369         VMap[II] = V;
00370         delete NewInst;
00371         continue;
00372       }
00373     }
00374 
00375     if (II->hasName())
00376       NewInst->setName(II->getName()+NameSuffix);
00377     VMap[II] = NewInst;                // Add instruction map to value.
00378     NewBB->getInstList().push_back(NewInst);
00379     hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
00380     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00381       if (isa<ConstantInt>(AI->getArraySize()))
00382         hasStaticAllocas = true;
00383       else
00384         hasDynamicAllocas = true;
00385     }
00386   }
00387   
00388   // Finally, clone over the terminator.
00389   const TerminatorInst *OldTI = BB->getTerminator();
00390   bool TerminatorDone = false;
00391   if (Director) {
00392     CloningDirector::CloningAction Action 
00393                            = Director->handleInstruction(VMap, OldTI, NewBB);
00394     // If the cloning director says stop, we want to stop everything, not
00395     // just break out of the loop (which would cause the terminator to be
00396     // cloned).  The cloning director is responsible for inserting a proper
00397     // terminator into the new basic block in this case.
00398     if (Action == CloningDirector::StopCloningBB)
00399       return;
00400     assert(Action != CloningDirector::SkipInstruction && 
00401            "SkipInstruction is not valid for terminators.");
00402   }
00403   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
00404     if (BI->isConditional()) {
00405       // If the condition was a known constant in the callee...
00406       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
00407       // Or is a known constant in the caller...
00408       if (!Cond) {
00409         Value *V = VMap[BI->getCondition()];
00410         Cond = dyn_cast_or_null<ConstantInt>(V);
00411       }
00412 
00413       // Constant fold to uncond branch!
00414       if (Cond) {
00415         BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
00416         VMap[OldTI] = BranchInst::Create(Dest, NewBB);
00417         ToClone.push_back(Dest);
00418         TerminatorDone = true;
00419       }
00420     }
00421   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
00422     // If switching on a value known constant in the caller.
00423     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
00424     if (!Cond) { // Or known constant after constant prop in the callee...
00425       Value *V = VMap[SI->getCondition()];
00426       Cond = dyn_cast_or_null<ConstantInt>(V);
00427     }
00428     if (Cond) {     // Constant fold to uncond branch!
00429       SwitchInst::ConstCaseIt Case = SI->findCaseValue(Cond);
00430       BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor());
00431       VMap[OldTI] = BranchInst::Create(Dest, NewBB);
00432       ToClone.push_back(Dest);
00433       TerminatorDone = true;
00434     }
00435   }
00436   
00437   if (!TerminatorDone) {
00438     Instruction *NewInst = OldTI->clone();
00439     if (OldTI->hasName())
00440       NewInst->setName(OldTI->getName()+NameSuffix);
00441     NewBB->getInstList().push_back(NewInst);
00442     VMap[OldTI] = NewInst;             // Add instruction map to value.
00443     
00444     // Recursively clone any reachable successor blocks.
00445     const TerminatorInst *TI = BB->getTerminator();
00446     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00447       ToClone.push_back(TI->getSuccessor(i));
00448   }
00449   
00450   if (CodeInfo) {
00451     CodeInfo->ContainsCalls          |= hasCalls;
00452     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00453     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00454       BB != &BB->getParent()->front();
00455   }
00456 }
00457 
00458 /// CloneAndPruneIntoFromInst - This works like CloneAndPruneFunctionInto, except
00459 /// that it does not clone the entire function. Instead it starts at an
00460 /// instruction provided by the caller and copies (and prunes) only the code 
00461 /// reachable from that instruction.
00462 void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
00463                                      const Instruction *StartingInst,
00464                                      ValueToValueMapTy &VMap,
00465                                      bool ModuleLevelChanges,
00466                                      SmallVectorImpl<ReturnInst *> &Returns,
00467                                      const char *NameSuffix, 
00468                                      ClonedCodeInfo *CodeInfo,
00469                                      const DataLayout *DL,
00470                                      CloningDirector *Director) {
00471   assert(NameSuffix && "NameSuffix cannot be null!");
00472 
00473   ValueMapTypeRemapper *TypeMapper = nullptr;
00474   ValueMaterializer *Materializer = nullptr;
00475 
00476   if (Director) {
00477     TypeMapper = Director->getTypeRemapper();
00478     Materializer = Director->getValueMaterializer();
00479   }
00480 
00481 #ifndef NDEBUG
00482   // If the cloning starts at the begining of the function, verify that
00483   // the function arguments are mapped.
00484   if (!StartingInst)
00485     for (Function::const_arg_iterator II = OldFunc->arg_begin(),
00486          E = OldFunc->arg_end(); II != E; ++II)
00487       assert(VMap.count(II) && "No mapping from source argument specified!");
00488 #endif
00489 
00490   PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
00491                             NameSuffix, CodeInfo, DL, Director);
00492   const BasicBlock *StartingBB;
00493   if (StartingInst)
00494     StartingBB = StartingInst->getParent();
00495   else {
00496     StartingBB = &OldFunc->getEntryBlock();
00497     StartingInst = StartingBB->begin();
00498   }
00499 
00500   // Clone the entry block, and anything recursively reachable from it.
00501   std::vector<const BasicBlock*> CloneWorklist;
00502   PFC.CloneBlock(StartingBB, StartingInst, CloneWorklist);
00503   while (!CloneWorklist.empty()) {
00504     const BasicBlock *BB = CloneWorklist.back();
00505     CloneWorklist.pop_back();
00506     PFC.CloneBlock(BB, BB->begin(), CloneWorklist);
00507   }
00508   
00509   // Loop over all of the basic blocks in the old function.  If the block was
00510   // reachable, we have cloned it and the old block is now in the value map:
00511   // insert it into the new function in the right order.  If not, ignore it.
00512   //
00513   // Defer PHI resolution until rest of function is resolved.
00514   SmallVector<const PHINode*, 16> PHIToResolve;
00515   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00516        BI != BE; ++BI) {
00517     Value *V = VMap[BI];
00518     BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
00519     if (!NewBB) continue;  // Dead block.
00520 
00521     // Add the new block to the new function.
00522     NewFunc->getBasicBlockList().push_back(NewBB);
00523 
00524     // Handle PHI nodes specially, as we have to remove references to dead
00525     // blocks.
00526     for (BasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I)
00527       if (const PHINode *PN = dyn_cast<PHINode>(I))
00528         PHIToResolve.push_back(PN);
00529       else
00530         break;
00531 
00532     // Finally, remap the terminator instructions, as those can't be remapped
00533     // until all BBs are mapped.
00534     RemapInstruction(NewBB->getTerminator(), VMap,
00535                      ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
00536                      TypeMapper, Materializer);
00537   }
00538   
00539   // Defer PHI resolution until rest of function is resolved, PHI resolution
00540   // requires the CFG to be up-to-date.
00541   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
00542     const PHINode *OPN = PHIToResolve[phino];
00543     unsigned NumPreds = OPN->getNumIncomingValues();
00544     const BasicBlock *OldBB = OPN->getParent();
00545     BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);
00546 
00547     // Map operands for blocks that are live and remove operands for blocks
00548     // that are dead.
00549     for (; phino != PHIToResolve.size() &&
00550          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
00551       OPN = PHIToResolve[phino];
00552       PHINode *PN = cast<PHINode>(VMap[OPN]);
00553       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
00554         Value *V = VMap[PN->getIncomingBlock(pred)];
00555         if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
00556           Value *InVal = MapValue(PN->getIncomingValue(pred),
00557                                   VMap, 
00558                         ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
00559           assert(InVal && "Unknown input value?");
00560           PN->setIncomingValue(pred, InVal);
00561           PN->setIncomingBlock(pred, MappedBlock);
00562         } else {
00563           PN->removeIncomingValue(pred, false);
00564           --pred, --e;  // Revisit the next entry.
00565         }
00566       } 
00567     }
00568     
00569     // The loop above has removed PHI entries for those blocks that are dead
00570     // and has updated others.  However, if a block is live (i.e. copied over)
00571     // but its terminator has been changed to not go to this block, then our
00572     // phi nodes will have invalid entries.  Update the PHI nodes in this
00573     // case.
00574     PHINode *PN = cast<PHINode>(NewBB->begin());
00575     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
00576     if (NumPreds != PN->getNumIncomingValues()) {
00577       assert(NumPreds < PN->getNumIncomingValues());
00578       // Count how many times each predecessor comes to this block.
00579       std::map<BasicBlock*, unsigned> PredCount;
00580       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
00581            PI != E; ++PI)
00582         --PredCount[*PI];
00583       
00584       // Figure out how many entries to remove from each PHI.
00585       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00586         ++PredCount[PN->getIncomingBlock(i)];
00587       
00588       // At this point, the excess predecessor entries are positive in the
00589       // map.  Loop over all of the PHIs and remove excess predecessor
00590       // entries.
00591       BasicBlock::iterator I = NewBB->begin();
00592       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
00593         for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
00594              E = PredCount.end(); PCI != E; ++PCI) {
00595           BasicBlock *Pred     = PCI->first;
00596           for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
00597             PN->removeIncomingValue(Pred, false);
00598         }
00599       }
00600     }
00601     
00602     // If the loops above have made these phi nodes have 0 or 1 operand,
00603     // replace them with undef or the input value.  We must do this for
00604     // correctness, because 0-operand phis are not valid.
00605     PN = cast<PHINode>(NewBB->begin());
00606     if (PN->getNumIncomingValues() == 0) {
00607       BasicBlock::iterator I = NewBB->begin();
00608       BasicBlock::const_iterator OldI = OldBB->begin();
00609       while ((PN = dyn_cast<PHINode>(I++))) {
00610         Value *NV = UndefValue::get(PN->getType());
00611         PN->replaceAllUsesWith(NV);
00612         assert(VMap[OldI] == PN && "VMap mismatch");
00613         VMap[OldI] = NV;
00614         PN->eraseFromParent();
00615         ++OldI;
00616       }
00617     }
00618   }
00619 
00620   // Make a second pass over the PHINodes now that all of them have been
00621   // remapped into the new function, simplifying the PHINode and performing any
00622   // recursive simplifications exposed. This will transparently update the
00623   // WeakVH in the VMap. Notably, we rely on that so that if we coalesce
00624   // two PHINodes, the iteration over the old PHIs remains valid, and the
00625   // mapping will just map us to the new node (which may not even be a PHI
00626   // node).
00627   for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
00628     if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]]))
00629       recursivelySimplifyInstruction(PN, DL);
00630 
00631   // Now that the inlined function body has been fully constructed, go through
00632   // and zap unconditional fall-through branches.  This happen all the time when
00633   // specializing code: code specialization turns conditional branches into
00634   // uncond branches, and this code folds them.
00635   Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB]);
00636   Function::iterator I = Begin;
00637   while (I != NewFunc->end()) {
00638     // Check if this block has become dead during inlining or other
00639     // simplifications. Note that the first block will appear dead, as it has
00640     // not yet been wired up properly.
00641     if (I != Begin && (pred_begin(I) == pred_end(I) ||
00642                        I->getSinglePredecessor() == I)) {
00643       BasicBlock *DeadBB = I++;
00644       DeleteDeadBlock(DeadBB);
00645       continue;
00646     }
00647 
00648     // We need to simplify conditional branches and switches with a constant
00649     // operand. We try to prune these out when cloning, but if the
00650     // simplification required looking through PHI nodes, those are only
00651     // available after forming the full basic block. That may leave some here,
00652     // and we still want to prune the dead code as early as possible.
00653     ConstantFoldTerminator(I);
00654 
00655     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
00656     if (!BI || BI->isConditional()) { ++I; continue; }
00657     
00658     BasicBlock *Dest = BI->getSuccessor(0);
00659     if (!Dest->getSinglePredecessor()) {
00660       ++I; continue;
00661     }
00662 
00663     // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
00664     // above should have zapped all of them..
00665     assert(!isa<PHINode>(Dest->begin()));
00666 
00667     // We know all single-entry PHI nodes in the inlined function have been
00668     // removed, so we just need to splice the blocks.
00669     BI->eraseFromParent();
00670     
00671     // Make all PHI nodes that referred to Dest now refer to I as their source.
00672     Dest->replaceAllUsesWith(I);
00673 
00674     // Move all the instructions in the succ to the pred.
00675     I->getInstList().splice(I->end(), Dest->getInstList());
00676     
00677     // Remove the dest block.
00678     Dest->eraseFromParent();
00679     
00680     // Do not increment I, iteratively merge all things this block branches to.
00681   }
00682 
00683   // Make a final pass over the basic blocks from theh old function to gather
00684   // any return instructions which survived folding. We have to do this here
00685   // because we can iteratively remove and merge returns above.
00686   for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB]),
00687                           E = NewFunc->end();
00688        I != E; ++I)
00689     if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
00690       Returns.push_back(RI);
00691 }
00692 
00693 
00694 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
00695 /// except that it does some simple constant prop and DCE on the fly.  The
00696 /// effect of this is to copy significantly less code in cases where (for
00697 /// example) a function call with constant arguments is inlined, and those
00698 /// constant arguments cause a significant amount of code in the callee to be
00699 /// dead.  Since this doesn't produce an exact copy of the input, it can't be
00700 /// used for things like CloneFunction or CloneModule.
00701 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
00702                                      ValueToValueMapTy &VMap,
00703                                      bool ModuleLevelChanges,
00704                                      SmallVectorImpl<ReturnInst*> &Returns,
00705                                      const char *NameSuffix, 
00706                                      ClonedCodeInfo *CodeInfo,
00707                                      const DataLayout *DL,
00708                                      Instruction *TheCall) {
00709   CloneAndPruneIntoFromInst(NewFunc, OldFunc, OldFunc->front().begin(),
00710                             VMap, ModuleLevelChanges, Returns, NameSuffix,
00711                             CodeInfo, DL, nullptr);
00712 }