2104 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the interface to tear out a code region, such as an10// individual loop or a parallel section, into a new function, replacing it with11// 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 <vector>67 68using namespace llvm;69using namespace llvm::PatternMatch;70using ProfileCount = Function::ProfileCount;71 72#define DEBUG_TYPE "code-extractor"73 74// Provide a command-line option to aggregate function arguments into a struct75// for functions produced by the code extractor. This is useful when converting76// extracted functions to pthread-based code, as only one argument (void*) can77// be passed in to pthread_create().78static cl::opt<bool>79AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,80 cl::desc("Aggregate arguments to code-extracted functions"));81 82/// Test whether a block is valid for extraction.83static bool isBlockValidForExtraction(const BasicBlock &BB,84 const SetVector<BasicBlock *> &Result,85 bool AllowVarArgs, bool AllowAlloca) {86 // taking the address of a basic block moved to another function is illegal87 if (BB.hasAddressTaken())88 return false;89 90 // don't hoist code that uses another basicblock address, as it's likely to91 // lead to unexpected behavior, like cross-function jumps92 SmallPtrSet<User const *, 16> Visited;93 SmallVector<User const *, 16> ToVisit(llvm::make_pointer_range(BB));94 95 while (!ToVisit.empty()) {96 User const *Curr = ToVisit.pop_back_val();97 if (!Visited.insert(Curr).second)98 continue;99 if (isa<BlockAddress const>(Curr))100 return false; // even a reference to self is likely to be not compatible101 102 if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)103 continue;104 105 for (auto const &U : Curr->operands()) {106 if (auto *UU = dyn_cast<User>(U))107 ToVisit.push_back(UU);108 }109 }110 111 // If explicitly requested, allow vastart and alloca. For invoke instructions112 // verify that extraction is valid.113 for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {114 if (isa<AllocaInst>(I)) {115 if (!AllowAlloca)116 return false;117 continue;118 }119 120 if (const auto *II = dyn_cast<InvokeInst>(I)) {121 // Unwind destination (either a landingpad, catchswitch, or cleanuppad)122 // must be a part of the subgraph which is being extracted.123 if (auto *UBB = II->getUnwindDest())124 if (!Result.count(UBB))125 return false;126 continue;127 }128 129 // All catch handlers of a catchswitch instruction as well as the unwind130 // destination must be in the subgraph.131 if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) {132 if (auto *UBB = CSI->getUnwindDest())133 if (!Result.count(UBB))134 return false;135 for (const auto *HBB : CSI->handlers())136 if (!Result.count(const_cast<BasicBlock*>(HBB)))137 return false;138 continue;139 }140 141 // Make sure that entire catch handler is within subgraph. It is sufficient142 // to check that catch return's block is in the list.143 if (const auto *CPI = dyn_cast<CatchPadInst>(I)) {144 for (const auto *U : CPI->users())145 if (const auto *CRI = dyn_cast<CatchReturnInst>(U))146 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))147 return false;148 continue;149 }150 151 // And do similar checks for cleanup handler - the entire handler must be152 // in subgraph which is going to be extracted. For cleanup return should153 // additionally check that the unwind destination is also in the subgraph.154 if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) {155 for (const auto *U : CPI->users())156 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))157 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))158 return false;159 continue;160 }161 if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) {162 if (auto *UBB = CRI->getUnwindDest())163 if (!Result.count(UBB))164 return false;165 continue;166 }167 168 if (const CallInst *CI = dyn_cast<CallInst>(I)) {169 // musttail calls have several restrictions, generally enforcing matching170 // calling conventions between the caller parent and musttail callee.171 // We can't usually honor them, because the extracted function has a172 // different signature altogether, taking inputs/outputs and returning173 // a control-flow identifier rather than the actual return value.174 if (CI->isMustTailCall())175 return false;176 177 if (const Function *F = CI->getCalledFunction()) {178 auto IID = F->getIntrinsicID();179 if (IID == Intrinsic::vastart) {180 if (AllowVarArgs)181 continue;182 else183 return false;184 }185 186 // Currently, we miscompile outlined copies of eh_typid_for. There are187 // proposals for fixing this in llvm.org/PR39545.188 if (IID == Intrinsic::eh_typeid_for)189 return false;190 }191 }192 }193 194 return true;195}196 197/// Build a set of blocks to extract if the input blocks are viable.198static SetVector<BasicBlock *>199buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,200 bool AllowVarArgs, bool AllowAlloca) {201 assert(!BBs.empty() && "The set of blocks to extract must be non-empty");202 SetVector<BasicBlock *> Result;203 204 // Loop over the blocks, adding them to our set-vector, and aborting with an205 // empty set if we encounter invalid blocks.206 for (BasicBlock *BB : BBs) {207 // If this block is dead, don't process it.208 if (DT && !DT->isReachableFromEntry(BB))209 continue;210 211 if (!Result.insert(BB))212 llvm_unreachable("Repeated basic blocks in extraction input");213 }214 215 LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName()216 << '\n');217 218 for (auto *BB : Result) {219 if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca))220 return {};221 222 // Make sure that the first block is not a landing pad.223 if (BB == Result.front()) {224 if (BB->isEHPad()) {225 LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n");226 return {};227 }228 continue;229 }230 231 // All blocks other than the first must not have predecessors outside of232 // the subgraph which is being extracted.233 for (auto *PBB : predecessors(BB))234 if (!Result.count(PBB)) {235 LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from "236 "outside the region except for the first block!\n"237 << "Problematic source BB: " << BB->getName() << "\n"238 << "Problematic destination BB: " << PBB->getName()239 << "\n");240 return {};241 }242 }243 244 return Result;245}246 247/// isAlignmentPreservedForAddrCast - Return true if the cast operation248/// for specified target preserves original alignment249static bool isAlignmentPreservedForAddrCast(const Triple &TargetTriple) {250 switch (TargetTriple.getArch()) {251 case Triple::ArchType::amdgcn:252 case Triple::ArchType::r600:253 return true;254 // TODO: Add other architectures for which we are certain that alignment255 // is preserved during address space cast operations.256 default:257 return false;258 }259 return false;260}261 262CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,263 bool AggregateArgs, BlockFrequencyInfo *BFI,264 BranchProbabilityInfo *BPI, AssumptionCache *AC,265 bool AllowVarArgs, bool AllowAlloca,266 BasicBlock *AllocationBlock, std::string Suffix,267 bool ArgsInZeroAddressSpace)268 : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),269 BPI(BPI), AC(AC), AllocationBlock(AllocationBlock),270 AllowVarArgs(AllowVarArgs),271 Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)),272 Suffix(Suffix), ArgsInZeroAddressSpace(ArgsInZeroAddressSpace) {}273 274/// definedInRegion - Return true if the specified value is defined in the275/// extracted region.276static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {277 if (Instruction *I = dyn_cast<Instruction>(V))278 if (Blocks.count(I->getParent()))279 return true;280 return false;281}282 283/// definedInCaller - Return true if the specified value is defined in the284/// function being code extracted, but not in the region being extracted.285/// These values must be passed in as live-ins to the function.286static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {287 if (isa<Argument>(V)) return true;288 if (Instruction *I = dyn_cast<Instruction>(V))289 if (!Blocks.count(I->getParent()))290 return true;291 return false;292}293 294static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {295 BasicBlock *CommonExitBlock = nullptr;296 auto hasNonCommonExitSucc = [&](BasicBlock *Block) {297 for (auto *Succ : successors(Block)) {298 // Internal edges, ok.299 if (Blocks.count(Succ))300 continue;301 if (!CommonExitBlock) {302 CommonExitBlock = Succ;303 continue;304 }305 if (CommonExitBlock != Succ)306 return true;307 }308 return false;309 };310 311 if (any_of(Blocks, hasNonCommonExitSucc))312 return nullptr;313 314 return CommonExitBlock;315}316 317CodeExtractorAnalysisCache::CodeExtractorAnalysisCache(Function &F) {318 for (BasicBlock &BB : F) {319 for (Instruction &II : BB.instructionsWithoutDebug())320 if (auto *AI = dyn_cast<AllocaInst>(&II))321 Allocas.push_back(AI);322 323 findSideEffectInfoForBlock(BB);324 }325}326 327void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) {328 for (Instruction &II : BB.instructionsWithoutDebug()) {329 unsigned Opcode = II.getOpcode();330 Value *MemAddr = nullptr;331 switch (Opcode) {332 case Instruction::Store:333 case Instruction::Load: {334 if (Opcode == Instruction::Store) {335 StoreInst *SI = cast<StoreInst>(&II);336 MemAddr = SI->getPointerOperand();337 } else {338 LoadInst *LI = cast<LoadInst>(&II);339 MemAddr = LI->getPointerOperand();340 }341 // Global variable can not be aliased with locals.342 if (isa<Constant>(MemAddr))343 break;344 Value *Base = MemAddr->stripInBoundsConstantOffsets();345 if (!isa<AllocaInst>(Base)) {346 SideEffectingBlocks.insert(&BB);347 return;348 }349 BaseMemAddrs[&BB].insert(Base);350 break;351 }352 default: {353 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);354 if (IntrInst) {355 if (IntrInst->isLifetimeStartOrEnd())356 break;357 SideEffectingBlocks.insert(&BB);358 return;359 }360 // Treat all the other cases conservatively if it has side effects.361 if (II.mayHaveSideEffects()) {362 SideEffectingBlocks.insert(&BB);363 return;364 }365 }366 }367 }368}369 370bool CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr(371 BasicBlock &BB, AllocaInst *Addr) const {372 if (SideEffectingBlocks.count(&BB))373 return true;374 auto It = BaseMemAddrs.find(&BB);375 if (It != BaseMemAddrs.end())376 return It->second.count(Addr);377 return false;378}379 380bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(381 const CodeExtractorAnalysisCache &CEAC, Instruction *Addr) const {382 AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());383 Function *Func = (*Blocks.begin())->getParent();384 for (BasicBlock &BB : *Func) {385 if (Blocks.count(&BB))386 continue;387 if (CEAC.doesBlockContainClobberOfAddr(BB, AI))388 return false;389 }390 return true;391}392 393BasicBlock *394CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {395 BasicBlock *SinglePredFromOutlineRegion = nullptr;396 assert(!Blocks.count(CommonExitBlock) &&397 "Expect a block outside the region!");398 for (auto *Pred : predecessors(CommonExitBlock)) {399 if (!Blocks.count(Pred))400 continue;401 if (!SinglePredFromOutlineRegion) {402 SinglePredFromOutlineRegion = Pred;403 } else if (SinglePredFromOutlineRegion != Pred) {404 SinglePredFromOutlineRegion = nullptr;405 break;406 }407 }408 409 if (SinglePredFromOutlineRegion)410 return SinglePredFromOutlineRegion;411 412#ifndef NDEBUG413 auto getFirstPHI = [](BasicBlock *BB) {414 BasicBlock::iterator I = BB->begin();415 PHINode *FirstPhi = nullptr;416 while (I != BB->end()) {417 PHINode *Phi = dyn_cast<PHINode>(I);418 if (!Phi)419 break;420 if (!FirstPhi) {421 FirstPhi = Phi;422 break;423 }424 }425 return FirstPhi;426 };427 // If there are any phi nodes, the single pred either exists or has already428 // be created before code extraction.429 assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");430#endif431 432 BasicBlock *NewExitBlock =433 CommonExitBlock->splitBasicBlock(CommonExitBlock->getFirstNonPHIIt());434 435 for (BasicBlock *Pred :436 llvm::make_early_inc_range(predecessors(CommonExitBlock))) {437 if (Blocks.count(Pred))438 continue;439 Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);440 }441 // Now add the old exit block to the outline region.442 Blocks.insert(CommonExitBlock);443 return CommonExitBlock;444}445 446// Find the pair of life time markers for address 'Addr' that are either447// defined inside the outline region or can legally be shrinkwrapped into the448// outline region. If there are not other untracked uses of the address, return449// the pair of markers if found; otherwise return a pair of nullptr.450CodeExtractor::LifetimeMarkerInfo451CodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,452 Instruction *Addr,453 BasicBlock *ExitBlock) const {454 LifetimeMarkerInfo Info;455 456 for (User *U : Addr->users()) {457 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);458 if (IntrInst) {459 // We don't model addresses with multiple start/end markers, but the460 // markers do not need to be in the region.461 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {462 if (Info.LifeStart)463 return {};464 Info.LifeStart = IntrInst;465 continue;466 }467 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {468 if (Info.LifeEnd)469 return {};470 Info.LifeEnd = IntrInst;471 continue;472 }473 }474 // Find untracked uses of the address, bail.475 if (!definedInRegion(Blocks, U))476 return {};477 }478 479 if (!Info.LifeStart || !Info.LifeEnd)480 return {};481 482 Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart);483 Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd);484 // Do legality check.485 if ((Info.SinkLifeStart || Info.HoistLifeEnd) &&486 !isLegalToShrinkwrapLifetimeMarkers(CEAC, Addr))487 return {};488 489 // Check to see if we have a place to do hoisting, if not, bail.490 if (Info.HoistLifeEnd && !ExitBlock)491 return {};492 493 return Info;494}495 496void CodeExtractor::findAllocas(const CodeExtractorAnalysisCache &CEAC,497 ValueSet &SinkCands, ValueSet &HoistCands,498 BasicBlock *&ExitBlock) const {499 Function *Func = (*Blocks.begin())->getParent();500 ExitBlock = getCommonExitBlock(Blocks);501 502 auto moveOrIgnoreLifetimeMarkers =503 [&](const LifetimeMarkerInfo &LMI) -> bool {504 if (!LMI.LifeStart)505 return false;506 if (LMI.SinkLifeStart) {507 LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart508 << "\n");509 SinkCands.insert(LMI.LifeStart);510 }511 if (LMI.HoistLifeEnd) {512 LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n");513 HoistCands.insert(LMI.LifeEnd);514 }515 return true;516 };517 518 // Look up allocas in the original function in CodeExtractorAnalysisCache, as519 // this is much faster than walking all the instructions.520 for (AllocaInst *AI : CEAC.getAllocas()) {521 BasicBlock *BB = AI->getParent();522 if (Blocks.count(BB))523 continue;524 525 // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca,526 // check whether it is actually still in the original function.527 Function *AIFunc = BB->getParent();528 if (AIFunc != Func)529 continue;530 531 LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock);532 bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);533 if (Moved) {534 LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n");535 SinkCands.insert(AI);536 continue;537 }538 539 // Find bitcasts in the outlined region that have lifetime marker users540 // outside that region. Replace the lifetime marker use with an541 // outside region bitcast to avoid unnecessary alloca/reload instructions542 // and extra lifetime markers.543 SmallVector<Instruction *, 2> LifetimeBitcastUsers;544 for (User *U : AI->users()) {545 if (!definedInRegion(Blocks, U))546 continue;547 548 if (U->stripInBoundsConstantOffsets() != AI)549 continue;550 551 Instruction *Bitcast = cast<Instruction>(U);552 for (User *BU : Bitcast->users()) {553 auto *IntrInst = dyn_cast<LifetimeIntrinsic>(BU);554 if (!IntrInst)555 continue;556 557 if (definedInRegion(Blocks, IntrInst))558 continue;559 560 LLVM_DEBUG(dbgs() << "Replace use of extracted region bitcast"561 << *Bitcast << " in out-of-region lifetime marker "562 << *IntrInst << "\n");563 LifetimeBitcastUsers.push_back(IntrInst);564 }565 }566 567 for (Instruction *I : LifetimeBitcastUsers) {568 Module *M = AIFunc->getParent();569 LLVMContext &Ctx = M->getContext();570 auto *Int8PtrTy = PointerType::getUnqual(Ctx);571 CastInst *CastI =572 CastInst::CreatePointerCast(AI, Int8PtrTy, "lt.cast", I->getIterator());573 I->replaceUsesOfWith(I->getOperand(1), CastI);574 }575 576 // Follow any bitcasts.577 SmallVector<Instruction *, 2> Bitcasts;578 SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo;579 for (User *U : AI->users()) {580 if (U->stripInBoundsConstantOffsets() == AI) {581 Instruction *Bitcast = cast<Instruction>(U);582 LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock);583 if (LMI.LifeStart) {584 Bitcasts.push_back(Bitcast);585 BitcastLifetimeInfo.push_back(LMI);586 continue;587 }588 }589 590 // Found unknown use of AI.591 if (!definedInRegion(Blocks, U)) {592 Bitcasts.clear();593 break;594 }595 }596 597 // Either no bitcasts reference the alloca or there are unknown uses.598 if (Bitcasts.empty())599 continue;600 601 LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n");602 SinkCands.insert(AI);603 for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) {604 Instruction *BitcastAddr = Bitcasts[I];605 const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I];606 assert(LMI.LifeStart &&607 "Unsafe to sink bitcast without lifetime markers");608 moveOrIgnoreLifetimeMarkers(LMI);609 if (!definedInRegion(Blocks, BitcastAddr)) {610 LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr611 << "\n");612 SinkCands.insert(BitcastAddr);613 }614 }615 }616}617 618bool CodeExtractor::isEligible() const {619 if (Blocks.empty())620 return false;621 BasicBlock *Header = *Blocks.begin();622 Function *F = Header->getParent();623 624 // For functions with varargs, check that varargs handling is only done in the625 // outlined function, i.e vastart and vaend are only used in outlined blocks.626 if (AllowVarArgs && F->getFunctionType()->isVarArg()) {627 auto containsVarArgIntrinsic = [](const Instruction &I) {628 if (const CallInst *CI = dyn_cast<CallInst>(&I))629 if (const Function *Callee = CI->getCalledFunction())630 return Callee->getIntrinsicID() == Intrinsic::vastart ||631 Callee->getIntrinsicID() == Intrinsic::vaend;632 return false;633 };634 635 for (auto &BB : *F) {636 if (Blocks.count(&BB))637 continue;638 if (llvm::any_of(BB, containsVarArgIntrinsic))639 return false;640 }641 }642 // stacksave as input implies stackrestore in the outlined function.643 // This can confuse prolog epilog insertion phase.644 // stacksave's uses must not cross outlined function.645 for (BasicBlock *BB : Blocks) {646 for (Instruction &I : *BB) {647 IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);648 if (!II)649 continue;650 bool IsSave = II->getIntrinsicID() == Intrinsic::stacksave;651 bool IsRestore = II->getIntrinsicID() == Intrinsic::stackrestore;652 if (IsSave && any_of(II->users(), [&Blks = this->Blocks](User *U) {653 return !definedInRegion(Blks, U);654 }))655 return false;656 if (IsRestore && !definedInRegion(Blocks, II->getArgOperand(0)))657 return false;658 }659 }660 return true;661}662 663void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,664 const ValueSet &SinkCands,665 bool CollectGlobalInputs) const {666 for (BasicBlock *BB : Blocks) {667 // If a used value is defined outside the region, it's an input. If an668 // instruction is used outside the region, it's an output.669 for (Instruction &II : *BB) {670 for (auto &OI : II.operands()) {671 Value *V = OI;672 if (!SinkCands.count(V) &&673 (definedInCaller(Blocks, V) ||674 (CollectGlobalInputs && llvm::isa<llvm::GlobalVariable>(V))))675 Inputs.insert(V);676 }677 678 for (User *U : II.users())679 if (!definedInRegion(Blocks, U)) {680 Outputs.insert(&II);681 break;682 }683 }684 }685}686 687/// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside688/// of the region, we need to split the entry block of the region so that the689/// PHI node is easier to deal with.690void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {691 unsigned NumPredsFromRegion = 0;692 unsigned NumPredsOutsideRegion = 0;693 694 if (Header != &Header->getParent()->getEntryBlock()) {695 PHINode *PN = dyn_cast<PHINode>(Header->begin());696 if (!PN) return; // No PHI nodes.697 698 // If the header node contains any PHI nodes, check to see if there is more699 // than one entry from outside the region. If so, we need to sever the700 // header block into two.701 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)702 if (Blocks.count(PN->getIncomingBlock(i)))703 ++NumPredsFromRegion;704 else705 ++NumPredsOutsideRegion;706 707 // If there is one (or fewer) predecessor from outside the region, we don't708 // need to do anything special.709 if (NumPredsOutsideRegion <= 1) return;710 }711 712 // Otherwise, we need to split the header block into two pieces: one713 // containing PHI nodes merging values from outside of the region, and a714 // second that contains all of the code for the block and merges back any715 // incoming values from inside of the region.716 BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHIIt(), DT);717 718 // We only want to code extract the second block now, and it becomes the new719 // header of the region.720 BasicBlock *OldPred = Header;721 Blocks.remove(OldPred);722 Blocks.insert(NewBB);723 Header = NewBB;724 725 // Okay, now we need to adjust the PHI nodes and any branches from within the726 // region to go to the new header block instead of the old header block.727 if (NumPredsFromRegion) {728 PHINode *PN = cast<PHINode>(OldPred->begin());729 // Loop over all of the predecessors of OldPred that are in the region,730 // changing them to branch to NewBB instead.731 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)732 if (Blocks.count(PN->getIncomingBlock(i))) {733 Instruction *TI = PN->getIncomingBlock(i)->getTerminator();734 TI->replaceUsesOfWith(OldPred, NewBB);735 }736 737 // Okay, everything within the region is now branching to the right block, we738 // just have to update the PHI nodes now, inserting PHI nodes into NewBB.739 BasicBlock::iterator AfterPHIs;740 for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {741 PHINode *PN = cast<PHINode>(AfterPHIs);742 // Create a new PHI node in the new region, which has an incoming value743 // from OldPred of PN.744 PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,745 PN->getName() + ".ce");746 NewPN->insertBefore(NewBB->begin());747 PN->replaceAllUsesWith(NewPN);748 NewPN->addIncoming(PN, OldPred);749 750 // Loop over all of the incoming value in PN, moving them to NewPN if they751 // are from the extracted region.752 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {753 if (Blocks.count(PN->getIncomingBlock(i))) {754 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));755 PN->removeIncomingValue(i);756 --i;757 }758 }759 }760 }761}762 763/// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from764/// outlined region, we split these PHIs on two: one with inputs from region765/// and other with remaining incoming blocks; then first PHIs are placed in766/// outlined region.767void CodeExtractor::severSplitPHINodesOfExits() {768 for (BasicBlock *ExitBB : ExtractedFuncRetVals) {769 BasicBlock *NewBB = nullptr;770 771 for (PHINode &PN : ExitBB->phis()) {772 // Find all incoming values from the outlining region.773 SmallVector<unsigned, 2> IncomingVals;774 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)775 if (Blocks.count(PN.getIncomingBlock(i)))776 IncomingVals.push_back(i);777 778 // Do not process PHI if there is one (or fewer) predecessor from region.779 // If PHI has exactly one predecessor from region, only this one incoming780 // will be replaced on codeRepl block, so it should be safe to skip PHI.781 if (IncomingVals.size() <= 1)782 continue;783 784 // Create block for new PHIs and add it to the list of outlined if it785 // wasn't done before.786 if (!NewBB) {787 NewBB = BasicBlock::Create(ExitBB->getContext(),788 ExitBB->getName() + ".split",789 ExitBB->getParent(), ExitBB);790 SmallVector<BasicBlock *, 4> Preds(predecessors(ExitBB));791 for (BasicBlock *PredBB : Preds)792 if (Blocks.count(PredBB))793 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);794 BranchInst::Create(ExitBB, NewBB);795 Blocks.insert(NewBB);796 }797 798 // Split this PHI.799 PHINode *NewPN = PHINode::Create(PN.getType(), IncomingVals.size(),800 PN.getName() + ".ce");801 NewPN->insertBefore(NewBB->getFirstNonPHIIt());802 for (unsigned i : IncomingVals)803 NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));804 for (unsigned i : reverse(IncomingVals))805 PN.removeIncomingValue(i, false);806 PN.addIncoming(NewPN, NewBB);807 }808 }809}810 811void CodeExtractor::splitReturnBlocks() {812 for (BasicBlock *Block : Blocks)813 if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {814 BasicBlock *New =815 Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");816 if (DT) {817 // Old dominates New. New node dominates all other nodes dominated818 // by Old.819 DomTreeNode *OldNode = DT->getNode(Block);820 SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),821 OldNode->end());822 823 DomTreeNode *NewNode = DT->addNewBlock(New, Block);824 825 for (DomTreeNode *I : Children)826 DT->changeImmediateDominator(I, NewNode);827 }828 }829}830 831Function *CodeExtractor::constructFunctionDeclaration(832 const ValueSet &inputs, const ValueSet &outputs, BlockFrequency EntryFreq,833 const Twine &Name, ValueSet &StructValues, StructType *&StructTy) {834 LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");835 LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");836 837 Function *oldFunction = Blocks.front()->getParent();838 Module *M = Blocks.front()->getModule();839 840 // Assemble the function's parameter lists.841 std::vector<Type *> ParamTy;842 std::vector<Type *> AggParamTy;843 const DataLayout &DL = M->getDataLayout();844 845 // Add the types of the input values to the function's argument list846 for (Value *value : inputs) {847 LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");848 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(value)) {849 AggParamTy.push_back(value->getType());850 StructValues.insert(value);851 } else852 ParamTy.push_back(value->getType());853 }854 855 // Add the types of the output values to the function's argument list.856 for (Value *output : outputs) {857 LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");858 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {859 AggParamTy.push_back(output->getType());860 StructValues.insert(output);861 } else862 ParamTy.push_back(863 PointerType::get(output->getContext(), DL.getAllocaAddrSpace()));864 }865 866 assert(867 (ParamTy.size() + AggParamTy.size()) ==868 (inputs.size() + outputs.size()) &&869 "Number of scalar and aggregate params does not match inputs, outputs");870 assert((StructValues.empty() || AggregateArgs) &&871 "Expeced StructValues only with AggregateArgs set");872 873 // Concatenate scalar and aggregate params in ParamTy.874 if (!AggParamTy.empty()) {875 StructTy = StructType::get(M->getContext(), AggParamTy);876 ParamTy.push_back(PointerType::get(877 M->getContext(), ArgsInZeroAddressSpace ? 0 : DL.getAllocaAddrSpace()));878 }879 880 Type *RetTy = getSwitchType();881 LLVM_DEBUG({882 dbgs() << "Function type: " << *RetTy << " f(";883 for (Type *i : ParamTy)884 dbgs() << *i << ", ";885 dbgs() << ")\n";886 });887 888 FunctionType *funcType = FunctionType::get(889 RetTy, ParamTy, AllowVarArgs && oldFunction->isVarArg());890 891 // Create the new function892 Function *newFunction =893 Function::Create(funcType, GlobalValue::InternalLinkage,894 oldFunction->getAddressSpace(), Name, M);895 896 // Propagate personality info to the new function if there is one.897 if (oldFunction->hasPersonalityFn())898 newFunction->setPersonalityFn(oldFunction->getPersonalityFn());899 900 // Inherit all of the target dependent attributes and white-listed901 // target independent attributes.902 // (e.g. If the extracted region contains a call to an x86.sse903 // instruction we need to make sure that the extracted region has the904 // "target-features" attribute allowing it to be lowered.905 // FIXME: This should be changed to check to see if a specific906 // attribute can not be inherited.907 for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) {908 if (Attr.isStringAttribute()) {909 if (Attr.getKindAsString() == "thunk")910 continue;911 } else912 switch (Attr.getKindAsEnum()) {913 // Those attributes cannot be propagated safely. Explicitly list them914 // here so we get a warning if new attributes are added.915 case Attribute::AllocSize:916 case Attribute::Builtin:917 case Attribute::Convergent:918 case Attribute::JumpTable:919 case Attribute::Naked:920 case Attribute::NoBuiltin:921 case Attribute::NoMerge:922 case Attribute::NoReturn:923 case Attribute::NoSync:924 case Attribute::ReturnsTwice:925 case Attribute::Speculatable:926 case Attribute::StackAlignment:927 case Attribute::WillReturn:928 case Attribute::AllocKind:929 case Attribute::PresplitCoroutine:930 case Attribute::Memory:931 case Attribute::NoFPClass:932 case Attribute::CoroDestroyOnlyWhenComplete:933 case Attribute::CoroElideSafe:934 case Attribute::NoDivergenceSource:935 case Attribute::NoCreateUndefOrPoison:936 continue;937 // Those attributes should be safe to propagate to the extracted function.938 case Attribute::AlwaysInline:939 case Attribute::Cold:940 case Attribute::DisableSanitizerInstrumentation:941 case Attribute::FnRetThunkExtern:942 case Attribute::Hot:943 case Attribute::HybridPatchable:944 case Attribute::NoRecurse:945 case Attribute::InlineHint:946 case Attribute::MinSize:947 case Attribute::NoCallback:948 case Attribute::NoDuplicate:949 case Attribute::NoFree:950 case Attribute::NoImplicitFloat:951 case Attribute::NoInline:952 case Attribute::NonLazyBind:953 case Attribute::NoRedZone:954 case Attribute::NoUnwind:955 case Attribute::NoSanitizeBounds:956 case Attribute::NoSanitizeCoverage:957 case Attribute::NullPointerIsValid:958 case Attribute::OptimizeForDebugging:959 case Attribute::OptForFuzzing:960 case Attribute::OptimizeNone:961 case Attribute::OptimizeForSize:962 case Attribute::SafeStack:963 case Attribute::ShadowCallStack:964 case Attribute::SanitizeAddress:965 case Attribute::SanitizeMemory:966 case Attribute::SanitizeNumericalStability:967 case Attribute::SanitizeThread:968 case Attribute::SanitizeType:969 case Attribute::SanitizeHWAddress:970 case Attribute::SanitizeMemTag:971 case Attribute::SanitizeRealtime:972 case Attribute::SanitizeRealtimeBlocking:973 case Attribute::SanitizeAllocToken:974 case Attribute::SpeculativeLoadHardening:975 case Attribute::StackProtect:976 case Attribute::StackProtectReq:977 case Attribute::StackProtectStrong:978 case Attribute::StrictFP:979 case Attribute::UWTable:980 case Attribute::VScaleRange:981 case Attribute::NoCfCheck:982 case Attribute::MustProgress:983 case Attribute::NoProfile:984 case Attribute::SkipProfile:985 break;986 // These attributes cannot be applied to functions.987 case Attribute::Alignment:988 case Attribute::AllocatedPointer:989 case Attribute::AllocAlign:990 case Attribute::ByVal:991 case Attribute::Captures:992 case Attribute::Dereferenceable:993 case Attribute::DereferenceableOrNull:994 case Attribute::ElementType:995 case Attribute::InAlloca:996 case Attribute::InReg:997 case Attribute::Nest:998 case Attribute::NoAlias:999 case Attribute::NoUndef:1000 case Attribute::NonNull:1001 case Attribute::Preallocated:1002 case Attribute::ReadNone:1003 case Attribute::ReadOnly:1004 case Attribute::Returned:1005 case Attribute::SExt:1006 case Attribute::StructRet:1007 case Attribute::SwiftError:1008 case Attribute::SwiftSelf:1009 case Attribute::SwiftAsync:1010 case Attribute::ZExt:1011 case Attribute::ImmArg:1012 case Attribute::ByRef:1013 case Attribute::WriteOnly:1014 case Attribute::Writable:1015 case Attribute::DeadOnUnwind:1016 case Attribute::Range:1017 case Attribute::Initializes:1018 case Attribute::NoExt:1019 // These are not really attributes.1020 case Attribute::None:1021 case Attribute::EndAttrKinds:1022 case Attribute::EmptyKey:1023 case Attribute::TombstoneKey:1024 case Attribute::DeadOnReturn:1025 llvm_unreachable("Not a function attribute");1026 }1027 1028 newFunction->addFnAttr(Attr);1029 }1030 1031 // Create scalar and aggregate iterators to name all of the arguments we1032 // inserted.1033 Function::arg_iterator ScalarAI = newFunction->arg_begin();1034 1035 // Set names and attributes for input and output arguments.1036 ScalarAI = newFunction->arg_begin();1037 for (Value *input : inputs) {1038 if (StructValues.contains(input))1039 continue;1040 1041 ScalarAI->setName(input->getName());1042 if (input->isSwiftError())1043 newFunction->addParamAttr(ScalarAI - newFunction->arg_begin(),1044 Attribute::SwiftError);1045 ++ScalarAI;1046 }1047 for (Value *output : outputs) {1048 if (StructValues.contains(output))1049 continue;1050 1051 ScalarAI->setName(output->getName() + ".out");1052 ++ScalarAI;1053 }1054 1055 // Update the entry count of the function.1056 if (BFI) {1057 auto Count = BFI->getProfileCountFromFreq(EntryFreq);1058 if (Count.has_value())1059 newFunction->setEntryCount(1060 ProfileCount(*Count, Function::PCT_Real)); // FIXME1061 }1062 1063 return newFunction;1064}1065 1066/// If the original function has debug info, we have to add a debug location1067/// to the new branch instruction from the artificial entry block.1068/// We use the debug location of the first instruction in the extracted1069/// blocks, as there is no other equivalent line in the source code.1070static void applyFirstDebugLoc(Function *oldFunction,1071 ArrayRef<BasicBlock *> Blocks,1072 Instruction *BranchI) {1073 if (oldFunction->getSubprogram()) {1074 any_of(Blocks, [&BranchI](const BasicBlock *BB) {1075 return any_of(*BB, [&BranchI](const Instruction &I) {1076 if (!I.getDebugLoc())1077 return false;1078 BranchI->setDebugLoc(I.getDebugLoc());1079 return true;1080 });1081 });1082 }1083}1084 1085/// Erase lifetime.start markers which reference inputs to the extraction1086/// region, and insert the referenced memory into \p LifetimesStart.1087///1088/// The extraction region is defined by a set of blocks (\p Blocks), and a set1089/// of allocas which will be moved from the caller function into the extracted1090/// function (\p SunkAllocas).1091static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks,1092 const SetVector<Value *> &SunkAllocas,1093 SetVector<Value *> &LifetimesStart) {1094 for (BasicBlock *BB : Blocks) {1095 for (Instruction &I : llvm::make_early_inc_range(*BB)) {1096 auto *II = dyn_cast<LifetimeIntrinsic>(&I);1097 if (!II)1098 continue;1099 1100 // Get the memory operand of the lifetime marker. If the underlying1101 // object is a sunk alloca, or is otherwise defined in the extraction1102 // region, the lifetime marker must not be erased.1103 Value *Mem = II->getOperand(0);1104 if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))1105 continue;1106 1107 if (II->getIntrinsicID() == Intrinsic::lifetime_start)1108 LifetimesStart.insert(Mem);1109 II->eraseFromParent();1110 }1111 }1112}1113 1114/// Insert lifetime start/end markers surrounding the call to the new function1115/// for objects defined in the caller.1116static void insertLifetimeMarkersSurroundingCall(1117 Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,1118 CallInst *TheCall) {1119 Instruction *Term = TheCall->getParent()->getTerminator();1120 1121 // Emit lifetime markers for the pointers given in \p Objects. Insert the1122 // markers before the call if \p InsertBefore, and after the call otherwise.1123 auto insertMarkers = [&](Intrinsic::ID MarkerFunc, ArrayRef<Value *> Objects,1124 bool InsertBefore) {1125 for (Value *Mem : Objects) {1126 assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==1127 TheCall->getFunction()) &&1128 "Input memory not defined in original function");1129 1130 Function *Func =1131 Intrinsic::getOrInsertDeclaration(M, MarkerFunc, Mem->getType());1132 auto Marker = CallInst::Create(Func, Mem);1133 if (InsertBefore)1134 Marker->insertBefore(TheCall->getIterator());1135 else1136 Marker->insertBefore(Term->getIterator());1137 }1138 };1139 1140 if (!LifetimesStart.empty()) {1141 insertMarkers(Intrinsic::lifetime_start, LifetimesStart,1142 /*InsertBefore=*/true);1143 }1144 1145 if (!LifetimesEnd.empty()) {1146 insertMarkers(Intrinsic::lifetime_end, LifetimesEnd,1147 /*InsertBefore=*/false);1148 }1149}1150 1151void CodeExtractor::moveCodeToFunction(Function *newFunction) {1152 auto newFuncIt = newFunction->begin();1153 for (BasicBlock *Block : Blocks) {1154 // Delete the basic block from the old function, and the list of blocks1155 Block->removeFromParent();1156 1157 // Insert this basic block into the new function1158 // Insert the original blocks after the entry block created1159 // for the new function. The entry block may be followed1160 // by a set of exit blocks at this point, but these exit1161 // blocks better be placed at the end of the new function.1162 newFuncIt = newFunction->insert(std::next(newFuncIt), Block);1163 }1164}1165 1166void CodeExtractor::calculateNewCallTerminatorWeights(1167 BasicBlock *CodeReplacer,1168 const DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,1169 BranchProbabilityInfo *BPI) {1170 using Distribution = BlockFrequencyInfoImplBase::Distribution;1171 using BlockNode = BlockFrequencyInfoImplBase::BlockNode;1172 1173 // Update the branch weights for the exit block.1174 Instruction *TI = CodeReplacer->getTerminator();1175 SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);1176 1177 // Block Frequency distribution with dummy node.1178 Distribution BranchDist;1179 1180 SmallVector<BranchProbability, 4> EdgeProbabilities(1181 TI->getNumSuccessors(), BranchProbability::getUnknown());1182 1183 // Add each of the frequencies of the successors.1184 for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {1185 BlockNode ExitNode(i);1186 uint64_t ExitFreq = ExitWeights.lookup(TI->getSuccessor(i)).getFrequency();1187 if (ExitFreq != 0)1188 BranchDist.addExit(ExitNode, ExitFreq);1189 else1190 EdgeProbabilities[i] = BranchProbability::getZero();1191 }1192 1193 // Check for no total weight.1194 if (BranchDist.Total == 0) {1195 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);1196 return;1197 }1198 1199 // Normalize the distribution so that they can fit in unsigned.1200 BranchDist.normalize();1201 1202 // Create normalized branch weights and set the metadata.1203 for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {1204 const auto &Weight = BranchDist.Weights[I];1205 1206 // Get the weight and update the current BFI.1207 BranchWeights[Weight.TargetNode.Index] = Weight.Amount;1208 BranchProbability BP(Weight.Amount, BranchDist.Total);1209 EdgeProbabilities[Weight.TargetNode.Index] = BP;1210 }1211 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);1212 TI->setMetadata(1213 LLVMContext::MD_prof,1214 MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));1215}1216 1217/// Erase debug info intrinsics which refer to values in \p F but aren't in1218/// \p F.1219static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F) {1220 for (Instruction &I : instructions(F)) {1221 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;1222 findDbgUsers(&I, DbgVariableRecords);1223 for (DbgVariableRecord *DVR : DbgVariableRecords)1224 if (DVR->getFunction() != &F)1225 DVR->eraseFromParent();1226 }1227}1228 1229/// Fix up the debug info in the old and new functions. Following changes are1230/// done.1231/// 1. If a debug record points to a value that has been replaced, update the1232/// record to use the new value.1233/// 2. If an Input value that has been replaced was used as a location of a1234/// debug record in the Parent function, then materealize a similar record in1235/// the new function.1236/// 3. Point line locations and debug intrinsics to the new subprogram scope1237/// 4. Remove intrinsics which point to values outside of the new function.1238static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,1239 CallInst &TheCall,1240 const SetVector<Value *> &Inputs,1241 ArrayRef<Value *> NewValues) {1242 DISubprogram *OldSP = OldFunc.getSubprogram();1243 LLVMContext &Ctx = OldFunc.getContext();1244 1245 if (!OldSP) {1246 // Erase any debug info the new function contains.1247 stripDebugInfo(NewFunc);1248 // Make sure the old function doesn't contain any non-local metadata refs.1249 eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);1250 return;1251 }1252 1253 // Create a subprogram for the new function. Leave out a description of the1254 // function arguments, as the parameters don't correspond to anything at the1255 // source level.1256 assert(OldSP->getUnit() && "Missing compile unit for subprogram");1257 DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,1258 OldSP->getUnit());1259 auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray({}));1260 DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |1261 DISubprogram::SPFlagOptimized |1262 DISubprogram::SPFlagLocalToUnit;1263 auto NewSP = DIB.createFunction(1264 OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),1265 /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);1266 NewFunc.setSubprogram(NewSP);1267 1268 auto UpdateOrInsertDebugRecord = [&](auto *DR, Value *OldLoc, Value *NewLoc,1269 DIExpression *Expr, bool Declare) {1270 if (DR->getParent()->getParent() == &NewFunc) {1271 DR->replaceVariableLocationOp(OldLoc, NewLoc);1272 return;1273 }1274 if (Declare) {1275 DIB.insertDeclare(NewLoc, DR->getVariable(), Expr, DR->getDebugLoc(),1276 &NewFunc.getEntryBlock());1277 return;1278 }1279 DIB.insertDbgValueIntrinsic(1280 NewLoc, DR->getVariable(), Expr, DR->getDebugLoc(),1281 NewFunc.getEntryBlock().getTerminator()->getIterator());1282 };1283 for (auto [Input, NewVal] : zip_equal(Inputs, NewValues)) {1284 SmallVector<DbgVariableRecord *, 1> DPUsers;1285 findDbgUsers(Input, DPUsers);1286 DIExpression *Expr = DIB.createExpression();1287 1288 // Iterate the debud users of the Input values. If they are in the extracted1289 // function then update their location with the new value. If they are in1290 // the parent function then create a similar debug record.1291 for (auto *DVR : DPUsers)1292 UpdateOrInsertDebugRecord(DVR, Input, NewVal, Expr, DVR->isDbgDeclare());1293 }1294 1295 auto IsInvalidLocation = [&NewFunc](Value *Location) {1296 // Location is invalid if it isn't a constant, an instruction or an1297 // argument, or is an instruction/argument but isn't in the new function.1298 if (!Location || (!isa<Constant>(Location) && !isa<Argument>(Location) &&1299 !isa<Instruction>(Location)))1300 return true;1301 1302 if (Argument *Arg = dyn_cast<Argument>(Location))1303 return Arg->getParent() != &NewFunc;1304 if (Instruction *LocationInst = dyn_cast<Instruction>(Location))1305 return LocationInst->getFunction() != &NewFunc;1306 return false;1307 };1308 1309 // Debug intrinsics in the new function need to be updated in one of two1310 // ways:1311 // 1) They need to be deleted, because they describe a value in the old1312 // function.1313 // 2) They need to point to fresh metadata, e.g. because they currently1314 // point to a variable in the wrong scope.1315 SmallDenseMap<DINode *, DINode *> RemappedMetadata;1316 SmallVector<DbgVariableRecord *, 4> DVRsToDelete;1317 DenseMap<const MDNode *, MDNode *> Cache;1318 1319 auto GetUpdatedDIVariable = [&](DILocalVariable *OldVar) {1320 DINode *&NewVar = RemappedMetadata[OldVar];1321 if (!NewVar) {1322 DILocalScope *NewScope = DILocalScope::cloneScopeForSubprogram(1323 *OldVar->getScope(), *NewSP, Ctx, Cache);1324 NewVar = DIB.createAutoVariable(1325 NewScope, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),1326 OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,1327 OldVar->getAlignInBits());1328 }1329 return cast<DILocalVariable>(NewVar);1330 };1331 1332 auto UpdateDbgLabel = [&](auto *LabelRecord) {1333 // Point the label record to a fresh label within the new function if1334 // the record was not inlined from some other function.1335 if (LabelRecord->getDebugLoc().getInlinedAt())1336 return;1337 DILabel *OldLabel = LabelRecord->getLabel();1338 DINode *&NewLabel = RemappedMetadata[OldLabel];1339 if (!NewLabel) {1340 DILocalScope *NewScope = DILocalScope::cloneScopeForSubprogram(1341 *OldLabel->getScope(), *NewSP, Ctx, Cache);1342 NewLabel =1343 DILabel::get(Ctx, NewScope, OldLabel->getName(), OldLabel->getFile(),1344 OldLabel->getLine(), OldLabel->getColumn(),1345 OldLabel->isArtificial(), OldLabel->getCoroSuspendIdx());1346 }1347 LabelRecord->setLabel(cast<DILabel>(NewLabel));1348 };1349 1350 auto UpdateDbgRecordsOnInst = [&](Instruction &I) -> void {1351 for (DbgRecord &DR : I.getDbgRecordRange()) {1352 if (DbgLabelRecord *DLR = dyn_cast<DbgLabelRecord>(&DR)) {1353 UpdateDbgLabel(DLR);1354 continue;1355 }1356 1357 DbgVariableRecord &DVR = cast<DbgVariableRecord>(DR);1358 // If any of the used locations are invalid, delete the record.1359 if (any_of(DVR.location_ops(), IsInvalidLocation)) {1360 DVRsToDelete.push_back(&DVR);1361 continue;1362 }1363 1364 // DbgAssign intrinsics have an extra Value argument:1365 if (DVR.isDbgAssign() && IsInvalidLocation(DVR.getAddress())) {1366 DVRsToDelete.push_back(&DVR);1367 continue;1368 }1369 1370 // If the variable was in the scope of the old function, i.e. it was not1371 // inlined, point the intrinsic to a fresh variable within the new1372 // function.1373 if (!DVR.getDebugLoc().getInlinedAt())1374 DVR.setVariable(GetUpdatedDIVariable(DVR.getVariable()));1375 }1376 };1377 1378 for (Instruction &I : instructions(NewFunc))1379 UpdateDbgRecordsOnInst(I);1380 1381 for (auto *DVR : DVRsToDelete)1382 DVR->getMarker()->MarkedInstr->dropOneDbgRecord(DVR);1383 DIB.finalizeSubprogram(NewSP);1384 1385 // Fix up the scope information attached to the line locations and the1386 // debug assignment metadata in the new function.1387 DenseMap<DIAssignID *, DIAssignID *> AssignmentIDMap;1388 for (Instruction &I : instructions(NewFunc)) {1389 if (const DebugLoc &DL = I.getDebugLoc())1390 I.setDebugLoc(1391 DebugLoc::replaceInlinedAtSubprogram(DL, *NewSP, Ctx, Cache));1392 for (DbgRecord &DR : I.getDbgRecordRange())1393 DR.setDebugLoc(DebugLoc::replaceInlinedAtSubprogram(DR.getDebugLoc(),1394 *NewSP, Ctx, Cache));1395 1396 // Loop info metadata may contain line locations. Fix them up.1397 auto updateLoopInfoLoc = [&Ctx, &Cache, NewSP](Metadata *MD) -> Metadata * {1398 if (auto *Loc = dyn_cast_or_null<DILocation>(MD))1399 return DebugLoc::replaceInlinedAtSubprogram(Loc, *NewSP, Ctx, Cache);1400 return MD;1401 };1402 updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);1403 at::remapAssignID(AssignmentIDMap, I);1404 }1405 if (!TheCall.getDebugLoc())1406 TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP));1407 1408 eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);1409}1410 1411Function *1412CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) {1413 ValueSet Inputs, Outputs;1414 return extractCodeRegion(CEAC, Inputs, Outputs);1415}1416 1417Function *1418CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC,1419 ValueSet &inputs, ValueSet &outputs) {1420 if (!isEligible())1421 return nullptr;1422 1423 // Assumption: this is a single-entry code region, and the header is the first1424 // block in the region.1425 BasicBlock *header = *Blocks.begin();1426 Function *oldFunction = header->getParent();1427 1428 normalizeCFGForExtraction(header);1429 1430 // Remove @llvm.assume calls that will be moved to the new function from the1431 // old function's assumption cache.1432 for (BasicBlock *Block : Blocks) {1433 for (Instruction &I : llvm::make_early_inc_range(*Block)) {1434 if (auto *AI = dyn_cast<AssumeInst>(&I)) {1435 if (AC)1436 AC->unregisterAssumption(AI);1437 AI->eraseFromParent();1438 }1439 }1440 }1441 1442 ValueSet SinkingCands, HoistingCands;1443 BasicBlock *CommonExit = nullptr;1444 findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);1445 assert(HoistingCands.empty() || CommonExit);1446 1447 // Find inputs to, outputs from the code region.1448 findInputsOutputs(inputs, outputs, SinkingCands);1449 1450 // Collect objects which are inputs to the extraction region and also1451 // referenced by lifetime start markers within it. The effects of these1452 // markers must be replicated in the calling function to prevent the stack1453 // coloring pass from merging slots which store input objects.1454 ValueSet LifetimesStart;1455 eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);1456 1457 if (!HoistingCands.empty()) {1458 auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);1459 Instruction *TI = HoistToBlock->getTerminator();1460 for (auto *II : HoistingCands)1461 cast<Instruction>(II)->moveBefore(TI->getIterator());1462 computeExtractedFuncRetVals();1463 }1464 1465 // CFG/ExitBlocks must not change hereafter1466 1467 // Calculate the entry frequency of the new function before we change the root1468 // block.1469 BlockFrequency EntryFreq;1470 DenseMap<BasicBlock *, BlockFrequency> ExitWeights;1471 if (BFI) {1472 assert(BPI && "Both BPI and BFI are required to preserve profile info");1473 for (BasicBlock *Pred : predecessors(header)) {1474 if (Blocks.count(Pred))1475 continue;1476 EntryFreq +=1477 BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);1478 }1479 1480 for (BasicBlock *Succ : ExtractedFuncRetVals) {1481 for (BasicBlock *Block : predecessors(Succ)) {1482 if (!Blocks.count(Block))1483 continue;1484 1485 // Update the branch weight for this successor.1486 BlockFrequency &BF = ExitWeights[Succ];1487 BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ);1488 }1489 }1490 }1491 1492 // Determine position for the replacement code. Do so before header is moved1493 // to the new function.1494 BasicBlock *ReplIP = header;1495 while (ReplIP && Blocks.count(ReplIP))1496 ReplIP = ReplIP->getNextNode();1497 1498 // Construct new function based on inputs/outputs & add allocas for all defs.1499 std::string SuffixToUse =1500 Suffix.empty()1501 ? (header->getName().empty() ? "extracted" : header->getName().str())1502 : Suffix;1503 1504 ValueSet StructValues;1505 StructType *StructTy = nullptr;1506 Function *newFunction = constructFunctionDeclaration(1507 inputs, outputs, EntryFreq, oldFunction->getName() + "." + SuffixToUse,1508 StructValues, StructTy);1509 SmallVector<Value *> NewValues;1510 1511 emitFunctionBody(inputs, outputs, StructValues, newFunction, StructTy, header,1512 SinkingCands, NewValues);1513 1514 std::vector<Value *> Reloads;1515 CallInst *TheCall = emitReplacerCall(1516 inputs, outputs, StructValues, newFunction, StructTy, oldFunction, ReplIP,1517 EntryFreq, LifetimesStart.getArrayRef(), Reloads);1518 1519 insertReplacerCall(oldFunction, header, TheCall->getParent(), outputs,1520 Reloads, ExitWeights);1521 1522 fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall, inputs,1523 NewValues);1524 1525 LLVM_DEBUG(llvm::dbgs() << "After extractCodeRegion - newFunction:\n");1526 LLVM_DEBUG(newFunction->dump());1527 LLVM_DEBUG(llvm::dbgs() << "After extractCodeRegion - oldFunction:\n");1528 LLVM_DEBUG(oldFunction->dump());1529 LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))1530 report_fatal_error("Stale Asumption cache for old Function!"));1531 return newFunction;1532}1533 1534void CodeExtractor::normalizeCFGForExtraction(BasicBlock *&header) {1535 // If we have any return instructions in the region, split those blocks so1536 // that the return is not in the region.1537 splitReturnBlocks();1538 1539 // If we have to split PHI nodes of the entry or exit blocks, do so now.1540 severSplitPHINodesOfEntry(header);1541 1542 // If a PHI in an exit block has multiple incoming values from the outlined1543 // region, create a new PHI for those values within the region such that only1544 // PHI itself becomes an output value, not each of its incoming values1545 // individually.1546 computeExtractedFuncRetVals();1547 severSplitPHINodesOfExits();1548}1549 1550void CodeExtractor::computeExtractedFuncRetVals() {1551 ExtractedFuncRetVals.clear();1552 1553 SmallPtrSet<BasicBlock *, 2> ExitBlocks;1554 for (BasicBlock *Block : Blocks) {1555 for (BasicBlock *Succ : successors(Block)) {1556 if (Blocks.count(Succ))1557 continue;1558 1559 bool IsNew = ExitBlocks.insert(Succ).second;1560 if (IsNew)1561 ExtractedFuncRetVals.push_back(Succ);1562 }1563 }1564}1565 1566Type *CodeExtractor::getSwitchType() {1567 LLVMContext &Context = Blocks.front()->getContext();1568 1569 assert(ExtractedFuncRetVals.size() < 0xffff &&1570 "too many exit blocks for switch");1571 switch (ExtractedFuncRetVals.size()) {1572 case 0:1573 case 1:1574 return Type::getVoidTy(Context);1575 case 2:1576 // Conditional branch, return a bool1577 return Type::getInt1Ty(Context);1578 default:1579 return Type::getInt16Ty(Context);1580 }1581}1582 1583void CodeExtractor::emitFunctionBody(1584 const ValueSet &inputs, const ValueSet &outputs,1585 const ValueSet &StructValues, Function *newFunction,1586 StructType *StructArgTy, BasicBlock *header, const ValueSet &SinkingCands,1587 SmallVectorImpl<Value *> &NewValues) {1588 Function *oldFunction = header->getParent();1589 LLVMContext &Context = oldFunction->getContext();1590 1591 // The new function needs a root node because other nodes can branch to the1592 // head of the region, but the entry node of a function cannot have preds.1593 BasicBlock *newFuncRoot =1594 BasicBlock::Create(Context, "newFuncRoot", newFunction);1595 1596 // Now sink all instructions which only have non-phi uses inside the region.1597 // Group the allocas at the start of the block, so that any bitcast uses of1598 // the allocas are well-defined.1599 for (auto *II : SinkingCands) {1600 if (!isa<AllocaInst>(II)) {1601 cast<Instruction>(II)->moveBefore(*newFuncRoot,1602 newFuncRoot->getFirstInsertionPt());1603 }1604 }1605 for (auto *II : SinkingCands) {1606 if (auto *AI = dyn_cast<AllocaInst>(II)) {1607 AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());1608 }1609 }1610 1611 Function::arg_iterator ScalarAI = newFunction->arg_begin();1612 Argument *AggArg = StructValues.empty()1613 ? nullptr1614 : newFunction->getArg(newFunction->arg_size() - 1);1615 1616 // Rewrite all users of the inputs in the extracted region to use the1617 // arguments (or appropriate addressing into struct) instead.1618 for (unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) {1619 Value *RewriteVal;1620 if (StructValues.contains(inputs[i])) {1621 Value *Idx[2];1622 Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));1623 Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), aggIdx);1624 GetElementPtrInst *GEP = GetElementPtrInst::Create(1625 StructArgTy, AggArg, Idx, "gep_" + inputs[i]->getName(), newFuncRoot);1626 LoadInst *LoadGEP =1627 new LoadInst(StructArgTy->getElementType(aggIdx), GEP,1628 "loadgep_" + inputs[i]->getName(), newFuncRoot);1629 // If we load pointer, we can add optional !align metadata1630 // The existence of the !align metadata on the instruction tells1631 // the optimizer that the value loaded is known to be aligned to1632 // a boundary specified by the integer value in the metadata node.1633 // Example:1634 // %res = load ptr, ptr %input, align 8, !align !align_md_node1635 // ^ ^1636 // | |1637 // alignment of %input address |1638 // |1639 // alignment of %res object1640 if (StructArgTy->getElementType(aggIdx)->isPointerTy()) {1641 unsigned AlignmentValue;1642 const Triple &TargetTriple =1643 newFunction->getParent()->getTargetTriple();1644 const DataLayout &DL = header->getDataLayout();1645 // Pointers without casting can provide more information about1646 // alignment. Use pointers without casts if given target preserves1647 // alignment information for cast the operation.1648 if (isAlignmentPreservedForAddrCast(TargetTriple))1649 AlignmentValue =1650 inputs[i]->stripPointerCasts()->getPointerAlignment(DL).value();1651 else1652 AlignmentValue = inputs[i]->getPointerAlignment(DL).value();1653 MDBuilder MDB(header->getContext());1654 LoadGEP->setMetadata(1655 LLVMContext::MD_align,1656 MDNode::get(1657 header->getContext(),1658 MDB.createConstant(ConstantInt::get(1659 Type::getInt64Ty(header->getContext()), AlignmentValue))));1660 }1661 RewriteVal = LoadGEP;1662 ++aggIdx;1663 } else1664 RewriteVal = &*ScalarAI++;1665 1666 NewValues.push_back(RewriteVal);1667 }1668 1669 moveCodeToFunction(newFunction);1670 1671 for (unsigned i = 0, e = inputs.size(); i != e; ++i) {1672 Value *RewriteVal = NewValues[i];1673 1674 std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());1675 for (User *use : Users)1676 if (Instruction *inst = dyn_cast<Instruction>(use))1677 if (Blocks.count(inst->getParent()))1678 inst->replaceUsesOfWith(inputs[i], RewriteVal);1679 }1680 1681 // Since there may be multiple exits from the original region, make the new1682 // function return an unsigned, switch on that number. This loop iterates1683 // over all of the blocks in the extracted region, updating any terminator1684 // instructions in the to-be-extracted region that branch to blocks that are1685 // not in the region to be extracted.1686 std::map<BasicBlock *, BasicBlock *> ExitBlockMap;1687 1688 // Iterate over the previously collected targets, and create new blocks inside1689 // the function to branch to.1690 for (auto P : enumerate(ExtractedFuncRetVals)) {1691 BasicBlock *OldTarget = P.value();1692 size_t SuccNum = P.index();1693 1694 BasicBlock *NewTarget = BasicBlock::Create(1695 Context, OldTarget->getName() + ".exitStub", newFunction);1696 ExitBlockMap[OldTarget] = NewTarget;1697 1698 Value *brVal = nullptr;1699 Type *RetTy = getSwitchType();1700 assert(ExtractedFuncRetVals.size() < 0xffff &&1701 "too many exit blocks for switch");1702 switch (ExtractedFuncRetVals.size()) {1703 case 0:1704 case 1:1705 // No value needed.1706 break;1707 case 2: // Conditional branch, return a bool1708 brVal = ConstantInt::get(RetTy, !SuccNum);1709 break;1710 default:1711 brVal = ConstantInt::get(RetTy, SuccNum);1712 break;1713 }1714 1715 ReturnInst::Create(Context, brVal, NewTarget);1716 }1717 1718 for (BasicBlock *Block : Blocks) {1719 Instruction *TI = Block->getTerminator();1720 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {1721 if (Blocks.count(TI->getSuccessor(i)))1722 continue;1723 BasicBlock *OldTarget = TI->getSuccessor(i);1724 // add a new basic block which returns the appropriate value1725 BasicBlock *NewTarget = ExitBlockMap[OldTarget];1726 assert(NewTarget && "Unknown target block!");1727 1728 // rewrite the original branch instruction with this new target1729 TI->setSuccessor(i, NewTarget);1730 }1731 }1732 1733 // Loop over all of the PHI nodes in the header and exit blocks, and change1734 // any references to the old incoming edge to be the new incoming edge.1735 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {1736 PHINode *PN = cast<PHINode>(I);1737 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)1738 if (!Blocks.count(PN->getIncomingBlock(i)))1739 PN->setIncomingBlock(i, newFuncRoot);1740 }1741 1742 // Connect newFunction entry block to new header.1743 BranchInst *BranchI = BranchInst::Create(header, newFuncRoot);1744 applyFirstDebugLoc(oldFunction, Blocks.getArrayRef(), BranchI);1745 1746 // Store the arguments right after the definition of output value.1747 // This should be proceeded after creating exit stubs to be ensure that invoke1748 // result restore will be placed in the outlined function.1749 ScalarAI = newFunction->arg_begin();1750 unsigned AggIdx = 0;1751 1752 for (Value *Input : inputs) {1753 if (StructValues.contains(Input))1754 ++AggIdx;1755 else1756 ++ScalarAI;1757 }1758 1759 for (Value *Output : outputs) {1760 // Find proper insertion point.1761 // In case Output is an invoke, we insert the store at the beginning in the1762 // 'normal destination' BB. Otherwise we insert the store right after1763 // Output.1764 BasicBlock::iterator InsertPt;1765 if (auto *InvokeI = dyn_cast<InvokeInst>(Output))1766 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();1767 else if (auto *Phi = dyn_cast<PHINode>(Output))1768 InsertPt = Phi->getParent()->getFirstInsertionPt();1769 else if (auto *OutI = dyn_cast<Instruction>(Output))1770 InsertPt = std::next(OutI->getIterator());1771 else {1772 // Globals don't need to be updated, just advance to the next argument.1773 if (StructValues.contains(Output))1774 ++AggIdx;1775 else1776 ++ScalarAI;1777 continue;1778 }1779 1780 assert((InsertPt->getFunction() == newFunction ||1781 Blocks.count(InsertPt->getParent())) &&1782 "InsertPt should be in new function");1783 1784 if (StructValues.contains(Output)) {1785 assert(AggArg && "Number of aggregate output arguments should match "1786 "the number of defined values");1787 Value *Idx[2];1788 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));1789 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), AggIdx);1790 GetElementPtrInst *GEP = GetElementPtrInst::Create(1791 StructArgTy, AggArg, Idx, "gep_" + Output->getName(), InsertPt);1792 new StoreInst(Output, GEP, InsertPt);1793 ++AggIdx;1794 } else {1795 assert(ScalarAI != newFunction->arg_end() &&1796 "Number of scalar output arguments should match "1797 "the number of defined values");1798 new StoreInst(Output, &*ScalarAI, InsertPt);1799 ++ScalarAI;1800 }1801 }1802 1803 if (ExtractedFuncRetVals.empty()) {1804 // Mark the new function `noreturn` if applicable. Terminators which resume1805 // exception propagation are treated as returning instructions. This is to1806 // avoid inserting traps after calls to outlined functions which unwind.1807 if (none_of(Blocks, [](const BasicBlock *BB) {1808 const Instruction *Term = BB->getTerminator();1809 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);1810 }))1811 newFunction->setDoesNotReturn();1812 }1813}1814 1815CallInst *CodeExtractor::emitReplacerCall(1816 const ValueSet &inputs, const ValueSet &outputs,1817 const ValueSet &StructValues, Function *newFunction,1818 StructType *StructArgTy, Function *oldFunction, BasicBlock *ReplIP,1819 BlockFrequency EntryFreq, ArrayRef<Value *> LifetimesStart,1820 std::vector<Value *> &Reloads) {1821 LLVMContext &Context = oldFunction->getContext();1822 Module *M = oldFunction->getParent();1823 const DataLayout &DL = M->getDataLayout();1824 1825 // This takes place of the original loop1826 BasicBlock *codeReplacer =1827 BasicBlock::Create(Context, "codeRepl", oldFunction, ReplIP);1828 if (AllocationBlock)1829 assert(AllocationBlock->getParent() == oldFunction &&1830 "AllocationBlock is not in the same function");1831 BasicBlock *AllocaBlock =1832 AllocationBlock ? AllocationBlock : &oldFunction->getEntryBlock();1833 1834 // Update the entry count of the function.1835 if (BFI)1836 BFI->setBlockFreq(codeReplacer, EntryFreq);1837 1838 std::vector<Value *> params;1839 1840 // Add inputs as params, or to be filled into the struct1841 for (Value *input : inputs) {1842 if (StructValues.contains(input))1843 continue;1844 1845 params.push_back(input);1846 }1847 1848 // Create allocas for the outputs1849 std::vector<Value *> ReloadOutputs;1850 for (Value *output : outputs) {1851 if (StructValues.contains(output))1852 continue;1853 1854 AllocaInst *alloca = new AllocaInst(1855 output->getType(), DL.getAllocaAddrSpace(), nullptr,1856 output->getName() + ".loc", AllocaBlock->getFirstInsertionPt());1857 params.push_back(alloca);1858 ReloadOutputs.push_back(alloca);1859 }1860 1861 AllocaInst *Struct = nullptr;1862 if (!StructValues.empty()) {1863 Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,1864 "structArg", AllocaBlock->getFirstInsertionPt());1865 if (ArgsInZeroAddressSpace && DL.getAllocaAddrSpace() != 0) {1866 auto *StructSpaceCast = new AddrSpaceCastInst(1867 Struct, PointerType ::get(Context, 0), "structArg.ascast");1868 StructSpaceCast->insertAfter(Struct->getIterator());1869 params.push_back(StructSpaceCast);1870 } else {1871 params.push_back(Struct);1872 }1873 1874 unsigned AggIdx = 0;1875 for (Value *input : inputs) {1876 if (!StructValues.contains(input))1877 continue;1878 1879 Value *Idx[2];1880 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));1881 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), AggIdx);1882 GetElementPtrInst *GEP = GetElementPtrInst::Create(1883 StructArgTy, Struct, Idx, "gep_" + input->getName());1884 GEP->insertInto(codeReplacer, codeReplacer->end());1885 new StoreInst(input, GEP, codeReplacer);1886 1887 ++AggIdx;1888 }1889 }1890 1891 // Emit the call to the function1892 CallInst *call = CallInst::Create(1893 newFunction, params, ExtractedFuncRetVals.size() > 1 ? "targetBlock" : "",1894 codeReplacer);1895 1896 // Set swifterror parameter attributes.1897 unsigned ParamIdx = 0;1898 unsigned AggIdx = 0;1899 for (auto input : inputs) {1900 if (StructValues.contains(input)) {1901 ++AggIdx;1902 } else {1903 if (input->isSwiftError())1904 call->addParamAttr(ParamIdx, Attribute::SwiftError);1905 ++ParamIdx;1906 }1907 }1908 1909 // Add debug location to the new call, if the original function has debug1910 // info. In that case, the terminator of the entry block of the extracted1911 // function contains the first debug location of the extracted function,1912 // set in extractCodeRegion.1913 if (codeReplacer->getParent()->getSubprogram()) {1914 if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())1915 call->setDebugLoc(DL);1916 }1917 1918 // Reload the outputs passed in by reference, use the struct if output is in1919 // the aggregate or reload from the scalar argument.1920 for (unsigned i = 0, e = outputs.size(), scalarIdx = 0; i != e; ++i) {1921 Value *Output = nullptr;1922 if (StructValues.contains(outputs[i])) {1923 Value *Idx[2];1924 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));1925 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), AggIdx);1926 GetElementPtrInst *GEP = GetElementPtrInst::Create(1927 StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());1928 GEP->insertInto(codeReplacer, codeReplacer->end());1929 Output = GEP;1930 ++AggIdx;1931 } else {1932 Output = ReloadOutputs[scalarIdx];1933 ++scalarIdx;1934 }1935 LoadInst *load =1936 new LoadInst(outputs[i]->getType(), Output,1937 outputs[i]->getName() + ".reload", codeReplacer);1938 Reloads.push_back(load);1939 }1940 1941 // Now we can emit a switch statement using the call as a value.1942 SwitchInst *TheSwitch =1943 SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),1944 codeReplacer, 0, codeReplacer);1945 for (auto P : enumerate(ExtractedFuncRetVals)) {1946 BasicBlock *OldTarget = P.value();1947 size_t SuccNum = P.index();1948 1949 TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), SuccNum),1950 OldTarget);1951 }1952 1953 // Now that we've done the deed, simplify the switch instruction.1954 Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();1955 switch (ExtractedFuncRetVals.size()) {1956 case 0:1957 // There are no successors (the block containing the switch itself), which1958 // means that previously this was the last part of the function, and hence1959 // this should be rewritten as a `ret` or `unreachable`.1960 if (newFunction->doesNotReturn()) {1961 // If fn is no return, end with an unreachable terminator.1962 (void)new UnreachableInst(Context, TheSwitch->getIterator());1963 } else if (OldFnRetTy->isVoidTy()) {1964 // We have no return value.1965 ReturnInst::Create(Context, nullptr,1966 TheSwitch->getIterator()); // Return void1967 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {1968 // return what we have1969 ReturnInst::Create(Context, TheSwitch->getCondition(),1970 TheSwitch->getIterator());1971 } else {1972 // Otherwise we must have code extracted an unwind or something, just1973 // return whatever we want.1974 ReturnInst::Create(Context, Constant::getNullValue(OldFnRetTy),1975 TheSwitch->getIterator());1976 }1977 1978 TheSwitch->eraseFromParent();1979 break;1980 case 1:1981 // Only a single destination, change the switch into an unconditional1982 // branch.1983 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getIterator());1984 TheSwitch->eraseFromParent();1985 break;1986 case 2:1987 // Only two destinations, convert to a condition branch.1988 // Remark: This also swaps the target branches:1989 // 0 -> false -> getSuccessor(2); 1 -> true -> getSuccessor(1)1990 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),1991 call, TheSwitch->getIterator());1992 TheSwitch->eraseFromParent();1993 break;1994 default:1995 // Otherwise, make the default destination of the switch instruction be one1996 // of the other successors.1997 TheSwitch->setCondition(call);1998 TheSwitch->setDefaultDest(1999 TheSwitch->getSuccessor(ExtractedFuncRetVals.size()));2000 // Remove redundant case2001 TheSwitch->removeCase(2002 SwitchInst::CaseIt(TheSwitch, ExtractedFuncRetVals.size() - 1));2003 break;2004 }2005 2006 // Insert lifetime markers around the reloads of any output values. The2007 // allocas output values are stored in are only in-use in the codeRepl block.2008 insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);2009 2010 // Replicate the effects of any lifetime start/end markers which referenced2011 // input objects in the extraction region by placing markers around the call.2012 insertLifetimeMarkersSurroundingCall(oldFunction->getParent(), LifetimesStart,2013 {}, call);2014 2015 return call;2016}2017 2018void CodeExtractor::insertReplacerCall(2019 Function *oldFunction, BasicBlock *header, BasicBlock *codeReplacer,2020 const ValueSet &outputs, ArrayRef<Value *> Reloads,2021 const DenseMap<BasicBlock *, BlockFrequency> &ExitWeights) {2022 2023 // Rewrite branches to basic blocks outside of the loop to new dummy blocks2024 // within the new function. This must be done before we lose track of which2025 // blocks were originally in the code region.2026 std::vector<User *> Users(header->user_begin(), header->user_end());2027 for (auto &U : Users)2028 // The BasicBlock which contains the branch is not in the region2029 // modify the branch target to a new block2030 if (Instruction *I = dyn_cast<Instruction>(U))2031 if (I->isTerminator() && I->getFunction() == oldFunction &&2032 !Blocks.count(I->getParent()))2033 I->replaceUsesOfWith(header, codeReplacer);2034 2035 // When moving the code region it is sufficient to replace all uses to the2036 // extracted function values. Since the original definition's block2037 // dominated its use, it will also be dominated by codeReplacer's switch2038 // which joined multiple exit blocks.2039 for (BasicBlock *ExitBB : ExtractedFuncRetVals)2040 for (PHINode &PN : ExitBB->phis()) {2041 Value *IncomingCodeReplacerVal = nullptr;2042 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {2043 // Ignore incoming values from outside of the extracted region.2044 if (!Blocks.count(PN.getIncomingBlock(i)))2045 continue;2046 2047 // Ensure that there is only one incoming value from codeReplacer.2048 if (!IncomingCodeReplacerVal) {2049 PN.setIncomingBlock(i, codeReplacer);2050 IncomingCodeReplacerVal = PN.getIncomingValue(i);2051 } else2052 assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&2053 "PHI has two incompatbile incoming values from codeRepl");2054 }2055 }2056 2057 for (unsigned i = 0, e = outputs.size(); i != e; ++i) {2058 Value *load = Reloads[i];2059 std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());2060 for (User *U : Users) {2061 Instruction *inst = cast<Instruction>(U);2062 if (inst->getParent()->getParent() == oldFunction)2063 inst->replaceUsesOfWith(outputs[i], load);2064 }2065 }2066 2067 // Update the branch weights for the exit block.2068 if (BFI && ExtractedFuncRetVals.size() > 1)2069 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);2070}2071 2072bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc,2073 const Function &NewFunc,2074 AssumptionCache *AC) {2075 for (auto AssumeVH : AC->assumptions()) {2076 auto *I = dyn_cast_or_null<CallInst>(AssumeVH);2077 if (!I)2078 continue;2079 2080 // There shouldn't be any llvm.assume intrinsics in the new function.2081 if (I->getFunction() != &OldFunc)2082 return true;2083 2084 // There shouldn't be any stale affected values in the assumption cache2085 // that were previously in the old function, but that have now been moved2086 // to the new function.2087 for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {2088 auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);2089 if (!AffectedCI)2090 continue;2091 if (AffectedCI->getFunction() != &OldFunc)2092 return true;2093 auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));2094 if (AssumedInst->getFunction() != &OldFunc)2095 return true;2096 }2097 }2098 return false;2099}2100 2101void CodeExtractor::excludeArgFromAggregate(Value *Arg) {2102 ExcludeArgsFromAggregate.insert(Arg);2103}2104