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