1 //===- CloneFunction.cpp - Clone a function into another function ---------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // 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/ADT/SmallVector.h" 18 #include "llvm/Analysis/ConstantFolding.h" 19 #include "llvm/Analysis/InstructionSimplify.h" 20 #include "llvm/IR/CFG.h" 21 #include "llvm/IR/Constants.h" 22 #include "llvm/IR/DebugInfo.h" 23 #include "llvm/IR/DerivedTypes.h" 24 #include "llvm/IR/Function.h" 25 #include "llvm/IR/GlobalVariable.h" 26 #include "llvm/IR/Instructions.h" 27 #include "llvm/IR/IntrinsicInst.h" 28 #include "llvm/IR/LLVMContext.h" 29 #include "llvm/IR/Metadata.h" 30 #include "llvm/IR/Module.h" 31 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 32 #include "llvm/Transforms/Utils/Local.h" 33 #include "llvm/Transforms/Utils/ValueMapper.h" 34 #include <map> 35 using namespace llvm; 36 37 // CloneBasicBlock - See comments in Cloning.h 38 BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, 39 ValueToValueMapTy &VMap, 40 const Twine &NameSuffix, Function *F, 41 ClonedCodeInfo *CodeInfo) { 42 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F); 43 if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); 44 45 bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; 46 47 // Loop over all instructions, and copy them over. 48 for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); 49 II != IE; ++II) { 50 Instruction *NewInst = II->clone(); 51 if (II->hasName()) 52 NewInst->setName(II->getName()+NameSuffix); 53 NewBB->getInstList().push_back(NewInst); 54 VMap[II] = NewInst; // Add instruction map to value. 55 56 hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)); 57 if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 58 if (isa<ConstantInt>(AI->getArraySize())) 59 hasStaticAllocas = true; 60 else 61 hasDynamicAllocas = true; 62 } 63 } 64 65 if (CodeInfo) { 66 CodeInfo->ContainsCalls |= hasCalls; 67 CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; 68 CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 69 BB != &BB->getParent()->getEntryBlock(); 70 } 71 return NewBB; 72 } 73 74 // Clone OldFunc into NewFunc, transforming the old arguments into references to 75 // VMap values. 76 // 77 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, 78 ValueToValueMapTy &VMap, 79 bool ModuleLevelChanges, 80 SmallVectorImpl<ReturnInst*> &Returns, 81 const char *NameSuffix, ClonedCodeInfo *CodeInfo, 82 ValueMapTypeRemapper *TypeMapper, 83 ValueMaterializer *Materializer) { 84 assert(NameSuffix && "NameSuffix cannot be null!"); 85 86 #ifndef NDEBUG 87 for (Function::const_arg_iterator I = OldFunc->arg_begin(), 88 E = OldFunc->arg_end(); I != E; ++I) 89 assert(VMap.count(I) && "No mapping from source argument specified!"); 90 #endif 91 92 // Copy all attributes other than those stored in the AttributeSet. We need 93 // to remap the parameter indices of the AttributeSet. 94 AttributeSet NewAttrs = NewFunc->getAttributes(); 95 NewFunc->copyAttributesFrom(OldFunc); 96 NewFunc->setAttributes(NewAttrs); 97 98 AttributeSet OldAttrs = OldFunc->getAttributes(); 99 // Clone any argument attributes that are present in the VMap. 100 for (const Argument &OldArg : OldFunc->args()) 101 if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) { 102 AttributeSet attrs = 103 OldAttrs.getParamAttributes(OldArg.getArgNo() + 1); 104 if (attrs.getNumSlots() > 0) 105 NewArg->addAttr(attrs); 106 } 107 108 NewFunc->setAttributes( 109 NewFunc->getAttributes() 110 .addAttributes(NewFunc->getContext(), AttributeSet::ReturnIndex, 111 OldAttrs.getRetAttributes()) 112 .addAttributes(NewFunc->getContext(), AttributeSet::FunctionIndex, 113 OldAttrs.getFnAttributes())); 114 115 // Loop over all of the basic blocks in the function, cloning them as 116 // appropriate. Note that we save BE this way in order to handle cloning of 117 // recursive functions into themselves. 118 // 119 for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); 120 BI != BE; ++BI) { 121 const BasicBlock &BB = *BI; 122 123 // Create a new basic block and copy instructions into it! 124 BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo); 125 126 // Add basic block mapping. 127 VMap[&BB] = CBB; 128 129 // It is only legal to clone a function if a block address within that 130 // function is never referenced outside of the function. Given that, we 131 // want to map block addresses from the old function to block addresses in 132 // the clone. (This is different from the generic ValueMapper 133 // implementation, which generates an invalid blockaddress when 134 // cloning a function.) 135 if (BB.hasAddressTaken()) { 136 Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), 137 const_cast<BasicBlock*>(&BB)); 138 VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB); 139 } 140 141 // Note return instructions for the caller. 142 if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator())) 143 Returns.push_back(RI); 144 } 145 146 // Loop over all of the instructions in the function, fixing up operand 147 // references as we go. This uses VMap to do all the hard work. 148 for (Function::iterator BB = cast<BasicBlock>(VMap[OldFunc->begin()]), 149 BE = NewFunc->end(); BB != BE; ++BB) 150 // Loop over all instructions, fixing each one as we find it... 151 for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) 152 RemapInstruction(II, VMap, 153 ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, 154 TypeMapper, Materializer); 155 } 156 157 // Find the MDNode which corresponds to the DISubprogram data that described F. 158 static MDNode* FindSubprogram(const Function *F, DebugInfoFinder &Finder) { 159 for (DISubprogram Subprogram : Finder.subprograms()) { 160 if (Subprogram.describes(F)) return Subprogram; 161 } 162 return nullptr; 163 } 164 165 // Add an operand to an existing MDNode. The new operand will be added at the 166 // back of the operand list. 167 static void AddOperand(MDNode *Node, Value *Operand) { 168 SmallVector<Value*, 16> Operands; 169 for (unsigned i = 0; i < Node->getNumOperands(); i++) { 170 Operands.push_back(Node->getOperand(i)); 171 } 172 Operands.push_back(Operand); 173 MDNode *NewNode = MDNode::get(Node->getContext(), Operands); 174 Node->replaceAllUsesWith(NewNode); 175 } 176 177 // Clone the module-level debug info associated with OldFunc. The cloned data 178 // will point to NewFunc instead. 179 static void CloneDebugInfoMetadata(Function *NewFunc, const Function *OldFunc, 180 ValueToValueMapTy &VMap) { 181 DebugInfoFinder Finder; 182 Finder.processModule(*OldFunc->getParent()); 183 184 const MDNode *OldSubprogramMDNode = FindSubprogram(OldFunc, Finder); 185 if (!OldSubprogramMDNode) return; 186 187 // Ensure that OldFunc appears in the map. 188 // (if it's already there it must point to NewFunc anyway) 189 VMap[OldFunc] = NewFunc; 190 DISubprogram NewSubprogram(MapValue(OldSubprogramMDNode, VMap)); 191 192 for (DICompileUnit CU : Finder.compile_units()) { 193 DIArray Subprograms(CU.getSubprograms()); 194 195 // If the compile unit's function list contains the old function, it should 196 // also contain the new one. 197 for (unsigned i = 0; i < Subprograms.getNumElements(); i++) { 198 if ((MDNode*)Subprograms.getElement(i) == OldSubprogramMDNode) { 199 AddOperand(Subprograms, NewSubprogram); 200 } 201 } 202 } 203 } 204 205 /// CloneFunction - Return a copy of the specified function, but without 206 /// embedding the function into another module. Also, any references specified 207 /// in the VMap are changed to refer to their mapped value instead of the 208 /// original one. If any of the arguments to the function are in the VMap, 209 /// the arguments are deleted from the resultant function. The VMap is 210 /// updated to include mappings from all of the instructions and basicblocks in 211 /// the function from their old to new values. 212 /// 213 Function *llvm::CloneFunction(const Function *F, ValueToValueMapTy &VMap, 214 bool ModuleLevelChanges, 215 ClonedCodeInfo *CodeInfo) { 216 std::vector<Type*> ArgTypes; 217 218 // The user might be deleting arguments to the function by specifying them in 219 // the VMap. If so, we need to not add the arguments to the arg ty vector 220 // 221 for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 222 I != E; ++I) 223 if (VMap.count(I) == 0) // Haven't mapped the argument to anything yet? 224 ArgTypes.push_back(I->getType()); 225 226 // Create a new function type... 227 FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(), 228 ArgTypes, F->getFunctionType()->isVarArg()); 229 230 // Create the new function... 231 Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName()); 232 233 // Loop over the arguments, copying the names of the mapped arguments over... 234 Function::arg_iterator DestI = NewF->arg_begin(); 235 for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 236 I != E; ++I) 237 if (VMap.count(I) == 0) { // Is this argument preserved? 238 DestI->setName(I->getName()); // Copy the name over... 239 VMap[I] = DestI++; // Add mapping to VMap 240 } 241 242 if (ModuleLevelChanges) 243 CloneDebugInfoMetadata(NewF, F, VMap); 244 245 SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned. 246 CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo); 247 return NewF; 248 } 249 250 251 252 namespace { 253 /// PruningFunctionCloner - This class is a private class used to implement 254 /// the CloneAndPruneFunctionInto method. 255 struct PruningFunctionCloner { 256 Function *NewFunc; 257 const Function *OldFunc; 258 ValueToValueMapTy &VMap; 259 bool ModuleLevelChanges; 260 const char *NameSuffix; 261 ClonedCodeInfo *CodeInfo; 262 const DataLayout *DL; 263 public: 264 PruningFunctionCloner(Function *newFunc, const Function *oldFunc, 265 ValueToValueMapTy &valueMap, 266 bool moduleLevelChanges, 267 const char *nameSuffix, 268 ClonedCodeInfo *codeInfo, 269 const DataLayout *DL) 270 : NewFunc(newFunc), OldFunc(oldFunc), 271 VMap(valueMap), ModuleLevelChanges(moduleLevelChanges), 272 NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL) { 273 } 274 275 /// CloneBlock - The specified block is found to be reachable, clone it and 276 /// anything that it can reach. 277 void CloneBlock(const BasicBlock *BB, 278 std::vector<const BasicBlock*> &ToClone); 279 }; 280 } 281 282 /// CloneBlock - The specified block is found to be reachable, clone it and 283 /// anything that it can reach. 284 void PruningFunctionCloner::CloneBlock(const BasicBlock *BB, 285 std::vector<const BasicBlock*> &ToClone){ 286 WeakVH &BBEntry = VMap[BB]; 287 288 // Have we already cloned this block? 289 if (BBEntry) return; 290 291 // Nope, clone it now. 292 BasicBlock *NewBB; 293 BBEntry = NewBB = BasicBlock::Create(BB->getContext()); 294 if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); 295 296 // It is only legal to clone a function if a block address within that 297 // function is never referenced outside of the function. Given that, we 298 // want to map block addresses from the old function to block addresses in 299 // the clone. (This is different from the generic ValueMapper 300 // implementation, which generates an invalid blockaddress when 301 // cloning a function.) 302 // 303 // Note that we don't need to fix the mapping for unreachable blocks; 304 // the default mapping there is safe. 305 if (BB->hasAddressTaken()) { 306 Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), 307 const_cast<BasicBlock*>(BB)); 308 VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB); 309 } 310 311 312 bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; 313 314 // Loop over all instructions, and copy them over, DCE'ing as we go. This 315 // loop doesn't include the terminator. 316 for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end(); 317 II != IE; ++II) { 318 Instruction *NewInst = II->clone(); 319 320 // Eagerly remap operands to the newly cloned instruction, except for PHI 321 // nodes for which we defer processing until we update the CFG. 322 if (!isa<PHINode>(NewInst)) { 323 RemapInstruction(NewInst, VMap, 324 ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); 325 326 // If we can simplify this instruction to some other value, simply add 327 // a mapping to that value rather than inserting a new instruction into 328 // the basic block. 329 if (Value *V = SimplifyInstruction(NewInst, DL)) { 330 // On the off-chance that this simplifies to an instruction in the old 331 // function, map it back into the new function. 332 if (Value *MappedV = VMap.lookup(V)) 333 V = MappedV; 334 335 VMap[II] = V; 336 delete NewInst; 337 continue; 338 } 339 } 340 341 if (II->hasName()) 342 NewInst->setName(II->getName()+NameSuffix); 343 VMap[II] = NewInst; // Add instruction map to value. 344 NewBB->getInstList().push_back(NewInst); 345 hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)); 346 if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 347 if (isa<ConstantInt>(AI->getArraySize())) 348 hasStaticAllocas = true; 349 else 350 hasDynamicAllocas = true; 351 } 352 } 353 354 // Finally, clone over the terminator. 355 const TerminatorInst *OldTI = BB->getTerminator(); 356 bool TerminatorDone = false; 357 if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) { 358 if (BI->isConditional()) { 359 // If the condition was a known constant in the callee... 360 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); 361 // Or is a known constant in the caller... 362 if (!Cond) { 363 Value *V = VMap[BI->getCondition()]; 364 Cond = dyn_cast_or_null<ConstantInt>(V); 365 } 366 367 // Constant fold to uncond branch! 368 if (Cond) { 369 BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue()); 370 VMap[OldTI] = BranchInst::Create(Dest, NewBB); 371 ToClone.push_back(Dest); 372 TerminatorDone = true; 373 } 374 } 375 } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) { 376 // If switching on a value known constant in the caller. 377 ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition()); 378 if (!Cond) { // Or known constant after constant prop in the callee... 379 Value *V = VMap[SI->getCondition()]; 380 Cond = dyn_cast_or_null<ConstantInt>(V); 381 } 382 if (Cond) { // Constant fold to uncond branch! 383 SwitchInst::ConstCaseIt Case = SI->findCaseValue(Cond); 384 BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor()); 385 VMap[OldTI] = BranchInst::Create(Dest, NewBB); 386 ToClone.push_back(Dest); 387 TerminatorDone = true; 388 } 389 } 390 391 if (!TerminatorDone) { 392 Instruction *NewInst = OldTI->clone(); 393 if (OldTI->hasName()) 394 NewInst->setName(OldTI->getName()+NameSuffix); 395 NewBB->getInstList().push_back(NewInst); 396 VMap[OldTI] = NewInst; // Add instruction map to value. 397 398 // Recursively clone any reachable successor blocks. 399 const TerminatorInst *TI = BB->getTerminator(); 400 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 401 ToClone.push_back(TI->getSuccessor(i)); 402 } 403 404 if (CodeInfo) { 405 CodeInfo->ContainsCalls |= hasCalls; 406 CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; 407 CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 408 BB != &BB->getParent()->front(); 409 } 410 } 411 412 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, 413 /// except that it does some simple constant prop and DCE on the fly. The 414 /// effect of this is to copy significantly less code in cases where (for 415 /// example) a function call with constant arguments is inlined, and those 416 /// constant arguments cause a significant amount of code in the callee to be 417 /// dead. Since this doesn't produce an exact copy of the input, it can't be 418 /// used for things like CloneFunction or CloneModule. 419 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, 420 ValueToValueMapTy &VMap, 421 bool ModuleLevelChanges, 422 SmallVectorImpl<ReturnInst*> &Returns, 423 const char *NameSuffix, 424 ClonedCodeInfo *CodeInfo, 425 const DataLayout *DL, 426 Instruction *TheCall) { 427 assert(NameSuffix && "NameSuffix cannot be null!"); 428 429 #ifndef NDEBUG 430 for (Function::const_arg_iterator II = OldFunc->arg_begin(), 431 E = OldFunc->arg_end(); II != E; ++II) 432 assert(VMap.count(II) && "No mapping from source argument specified!"); 433 #endif 434 435 PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges, 436 NameSuffix, CodeInfo, DL); 437 438 // Clone the entry block, and anything recursively reachable from it. 439 std::vector<const BasicBlock*> CloneWorklist; 440 CloneWorklist.push_back(&OldFunc->getEntryBlock()); 441 while (!CloneWorklist.empty()) { 442 const BasicBlock *BB = CloneWorklist.back(); 443 CloneWorklist.pop_back(); 444 PFC.CloneBlock(BB, CloneWorklist); 445 } 446 447 // Loop over all of the basic blocks in the old function. If the block was 448 // reachable, we have cloned it and the old block is now in the value map: 449 // insert it into the new function in the right order. If not, ignore it. 450 // 451 // Defer PHI resolution until rest of function is resolved. 452 SmallVector<const PHINode*, 16> PHIToResolve; 453 for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); 454 BI != BE; ++BI) { 455 Value *V = VMap[BI]; 456 BasicBlock *NewBB = cast_or_null<BasicBlock>(V); 457 if (!NewBB) continue; // Dead block. 458 459 // Add the new block to the new function. 460 NewFunc->getBasicBlockList().push_back(NewBB); 461 462 // Handle PHI nodes specially, as we have to remove references to dead 463 // blocks. 464 for (BasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) 465 if (const PHINode *PN = dyn_cast<PHINode>(I)) 466 PHIToResolve.push_back(PN); 467 else 468 break; 469 470 // Finally, remap the terminator instructions, as those can't be remapped 471 // until all BBs are mapped. 472 RemapInstruction(NewBB->getTerminator(), VMap, 473 ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); 474 } 475 476 // Defer PHI resolution until rest of function is resolved, PHI resolution 477 // requires the CFG to be up-to-date. 478 for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) { 479 const PHINode *OPN = PHIToResolve[phino]; 480 unsigned NumPreds = OPN->getNumIncomingValues(); 481 const BasicBlock *OldBB = OPN->getParent(); 482 BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]); 483 484 // Map operands for blocks that are live and remove operands for blocks 485 // that are dead. 486 for (; phino != PHIToResolve.size() && 487 PHIToResolve[phino]->getParent() == OldBB; ++phino) { 488 OPN = PHIToResolve[phino]; 489 PHINode *PN = cast<PHINode>(VMap[OPN]); 490 for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) { 491 Value *V = VMap[PN->getIncomingBlock(pred)]; 492 if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) { 493 Value *InVal = MapValue(PN->getIncomingValue(pred), 494 VMap, 495 ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); 496 assert(InVal && "Unknown input value?"); 497 PN->setIncomingValue(pred, InVal); 498 PN->setIncomingBlock(pred, MappedBlock); 499 } else { 500 PN->removeIncomingValue(pred, false); 501 --pred, --e; // Revisit the next entry. 502 } 503 } 504 } 505 506 // The loop above has removed PHI entries for those blocks that are dead 507 // and has updated others. However, if a block is live (i.e. copied over) 508 // but its terminator has been changed to not go to this block, then our 509 // phi nodes will have invalid entries. Update the PHI nodes in this 510 // case. 511 PHINode *PN = cast<PHINode>(NewBB->begin()); 512 NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB)); 513 if (NumPreds != PN->getNumIncomingValues()) { 514 assert(NumPreds < PN->getNumIncomingValues()); 515 // Count how many times each predecessor comes to this block. 516 std::map<BasicBlock*, unsigned> PredCount; 517 for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); 518 PI != E; ++PI) 519 --PredCount[*PI]; 520 521 // Figure out how many entries to remove from each PHI. 522 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 523 ++PredCount[PN->getIncomingBlock(i)]; 524 525 // At this point, the excess predecessor entries are positive in the 526 // map. Loop over all of the PHIs and remove excess predecessor 527 // entries. 528 BasicBlock::iterator I = NewBB->begin(); 529 for (; (PN = dyn_cast<PHINode>(I)); ++I) { 530 for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(), 531 E = PredCount.end(); PCI != E; ++PCI) { 532 BasicBlock *Pred = PCI->first; 533 for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove) 534 PN->removeIncomingValue(Pred, false); 535 } 536 } 537 } 538 539 // If the loops above have made these phi nodes have 0 or 1 operand, 540 // replace them with undef or the input value. We must do this for 541 // correctness, because 0-operand phis are not valid. 542 PN = cast<PHINode>(NewBB->begin()); 543 if (PN->getNumIncomingValues() == 0) { 544 BasicBlock::iterator I = NewBB->begin(); 545 BasicBlock::const_iterator OldI = OldBB->begin(); 546 while ((PN = dyn_cast<PHINode>(I++))) { 547 Value *NV = UndefValue::get(PN->getType()); 548 PN->replaceAllUsesWith(NV); 549 assert(VMap[OldI] == PN && "VMap mismatch"); 550 VMap[OldI] = NV; 551 PN->eraseFromParent(); 552 ++OldI; 553 } 554 } 555 } 556 557 // Make a second pass over the PHINodes now that all of them have been 558 // remapped into the new function, simplifying the PHINode and performing any 559 // recursive simplifications exposed. This will transparently update the 560 // WeakVH in the VMap. Notably, we rely on that so that if we coalesce 561 // two PHINodes, the iteration over the old PHIs remains valid, and the 562 // mapping will just map us to the new node (which may not even be a PHI 563 // node). 564 for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx) 565 if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]])) 566 recursivelySimplifyInstruction(PN, DL); 567 568 // Now that the inlined function body has been fully constructed, go through 569 // and zap unconditional fall-through branches. This happen all the time when 570 // specializing code: code specialization turns conditional branches into 571 // uncond branches, and this code folds them. 572 Function::iterator Begin = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]); 573 Function::iterator I = Begin; 574 while (I != NewFunc->end()) { 575 // Check if this block has become dead during inlining or other 576 // simplifications. Note that the first block will appear dead, as it has 577 // not yet been wired up properly. 578 if (I != Begin && (pred_begin(I) == pred_end(I) || 579 I->getSinglePredecessor() == I)) { 580 BasicBlock *DeadBB = I++; 581 DeleteDeadBlock(DeadBB); 582 continue; 583 } 584 585 // We need to simplify conditional branches and switches with a constant 586 // operand. We try to prune these out when cloning, but if the 587 // simplification required looking through PHI nodes, those are only 588 // available after forming the full basic block. That may leave some here, 589 // and we still want to prune the dead code as early as possible. 590 ConstantFoldTerminator(I); 591 592 BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator()); 593 if (!BI || BI->isConditional()) { ++I; continue; } 594 595 BasicBlock *Dest = BI->getSuccessor(0); 596 if (!Dest->getSinglePredecessor()) { 597 ++I; continue; 598 } 599 600 // We shouldn't be able to get single-entry PHI nodes here, as instsimplify 601 // above should have zapped all of them.. 602 assert(!isa<PHINode>(Dest->begin())); 603 604 // We know all single-entry PHI nodes in the inlined function have been 605 // removed, so we just need to splice the blocks. 606 BI->eraseFromParent(); 607 608 // Make all PHI nodes that referred to Dest now refer to I as their source. 609 Dest->replaceAllUsesWith(I); 610 611 // Move all the instructions in the succ to the pred. 612 I->getInstList().splice(I->end(), Dest->getInstList()); 613 614 // Remove the dest block. 615 Dest->eraseFromParent(); 616 617 // Do not increment I, iteratively merge all things this block branches to. 618 } 619 620 // Make a final pass over the basic blocks from theh old function to gather 621 // any return instructions which survived folding. We have to do this here 622 // because we can iteratively remove and merge returns above. 623 for (Function::iterator I = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]), 624 E = NewFunc->end(); 625 I != E; ++I) 626 if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator())) 627 Returns.push_back(RI); 628 } 629