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