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