CodeExtractor.cpp revision 353358
1193323Sed//===- CodeExtractor.cpp - Pull code region into a new function -----------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements the interface to tear out a code region, such as an 10193323Sed// individual loop or a parallel section, into a new function, replacing it with 11193323Sed// a call to the new function. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15239462Sdim#include "llvm/Transforms/Utils/CodeExtractor.h" 16327952Sdim#include "llvm/ADT/ArrayRef.h" 17327952Sdim#include "llvm/ADT/DenseMap.h" 18327952Sdim#include "llvm/ADT/Optional.h" 19276479Sdim#include "llvm/ADT/STLExtras.h" 20249423Sdim#include "llvm/ADT/SetVector.h" 21327952Sdim#include "llvm/ADT/SmallPtrSet.h" 22327952Sdim#include "llvm/ADT/SmallVector.h" 23353358Sdim#include "llvm/Analysis/AssumptionCache.h" 24314564Sdim#include "llvm/Analysis/BlockFrequencyInfo.h" 25314564Sdim#include "llvm/Analysis/BlockFrequencyInfoImpl.h" 26314564Sdim#include "llvm/Analysis/BranchProbabilityInfo.h" 27193323Sed#include "llvm/Analysis/LoopInfo.h" 28327952Sdim#include "llvm/IR/Argument.h" 29327952Sdim#include "llvm/IR/Attributes.h" 30327952Sdim#include "llvm/IR/BasicBlock.h" 31327952Sdim#include "llvm/IR/CFG.h" 32327952Sdim#include "llvm/IR/Constant.h" 33249423Sdim#include "llvm/IR/Constants.h" 34327952Sdim#include "llvm/IR/DataLayout.h" 35249423Sdim#include "llvm/IR/DerivedTypes.h" 36276479Sdim#include "llvm/IR/Dominators.h" 37327952Sdim#include "llvm/IR/Function.h" 38327952Sdim#include "llvm/IR/GlobalValue.h" 39327952Sdim#include "llvm/IR/InstrTypes.h" 40327952Sdim#include "llvm/IR/Instruction.h" 41249423Sdim#include "llvm/IR/Instructions.h" 42321369Sdim#include "llvm/IR/IntrinsicInst.h" 43249423Sdim#include "llvm/IR/Intrinsics.h" 44249423Sdim#include "llvm/IR/LLVMContext.h" 45314564Sdim#include "llvm/IR/MDBuilder.h" 46249423Sdim#include "llvm/IR/Module.h" 47353358Sdim#include "llvm/IR/PatternMatch.h" 48327952Sdim#include "llvm/IR/Type.h" 49327952Sdim#include "llvm/IR/User.h" 50327952Sdim#include "llvm/IR/Value.h" 51276479Sdim#include "llvm/IR/Verifier.h" 52249423Sdim#include "llvm/Pass.h" 53314564Sdim#include "llvm/Support/BlockFrequency.h" 54327952Sdim#include "llvm/Support/BranchProbability.h" 55327952Sdim#include "llvm/Support/Casting.h" 56193323Sed#include "llvm/Support/CommandLine.h" 57193323Sed#include "llvm/Support/Debug.h" 58198090Srdivacky#include "llvm/Support/ErrorHandling.h" 59198090Srdivacky#include "llvm/Support/raw_ostream.h" 60249423Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 61344779Sdim#include "llvm/Transforms/Utils/Local.h" 62327952Sdim#include <cassert> 63327952Sdim#include <cstdint> 64327952Sdim#include <iterator> 65327952Sdim#include <map> 66193323Sed#include <set> 67327952Sdim#include <utility> 68327952Sdim#include <vector> 69327952Sdim 70193323Sedusing namespace llvm; 71353358Sdimusing namespace llvm::PatternMatch; 72341825Sdimusing ProfileCount = Function::ProfileCount; 73193323Sed 74276479Sdim#define DEBUG_TYPE "code-extractor" 75276479Sdim 76193323Sed// Provide a command-line option to aggregate function arguments into a struct 77193323Sed// for functions produced by the code extractor. This is useful when converting 78193323Sed// extracted functions to pthread-based code, as only one argument (void*) can 79193323Sed// be passed in to pthread_create(). 80193323Sedstatic cl::opt<bool> 81193323SedAggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 82193323Sed cl::desc("Aggregate arguments to code-extracted functions")); 83193323Sed 84341825Sdim/// Test whether a block is valid for extraction. 85341825Sdimstatic bool isBlockValidForExtraction(const BasicBlock &BB, 86341825Sdim const SetVector<BasicBlock *> &Result, 87341825Sdim bool AllowVarArgs, bool AllowAlloca) { 88321369Sdim // taking the address of a basic block moved to another function is illegal 89321369Sdim if (BB.hasAddressTaken()) 90321369Sdim return false; 91193323Sed 92321369Sdim // don't hoist code that uses another basicblock address, as it's likely to 93321369Sdim // lead to unexpected behavior, like cross-function jumps 94321369Sdim SmallPtrSet<User const *, 16> Visited; 95321369Sdim SmallVector<User const *, 16> ToVisit; 96321369Sdim 97321369Sdim for (Instruction const &Inst : BB) 98321369Sdim ToVisit.push_back(&Inst); 99321369Sdim 100321369Sdim while (!ToVisit.empty()) { 101321369Sdim User const *Curr = ToVisit.pop_back_val(); 102321369Sdim if (!Visited.insert(Curr).second) 103321369Sdim continue; 104321369Sdim if (isa<BlockAddress const>(Curr)) 105321369Sdim return false; // even a reference to self is likely to be not compatible 106321369Sdim 107321369Sdim if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB) 108321369Sdim continue; 109321369Sdim 110321369Sdim for (auto const &U : Curr->operands()) { 111321369Sdim if (auto *UU = dyn_cast<User>(U)) 112321369Sdim ToVisit.push_back(UU); 113321369Sdim } 114321369Sdim } 115321369Sdim 116341825Sdim // If explicitly requested, allow vastart and alloca. For invoke instructions 117341825Sdim // verify that extraction is valid. 118239462Sdim for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { 119341825Sdim if (isa<AllocaInst>(I)) { 120341825Sdim if (!AllowAlloca) 121341825Sdim return false; 122341825Sdim continue; 123341825Sdim } 124341825Sdim 125341825Sdim if (const auto *II = dyn_cast<InvokeInst>(I)) { 126341825Sdim // Unwind destination (either a landingpad, catchswitch, or cleanuppad) 127341825Sdim // must be a part of the subgraph which is being extracted. 128341825Sdim if (auto *UBB = II->getUnwindDest()) 129341825Sdim if (!Result.count(UBB)) 130341825Sdim return false; 131341825Sdim continue; 132341825Sdim } 133341825Sdim 134341825Sdim // All catch handlers of a catchswitch instruction as well as the unwind 135341825Sdim // destination must be in the subgraph. 136341825Sdim if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) { 137341825Sdim if (auto *UBB = CSI->getUnwindDest()) 138341825Sdim if (!Result.count(UBB)) 139341825Sdim return false; 140341825Sdim for (auto *HBB : CSI->handlers()) 141341825Sdim if (!Result.count(const_cast<BasicBlock*>(HBB))) 142341825Sdim return false; 143341825Sdim continue; 144341825Sdim } 145341825Sdim 146341825Sdim // Make sure that entire catch handler is within subgraph. It is sufficient 147341825Sdim // to check that catch return's block is in the list. 148341825Sdim if (const auto *CPI = dyn_cast<CatchPadInst>(I)) { 149341825Sdim for (const auto *U : CPI->users()) 150341825Sdim if (const auto *CRI = dyn_cast<CatchReturnInst>(U)) 151341825Sdim if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) 152341825Sdim return false; 153341825Sdim continue; 154341825Sdim } 155341825Sdim 156341825Sdim // And do similar checks for cleanup handler - the entire handler must be 157341825Sdim // in subgraph which is going to be extracted. For cleanup return should 158341825Sdim // additionally check that the unwind destination is also in the subgraph. 159341825Sdim if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) { 160341825Sdim for (const auto *U : CPI->users()) 161341825Sdim if (const auto *CRI = dyn_cast<CleanupReturnInst>(U)) 162341825Sdim if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) 163341825Sdim return false; 164341825Sdim continue; 165341825Sdim } 166341825Sdim if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) { 167341825Sdim if (auto *UBB = CRI->getUnwindDest()) 168341825Sdim if (!Result.count(UBB)) 169341825Sdim return false; 170341825Sdim continue; 171341825Sdim } 172341825Sdim 173344779Sdim if (const CallInst *CI = dyn_cast<CallInst>(I)) { 174344779Sdim if (const Function *F = CI->getCalledFunction()) { 175344779Sdim auto IID = F->getIntrinsicID(); 176344779Sdim if (IID == Intrinsic::vastart) { 177327952Sdim if (AllowVarArgs) 178327952Sdim continue; 179327952Sdim else 180327952Sdim return false; 181327952Sdim } 182344779Sdim 183344779Sdim // Currently, we miscompile outlined copies of eh_typid_for. There are 184344779Sdim // proposals for fixing this in llvm.org/PR39545. 185344779Sdim if (IID == Intrinsic::eh_typeid_for) 186344779Sdim return false; 187344779Sdim } 188344779Sdim } 189239462Sdim } 190193323Sed 191239462Sdim return true; 192239462Sdim} 193193323Sed 194341825Sdim/// Build a set of blocks to extract if the input blocks are viable. 195321369Sdimstatic SetVector<BasicBlock *> 196327952SdimbuildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 197341825Sdim bool AllowVarArgs, bool AllowAlloca) { 198321369Sdim assert(!BBs.empty() && "The set of blocks to extract must be non-empty"); 199239462Sdim SetVector<BasicBlock *> Result; 200193323Sed 201239462Sdim // Loop over the blocks, adding them to our set-vector, and aborting with an 202239462Sdim // empty set if we encounter invalid blocks. 203321369Sdim for (BasicBlock *BB : BBs) { 204321369Sdim // If this block is dead, don't process it. 205321369Sdim if (DT && !DT->isReachableFromEntry(BB)) 206321369Sdim continue; 207321369Sdim 208321369Sdim if (!Result.insert(BB)) 209239462Sdim llvm_unreachable("Repeated basic blocks in extraction input"); 210341825Sdim } 211341825Sdim 212353358Sdim LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName() 213353358Sdim << '\n'); 214353358Sdim 215341825Sdim for (auto *BB : Result) { 216341825Sdim if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca)) 217341825Sdim return {}; 218341825Sdim 219341825Sdim // Make sure that the first block is not a landing pad. 220341825Sdim if (BB == Result.front()) { 221341825Sdim if (BB->isEHPad()) { 222341825Sdim LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n"); 223341825Sdim return {}; 224341825Sdim } 225341825Sdim continue; 226193323Sed } 227341825Sdim 228341825Sdim // All blocks other than the first must not have predecessors outside of 229341825Sdim // the subgraph which is being extracted. 230341825Sdim for (auto *PBB : predecessors(BB)) 231341825Sdim if (!Result.count(PBB)) { 232353358Sdim LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from " 233353358Sdim "outside the region except for the first block!\n" 234353358Sdim << "Problematic source BB: " << BB->getName() << "\n" 235353358Sdim << "Problematic destination BB: " << PBB->getName() 236353358Sdim << "\n"); 237341825Sdim return {}; 238341825Sdim } 239321369Sdim } 240193323Sed 241239462Sdim return Result; 242239462Sdim} 243193323Sed 244239462SdimCodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 245314564Sdim bool AggregateArgs, BlockFrequencyInfo *BFI, 246353358Sdim BranchProbabilityInfo *BPI, AssumptionCache *AC, 247353358Sdim bool AllowVarArgs, bool AllowAlloca, 248353358Sdim std::string Suffix) 249314564Sdim : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), 250353358Sdim BPI(BPI), AC(AC), AllowVarArgs(AllowVarArgs), 251344779Sdim Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)), 252344779Sdim Suffix(Suffix) {} 253239462Sdim 254314564SdimCodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs, 255314564Sdim BlockFrequencyInfo *BFI, 256353358Sdim BranchProbabilityInfo *BPI, AssumptionCache *AC, 257353358Sdim std::string Suffix) 258314564Sdim : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), 259353358Sdim BPI(BPI), AC(AC), AllowVarArgs(false), 260327952Sdim Blocks(buildExtractionBlockSet(L.getBlocks(), &DT, 261341825Sdim /* AllowVarArgs */ false, 262344779Sdim /* AllowAlloca */ false)), 263344779Sdim Suffix(Suffix) {} 264239462Sdim 265239462Sdim/// definedInRegion - Return true if the specified value is defined in the 266239462Sdim/// extracted region. 267239462Sdimstatic bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { 268239462Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 269239462Sdim if (Blocks.count(I->getParent())) 270239462Sdim return true; 271239462Sdim return false; 272239462Sdim} 273239462Sdim 274239462Sdim/// definedInCaller - Return true if the specified value is defined in the 275239462Sdim/// function being code extracted, but not in the region being extracted. 276239462Sdim/// These values must be passed in as live-ins to the function. 277239462Sdimstatic bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { 278239462Sdim if (isa<Argument>(V)) return true; 279239462Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 280239462Sdim if (!Blocks.count(I->getParent())) 281239462Sdim return true; 282239462Sdim return false; 283239462Sdim} 284239462Sdim 285321369Sdimstatic BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) { 286321369Sdim BasicBlock *CommonExitBlock = nullptr; 287321369Sdim auto hasNonCommonExitSucc = [&](BasicBlock *Block) { 288321369Sdim for (auto *Succ : successors(Block)) { 289321369Sdim // Internal edges, ok. 290321369Sdim if (Blocks.count(Succ)) 291321369Sdim continue; 292321369Sdim if (!CommonExitBlock) { 293321369Sdim CommonExitBlock = Succ; 294321369Sdim continue; 295321369Sdim } 296321369Sdim if (CommonExitBlock == Succ) 297321369Sdim continue; 298321369Sdim 299321369Sdim return true; 300321369Sdim } 301321369Sdim return false; 302321369Sdim }; 303321369Sdim 304321369Sdim if (any_of(Blocks, hasNonCommonExitSucc)) 305321369Sdim return nullptr; 306321369Sdim 307321369Sdim return CommonExitBlock; 308321369Sdim} 309321369Sdim 310321369Sdimbool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers( 311321369Sdim Instruction *Addr) const { 312321369Sdim AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets()); 313321369Sdim Function *Func = (*Blocks.begin())->getParent(); 314321369Sdim for (BasicBlock &BB : *Func) { 315321369Sdim if (Blocks.count(&BB)) 316321369Sdim continue; 317321369Sdim for (Instruction &II : BB) { 318321369Sdim if (isa<DbgInfoIntrinsic>(II)) 319321369Sdim continue; 320321369Sdim 321321369Sdim unsigned Opcode = II.getOpcode(); 322321369Sdim Value *MemAddr = nullptr; 323321369Sdim switch (Opcode) { 324321369Sdim case Instruction::Store: 325321369Sdim case Instruction::Load: { 326321369Sdim if (Opcode == Instruction::Store) { 327321369Sdim StoreInst *SI = cast<StoreInst>(&II); 328321369Sdim MemAddr = SI->getPointerOperand(); 329321369Sdim } else { 330321369Sdim LoadInst *LI = cast<LoadInst>(&II); 331321369Sdim MemAddr = LI->getPointerOperand(); 332321369Sdim } 333321369Sdim // Global variable can not be aliased with locals. 334321369Sdim if (dyn_cast<Constant>(MemAddr)) 335321369Sdim break; 336321369Sdim Value *Base = MemAddr->stripInBoundsConstantOffsets(); 337353358Sdim if (!isa<AllocaInst>(Base) || Base == AI) 338321369Sdim return false; 339321369Sdim break; 340321369Sdim } 341321369Sdim default: { 342321369Sdim IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II); 343321369Sdim if (IntrInst) { 344344779Sdim if (IntrInst->isLifetimeStartOrEnd()) 345321369Sdim break; 346321369Sdim return false; 347321369Sdim } 348321369Sdim // Treat all the other cases conservatively if it has side effects. 349321369Sdim if (II.mayHaveSideEffects()) 350321369Sdim return false; 351321369Sdim } 352321369Sdim } 353321369Sdim } 354321369Sdim } 355321369Sdim 356321369Sdim return true; 357321369Sdim} 358321369Sdim 359321369SdimBasicBlock * 360321369SdimCodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) { 361321369Sdim BasicBlock *SinglePredFromOutlineRegion = nullptr; 362321369Sdim assert(!Blocks.count(CommonExitBlock) && 363321369Sdim "Expect a block outside the region!"); 364321369Sdim for (auto *Pred : predecessors(CommonExitBlock)) { 365321369Sdim if (!Blocks.count(Pred)) 366321369Sdim continue; 367321369Sdim if (!SinglePredFromOutlineRegion) { 368321369Sdim SinglePredFromOutlineRegion = Pred; 369321369Sdim } else if (SinglePredFromOutlineRegion != Pred) { 370321369Sdim SinglePredFromOutlineRegion = nullptr; 371321369Sdim break; 372321369Sdim } 373321369Sdim } 374321369Sdim 375321369Sdim if (SinglePredFromOutlineRegion) 376321369Sdim return SinglePredFromOutlineRegion; 377321369Sdim 378321369Sdim#ifndef NDEBUG 379321369Sdim auto getFirstPHI = [](BasicBlock *BB) { 380321369Sdim BasicBlock::iterator I = BB->begin(); 381321369Sdim PHINode *FirstPhi = nullptr; 382321369Sdim while (I != BB->end()) { 383321369Sdim PHINode *Phi = dyn_cast<PHINode>(I); 384321369Sdim if (!Phi) 385321369Sdim break; 386321369Sdim if (!FirstPhi) { 387321369Sdim FirstPhi = Phi; 388321369Sdim break; 389321369Sdim } 390321369Sdim } 391321369Sdim return FirstPhi; 392321369Sdim }; 393321369Sdim // If there are any phi nodes, the single pred either exists or has already 394321369Sdim // be created before code extraction. 395321369Sdim assert(!getFirstPHI(CommonExitBlock) && "Phi not expected"); 396321369Sdim#endif 397321369Sdim 398321369Sdim BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock( 399321369Sdim CommonExitBlock->getFirstNonPHI()->getIterator()); 400321369Sdim 401327952Sdim for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock); 402327952Sdim PI != PE;) { 403327952Sdim BasicBlock *Pred = *PI++; 404321369Sdim if (Blocks.count(Pred)) 405321369Sdim continue; 406321369Sdim Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock); 407321369Sdim } 408321369Sdim // Now add the old exit block to the outline region. 409321369Sdim Blocks.insert(CommonExitBlock); 410321369Sdim return CommonExitBlock; 411321369Sdim} 412321369Sdim 413353358Sdim// Find the pair of life time markers for address 'Addr' that are either 414353358Sdim// defined inside the outline region or can legally be shrinkwrapped into the 415353358Sdim// outline region. If there are not other untracked uses of the address, return 416353358Sdim// the pair of markers if found; otherwise return a pair of nullptr. 417353358SdimCodeExtractor::LifetimeMarkerInfo 418353358SdimCodeExtractor::getLifetimeMarkers(Instruction *Addr, 419353358Sdim BasicBlock *ExitBlock) const { 420353358Sdim LifetimeMarkerInfo Info; 421353358Sdim 422353358Sdim for (User *U : Addr->users()) { 423353358Sdim IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U); 424353358Sdim if (IntrInst) { 425353358Sdim if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) { 426353358Sdim // Do not handle the case where Addr has multiple start markers. 427353358Sdim if (Info.LifeStart) 428353358Sdim return {}; 429353358Sdim Info.LifeStart = IntrInst; 430353358Sdim } 431353358Sdim if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) { 432353358Sdim if (Info.LifeEnd) 433353358Sdim return {}; 434353358Sdim Info.LifeEnd = IntrInst; 435353358Sdim } 436353358Sdim continue; 437353358Sdim } 438353358Sdim // Find untracked uses of the address, bail. 439353358Sdim if (!definedInRegion(Blocks, U)) 440353358Sdim return {}; 441353358Sdim } 442353358Sdim 443353358Sdim if (!Info.LifeStart || !Info.LifeEnd) 444353358Sdim return {}; 445353358Sdim 446353358Sdim Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart); 447353358Sdim Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd); 448353358Sdim // Do legality check. 449353358Sdim if ((Info.SinkLifeStart || Info.HoistLifeEnd) && 450353358Sdim !isLegalToShrinkwrapLifetimeMarkers(Addr)) 451353358Sdim return {}; 452353358Sdim 453353358Sdim // Check to see if we have a place to do hoisting, if not, bail. 454353358Sdim if (Info.HoistLifeEnd && !ExitBlock) 455353358Sdim return {}; 456353358Sdim 457353358Sdim return Info; 458353358Sdim} 459353358Sdim 460321369Sdimvoid CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, 461321369Sdim BasicBlock *&ExitBlock) const { 462321369Sdim Function *Func = (*Blocks.begin())->getParent(); 463321369Sdim ExitBlock = getCommonExitBlock(Blocks); 464321369Sdim 465353358Sdim auto moveOrIgnoreLifetimeMarkers = 466353358Sdim [&](const LifetimeMarkerInfo &LMI) -> bool { 467353358Sdim if (!LMI.LifeStart) 468353358Sdim return false; 469353358Sdim if (LMI.SinkLifeStart) { 470353358Sdim LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart 471353358Sdim << "\n"); 472353358Sdim SinkCands.insert(LMI.LifeStart); 473353358Sdim } 474353358Sdim if (LMI.HoistLifeEnd) { 475353358Sdim LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n"); 476353358Sdim HoistCands.insert(LMI.LifeEnd); 477353358Sdim } 478353358Sdim return true; 479353358Sdim }; 480353358Sdim 481321369Sdim for (BasicBlock &BB : *Func) { 482321369Sdim if (Blocks.count(&BB)) 483321369Sdim continue; 484321369Sdim for (Instruction &II : BB) { 485321369Sdim auto *AI = dyn_cast<AllocaInst>(&II); 486321369Sdim if (!AI) 487321369Sdim continue; 488321369Sdim 489353358Sdim LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(AI, ExitBlock); 490353358Sdim bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo); 491353358Sdim if (Moved) { 492353358Sdim LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n"); 493321369Sdim SinkCands.insert(AI); 494321369Sdim continue; 495321369Sdim } 496321369Sdim 497353358Sdim // Follow any bitcasts. 498353358Sdim SmallVector<Instruction *, 2> Bitcasts; 499353358Sdim SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo; 500321369Sdim for (User *U : AI->users()) { 501321369Sdim if (U->stripInBoundsConstantOffsets() == AI) { 502321369Sdim Instruction *Bitcast = cast<Instruction>(U); 503353358Sdim LifetimeMarkerInfo LMI = getLifetimeMarkers(Bitcast, ExitBlock); 504353358Sdim if (LMI.LifeStart) { 505353358Sdim Bitcasts.push_back(Bitcast); 506353358Sdim BitcastLifetimeInfo.push_back(LMI); 507321369Sdim continue; 508321369Sdim } 509321369Sdim } 510321369Sdim 511321369Sdim // Found unknown use of AI. 512321369Sdim if (!definedInRegion(Blocks, U)) { 513353358Sdim Bitcasts.clear(); 514321369Sdim break; 515321369Sdim } 516321369Sdim } 517321369Sdim 518353358Sdim // Either no bitcasts reference the alloca or there are unknown uses. 519353358Sdim if (Bitcasts.empty()) 520353358Sdim continue; 521353358Sdim 522353358Sdim LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n"); 523353358Sdim SinkCands.insert(AI); 524353358Sdim for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) { 525353358Sdim Instruction *BitcastAddr = Bitcasts[I]; 526353358Sdim const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I]; 527353358Sdim assert(LMI.LifeStart && 528353358Sdim "Unsafe to sink bitcast without lifetime markers"); 529353358Sdim moveOrIgnoreLifetimeMarkers(LMI); 530353358Sdim if (!definedInRegion(Blocks, BitcastAddr)) { 531353358Sdim LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr 532353358Sdim << "\n"); 533353358Sdim SinkCands.insert(BitcastAddr); 534353358Sdim } 535321369Sdim } 536321369Sdim } 537321369Sdim } 538321369Sdim} 539321369Sdim 540321369Sdimvoid CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 541321369Sdim const ValueSet &SinkCands) const { 542309124Sdim for (BasicBlock *BB : Blocks) { 543239462Sdim // If a used value is defined outside the region, it's an input. If an 544239462Sdim // instruction is used outside the region, it's an output. 545309124Sdim for (Instruction &II : *BB) { 546309124Sdim for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE; 547321369Sdim ++OI) { 548321369Sdim Value *V = *OI; 549321369Sdim if (!SinkCands.count(V) && definedInCaller(Blocks, V)) 550321369Sdim Inputs.insert(V); 551321369Sdim } 552239462Sdim 553309124Sdim for (User *U : II.users()) 554276479Sdim if (!definedInRegion(Blocks, U)) { 555309124Sdim Outputs.insert(&II); 556239462Sdim break; 557239462Sdim } 558239462Sdim } 559239462Sdim } 560239462Sdim} 561239462Sdim 562344779Sdim/// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside 563344779Sdim/// of the region, we need to split the entry block of the region so that the 564344779Sdim/// PHI node is easier to deal with. 565344779Sdimvoid CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) { 566221345Sdim unsigned NumPredsFromRegion = 0; 567193323Sed unsigned NumPredsOutsideRegion = 0; 568193323Sed 569193323Sed if (Header != &Header->getParent()->getEntryBlock()) { 570193323Sed PHINode *PN = dyn_cast<PHINode>(Header->begin()); 571193323Sed if (!PN) return; // No PHI nodes. 572193323Sed 573193323Sed // If the header node contains any PHI nodes, check to see if there is more 574193323Sed // than one entry from outside the region. If so, we need to sever the 575193323Sed // header block into two. 576193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 577239462Sdim if (Blocks.count(PN->getIncomingBlock(i))) 578221345Sdim ++NumPredsFromRegion; 579193323Sed else 580193323Sed ++NumPredsOutsideRegion; 581193323Sed 582193323Sed // If there is one (or fewer) predecessor from outside the region, we don't 583193323Sed // need to do anything special. 584193323Sed if (NumPredsOutsideRegion <= 1) return; 585193323Sed } 586193323Sed 587193323Sed // Otherwise, we need to split the header block into two pieces: one 588193323Sed // containing PHI nodes merging values from outside of the region, and a 589193323Sed // second that contains all of the code for the block and merges back any 590193323Sed // incoming values from inside of the region. 591327952Sdim BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT); 592193323Sed 593193323Sed // We only want to code extract the second block now, and it becomes the new 594193323Sed // header of the region. 595193323Sed BasicBlock *OldPred = Header; 596239462Sdim Blocks.remove(OldPred); 597239462Sdim Blocks.insert(NewBB); 598193323Sed Header = NewBB; 599193323Sed 600193323Sed // Okay, now we need to adjust the PHI nodes and any branches from within the 601193323Sed // region to go to the new header block instead of the old header block. 602221345Sdim if (NumPredsFromRegion) { 603193323Sed PHINode *PN = cast<PHINode>(OldPred->begin()); 604193323Sed // Loop over all of the predecessors of OldPred that are in the region, 605193323Sed // changing them to branch to NewBB instead. 606193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 607239462Sdim if (Blocks.count(PN->getIncomingBlock(i))) { 608344779Sdim Instruction *TI = PN->getIncomingBlock(i)->getTerminator(); 609193323Sed TI->replaceUsesOfWith(OldPred, NewBB); 610193323Sed } 611193323Sed 612221345Sdim // Okay, everything within the region is now branching to the right block, we 613193323Sed // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 614321369Sdim BasicBlock::iterator AfterPHIs; 615193323Sed for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 616193323Sed PHINode *PN = cast<PHINode>(AfterPHIs); 617193323Sed // Create a new PHI node in the new region, which has an incoming value 618193323Sed // from OldPred of PN. 619221345Sdim PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, 620296417Sdim PN->getName() + ".ce", &NewBB->front()); 621321369Sdim PN->replaceAllUsesWith(NewPN); 622193323Sed NewPN->addIncoming(PN, OldPred); 623193323Sed 624193323Sed // Loop over all of the incoming value in PN, moving them to NewPN if they 625193323Sed // are from the extracted region. 626193323Sed for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 627239462Sdim if (Blocks.count(PN->getIncomingBlock(i))) { 628193323Sed NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 629193323Sed PN->removeIncomingValue(i); 630193323Sed --i; 631193323Sed } 632193323Sed } 633193323Sed } 634193323Sed } 635193323Sed} 636193323Sed 637344779Sdim/// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from 638344779Sdim/// outlined region, we split these PHIs on two: one with inputs from region 639344779Sdim/// and other with remaining incoming blocks; then first PHIs are placed in 640344779Sdim/// outlined region. 641344779Sdimvoid CodeExtractor::severSplitPHINodesOfExits( 642344779Sdim const SmallPtrSetImpl<BasicBlock *> &Exits) { 643344779Sdim for (BasicBlock *ExitBB : Exits) { 644344779Sdim BasicBlock *NewBB = nullptr; 645344779Sdim 646344779Sdim for (PHINode &PN : ExitBB->phis()) { 647344779Sdim // Find all incoming values from the outlining region. 648344779Sdim SmallVector<unsigned, 2> IncomingVals; 649344779Sdim for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i) 650344779Sdim if (Blocks.count(PN.getIncomingBlock(i))) 651344779Sdim IncomingVals.push_back(i); 652344779Sdim 653344779Sdim // Do not process PHI if there is one (or fewer) predecessor from region. 654344779Sdim // If PHI has exactly one predecessor from region, only this one incoming 655344779Sdim // will be replaced on codeRepl block, so it should be safe to skip PHI. 656344779Sdim if (IncomingVals.size() <= 1) 657344779Sdim continue; 658344779Sdim 659344779Sdim // Create block for new PHIs and add it to the list of outlined if it 660344779Sdim // wasn't done before. 661344779Sdim if (!NewBB) { 662344779Sdim NewBB = BasicBlock::Create(ExitBB->getContext(), 663344779Sdim ExitBB->getName() + ".split", 664344779Sdim ExitBB->getParent(), ExitBB); 665344779Sdim SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB), 666344779Sdim pred_end(ExitBB)); 667344779Sdim for (BasicBlock *PredBB : Preds) 668344779Sdim if (Blocks.count(PredBB)) 669344779Sdim PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB); 670344779Sdim BranchInst::Create(ExitBB, NewBB); 671344779Sdim Blocks.insert(NewBB); 672344779Sdim } 673344779Sdim 674344779Sdim // Split this PHI. 675344779Sdim PHINode *NewPN = 676344779Sdim PHINode::Create(PN.getType(), IncomingVals.size(), 677344779Sdim PN.getName() + ".ce", NewBB->getFirstNonPHI()); 678344779Sdim for (unsigned i : IncomingVals) 679344779Sdim NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i)); 680344779Sdim for (unsigned i : reverse(IncomingVals)) 681344779Sdim PN.removeIncomingValue(i, false); 682344779Sdim PN.addIncoming(NewPN, NewBB); 683344779Sdim } 684344779Sdim } 685344779Sdim} 686344779Sdim 687193323Sedvoid CodeExtractor::splitReturnBlocks() { 688309124Sdim for (BasicBlock *Block : Blocks) 689309124Sdim if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) { 690296417Sdim BasicBlock *New = 691309124Sdim Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret"); 692198090Srdivacky if (DT) { 693218893Sdim // Old dominates New. New node dominates all other nodes dominated 694218893Sdim // by Old. 695309124Sdim DomTreeNode *OldNode = DT->getNode(Block); 696309124Sdim SmallVector<DomTreeNode *, 8> Children(OldNode->begin(), 697309124Sdim OldNode->end()); 698198090Srdivacky 699309124Sdim DomTreeNode *NewNode = DT->addNewBlock(New, Block); 700198090Srdivacky 701309124Sdim for (DomTreeNode *I : Children) 702309124Sdim DT->changeImmediateDominator(I, NewNode); 703198090Srdivacky } 704198090Srdivacky } 705193323Sed} 706193323Sed 707193323Sed/// constructFunction - make a function based on inputs and outputs, as follows: 708193323Sed/// f(in0, ..., inN, out0, ..., outN) 709239462SdimFunction *CodeExtractor::constructFunction(const ValueSet &inputs, 710239462Sdim const ValueSet &outputs, 711193323Sed BasicBlock *header, 712193323Sed BasicBlock *newRootNode, 713193323Sed BasicBlock *newHeader, 714193323Sed Function *oldFunction, 715193323Sed Module *M) { 716341825Sdim LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n"); 717341825Sdim LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n"); 718193323Sed 719193323Sed // This function returns unsigned, outputs will go back by reference. 720193323Sed switch (NumExitBlocks) { 721193323Sed case 0: 722198090Srdivacky case 1: RetTy = Type::getVoidTy(header->getContext()); break; 723198090Srdivacky case 2: RetTy = Type::getInt1Ty(header->getContext()); break; 724198090Srdivacky default: RetTy = Type::getInt16Ty(header->getContext()); break; 725193323Sed } 726193323Sed 727327952Sdim std::vector<Type *> paramTy; 728193323Sed 729193323Sed // Add the types of the input values to the function's argument list 730309124Sdim for (Value *value : inputs) { 731341825Sdim LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n"); 732193323Sed paramTy.push_back(value->getType()); 733193323Sed } 734193323Sed 735193323Sed // Add the types of the output values to the function's argument list. 736309124Sdim for (Value *output : outputs) { 737341825Sdim LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n"); 738193323Sed if (AggregateArgs) 739309124Sdim paramTy.push_back(output->getType()); 740193323Sed else 741309124Sdim paramTy.push_back(PointerType::getUnqual(output->getType())); 742193323Sed } 743193323Sed 744341825Sdim LLVM_DEBUG({ 745309124Sdim dbgs() << "Function type: " << *RetTy << " f("; 746309124Sdim for (Type *i : paramTy) 747309124Sdim dbgs() << *i << ", "; 748309124Sdim dbgs() << ")\n"; 749309124Sdim }); 750193323Sed 751288943Sdim StructType *StructTy; 752193323Sed if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 753288943Sdim StructTy = StructType::get(M->getContext(), paramTy); 754193323Sed paramTy.clear(); 755288943Sdim paramTy.push_back(PointerType::getUnqual(StructTy)); 756193323Sed } 757226633Sdim FunctionType *funcType = 758327952Sdim FunctionType::get(RetTy, paramTy, 759327952Sdim AllowVarArgs && oldFunction->isVarArg()); 760193323Sed 761344779Sdim std::string SuffixToUse = 762344779Sdim Suffix.empty() 763344779Sdim ? (header->getName().empty() ? "extracted" : header->getName().str()) 764344779Sdim : Suffix; 765193323Sed // Create the new function 766344779Sdim Function *newFunction = Function::Create( 767344779Sdim funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(), 768344779Sdim oldFunction->getName() + "." + SuffixToUse, M); 769193323Sed // If the old function is no-throw, so is the new one. 770193323Sed if (oldFunction->doesNotThrow()) 771243830Sdim newFunction->setDoesNotThrow(); 772314564Sdim 773314564Sdim // Inherit the uwtable attribute if we need to. 774314564Sdim if (oldFunction->hasUWTable()) 775314564Sdim newFunction->setHasUWTable(); 776314564Sdim 777341825Sdim // Inherit all of the target dependent attributes and white-listed 778341825Sdim // target independent attributes. 779314564Sdim // (e.g. If the extracted region contains a call to an x86.sse 780314564Sdim // instruction we need to make sure that the extracted region has the 781314564Sdim // "target-features" attribute allowing it to be lowered. 782314564Sdim // FIXME: This should be changed to check to see if a specific 783314564Sdim // attribute can not be inherited. 784341825Sdim for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) { 785341825Sdim if (Attr.isStringAttribute()) { 786341825Sdim if (Attr.getKindAsString() == "thunk") 787341825Sdim continue; 788341825Sdim } else 789341825Sdim switch (Attr.getKindAsEnum()) { 790341825Sdim // Those attributes cannot be propagated safely. Explicitly list them 791341825Sdim // here so we get a warning if new attributes are added. This list also 792341825Sdim // includes non-function attributes. 793341825Sdim case Attribute::Alignment: 794341825Sdim case Attribute::AllocSize: 795341825Sdim case Attribute::ArgMemOnly: 796341825Sdim case Attribute::Builtin: 797341825Sdim case Attribute::ByVal: 798341825Sdim case Attribute::Convergent: 799341825Sdim case Attribute::Dereferenceable: 800341825Sdim case Attribute::DereferenceableOrNull: 801341825Sdim case Attribute::InAlloca: 802341825Sdim case Attribute::InReg: 803341825Sdim case Attribute::InaccessibleMemOnly: 804341825Sdim case Attribute::InaccessibleMemOrArgMemOnly: 805341825Sdim case Attribute::JumpTable: 806341825Sdim case Attribute::Naked: 807341825Sdim case Attribute::Nest: 808341825Sdim case Attribute::NoAlias: 809341825Sdim case Attribute::NoBuiltin: 810341825Sdim case Attribute::NoCapture: 811341825Sdim case Attribute::NoReturn: 812353358Sdim case Attribute::NoSync: 813341825Sdim case Attribute::None: 814341825Sdim case Attribute::NonNull: 815341825Sdim case Attribute::ReadNone: 816341825Sdim case Attribute::ReadOnly: 817341825Sdim case Attribute::Returned: 818341825Sdim case Attribute::ReturnsTwice: 819341825Sdim case Attribute::SExt: 820341825Sdim case Attribute::Speculatable: 821341825Sdim case Attribute::StackAlignment: 822341825Sdim case Attribute::StructRet: 823341825Sdim case Attribute::SwiftError: 824341825Sdim case Attribute::SwiftSelf: 825353358Sdim case Attribute::WillReturn: 826341825Sdim case Attribute::WriteOnly: 827341825Sdim case Attribute::ZExt: 828353358Sdim case Attribute::ImmArg: 829341825Sdim case Attribute::EndAttrKinds: 830341825Sdim continue; 831341825Sdim // Those attributes should be safe to propagate to the extracted function. 832341825Sdim case Attribute::AlwaysInline: 833341825Sdim case Attribute::Cold: 834341825Sdim case Attribute::NoRecurse: 835341825Sdim case Attribute::InlineHint: 836341825Sdim case Attribute::MinSize: 837341825Sdim case Attribute::NoDuplicate: 838353358Sdim case Attribute::NoFree: 839341825Sdim case Attribute::NoImplicitFloat: 840341825Sdim case Attribute::NoInline: 841341825Sdim case Attribute::NonLazyBind: 842341825Sdim case Attribute::NoRedZone: 843341825Sdim case Attribute::NoUnwind: 844341825Sdim case Attribute::OptForFuzzing: 845341825Sdim case Attribute::OptimizeNone: 846341825Sdim case Attribute::OptimizeForSize: 847341825Sdim case Attribute::SafeStack: 848341825Sdim case Attribute::ShadowCallStack: 849341825Sdim case Attribute::SanitizeAddress: 850341825Sdim case Attribute::SanitizeMemory: 851341825Sdim case Attribute::SanitizeThread: 852341825Sdim case Attribute::SanitizeHWAddress: 853353358Sdim case Attribute::SanitizeMemTag: 854344779Sdim case Attribute::SpeculativeLoadHardening: 855341825Sdim case Attribute::StackProtect: 856341825Sdim case Attribute::StackProtectReq: 857341825Sdim case Attribute::StackProtectStrong: 858341825Sdim case Attribute::StrictFP: 859341825Sdim case Attribute::UWTable: 860341825Sdim case Attribute::NoCfCheck: 861341825Sdim break; 862341825Sdim } 863314564Sdim 864341825Sdim newFunction->addFnAttr(Attr); 865341825Sdim } 866193323Sed newFunction->getBasicBlockList().push_back(newRootNode); 867193323Sed 868193323Sed // Create an iterator to name all of the arguments we inserted. 869193323Sed Function::arg_iterator AI = newFunction->arg_begin(); 870193323Sed 871193323Sed // Rewrite all users of the inputs in the extracted region to use the 872193323Sed // arguments (or appropriate addressing into struct) instead. 873193323Sed for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 874193323Sed Value *RewriteVal; 875193323Sed if (AggregateArgs) { 876193323Sed Value *Idx[2]; 877198090Srdivacky Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); 878198090Srdivacky Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); 879344779Sdim Instruction *TI = newFunction->begin()->getTerminator(); 880288943Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 881296417Sdim StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI); 882353358Sdim RewriteVal = new LoadInst(StructTy->getElementType(i), GEP, 883353358Sdim "loadgep_" + inputs[i]->getName(), TI); 884193323Sed } else 885296417Sdim RewriteVal = &*AI++; 886193323Sed 887327952Sdim std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end()); 888309124Sdim for (User *use : Users) 889309124Sdim if (Instruction *inst = dyn_cast<Instruction>(use)) 890239462Sdim if (Blocks.count(inst->getParent())) 891193323Sed inst->replaceUsesOfWith(inputs[i], RewriteVal); 892193323Sed } 893193323Sed 894193323Sed // Set names for input and output arguments. 895193323Sed if (!AggregateArgs) { 896193323Sed AI = newFunction->arg_begin(); 897193323Sed for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 898193323Sed AI->setName(inputs[i]->getName()); 899193323Sed for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 900193323Sed AI->setName(outputs[i]->getName()+".out"); 901193323Sed } 902193323Sed 903193323Sed // Rewrite branches to basic blocks outside of the loop to new dummy blocks 904193323Sed // within the new function. This must be done before we lose track of which 905193323Sed // blocks were originally in the code region. 906327952Sdim std::vector<User *> Users(header->user_begin(), header->user_end()); 907193323Sed for (unsigned i = 0, e = Users.size(); i != e; ++i) 908193323Sed // The BasicBlock which contains the branch is not in the region 909193323Sed // modify the branch target to a new block 910344779Sdim if (Instruction *I = dyn_cast<Instruction>(Users[i])) 911344779Sdim if (I->isTerminator() && !Blocks.count(I->getParent()) && 912344779Sdim I->getParent()->getParent() == oldFunction) 913344779Sdim I->replaceUsesOfWith(header, newHeader); 914193323Sed 915193323Sed return newFunction; 916193323Sed} 917193323Sed 918353358Sdim/// Erase lifetime.start markers which reference inputs to the extraction 919353358Sdim/// region, and insert the referenced memory into \p LifetimesStart. 920353358Sdim/// 921353358Sdim/// The extraction region is defined by a set of blocks (\p Blocks), and a set 922353358Sdim/// of allocas which will be moved from the caller function into the extracted 923353358Sdim/// function (\p SunkAllocas). 924353358Sdimstatic void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks, 925353358Sdim const SetVector<Value *> &SunkAllocas, 926353358Sdim SetVector<Value *> &LifetimesStart) { 927353358Sdim for (BasicBlock *BB : Blocks) { 928353358Sdim for (auto It = BB->begin(), End = BB->end(); It != End;) { 929353358Sdim auto *II = dyn_cast<IntrinsicInst>(&*It); 930353358Sdim ++It; 931353358Sdim if (!II || !II->isLifetimeStartOrEnd()) 932353358Sdim continue; 933353358Sdim 934353358Sdim // Get the memory operand of the lifetime marker. If the underlying 935353358Sdim // object is a sunk alloca, or is otherwise defined in the extraction 936353358Sdim // region, the lifetime marker must not be erased. 937353358Sdim Value *Mem = II->getOperand(1)->stripInBoundsOffsets(); 938353358Sdim if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem)) 939353358Sdim continue; 940353358Sdim 941353358Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start) 942353358Sdim LifetimesStart.insert(Mem); 943353358Sdim II->eraseFromParent(); 944353358Sdim } 945353358Sdim } 946353358Sdim} 947353358Sdim 948353358Sdim/// Insert lifetime start/end markers surrounding the call to the new function 949353358Sdim/// for objects defined in the caller. 950353358Sdimstatic void insertLifetimeMarkersSurroundingCall( 951353358Sdim Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd, 952353358Sdim CallInst *TheCall) { 953353358Sdim LLVMContext &Ctx = M->getContext(); 954353358Sdim auto Int8PtrTy = Type::getInt8PtrTy(Ctx); 955353358Sdim auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1); 956353358Sdim Instruction *Term = TheCall->getParent()->getTerminator(); 957353358Sdim 958353358Sdim // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts 959353358Sdim // needed to satisfy this requirement so they may be reused. 960353358Sdim DenseMap<Value *, Value *> Bitcasts; 961353358Sdim 962353358Sdim // Emit lifetime markers for the pointers given in \p Objects. Insert the 963353358Sdim // markers before the call if \p InsertBefore, and after the call otherwise. 964353358Sdim auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects, 965353358Sdim bool InsertBefore) { 966353358Sdim for (Value *Mem : Objects) { 967353358Sdim assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == 968353358Sdim TheCall->getFunction()) && 969353358Sdim "Input memory not defined in original function"); 970353358Sdim Value *&MemAsI8Ptr = Bitcasts[Mem]; 971353358Sdim if (!MemAsI8Ptr) { 972353358Sdim if (Mem->getType() == Int8PtrTy) 973353358Sdim MemAsI8Ptr = Mem; 974353358Sdim else 975353358Sdim MemAsI8Ptr = 976353358Sdim CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall); 977353358Sdim } 978353358Sdim 979353358Sdim auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr}); 980353358Sdim if (InsertBefore) 981353358Sdim Marker->insertBefore(TheCall); 982353358Sdim else 983353358Sdim Marker->insertBefore(Term); 984353358Sdim } 985353358Sdim }; 986353358Sdim 987353358Sdim if (!LifetimesStart.empty()) { 988353358Sdim auto StartFn = llvm::Intrinsic::getDeclaration( 989353358Sdim M, llvm::Intrinsic::lifetime_start, Int8PtrTy); 990353358Sdim insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true); 991353358Sdim } 992353358Sdim 993353358Sdim if (!LifetimesEnd.empty()) { 994353358Sdim auto EndFn = llvm::Intrinsic::getDeclaration( 995353358Sdim M, llvm::Intrinsic::lifetime_end, Int8PtrTy); 996353358Sdim insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false); 997353358Sdim } 998353358Sdim} 999353358Sdim 1000193323Sed/// emitCallAndSwitchStatement - This method sets up the caller side by adding 1001193323Sed/// the call instruction, splitting any PHI nodes in the header block as 1002193323Sed/// necessary. 1003344779SdimCallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction, 1004344779Sdim BasicBlock *codeReplacer, 1005344779Sdim ValueSet &inputs, 1006344779Sdim ValueSet &outputs) { 1007193323Sed // Emit a call to the new function, passing in: *pointer to struct (if 1008193323Sed // aggregating parameters), or plan inputs and allocated memory for outputs 1009327952Sdim std::vector<Value *> params, StructValues, ReloadOutputs, Reloads; 1010193323Sed 1011321369Sdim Module *M = newFunction->getParent(); 1012321369Sdim LLVMContext &Context = M->getContext(); 1013321369Sdim const DataLayout &DL = M->getDataLayout(); 1014344779Sdim CallInst *call = nullptr; 1015321369Sdim 1016193323Sed // Add inputs as params, or to be filled into the struct 1017353358Sdim unsigned ArgNo = 0; 1018353358Sdim SmallVector<unsigned, 1> SwiftErrorArgs; 1019353358Sdim for (Value *input : inputs) { 1020193323Sed if (AggregateArgs) 1021309124Sdim StructValues.push_back(input); 1022353358Sdim else { 1023309124Sdim params.push_back(input); 1024353358Sdim if (input->isSwiftError()) 1025353358Sdim SwiftErrorArgs.push_back(ArgNo); 1026353358Sdim } 1027353358Sdim ++ArgNo; 1028353358Sdim } 1029193323Sed 1030193323Sed // Create allocas for the outputs 1031309124Sdim for (Value *output : outputs) { 1032193323Sed if (AggregateArgs) { 1033309124Sdim StructValues.push_back(output); 1034193323Sed } else { 1035193323Sed AllocaInst *alloca = 1036321369Sdim new AllocaInst(output->getType(), DL.getAllocaAddrSpace(), 1037321369Sdim nullptr, output->getName() + ".loc", 1038321369Sdim &codeReplacer->getParent()->front().front()); 1039193323Sed ReloadOutputs.push_back(alloca); 1040193323Sed params.push_back(alloca); 1041193323Sed } 1042193323Sed } 1043193323Sed 1044288943Sdim StructType *StructArgTy = nullptr; 1045276479Sdim AllocaInst *Struct = nullptr; 1046193323Sed if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 1047327952Sdim std::vector<Type *> ArgTypes; 1048239462Sdim for (ValueSet::iterator v = StructValues.begin(), 1049193323Sed ve = StructValues.end(); v != ve; ++v) 1050193323Sed ArgTypes.push_back((*v)->getType()); 1051193323Sed 1052193323Sed // Allocate a struct at the beginning of this function 1053288943Sdim StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); 1054321369Sdim Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr, 1055321369Sdim "structArg", 1056296417Sdim &codeReplacer->getParent()->front().front()); 1057193323Sed params.push_back(Struct); 1058193323Sed 1059193323Sed for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 1060193323Sed Value *Idx[2]; 1061198090Srdivacky Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1062198090Srdivacky Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); 1063288943Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 1064288943Sdim StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); 1065193323Sed codeReplacer->getInstList().push_back(GEP); 1066193323Sed StoreInst *SI = new StoreInst(StructValues[i], GEP); 1067193323Sed codeReplacer->getInstList().push_back(SI); 1068193323Sed } 1069193323Sed } 1070193323Sed 1071193323Sed // Emit the call to the function 1072344779Sdim call = CallInst::Create(newFunction, params, 1073344779Sdim NumExitBlocks > 1 ? "targetBlock" : ""); 1074327952Sdim // Add debug location to the new call, if the original function has debug 1075327952Sdim // info. In that case, the terminator of the entry block of the extracted 1076327952Sdim // function contains the first debug location of the extracted function, 1077327952Sdim // set in extractCodeRegion. 1078327952Sdim if (codeReplacer->getParent()->getSubprogram()) { 1079327952Sdim if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc()) 1080327952Sdim call->setDebugLoc(DL); 1081327952Sdim } 1082193323Sed codeReplacer->getInstList().push_back(call); 1083193323Sed 1084353358Sdim // Set swifterror parameter attributes. 1085353358Sdim for (unsigned SwiftErrArgNo : SwiftErrorArgs) { 1086353358Sdim call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1087353358Sdim newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1088353358Sdim } 1089353358Sdim 1090193323Sed Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); 1091193323Sed unsigned FirstOut = inputs.size(); 1092193323Sed if (!AggregateArgs) 1093193323Sed std::advance(OutputArgBegin, inputs.size()); 1094193323Sed 1095327952Sdim // Reload the outputs passed in by reference. 1096193323Sed for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 1097276479Sdim Value *Output = nullptr; 1098193323Sed if (AggregateArgs) { 1099193323Sed Value *Idx[2]; 1100198090Srdivacky Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1101198090Srdivacky Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 1102288943Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 1103288943Sdim StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); 1104193323Sed codeReplacer->getInstList().push_back(GEP); 1105193323Sed Output = GEP; 1106193323Sed } else { 1107193323Sed Output = ReloadOutputs[i]; 1108193323Sed } 1109353358Sdim LoadInst *load = new LoadInst(outputs[i]->getType(), Output, 1110353358Sdim outputs[i]->getName() + ".reload"); 1111198090Srdivacky Reloads.push_back(load); 1112193323Sed codeReplacer->getInstList().push_back(load); 1113327952Sdim std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end()); 1114193323Sed for (unsigned u = 0, e = Users.size(); u != e; ++u) { 1115193323Sed Instruction *inst = cast<Instruction>(Users[u]); 1116239462Sdim if (!Blocks.count(inst->getParent())) 1117193323Sed inst->replaceUsesOfWith(outputs[i], load); 1118193323Sed } 1119193323Sed } 1120193323Sed 1121193323Sed // Now we can emit a switch statement using the call as a value. 1122193323Sed SwitchInst *TheSwitch = 1123198090Srdivacky SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), 1124193323Sed codeReplacer, 0, codeReplacer); 1125193323Sed 1126193323Sed // Since there may be multiple exits from the original region, make the new 1127193323Sed // function return an unsigned, switch on that number. This loop iterates 1128193323Sed // over all of the blocks in the extracted region, updating any terminator 1129193323Sed // instructions in the to-be-extracted region that branch to blocks that are 1130193323Sed // not in the region to be extracted. 1131327952Sdim std::map<BasicBlock *, BasicBlock *> ExitBlockMap; 1132193323Sed 1133193323Sed unsigned switchVal = 0; 1134309124Sdim for (BasicBlock *Block : Blocks) { 1135344779Sdim Instruction *TI = Block->getTerminator(); 1136193323Sed for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 1137239462Sdim if (!Blocks.count(TI->getSuccessor(i))) { 1138193323Sed BasicBlock *OldTarget = TI->getSuccessor(i); 1139193323Sed // add a new basic block which returns the appropriate value 1140193323Sed BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 1141193323Sed if (!NewTarget) { 1142193323Sed // If we don't already have an exit stub for this non-extracted 1143193323Sed // destination, create one now! 1144198090Srdivacky NewTarget = BasicBlock::Create(Context, 1145198090Srdivacky OldTarget->getName() + ".exitStub", 1146193323Sed newFunction); 1147193323Sed unsigned SuccNum = switchVal++; 1148193323Sed 1149276479Sdim Value *brVal = nullptr; 1150193323Sed switch (NumExitBlocks) { 1151193323Sed case 0: 1152193323Sed case 1: break; // No value needed. 1153193323Sed case 2: // Conditional branch, return a bool 1154198090Srdivacky brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); 1155193323Sed break; 1156193323Sed default: 1157198090Srdivacky brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); 1158193323Sed break; 1159193323Sed } 1160193323Sed 1161327952Sdim ReturnInst::Create(Context, brVal, NewTarget); 1162193323Sed 1163193323Sed // Update the switch instruction. 1164198090Srdivacky TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), 1165198090Srdivacky SuccNum), 1166193323Sed OldTarget); 1167193323Sed } 1168193323Sed 1169193323Sed // rewrite the original branch instruction with this new target 1170193323Sed TI->setSuccessor(i, NewTarget); 1171193323Sed } 1172193323Sed } 1173193323Sed 1174353358Sdim // Store the arguments right after the definition of output value. 1175353358Sdim // This should be proceeded after creating exit stubs to be ensure that invoke 1176353358Sdim // result restore will be placed in the outlined function. 1177353358Sdim Function::arg_iterator OAI = OutputArgBegin; 1178353358Sdim for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 1179353358Sdim auto *OutI = dyn_cast<Instruction>(outputs[i]); 1180353358Sdim if (!OutI) 1181353358Sdim continue; 1182353358Sdim 1183353358Sdim // Find proper insertion point. 1184353358Sdim BasicBlock::iterator InsertPt; 1185353358Sdim // In case OutI is an invoke, we insert the store at the beginning in the 1186353358Sdim // 'normal destination' BB. Otherwise we insert the store right after OutI. 1187353358Sdim if (auto *InvokeI = dyn_cast<InvokeInst>(OutI)) 1188353358Sdim InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt(); 1189353358Sdim else if (auto *Phi = dyn_cast<PHINode>(OutI)) 1190353358Sdim InsertPt = Phi->getParent()->getFirstInsertionPt(); 1191353358Sdim else 1192353358Sdim InsertPt = std::next(OutI->getIterator()); 1193353358Sdim 1194353358Sdim Instruction *InsertBefore = &*InsertPt; 1195353358Sdim assert((InsertBefore->getFunction() == newFunction || 1196353358Sdim Blocks.count(InsertBefore->getParent())) && 1197353358Sdim "InsertPt should be in new function"); 1198353358Sdim assert(OAI != newFunction->arg_end() && 1199353358Sdim "Number of output arguments should match " 1200353358Sdim "the amount of defined values"); 1201353358Sdim if (AggregateArgs) { 1202353358Sdim Value *Idx[2]; 1203353358Sdim Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1204353358Sdim Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 1205353358Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 1206353358Sdim StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), 1207353358Sdim InsertBefore); 1208353358Sdim new StoreInst(outputs[i], GEP, InsertBefore); 1209353358Sdim // Since there should be only one struct argument aggregating 1210353358Sdim // all the output values, we shouldn't increment OAI, which always 1211353358Sdim // points to the struct argument, in this case. 1212353358Sdim } else { 1213353358Sdim new StoreInst(outputs[i], &*OAI, InsertBefore); 1214353358Sdim ++OAI; 1215353358Sdim } 1216353358Sdim } 1217353358Sdim 1218193323Sed // Now that we've done the deed, simplify the switch instruction. 1219226633Sdim Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 1220193323Sed switch (NumExitBlocks) { 1221193323Sed case 0: 1222193323Sed // There are no successors (the block containing the switch itself), which 1223193323Sed // means that previously this was the last part of the function, and hence 1224193323Sed // this should be rewritten as a `ret' 1225193323Sed 1226193323Sed // Check if the function should return a value 1227202375Srdivacky if (OldFnRetTy->isVoidTy()) { 1228276479Sdim ReturnInst::Create(Context, nullptr, TheSwitch); // Return void 1229193323Sed } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 1230193323Sed // return what we have 1231198090Srdivacky ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); 1232193323Sed } else { 1233193323Sed // Otherwise we must have code extracted an unwind or something, just 1234193323Sed // return whatever we want. 1235341825Sdim ReturnInst::Create(Context, 1236198090Srdivacky Constant::getNullValue(OldFnRetTy), TheSwitch); 1237193323Sed } 1238193323Sed 1239193323Sed TheSwitch->eraseFromParent(); 1240193323Sed break; 1241193323Sed case 1: 1242193323Sed // Only a single destination, change the switch into an unconditional 1243193323Sed // branch. 1244193323Sed BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); 1245193323Sed TheSwitch->eraseFromParent(); 1246193323Sed break; 1247193323Sed case 2: 1248193323Sed BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 1249193323Sed call, TheSwitch); 1250193323Sed TheSwitch->eraseFromParent(); 1251193323Sed break; 1252193323Sed default: 1253193323Sed // Otherwise, make the default destination of the switch instruction be one 1254193323Sed // of the other successors. 1255234353Sdim TheSwitch->setCondition(call); 1256234353Sdim TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); 1257234353Sdim // Remove redundant case 1258261991Sdim TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); 1259193323Sed break; 1260193323Sed } 1261344779Sdim 1262353358Sdim // Insert lifetime markers around the reloads of any output values. The 1263353358Sdim // allocas output values are stored in are only in-use in the codeRepl block. 1264353358Sdim insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call); 1265353358Sdim 1266344779Sdim return call; 1267193323Sed} 1268193323Sed 1269193323Sedvoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 1270239462Sdim Function *oldFunc = (*Blocks.begin())->getParent(); 1271193323Sed Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 1272193323Sed Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 1273193323Sed 1274309124Sdim for (BasicBlock *Block : Blocks) { 1275193323Sed // Delete the basic block from the old function, and the list of blocks 1276309124Sdim oldBlocks.remove(Block); 1277193323Sed 1278193323Sed // Insert this basic block into the new function 1279309124Sdim newBlocks.push_back(Block); 1280353358Sdim 1281353358Sdim // Remove @llvm.assume calls that were moved to the new function from the 1282353358Sdim // old function's assumption cache. 1283353358Sdim if (AC) 1284353358Sdim for (auto &I : *Block) 1285353358Sdim if (match(&I, m_Intrinsic<Intrinsic::assume>())) 1286353358Sdim AC->unregisterAssumption(cast<CallInst>(&I)); 1287193323Sed } 1288193323Sed} 1289193323Sed 1290314564Sdimvoid CodeExtractor::calculateNewCallTerminatorWeights( 1291314564Sdim BasicBlock *CodeReplacer, 1292314564Sdim DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 1293314564Sdim BranchProbabilityInfo *BPI) { 1294327952Sdim using Distribution = BlockFrequencyInfoImplBase::Distribution; 1295327952Sdim using BlockNode = BlockFrequencyInfoImplBase::BlockNode; 1296314564Sdim 1297314564Sdim // Update the branch weights for the exit block. 1298344779Sdim Instruction *TI = CodeReplacer->getTerminator(); 1299314564Sdim SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0); 1300314564Sdim 1301314564Sdim // Block Frequency distribution with dummy node. 1302314564Sdim Distribution BranchDist; 1303314564Sdim 1304314564Sdim // Add each of the frequencies of the successors. 1305314564Sdim for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { 1306314564Sdim BlockNode ExitNode(i); 1307314564Sdim uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency(); 1308314564Sdim if (ExitFreq != 0) 1309314564Sdim BranchDist.addExit(ExitNode, ExitFreq); 1310314564Sdim else 1311314564Sdim BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero()); 1312314564Sdim } 1313314564Sdim 1314314564Sdim // Check for no total weight. 1315314564Sdim if (BranchDist.Total == 0) 1316314564Sdim return; 1317314564Sdim 1318314564Sdim // Normalize the distribution so that they can fit in unsigned. 1319314564Sdim BranchDist.normalize(); 1320314564Sdim 1321314564Sdim // Create normalized branch weights and set the metadata. 1322314564Sdim for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) { 1323314564Sdim const auto &Weight = BranchDist.Weights[I]; 1324314564Sdim 1325314564Sdim // Get the weight and update the current BFI. 1326314564Sdim BranchWeights[Weight.TargetNode.Index] = Weight.Amount; 1327314564Sdim BranchProbability BP(Weight.Amount, BranchDist.Total); 1328314564Sdim BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP); 1329314564Sdim } 1330314564Sdim TI->setMetadata( 1331314564Sdim LLVMContext::MD_prof, 1332314564Sdim MDBuilder(TI->getContext()).createBranchWeights(BranchWeights)); 1333314564Sdim} 1334314564Sdim 1335239462SdimFunction *CodeExtractor::extractCodeRegion() { 1336239462Sdim if (!isEligible()) 1337276479Sdim return nullptr; 1338193323Sed 1339193323Sed // Assumption: this is a single-entry code region, and the header is the first 1340193323Sed // block in the region. 1341239462Sdim BasicBlock *header = *Blocks.begin(); 1342327952Sdim Function *oldFunction = header->getParent(); 1343193323Sed 1344327952Sdim // For functions with varargs, check that varargs handling is only done in the 1345327952Sdim // outlined function, i.e vastart and vaend are only used in outlined blocks. 1346327952Sdim if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) { 1347327952Sdim auto containsVarArgIntrinsic = [](Instruction &I) { 1348327952Sdim if (const CallInst *CI = dyn_cast<CallInst>(&I)) 1349327952Sdim if (const Function *F = CI->getCalledFunction()) 1350327952Sdim return F->getIntrinsicID() == Intrinsic::vastart || 1351327952Sdim F->getIntrinsicID() == Intrinsic::vaend; 1352327952Sdim return false; 1353327952Sdim }; 1354327952Sdim 1355327952Sdim for (auto &BB : *oldFunction) { 1356327952Sdim if (Blocks.count(&BB)) 1357327952Sdim continue; 1358327952Sdim if (llvm::any_of(BB, containsVarArgIntrinsic)) 1359327952Sdim return nullptr; 1360327952Sdim } 1361327952Sdim } 1362327952Sdim ValueSet inputs, outputs, SinkingCands, HoistingCands; 1363327952Sdim BasicBlock *CommonExit = nullptr; 1364327952Sdim 1365314564Sdim // Calculate the entry frequency of the new function before we change the root 1366314564Sdim // block. 1367314564Sdim BlockFrequency EntryFreq; 1368314564Sdim if (BFI) { 1369314564Sdim assert(BPI && "Both BPI and BFI are required to preserve profile info"); 1370314564Sdim for (BasicBlock *Pred : predecessors(header)) { 1371314564Sdim if (Blocks.count(Pred)) 1372314564Sdim continue; 1373314564Sdim EntryFreq += 1374314564Sdim BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header); 1375314564Sdim } 1376314564Sdim } 1377314564Sdim 1378193323Sed // If we have any return instructions in the region, split those blocks so 1379193323Sed // that the return is not in the region. 1380193323Sed splitReturnBlocks(); 1381193323Sed 1382344779Sdim // Calculate the exit blocks for the extracted region and the total exit 1383344779Sdim // weights for each of those blocks. 1384344779Sdim DenseMap<BasicBlock *, BlockFrequency> ExitWeights; 1385344779Sdim SmallPtrSet<BasicBlock *, 1> ExitBlocks; 1386344779Sdim for (BasicBlock *Block : Blocks) { 1387344779Sdim for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE; 1388344779Sdim ++SI) { 1389344779Sdim if (!Blocks.count(*SI)) { 1390344779Sdim // Update the branch weight for this successor. 1391344779Sdim if (BFI) { 1392344779Sdim BlockFrequency &BF = ExitWeights[*SI]; 1393344779Sdim BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI); 1394344779Sdim } 1395344779Sdim ExitBlocks.insert(*SI); 1396344779Sdim } 1397344779Sdim } 1398344779Sdim } 1399344779Sdim NumExitBlocks = ExitBlocks.size(); 1400344779Sdim 1401344779Sdim // If we have to split PHI nodes of the entry or exit blocks, do so now. 1402344779Sdim severSplitPHINodesOfEntry(header); 1403344779Sdim severSplitPHINodesOfExits(ExitBlocks); 1404344779Sdim 1405193323Sed // This takes place of the original loop 1406341825Sdim BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), 1407198090Srdivacky "codeRepl", oldFunction, 1408193323Sed header); 1409193323Sed 1410193323Sed // The new function needs a root node because other nodes can branch to the 1411193323Sed // head of the region, but the entry node of a function cannot have preds. 1412341825Sdim BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 1413198090Srdivacky "newFuncRoot"); 1414327952Sdim auto *BranchI = BranchInst::Create(header); 1415327952Sdim // If the original function has debug info, we have to add a debug location 1416327952Sdim // to the new branch instruction from the artificial entry block. 1417327952Sdim // We use the debug location of the first instruction in the extracted 1418327952Sdim // blocks, as there is no other equivalent line in the source code. 1419327952Sdim if (oldFunction->getSubprogram()) { 1420327952Sdim any_of(Blocks, [&BranchI](const BasicBlock *BB) { 1421327952Sdim return any_of(*BB, [&BranchI](const Instruction &I) { 1422327952Sdim if (!I.getDebugLoc()) 1423327952Sdim return false; 1424327952Sdim BranchI->setDebugLoc(I.getDebugLoc()); 1425327952Sdim return true; 1426327952Sdim }); 1427327952Sdim }); 1428327952Sdim } 1429327952Sdim newFuncRoot->getInstList().push_back(BranchI); 1430193323Sed 1431321369Sdim findAllocas(SinkingCands, HoistingCands, CommonExit); 1432321369Sdim assert(HoistingCands.empty() || CommonExit); 1433321369Sdim 1434193323Sed // Find inputs to, outputs from the code region. 1435321369Sdim findInputsOutputs(inputs, outputs, SinkingCands); 1436193323Sed 1437353358Sdim // Now sink all instructions which only have non-phi uses inside the region. 1438353358Sdim // Group the allocas at the start of the block, so that any bitcast uses of 1439353358Sdim // the allocas are well-defined. 1440353358Sdim AllocaInst *FirstSunkAlloca = nullptr; 1441353358Sdim for (auto *II : SinkingCands) { 1442353358Sdim if (auto *AI = dyn_cast<AllocaInst>(II)) { 1443353358Sdim AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt()); 1444353358Sdim if (!FirstSunkAlloca) 1445353358Sdim FirstSunkAlloca = AI; 1446353358Sdim } 1447353358Sdim } 1448353358Sdim assert((SinkingCands.empty() || FirstSunkAlloca) && 1449353358Sdim "Did not expect a sink candidate without any allocas"); 1450353358Sdim for (auto *II : SinkingCands) { 1451353358Sdim if (!isa<AllocaInst>(II)) { 1452353358Sdim cast<Instruction>(II)->moveAfter(FirstSunkAlloca); 1453353358Sdim } 1454353358Sdim } 1455321369Sdim 1456321369Sdim if (!HoistingCands.empty()) { 1457321369Sdim auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit); 1458321369Sdim Instruction *TI = HoistToBlock->getTerminator(); 1459321369Sdim for (auto *II : HoistingCands) 1460321369Sdim cast<Instruction>(II)->moveBefore(TI); 1461321369Sdim } 1462321369Sdim 1463344779Sdim // Collect objects which are inputs to the extraction region and also 1464353358Sdim // referenced by lifetime start markers within it. The effects of these 1465344779Sdim // markers must be replicated in the calling function to prevent the stack 1466344779Sdim // coloring pass from merging slots which store input objects. 1467353358Sdim ValueSet LifetimesStart; 1468353358Sdim eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart); 1469239462Sdim 1470193323Sed // Construct new function based on inputs/outputs & add allocas for all defs. 1471344779Sdim Function *newFunction = 1472344779Sdim constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer, 1473344779Sdim oldFunction, oldFunction->getParent()); 1474193323Sed 1475314564Sdim // Update the entry count of the function. 1476314564Sdim if (BFI) { 1477341825Sdim auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency()); 1478341825Sdim if (Count.hasValue()) 1479341825Sdim newFunction->setEntryCount( 1480341825Sdim ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME 1481314564Sdim BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency()); 1482314564Sdim } 1483314564Sdim 1484344779Sdim CallInst *TheCall = 1485344779Sdim emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 1486193323Sed 1487193323Sed moveCodeToFunction(newFunction); 1488193323Sed 1489344779Sdim // Replicate the effects of any lifetime start/end markers which referenced 1490344779Sdim // input objects in the extraction region by placing markers around the call. 1491353358Sdim insertLifetimeMarkersSurroundingCall( 1492353358Sdim oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall); 1493344779Sdim 1494341825Sdim // Propagate personality info to the new function if there is one. 1495341825Sdim if (oldFunction->hasPersonalityFn()) 1496341825Sdim newFunction->setPersonalityFn(oldFunction->getPersonalityFn()); 1497341825Sdim 1498314564Sdim // Update the branch weights for the exit block. 1499314564Sdim if (BFI && NumExitBlocks > 1) 1500314564Sdim calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI); 1501314564Sdim 1502344779Sdim // Loop over all of the PHI nodes in the header and exit blocks, and change 1503344779Sdim // any references to the old incoming edge to be the new incoming edge. 1504193323Sed for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 1505193323Sed PHINode *PN = cast<PHINode>(I); 1506193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1507239462Sdim if (!Blocks.count(PN->getIncomingBlock(i))) 1508193323Sed PN->setIncomingBlock(i, newFuncRoot); 1509193323Sed } 1510193323Sed 1511344779Sdim for (BasicBlock *ExitBB : ExitBlocks) 1512344779Sdim for (PHINode &PN : ExitBB->phis()) { 1513344779Sdim Value *IncomingCodeReplacerVal = nullptr; 1514344779Sdim for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 1515344779Sdim // Ignore incoming values from outside of the extracted region. 1516344779Sdim if (!Blocks.count(PN.getIncomingBlock(i))) 1517344779Sdim continue; 1518344779Sdim 1519344779Sdim // Ensure that there is only one incoming value from codeReplacer. 1520344779Sdim if (!IncomingCodeReplacerVal) { 1521344779Sdim PN.setIncomingBlock(i, codeReplacer); 1522344779Sdim IncomingCodeReplacerVal = PN.getIncomingValue(i); 1523344779Sdim } else 1524344779Sdim assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) && 1525344779Sdim "PHI has two incompatbile incoming values from codeRepl"); 1526344779Sdim } 1527193323Sed } 1528193323Sed 1529344779Sdim // Erase debug info intrinsics. Variable updates within the new function are 1530344779Sdim // invisible to debuggers. This could be improved by defining a DISubprogram 1531344779Sdim // for the new function. 1532344779Sdim for (BasicBlock &BB : *newFunction) { 1533344779Sdim auto BlockIt = BB.begin(); 1534344779Sdim // Remove debug info intrinsics from the new function. 1535344779Sdim while (BlockIt != BB.end()) { 1536344779Sdim Instruction *Inst = &*BlockIt; 1537344779Sdim ++BlockIt; 1538344779Sdim if (isa<DbgInfoIntrinsic>(Inst)) 1539344779Sdim Inst->eraseFromParent(); 1540344779Sdim } 1541344779Sdim // Remove debug info intrinsics which refer to values in the new function 1542344779Sdim // from the old function. 1543344779Sdim SmallVector<DbgVariableIntrinsic *, 4> DbgUsers; 1544344779Sdim for (Instruction &I : BB) 1545344779Sdim findDbgUsers(DbgUsers, &I); 1546344779Sdim for (DbgVariableIntrinsic *DVI : DbgUsers) 1547344779Sdim DVI->eraseFromParent(); 1548344779Sdim } 1549344779Sdim 1550344779Sdim // Mark the new function `noreturn` if applicable. Terminators which resume 1551344779Sdim // exception propagation are treated as returning instructions. This is to 1552344779Sdim // avoid inserting traps after calls to outlined functions which unwind. 1553344779Sdim bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) { 1554344779Sdim const Instruction *Term = BB.getTerminator(); 1555344779Sdim return isa<ReturnInst>(Term) || isa<ResumeInst>(Term); 1556344779Sdim }); 1557344779Sdim if (doesNotReturn) 1558344779Sdim newFunction->setDoesNotReturn(); 1559344779Sdim 1560344779Sdim LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) { 1561344779Sdim newFunction->dump(); 1562344779Sdim report_fatal_error("verification of newFunction failed!"); 1563344779Sdim }); 1564344779Sdim LLVM_DEBUG(if (verifyFunction(*oldFunction)) 1565344779Sdim report_fatal_error("verification of oldFunction failed!")); 1566193323Sed return newFunction; 1567193323Sed} 1568