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/Optional.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallPtrSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/Analysis/AssumptionCache.h" 24 #include "llvm/Analysis/BlockFrequencyInfo.h" 25 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 26 #include "llvm/Analysis/BranchProbabilityInfo.h" 27 #include "llvm/Analysis/LoopInfo.h" 28 #include "llvm/IR/Argument.h" 29 #include "llvm/IR/Attributes.h" 30 #include "llvm/IR/BasicBlock.h" 31 #include "llvm/IR/CFG.h" 32 #include "llvm/IR/Constant.h" 33 #include "llvm/IR/Constants.h" 34 #include "llvm/IR/DataLayout.h" 35 #include "llvm/IR/DerivedTypes.h" 36 #include "llvm/IR/Dominators.h" 37 #include "llvm/IR/Function.h" 38 #include "llvm/IR/GlobalValue.h" 39 #include "llvm/IR/InstrTypes.h" 40 #include "llvm/IR/Instruction.h" 41 #include "llvm/IR/Instructions.h" 42 #include "llvm/IR/IntrinsicInst.h" 43 #include "llvm/IR/Intrinsics.h" 44 #include "llvm/IR/LLVMContext.h" 45 #include "llvm/IR/MDBuilder.h" 46 #include "llvm/IR/Module.h" 47 #include "llvm/IR/PatternMatch.h" 48 #include "llvm/IR/Type.h" 49 #include "llvm/IR/User.h" 50 #include "llvm/IR/Value.h" 51 #include "llvm/IR/Verifier.h" 52 #include "llvm/Pass.h" 53 #include "llvm/Support/BlockFrequency.h" 54 #include "llvm/Support/BranchProbability.h" 55 #include "llvm/Support/Casting.h" 56 #include "llvm/Support/CommandLine.h" 57 #include "llvm/Support/Debug.h" 58 #include "llvm/Support/ErrorHandling.h" 59 #include "llvm/Support/raw_ostream.h" 60 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 61 #include "llvm/Transforms/Utils/Local.h" 62 #include <cassert> 63 #include <cstdint> 64 #include <iterator> 65 #include <map> 66 #include <set> 67 #include <utility> 68 #include <vector> 69 70 using namespace llvm; 71 using namespace llvm::PatternMatch; 72 using ProfileCount = Function::ProfileCount; 73 74 #define DEBUG_TYPE "code-extractor" 75 76 // Provide a command-line option to aggregate function arguments into a struct 77 // for functions produced by the code extractor. This is useful when converting 78 // extracted functions to pthread-based code, as only one argument (void*) can 79 // be passed in to pthread_create(). 80 static cl::opt<bool> 81 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 82 cl::desc("Aggregate arguments to code-extracted functions")); 83 84 /// Test whether a block is valid for extraction. 85 static bool isBlockValidForExtraction(const BasicBlock &BB, 86 const SetVector<BasicBlock *> &Result, 87 bool AllowVarArgs, bool AllowAlloca) { 88 // taking the address of a basic block moved to another function is illegal 89 if (BB.hasAddressTaken()) 90 return false; 91 92 // don't hoist code that uses another basicblock address, as it's likely to 93 // lead to unexpected behavior, like cross-function jumps 94 SmallPtrSet<User const *, 16> Visited; 95 SmallVector<User const *, 16> ToVisit; 96 97 for (Instruction const &Inst : BB) 98 ToVisit.push_back(&Inst); 99 100 while (!ToVisit.empty()) { 101 User const *Curr = ToVisit.pop_back_val(); 102 if (!Visited.insert(Curr).second) 103 continue; 104 if (isa<BlockAddress const>(Curr)) 105 return false; // even a reference to self is likely to be not compatible 106 107 if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB) 108 continue; 109 110 for (auto const &U : Curr->operands()) { 111 if (auto *UU = dyn_cast<User>(U)) 112 ToVisit.push_back(UU); 113 } 114 } 115 116 // If explicitly requested, allow vastart and alloca. For invoke instructions 117 // verify that extraction is valid. 118 for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { 119 if (isa<AllocaInst>(I)) { 120 if (!AllowAlloca) 121 return false; 122 continue; 123 } 124 125 if (const auto *II = dyn_cast<InvokeInst>(I)) { 126 // Unwind destination (either a landingpad, catchswitch, or cleanuppad) 127 // must be a part of the subgraph which is being extracted. 128 if (auto *UBB = II->getUnwindDest()) 129 if (!Result.count(UBB)) 130 return false; 131 continue; 132 } 133 134 // All catch handlers of a catchswitch instruction as well as the unwind 135 // destination must be in the subgraph. 136 if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) { 137 if (auto *UBB = CSI->getUnwindDest()) 138 if (!Result.count(UBB)) 139 return false; 140 for (auto *HBB : CSI->handlers()) 141 if (!Result.count(const_cast<BasicBlock*>(HBB))) 142 return false; 143 continue; 144 } 145 146 // Make sure that entire catch handler is within subgraph. It is sufficient 147 // to check that catch return's block is in the list. 148 if (const auto *CPI = dyn_cast<CatchPadInst>(I)) { 149 for (const auto *U : CPI->users()) 150 if (const auto *CRI = dyn_cast<CatchReturnInst>(U)) 151 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) 152 return false; 153 continue; 154 } 155 156 // And do similar checks for cleanup handler - the entire handler must be 157 // in subgraph which is going to be extracted. For cleanup return should 158 // additionally check that the unwind destination is also in the subgraph. 159 if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) { 160 for (const auto *U : CPI->users()) 161 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U)) 162 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) 163 return false; 164 continue; 165 } 166 if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) { 167 if (auto *UBB = CRI->getUnwindDest()) 168 if (!Result.count(UBB)) 169 return false; 170 continue; 171 } 172 173 if (const CallInst *CI = dyn_cast<CallInst>(I)) { 174 if (const Function *F = CI->getCalledFunction()) { 175 auto IID = F->getIntrinsicID(); 176 if (IID == Intrinsic::vastart) { 177 if (AllowVarArgs) 178 continue; 179 else 180 return false; 181 } 182 183 // Currently, we miscompile outlined copies of eh_typid_for. There are 184 // proposals for fixing this in llvm.org/PR39545. 185 if (IID == Intrinsic::eh_typeid_for) 186 return false; 187 } 188 } 189 } 190 191 return true; 192 } 193 194 /// Build a set of blocks to extract if the input blocks are viable. 195 static SetVector<BasicBlock *> 196 buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 197 bool AllowVarArgs, bool AllowAlloca) { 198 assert(!BBs.empty() && "The set of blocks to extract must be non-empty"); 199 SetVector<BasicBlock *> Result; 200 201 // Loop over the blocks, adding them to our set-vector, and aborting with an 202 // empty set if we encounter invalid blocks. 203 for (BasicBlock *BB : BBs) { 204 // If this block is dead, don't process it. 205 if (DT && !DT->isReachableFromEntry(BB)) 206 continue; 207 208 if (!Result.insert(BB)) 209 llvm_unreachable("Repeated basic blocks in extraction input"); 210 } 211 212 LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName() 213 << '\n'); 214 215 for (auto *BB : Result) { 216 if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca)) 217 return {}; 218 219 // Make sure that the first block is not a landing pad. 220 if (BB == Result.front()) { 221 if (BB->isEHPad()) { 222 LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n"); 223 return {}; 224 } 225 continue; 226 } 227 228 // All blocks other than the first must not have predecessors outside of 229 // the subgraph which is being extracted. 230 for (auto *PBB : predecessors(BB)) 231 if (!Result.count(PBB)) { 232 LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from " 233 "outside the region except for the first block!\n" 234 << "Problematic source BB: " << BB->getName() << "\n" 235 << "Problematic destination BB: " << PBB->getName() 236 << "\n"); 237 return {}; 238 } 239 } 240 241 return Result; 242 } 243 244 CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 245 bool AggregateArgs, BlockFrequencyInfo *BFI, 246 BranchProbabilityInfo *BPI, AssumptionCache *AC, 247 bool AllowVarArgs, bool AllowAlloca, 248 std::string Suffix) 249 : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), 250 BPI(BPI), AC(AC), AllowVarArgs(AllowVarArgs), 251 Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)), 252 Suffix(Suffix) {} 253 254 CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs, 255 BlockFrequencyInfo *BFI, 256 BranchProbabilityInfo *BPI, AssumptionCache *AC, 257 std::string Suffix) 258 : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), 259 BPI(BPI), AC(AC), AllowVarArgs(false), 260 Blocks(buildExtractionBlockSet(L.getBlocks(), &DT, 261 /* AllowVarArgs */ false, 262 /* AllowAlloca */ false)), 263 Suffix(Suffix) {} 264 265 /// definedInRegion - Return true if the specified value is defined in the 266 /// extracted region. 267 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { 268 if (Instruction *I = dyn_cast<Instruction>(V)) 269 if (Blocks.count(I->getParent())) 270 return true; 271 return false; 272 } 273 274 /// definedInCaller - Return true if the specified value is defined in the 275 /// function being code extracted, but not in the region being extracted. 276 /// These values must be passed in as live-ins to the function. 277 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { 278 if (isa<Argument>(V)) return true; 279 if (Instruction *I = dyn_cast<Instruction>(V)) 280 if (!Blocks.count(I->getParent())) 281 return true; 282 return false; 283 } 284 285 static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) { 286 BasicBlock *CommonExitBlock = nullptr; 287 auto hasNonCommonExitSucc = [&](BasicBlock *Block) { 288 for (auto *Succ : successors(Block)) { 289 // Internal edges, ok. 290 if (Blocks.count(Succ)) 291 continue; 292 if (!CommonExitBlock) { 293 CommonExitBlock = Succ; 294 continue; 295 } 296 if (CommonExitBlock == Succ) 297 continue; 298 299 return true; 300 } 301 return false; 302 }; 303 304 if (any_of(Blocks, hasNonCommonExitSucc)) 305 return nullptr; 306 307 return CommonExitBlock; 308 } 309 310 bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers( 311 Instruction *Addr) const { 312 AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets()); 313 Function *Func = (*Blocks.begin())->getParent(); 314 for (BasicBlock &BB : *Func) { 315 if (Blocks.count(&BB)) 316 continue; 317 for (Instruction &II : BB) { 318 if (isa<DbgInfoIntrinsic>(II)) 319 continue; 320 321 unsigned Opcode = II.getOpcode(); 322 Value *MemAddr = nullptr; 323 switch (Opcode) { 324 case Instruction::Store: 325 case Instruction::Load: { 326 if (Opcode == Instruction::Store) { 327 StoreInst *SI = cast<StoreInst>(&II); 328 MemAddr = SI->getPointerOperand(); 329 } else { 330 LoadInst *LI = cast<LoadInst>(&II); 331 MemAddr = LI->getPointerOperand(); 332 } 333 // Global variable can not be aliased with locals. 334 if (dyn_cast<Constant>(MemAddr)) 335 break; 336 Value *Base = MemAddr->stripInBoundsConstantOffsets(); 337 if (!isa<AllocaInst>(Base) || Base == AI) 338 return false; 339 break; 340 } 341 default: { 342 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II); 343 if (IntrInst) { 344 if (IntrInst->isLifetimeStartOrEnd()) 345 break; 346 return false; 347 } 348 // Treat all the other cases conservatively if it has side effects. 349 if (II.mayHaveSideEffects()) 350 return false; 351 } 352 } 353 } 354 } 355 356 return true; 357 } 358 359 BasicBlock * 360 CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) { 361 BasicBlock *SinglePredFromOutlineRegion = nullptr; 362 assert(!Blocks.count(CommonExitBlock) && 363 "Expect a block outside the region!"); 364 for (auto *Pred : predecessors(CommonExitBlock)) { 365 if (!Blocks.count(Pred)) 366 continue; 367 if (!SinglePredFromOutlineRegion) { 368 SinglePredFromOutlineRegion = Pred; 369 } else if (SinglePredFromOutlineRegion != Pred) { 370 SinglePredFromOutlineRegion = nullptr; 371 break; 372 } 373 } 374 375 if (SinglePredFromOutlineRegion) 376 return SinglePredFromOutlineRegion; 377 378 #ifndef NDEBUG 379 auto getFirstPHI = [](BasicBlock *BB) { 380 BasicBlock::iterator I = BB->begin(); 381 PHINode *FirstPhi = nullptr; 382 while (I != BB->end()) { 383 PHINode *Phi = dyn_cast<PHINode>(I); 384 if (!Phi) 385 break; 386 if (!FirstPhi) { 387 FirstPhi = Phi; 388 break; 389 } 390 } 391 return FirstPhi; 392 }; 393 // If there are any phi nodes, the single pred either exists or has already 394 // be created before code extraction. 395 assert(!getFirstPHI(CommonExitBlock) && "Phi not expected"); 396 #endif 397 398 BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock( 399 CommonExitBlock->getFirstNonPHI()->getIterator()); 400 401 for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock); 402 PI != PE;) { 403 BasicBlock *Pred = *PI++; 404 if (Blocks.count(Pred)) 405 continue; 406 Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock); 407 } 408 // Now add the old exit block to the outline region. 409 Blocks.insert(CommonExitBlock); 410 return CommonExitBlock; 411 } 412 413 // Find the pair of life time markers for address 'Addr' that are either 414 // defined inside the outline region or can legally be shrinkwrapped into the 415 // outline region. If there are not other untracked uses of the address, return 416 // the pair of markers if found; otherwise return a pair of nullptr. 417 CodeExtractor::LifetimeMarkerInfo 418 CodeExtractor::getLifetimeMarkers(Instruction *Addr, 419 BasicBlock *ExitBlock) const { 420 LifetimeMarkerInfo Info; 421 422 for (User *U : Addr->users()) { 423 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U); 424 if (IntrInst) { 425 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) { 426 // Do not handle the case where Addr has multiple start markers. 427 if (Info.LifeStart) 428 return {}; 429 Info.LifeStart = IntrInst; 430 } 431 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) { 432 if (Info.LifeEnd) 433 return {}; 434 Info.LifeEnd = IntrInst; 435 } 436 continue; 437 } 438 // Find untracked uses of the address, bail. 439 if (!definedInRegion(Blocks, U)) 440 return {}; 441 } 442 443 if (!Info.LifeStart || !Info.LifeEnd) 444 return {}; 445 446 Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart); 447 Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd); 448 // Do legality check. 449 if ((Info.SinkLifeStart || Info.HoistLifeEnd) && 450 !isLegalToShrinkwrapLifetimeMarkers(Addr)) 451 return {}; 452 453 // Check to see if we have a place to do hoisting, if not, bail. 454 if (Info.HoistLifeEnd && !ExitBlock) 455 return {}; 456 457 return Info; 458 } 459 460 void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, 461 BasicBlock *&ExitBlock) const { 462 Function *Func = (*Blocks.begin())->getParent(); 463 ExitBlock = getCommonExitBlock(Blocks); 464 465 auto moveOrIgnoreLifetimeMarkers = 466 [&](const LifetimeMarkerInfo &LMI) -> bool { 467 if (!LMI.LifeStart) 468 return false; 469 if (LMI.SinkLifeStart) { 470 LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart 471 << "\n"); 472 SinkCands.insert(LMI.LifeStart); 473 } 474 if (LMI.HoistLifeEnd) { 475 LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n"); 476 HoistCands.insert(LMI.LifeEnd); 477 } 478 return true; 479 }; 480 481 for (BasicBlock &BB : *Func) { 482 if (Blocks.count(&BB)) 483 continue; 484 for (Instruction &II : BB) { 485 auto *AI = dyn_cast<AllocaInst>(&II); 486 if (!AI) 487 continue; 488 489 LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(AI, ExitBlock); 490 bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo); 491 if (Moved) { 492 LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n"); 493 SinkCands.insert(AI); 494 continue; 495 } 496 497 // Follow any bitcasts. 498 SmallVector<Instruction *, 2> Bitcasts; 499 SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo; 500 for (User *U : AI->users()) { 501 if (U->stripInBoundsConstantOffsets() == AI) { 502 Instruction *Bitcast = cast<Instruction>(U); 503 LifetimeMarkerInfo LMI = getLifetimeMarkers(Bitcast, ExitBlock); 504 if (LMI.LifeStart) { 505 Bitcasts.push_back(Bitcast); 506 BitcastLifetimeInfo.push_back(LMI); 507 continue; 508 } 509 } 510 511 // Found unknown use of AI. 512 if (!definedInRegion(Blocks, U)) { 513 Bitcasts.clear(); 514 break; 515 } 516 } 517 518 // Either no bitcasts reference the alloca or there are unknown uses. 519 if (Bitcasts.empty()) 520 continue; 521 522 LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n"); 523 SinkCands.insert(AI); 524 for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) { 525 Instruction *BitcastAddr = Bitcasts[I]; 526 const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I]; 527 assert(LMI.LifeStart && 528 "Unsafe to sink bitcast without lifetime markers"); 529 moveOrIgnoreLifetimeMarkers(LMI); 530 if (!definedInRegion(Blocks, BitcastAddr)) { 531 LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr 532 << "\n"); 533 SinkCands.insert(BitcastAddr); 534 } 535 } 536 } 537 } 538 } 539 540 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 541 const ValueSet &SinkCands) const { 542 for (BasicBlock *BB : Blocks) { 543 // If a used value is defined outside the region, it's an input. If an 544 // instruction is used outside the region, it's an output. 545 for (Instruction &II : *BB) { 546 for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE; 547 ++OI) { 548 Value *V = *OI; 549 if (!SinkCands.count(V) && definedInCaller(Blocks, V)) 550 Inputs.insert(V); 551 } 552 553 for (User *U : II.users()) 554 if (!definedInRegion(Blocks, U)) { 555 Outputs.insert(&II); 556 break; 557 } 558 } 559 } 560 } 561 562 /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside 563 /// of the region, we need to split the entry block of the region so that the 564 /// PHI node is easier to deal with. 565 void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) { 566 unsigned NumPredsFromRegion = 0; 567 unsigned NumPredsOutsideRegion = 0; 568 569 if (Header != &Header->getParent()->getEntryBlock()) { 570 PHINode *PN = dyn_cast<PHINode>(Header->begin()); 571 if (!PN) return; // No PHI nodes. 572 573 // If the header node contains any PHI nodes, check to see if there is more 574 // than one entry from outside the region. If so, we need to sever the 575 // header block into two. 576 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 577 if (Blocks.count(PN->getIncomingBlock(i))) 578 ++NumPredsFromRegion; 579 else 580 ++NumPredsOutsideRegion; 581 582 // If there is one (or fewer) predecessor from outside the region, we don't 583 // need to do anything special. 584 if (NumPredsOutsideRegion <= 1) return; 585 } 586 587 // Otherwise, we need to split the header block into two pieces: one 588 // containing PHI nodes merging values from outside of the region, and a 589 // second that contains all of the code for the block and merges back any 590 // incoming values from inside of the region. 591 BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT); 592 593 // We only want to code extract the second block now, and it becomes the new 594 // header of the region. 595 BasicBlock *OldPred = Header; 596 Blocks.remove(OldPred); 597 Blocks.insert(NewBB); 598 Header = NewBB; 599 600 // Okay, now we need to adjust the PHI nodes and any branches from within the 601 // region to go to the new header block instead of the old header block. 602 if (NumPredsFromRegion) { 603 PHINode *PN = cast<PHINode>(OldPred->begin()); 604 // Loop over all of the predecessors of OldPred that are in the region, 605 // changing them to branch to NewBB instead. 606 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 607 if (Blocks.count(PN->getIncomingBlock(i))) { 608 Instruction *TI = PN->getIncomingBlock(i)->getTerminator(); 609 TI->replaceUsesOfWith(OldPred, NewBB); 610 } 611 612 // Okay, everything within the region is now branching to the right block, we 613 // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 614 BasicBlock::iterator AfterPHIs; 615 for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 616 PHINode *PN = cast<PHINode>(AfterPHIs); 617 // Create a new PHI node in the new region, which has an incoming value 618 // from OldPred of PN. 619 PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, 620 PN->getName() + ".ce", &NewBB->front()); 621 PN->replaceAllUsesWith(NewPN); 622 NewPN->addIncoming(PN, OldPred); 623 624 // Loop over all of the incoming value in PN, moving them to NewPN if they 625 // are from the extracted region. 626 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 627 if (Blocks.count(PN->getIncomingBlock(i))) { 628 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 629 PN->removeIncomingValue(i); 630 --i; 631 } 632 } 633 } 634 } 635 } 636 637 /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from 638 /// outlined region, we split these PHIs on two: one with inputs from region 639 /// and other with remaining incoming blocks; then first PHIs are placed in 640 /// outlined region. 641 void CodeExtractor::severSplitPHINodesOfExits( 642 const SmallPtrSetImpl<BasicBlock *> &Exits) { 643 for (BasicBlock *ExitBB : Exits) { 644 BasicBlock *NewBB = nullptr; 645 646 for (PHINode &PN : ExitBB->phis()) { 647 // Find all incoming values from the outlining region. 648 SmallVector<unsigned, 2> IncomingVals; 649 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i) 650 if (Blocks.count(PN.getIncomingBlock(i))) 651 IncomingVals.push_back(i); 652 653 // Do not process PHI if there is one (or fewer) predecessor from region. 654 // If PHI has exactly one predecessor from region, only this one incoming 655 // will be replaced on codeRepl block, so it should be safe to skip PHI. 656 if (IncomingVals.size() <= 1) 657 continue; 658 659 // Create block for new PHIs and add it to the list of outlined if it 660 // wasn't done before. 661 if (!NewBB) { 662 NewBB = BasicBlock::Create(ExitBB->getContext(), 663 ExitBB->getName() + ".split", 664 ExitBB->getParent(), ExitBB); 665 SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB), 666 pred_end(ExitBB)); 667 for (BasicBlock *PredBB : Preds) 668 if (Blocks.count(PredBB)) 669 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB); 670 BranchInst::Create(ExitBB, NewBB); 671 Blocks.insert(NewBB); 672 } 673 674 // Split this PHI. 675 PHINode *NewPN = 676 PHINode::Create(PN.getType(), IncomingVals.size(), 677 PN.getName() + ".ce", NewBB->getFirstNonPHI()); 678 for (unsigned i : IncomingVals) 679 NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i)); 680 for (unsigned i : reverse(IncomingVals)) 681 PN.removeIncomingValue(i, false); 682 PN.addIncoming(NewPN, NewBB); 683 } 684 } 685 } 686 687 void CodeExtractor::splitReturnBlocks() { 688 for (BasicBlock *Block : Blocks) 689 if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) { 690 BasicBlock *New = 691 Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret"); 692 if (DT) { 693 // Old dominates New. New node dominates all other nodes dominated 694 // by Old. 695 DomTreeNode *OldNode = DT->getNode(Block); 696 SmallVector<DomTreeNode *, 8> Children(OldNode->begin(), 697 OldNode->end()); 698 699 DomTreeNode *NewNode = DT->addNewBlock(New, Block); 700 701 for (DomTreeNode *I : Children) 702 DT->changeImmediateDominator(I, NewNode); 703 } 704 } 705 } 706 707 /// constructFunction - make a function based on inputs and outputs, as follows: 708 /// f(in0, ..., inN, out0, ..., outN) 709 Function *CodeExtractor::constructFunction(const ValueSet &inputs, 710 const ValueSet &outputs, 711 BasicBlock *header, 712 BasicBlock *newRootNode, 713 BasicBlock *newHeader, 714 Function *oldFunction, 715 Module *M) { 716 LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n"); 717 LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n"); 718 719 // This function returns unsigned, outputs will go back by reference. 720 switch (NumExitBlocks) { 721 case 0: 722 case 1: RetTy = Type::getVoidTy(header->getContext()); break; 723 case 2: RetTy = Type::getInt1Ty(header->getContext()); break; 724 default: RetTy = Type::getInt16Ty(header->getContext()); break; 725 } 726 727 std::vector<Type *> paramTy; 728 729 // Add the types of the input values to the function's argument list 730 for (Value *value : inputs) { 731 LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n"); 732 paramTy.push_back(value->getType()); 733 } 734 735 // Add the types of the output values to the function's argument list. 736 for (Value *output : outputs) { 737 LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n"); 738 if (AggregateArgs) 739 paramTy.push_back(output->getType()); 740 else 741 paramTy.push_back(PointerType::getUnqual(output->getType())); 742 } 743 744 LLVM_DEBUG({ 745 dbgs() << "Function type: " << *RetTy << " f("; 746 for (Type *i : paramTy) 747 dbgs() << *i << ", "; 748 dbgs() << ")\n"; 749 }); 750 751 StructType *StructTy; 752 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 753 StructTy = StructType::get(M->getContext(), paramTy); 754 paramTy.clear(); 755 paramTy.push_back(PointerType::getUnqual(StructTy)); 756 } 757 FunctionType *funcType = 758 FunctionType::get(RetTy, paramTy, 759 AllowVarArgs && oldFunction->isVarArg()); 760 761 std::string SuffixToUse = 762 Suffix.empty() 763 ? (header->getName().empty() ? "extracted" : header->getName().str()) 764 : Suffix; 765 // Create the new function 766 Function *newFunction = Function::Create( 767 funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(), 768 oldFunction->getName() + "." + SuffixToUse, M); 769 // If the old function is no-throw, so is the new one. 770 if (oldFunction->doesNotThrow()) 771 newFunction->setDoesNotThrow(); 772 773 // Inherit the uwtable attribute if we need to. 774 if (oldFunction->hasUWTable()) 775 newFunction->setHasUWTable(); 776 777 // Inherit all of the target dependent attributes and white-listed 778 // target independent attributes. 779 // (e.g. If the extracted region contains a call to an x86.sse 780 // instruction we need to make sure that the extracted region has the 781 // "target-features" attribute allowing it to be lowered. 782 // FIXME: This should be changed to check to see if a specific 783 // attribute can not be inherited. 784 for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) { 785 if (Attr.isStringAttribute()) { 786 if (Attr.getKindAsString() == "thunk") 787 continue; 788 } else 789 switch (Attr.getKindAsEnum()) { 790 // Those attributes cannot be propagated safely. Explicitly list them 791 // here so we get a warning if new attributes are added. This list also 792 // includes non-function attributes. 793 case Attribute::Alignment: 794 case Attribute::AllocSize: 795 case Attribute::ArgMemOnly: 796 case Attribute::Builtin: 797 case Attribute::ByVal: 798 case Attribute::Convergent: 799 case Attribute::Dereferenceable: 800 case Attribute::DereferenceableOrNull: 801 case Attribute::InAlloca: 802 case Attribute::InReg: 803 case Attribute::InaccessibleMemOnly: 804 case Attribute::InaccessibleMemOrArgMemOnly: 805 case Attribute::JumpTable: 806 case Attribute::Naked: 807 case Attribute::Nest: 808 case Attribute::NoAlias: 809 case Attribute::NoBuiltin: 810 case Attribute::NoCapture: 811 case Attribute::NoReturn: 812 case Attribute::NoSync: 813 case Attribute::None: 814 case Attribute::NonNull: 815 case Attribute::ReadNone: 816 case Attribute::ReadOnly: 817 case Attribute::Returned: 818 case Attribute::ReturnsTwice: 819 case Attribute::SExt: 820 case Attribute::Speculatable: 821 case Attribute::StackAlignment: 822 case Attribute::StructRet: 823 case Attribute::SwiftError: 824 case Attribute::SwiftSelf: 825 case Attribute::WillReturn: 826 case Attribute::WriteOnly: 827 case Attribute::ZExt: 828 case Attribute::ImmArg: 829 case Attribute::EndAttrKinds: 830 continue; 831 // Those attributes should be safe to propagate to the extracted function. 832 case Attribute::AlwaysInline: 833 case Attribute::Cold: 834 case Attribute::NoRecurse: 835 case Attribute::InlineHint: 836 case Attribute::MinSize: 837 case Attribute::NoDuplicate: 838 case Attribute::NoFree: 839 case Attribute::NoImplicitFloat: 840 case Attribute::NoInline: 841 case Attribute::NonLazyBind: 842 case Attribute::NoRedZone: 843 case Attribute::NoUnwind: 844 case Attribute::OptForFuzzing: 845 case Attribute::OptimizeNone: 846 case Attribute::OptimizeForSize: 847 case Attribute::SafeStack: 848 case Attribute::ShadowCallStack: 849 case Attribute::SanitizeAddress: 850 case Attribute::SanitizeMemory: 851 case Attribute::SanitizeThread: 852 case Attribute::SanitizeHWAddress: 853 case Attribute::SanitizeMemTag: 854 case Attribute::SpeculativeLoadHardening: 855 case Attribute::StackProtect: 856 case Attribute::StackProtectReq: 857 case Attribute::StackProtectStrong: 858 case Attribute::StrictFP: 859 case Attribute::UWTable: 860 case Attribute::NoCfCheck: 861 break; 862 } 863 864 newFunction->addFnAttr(Attr); 865 } 866 newFunction->getBasicBlockList().push_back(newRootNode); 867 868 // Create an iterator to name all of the arguments we inserted. 869 Function::arg_iterator AI = newFunction->arg_begin(); 870 871 // Rewrite all users of the inputs in the extracted region to use the 872 // arguments (or appropriate addressing into struct) instead. 873 for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 874 Value *RewriteVal; 875 if (AggregateArgs) { 876 Value *Idx[2]; 877 Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); 878 Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); 879 Instruction *TI = newFunction->begin()->getTerminator(); 880 GetElementPtrInst *GEP = GetElementPtrInst::Create( 881 StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI); 882 RewriteVal = new LoadInst(StructTy->getElementType(i), GEP, 883 "loadgep_" + inputs[i]->getName(), TI); 884 } else 885 RewriteVal = &*AI++; 886 887 std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end()); 888 for (User *use : Users) 889 if (Instruction *inst = dyn_cast<Instruction>(use)) 890 if (Blocks.count(inst->getParent())) 891 inst->replaceUsesOfWith(inputs[i], RewriteVal); 892 } 893 894 // Set names for input and output arguments. 895 if (!AggregateArgs) { 896 AI = newFunction->arg_begin(); 897 for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 898 AI->setName(inputs[i]->getName()); 899 for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 900 AI->setName(outputs[i]->getName()+".out"); 901 } 902 903 // Rewrite branches to basic blocks outside of the loop to new dummy blocks 904 // within the new function. This must be done before we lose track of which 905 // blocks were originally in the code region. 906 std::vector<User *> Users(header->user_begin(), header->user_end()); 907 for (unsigned i = 0, e = Users.size(); i != e; ++i) 908 // The BasicBlock which contains the branch is not in the region 909 // modify the branch target to a new block 910 if (Instruction *I = dyn_cast<Instruction>(Users[i])) 911 if (I->isTerminator() && !Blocks.count(I->getParent()) && 912 I->getParent()->getParent() == oldFunction) 913 I->replaceUsesOfWith(header, newHeader); 914 915 return newFunction; 916 } 917 918 /// Erase lifetime.start markers which reference inputs to the extraction 919 /// region, and insert the referenced memory into \p LifetimesStart. 920 /// 921 /// The extraction region is defined by a set of blocks (\p Blocks), and a set 922 /// of allocas which will be moved from the caller function into the extracted 923 /// function (\p SunkAllocas). 924 static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks, 925 const SetVector<Value *> &SunkAllocas, 926 SetVector<Value *> &LifetimesStart) { 927 for (BasicBlock *BB : Blocks) { 928 for (auto It = BB->begin(), End = BB->end(); It != End;) { 929 auto *II = dyn_cast<IntrinsicInst>(&*It); 930 ++It; 931 if (!II || !II->isLifetimeStartOrEnd()) 932 continue; 933 934 // Get the memory operand of the lifetime marker. If the underlying 935 // object is a sunk alloca, or is otherwise defined in the extraction 936 // region, the lifetime marker must not be erased. 937 Value *Mem = II->getOperand(1)->stripInBoundsOffsets(); 938 if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem)) 939 continue; 940 941 if (II->getIntrinsicID() == Intrinsic::lifetime_start) 942 LifetimesStart.insert(Mem); 943 II->eraseFromParent(); 944 } 945 } 946 } 947 948 /// Insert lifetime start/end markers surrounding the call to the new function 949 /// for objects defined in the caller. 950 static void insertLifetimeMarkersSurroundingCall( 951 Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd, 952 CallInst *TheCall) { 953 LLVMContext &Ctx = M->getContext(); 954 auto Int8PtrTy = Type::getInt8PtrTy(Ctx); 955 auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1); 956 Instruction *Term = TheCall->getParent()->getTerminator(); 957 958 // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts 959 // needed to satisfy this requirement so they may be reused. 960 DenseMap<Value *, Value *> Bitcasts; 961 962 // Emit lifetime markers for the pointers given in \p Objects. Insert the 963 // markers before the call if \p InsertBefore, and after the call otherwise. 964 auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects, 965 bool InsertBefore) { 966 for (Value *Mem : Objects) { 967 assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == 968 TheCall->getFunction()) && 969 "Input memory not defined in original function"); 970 Value *&MemAsI8Ptr = Bitcasts[Mem]; 971 if (!MemAsI8Ptr) { 972 if (Mem->getType() == Int8PtrTy) 973 MemAsI8Ptr = Mem; 974 else 975 MemAsI8Ptr = 976 CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall); 977 } 978 979 auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr}); 980 if (InsertBefore) 981 Marker->insertBefore(TheCall); 982 else 983 Marker->insertBefore(Term); 984 } 985 }; 986 987 if (!LifetimesStart.empty()) { 988 auto StartFn = llvm::Intrinsic::getDeclaration( 989 M, llvm::Intrinsic::lifetime_start, Int8PtrTy); 990 insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true); 991 } 992 993 if (!LifetimesEnd.empty()) { 994 auto EndFn = llvm::Intrinsic::getDeclaration( 995 M, llvm::Intrinsic::lifetime_end, Int8PtrTy); 996 insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false); 997 } 998 } 999 1000 /// emitCallAndSwitchStatement - This method sets up the caller side by adding 1001 /// the call instruction, splitting any PHI nodes in the header block as 1002 /// necessary. 1003 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction, 1004 BasicBlock *codeReplacer, 1005 ValueSet &inputs, 1006 ValueSet &outputs) { 1007 // Emit a call to the new function, passing in: *pointer to struct (if 1008 // aggregating parameters), or plan inputs and allocated memory for outputs 1009 std::vector<Value *> params, StructValues, ReloadOutputs, Reloads; 1010 1011 Module *M = newFunction->getParent(); 1012 LLVMContext &Context = M->getContext(); 1013 const DataLayout &DL = M->getDataLayout(); 1014 CallInst *call = nullptr; 1015 1016 // Add inputs as params, or to be filled into the struct 1017 unsigned ArgNo = 0; 1018 SmallVector<unsigned, 1> SwiftErrorArgs; 1019 for (Value *input : inputs) { 1020 if (AggregateArgs) 1021 StructValues.push_back(input); 1022 else { 1023 params.push_back(input); 1024 if (input->isSwiftError()) 1025 SwiftErrorArgs.push_back(ArgNo); 1026 } 1027 ++ArgNo; 1028 } 1029 1030 // Create allocas for the outputs 1031 for (Value *output : outputs) { 1032 if (AggregateArgs) { 1033 StructValues.push_back(output); 1034 } else { 1035 AllocaInst *alloca = 1036 new AllocaInst(output->getType(), DL.getAllocaAddrSpace(), 1037 nullptr, output->getName() + ".loc", 1038 &codeReplacer->getParent()->front().front()); 1039 ReloadOutputs.push_back(alloca); 1040 params.push_back(alloca); 1041 } 1042 } 1043 1044 StructType *StructArgTy = nullptr; 1045 AllocaInst *Struct = nullptr; 1046 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 1047 std::vector<Type *> ArgTypes; 1048 for (ValueSet::iterator v = StructValues.begin(), 1049 ve = StructValues.end(); v != ve; ++v) 1050 ArgTypes.push_back((*v)->getType()); 1051 1052 // Allocate a struct at the beginning of this function 1053 StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); 1054 Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr, 1055 "structArg", 1056 &codeReplacer->getParent()->front().front()); 1057 params.push_back(Struct); 1058 1059 for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 1060 Value *Idx[2]; 1061 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1062 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); 1063 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1064 StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); 1065 codeReplacer->getInstList().push_back(GEP); 1066 StoreInst *SI = new StoreInst(StructValues[i], GEP); 1067 codeReplacer->getInstList().push_back(SI); 1068 } 1069 } 1070 1071 // Emit the call to the function 1072 call = CallInst::Create(newFunction, params, 1073 NumExitBlocks > 1 ? "targetBlock" : ""); 1074 // Add debug location to the new call, if the original function has debug 1075 // info. In that case, the terminator of the entry block of the extracted 1076 // function contains the first debug location of the extracted function, 1077 // set in extractCodeRegion. 1078 if (codeReplacer->getParent()->getSubprogram()) { 1079 if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc()) 1080 call->setDebugLoc(DL); 1081 } 1082 codeReplacer->getInstList().push_back(call); 1083 1084 // Set swifterror parameter attributes. 1085 for (unsigned SwiftErrArgNo : SwiftErrorArgs) { 1086 call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1087 newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1088 } 1089 1090 Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); 1091 unsigned FirstOut = inputs.size(); 1092 if (!AggregateArgs) 1093 std::advance(OutputArgBegin, inputs.size()); 1094 1095 // Reload the outputs passed in by reference. 1096 for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 1097 Value *Output = nullptr; 1098 if (AggregateArgs) { 1099 Value *Idx[2]; 1100 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1101 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 1102 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1103 StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); 1104 codeReplacer->getInstList().push_back(GEP); 1105 Output = GEP; 1106 } else { 1107 Output = ReloadOutputs[i]; 1108 } 1109 LoadInst *load = new LoadInst(outputs[i]->getType(), Output, 1110 outputs[i]->getName() + ".reload"); 1111 Reloads.push_back(load); 1112 codeReplacer->getInstList().push_back(load); 1113 std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end()); 1114 for (unsigned u = 0, e = Users.size(); u != e; ++u) { 1115 Instruction *inst = cast<Instruction>(Users[u]); 1116 if (!Blocks.count(inst->getParent())) 1117 inst->replaceUsesOfWith(outputs[i], load); 1118 } 1119 } 1120 1121 // Now we can emit a switch statement using the call as a value. 1122 SwitchInst *TheSwitch = 1123 SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), 1124 codeReplacer, 0, codeReplacer); 1125 1126 // Since there may be multiple exits from the original region, make the new 1127 // function return an unsigned, switch on that number. This loop iterates 1128 // over all of the blocks in the extracted region, updating any terminator 1129 // instructions in the to-be-extracted region that branch to blocks that are 1130 // not in the region to be extracted. 1131 std::map<BasicBlock *, BasicBlock *> ExitBlockMap; 1132 1133 unsigned switchVal = 0; 1134 for (BasicBlock *Block : Blocks) { 1135 Instruction *TI = Block->getTerminator(); 1136 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 1137 if (!Blocks.count(TI->getSuccessor(i))) { 1138 BasicBlock *OldTarget = TI->getSuccessor(i); 1139 // add a new basic block which returns the appropriate value 1140 BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 1141 if (!NewTarget) { 1142 // If we don't already have an exit stub for this non-extracted 1143 // destination, create one now! 1144 NewTarget = BasicBlock::Create(Context, 1145 OldTarget->getName() + ".exitStub", 1146 newFunction); 1147 unsigned SuccNum = switchVal++; 1148 1149 Value *brVal = nullptr; 1150 switch (NumExitBlocks) { 1151 case 0: 1152 case 1: break; // No value needed. 1153 case 2: // Conditional branch, return a bool 1154 brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); 1155 break; 1156 default: 1157 brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); 1158 break; 1159 } 1160 1161 ReturnInst::Create(Context, brVal, NewTarget); 1162 1163 // Update the switch instruction. 1164 TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), 1165 SuccNum), 1166 OldTarget); 1167 } 1168 1169 // rewrite the original branch instruction with this new target 1170 TI->setSuccessor(i, NewTarget); 1171 } 1172 } 1173 1174 // Store the arguments right after the definition of output value. 1175 // This should be proceeded after creating exit stubs to be ensure that invoke 1176 // result restore will be placed in the outlined function. 1177 Function::arg_iterator OAI = OutputArgBegin; 1178 for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 1179 auto *OutI = dyn_cast<Instruction>(outputs[i]); 1180 if (!OutI) 1181 continue; 1182 1183 // Find proper insertion point. 1184 BasicBlock::iterator InsertPt; 1185 // In case OutI is an invoke, we insert the store at the beginning in the 1186 // 'normal destination' BB. Otherwise we insert the store right after OutI. 1187 if (auto *InvokeI = dyn_cast<InvokeInst>(OutI)) 1188 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt(); 1189 else if (auto *Phi = dyn_cast<PHINode>(OutI)) 1190 InsertPt = Phi->getParent()->getFirstInsertionPt(); 1191 else 1192 InsertPt = std::next(OutI->getIterator()); 1193 1194 Instruction *InsertBefore = &*InsertPt; 1195 assert((InsertBefore->getFunction() == newFunction || 1196 Blocks.count(InsertBefore->getParent())) && 1197 "InsertPt should be in new function"); 1198 assert(OAI != newFunction->arg_end() && 1199 "Number of output arguments should match " 1200 "the amount of defined values"); 1201 if (AggregateArgs) { 1202 Value *Idx[2]; 1203 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1204 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 1205 GetElementPtrInst *GEP = GetElementPtrInst::Create( 1206 StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), 1207 InsertBefore); 1208 new StoreInst(outputs[i], GEP, InsertBefore); 1209 // Since there should be only one struct argument aggregating 1210 // all the output values, we shouldn't increment OAI, which always 1211 // points to the struct argument, in this case. 1212 } else { 1213 new StoreInst(outputs[i], &*OAI, InsertBefore); 1214 ++OAI; 1215 } 1216 } 1217 1218 // Now that we've done the deed, simplify the switch instruction. 1219 Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 1220 switch (NumExitBlocks) { 1221 case 0: 1222 // There are no successors (the block containing the switch itself), which 1223 // means that previously this was the last part of the function, and hence 1224 // this should be rewritten as a `ret' 1225 1226 // Check if the function should return a value 1227 if (OldFnRetTy->isVoidTy()) { 1228 ReturnInst::Create(Context, nullptr, TheSwitch); // Return void 1229 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 1230 // return what we have 1231 ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); 1232 } else { 1233 // Otherwise we must have code extracted an unwind or something, just 1234 // return whatever we want. 1235 ReturnInst::Create(Context, 1236 Constant::getNullValue(OldFnRetTy), TheSwitch); 1237 } 1238 1239 TheSwitch->eraseFromParent(); 1240 break; 1241 case 1: 1242 // Only a single destination, change the switch into an unconditional 1243 // branch. 1244 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); 1245 TheSwitch->eraseFromParent(); 1246 break; 1247 case 2: 1248 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 1249 call, TheSwitch); 1250 TheSwitch->eraseFromParent(); 1251 break; 1252 default: 1253 // Otherwise, make the default destination of the switch instruction be one 1254 // of the other successors. 1255 TheSwitch->setCondition(call); 1256 TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); 1257 // Remove redundant case 1258 TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); 1259 break; 1260 } 1261 1262 // Insert lifetime markers around the reloads of any output values. The 1263 // allocas output values are stored in are only in-use in the codeRepl block. 1264 insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call); 1265 1266 return call; 1267 } 1268 1269 void CodeExtractor::moveCodeToFunction(Function *newFunction) { 1270 Function *oldFunc = (*Blocks.begin())->getParent(); 1271 Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 1272 Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 1273 1274 for (BasicBlock *Block : Blocks) { 1275 // Delete the basic block from the old function, and the list of blocks 1276 oldBlocks.remove(Block); 1277 1278 // Insert this basic block into the new function 1279 newBlocks.push_back(Block); 1280 1281 // Remove @llvm.assume calls that were moved to the new function from the 1282 // old function's assumption cache. 1283 if (AC) 1284 for (auto &I : *Block) 1285 if (match(&I, m_Intrinsic<Intrinsic::assume>())) 1286 AC->unregisterAssumption(cast<CallInst>(&I)); 1287 } 1288 } 1289 1290 void CodeExtractor::calculateNewCallTerminatorWeights( 1291 BasicBlock *CodeReplacer, 1292 DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 1293 BranchProbabilityInfo *BPI) { 1294 using Distribution = BlockFrequencyInfoImplBase::Distribution; 1295 using BlockNode = BlockFrequencyInfoImplBase::BlockNode; 1296 1297 // Update the branch weights for the exit block. 1298 Instruction *TI = CodeReplacer->getTerminator(); 1299 SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0); 1300 1301 // Block Frequency distribution with dummy node. 1302 Distribution BranchDist; 1303 1304 // Add each of the frequencies of the successors. 1305 for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { 1306 BlockNode ExitNode(i); 1307 uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency(); 1308 if (ExitFreq != 0) 1309 BranchDist.addExit(ExitNode, ExitFreq); 1310 else 1311 BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero()); 1312 } 1313 1314 // Check for no total weight. 1315 if (BranchDist.Total == 0) 1316 return; 1317 1318 // Normalize the distribution so that they can fit in unsigned. 1319 BranchDist.normalize(); 1320 1321 // Create normalized branch weights and set the metadata. 1322 for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) { 1323 const auto &Weight = BranchDist.Weights[I]; 1324 1325 // Get the weight and update the current BFI. 1326 BranchWeights[Weight.TargetNode.Index] = Weight.Amount; 1327 BranchProbability BP(Weight.Amount, BranchDist.Total); 1328 BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP); 1329 } 1330 TI->setMetadata( 1331 LLVMContext::MD_prof, 1332 MDBuilder(TI->getContext()).createBranchWeights(BranchWeights)); 1333 } 1334 1335 Function *CodeExtractor::extractCodeRegion() { 1336 if (!isEligible()) 1337 return nullptr; 1338 1339 // Assumption: this is a single-entry code region, and the header is the first 1340 // block in the region. 1341 BasicBlock *header = *Blocks.begin(); 1342 Function *oldFunction = header->getParent(); 1343 1344 // For functions with varargs, check that varargs handling is only done in the 1345 // outlined function, i.e vastart and vaend are only used in outlined blocks. 1346 if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) { 1347 auto containsVarArgIntrinsic = [](Instruction &I) { 1348 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 1349 if (const Function *F = CI->getCalledFunction()) 1350 return F->getIntrinsicID() == Intrinsic::vastart || 1351 F->getIntrinsicID() == Intrinsic::vaend; 1352 return false; 1353 }; 1354 1355 for (auto &BB : *oldFunction) { 1356 if (Blocks.count(&BB)) 1357 continue; 1358 if (llvm::any_of(BB, containsVarArgIntrinsic)) 1359 return nullptr; 1360 } 1361 } 1362 ValueSet inputs, outputs, SinkingCands, HoistingCands; 1363 BasicBlock *CommonExit = nullptr; 1364 1365 // Calculate the entry frequency of the new function before we change the root 1366 // block. 1367 BlockFrequency EntryFreq; 1368 if (BFI) { 1369 assert(BPI && "Both BPI and BFI are required to preserve profile info"); 1370 for (BasicBlock *Pred : predecessors(header)) { 1371 if (Blocks.count(Pred)) 1372 continue; 1373 EntryFreq += 1374 BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header); 1375 } 1376 } 1377 1378 // If we have any return instructions in the region, split those blocks so 1379 // that the return is not in the region. 1380 splitReturnBlocks(); 1381 1382 // Calculate the exit blocks for the extracted region and the total exit 1383 // weights for each of those blocks. 1384 DenseMap<BasicBlock *, BlockFrequency> ExitWeights; 1385 SmallPtrSet<BasicBlock *, 1> ExitBlocks; 1386 for (BasicBlock *Block : Blocks) { 1387 for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE; 1388 ++SI) { 1389 if (!Blocks.count(*SI)) { 1390 // Update the branch weight for this successor. 1391 if (BFI) { 1392 BlockFrequency &BF = ExitWeights[*SI]; 1393 BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI); 1394 } 1395 ExitBlocks.insert(*SI); 1396 } 1397 } 1398 } 1399 NumExitBlocks = ExitBlocks.size(); 1400 1401 // If we have to split PHI nodes of the entry or exit blocks, do so now. 1402 severSplitPHINodesOfEntry(header); 1403 severSplitPHINodesOfExits(ExitBlocks); 1404 1405 // This takes place of the original loop 1406 BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), 1407 "codeRepl", oldFunction, 1408 header); 1409 1410 // The new function needs a root node because other nodes can branch to the 1411 // head of the region, but the entry node of a function cannot have preds. 1412 BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 1413 "newFuncRoot"); 1414 auto *BranchI = BranchInst::Create(header); 1415 // If the original function has debug info, we have to add a debug location 1416 // to the new branch instruction from the artificial entry block. 1417 // We use the debug location of the first instruction in the extracted 1418 // blocks, as there is no other equivalent line in the source code. 1419 if (oldFunction->getSubprogram()) { 1420 any_of(Blocks, [&BranchI](const BasicBlock *BB) { 1421 return any_of(*BB, [&BranchI](const Instruction &I) { 1422 if (!I.getDebugLoc()) 1423 return false; 1424 BranchI->setDebugLoc(I.getDebugLoc()); 1425 return true; 1426 }); 1427 }); 1428 } 1429 newFuncRoot->getInstList().push_back(BranchI); 1430 1431 findAllocas(SinkingCands, HoistingCands, CommonExit); 1432 assert(HoistingCands.empty() || CommonExit); 1433 1434 // Find inputs to, outputs from the code region. 1435 findInputsOutputs(inputs, outputs, SinkingCands); 1436 1437 // Now sink all instructions which only have non-phi uses inside the region. 1438 // Group the allocas at the start of the block, so that any bitcast uses of 1439 // the allocas are well-defined. 1440 AllocaInst *FirstSunkAlloca = nullptr; 1441 for (auto *II : SinkingCands) { 1442 if (auto *AI = dyn_cast<AllocaInst>(II)) { 1443 AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt()); 1444 if (!FirstSunkAlloca) 1445 FirstSunkAlloca = AI; 1446 } 1447 } 1448 assert((SinkingCands.empty() || FirstSunkAlloca) && 1449 "Did not expect a sink candidate without any allocas"); 1450 for (auto *II : SinkingCands) { 1451 if (!isa<AllocaInst>(II)) { 1452 cast<Instruction>(II)->moveAfter(FirstSunkAlloca); 1453 } 1454 } 1455 1456 if (!HoistingCands.empty()) { 1457 auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit); 1458 Instruction *TI = HoistToBlock->getTerminator(); 1459 for (auto *II : HoistingCands) 1460 cast<Instruction>(II)->moveBefore(TI); 1461 } 1462 1463 // Collect objects which are inputs to the extraction region and also 1464 // referenced by lifetime start markers within it. The effects of these 1465 // markers must be replicated in the calling function to prevent the stack 1466 // coloring pass from merging slots which store input objects. 1467 ValueSet LifetimesStart; 1468 eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart); 1469 1470 // Construct new function based on inputs/outputs & add allocas for all defs. 1471 Function *newFunction = 1472 constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer, 1473 oldFunction, oldFunction->getParent()); 1474 1475 // Update the entry count of the function. 1476 if (BFI) { 1477 auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency()); 1478 if (Count.hasValue()) 1479 newFunction->setEntryCount( 1480 ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME 1481 BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency()); 1482 } 1483 1484 CallInst *TheCall = 1485 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 1486 1487 moveCodeToFunction(newFunction); 1488 1489 // Replicate the effects of any lifetime start/end markers which referenced 1490 // input objects in the extraction region by placing markers around the call. 1491 insertLifetimeMarkersSurroundingCall( 1492 oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall); 1493 1494 // Propagate personality info to the new function if there is one. 1495 if (oldFunction->hasPersonalityFn()) 1496 newFunction->setPersonalityFn(oldFunction->getPersonalityFn()); 1497 1498 // Update the branch weights for the exit block. 1499 if (BFI && NumExitBlocks > 1) 1500 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI); 1501 1502 // Loop over all of the PHI nodes in the header and exit blocks, and change 1503 // any references to the old incoming edge to be the new incoming edge. 1504 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 1505 PHINode *PN = cast<PHINode>(I); 1506 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1507 if (!Blocks.count(PN->getIncomingBlock(i))) 1508 PN->setIncomingBlock(i, newFuncRoot); 1509 } 1510 1511 for (BasicBlock *ExitBB : ExitBlocks) 1512 for (PHINode &PN : ExitBB->phis()) { 1513 Value *IncomingCodeReplacerVal = nullptr; 1514 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 1515 // Ignore incoming values from outside of the extracted region. 1516 if (!Blocks.count(PN.getIncomingBlock(i))) 1517 continue; 1518 1519 // Ensure that there is only one incoming value from codeReplacer. 1520 if (!IncomingCodeReplacerVal) { 1521 PN.setIncomingBlock(i, codeReplacer); 1522 IncomingCodeReplacerVal = PN.getIncomingValue(i); 1523 } else 1524 assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) && 1525 "PHI has two incompatbile incoming values from codeRepl"); 1526 } 1527 } 1528 1529 // Erase debug info intrinsics. Variable updates within the new function are 1530 // invisible to debuggers. This could be improved by defining a DISubprogram 1531 // for the new function. 1532 for (BasicBlock &BB : *newFunction) { 1533 auto BlockIt = BB.begin(); 1534 // Remove debug info intrinsics from the new function. 1535 while (BlockIt != BB.end()) { 1536 Instruction *Inst = &*BlockIt; 1537 ++BlockIt; 1538 if (isa<DbgInfoIntrinsic>(Inst)) 1539 Inst->eraseFromParent(); 1540 } 1541 // Remove debug info intrinsics which refer to values in the new function 1542 // from the old function. 1543 SmallVector<DbgVariableIntrinsic *, 4> DbgUsers; 1544 for (Instruction &I : BB) 1545 findDbgUsers(DbgUsers, &I); 1546 for (DbgVariableIntrinsic *DVI : DbgUsers) 1547 DVI->eraseFromParent(); 1548 } 1549 1550 // Mark the new function `noreturn` if applicable. Terminators which resume 1551 // exception propagation are treated as returning instructions. This is to 1552 // avoid inserting traps after calls to outlined functions which unwind. 1553 bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) { 1554 const Instruction *Term = BB.getTerminator(); 1555 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term); 1556 }); 1557 if (doesNotReturn) 1558 newFunction->setDoesNotReturn(); 1559 1560 LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) { 1561 newFunction->dump(); 1562 report_fatal_error("verification of newFunction failed!"); 1563 }); 1564 LLVM_DEBUG(if (verifyFunction(*oldFunction)) 1565 report_fatal_error("verification of oldFunction failed!")); 1566 return newFunction; 1567 } 1568