LLVM API Documentation

CloneFunction.cpp

Go to the documentation of this file.
00001 //===- CloneFunction.cpp - Clone a function into another function ---------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the CloneFunctionInto interface, which is used as the
00011 // low-level function cloner.  This is used by the CloneFunction and function
00012 // inliner to do the dirty work of copying the body of a function around.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/Utils/Cloning.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/DerivedTypes.h"
00019 #include "llvm/Instructions.h"
00020 #include "llvm/Function.h"
00021 #include "llvm/Support/CFG.h"
00022 #include "ValueMapper.h"
00023 #include "llvm/Transforms/Utils/Local.h"
00024 using namespace llvm;
00025 
00026 // CloneBasicBlock - See comments in Cloning.h
00027 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
00028                                   std::map<const Value*, Value*> &ValueMap,
00029                                   const char *NameSuffix, Function *F,
00030                                   ClonedCodeInfo *CodeInfo) {
00031   BasicBlock *NewBB = new BasicBlock("", F);
00032   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00033 
00034   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00035   
00036   // Loop over all instructions, and copy them over.
00037   for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
00038        II != IE; ++II) {
00039     Instruction *NewInst = II->clone();
00040     if (II->hasName())
00041       NewInst->setName(II->getName()+NameSuffix);
00042     NewBB->getInstList().push_back(NewInst);
00043     ValueMap[II] = NewInst;                // Add instruction map to value.
00044     
00045     hasCalls |= isa<CallInst>(II);
00046     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00047       if (isa<ConstantInt>(AI->getArraySize()))
00048         hasStaticAllocas = true;
00049       else
00050         hasDynamicAllocas = true;
00051     }
00052   }
00053   
00054   if (CodeInfo) {
00055     CodeInfo->ContainsCalls          |= hasCalls;
00056     CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(BB->getTerminator());
00057     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00058     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00059                                         BB != &BB->getParent()->front();
00060   }
00061   return NewBB;
00062 }
00063 
00064 // Clone OldFunc into NewFunc, transforming the old arguments into references to
00065 // ArgMap values.
00066 //
00067 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
00068                              std::map<const Value*, Value*> &ValueMap,
00069                              std::vector<ReturnInst*> &Returns,
00070                              const char *NameSuffix, ClonedCodeInfo *CodeInfo) {
00071   assert(NameSuffix && "NameSuffix cannot be null!");
00072 
00073 #ifndef NDEBUG
00074   for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
00075        E = OldFunc->arg_end(); I != E; ++I)
00076     assert(ValueMap.count(I) && "No mapping from source argument specified!");
00077 #endif
00078 
00079   // Loop over all of the basic blocks in the function, cloning them as
00080   // appropriate.  Note that we save BE this way in order to handle cloning of
00081   // recursive functions into themselves.
00082   //
00083   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00084        BI != BE; ++BI) {
00085     const BasicBlock &BB = *BI;
00086 
00087     // Create a new basic block and copy instructions into it!
00088     BasicBlock *CBB = CloneBasicBlock(&BB, ValueMap, NameSuffix, NewFunc,
00089                                       CodeInfo);
00090     ValueMap[&BB] = CBB;                       // Add basic block mapping.
00091 
00092     if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
00093       Returns.push_back(RI);
00094   }
00095 
00096   // Loop over all of the instructions in the function, fixing up operand
00097   // references as we go.  This uses ValueMap to do all the hard work.
00098   //
00099   for (Function::iterator BB = cast<BasicBlock>(ValueMap[OldFunc->begin()]),
00100          BE = NewFunc->end(); BB != BE; ++BB)
00101     // Loop over all instructions, fixing each one as we find it...
00102     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
00103       RemapInstruction(II, ValueMap);
00104 }
00105 
00106 /// CloneFunction - Return a copy of the specified function, but without
00107 /// embedding the function into another module.  Also, any references specified
00108 /// in the ValueMap are changed to refer to their mapped value instead of the
00109 /// original one.  If any of the arguments to the function are in the ValueMap,
00110 /// the arguments are deleted from the resultant function.  The ValueMap is
00111 /// updated to include mappings from all of the instructions and basicblocks in
00112 /// the function from their old to new values.
00113 ///
00114 Function *llvm::CloneFunction(const Function *F,
00115                               std::map<const Value*, Value*> &ValueMap,
00116                               ClonedCodeInfo *CodeInfo) {
00117   std::vector<const Type*> ArgTypes;
00118 
00119   // The user might be deleting arguments to the function by specifying them in
00120   // the ValueMap.  If so, we need to not add the arguments to the arg ty vector
00121   //
00122   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00123        I != E; ++I)
00124     if (ValueMap.count(I) == 0)  // Haven't mapped the argument to anything yet?
00125       ArgTypes.push_back(I->getType());
00126 
00127   // Create a new function type...
00128   FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
00129                                     ArgTypes, F->getFunctionType()->isVarArg());
00130 
00131   // Create the new function...
00132   Function *NewF = new Function(FTy, F->getLinkage(), F->getName());
00133 
00134   // Loop over the arguments, copying the names of the mapped arguments over...
00135   Function::arg_iterator DestI = NewF->arg_begin();
00136   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00137        I != E; ++I)
00138     if (ValueMap.count(I) == 0) {   // Is this argument preserved?
00139       DestI->setName(I->getName()); // Copy the name over...
00140       ValueMap[I] = DestI++;        // Add mapping to ValueMap
00141     }
00142 
00143   std::vector<ReturnInst*> Returns;  // Ignore returns cloned...
00144   CloneFunctionInto(NewF, F, ValueMap, Returns, "", CodeInfo);
00145   return NewF;
00146 }
00147 
00148 
00149 
00150 namespace {
00151   /// PruningFunctionCloner - This class is a private class used to implement
00152   /// the CloneAndPruneFunctionInto method.
00153   struct PruningFunctionCloner {
00154     Function *NewFunc;
00155     const Function *OldFunc;
00156     std::map<const Value*, Value*> &ValueMap;
00157     std::vector<ReturnInst*> &Returns;
00158     const char *NameSuffix;
00159     ClonedCodeInfo *CodeInfo;
00160 
00161   public:
00162     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
00163                           std::map<const Value*, Value*> &valueMap,
00164                           std::vector<ReturnInst*> &returns,
00165                           const char *nameSuffix, 
00166                           ClonedCodeInfo *codeInfo)
00167     : NewFunc(newFunc), OldFunc(oldFunc), ValueMap(valueMap), Returns(returns),
00168       NameSuffix(nameSuffix), CodeInfo(codeInfo) {
00169     }
00170 
00171     /// CloneBlock - The specified block is found to be reachable, clone it and
00172     /// anything that it can reach.
00173     void CloneBlock(const BasicBlock *BB);
00174     
00175   public:
00176     /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
00177     /// mapping its operands through ValueMap if they are available.
00178     Constant *ConstantFoldMappedInstruction(const Instruction *I);
00179   };
00180 }
00181 
00182 /// CloneBlock - The specified block is found to be reachable, clone it and
00183 /// anything that it can reach.
00184 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB) {
00185   Value *&BBEntry = ValueMap[BB];
00186 
00187   // Have we already cloned this block?
00188   if (BBEntry) return;
00189   
00190   // Nope, clone it now.
00191   BasicBlock *NewBB;
00192   BBEntry = NewBB = new BasicBlock();
00193   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
00194 
00195   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
00196   
00197   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
00198   // loop doesn't include the terminator.
00199   for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
00200        II != IE; ++II) {
00201     // If this instruction constant folds, don't bother cloning the instruction,
00202     // instead, just add the constant to the value map.
00203     if (Constant *C = ConstantFoldMappedInstruction(II)) {
00204       ValueMap[II] = C;
00205       continue;
00206     }
00207     
00208     Instruction *NewInst = II->clone();
00209     if (II->hasName())
00210       NewInst->setName(II->getName()+NameSuffix);
00211     NewBB->getInstList().push_back(NewInst);
00212     ValueMap[II] = NewInst;                // Add instruction map to value.
00213     
00214     hasCalls |= isa<CallInst>(II);
00215     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
00216       if (isa<ConstantInt>(AI->getArraySize()))
00217         hasStaticAllocas = true;
00218       else
00219         hasDynamicAllocas = true;
00220     }
00221   }
00222   
00223   // Finally, clone over the terminator.
00224   const TerminatorInst *OldTI = BB->getTerminator();
00225   bool TerminatorDone = false;
00226   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
00227     if (BI->isConditional()) {
00228       // If the condition was a known constant in the callee...
00229       ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition());
00230       if (Cond == 0)  // Or is a known constant in the caller...
00231         Cond = dyn_cast_or_null<ConstantBool>(ValueMap[BI->getCondition()]);
00232       if (Cond) {     // Constant fold to uncond branch!
00233         BasicBlock *Dest = BI->getSuccessor(!Cond->getValue());
00234         ValueMap[OldTI] = new BranchInst(Dest, NewBB);
00235         CloneBlock(Dest);
00236         TerminatorDone = true;
00237       }
00238     }
00239   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
00240     // If switching on a value known constant in the caller.
00241     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
00242     if (Cond == 0)  // Or known constant after constant prop in the callee...
00243       Cond = dyn_cast_or_null<ConstantInt>(ValueMap[SI->getCondition()]);
00244     if (Cond) {     // Constant fold to uncond branch!
00245       BasicBlock *Dest = SI->getSuccessor(SI->findCaseValue(Cond));
00246       ValueMap[OldTI] = new BranchInst(Dest, NewBB);
00247       CloneBlock(Dest);
00248       TerminatorDone = true;
00249     }
00250   }
00251   
00252   if (!TerminatorDone) {
00253     Instruction *NewInst = OldTI->clone();
00254     if (OldTI->hasName())
00255       NewInst->setName(OldTI->getName()+NameSuffix);
00256     NewBB->getInstList().push_back(NewInst);
00257     ValueMap[OldTI] = NewInst;             // Add instruction map to value.
00258     
00259     // Recursively clone any reachable successor blocks.
00260     const TerminatorInst *TI = BB->getTerminator();
00261     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00262       CloneBlock(TI->getSuccessor(i));
00263   }
00264   
00265   if (CodeInfo) {
00266     CodeInfo->ContainsCalls          |= hasCalls;
00267     CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(OldTI);
00268     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
00269     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
00270       BB != &BB->getParent()->front();
00271   }
00272   
00273   if (ReturnInst *RI = dyn_cast<ReturnInst>(NewBB->getTerminator()))
00274     Returns.push_back(RI);
00275 }
00276 
00277 /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
00278 /// mapping its operands through ValueMap if they are available.
00279 Constant *PruningFunctionCloner::
00280 ConstantFoldMappedInstruction(const Instruction *I) {
00281   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) {
00282     if (Constant *Op0 = dyn_cast_or_null<Constant>(MapValue(I->getOperand(0),
00283                                                             ValueMap)))
00284       if (Constant *Op1 = dyn_cast_or_null<Constant>(MapValue(I->getOperand(1),
00285                                                               ValueMap)))
00286         return ConstantExpr::get(I->getOpcode(), Op0, Op1);
00287     return 0;
00288   }
00289 
00290   std::vector<Constant*> Ops;
00291   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00292     if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i),
00293                                                            ValueMap)))
00294       Ops.push_back(Op);
00295     else
00296       return 0;  // All operands not constant!
00297 
00298   return ConstantFoldInstOperands(I->getOpcode(), I->getType(), Ops);
00299 }
00300 
00301 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
00302 /// except that it does some simple constant prop and DCE on the fly.  The
00303 /// effect of this is to copy significantly less code in cases where (for
00304 /// example) a function call with constant arguments is inlined, and those
00305 /// constant arguments cause a significant amount of code in the callee to be
00306 /// dead.  Since this doesn't produce an exactly copy of the input, it can't be
00307 /// used for things like CloneFunction or CloneModule.
00308 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
00309                                      std::map<const Value*, Value*> &ValueMap,
00310                                      std::vector<ReturnInst*> &Returns,
00311                                      const char *NameSuffix, 
00312                                      ClonedCodeInfo *CodeInfo) {
00313   assert(NameSuffix && "NameSuffix cannot be null!");
00314   
00315 #ifndef NDEBUG
00316   for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
00317        E = OldFunc->arg_end(); I != E; ++I)
00318     assert(ValueMap.count(I) && "No mapping from source argument specified!");
00319 #endif
00320   
00321   PruningFunctionCloner PFC(NewFunc, OldFunc, ValueMap, Returns, 
00322                             NameSuffix, CodeInfo);
00323 
00324   // Clone the entry block, and anything recursively reachable from it.
00325   PFC.CloneBlock(&OldFunc->getEntryBlock());
00326   
00327   // Loop over all of the basic blocks in the old function.  If the block was
00328   // reachable, we have cloned it and the old block is now in the value map:
00329   // insert it into the new function in the right order.  If not, ignore it.
00330   //
00331   // Defer PHI resolution until rest of function is resolved.
00332   std::vector<const PHINode*> PHIToResolve;
00333   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
00334        BI != BE; ++BI) {
00335     BasicBlock *NewBB = cast_or_null<BasicBlock>(ValueMap[BI]);
00336     if (NewBB == 0) continue;  // Dead block.
00337 
00338     // Add the new block to the new function.
00339     NewFunc->getBasicBlockList().push_back(NewBB);
00340     
00341     // Loop over all of the instructions in the block, fixing up operand
00342     // references as we go.  This uses ValueMap to do all the hard work.
00343     //
00344     BasicBlock::iterator I = NewBB->begin();
00345     
00346     // Handle PHI nodes specially, as we have to remove references to dead
00347     // blocks.
00348     if (PHINode *PN = dyn_cast<PHINode>(I)) {
00349       // Skip over all PHI nodes, remembering them for later.
00350       BasicBlock::const_iterator OldI = BI->begin();
00351       for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI)
00352         PHIToResolve.push_back(cast<PHINode>(OldI));
00353     }
00354     
00355     // Otherwise, remap the rest of the instructions normally.
00356     for (; I != NewBB->end(); ++I)
00357       RemapInstruction(I, ValueMap);
00358   }
00359   
00360   // Defer PHI resolution until rest of function is resolved, PHI resolution
00361   // requires the CFG to be up-to-date.
00362   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
00363     const PHINode *OPN = PHIToResolve[phino];
00364     
00365     unsigned NumPreds = OPN->getNumIncomingValues();
00366     
00367     unsigned BBPHIStart = phino;
00368     const BasicBlock *OldBB = OPN->getParent();
00369     BasicBlock *NewBB = cast<BasicBlock>(ValueMap[OldBB]);
00370 
00371     // Map operands for blocks that are live and remove operands for blocks
00372     // that are dead.
00373     for (; phino != PHIToResolve.size() &&
00374          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
00375       OPN = PHIToResolve[phino];
00376       PHINode *PN = cast<PHINode>(ValueMap[OPN]);
00377       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
00378         if (BasicBlock *MappedBlock = 
00379             cast_or_null<BasicBlock>(ValueMap[PN->getIncomingBlock(pred)])) {
00380           Value *InVal = MapValue(PN->getIncomingValue(pred), ValueMap);
00381           assert(InVal && "Unknown input value?");
00382           PN->setIncomingValue(pred, InVal);
00383           PN->setIncomingBlock(pred, MappedBlock);
00384         } else {
00385           PN->removeIncomingValue(pred, false);
00386           --pred, --e;  // Revisit the next entry.
00387         }
00388       } 
00389     }
00390     
00391     // The loop above has removed PHI entries for those blocks that are dead
00392     // and has updated others.  However, if a block is live (i.e. copied over)
00393     // but its terminator has been changed to not go to this block, then our
00394     // phi nodes will have invalid entries.  Update the PHI nodes in this
00395     // case.
00396     PHINode *PN = cast<PHINode>(NewBB->begin());
00397     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
00398     if (NumPreds != PN->getNumIncomingValues()) {
00399       assert(NumPreds < PN->getNumIncomingValues());
00400       // Count how many times each predecessor comes to this block.
00401       std::map<BasicBlock*, unsigned> PredCount;
00402       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
00403            PI != E; ++PI)
00404         --PredCount[*PI];
00405       
00406       // Figure out how many entries to remove from each PHI.
00407       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00408         ++PredCount[PN->getIncomingBlock(i)];
00409       
00410       // At this point, the excess predecessor entries are positive in the
00411       // map.  Loop over all of the PHIs and remove excess predecessor
00412       // entries.
00413       BasicBlock::iterator I = NewBB->begin();
00414       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
00415         for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
00416              E = PredCount.end(); PCI != E; ++PCI) {
00417           BasicBlock *Pred     = PCI->first;
00418           for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
00419             PN->removeIncomingValue(Pred, false);
00420         }
00421       }
00422     }
00423     
00424     // If the loops above have made these phi nodes have 0 or 1 operand,
00425     // replace them with undef or the input value.  We must do this for
00426     // correctness, because 0-operand phis are not valid.
00427     PN = cast<PHINode>(NewBB->begin());
00428     if (PN->getNumIncomingValues() == 0) {
00429       BasicBlock::iterator I = NewBB->begin();
00430       BasicBlock::const_iterator OldI = OldBB->begin();
00431       while ((PN = dyn_cast<PHINode>(I++))) {
00432         Value *NV = UndefValue::get(PN->getType());
00433         PN->replaceAllUsesWith(NV);
00434         assert(ValueMap[OldI] == PN && "ValueMap mismatch");
00435         ValueMap[OldI] = NV;
00436         PN->eraseFromParent();
00437         ++OldI;
00438       }
00439     } else if (PN->getNumIncomingValues() == 1) {
00440       BasicBlock::iterator I = NewBB->begin();
00441       BasicBlock::const_iterator OldI = OldBB->begin();
00442       while ((PN = dyn_cast<PHINode>(I++))) {
00443         Value *NV = PN->getIncomingValue(0);
00444         PN->replaceAllUsesWith(NV);
00445         assert(ValueMap[OldI] == PN && "ValueMap mismatch");
00446         ValueMap[OldI] = NV;
00447         PN->eraseFromParent();
00448         ++OldI;
00449       }
00450     }
00451   }
00452 }
00453 
00454