1 //===- CodeExtractor.cpp - Pull code region into a new function -----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the interface to tear out a code region, such as an 10 // individual loop or a parallel section, into a new function, replacing it with 11 // a call to the new function. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/CodeExtractor.h" 16 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/SetVector.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/Analysis/AssumptionCache.h" 23 #include "llvm/Analysis/BlockFrequencyInfo.h" 24 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 25 #include "llvm/Analysis/BranchProbabilityInfo.h" 26 #include "llvm/IR/Argument.h" 27 #include "llvm/IR/Attributes.h" 28 #include "llvm/IR/BasicBlock.h" 29 #include "llvm/IR/CFG.h" 30 #include "llvm/IR/Constant.h" 31 #include "llvm/IR/Constants.h" 32 #include "llvm/IR/DIBuilder.h" 33 #include "llvm/IR/DataLayout.h" 34 #include "llvm/IR/DebugInfo.h" 35 #include "llvm/IR/DebugInfoMetadata.h" 36 #include "llvm/IR/DerivedTypes.h" 37 #include "llvm/IR/Dominators.h" 38 #include "llvm/IR/Function.h" 39 #include "llvm/IR/GlobalValue.h" 40 #include "llvm/IR/InstIterator.h" 41 #include "llvm/IR/InstrTypes.h" 42 #include "llvm/IR/Instruction.h" 43 #include "llvm/IR/Instructions.h" 44 #include "llvm/IR/IntrinsicInst.h" 45 #include "llvm/IR/Intrinsics.h" 46 #include "llvm/IR/LLVMContext.h" 47 #include "llvm/IR/MDBuilder.h" 48 #include "llvm/IR/Module.h" 49 #include "llvm/IR/PatternMatch.h" 50 #include "llvm/IR/Type.h" 51 #include "llvm/IR/User.h" 52 #include "llvm/IR/Value.h" 53 #include "llvm/IR/Verifier.h" 54 #include "llvm/Support/BlockFrequency.h" 55 #include "llvm/Support/BranchProbability.h" 56 #include "llvm/Support/Casting.h" 57 #include "llvm/Support/CommandLine.h" 58 #include "llvm/Support/Debug.h" 59 #include "llvm/Support/ErrorHandling.h" 60 #include "llvm/Support/raw_ostream.h" 61 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 62 #include <cassert> 63 #include <cstdint> 64 #include <iterator> 65 #include <map> 66 #include <utility> 67 #include <vector> 68 69 using namespace llvm; 70 using namespace llvm::PatternMatch; 71 using ProfileCount = Function::ProfileCount; 72 73 #define DEBUG_TYPE "code-extractor" 74 75 // Provide a command-line option to aggregate function arguments into a struct 76 // for functions produced by the code extractor. This is useful when converting 77 // extracted functions to pthread-based code, as only one argument (void*) can 78 // be passed in to pthread_create(). 79 static cl::opt<bool> 80 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 81 cl::desc("Aggregate arguments to code-extracted functions")); 82 83 /// Test whether a block is valid for extraction. 84 static bool isBlockValidForExtraction(const BasicBlock &BB, 85 const SetVector<BasicBlock *> &Result, 86 bool AllowVarArgs, bool AllowAlloca) { 87 // taking the address of a basic block moved to another function is illegal 88 if (BB.hasAddressTaken()) 89 return false; 90 91 // don't hoist code that uses another basicblock address, as it's likely to 92 // lead to unexpected behavior, like cross-function jumps 93 SmallPtrSet<User const *, 16> Visited; 94 SmallVector<User const *, 16> ToVisit; 95 96 for (Instruction const &Inst : BB) 97 ToVisit.push_back(&Inst); 98 99 while (!ToVisit.empty()) { 100 User const *Curr = ToVisit.pop_back_val(); 101 if (!Visited.insert(Curr).second) 102 continue; 103 if (isa<BlockAddress const>(Curr)) 104 return false; // even a reference to self is likely to be not compatible 105 106 if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB) 107 continue; 108 109 for (auto const &U : Curr->operands()) { 110 if (auto *UU = dyn_cast<User>(U)) 111 ToVisit.push_back(UU); 112 } 113 } 114 115 // If explicitly requested, allow vastart and alloca. For invoke instructions 116 // verify that extraction is valid. 117 for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { 118 if (isa<AllocaInst>(I)) { 119 if (!AllowAlloca) 120 return false; 121 continue; 122 } 123 124 if (const auto *II = dyn_cast<InvokeInst>(I)) { 125 // Unwind destination (either a landingpad, catchswitch, or cleanuppad) 126 // must be a part of the subgraph which is being extracted. 127 if (auto *UBB = II->getUnwindDest()) 128 if (!Result.count(UBB)) 129 return false; 130 continue; 131 } 132 133 // All catch handlers of a catchswitch instruction as well as the unwind 134 // destination must be in the subgraph. 135 if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) { 136 if (auto *UBB = CSI->getUnwindDest()) 137 if (!Result.count(UBB)) 138 return false; 139 for (const auto *HBB : CSI->handlers()) 140 if (!Result.count(const_cast<BasicBlock*>(HBB))) 141 return false; 142 continue; 143 } 144 145 // Make sure that entire catch handler is within subgraph. It is sufficient 146 // to check that catch return's block is in the list. 147 if (const auto *CPI = dyn_cast<CatchPadInst>(I)) { 148 for (const auto *U : CPI->users()) 149 if (const auto *CRI = dyn_cast<CatchReturnInst>(U)) 150 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) 151 return false; 152 continue; 153 } 154 155 // And do similar checks for cleanup handler - the entire handler must be 156 // in subgraph which is going to be extracted. For cleanup return should 157 // additionally check that the unwind destination is also in the subgraph. 158 if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) { 159 for (const auto *U : CPI->users()) 160 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U)) 161 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) 162 return false; 163 continue; 164 } 165 if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) { 166 if (auto *UBB = CRI->getUnwindDest()) 167 if (!Result.count(UBB)) 168 return false; 169 continue; 170 } 171 172 if (const CallInst *CI = dyn_cast<CallInst>(I)) { 173 if (const Function *F = CI->getCalledFunction()) { 174 auto IID = F->getIntrinsicID(); 175 if (IID == Intrinsic::vastart) { 176 if (AllowVarArgs) 177 continue; 178 else 179 return false; 180 } 181 182 // Currently, we miscompile outlined copies of eh_typid_for. There are 183 // proposals for fixing this in llvm.org/PR39545. 184 if (IID == Intrinsic::eh_typeid_for) 185 return false; 186 } 187 } 188 } 189 190 return true; 191 } 192 193 /// Build a set of blocks to extract if the input blocks are viable. 194 static SetVector<BasicBlock *> 195 buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 196 bool AllowVarArgs, bool AllowAlloca) { 197 assert(!BBs.empty() && "The set of blocks to extract must be non-empty"); 198 SetVector<BasicBlock *> Result; 199 200 // Loop over the blocks, adding them to our set-vector, and aborting with an 201 // empty set if we encounter invalid blocks. 202 for (BasicBlock *BB : BBs) { 203 // If this block is dead, don't process it. 204 if (DT && !DT->isReachableFromEntry(BB)) 205 continue; 206 207 if (!Result.insert(BB)) 208 llvm_unreachable("Repeated basic blocks in extraction input"); 209 } 210 211 LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName() 212 << '\n'); 213 214 for (auto *BB : Result) { 215 if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca)) 216 return {}; 217 218 // Make sure that the first block is not a landing pad. 219 if (BB == Result.front()) { 220 if (BB->isEHPad()) { 221 LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n"); 222 return {}; 223 } 224 continue; 225 } 226 227 // All blocks other than the first must not have predecessors outside of 228 // the subgraph which is being extracted. 229 for (auto *PBB : predecessors(BB)) 230 if (!Result.count(PBB)) { 231 LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from " 232 "outside the region except for the first block!\n" 233 << "Problematic source BB: " << BB->getName() << "\n" 234 << "Problematic destination BB: " << PBB->getName() 235 << "\n"); 236 return {}; 237 } 238 } 239 240 return Result; 241 } 242 243 CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 244 bool AggregateArgs, BlockFrequencyInfo *BFI, 245 BranchProbabilityInfo *BPI, AssumptionCache *AC, 246 bool AllowVarArgs, bool AllowAlloca, 247 BasicBlock *AllocationBlock, std::string Suffix, 248 bool ArgsInZeroAddressSpace) 249 : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), 250 BPI(BPI), AC(AC), AllocationBlock(AllocationBlock), 251 AllowVarArgs(AllowVarArgs), 252 Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)), 253 Suffix(Suffix), ArgsInZeroAddressSpace(ArgsInZeroAddressSpace) {} 254 255 /// definedInRegion - Return true if the specified value is defined in the 256 /// extracted region. 257 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { 258 if (Instruction *I = dyn_cast<Instruction>(V)) 259 if (Blocks.count(I->getParent())) 260 return true; 261 return false; 262 } 263 264 /// definedInCaller - Return true if the specified value is defined in the 265 /// function being code extracted, but not in the region being extracted. 266 /// These values must be passed in as live-ins to the function. 267 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { 268 if (isa<Argument>(V)) return true; 269 if (Instruction *I = dyn_cast<Instruction>(V)) 270 if (!Blocks.count(I->getParent())) 271 return true; 272 return false; 273 } 274 275 static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) { 276 BasicBlock *CommonExitBlock = nullptr; 277 auto hasNonCommonExitSucc = [&](BasicBlock *Block) { 278 for (auto *Succ : successors(Block)) { 279 // Internal edges, ok. 280 if (Blocks.count(Succ)) 281 continue; 282 if (!CommonExitBlock) { 283 CommonExitBlock = Succ; 284 continue; 285 } 286 if (CommonExitBlock != Succ) 287 return true; 288 } 289 return false; 290 }; 291 292 if (any_of(Blocks, hasNonCommonExitSucc)) 293 return nullptr; 294 295 return CommonExitBlock; 296 } 297 298 CodeExtractorAnalysisCache::CodeExtractorAnalysisCache(Function &F) { 299 for (BasicBlock &BB : F) { 300 for (Instruction &II : BB.instructionsWithoutDebug()) 301 if (auto *AI = dyn_cast<AllocaInst>(&II)) 302 Allocas.push_back(AI); 303 304 findSideEffectInfoForBlock(BB); 305 } 306 } 307 308 void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) { 309 for (Instruction &II : BB.instructionsWithoutDebug()) { 310 unsigned Opcode = II.getOpcode(); 311 Value *MemAddr = nullptr; 312 switch (Opcode) { 313 case Instruction::Store: 314 case Instruction::Load: { 315 if (Opcode == Instruction::Store) { 316 StoreInst *SI = cast<StoreInst>(&II); 317 MemAddr = SI->getPointerOperand(); 318 } else { 319 LoadInst *LI = cast<LoadInst>(&II); 320 MemAddr = LI->getPointerOperand(); 321 } 322 // Global variable can not be aliased with locals. 323 if (isa<Constant>(MemAddr)) 324 break; 325 Value *Base = MemAddr->stripInBoundsConstantOffsets(); 326 if (!isa<AllocaInst>(Base)) { 327 SideEffectingBlocks.insert(&BB); 328 return; 329 } 330 BaseMemAddrs[&BB].insert(Base); 331 break; 332 } 333 default: { 334 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II); 335 if (IntrInst) { 336 if (IntrInst->isLifetimeStartOrEnd()) 337 break; 338 SideEffectingBlocks.insert(&BB); 339 return; 340 } 341 // Treat all the other cases conservatively if it has side effects. 342 if (II.mayHaveSideEffects()) { 343 SideEffectingBlocks.insert(&BB); 344 return; 345 } 346 } 347 } 348 } 349 } 350 351 bool CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr( 352 BasicBlock &BB, AllocaInst *Addr) const { 353 if (SideEffectingBlocks.count(&BB)) 354 return true; 355 auto It = BaseMemAddrs.find(&BB); 356 if (It != BaseMemAddrs.end()) 357 return It->second.count(Addr); 358 return false; 359 } 360 361 bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers( 362 const CodeExtractorAnalysisCache &CEAC, Instruction *Addr) const { 363 AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets()); 364 Function *Func = (*Blocks.begin())->getParent(); 365 for (BasicBlock &BB : *Func) { 366 if (Blocks.count(&BB)) 367 continue; 368 if (CEAC.doesBlockContainClobberOfAddr(BB, AI)) 369 return false; 370 } 371 return true; 372 } 373 374 BasicBlock * 375 CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) { 376 BasicBlock *SinglePredFromOutlineRegion = nullptr; 377 assert(!Blocks.count(CommonExitBlock) && 378 "Expect a block outside the region!"); 379 for (auto *Pred : predecessors(CommonExitBlock)) { 380 if (!Blocks.count(Pred)) 381 continue; 382 if (!SinglePredFromOutlineRegion) { 383 SinglePredFromOutlineRegion = Pred; 384 } else if (SinglePredFromOutlineRegion != Pred) { 385 SinglePredFromOutlineRegion = nullptr; 386 break; 387 } 388 } 389 390 if (SinglePredFromOutlineRegion) 391 return SinglePredFromOutlineRegion; 392 393 #ifndef NDEBUG 394 auto getFirstPHI = [](BasicBlock *BB) { 395 BasicBlock::iterator I = BB->begin(); 396 PHINode *FirstPhi = nullptr; 397 while (I != BB->end()) { 398 PHINode *Phi = dyn_cast<PHINode>(I); 399 if (!Phi) 400 break; 401 if (!FirstPhi) { 402 FirstPhi = Phi; 403 break; 404 } 405 } 406 return FirstPhi; 407 }; 408 // If there are any phi nodes, the single pred either exists or has already 409 // be created before code extraction. 410 assert(!getFirstPHI(CommonExitBlock) && "Phi not expected"); 411 #endif 412 413 BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock( 414 CommonExitBlock->getFirstNonPHI()->getIterator()); 415 416 for (BasicBlock *Pred : 417 llvm::make_early_inc_range(predecessors(CommonExitBlock))) { 418 if (Blocks.count(Pred)) 419 continue; 420 Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock); 421 } 422 // Now add the old exit block to the outline region. 423 Blocks.insert(CommonExitBlock); 424 OldTargets.push_back(NewExitBlock); 425 return CommonExitBlock; 426 } 427 428 // Find the pair of life time markers for address 'Addr' that are either 429 // defined inside the outline region or can legally be shrinkwrapped into the 430 // outline region. If there are not other untracked uses of the address, return 431 // the pair of markers if found; otherwise return a pair of nullptr. 432 CodeExtractor::LifetimeMarkerInfo 433 CodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 434 Instruction *Addr, 435 BasicBlock *ExitBlock) const { 436 LifetimeMarkerInfo Info; 437 438 for (User *U : Addr->users()) { 439 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U); 440 if (IntrInst) { 441 // We don't model addresses with multiple start/end markers, but the 442 // markers do not need to be in the region. 443 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) { 444 if (Info.LifeStart) 445 return {}; 446 Info.LifeStart = IntrInst; 447 continue; 448 } 449 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) { 450 if (Info.LifeEnd) 451 return {}; 452 Info.LifeEnd = IntrInst; 453 continue; 454 } 455 // At this point, permit debug uses outside of the region. 456 // This is fixed in a later call to fixupDebugInfoPostExtraction(). 457 if (isa<DbgInfoIntrinsic>(IntrInst)) 458 continue; 459 } 460 // Find untracked uses of the address, bail. 461 if (!definedInRegion(Blocks, U)) 462 return {}; 463 } 464 465 if (!Info.LifeStart || !Info.LifeEnd) 466 return {}; 467 468 Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart); 469 Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd); 470 // Do legality check. 471 if ((Info.SinkLifeStart || Info.HoistLifeEnd) && 472 !isLegalToShrinkwrapLifetimeMarkers(CEAC, Addr)) 473 return {}; 474 475 // Check to see if we have a place to do hoisting, if not, bail. 476 if (Info.HoistLifeEnd && !ExitBlock) 477 return {}; 478 479 return Info; 480 } 481 482 void CodeExtractor::findAllocas(const CodeExtractorAnalysisCache &CEAC, 483 ValueSet &SinkCands, ValueSet &HoistCands, 484 BasicBlock *&ExitBlock) const { 485 Function *Func = (*Blocks.begin())->getParent(); 486 ExitBlock = getCommonExitBlock(Blocks); 487 488 auto moveOrIgnoreLifetimeMarkers = 489 [&](const LifetimeMarkerInfo &LMI) -> bool { 490 if (!LMI.LifeStart) 491 return false; 492 if (LMI.SinkLifeStart) { 493 LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart 494 << "\n"); 495 SinkCands.insert(LMI.LifeStart); 496 } 497 if (LMI.HoistLifeEnd) { 498 LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n"); 499 HoistCands.insert(LMI.LifeEnd); 500 } 501 return true; 502 }; 503 504 // Look up allocas in the original function in CodeExtractorAnalysisCache, as 505 // this is much faster than walking all the instructions. 506 for (AllocaInst *AI : CEAC.getAllocas()) { 507 BasicBlock *BB = AI->getParent(); 508 if (Blocks.count(BB)) 509 continue; 510 511 // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca, 512 // check whether it is actually still in the original function. 513 Function *AIFunc = BB->getParent(); 514 if (AIFunc != Func) 515 continue; 516 517 LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock); 518 bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo); 519 if (Moved) { 520 LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n"); 521 SinkCands.insert(AI); 522 continue; 523 } 524 525 // Find bitcasts in the outlined region that have lifetime marker users 526 // outside that region. Replace the lifetime marker use with an 527 // outside region bitcast to avoid unnecessary alloca/reload instructions 528 // and extra lifetime markers. 529 SmallVector<Instruction *, 2> LifetimeBitcastUsers; 530 for (User *U : AI->users()) { 531 if (!definedInRegion(Blocks, U)) 532 continue; 533 534 if (U->stripInBoundsConstantOffsets() != AI) 535 continue; 536 537 Instruction *Bitcast = cast<Instruction>(U); 538 for (User *BU : Bitcast->users()) { 539 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(BU); 540 if (!IntrInst) 541 continue; 542 543 if (!IntrInst->isLifetimeStartOrEnd()) 544 continue; 545 546 if (definedInRegion(Blocks, IntrInst)) 547 continue; 548 549 LLVM_DEBUG(dbgs() << "Replace use of extracted region bitcast" 550 << *Bitcast << " in out-of-region lifetime marker " 551 << *IntrInst << "\n"); 552 LifetimeBitcastUsers.push_back(IntrInst); 553 } 554 } 555 556 for (Instruction *I : LifetimeBitcastUsers) { 557 Module *M = AIFunc->getParent(); 558 LLVMContext &Ctx = M->getContext(); 559 auto *Int8PtrTy = PointerType::getUnqual(Ctx); 560 CastInst *CastI = 561 CastInst::CreatePointerCast(AI, Int8PtrTy, "lt.cast", I->getIterator()); 562 I->replaceUsesOfWith(I->getOperand(1), CastI); 563 } 564 565 // Follow any bitcasts. 566 SmallVector<Instruction *, 2> Bitcasts; 567 SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo; 568 for (User *U : AI->users()) { 569 if (U->stripInBoundsConstantOffsets() == AI) { 570 Instruction *Bitcast = cast<Instruction>(U); 571 LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock); 572 if (LMI.LifeStart) { 573 Bitcasts.push_back(Bitcast); 574 BitcastLifetimeInfo.push_back(LMI); 575 continue; 576 } 577 } 578 579 // Found unknown use of AI. 580 if (!definedInRegion(Blocks, U)) { 581 Bitcasts.clear(); 582 break; 583 } 584 } 585 586 // Either no bitcasts reference the alloca or there are unknown uses. 587 if (Bitcasts.empty()) 588 continue; 589 590 LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n"); 591 SinkCands.insert(AI); 592 for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) { 593 Instruction *BitcastAddr = Bitcasts[I]; 594 const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I]; 595 assert(LMI.LifeStart && 596 "Unsafe to sink bitcast without lifetime markers"); 597 moveOrIgnoreLifetimeMarkers(LMI); 598 if (!definedInRegion(Blocks, BitcastAddr)) { 599 LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr 600 << "\n"); 601 SinkCands.insert(BitcastAddr); 602 } 603 } 604 } 605 } 606 607 bool CodeExtractor::isEligible() const { 608 if (Blocks.empty()) 609 return false; 610 BasicBlock *Header = *Blocks.begin(); 611 Function *F = Header->getParent(); 612 613 // For functions with varargs, check that varargs handling is only done in the 614 // outlined function, i.e vastart and vaend are only used in outlined blocks. 615 if (AllowVarArgs && F->getFunctionType()->isVarArg()) { 616 auto containsVarArgIntrinsic = [](const Instruction &I) { 617 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 618 if (const Function *Callee = CI->getCalledFunction()) 619 return Callee->getIntrinsicID() == Intrinsic::vastart || 620 Callee->getIntrinsicID() == Intrinsic::vaend; 621 return false; 622 }; 623 624 for (auto &BB : *F) { 625 if (Blocks.count(&BB)) 626 continue; 627 if (llvm::any_of(BB, containsVarArgIntrinsic)) 628 return false; 629 } 630 } 631 return true; 632 } 633 634 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 635 const ValueSet &SinkCands, 636 bool CollectGlobalInputs) const { 637 for (BasicBlock *BB : Blocks) { 638 // If a used value is defined outside the region, it's an input. If an 639 // instruction is used outside the region, it's an output. 640 for (Instruction &II : *BB) { 641 for (auto &OI : II.operands()) { 642 Value *V = OI; 643 if (!SinkCands.count(V) && 644 (definedInCaller(Blocks, V) || 645 (CollectGlobalInputs && llvm::isa<llvm::GlobalVariable>(V)))) 646 Inputs.insert(V); 647 } 648 649 for (User *U : II.users()) 650 if (!definedInRegion(Blocks, U)) { 651 Outputs.insert(&II); 652 break; 653 } 654 } 655 } 656 } 657 658 /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside 659 /// of the region, we need to split the entry block of the region so that the 660 /// PHI node is easier to deal with. 661 void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) { 662 unsigned NumPredsFromRegion = 0; 663 unsigned NumPredsOutsideRegion = 0; 664 665 if (Header != &Header->getParent()->getEntryBlock()) { 666 PHINode *PN = dyn_cast<PHINode>(Header->begin()); 667 if (!PN) return; // No PHI nodes. 668 669 // If the header node contains any PHI nodes, check to see if there is more 670 // than one entry from outside the region. If so, we need to sever the 671 // header block into two. 672 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 673 if (Blocks.count(PN->getIncomingBlock(i))) 674 ++NumPredsFromRegion; 675 else 676 ++NumPredsOutsideRegion; 677 678 // If there is one (or fewer) predecessor from outside the region, we don't 679 // need to do anything special. 680 if (NumPredsOutsideRegion <= 1) return; 681 } 682 683 // Otherwise, we need to split the header block into two pieces: one 684 // containing PHI nodes merging values from outside of the region, and a 685 // second that contains all of the code for the block and merges back any 686 // incoming values from inside of the region. 687 BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT); 688 689 // We only want to code extract the second block now, and it becomes the new 690 // header of the region. 691 BasicBlock *OldPred = Header; 692 Blocks.remove(OldPred); 693 Blocks.insert(NewBB); 694 Header = NewBB; 695 696 // Okay, now we need to adjust the PHI nodes and any branches from within the 697 // region to go to the new header block instead of the old header block. 698 if (NumPredsFromRegion) { 699 PHINode *PN = cast<PHINode>(OldPred->begin()); 700 // Loop over all of the predecessors of OldPred that are in the region, 701 // changing them to branch to NewBB instead. 702 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 703 if (Blocks.count(PN->getIncomingBlock(i))) { 704 Instruction *TI = PN->getIncomingBlock(i)->getTerminator(); 705 TI->replaceUsesOfWith(OldPred, NewBB); 706 } 707 708 // Okay, everything within the region is now branching to the right block, we 709 // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 710 BasicBlock::iterator AfterPHIs; 711 for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 712 PHINode *PN = cast<PHINode>(AfterPHIs); 713 // Create a new PHI node in the new region, which has an incoming value 714 // from OldPred of PN. 715 PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, 716 PN->getName() + ".ce"); 717 NewPN->insertBefore(NewBB->begin()); 718 PN->replaceAllUsesWith(NewPN); 719 NewPN->addIncoming(PN, OldPred); 720 721 // Loop over all of the incoming value in PN, moving them to NewPN if they 722 // are from the extracted region. 723 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 724 if (Blocks.count(PN->getIncomingBlock(i))) { 725 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 726 PN->removeIncomingValue(i); 727 --i; 728 } 729 } 730 } 731 } 732 } 733 734 /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from 735 /// outlined region, we split these PHIs on two: one with inputs from region 736 /// and other with remaining incoming blocks; then first PHIs are placed in 737 /// outlined region. 738 void CodeExtractor::severSplitPHINodesOfExits( 739 const SetVector<BasicBlock *> &Exits) { 740 for (BasicBlock *ExitBB : Exits) { 741 BasicBlock *NewBB = nullptr; 742 743 for (PHINode &PN : ExitBB->phis()) { 744 // Find all incoming values from the outlining region. 745 SmallVector<unsigned, 2> IncomingVals; 746 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i) 747 if (Blocks.count(PN.getIncomingBlock(i))) 748 IncomingVals.push_back(i); 749 750 // Do not process PHI if there is one (or fewer) predecessor from region. 751 // If PHI has exactly one predecessor from region, only this one incoming 752 // will be replaced on codeRepl block, so it should be safe to skip PHI. 753 if (IncomingVals.size() <= 1) 754 continue; 755 756 // Create block for new PHIs and add it to the list of outlined if it 757 // wasn't done before. 758 if (!NewBB) { 759 NewBB = BasicBlock::Create(ExitBB->getContext(), 760 ExitBB->getName() + ".split", 761 ExitBB->getParent(), ExitBB); 762 NewBB->IsNewDbgInfoFormat = ExitBB->IsNewDbgInfoFormat; 763 SmallVector<BasicBlock *, 4> Preds(predecessors(ExitBB)); 764 for (BasicBlock *PredBB : Preds) 765 if (Blocks.count(PredBB)) 766 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB); 767 BranchInst::Create(ExitBB, NewBB); 768 Blocks.insert(NewBB); 769 } 770 771 // Split this PHI. 772 PHINode *NewPN = PHINode::Create(PN.getType(), IncomingVals.size(), 773 PN.getName() + ".ce"); 774 NewPN->insertBefore(NewBB->getFirstNonPHIIt()); 775 for (unsigned i : IncomingVals) 776 NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i)); 777 for (unsigned i : reverse(IncomingVals)) 778 PN.removeIncomingValue(i, false); 779 PN.addIncoming(NewPN, NewBB); 780 } 781 } 782 } 783 784 void CodeExtractor::splitReturnBlocks() { 785 for (BasicBlock *Block : Blocks) 786 if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) { 787 BasicBlock *New = 788 Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret"); 789 if (DT) { 790 // Old dominates New. New node dominates all other nodes dominated 791 // by Old. 792 DomTreeNode *OldNode = DT->getNode(Block); 793 SmallVector<DomTreeNode *, 8> Children(OldNode->begin(), 794 OldNode->end()); 795 796 DomTreeNode *NewNode = DT->addNewBlock(New, Block); 797 798 for (DomTreeNode *I : Children) 799 DT->changeImmediateDominator(I, NewNode); 800 } 801 } 802 } 803 804 /// constructFunction - make a function based on inputs and outputs, as follows: 805 /// f(in0, ..., inN, out0, ..., outN) 806 Function *CodeExtractor::constructFunction(const ValueSet &inputs, 807 const ValueSet &outputs, 808 BasicBlock *header, 809 BasicBlock *newRootNode, 810 BasicBlock *newHeader, 811 Function *oldFunction, 812 Module *M) { 813 LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n"); 814 LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n"); 815 816 // This function returns unsigned, outputs will go back by reference. 817 switch (NumExitBlocks) { 818 case 0: 819 case 1: RetTy = Type::getVoidTy(header->getContext()); break; 820 case 2: RetTy = Type::getInt1Ty(header->getContext()); break; 821 default: RetTy = Type::getInt16Ty(header->getContext()); break; 822 } 823 824 std::vector<Type *> ParamTy; 825 std::vector<Type *> AggParamTy; 826 ValueSet StructValues; 827 const DataLayout &DL = M->getDataLayout(); 828 829 // Add the types of the input values to the function's argument list 830 for (Value *value : inputs) { 831 LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n"); 832 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(value)) { 833 AggParamTy.push_back(value->getType()); 834 StructValues.insert(value); 835 } else 836 ParamTy.push_back(value->getType()); 837 } 838 839 // Add the types of the output values to the function's argument list. 840 for (Value *output : outputs) { 841 LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n"); 842 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) { 843 AggParamTy.push_back(output->getType()); 844 StructValues.insert(output); 845 } else 846 ParamTy.push_back( 847 PointerType::get(output->getType(), DL.getAllocaAddrSpace())); 848 } 849 850 assert( 851 (ParamTy.size() + AggParamTy.size()) == 852 (inputs.size() + outputs.size()) && 853 "Number of scalar and aggregate params does not match inputs, outputs"); 854 assert((StructValues.empty() || AggregateArgs) && 855 "Expeced StructValues only with AggregateArgs set"); 856 857 // Concatenate scalar and aggregate params in ParamTy. 858 size_t NumScalarParams = ParamTy.size(); 859 StructType *StructTy = nullptr; 860 if (AggregateArgs && !AggParamTy.empty()) { 861 StructTy = StructType::get(M->getContext(), AggParamTy); 862 ParamTy.push_back(PointerType::get( 863 StructTy, ArgsInZeroAddressSpace ? 0 : DL.getAllocaAddrSpace())); 864 } 865 866 LLVM_DEBUG({ 867 dbgs() << "Function type: " << *RetTy << " f("; 868 for (Type *i : ParamTy) 869 dbgs() << *i << ", "; 870 dbgs() << ")\n"; 871 }); 872 873 FunctionType *funcType = FunctionType::get( 874 RetTy, ParamTy, AllowVarArgs && oldFunction->isVarArg()); 875 876 std::string SuffixToUse = 877 Suffix.empty() 878 ? (header->getName().empty() ? "extracted" : header->getName().str()) 879 : Suffix; 880 // Create the new function 881 Function *newFunction = Function::Create( 882 funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(), 883 oldFunction->getName() + "." + SuffixToUse, M); 884 newFunction->IsNewDbgInfoFormat = oldFunction->IsNewDbgInfoFormat; 885 886 // Inherit all of the target dependent attributes and white-listed 887 // target independent attributes. 888 // (e.g. If the extracted region contains a call to an x86.sse 889 // instruction we need to make sure that the extracted region has the 890 // "target-features" attribute allowing it to be lowered. 891 // FIXME: This should be changed to check to see if a specific 892 // attribute can not be inherited. 893 for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) { 894 if (Attr.isStringAttribute()) { 895 if (Attr.getKindAsString() == "thunk") 896 continue; 897 } else 898 switch (Attr.getKindAsEnum()) { 899 // Those attributes cannot be propagated safely. Explicitly list them 900 // here so we get a warning if new attributes are added. 901 case Attribute::AllocSize: 902 case Attribute::Builtin: 903 case Attribute::Convergent: 904 case Attribute::JumpTable: 905 case Attribute::Naked: 906 case Attribute::NoBuiltin: 907 case Attribute::NoMerge: 908 case Attribute::NoReturn: 909 case Attribute::NoSync: 910 case Attribute::ReturnsTwice: 911 case Attribute::Speculatable: 912 case Attribute::StackAlignment: 913 case Attribute::WillReturn: 914 case Attribute::AllocKind: 915 case Attribute::PresplitCoroutine: 916 case Attribute::Memory: 917 case Attribute::NoFPClass: 918 case Attribute::CoroDestroyOnlyWhenComplete: 919 case Attribute::CoroElideSafe: 920 continue; 921 // Those attributes should be safe to propagate to the extracted function. 922 case Attribute::AlwaysInline: 923 case Attribute::Cold: 924 case Attribute::DisableSanitizerInstrumentation: 925 case Attribute::FnRetThunkExtern: 926 case Attribute::Hot: 927 case Attribute::HybridPatchable: 928 case Attribute::NoRecurse: 929 case Attribute::InlineHint: 930 case Attribute::MinSize: 931 case Attribute::NoCallback: 932 case Attribute::NoDuplicate: 933 case Attribute::NoFree: 934 case Attribute::NoImplicitFloat: 935 case Attribute::NoInline: 936 case Attribute::NonLazyBind: 937 case Attribute::NoRedZone: 938 case Attribute::NoUnwind: 939 case Attribute::NoSanitizeBounds: 940 case Attribute::NoSanitizeCoverage: 941 case Attribute::NullPointerIsValid: 942 case Attribute::OptimizeForDebugging: 943 case Attribute::OptForFuzzing: 944 case Attribute::OptimizeNone: 945 case Attribute::OptimizeForSize: 946 case Attribute::SafeStack: 947 case Attribute::ShadowCallStack: 948 case Attribute::SanitizeAddress: 949 case Attribute::SanitizeMemory: 950 case Attribute::SanitizeNumericalStability: 951 case Attribute::SanitizeThread: 952 case Attribute::SanitizeHWAddress: 953 case Attribute::SanitizeMemTag: 954 case Attribute::SanitizeRealtime: 955 case Attribute::SpeculativeLoadHardening: 956 case Attribute::StackProtect: 957 case Attribute::StackProtectReq: 958 case Attribute::StackProtectStrong: 959 case Attribute::StrictFP: 960 case Attribute::UWTable: 961 case Attribute::VScaleRange: 962 case Attribute::NoCfCheck: 963 case Attribute::MustProgress: 964 case Attribute::NoProfile: 965 case Attribute::SkipProfile: 966 break; 967 // These attributes cannot be applied to functions. 968 case Attribute::Alignment: 969 case Attribute::AllocatedPointer: 970 case Attribute::AllocAlign: 971 case Attribute::ByVal: 972 case Attribute::Dereferenceable: 973 case Attribute::DereferenceableOrNull: 974 case Attribute::ElementType: 975 case Attribute::InAlloca: 976 case Attribute::InReg: 977 case Attribute::Nest: 978 case Attribute::NoAlias: 979 case Attribute::NoCapture: 980 case Attribute::NoUndef: 981 case Attribute::NonNull: 982 case Attribute::Preallocated: 983 case Attribute::ReadNone: 984 case Attribute::ReadOnly: 985 case Attribute::Returned: 986 case Attribute::SExt: 987 case Attribute::StructRet: 988 case Attribute::SwiftError: 989 case Attribute::SwiftSelf: 990 case Attribute::SwiftAsync: 991 case Attribute::ZExt: 992 case Attribute::ImmArg: 993 case Attribute::ByRef: 994 case Attribute::WriteOnly: 995 case Attribute::Writable: 996 case Attribute::DeadOnUnwind: 997 case Attribute::Range: 998 case Attribute::Initializes: 999 // These are not really attributes. 1000 case Attribute::None: 1001 case Attribute::EndAttrKinds: 1002 case Attribute::EmptyKey: 1003 case Attribute::TombstoneKey: 1004 llvm_unreachable("Not a function attribute"); 1005 } 1006 1007 newFunction->addFnAttr(Attr); 1008 } 1009 1010 if (NumExitBlocks == 0) { 1011 // Mark the new function `noreturn` if applicable. Terminators which resume 1012 // exception propagation are treated as returning instructions. This is to 1013 // avoid inserting traps after calls to outlined functions which unwind. 1014 if (none_of(Blocks, [](const BasicBlock *BB) { 1015 const Instruction *Term = BB->getTerminator(); 1016 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term); 1017 })) 1018 newFunction->setDoesNotReturn(); 1019 } 1020 1021 newFunction->insert(newFunction->end(), newRootNode); 1022 1023 // Create scalar and aggregate iterators to name all of the arguments we 1024 // inserted. 1025 Function::arg_iterator ScalarAI = newFunction->arg_begin(); 1026 Function::arg_iterator AggAI = std::next(ScalarAI, NumScalarParams); 1027 1028 // Rewrite all users of the inputs in the extracted region to use the 1029 // arguments (or appropriate addressing into struct) instead. 1030 for (unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) { 1031 Value *RewriteVal; 1032 if (AggregateArgs && StructValues.contains(inputs[i])) { 1033 Value *Idx[2]; 1034 Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); 1035 Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), aggIdx); 1036 BasicBlock::iterator TI = newFunction->begin()->getTerminator()->getIterator(); 1037 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1038 StructTy, &*AggAI, Idx, "gep_" + inputs[i]->getName(), TI); 1039 RewriteVal = new LoadInst(StructTy->getElementType(aggIdx), GEP, 1040 "loadgep_" + inputs[i]->getName(), TI); 1041 ++aggIdx; 1042 } else 1043 RewriteVal = &*ScalarAI++; 1044 1045 std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end()); 1046 for (User *use : Users) 1047 if (Instruction *inst = dyn_cast<Instruction>(use)) 1048 if (Blocks.count(inst->getParent())) 1049 inst->replaceUsesOfWith(inputs[i], RewriteVal); 1050 } 1051 1052 // Set names for input and output arguments. 1053 if (NumScalarParams) { 1054 ScalarAI = newFunction->arg_begin(); 1055 for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++ScalarAI) 1056 if (!StructValues.contains(inputs[i])) 1057 ScalarAI->setName(inputs[i]->getName()); 1058 for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++ScalarAI) 1059 if (!StructValues.contains(outputs[i])) 1060 ScalarAI->setName(outputs[i]->getName() + ".out"); 1061 } 1062 1063 // Rewrite branches to basic blocks outside of the loop to new dummy blocks 1064 // within the new function. This must be done before we lose track of which 1065 // blocks were originally in the code region. 1066 std::vector<User *> Users(header->user_begin(), header->user_end()); 1067 for (auto &U : Users) 1068 // The BasicBlock which contains the branch is not in the region 1069 // modify the branch target to a new block 1070 if (Instruction *I = dyn_cast<Instruction>(U)) 1071 if (I->isTerminator() && I->getFunction() == oldFunction && 1072 !Blocks.count(I->getParent())) 1073 I->replaceUsesOfWith(header, newHeader); 1074 1075 return newFunction; 1076 } 1077 1078 /// Erase lifetime.start markers which reference inputs to the extraction 1079 /// region, and insert the referenced memory into \p LifetimesStart. 1080 /// 1081 /// The extraction region is defined by a set of blocks (\p Blocks), and a set 1082 /// of allocas which will be moved from the caller function into the extracted 1083 /// function (\p SunkAllocas). 1084 static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks, 1085 const SetVector<Value *> &SunkAllocas, 1086 SetVector<Value *> &LifetimesStart) { 1087 for (BasicBlock *BB : Blocks) { 1088 for (Instruction &I : llvm::make_early_inc_range(*BB)) { 1089 auto *II = dyn_cast<IntrinsicInst>(&I); 1090 if (!II || !II->isLifetimeStartOrEnd()) 1091 continue; 1092 1093 // Get the memory operand of the lifetime marker. If the underlying 1094 // object is a sunk alloca, or is otherwise defined in the extraction 1095 // region, the lifetime marker must not be erased. 1096 Value *Mem = II->getOperand(1)->stripInBoundsOffsets(); 1097 if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem)) 1098 continue; 1099 1100 if (II->getIntrinsicID() == Intrinsic::lifetime_start) 1101 LifetimesStart.insert(Mem); 1102 II->eraseFromParent(); 1103 } 1104 } 1105 } 1106 1107 /// Insert lifetime start/end markers surrounding the call to the new function 1108 /// for objects defined in the caller. 1109 static void insertLifetimeMarkersSurroundingCall( 1110 Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd, 1111 CallInst *TheCall) { 1112 LLVMContext &Ctx = M->getContext(); 1113 auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1); 1114 Instruction *Term = TheCall->getParent()->getTerminator(); 1115 1116 // Emit lifetime markers for the pointers given in \p Objects. Insert the 1117 // markers before the call if \p InsertBefore, and after the call otherwise. 1118 auto insertMarkers = [&](Intrinsic::ID MarkerFunc, ArrayRef<Value *> Objects, 1119 bool InsertBefore) { 1120 for (Value *Mem : Objects) { 1121 assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == 1122 TheCall->getFunction()) && 1123 "Input memory not defined in original function"); 1124 1125 Function *Func = Intrinsic::getDeclaration(M, MarkerFunc, Mem->getType()); 1126 auto Marker = CallInst::Create(Func, {NegativeOne, Mem}); 1127 if (InsertBefore) 1128 Marker->insertBefore(TheCall); 1129 else 1130 Marker->insertBefore(Term); 1131 } 1132 }; 1133 1134 if (!LifetimesStart.empty()) { 1135 insertMarkers(Intrinsic::lifetime_start, LifetimesStart, 1136 /*InsertBefore=*/true); 1137 } 1138 1139 if (!LifetimesEnd.empty()) { 1140 insertMarkers(Intrinsic::lifetime_end, LifetimesEnd, 1141 /*InsertBefore=*/false); 1142 } 1143 } 1144 1145 /// emitCallAndSwitchStatement - This method sets up the caller side by adding 1146 /// the call instruction, splitting any PHI nodes in the header block as 1147 /// necessary. 1148 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction, 1149 BasicBlock *codeReplacer, 1150 ValueSet &inputs, 1151 ValueSet &outputs) { 1152 // Emit a call to the new function, passing in: *pointer to struct (if 1153 // aggregating parameters), or plan inputs and allocated memory for outputs 1154 std::vector<Value *> params, ReloadOutputs, Reloads; 1155 ValueSet StructValues; 1156 1157 Module *M = newFunction->getParent(); 1158 LLVMContext &Context = M->getContext(); 1159 const DataLayout &DL = M->getDataLayout(); 1160 CallInst *call = nullptr; 1161 1162 // Add inputs as params, or to be filled into the struct 1163 unsigned ScalarInputArgNo = 0; 1164 SmallVector<unsigned, 1> SwiftErrorArgs; 1165 for (Value *input : inputs) { 1166 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(input)) 1167 StructValues.insert(input); 1168 else { 1169 params.push_back(input); 1170 if (input->isSwiftError()) 1171 SwiftErrorArgs.push_back(ScalarInputArgNo); 1172 } 1173 ++ScalarInputArgNo; 1174 } 1175 1176 // Create allocas for the outputs 1177 unsigned ScalarOutputArgNo = 0; 1178 for (Value *output : outputs) { 1179 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) { 1180 StructValues.insert(output); 1181 } else { 1182 AllocaInst *alloca = 1183 new AllocaInst(output->getType(), DL.getAllocaAddrSpace(), 1184 nullptr, output->getName() + ".loc", 1185 codeReplacer->getParent()->front().begin()); 1186 ReloadOutputs.push_back(alloca); 1187 params.push_back(alloca); 1188 ++ScalarOutputArgNo; 1189 } 1190 } 1191 1192 StructType *StructArgTy = nullptr; 1193 AllocaInst *Struct = nullptr; 1194 unsigned NumAggregatedInputs = 0; 1195 if (AggregateArgs && !StructValues.empty()) { 1196 std::vector<Type *> ArgTypes; 1197 for (Value *V : StructValues) 1198 ArgTypes.push_back(V->getType()); 1199 1200 // Allocate a struct at the beginning of this function 1201 StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); 1202 Struct = new AllocaInst( 1203 StructArgTy, DL.getAllocaAddrSpace(), nullptr, "structArg", 1204 AllocationBlock ? AllocationBlock->getFirstInsertionPt() 1205 : codeReplacer->getParent()->front().begin()); 1206 1207 if (ArgsInZeroAddressSpace && DL.getAllocaAddrSpace() != 0) { 1208 auto *StructSpaceCast = new AddrSpaceCastInst( 1209 Struct, PointerType ::get(Context, 0), "structArg.ascast"); 1210 StructSpaceCast->insertAfter(Struct); 1211 params.push_back(StructSpaceCast); 1212 } else { 1213 params.push_back(Struct); 1214 } 1215 // Store aggregated inputs in the struct. 1216 for (unsigned i = 0, e = StructValues.size(); i != e; ++i) { 1217 if (inputs.contains(StructValues[i])) { 1218 Value *Idx[2]; 1219 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1220 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); 1221 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1222 StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); 1223 GEP->insertInto(codeReplacer, codeReplacer->end()); 1224 new StoreInst(StructValues[i], GEP, codeReplacer); 1225 NumAggregatedInputs++; 1226 } 1227 } 1228 } 1229 1230 // Emit the call to the function 1231 call = CallInst::Create(newFunction, params, 1232 NumExitBlocks > 1 ? "targetBlock" : ""); 1233 // Add debug location to the new call, if the original function has debug 1234 // info. In that case, the terminator of the entry block of the extracted 1235 // function contains the first debug location of the extracted function, 1236 // set in extractCodeRegion. 1237 if (codeReplacer->getParent()->getSubprogram()) { 1238 if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc()) 1239 call->setDebugLoc(DL); 1240 } 1241 call->insertInto(codeReplacer, codeReplacer->end()); 1242 1243 // Set swifterror parameter attributes. 1244 for (unsigned SwiftErrArgNo : SwiftErrorArgs) { 1245 call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1246 newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1247 } 1248 1249 // Reload the outputs passed in by reference, use the struct if output is in 1250 // the aggregate or reload from the scalar argument. 1251 for (unsigned i = 0, e = outputs.size(), scalarIdx = 0, 1252 aggIdx = NumAggregatedInputs; 1253 i != e; ++i) { 1254 Value *Output = nullptr; 1255 if (AggregateArgs && StructValues.contains(outputs[i])) { 1256 Value *Idx[2]; 1257 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1258 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx); 1259 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1260 StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); 1261 GEP->insertInto(codeReplacer, codeReplacer->end()); 1262 Output = GEP; 1263 ++aggIdx; 1264 } else { 1265 Output = ReloadOutputs[scalarIdx]; 1266 ++scalarIdx; 1267 } 1268 LoadInst *load = new LoadInst(outputs[i]->getType(), Output, 1269 outputs[i]->getName() + ".reload", 1270 codeReplacer); 1271 Reloads.push_back(load); 1272 std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end()); 1273 for (User *U : Users) { 1274 Instruction *inst = cast<Instruction>(U); 1275 if (!Blocks.count(inst->getParent())) 1276 inst->replaceUsesOfWith(outputs[i], load); 1277 } 1278 } 1279 1280 // Now we can emit a switch statement using the call as a value. 1281 SwitchInst *TheSwitch = 1282 SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), 1283 codeReplacer, 0, codeReplacer); 1284 1285 // Since there may be multiple exits from the original region, make the new 1286 // function return an unsigned, switch on that number. This loop iterates 1287 // over all of the blocks in the extracted region, updating any terminator 1288 // instructions in the to-be-extracted region that branch to blocks that are 1289 // not in the region to be extracted. 1290 std::map<BasicBlock *, BasicBlock *> ExitBlockMap; 1291 1292 // Iterate over the previously collected targets, and create new blocks inside 1293 // the function to branch to. 1294 unsigned switchVal = 0; 1295 for (BasicBlock *OldTarget : OldTargets) { 1296 if (Blocks.count(OldTarget)) 1297 continue; 1298 BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 1299 if (NewTarget) 1300 continue; 1301 1302 // If we don't already have an exit stub for this non-extracted 1303 // destination, create one now! 1304 NewTarget = BasicBlock::Create(Context, 1305 OldTarget->getName() + ".exitStub", 1306 newFunction); 1307 unsigned SuccNum = switchVal++; 1308 1309 Value *brVal = nullptr; 1310 assert(NumExitBlocks < 0xffff && "too many exit blocks for switch"); 1311 switch (NumExitBlocks) { 1312 case 0: 1313 case 1: break; // No value needed. 1314 case 2: // Conditional branch, return a bool 1315 brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); 1316 break; 1317 default: 1318 brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); 1319 break; 1320 } 1321 1322 ReturnInst::Create(Context, brVal, NewTarget); 1323 1324 // Update the switch instruction. 1325 TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), 1326 SuccNum), 1327 OldTarget); 1328 } 1329 1330 for (BasicBlock *Block : Blocks) { 1331 Instruction *TI = Block->getTerminator(); 1332 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 1333 if (Blocks.count(TI->getSuccessor(i))) 1334 continue; 1335 BasicBlock *OldTarget = TI->getSuccessor(i); 1336 // add a new basic block which returns the appropriate value 1337 BasicBlock *NewTarget = ExitBlockMap[OldTarget]; 1338 assert(NewTarget && "Unknown target block!"); 1339 1340 // rewrite the original branch instruction with this new target 1341 TI->setSuccessor(i, NewTarget); 1342 } 1343 } 1344 1345 // Store the arguments right after the definition of output value. 1346 // This should be proceeded after creating exit stubs to be ensure that invoke 1347 // result restore will be placed in the outlined function. 1348 Function::arg_iterator ScalarOutputArgBegin = newFunction->arg_begin(); 1349 std::advance(ScalarOutputArgBegin, ScalarInputArgNo); 1350 Function::arg_iterator AggOutputArgBegin = newFunction->arg_begin(); 1351 std::advance(AggOutputArgBegin, ScalarInputArgNo + ScalarOutputArgNo); 1352 1353 for (unsigned i = 0, e = outputs.size(), aggIdx = NumAggregatedInputs; i != e; 1354 ++i) { 1355 auto *OutI = dyn_cast<Instruction>(outputs[i]); 1356 if (!OutI) 1357 continue; 1358 1359 // Find proper insertion point. 1360 BasicBlock::iterator InsertPt; 1361 // In case OutI is an invoke, we insert the store at the beginning in the 1362 // 'normal destination' BB. Otherwise we insert the store right after OutI. 1363 if (auto *InvokeI = dyn_cast<InvokeInst>(OutI)) 1364 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt(); 1365 else if (auto *Phi = dyn_cast<PHINode>(OutI)) 1366 InsertPt = Phi->getParent()->getFirstInsertionPt(); 1367 else 1368 InsertPt = std::next(OutI->getIterator()); 1369 1370 assert((InsertPt->getFunction() == newFunction || 1371 Blocks.count(InsertPt->getParent())) && 1372 "InsertPt should be in new function"); 1373 if (AggregateArgs && StructValues.contains(outputs[i])) { 1374 assert(AggOutputArgBegin != newFunction->arg_end() && 1375 "Number of aggregate output arguments should match " 1376 "the number of defined values"); 1377 Value *Idx[2]; 1378 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1379 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx); 1380 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1381 StructArgTy, &*AggOutputArgBegin, Idx, "gep_" + outputs[i]->getName(), 1382 InsertPt); 1383 new StoreInst(outputs[i], GEP, InsertPt); 1384 ++aggIdx; 1385 // Since there should be only one struct argument aggregating 1386 // all the output values, we shouldn't increment AggOutputArgBegin, which 1387 // always points to the struct argument, in this case. 1388 } else { 1389 assert(ScalarOutputArgBegin != newFunction->arg_end() && 1390 "Number of scalar output arguments should match " 1391 "the number of defined values"); 1392 new StoreInst(outputs[i], &*ScalarOutputArgBegin, InsertPt); 1393 ++ScalarOutputArgBegin; 1394 } 1395 } 1396 1397 // Now that we've done the deed, simplify the switch instruction. 1398 Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 1399 switch (NumExitBlocks) { 1400 case 0: 1401 // There are no successors (the block containing the switch itself), which 1402 // means that previously this was the last part of the function, and hence 1403 // this should be rewritten as a `ret` or `unreachable`. 1404 if (newFunction->doesNotReturn()) { 1405 // If fn is no return, end with an unreachable terminator. 1406 (void)new UnreachableInst(Context, TheSwitch->getIterator()); 1407 } else if (OldFnRetTy->isVoidTy()) { 1408 // We have no return value. 1409 ReturnInst::Create(Context, nullptr, 1410 TheSwitch->getIterator()); // Return void 1411 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 1412 // return what we have 1413 ReturnInst::Create(Context, TheSwitch->getCondition(), 1414 TheSwitch->getIterator()); 1415 } else { 1416 // Otherwise we must have code extracted an unwind or something, just 1417 // return whatever we want. 1418 ReturnInst::Create(Context, Constant::getNullValue(OldFnRetTy), 1419 TheSwitch->getIterator()); 1420 } 1421 1422 TheSwitch->eraseFromParent(); 1423 break; 1424 case 1: 1425 // Only a single destination, change the switch into an unconditional 1426 // branch. 1427 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getIterator()); 1428 TheSwitch->eraseFromParent(); 1429 break; 1430 case 2: 1431 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 1432 call, TheSwitch->getIterator()); 1433 TheSwitch->eraseFromParent(); 1434 break; 1435 default: 1436 // Otherwise, make the default destination of the switch instruction be one 1437 // of the other successors. 1438 TheSwitch->setCondition(call); 1439 TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); 1440 // Remove redundant case 1441 TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); 1442 break; 1443 } 1444 1445 // Insert lifetime markers around the reloads of any output values. The 1446 // allocas output values are stored in are only in-use in the codeRepl block. 1447 insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call); 1448 1449 return call; 1450 } 1451 1452 void CodeExtractor::moveCodeToFunction(Function *newFunction) { 1453 auto newFuncIt = newFunction->front().getIterator(); 1454 for (BasicBlock *Block : Blocks) { 1455 // Delete the basic block from the old function, and the list of blocks 1456 Block->removeFromParent(); 1457 1458 // Insert this basic block into the new function 1459 // Insert the original blocks after the entry block created 1460 // for the new function. The entry block may be followed 1461 // by a set of exit blocks at this point, but these exit 1462 // blocks better be placed at the end of the new function. 1463 newFuncIt = newFunction->insert(std::next(newFuncIt), Block); 1464 } 1465 } 1466 1467 void CodeExtractor::calculateNewCallTerminatorWeights( 1468 BasicBlock *CodeReplacer, 1469 DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 1470 BranchProbabilityInfo *BPI) { 1471 using Distribution = BlockFrequencyInfoImplBase::Distribution; 1472 using BlockNode = BlockFrequencyInfoImplBase::BlockNode; 1473 1474 // Update the branch weights for the exit block. 1475 Instruction *TI = CodeReplacer->getTerminator(); 1476 SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0); 1477 1478 // Block Frequency distribution with dummy node. 1479 Distribution BranchDist; 1480 1481 SmallVector<BranchProbability, 4> EdgeProbabilities( 1482 TI->getNumSuccessors(), BranchProbability::getUnknown()); 1483 1484 // Add each of the frequencies of the successors. 1485 for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { 1486 BlockNode ExitNode(i); 1487 uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency(); 1488 if (ExitFreq != 0) 1489 BranchDist.addExit(ExitNode, ExitFreq); 1490 else 1491 EdgeProbabilities[i] = BranchProbability::getZero(); 1492 } 1493 1494 // Check for no total weight. 1495 if (BranchDist.Total == 0) { 1496 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities); 1497 return; 1498 } 1499 1500 // Normalize the distribution so that they can fit in unsigned. 1501 BranchDist.normalize(); 1502 1503 // Create normalized branch weights and set the metadata. 1504 for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) { 1505 const auto &Weight = BranchDist.Weights[I]; 1506 1507 // Get the weight and update the current BFI. 1508 BranchWeights[Weight.TargetNode.Index] = Weight.Amount; 1509 BranchProbability BP(Weight.Amount, BranchDist.Total); 1510 EdgeProbabilities[Weight.TargetNode.Index] = BP; 1511 } 1512 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities); 1513 TI->setMetadata( 1514 LLVMContext::MD_prof, 1515 MDBuilder(TI->getContext()).createBranchWeights(BranchWeights)); 1516 } 1517 1518 /// Erase debug info intrinsics which refer to values in \p F but aren't in 1519 /// \p F. 1520 static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F) { 1521 for (Instruction &I : instructions(F)) { 1522 SmallVector<DbgVariableIntrinsic *, 4> DbgUsers; 1523 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords; 1524 findDbgUsers(DbgUsers, &I, &DbgVariableRecords); 1525 for (DbgVariableIntrinsic *DVI : DbgUsers) 1526 if (DVI->getFunction() != &F) 1527 DVI->eraseFromParent(); 1528 for (DbgVariableRecord *DVR : DbgVariableRecords) 1529 if (DVR->getFunction() != &F) 1530 DVR->eraseFromParent(); 1531 } 1532 } 1533 1534 /// Fix up the debug info in the old and new functions by pointing line 1535 /// locations and debug intrinsics to the new subprogram scope, and by deleting 1536 /// intrinsics which point to values outside of the new function. 1537 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc, 1538 CallInst &TheCall) { 1539 DISubprogram *OldSP = OldFunc.getSubprogram(); 1540 LLVMContext &Ctx = OldFunc.getContext(); 1541 1542 if (!OldSP) { 1543 // Erase any debug info the new function contains. 1544 stripDebugInfo(NewFunc); 1545 // Make sure the old function doesn't contain any non-local metadata refs. 1546 eraseDebugIntrinsicsWithNonLocalRefs(NewFunc); 1547 return; 1548 } 1549 1550 // Create a subprogram for the new function. Leave out a description of the 1551 // function arguments, as the parameters don't correspond to anything at the 1552 // source level. 1553 assert(OldSP->getUnit() && "Missing compile unit for subprogram"); 1554 DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false, 1555 OldSP->getUnit()); 1556 auto SPType = 1557 DIB.createSubroutineType(DIB.getOrCreateTypeArray(std::nullopt)); 1558 DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition | 1559 DISubprogram::SPFlagOptimized | 1560 DISubprogram::SPFlagLocalToUnit; 1561 auto NewSP = DIB.createFunction( 1562 OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(), 1563 /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags); 1564 NewFunc.setSubprogram(NewSP); 1565 1566 auto IsInvalidLocation = [&NewFunc](Value *Location) { 1567 // Location is invalid if it isn't a constant or an instruction, or is an 1568 // instruction but isn't in the new function. 1569 if (!Location || 1570 (!isa<Constant>(Location) && !isa<Instruction>(Location))) 1571 return true; 1572 Instruction *LocationInst = dyn_cast<Instruction>(Location); 1573 return LocationInst && LocationInst->getFunction() != &NewFunc; 1574 }; 1575 1576 // Debug intrinsics in the new function need to be updated in one of two 1577 // ways: 1578 // 1) They need to be deleted, because they describe a value in the old 1579 // function. 1580 // 2) They need to point to fresh metadata, e.g. because they currently 1581 // point to a variable in the wrong scope. 1582 SmallDenseMap<DINode *, DINode *> RemappedMetadata; 1583 SmallVector<Instruction *, 4> DebugIntrinsicsToDelete; 1584 SmallVector<DbgVariableRecord *, 4> DVRsToDelete; 1585 DenseMap<const MDNode *, MDNode *> Cache; 1586 1587 auto GetUpdatedDIVariable = [&](DILocalVariable *OldVar) { 1588 DINode *&NewVar = RemappedMetadata[OldVar]; 1589 if (!NewVar) { 1590 DILocalScope *NewScope = DILocalScope::cloneScopeForSubprogram( 1591 *OldVar->getScope(), *NewSP, Ctx, Cache); 1592 NewVar = DIB.createAutoVariable( 1593 NewScope, OldVar->getName(), OldVar->getFile(), OldVar->getLine(), 1594 OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero, 1595 OldVar->getAlignInBits()); 1596 } 1597 return cast<DILocalVariable>(NewVar); 1598 }; 1599 1600 auto UpdateDbgLabel = [&](auto *LabelRecord) { 1601 // Point the label record to a fresh label within the new function if 1602 // the record was not inlined from some other function. 1603 if (LabelRecord->getDebugLoc().getInlinedAt()) 1604 return; 1605 DILabel *OldLabel = LabelRecord->getLabel(); 1606 DINode *&NewLabel = RemappedMetadata[OldLabel]; 1607 if (!NewLabel) { 1608 DILocalScope *NewScope = DILocalScope::cloneScopeForSubprogram( 1609 *OldLabel->getScope(), *NewSP, Ctx, Cache); 1610 NewLabel = DILabel::get(Ctx, NewScope, OldLabel->getName(), 1611 OldLabel->getFile(), OldLabel->getLine()); 1612 } 1613 LabelRecord->setLabel(cast<DILabel>(NewLabel)); 1614 }; 1615 1616 auto UpdateDbgRecordsOnInst = [&](Instruction &I) -> void { 1617 for (DbgRecord &DR : I.getDbgRecordRange()) { 1618 if (DbgLabelRecord *DLR = dyn_cast<DbgLabelRecord>(&DR)) { 1619 UpdateDbgLabel(DLR); 1620 continue; 1621 } 1622 1623 DbgVariableRecord &DVR = cast<DbgVariableRecord>(DR); 1624 // Apply the two updates that dbg.values get: invalid operands, and 1625 // variable metadata fixup. 1626 if (any_of(DVR.location_ops(), IsInvalidLocation)) { 1627 DVRsToDelete.push_back(&DVR); 1628 continue; 1629 } 1630 if (DVR.isDbgAssign() && IsInvalidLocation(DVR.getAddress())) { 1631 DVRsToDelete.push_back(&DVR); 1632 continue; 1633 } 1634 if (!DVR.getDebugLoc().getInlinedAt()) 1635 DVR.setVariable(GetUpdatedDIVariable(DVR.getVariable())); 1636 } 1637 }; 1638 1639 for (Instruction &I : instructions(NewFunc)) { 1640 UpdateDbgRecordsOnInst(I); 1641 1642 auto *DII = dyn_cast<DbgInfoIntrinsic>(&I); 1643 if (!DII) 1644 continue; 1645 1646 // Point the intrinsic to a fresh label within the new function if the 1647 // intrinsic was not inlined from some other function. 1648 if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) { 1649 UpdateDbgLabel(DLI); 1650 continue; 1651 } 1652 1653 auto *DVI = cast<DbgVariableIntrinsic>(DII); 1654 // If any of the used locations are invalid, delete the intrinsic. 1655 if (any_of(DVI->location_ops(), IsInvalidLocation)) { 1656 DebugIntrinsicsToDelete.push_back(DVI); 1657 continue; 1658 } 1659 // DbgAssign intrinsics have an extra Value argument: 1660 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI); 1661 DAI && IsInvalidLocation(DAI->getAddress())) { 1662 DebugIntrinsicsToDelete.push_back(DVI); 1663 continue; 1664 } 1665 // If the variable was in the scope of the old function, i.e. it was not 1666 // inlined, point the intrinsic to a fresh variable within the new function. 1667 if (!DVI->getDebugLoc().getInlinedAt()) 1668 DVI->setVariable(GetUpdatedDIVariable(DVI->getVariable())); 1669 } 1670 1671 for (auto *DII : DebugIntrinsicsToDelete) 1672 DII->eraseFromParent(); 1673 for (auto *DVR : DVRsToDelete) 1674 DVR->getMarker()->MarkedInstr->dropOneDbgRecord(DVR); 1675 DIB.finalizeSubprogram(NewSP); 1676 1677 // Fix up the scope information attached to the line locations and the 1678 // debug assignment metadata in the new function. 1679 DenseMap<DIAssignID *, DIAssignID *> AssignmentIDMap; 1680 for (Instruction &I : instructions(NewFunc)) { 1681 if (const DebugLoc &DL = I.getDebugLoc()) 1682 I.setDebugLoc( 1683 DebugLoc::replaceInlinedAtSubprogram(DL, *NewSP, Ctx, Cache)); 1684 for (DbgRecord &DR : I.getDbgRecordRange()) 1685 DR.setDebugLoc(DebugLoc::replaceInlinedAtSubprogram(DR.getDebugLoc(), 1686 *NewSP, Ctx, Cache)); 1687 1688 // Loop info metadata may contain line locations. Fix them up. 1689 auto updateLoopInfoLoc = [&Ctx, &Cache, NewSP](Metadata *MD) -> Metadata * { 1690 if (auto *Loc = dyn_cast_or_null<DILocation>(MD)) 1691 return DebugLoc::replaceInlinedAtSubprogram(Loc, *NewSP, Ctx, Cache); 1692 return MD; 1693 }; 1694 updateLoopMetadataDebugLocations(I, updateLoopInfoLoc); 1695 at::remapAssignID(AssignmentIDMap, I); 1696 } 1697 if (!TheCall.getDebugLoc()) 1698 TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP)); 1699 1700 eraseDebugIntrinsicsWithNonLocalRefs(NewFunc); 1701 } 1702 1703 Function * 1704 CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) { 1705 ValueSet Inputs, Outputs; 1706 return extractCodeRegion(CEAC, Inputs, Outputs); 1707 } 1708 1709 Function * 1710 CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC, 1711 ValueSet &inputs, ValueSet &outputs) { 1712 if (!isEligible()) 1713 return nullptr; 1714 1715 // Assumption: this is a single-entry code region, and the header is the first 1716 // block in the region. 1717 BasicBlock *header = *Blocks.begin(); 1718 Function *oldFunction = header->getParent(); 1719 1720 // Calculate the entry frequency of the new function before we change the root 1721 // block. 1722 BlockFrequency EntryFreq; 1723 if (BFI) { 1724 assert(BPI && "Both BPI and BFI are required to preserve profile info"); 1725 for (BasicBlock *Pred : predecessors(header)) { 1726 if (Blocks.count(Pred)) 1727 continue; 1728 EntryFreq += 1729 BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header); 1730 } 1731 } 1732 1733 // Remove @llvm.assume calls that will be moved to the new function from the 1734 // old function's assumption cache. 1735 for (BasicBlock *Block : Blocks) { 1736 for (Instruction &I : llvm::make_early_inc_range(*Block)) { 1737 if (auto *AI = dyn_cast<AssumeInst>(&I)) { 1738 if (AC) 1739 AC->unregisterAssumption(AI); 1740 AI->eraseFromParent(); 1741 } 1742 } 1743 } 1744 1745 // If we have any return instructions in the region, split those blocks so 1746 // that the return is not in the region. 1747 splitReturnBlocks(); 1748 1749 // Calculate the exit blocks for the extracted region and the total exit 1750 // weights for each of those blocks. 1751 DenseMap<BasicBlock *, BlockFrequency> ExitWeights; 1752 SetVector<BasicBlock *> ExitBlocks; 1753 for (BasicBlock *Block : Blocks) { 1754 for (BasicBlock *Succ : successors(Block)) { 1755 if (!Blocks.count(Succ)) { 1756 // Update the branch weight for this successor. 1757 if (BFI) { 1758 BlockFrequency &BF = ExitWeights[Succ]; 1759 BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ); 1760 } 1761 ExitBlocks.insert(Succ); 1762 } 1763 } 1764 } 1765 NumExitBlocks = ExitBlocks.size(); 1766 1767 for (BasicBlock *Block : Blocks) { 1768 for (BasicBlock *OldTarget : successors(Block)) 1769 if (!Blocks.contains(OldTarget)) 1770 OldTargets.push_back(OldTarget); 1771 } 1772 1773 // If we have to split PHI nodes of the entry or exit blocks, do so now. 1774 severSplitPHINodesOfEntry(header); 1775 severSplitPHINodesOfExits(ExitBlocks); 1776 1777 // This takes place of the original loop 1778 BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), 1779 "codeRepl", oldFunction, 1780 header); 1781 codeReplacer->IsNewDbgInfoFormat = oldFunction->IsNewDbgInfoFormat; 1782 1783 // The new function needs a root node because other nodes can branch to the 1784 // head of the region, but the entry node of a function cannot have preds. 1785 BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 1786 "newFuncRoot"); 1787 newFuncRoot->IsNewDbgInfoFormat = oldFunction->IsNewDbgInfoFormat; 1788 1789 auto *BranchI = BranchInst::Create(header); 1790 // If the original function has debug info, we have to add a debug location 1791 // to the new branch instruction from the artificial entry block. 1792 // We use the debug location of the first instruction in the extracted 1793 // blocks, as there is no other equivalent line in the source code. 1794 if (oldFunction->getSubprogram()) { 1795 any_of(Blocks, [&BranchI](const BasicBlock *BB) { 1796 return any_of(*BB, [&BranchI](const Instruction &I) { 1797 if (!I.getDebugLoc()) 1798 return false; 1799 // Don't use source locations attached to debug-intrinsics: they could 1800 // be from completely unrelated scopes. 1801 if (isa<DbgInfoIntrinsic>(I)) 1802 return false; 1803 BranchI->setDebugLoc(I.getDebugLoc()); 1804 return true; 1805 }); 1806 }); 1807 } 1808 BranchI->insertInto(newFuncRoot, newFuncRoot->end()); 1809 1810 ValueSet SinkingCands, HoistingCands; 1811 BasicBlock *CommonExit = nullptr; 1812 findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit); 1813 assert(HoistingCands.empty() || CommonExit); 1814 1815 // Find inputs to, outputs from the code region. 1816 findInputsOutputs(inputs, outputs, SinkingCands); 1817 1818 // Now sink all instructions which only have non-phi uses inside the region. 1819 // Group the allocas at the start of the block, so that any bitcast uses of 1820 // the allocas are well-defined. 1821 AllocaInst *FirstSunkAlloca = nullptr; 1822 for (auto *II : SinkingCands) { 1823 if (auto *AI = dyn_cast<AllocaInst>(II)) { 1824 AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt()); 1825 if (!FirstSunkAlloca) 1826 FirstSunkAlloca = AI; 1827 } 1828 } 1829 assert((SinkingCands.empty() || FirstSunkAlloca) && 1830 "Did not expect a sink candidate without any allocas"); 1831 for (auto *II : SinkingCands) { 1832 if (!isa<AllocaInst>(II)) { 1833 cast<Instruction>(II)->moveAfter(FirstSunkAlloca); 1834 } 1835 } 1836 1837 if (!HoistingCands.empty()) { 1838 auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit); 1839 Instruction *TI = HoistToBlock->getTerminator(); 1840 for (auto *II : HoistingCands) 1841 cast<Instruction>(II)->moveBefore(TI); 1842 } 1843 1844 // Collect objects which are inputs to the extraction region and also 1845 // referenced by lifetime start markers within it. The effects of these 1846 // markers must be replicated in the calling function to prevent the stack 1847 // coloring pass from merging slots which store input objects. 1848 ValueSet LifetimesStart; 1849 eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart); 1850 1851 // Construct new function based on inputs/outputs & add allocas for all defs. 1852 Function *newFunction = 1853 constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer, 1854 oldFunction, oldFunction->getParent()); 1855 1856 // Update the entry count of the function. 1857 if (BFI) { 1858 auto Count = BFI->getProfileCountFromFreq(EntryFreq); 1859 if (Count) 1860 newFunction->setEntryCount( 1861 ProfileCount(*Count, Function::PCT_Real)); // FIXME 1862 BFI->setBlockFreq(codeReplacer, EntryFreq); 1863 } 1864 1865 CallInst *TheCall = 1866 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 1867 1868 moveCodeToFunction(newFunction); 1869 1870 // Replicate the effects of any lifetime start/end markers which referenced 1871 // input objects in the extraction region by placing markers around the call. 1872 insertLifetimeMarkersSurroundingCall( 1873 oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall); 1874 1875 // Propagate personality info to the new function if there is one. 1876 if (oldFunction->hasPersonalityFn()) 1877 newFunction->setPersonalityFn(oldFunction->getPersonalityFn()); 1878 1879 // Update the branch weights for the exit block. 1880 if (BFI && NumExitBlocks > 1) 1881 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI); 1882 1883 // Loop over all of the PHI nodes in the header and exit blocks, and change 1884 // any references to the old incoming edge to be the new incoming edge. 1885 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 1886 PHINode *PN = cast<PHINode>(I); 1887 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1888 if (!Blocks.count(PN->getIncomingBlock(i))) 1889 PN->setIncomingBlock(i, newFuncRoot); 1890 } 1891 1892 for (BasicBlock *ExitBB : ExitBlocks) 1893 for (PHINode &PN : ExitBB->phis()) { 1894 Value *IncomingCodeReplacerVal = nullptr; 1895 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 1896 // Ignore incoming values from outside of the extracted region. 1897 if (!Blocks.count(PN.getIncomingBlock(i))) 1898 continue; 1899 1900 // Ensure that there is only one incoming value from codeReplacer. 1901 if (!IncomingCodeReplacerVal) { 1902 PN.setIncomingBlock(i, codeReplacer); 1903 IncomingCodeReplacerVal = PN.getIncomingValue(i); 1904 } else 1905 assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) && 1906 "PHI has two incompatbile incoming values from codeRepl"); 1907 } 1908 } 1909 1910 fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall); 1911 1912 LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) { 1913 newFunction->dump(); 1914 report_fatal_error("verification of newFunction failed!"); 1915 }); 1916 LLVM_DEBUG(if (verifyFunction(*oldFunction)) 1917 report_fatal_error("verification of oldFunction failed!")); 1918 LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC)) 1919 report_fatal_error("Stale Asumption cache for old Function!")); 1920 return newFunction; 1921 } 1922 1923 bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc, 1924 const Function &NewFunc, 1925 AssumptionCache *AC) { 1926 for (auto AssumeVH : AC->assumptions()) { 1927 auto *I = dyn_cast_or_null<CallInst>(AssumeVH); 1928 if (!I) 1929 continue; 1930 1931 // There shouldn't be any llvm.assume intrinsics in the new function. 1932 if (I->getFunction() != &OldFunc) 1933 return true; 1934 1935 // There shouldn't be any stale affected values in the assumption cache 1936 // that were previously in the old function, but that have now been moved 1937 // to the new function. 1938 for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) { 1939 auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH); 1940 if (!AffectedCI) 1941 continue; 1942 if (AffectedCI->getFunction() != &OldFunc) 1943 return true; 1944 auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0)); 1945 if (AssumedInst->getFunction() != &OldFunc) 1946 return true; 1947 } 1948 } 1949 return false; 1950 } 1951 1952 void CodeExtractor::excludeArgFromAggregate(Value *Arg) { 1953 ExcludeArgsFromAggregate.insert(Arg); 1954 } 1955