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