lib/Transforms/Utils/CloneFunction.cpp

   1 //===- CloneFunction.cpp - Clone a function into another function ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the CloneFunctionInto interface, which is used as the
  11 // low-level function cloner.  This is used by the CloneFunction and function
  12 // inliner to do the dirty work of copying the body of a function around.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Utils/Cloning.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/Support/CFG.h"
  22 #include "ValueMapper.h"
  23 #include "llvm/Transforms/Utils/Local.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 using namespace llvm;
  26
  27 // CloneBasicBlock - See comments in Cloning.h
  28 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
  29                                   std::map<const Value*, Value*> &ValueMap,
  30                                   const char *NameSuffix, Function *F,
  31                                   ClonedCodeInfo *CodeInfo) {
  32   BasicBlock *NewBB = new BasicBlock("", F);
  33   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
  34
  35   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
  36
  37   // Loop over all instructions, and copy them over.
  38   for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
  39        II != IE; ++II) {
  40     Instruction *NewInst = II->clone();
  41     if (II->hasName())
  42       NewInst->setName(II->getName()+NameSuffix);
  43     NewBB->getInstList().push_back(NewInst);
  44     ValueMap[II] = NewInst;                // Add instruction map to value.
  45
  46     hasCalls |= isa<CallInst>(II);
  47     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
  48       if (isa<ConstantInt>(AI->getArraySize()))
  49         hasStaticAllocas = true;
  50       else
  51         hasDynamicAllocas = true;
  52     }
  53   }
  54
  55   if (CodeInfo) {
  56     CodeInfo->ContainsCalls          |= hasCalls;
  57     CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(BB->getTerminator());
  58     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
  59     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
  60                                         BB != &BB->getParent()->front();
  61   }
  62   return NewBB;
  63 }
  64
  65 // Clone OldFunc into NewFunc, transforming the old arguments into references to
  66 // ArgMap values.
  67 //
  68 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
  69                              std::map<const Value*, Value*> &ValueMap,
  70                              std::vector<ReturnInst*> &Returns,
  71                              const char *NameSuffix, ClonedCodeInfo *CodeInfo) {
  72   assert(NameSuffix && "NameSuffix cannot be null!");
  73
  74 #ifndef NDEBUG
  75   for (Function::const_arg_iterator I = OldFunc->arg_begin(),
  76        E = OldFunc->arg_end(); I != E; ++I)
  77     assert(ValueMap.count(I) && "No mapping from source argument specified!");
  78 #endif
  79
  80   // Loop over all of the basic blocks in the function, cloning them as
  81   // appropriate.  Note that we save BE this way in order to handle cloning of
  82   // recursive functions into themselves.
  83   //
  84   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
  85        BI != BE; ++BI) {
  86     const BasicBlock &BB = *BI;
  87
  88     // Create a new basic block and copy instructions into it!
  89     BasicBlock *CBB = CloneBasicBlock(&BB, ValueMap, NameSuffix, NewFunc,
  90                                       CodeInfo);
  91     ValueMap[&BB] = CBB;                       // Add basic block mapping.
  92
  93     if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
  94       Returns.push_back(RI);
  95   }
  96
  97   // Loop over all of the instructions in the function, fixing up operand
  98   // references as we go.  This uses ValueMap to do all the hard work.
  99   //
 100   for (Function::iterator BB = cast<BasicBlock>(ValueMap[OldFunc->begin()]),
 101          BE = NewFunc->end(); BB != BE; ++BB)
 102     // Loop over all instructions, fixing each one as we find it...
 103     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
 104       RemapInstruction(II, ValueMap);
 105 }
 106
 107 /// CloneFunction - Return a copy of the specified function, but without
 108 /// embedding the function into another module.  Also, any references specified
 109 /// in the ValueMap are changed to refer to their mapped value instead of the
 110 /// original one.  If any of the arguments to the function are in the ValueMap,
 111 /// the arguments are deleted from the resultant function.  The ValueMap is
 112 /// updated to include mappings from all of the instructions and basicblocks in
 113 /// the function from their old to new values.
 114 ///
 115 Function *llvm::CloneFunction(const Function *F,
 116                               std::map<const Value*, Value*> &ValueMap,
 117                               ClonedCodeInfo *CodeInfo) {
 118   std::vector<const Type*> ArgTypes;
 119
 120   // The user might be deleting arguments to the function by specifying them in
 121   // the ValueMap.  If so, we need to not add the arguments to the arg ty vector
 122   //
 123   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
 124        I != E; ++I)
 125     if (ValueMap.count(I) == 0)  // Haven't mapped the argument to anything yet?
 126       ArgTypes.push_back(I->getType());
 127
 128   // Create a new function type...
 129   FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
 130                                     ArgTypes, F->getFunctionType()->isVarArg());
 131
 132   // Create the new function...
 133   Function *NewF = new Function(FTy, F->getLinkage(), F->getName());
 134
 135   // Loop over the arguments, copying the names of the mapped arguments over...
 136   Function::arg_iterator DestI = NewF->arg_begin();
 137   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
 138        I != E; ++I)
 139     if (ValueMap.count(I) == 0) {   // Is this argument preserved?
 140       DestI->setName(I->getName()); // Copy the name over...
 141       ValueMap[I] = DestI++;        // Add mapping to ValueMap
 142     }
 143
 144   std::vector<ReturnInst*> Returns;  // Ignore returns cloned...
 145   CloneFunctionInto(NewF, F, ValueMap, Returns, "", CodeInfo);
 146   return NewF;
 147 }
 148
 149
 150
 151 namespace {
 152   /// PruningFunctionCloner - This class is a private class used to implement
 153   /// the CloneAndPruneFunctionInto method.
 154   struct PruningFunctionCloner {
 155     Function *NewFunc;
 156     const Function *OldFunc;
 157     std::map<const Value*, Value*> &ValueMap;
 158     std::vector<ReturnInst*> &Returns;
 159     const char *NameSuffix;
 160     ClonedCodeInfo *CodeInfo;
 161
 162   public:
 163     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
 164                           std::map<const Value*, Value*> &valueMap,
 165                           std::vector<ReturnInst*> &returns,
 166                           const char *nameSuffix,
 167                           ClonedCodeInfo *codeInfo)
 168     : NewFunc(newFunc), OldFunc(oldFunc), ValueMap(valueMap), Returns(returns),
 169       NameSuffix(nameSuffix), CodeInfo(codeInfo) {
 170     }
 171
 172     /// CloneBlock - The specified block is found to be reachable, clone it and
 173     /// anything that it can reach.
 174     void CloneBlock(const BasicBlock *BB);
 175
 176   public:
 177     /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
 178     /// mapping its operands through ValueMap if they are available.
 179     Constant *ConstantFoldMappedInstruction(const Instruction *I);
 180   };
 181 }
 182
 183 /// CloneBlock - The specified block is found to be reachable, clone it and
 184 /// anything that it can reach.
 185 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB) {
 186   Value *&BBEntry = ValueMap[BB];
 187
 188   // Have we already cloned this block?
 189   if (BBEntry) return;
 190
 191   // Nope, clone it now.
 192   BasicBlock *NewBB;
 193   BBEntry = NewBB = new BasicBlock();
 194   if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
 195
 196   bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
 197
 198   // Loop over all instructions, and copy them over, DCE'ing as we go.  This
 199   // loop doesn't include the terminator.
 200   for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
 201        II != IE; ++II) {
 202     // If this instruction constant folds, don't bother cloning the instruction,
 203     // instead, just add the constant to the value map.
 204     if (Constant *C = ConstantFoldMappedInstruction(II)) {
 205       ValueMap[II] = C;
 206       continue;
 207     }
 208
 209     Instruction *NewInst = II->clone();
 210     if (II->hasName())
 211       NewInst->setName(II->getName()+NameSuffix);
 212     NewBB->getInstList().push_back(NewInst);
 213     ValueMap[II] = NewInst;                // Add instruction map to value.
 214
 215     hasCalls |= isa<CallInst>(II);
 216     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
 217       if (isa<ConstantInt>(AI->getArraySize()))
 218         hasStaticAllocas = true;
 219       else
 220         hasDynamicAllocas = true;
 221     }
 222   }
 223
 224   // Finally, clone over the terminator.
 225   const TerminatorInst *OldTI = BB->getTerminator();
 226   bool TerminatorDone = false;
 227   if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
 228     if (BI->isConditional()) {
 229       // If the condition was a known constant in the callee...
 230       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
 231       // Or is a known constant in the caller...
 232       if (Cond == 0)
 233         Cond = dyn_cast_or_null<ConstantInt>(ValueMap[BI->getCondition()]);
 234
 235       // Constant fold to uncond branch!
 236       if (Cond) {
 237         BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
 238         ValueMap[OldTI] = new BranchInst(Dest, NewBB);
 239         CloneBlock(Dest);
 240         TerminatorDone = true;
 241       }
 242     }
 243   } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
 244     // If switching on a value known constant in the caller.
 245     ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
 246     if (Cond == 0)  // Or known constant after constant prop in the callee...
 247       Cond = dyn_cast_or_null<ConstantInt>(ValueMap[SI->getCondition()]);
 248     if (Cond) {     // Constant fold to uncond branch!
 249       BasicBlock *Dest = SI->getSuccessor(SI->findCaseValue(Cond));
 250       ValueMap[OldTI] = new BranchInst(Dest, NewBB);
 251       CloneBlock(Dest);
 252       TerminatorDone = true;
 253     }
 254   }
 255
 256   if (!TerminatorDone) {
 257     Instruction *NewInst = OldTI->clone();
 258     if (OldTI->hasName())
 259       NewInst->setName(OldTI->getName()+NameSuffix);
 260     NewBB->getInstList().push_back(NewInst);
 261     ValueMap[OldTI] = NewInst;             // Add instruction map to value.
 262
 263     // Recursively clone any reachable successor blocks.
 264     const TerminatorInst *TI = BB->getTerminator();
 265     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 266       CloneBlock(TI->getSuccessor(i));
 267   }
 268
 269   if (CodeInfo) {
 270     CodeInfo->ContainsCalls          |= hasCalls;
 271     CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(OldTI);
 272     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
 273     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
 274       BB != &BB->getParent()->front();
 275   }
 276
 277   if (ReturnInst *RI = dyn_cast<ReturnInst>(NewBB->getTerminator()))
 278     Returns.push_back(RI);
 279 }
 280
 281 /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
 282 /// mapping its operands through ValueMap if they are available.
 283 Constant *PruningFunctionCloner::
 284 ConstantFoldMappedInstruction(const Instruction *I) {
 285   SmallVector<Constant*, 8> Ops;
 286   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 287     if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i),
 288                                                            ValueMap)))
 289       Ops.push_back(Op);
 290     else
 291       return 0;  // All operands not constant!
 292
 293   return ConstantFoldInstOperands(I, &Ops[0], Ops.size());
 294 }
 295
 296 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
 297 /// except that it does some simple constant prop and DCE on the fly.  The
 298 /// effect of this is to copy significantly less code in cases where (for
 299 /// example) a function call with constant arguments is inlined, and those
 300 /// constant arguments cause a significant amount of code in the callee to be
 301 /// dead.  Since this doesn't produce an exactly copy of the input, it can't be
 302 /// used for things like CloneFunction or CloneModule.
 303 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
 304                                      std::map<const Value*, Value*> &ValueMap,
 305                                      std::vector<ReturnInst*> &Returns,
 306                                      const char *NameSuffix,
 307                                      ClonedCodeInfo *CodeInfo) {
 308   assert(NameSuffix && "NameSuffix cannot be null!");
 309
 310 #ifndef NDEBUG
 311   for (Function::const_arg_iterator II = OldFunc->arg_begin(),
 312        E = OldFunc->arg_end(); II != E; ++II)
 313     assert(ValueMap.count(II) && "No mapping from source argument specified!");
 314 #endif
 315
 316   PruningFunctionCloner PFC(NewFunc, OldFunc, ValueMap, Returns,
 317                             NameSuffix, CodeInfo);
 318
 319   // Clone the entry block, and anything recursively reachable from it.
 320   PFC.CloneBlock(&OldFunc->getEntryBlock());
 321
 322   // Loop over all of the basic blocks in the old function.  If the block was
 323   // reachable, we have cloned it and the old block is now in the value map:
 324   // insert it into the new function in the right order.  If not, ignore it.
 325   //
 326   // Defer PHI resolution until rest of function is resolved.
 327   std::vector<const PHINode*> PHIToResolve;
 328   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
 329        BI != BE; ++BI) {
 330     BasicBlock *NewBB = cast_or_null<BasicBlock>(ValueMap[BI]);
 331     if (NewBB == 0) continue;  // Dead block.
 332
 333     // Add the new block to the new function.
 334     NewFunc->getBasicBlockList().push_back(NewBB);
 335
 336     // Loop over all of the instructions in the block, fixing up operand
 337     // references as we go.  This uses ValueMap to do all the hard work.
 338     //
 339     BasicBlock::iterator I = NewBB->begin();
 340
 341     // Handle PHI nodes specially, as we have to remove references to dead
 342     // blocks.
 343     if (PHINode *PN = dyn_cast<PHINode>(I)) {
 344       // Skip over all PHI nodes, remembering them for later.
 345       BasicBlock::const_iterator OldI = BI->begin();
 346       for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI)
 347         PHIToResolve.push_back(cast<PHINode>(OldI));
 348     }
 349
 350     // Otherwise, remap the rest of the instructions normally.
 351     for (; I != NewBB->end(); ++I)
 352       RemapInstruction(I, ValueMap);
 353   }
 354
 355   // Defer PHI resolution until rest of function is resolved, PHI resolution
 356   // requires the CFG to be up-to-date.
 357   for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
 358     const PHINode *OPN = PHIToResolve[phino];
 359     unsigned NumPreds = OPN->getNumIncomingValues();
 360     const BasicBlock *OldBB = OPN->getParent();
 361     BasicBlock *NewBB = cast<BasicBlock>(ValueMap[OldBB]);
 362
 363     // Map operands for blocks that are live and remove operands for blocks
 364     // that are dead.
 365     for (; phino != PHIToResolve.size() &&
 366          PHIToResolve[phino]->getParent() == OldBB; ++phino) {
 367       OPN = PHIToResolve[phino];
 368       PHINode *PN = cast<PHINode>(ValueMap[OPN]);
 369       for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
 370         if (BasicBlock *MappedBlock =
 371             cast_or_null<BasicBlock>(ValueMap[PN->getIncomingBlock(pred)])) {
 372           Value *InVal = MapValue(PN->getIncomingValue(pred), ValueMap);
 373           assert(InVal && "Unknown input value?");
 374           PN->setIncomingValue(pred, InVal);
 375           PN->setIncomingBlock(pred, MappedBlock);
 376         } else {
 377           PN->removeIncomingValue(pred, false);
 378           --pred, --e;  // Revisit the next entry.
 379         }
 380       }
 381     }
 382
 383     // The loop above has removed PHI entries for those blocks that are dead
 384     // and has updated others.  However, if a block is live (i.e. copied over)
 385     // but its terminator has been changed to not go to this block, then our
 386     // phi nodes will have invalid entries.  Update the PHI nodes in this
 387     // case.
 388     PHINode *PN = cast<PHINode>(NewBB->begin());
 389     NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
 390     if (NumPreds != PN->getNumIncomingValues()) {
 391       assert(NumPreds < PN->getNumIncomingValues());
 392       // Count how many times each predecessor comes to this block.
 393       std::map<BasicBlock*, unsigned> PredCount;
 394       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
 395            PI != E; ++PI)
 396         --PredCount[*PI];
 397
 398       // Figure out how many entries to remove from each PHI.
 399       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 400         ++PredCount[PN->getIncomingBlock(i)];
 401
 402       // At this point, the excess predecessor entries are positive in the
 403       // map.  Loop over all of the PHIs and remove excess predecessor
 404       // entries.
 405       BasicBlock::iterator I = NewBB->begin();
 406       for (; (PN = dyn_cast<PHINode>(I)); ++I) {
 407         for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
 408              E = PredCount.end(); PCI != E; ++PCI) {
 409           BasicBlock *Pred     = PCI->first;
 410           for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
 411             PN->removeIncomingValue(Pred, false);
 412         }
 413       }
 414     }
 415
 416     // If the loops above have made these phi nodes have 0 or 1 operand,
 417     // replace them with undef or the input value.  We must do this for
 418     // correctness, because 0-operand phis are not valid.
 419     PN = cast<PHINode>(NewBB->begin());
 420     if (PN->getNumIncomingValues() == 0) {
 421       BasicBlock::iterator I = NewBB->begin();
 422       BasicBlock::const_iterator OldI = OldBB->begin();
 423       while ((PN = dyn_cast<PHINode>(I++))) {
 424         Value *NV = UndefValue::get(PN->getType());
 425         PN->replaceAllUsesWith(NV);
 426         assert(ValueMap[OldI] == PN && "ValueMap mismatch");
 427         ValueMap[OldI] = NV;
 428         PN->eraseFromParent();
 429         ++OldI;
 430       }
 431     } else if (PN->getNumIncomingValues() == 1) {
 432       BasicBlock::iterator I = NewBB->begin();
 433       BasicBlock::const_iterator OldI = OldBB->begin();
 434       while ((PN = dyn_cast<PHINode>(I++))) {
 435         Value *NV = PN->getIncomingValue(0);
 436         PN->replaceAllUsesWith(NV);
 437         assert(ValueMap[OldI] == PN && "ValueMap mismatch");
 438         ValueMap[OldI] = NV;
 439         PN->eraseFromParent();
 440         ++OldI;
 441       }
 442     }
 443   }
 444
 445   // Now that the inlined function body has been fully constructed, go through
 446   // and zap unconditional fall-through branches.  This happen all the time when
 447   // specializing code: code specialization turns conditional branches into
 448   // uncond branches, and this code folds them.
 449   Function::iterator I = cast<BasicBlock>(ValueMap[&OldFunc->getEntryBlock()]);
 450   while (I != NewFunc->end()) {
 451     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
 452     if (!BI || BI->isConditional()) { ++I; continue; }
 453
 454     BasicBlock *Dest = BI->getSuccessor(0);
 455     if (!Dest->getSinglePredecessor()) { ++I; continue; }
 456
 457     // We know all single-entry PHI nodes in the inlined function have been
 458     // removed, so we just need to splice the blocks.
 459     BI->eraseFromParent();
 460
 461     // Move all the instructions in the succ to the pred.
 462     I->getInstList().splice(I->end(), Dest->getInstList());
 463
 464     // Make all PHI nodes that referred to Dest now refer to I as their source.
 465     Dest->replaceAllUsesWith(I);
 466
 467     // Remove the dest block.
 468     Dest->eraseFromParent();
 469
 470     // Do not increment I, iteratively merge all things this block branches to.
 471   }
 472 }