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 } 296360784Sdim if (CommonExitBlock != Succ) 297360784Sdim return true; 298321369Sdim } 299321369Sdim return false; 300321369Sdim }; 301321369Sdim 302321369Sdim if (any_of(Blocks, hasNonCommonExitSucc)) 303321369Sdim return nullptr; 304321369Sdim 305321369Sdim return CommonExitBlock; 306321369Sdim} 307321369Sdim 308360784SdimCodeExtractorAnalysisCache::CodeExtractorAnalysisCache(Function &F) { 309360784Sdim for (BasicBlock &BB : F) { 310360784Sdim for (Instruction &II : BB.instructionsWithoutDebug()) 311360784Sdim if (auto *AI = dyn_cast<AllocaInst>(&II)) 312360784Sdim Allocas.push_back(AI); 313321369Sdim 314360784Sdim findSideEffectInfoForBlock(BB); 315360784Sdim } 316360784Sdim} 317360784Sdim 318360784Sdimvoid CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) { 319360784Sdim for (Instruction &II : BB.instructionsWithoutDebug()) { 320360784Sdim unsigned Opcode = II.getOpcode(); 321360784Sdim Value *MemAddr = nullptr; 322360784Sdim switch (Opcode) { 323360784Sdim case Instruction::Store: 324360784Sdim case Instruction::Load: { 325360784Sdim if (Opcode == Instruction::Store) { 326360784Sdim StoreInst *SI = cast<StoreInst>(&II); 327360784Sdim MemAddr = SI->getPointerOperand(); 328360784Sdim } else { 329360784Sdim LoadInst *LI = cast<LoadInst>(&II); 330360784Sdim MemAddr = LI->getPointerOperand(); 331360784Sdim } 332360784Sdim // Global variable can not be aliased with locals. 333360784Sdim if (dyn_cast<Constant>(MemAddr)) 334321369Sdim break; 335360784Sdim Value *Base = MemAddr->stripInBoundsConstantOffsets(); 336360784Sdim if (!isa<AllocaInst>(Base)) { 337360784Sdim SideEffectingBlocks.insert(&BB); 338360784Sdim return; 339321369Sdim } 340360784Sdim BaseMemAddrs[&BB].insert(Base); 341360784Sdim break; 342360784Sdim } 343360784Sdim default: { 344360784Sdim IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II); 345360784Sdim if (IntrInst) { 346360784Sdim if (IntrInst->isLifetimeStartOrEnd()) 347360784Sdim break; 348360784Sdim SideEffectingBlocks.insert(&BB); 349360784Sdim return; 350321369Sdim } 351360784Sdim // Treat all the other cases conservatively if it has side effects. 352360784Sdim if (II.mayHaveSideEffects()) { 353360784Sdim SideEffectingBlocks.insert(&BB); 354360784Sdim return; 355321369Sdim } 356321369Sdim } 357360784Sdim } 358321369Sdim } 359360784Sdim} 360321369Sdim 361360784Sdimbool CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr( 362360784Sdim BasicBlock &BB, AllocaInst *Addr) const { 363360784Sdim if (SideEffectingBlocks.count(&BB)) 364360784Sdim return true; 365360784Sdim auto It = BaseMemAddrs.find(&BB); 366360784Sdim if (It != BaseMemAddrs.end()) 367360784Sdim return It->second.count(Addr); 368360784Sdim return false; 369360784Sdim} 370360784Sdim 371360784Sdimbool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers( 372360784Sdim const CodeExtractorAnalysisCache &CEAC, Instruction *Addr) const { 373360784Sdim AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets()); 374360784Sdim Function *Func = (*Blocks.begin())->getParent(); 375360784Sdim for (BasicBlock &BB : *Func) { 376360784Sdim if (Blocks.count(&BB)) 377360784Sdim continue; 378360784Sdim if (CEAC.doesBlockContainClobberOfAddr(BB, AI)) 379360784Sdim return false; 380360784Sdim } 381321369Sdim return true; 382321369Sdim} 383321369Sdim 384321369SdimBasicBlock * 385321369SdimCodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) { 386321369Sdim BasicBlock *SinglePredFromOutlineRegion = nullptr; 387321369Sdim assert(!Blocks.count(CommonExitBlock) && 388321369Sdim "Expect a block outside the region!"); 389321369Sdim for (auto *Pred : predecessors(CommonExitBlock)) { 390321369Sdim if (!Blocks.count(Pred)) 391321369Sdim continue; 392321369Sdim if (!SinglePredFromOutlineRegion) { 393321369Sdim SinglePredFromOutlineRegion = Pred; 394321369Sdim } else if (SinglePredFromOutlineRegion != Pred) { 395321369Sdim SinglePredFromOutlineRegion = nullptr; 396321369Sdim break; 397321369Sdim } 398321369Sdim } 399321369Sdim 400321369Sdim if (SinglePredFromOutlineRegion) 401321369Sdim return SinglePredFromOutlineRegion; 402321369Sdim 403321369Sdim#ifndef NDEBUG 404321369Sdim auto getFirstPHI = [](BasicBlock *BB) { 405321369Sdim BasicBlock::iterator I = BB->begin(); 406321369Sdim PHINode *FirstPhi = nullptr; 407321369Sdim while (I != BB->end()) { 408321369Sdim PHINode *Phi = dyn_cast<PHINode>(I); 409321369Sdim if (!Phi) 410321369Sdim break; 411321369Sdim if (!FirstPhi) { 412321369Sdim FirstPhi = Phi; 413321369Sdim break; 414321369Sdim } 415321369Sdim } 416321369Sdim return FirstPhi; 417321369Sdim }; 418321369Sdim // If there are any phi nodes, the single pred either exists or has already 419321369Sdim // be created before code extraction. 420321369Sdim assert(!getFirstPHI(CommonExitBlock) && "Phi not expected"); 421321369Sdim#endif 422321369Sdim 423321369Sdim BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock( 424321369Sdim CommonExitBlock->getFirstNonPHI()->getIterator()); 425321369Sdim 426327952Sdim for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock); 427327952Sdim PI != PE;) { 428327952Sdim BasicBlock *Pred = *PI++; 429321369Sdim if (Blocks.count(Pred)) 430321369Sdim continue; 431321369Sdim Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock); 432321369Sdim } 433321369Sdim // Now add the old exit block to the outline region. 434321369Sdim Blocks.insert(CommonExitBlock); 435321369Sdim return CommonExitBlock; 436321369Sdim} 437321369Sdim 438353358Sdim// Find the pair of life time markers for address 'Addr' that are either 439353358Sdim// defined inside the outline region or can legally be shrinkwrapped into the 440353358Sdim// outline region. If there are not other untracked uses of the address, return 441353358Sdim// the pair of markers if found; otherwise return a pair of nullptr. 442353358SdimCodeExtractor::LifetimeMarkerInfo 443360784SdimCodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 444360784Sdim Instruction *Addr, 445353358Sdim BasicBlock *ExitBlock) const { 446353358Sdim LifetimeMarkerInfo Info; 447353358Sdim 448353358Sdim for (User *U : Addr->users()) { 449353358Sdim IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U); 450353358Sdim if (IntrInst) { 451353358Sdim if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) { 452353358Sdim // Do not handle the case where Addr has multiple start markers. 453353358Sdim if (Info.LifeStart) 454353358Sdim return {}; 455353358Sdim Info.LifeStart = IntrInst; 456353358Sdim } 457353358Sdim if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) { 458353358Sdim if (Info.LifeEnd) 459353358Sdim return {}; 460353358Sdim Info.LifeEnd = IntrInst; 461353358Sdim } 462353358Sdim continue; 463353358Sdim } 464353358Sdim // Find untracked uses of the address, bail. 465353358Sdim if (!definedInRegion(Blocks, U)) 466353358Sdim return {}; 467353358Sdim } 468353358Sdim 469353358Sdim if (!Info.LifeStart || !Info.LifeEnd) 470353358Sdim return {}; 471353358Sdim 472353358Sdim Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart); 473353358Sdim Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd); 474353358Sdim // Do legality check. 475353358Sdim if ((Info.SinkLifeStart || Info.HoistLifeEnd) && 476360784Sdim !isLegalToShrinkwrapLifetimeMarkers(CEAC, Addr)) 477353358Sdim return {}; 478353358Sdim 479353358Sdim // Check to see if we have a place to do hoisting, if not, bail. 480353358Sdim if (Info.HoistLifeEnd && !ExitBlock) 481353358Sdim return {}; 482353358Sdim 483353358Sdim return Info; 484353358Sdim} 485353358Sdim 486360784Sdimvoid CodeExtractor::findAllocas(const CodeExtractorAnalysisCache &CEAC, 487360784Sdim ValueSet &SinkCands, ValueSet &HoistCands, 488321369Sdim BasicBlock *&ExitBlock) const { 489321369Sdim Function *Func = (*Blocks.begin())->getParent(); 490321369Sdim ExitBlock = getCommonExitBlock(Blocks); 491321369Sdim 492353358Sdim auto moveOrIgnoreLifetimeMarkers = 493353358Sdim [&](const LifetimeMarkerInfo &LMI) -> bool { 494353358Sdim if (!LMI.LifeStart) 495353358Sdim return false; 496353358Sdim if (LMI.SinkLifeStart) { 497353358Sdim LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart 498353358Sdim << "\n"); 499353358Sdim SinkCands.insert(LMI.LifeStart); 500353358Sdim } 501353358Sdim if (LMI.HoistLifeEnd) { 502353358Sdim LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n"); 503353358Sdim HoistCands.insert(LMI.LifeEnd); 504353358Sdim } 505353358Sdim return true; 506353358Sdim }; 507353358Sdim 508360784Sdim // Look up allocas in the original function in CodeExtractorAnalysisCache, as 509360784Sdim // this is much faster than walking all the instructions. 510360784Sdim for (AllocaInst *AI : CEAC.getAllocas()) { 511360784Sdim BasicBlock *BB = AI->getParent(); 512360784Sdim if (Blocks.count(BB)) 513321369Sdim continue; 514321369Sdim 515360784Sdim // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca, 516360784Sdim // check whether it is actually still in the original function. 517360784Sdim Function *AIFunc = BB->getParent(); 518360784Sdim if (AIFunc != Func) 519360784Sdim continue; 520321369Sdim 521360784Sdim LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock); 522360784Sdim bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo); 523360784Sdim if (Moved) { 524360784Sdim LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n"); 525360784Sdim SinkCands.insert(AI); 526360784Sdim continue; 527360784Sdim } 528321369Sdim 529360784Sdim // Follow any bitcasts. 530360784Sdim SmallVector<Instruction *, 2> Bitcasts; 531360784Sdim SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo; 532360784Sdim for (User *U : AI->users()) { 533360784Sdim if (U->stripInBoundsConstantOffsets() == AI) { 534360784Sdim Instruction *Bitcast = cast<Instruction>(U); 535360784Sdim LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock); 536360784Sdim if (LMI.LifeStart) { 537360784Sdim Bitcasts.push_back(Bitcast); 538360784Sdim BitcastLifetimeInfo.push_back(LMI); 539360784Sdim continue; 540321369Sdim } 541321369Sdim } 542321369Sdim 543360784Sdim // Found unknown use of AI. 544360784Sdim if (!definedInRegion(Blocks, U)) { 545360784Sdim Bitcasts.clear(); 546360784Sdim break; 547360784Sdim } 548360784Sdim } 549353358Sdim 550360784Sdim // Either no bitcasts reference the alloca or there are unknown uses. 551360784Sdim if (Bitcasts.empty()) 552360784Sdim continue; 553360784Sdim 554360784Sdim LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n"); 555360784Sdim SinkCands.insert(AI); 556360784Sdim for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) { 557360784Sdim Instruction *BitcastAddr = Bitcasts[I]; 558360784Sdim const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I]; 559360784Sdim assert(LMI.LifeStart && 560360784Sdim "Unsafe to sink bitcast without lifetime markers"); 561360784Sdim moveOrIgnoreLifetimeMarkers(LMI); 562360784Sdim if (!definedInRegion(Blocks, BitcastAddr)) { 563360784Sdim LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr 564360784Sdim << "\n"); 565360784Sdim SinkCands.insert(BitcastAddr); 566321369Sdim } 567321369Sdim } 568321369Sdim } 569321369Sdim} 570321369Sdim 571360784Sdimbool CodeExtractor::isEligible() const { 572360784Sdim if (Blocks.empty()) 573360784Sdim return false; 574360784Sdim BasicBlock *Header = *Blocks.begin(); 575360784Sdim Function *F = Header->getParent(); 576360784Sdim 577360784Sdim // For functions with varargs, check that varargs handling is only done in the 578360784Sdim // outlined function, i.e vastart and vaend are only used in outlined blocks. 579360784Sdim if (AllowVarArgs && F->getFunctionType()->isVarArg()) { 580360784Sdim auto containsVarArgIntrinsic = [](const Instruction &I) { 581360784Sdim if (const CallInst *CI = dyn_cast<CallInst>(&I)) 582360784Sdim if (const Function *Callee = CI->getCalledFunction()) 583360784Sdim return Callee->getIntrinsicID() == Intrinsic::vastart || 584360784Sdim Callee->getIntrinsicID() == Intrinsic::vaend; 585360784Sdim return false; 586360784Sdim }; 587360784Sdim 588360784Sdim for (auto &BB : *F) { 589360784Sdim if (Blocks.count(&BB)) 590360784Sdim continue; 591360784Sdim if (llvm::any_of(BB, containsVarArgIntrinsic)) 592360784Sdim return false; 593360784Sdim } 594360784Sdim } 595360784Sdim return true; 596360784Sdim} 597360784Sdim 598321369Sdimvoid CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 599321369Sdim const ValueSet &SinkCands) const { 600309124Sdim for (BasicBlock *BB : Blocks) { 601239462Sdim // If a used value is defined outside the region, it's an input. If an 602239462Sdim // instruction is used outside the region, it's an output. 603309124Sdim for (Instruction &II : *BB) { 604360784Sdim for (auto &OI : II.operands()) { 605360784Sdim Value *V = OI; 606321369Sdim if (!SinkCands.count(V) && definedInCaller(Blocks, V)) 607321369Sdim Inputs.insert(V); 608321369Sdim } 609239462Sdim 610309124Sdim for (User *U : II.users()) 611276479Sdim if (!definedInRegion(Blocks, U)) { 612309124Sdim Outputs.insert(&II); 613239462Sdim break; 614239462Sdim } 615239462Sdim } 616239462Sdim } 617239462Sdim} 618239462Sdim 619344779Sdim/// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside 620344779Sdim/// of the region, we need to split the entry block of the region so that the 621344779Sdim/// PHI node is easier to deal with. 622344779Sdimvoid CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) { 623221345Sdim unsigned NumPredsFromRegion = 0; 624193323Sed unsigned NumPredsOutsideRegion = 0; 625193323Sed 626193323Sed if (Header != &Header->getParent()->getEntryBlock()) { 627193323Sed PHINode *PN = dyn_cast<PHINode>(Header->begin()); 628193323Sed if (!PN) return; // No PHI nodes. 629193323Sed 630193323Sed // If the header node contains any PHI nodes, check to see if there is more 631193323Sed // than one entry from outside the region. If so, we need to sever the 632193323Sed // header block into two. 633193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 634239462Sdim if (Blocks.count(PN->getIncomingBlock(i))) 635221345Sdim ++NumPredsFromRegion; 636193323Sed else 637193323Sed ++NumPredsOutsideRegion; 638193323Sed 639193323Sed // If there is one (or fewer) predecessor from outside the region, we don't 640193323Sed // need to do anything special. 641193323Sed if (NumPredsOutsideRegion <= 1) return; 642193323Sed } 643193323Sed 644193323Sed // Otherwise, we need to split the header block into two pieces: one 645193323Sed // containing PHI nodes merging values from outside of the region, and a 646193323Sed // second that contains all of the code for the block and merges back any 647193323Sed // incoming values from inside of the region. 648327952Sdim BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT); 649193323Sed 650193323Sed // We only want to code extract the second block now, and it becomes the new 651193323Sed // header of the region. 652193323Sed BasicBlock *OldPred = Header; 653239462Sdim Blocks.remove(OldPred); 654239462Sdim Blocks.insert(NewBB); 655193323Sed Header = NewBB; 656193323Sed 657193323Sed // Okay, now we need to adjust the PHI nodes and any branches from within the 658193323Sed // region to go to the new header block instead of the old header block. 659221345Sdim if (NumPredsFromRegion) { 660193323Sed PHINode *PN = cast<PHINode>(OldPred->begin()); 661193323Sed // Loop over all of the predecessors of OldPred that are in the region, 662193323Sed // changing them to branch to NewBB instead. 663193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 664239462Sdim if (Blocks.count(PN->getIncomingBlock(i))) { 665344779Sdim Instruction *TI = PN->getIncomingBlock(i)->getTerminator(); 666193323Sed TI->replaceUsesOfWith(OldPred, NewBB); 667193323Sed } 668193323Sed 669221345Sdim // Okay, everything within the region is now branching to the right block, we 670193323Sed // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 671321369Sdim BasicBlock::iterator AfterPHIs; 672193323Sed for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 673193323Sed PHINode *PN = cast<PHINode>(AfterPHIs); 674193323Sed // Create a new PHI node in the new region, which has an incoming value 675193323Sed // from OldPred of PN. 676221345Sdim PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, 677296417Sdim PN->getName() + ".ce", &NewBB->front()); 678321369Sdim PN->replaceAllUsesWith(NewPN); 679193323Sed NewPN->addIncoming(PN, OldPred); 680193323Sed 681193323Sed // Loop over all of the incoming value in PN, moving them to NewPN if they 682193323Sed // are from the extracted region. 683193323Sed for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 684239462Sdim if (Blocks.count(PN->getIncomingBlock(i))) { 685193323Sed NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 686193323Sed PN->removeIncomingValue(i); 687193323Sed --i; 688193323Sed } 689193323Sed } 690193323Sed } 691193323Sed } 692193323Sed} 693193323Sed 694344779Sdim/// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from 695344779Sdim/// outlined region, we split these PHIs on two: one with inputs from region 696344779Sdim/// and other with remaining incoming blocks; then first PHIs are placed in 697344779Sdim/// outlined region. 698344779Sdimvoid CodeExtractor::severSplitPHINodesOfExits( 699344779Sdim const SmallPtrSetImpl<BasicBlock *> &Exits) { 700344779Sdim for (BasicBlock *ExitBB : Exits) { 701344779Sdim BasicBlock *NewBB = nullptr; 702344779Sdim 703344779Sdim for (PHINode &PN : ExitBB->phis()) { 704344779Sdim // Find all incoming values from the outlining region. 705344779Sdim SmallVector<unsigned, 2> IncomingVals; 706344779Sdim for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i) 707344779Sdim if (Blocks.count(PN.getIncomingBlock(i))) 708344779Sdim IncomingVals.push_back(i); 709344779Sdim 710344779Sdim // Do not process PHI if there is one (or fewer) predecessor from region. 711344779Sdim // If PHI has exactly one predecessor from region, only this one incoming 712344779Sdim // will be replaced on codeRepl block, so it should be safe to skip PHI. 713344779Sdim if (IncomingVals.size() <= 1) 714344779Sdim continue; 715344779Sdim 716344779Sdim // Create block for new PHIs and add it to the list of outlined if it 717344779Sdim // wasn't done before. 718344779Sdim if (!NewBB) { 719344779Sdim NewBB = BasicBlock::Create(ExitBB->getContext(), 720344779Sdim ExitBB->getName() + ".split", 721344779Sdim ExitBB->getParent(), ExitBB); 722344779Sdim SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB), 723344779Sdim pred_end(ExitBB)); 724344779Sdim for (BasicBlock *PredBB : Preds) 725344779Sdim if (Blocks.count(PredBB)) 726344779Sdim PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB); 727344779Sdim BranchInst::Create(ExitBB, NewBB); 728344779Sdim Blocks.insert(NewBB); 729344779Sdim } 730344779Sdim 731344779Sdim // Split this PHI. 732344779Sdim PHINode *NewPN = 733344779Sdim PHINode::Create(PN.getType(), IncomingVals.size(), 734344779Sdim PN.getName() + ".ce", NewBB->getFirstNonPHI()); 735344779Sdim for (unsigned i : IncomingVals) 736344779Sdim NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i)); 737344779Sdim for (unsigned i : reverse(IncomingVals)) 738344779Sdim PN.removeIncomingValue(i, false); 739344779Sdim PN.addIncoming(NewPN, NewBB); 740344779Sdim } 741344779Sdim } 742344779Sdim} 743344779Sdim 744193323Sedvoid CodeExtractor::splitReturnBlocks() { 745309124Sdim for (BasicBlock *Block : Blocks) 746309124Sdim if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) { 747296417Sdim BasicBlock *New = 748309124Sdim Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret"); 749198090Srdivacky if (DT) { 750218893Sdim // Old dominates New. New node dominates all other nodes dominated 751218893Sdim // by Old. 752309124Sdim DomTreeNode *OldNode = DT->getNode(Block); 753309124Sdim SmallVector<DomTreeNode *, 8> Children(OldNode->begin(), 754309124Sdim OldNode->end()); 755198090Srdivacky 756309124Sdim DomTreeNode *NewNode = DT->addNewBlock(New, Block); 757198090Srdivacky 758309124Sdim for (DomTreeNode *I : Children) 759309124Sdim DT->changeImmediateDominator(I, NewNode); 760198090Srdivacky } 761198090Srdivacky } 762193323Sed} 763193323Sed 764193323Sed/// constructFunction - make a function based on inputs and outputs, as follows: 765193323Sed/// f(in0, ..., inN, out0, ..., outN) 766239462SdimFunction *CodeExtractor::constructFunction(const ValueSet &inputs, 767239462Sdim const ValueSet &outputs, 768193323Sed BasicBlock *header, 769193323Sed BasicBlock *newRootNode, 770193323Sed BasicBlock *newHeader, 771193323Sed Function *oldFunction, 772193323Sed Module *M) { 773341825Sdim LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n"); 774341825Sdim LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n"); 775193323Sed 776193323Sed // This function returns unsigned, outputs will go back by reference. 777193323Sed switch (NumExitBlocks) { 778193323Sed case 0: 779198090Srdivacky case 1: RetTy = Type::getVoidTy(header->getContext()); break; 780198090Srdivacky case 2: RetTy = Type::getInt1Ty(header->getContext()); break; 781198090Srdivacky default: RetTy = Type::getInt16Ty(header->getContext()); break; 782193323Sed } 783193323Sed 784327952Sdim std::vector<Type *> paramTy; 785193323Sed 786193323Sed // Add the types of the input values to the function's argument list 787309124Sdim for (Value *value : inputs) { 788341825Sdim LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n"); 789193323Sed paramTy.push_back(value->getType()); 790193323Sed } 791193323Sed 792193323Sed // Add the types of the output values to the function's argument list. 793309124Sdim for (Value *output : outputs) { 794341825Sdim LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n"); 795193323Sed if (AggregateArgs) 796309124Sdim paramTy.push_back(output->getType()); 797193323Sed else 798309124Sdim paramTy.push_back(PointerType::getUnqual(output->getType())); 799193323Sed } 800193323Sed 801341825Sdim LLVM_DEBUG({ 802309124Sdim dbgs() << "Function type: " << *RetTy << " f("; 803309124Sdim for (Type *i : paramTy) 804309124Sdim dbgs() << *i << ", "; 805309124Sdim dbgs() << ")\n"; 806309124Sdim }); 807193323Sed 808360784Sdim StructType *StructTy = nullptr; 809193323Sed if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 810288943Sdim StructTy = StructType::get(M->getContext(), paramTy); 811193323Sed paramTy.clear(); 812288943Sdim paramTy.push_back(PointerType::getUnqual(StructTy)); 813193323Sed } 814226633Sdim FunctionType *funcType = 815327952Sdim FunctionType::get(RetTy, paramTy, 816327952Sdim AllowVarArgs && oldFunction->isVarArg()); 817193323Sed 818344779Sdim std::string SuffixToUse = 819344779Sdim Suffix.empty() 820344779Sdim ? (header->getName().empty() ? "extracted" : header->getName().str()) 821344779Sdim : Suffix; 822193323Sed // Create the new function 823344779Sdim Function *newFunction = Function::Create( 824344779Sdim funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(), 825344779Sdim oldFunction->getName() + "." + SuffixToUse, M); 826193323Sed // If the old function is no-throw, so is the new one. 827193323Sed if (oldFunction->doesNotThrow()) 828243830Sdim newFunction->setDoesNotThrow(); 829314564Sdim 830314564Sdim // Inherit the uwtable attribute if we need to. 831314564Sdim if (oldFunction->hasUWTable()) 832314564Sdim newFunction->setHasUWTable(); 833314564Sdim 834341825Sdim // Inherit all of the target dependent attributes and white-listed 835341825Sdim // target independent attributes. 836314564Sdim // (e.g. If the extracted region contains a call to an x86.sse 837314564Sdim // instruction we need to make sure that the extracted region has the 838314564Sdim // "target-features" attribute allowing it to be lowered. 839314564Sdim // FIXME: This should be changed to check to see if a specific 840314564Sdim // attribute can not be inherited. 841341825Sdim for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) { 842341825Sdim if (Attr.isStringAttribute()) { 843341825Sdim if (Attr.getKindAsString() == "thunk") 844341825Sdim continue; 845341825Sdim } else 846341825Sdim switch (Attr.getKindAsEnum()) { 847341825Sdim // Those attributes cannot be propagated safely. Explicitly list them 848341825Sdim // here so we get a warning if new attributes are added. This list also 849341825Sdim // includes non-function attributes. 850341825Sdim case Attribute::Alignment: 851341825Sdim case Attribute::AllocSize: 852341825Sdim case Attribute::ArgMemOnly: 853341825Sdim case Attribute::Builtin: 854341825Sdim case Attribute::ByVal: 855341825Sdim case Attribute::Convergent: 856341825Sdim case Attribute::Dereferenceable: 857341825Sdim case Attribute::DereferenceableOrNull: 858341825Sdim case Attribute::InAlloca: 859341825Sdim case Attribute::InReg: 860341825Sdim case Attribute::InaccessibleMemOnly: 861341825Sdim case Attribute::InaccessibleMemOrArgMemOnly: 862341825Sdim case Attribute::JumpTable: 863341825Sdim case Attribute::Naked: 864341825Sdim case Attribute::Nest: 865341825Sdim case Attribute::NoAlias: 866341825Sdim case Attribute::NoBuiltin: 867341825Sdim case Attribute::NoCapture: 868341825Sdim case Attribute::NoReturn: 869353358Sdim case Attribute::NoSync: 870341825Sdim case Attribute::None: 871341825Sdim case Attribute::NonNull: 872341825Sdim case Attribute::ReadNone: 873341825Sdim case Attribute::ReadOnly: 874341825Sdim case Attribute::Returned: 875341825Sdim case Attribute::ReturnsTwice: 876341825Sdim case Attribute::SExt: 877341825Sdim case Attribute::Speculatable: 878341825Sdim case Attribute::StackAlignment: 879341825Sdim case Attribute::StructRet: 880341825Sdim case Attribute::SwiftError: 881341825Sdim case Attribute::SwiftSelf: 882353358Sdim case Attribute::WillReturn: 883341825Sdim case Attribute::WriteOnly: 884341825Sdim case Attribute::ZExt: 885353358Sdim case Attribute::ImmArg: 886341825Sdim case Attribute::EndAttrKinds: 887341825Sdim continue; 888341825Sdim // Those attributes should be safe to propagate to the extracted function. 889341825Sdim case Attribute::AlwaysInline: 890341825Sdim case Attribute::Cold: 891341825Sdim case Attribute::NoRecurse: 892341825Sdim case Attribute::InlineHint: 893341825Sdim case Attribute::MinSize: 894341825Sdim case Attribute::NoDuplicate: 895353358Sdim case Attribute::NoFree: 896341825Sdim case Attribute::NoImplicitFloat: 897341825Sdim case Attribute::NoInline: 898341825Sdim case Attribute::NonLazyBind: 899341825Sdim case Attribute::NoRedZone: 900341825Sdim case Attribute::NoUnwind: 901341825Sdim case Attribute::OptForFuzzing: 902341825Sdim case Attribute::OptimizeNone: 903341825Sdim case Attribute::OptimizeForSize: 904341825Sdim case Attribute::SafeStack: 905341825Sdim case Attribute::ShadowCallStack: 906341825Sdim case Attribute::SanitizeAddress: 907341825Sdim case Attribute::SanitizeMemory: 908341825Sdim case Attribute::SanitizeThread: 909341825Sdim case Attribute::SanitizeHWAddress: 910353358Sdim case Attribute::SanitizeMemTag: 911344779Sdim case Attribute::SpeculativeLoadHardening: 912341825Sdim case Attribute::StackProtect: 913341825Sdim case Attribute::StackProtectReq: 914341825Sdim case Attribute::StackProtectStrong: 915341825Sdim case Attribute::StrictFP: 916341825Sdim case Attribute::UWTable: 917341825Sdim case Attribute::NoCfCheck: 918341825Sdim break; 919341825Sdim } 920314564Sdim 921341825Sdim newFunction->addFnAttr(Attr); 922341825Sdim } 923193323Sed newFunction->getBasicBlockList().push_back(newRootNode); 924193323Sed 925193323Sed // Create an iterator to name all of the arguments we inserted. 926193323Sed Function::arg_iterator AI = newFunction->arg_begin(); 927193323Sed 928193323Sed // Rewrite all users of the inputs in the extracted region to use the 929193323Sed // arguments (or appropriate addressing into struct) instead. 930193323Sed for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 931193323Sed Value *RewriteVal; 932193323Sed if (AggregateArgs) { 933193323Sed Value *Idx[2]; 934198090Srdivacky Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); 935198090Srdivacky Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); 936344779Sdim Instruction *TI = newFunction->begin()->getTerminator(); 937288943Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 938296417Sdim StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI); 939353358Sdim RewriteVal = new LoadInst(StructTy->getElementType(i), GEP, 940353358Sdim "loadgep_" + inputs[i]->getName(), TI); 941193323Sed } else 942296417Sdim RewriteVal = &*AI++; 943193323Sed 944327952Sdim std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end()); 945309124Sdim for (User *use : Users) 946309124Sdim if (Instruction *inst = dyn_cast<Instruction>(use)) 947239462Sdim if (Blocks.count(inst->getParent())) 948193323Sed inst->replaceUsesOfWith(inputs[i], RewriteVal); 949193323Sed } 950193323Sed 951193323Sed // Set names for input and output arguments. 952193323Sed if (!AggregateArgs) { 953193323Sed AI = newFunction->arg_begin(); 954193323Sed for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 955193323Sed AI->setName(inputs[i]->getName()); 956193323Sed for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 957193323Sed AI->setName(outputs[i]->getName()+".out"); 958193323Sed } 959193323Sed 960193323Sed // Rewrite branches to basic blocks outside of the loop to new dummy blocks 961193323Sed // within the new function. This must be done before we lose track of which 962193323Sed // blocks were originally in the code region. 963327952Sdim std::vector<User *> Users(header->user_begin(), header->user_end()); 964360784Sdim for (auto &U : Users) 965193323Sed // The BasicBlock which contains the branch is not in the region 966193323Sed // modify the branch target to a new block 967360784Sdim if (Instruction *I = dyn_cast<Instruction>(U)) 968360784Sdim if (I->isTerminator() && I->getFunction() == oldFunction && 969360784Sdim !Blocks.count(I->getParent())) 970344779Sdim I->replaceUsesOfWith(header, newHeader); 971193323Sed 972193323Sed return newFunction; 973193323Sed} 974193323Sed 975353358Sdim/// Erase lifetime.start markers which reference inputs to the extraction 976353358Sdim/// region, and insert the referenced memory into \p LifetimesStart. 977353358Sdim/// 978353358Sdim/// The extraction region is defined by a set of blocks (\p Blocks), and a set 979353358Sdim/// of allocas which will be moved from the caller function into the extracted 980353358Sdim/// function (\p SunkAllocas). 981353358Sdimstatic void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks, 982353358Sdim const SetVector<Value *> &SunkAllocas, 983353358Sdim SetVector<Value *> &LifetimesStart) { 984353358Sdim for (BasicBlock *BB : Blocks) { 985353358Sdim for (auto It = BB->begin(), End = BB->end(); It != End;) { 986353358Sdim auto *II = dyn_cast<IntrinsicInst>(&*It); 987353358Sdim ++It; 988353358Sdim if (!II || !II->isLifetimeStartOrEnd()) 989353358Sdim continue; 990353358Sdim 991353358Sdim // Get the memory operand of the lifetime marker. If the underlying 992353358Sdim // object is a sunk alloca, or is otherwise defined in the extraction 993353358Sdim // region, the lifetime marker must not be erased. 994353358Sdim Value *Mem = II->getOperand(1)->stripInBoundsOffsets(); 995353358Sdim if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem)) 996353358Sdim continue; 997353358Sdim 998353358Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start) 999353358Sdim LifetimesStart.insert(Mem); 1000353358Sdim II->eraseFromParent(); 1001353358Sdim } 1002353358Sdim } 1003353358Sdim} 1004353358Sdim 1005353358Sdim/// Insert lifetime start/end markers surrounding the call to the new function 1006353358Sdim/// for objects defined in the caller. 1007353358Sdimstatic void insertLifetimeMarkersSurroundingCall( 1008353358Sdim Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd, 1009353358Sdim CallInst *TheCall) { 1010353358Sdim LLVMContext &Ctx = M->getContext(); 1011353358Sdim auto Int8PtrTy = Type::getInt8PtrTy(Ctx); 1012353358Sdim auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1); 1013353358Sdim Instruction *Term = TheCall->getParent()->getTerminator(); 1014353358Sdim 1015353358Sdim // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts 1016353358Sdim // needed to satisfy this requirement so they may be reused. 1017353358Sdim DenseMap<Value *, Value *> Bitcasts; 1018353358Sdim 1019353358Sdim // Emit lifetime markers for the pointers given in \p Objects. Insert the 1020353358Sdim // markers before the call if \p InsertBefore, and after the call otherwise. 1021353358Sdim auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects, 1022353358Sdim bool InsertBefore) { 1023353358Sdim for (Value *Mem : Objects) { 1024353358Sdim assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == 1025353358Sdim TheCall->getFunction()) && 1026353358Sdim "Input memory not defined in original function"); 1027353358Sdim Value *&MemAsI8Ptr = Bitcasts[Mem]; 1028353358Sdim if (!MemAsI8Ptr) { 1029353358Sdim if (Mem->getType() == Int8PtrTy) 1030353358Sdim MemAsI8Ptr = Mem; 1031353358Sdim else 1032353358Sdim MemAsI8Ptr = 1033353358Sdim CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall); 1034353358Sdim } 1035353358Sdim 1036353358Sdim auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr}); 1037353358Sdim if (InsertBefore) 1038353358Sdim Marker->insertBefore(TheCall); 1039353358Sdim else 1040353358Sdim Marker->insertBefore(Term); 1041353358Sdim } 1042353358Sdim }; 1043353358Sdim 1044353358Sdim if (!LifetimesStart.empty()) { 1045353358Sdim auto StartFn = llvm::Intrinsic::getDeclaration( 1046353358Sdim M, llvm::Intrinsic::lifetime_start, Int8PtrTy); 1047353358Sdim insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true); 1048353358Sdim } 1049353358Sdim 1050353358Sdim if (!LifetimesEnd.empty()) { 1051353358Sdim auto EndFn = llvm::Intrinsic::getDeclaration( 1052353358Sdim M, llvm::Intrinsic::lifetime_end, Int8PtrTy); 1053353358Sdim insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false); 1054353358Sdim } 1055353358Sdim} 1056353358Sdim 1057193323Sed/// emitCallAndSwitchStatement - This method sets up the caller side by adding 1058193323Sed/// the call instruction, splitting any PHI nodes in the header block as 1059193323Sed/// necessary. 1060344779SdimCallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction, 1061344779Sdim BasicBlock *codeReplacer, 1062344779Sdim ValueSet &inputs, 1063344779Sdim ValueSet &outputs) { 1064193323Sed // Emit a call to the new function, passing in: *pointer to struct (if 1065193323Sed // aggregating parameters), or plan inputs and allocated memory for outputs 1066327952Sdim std::vector<Value *> params, StructValues, ReloadOutputs, Reloads; 1067193323Sed 1068321369Sdim Module *M = newFunction->getParent(); 1069321369Sdim LLVMContext &Context = M->getContext(); 1070321369Sdim const DataLayout &DL = M->getDataLayout(); 1071344779Sdim CallInst *call = nullptr; 1072321369Sdim 1073193323Sed // Add inputs as params, or to be filled into the struct 1074353358Sdim unsigned ArgNo = 0; 1075353358Sdim SmallVector<unsigned, 1> SwiftErrorArgs; 1076353358Sdim for (Value *input : inputs) { 1077193323Sed if (AggregateArgs) 1078309124Sdim StructValues.push_back(input); 1079353358Sdim else { 1080309124Sdim params.push_back(input); 1081353358Sdim if (input->isSwiftError()) 1082353358Sdim SwiftErrorArgs.push_back(ArgNo); 1083353358Sdim } 1084353358Sdim ++ArgNo; 1085353358Sdim } 1086193323Sed 1087193323Sed // Create allocas for the outputs 1088309124Sdim for (Value *output : outputs) { 1089193323Sed if (AggregateArgs) { 1090309124Sdim StructValues.push_back(output); 1091193323Sed } else { 1092193323Sed AllocaInst *alloca = 1093321369Sdim new AllocaInst(output->getType(), DL.getAllocaAddrSpace(), 1094321369Sdim nullptr, output->getName() + ".loc", 1095321369Sdim &codeReplacer->getParent()->front().front()); 1096193323Sed ReloadOutputs.push_back(alloca); 1097193323Sed params.push_back(alloca); 1098193323Sed } 1099193323Sed } 1100193323Sed 1101288943Sdim StructType *StructArgTy = nullptr; 1102276479Sdim AllocaInst *Struct = nullptr; 1103193323Sed if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 1104327952Sdim std::vector<Type *> ArgTypes; 1105239462Sdim for (ValueSet::iterator v = StructValues.begin(), 1106193323Sed ve = StructValues.end(); v != ve; ++v) 1107193323Sed ArgTypes.push_back((*v)->getType()); 1108193323Sed 1109193323Sed // Allocate a struct at the beginning of this function 1110288943Sdim StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); 1111321369Sdim Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr, 1112321369Sdim "structArg", 1113296417Sdim &codeReplacer->getParent()->front().front()); 1114193323Sed params.push_back(Struct); 1115193323Sed 1116193323Sed for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 1117193323Sed Value *Idx[2]; 1118198090Srdivacky Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1119198090Srdivacky Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); 1120288943Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 1121288943Sdim StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); 1122193323Sed codeReplacer->getInstList().push_back(GEP); 1123193323Sed StoreInst *SI = new StoreInst(StructValues[i], GEP); 1124193323Sed codeReplacer->getInstList().push_back(SI); 1125193323Sed } 1126193323Sed } 1127193323Sed 1128193323Sed // Emit the call to the function 1129344779Sdim call = CallInst::Create(newFunction, params, 1130344779Sdim NumExitBlocks > 1 ? "targetBlock" : ""); 1131327952Sdim // Add debug location to the new call, if the original function has debug 1132327952Sdim // info. In that case, the terminator of the entry block of the extracted 1133327952Sdim // function contains the first debug location of the extracted function, 1134327952Sdim // set in extractCodeRegion. 1135327952Sdim if (codeReplacer->getParent()->getSubprogram()) { 1136327952Sdim if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc()) 1137327952Sdim call->setDebugLoc(DL); 1138327952Sdim } 1139193323Sed codeReplacer->getInstList().push_back(call); 1140193323Sed 1141353358Sdim // Set swifterror parameter attributes. 1142353358Sdim for (unsigned SwiftErrArgNo : SwiftErrorArgs) { 1143353358Sdim call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1144353358Sdim newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); 1145353358Sdim } 1146353358Sdim 1147193323Sed Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); 1148193323Sed unsigned FirstOut = inputs.size(); 1149193323Sed if (!AggregateArgs) 1150193323Sed std::advance(OutputArgBegin, inputs.size()); 1151193323Sed 1152327952Sdim // Reload the outputs passed in by reference. 1153193323Sed for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 1154276479Sdim Value *Output = nullptr; 1155193323Sed if (AggregateArgs) { 1156193323Sed Value *Idx[2]; 1157198090Srdivacky Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1158198090Srdivacky Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 1159288943Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 1160288943Sdim StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); 1161193323Sed codeReplacer->getInstList().push_back(GEP); 1162193323Sed Output = GEP; 1163193323Sed } else { 1164193323Sed Output = ReloadOutputs[i]; 1165193323Sed } 1166353358Sdim LoadInst *load = new LoadInst(outputs[i]->getType(), Output, 1167353358Sdim outputs[i]->getName() + ".reload"); 1168198090Srdivacky Reloads.push_back(load); 1169193323Sed codeReplacer->getInstList().push_back(load); 1170327952Sdim std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end()); 1171193323Sed for (unsigned u = 0, e = Users.size(); u != e; ++u) { 1172193323Sed Instruction *inst = cast<Instruction>(Users[u]); 1173239462Sdim if (!Blocks.count(inst->getParent())) 1174193323Sed inst->replaceUsesOfWith(outputs[i], load); 1175193323Sed } 1176193323Sed } 1177193323Sed 1178193323Sed // Now we can emit a switch statement using the call as a value. 1179193323Sed SwitchInst *TheSwitch = 1180198090Srdivacky SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), 1181193323Sed codeReplacer, 0, codeReplacer); 1182193323Sed 1183193323Sed // Since there may be multiple exits from the original region, make the new 1184193323Sed // function return an unsigned, switch on that number. This loop iterates 1185193323Sed // over all of the blocks in the extracted region, updating any terminator 1186193323Sed // instructions in the to-be-extracted region that branch to blocks that are 1187193323Sed // not in the region to be extracted. 1188327952Sdim std::map<BasicBlock *, BasicBlock *> ExitBlockMap; 1189193323Sed 1190193323Sed unsigned switchVal = 0; 1191309124Sdim for (BasicBlock *Block : Blocks) { 1192344779Sdim Instruction *TI = Block->getTerminator(); 1193193323Sed for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 1194239462Sdim if (!Blocks.count(TI->getSuccessor(i))) { 1195193323Sed BasicBlock *OldTarget = TI->getSuccessor(i); 1196193323Sed // add a new basic block which returns the appropriate value 1197193323Sed BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 1198193323Sed if (!NewTarget) { 1199193323Sed // If we don't already have an exit stub for this non-extracted 1200193323Sed // destination, create one now! 1201198090Srdivacky NewTarget = BasicBlock::Create(Context, 1202198090Srdivacky OldTarget->getName() + ".exitStub", 1203193323Sed newFunction); 1204193323Sed unsigned SuccNum = switchVal++; 1205193323Sed 1206276479Sdim Value *brVal = nullptr; 1207193323Sed switch (NumExitBlocks) { 1208193323Sed case 0: 1209193323Sed case 1: break; // No value needed. 1210193323Sed case 2: // Conditional branch, return a bool 1211198090Srdivacky brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); 1212193323Sed break; 1213193323Sed default: 1214198090Srdivacky brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); 1215193323Sed break; 1216193323Sed } 1217193323Sed 1218327952Sdim ReturnInst::Create(Context, brVal, NewTarget); 1219193323Sed 1220193323Sed // Update the switch instruction. 1221198090Srdivacky TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), 1222198090Srdivacky SuccNum), 1223193323Sed OldTarget); 1224193323Sed } 1225193323Sed 1226193323Sed // rewrite the original branch instruction with this new target 1227193323Sed TI->setSuccessor(i, NewTarget); 1228193323Sed } 1229193323Sed } 1230193323Sed 1231353358Sdim // Store the arguments right after the definition of output value. 1232353358Sdim // This should be proceeded after creating exit stubs to be ensure that invoke 1233353358Sdim // result restore will be placed in the outlined function. 1234353358Sdim Function::arg_iterator OAI = OutputArgBegin; 1235353358Sdim for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 1236353358Sdim auto *OutI = dyn_cast<Instruction>(outputs[i]); 1237353358Sdim if (!OutI) 1238353358Sdim continue; 1239353358Sdim 1240353358Sdim // Find proper insertion point. 1241353358Sdim BasicBlock::iterator InsertPt; 1242353358Sdim // In case OutI is an invoke, we insert the store at the beginning in the 1243353358Sdim // 'normal destination' BB. Otherwise we insert the store right after OutI. 1244353358Sdim if (auto *InvokeI = dyn_cast<InvokeInst>(OutI)) 1245353358Sdim InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt(); 1246353358Sdim else if (auto *Phi = dyn_cast<PHINode>(OutI)) 1247353358Sdim InsertPt = Phi->getParent()->getFirstInsertionPt(); 1248353358Sdim else 1249353358Sdim InsertPt = std::next(OutI->getIterator()); 1250353358Sdim 1251353358Sdim Instruction *InsertBefore = &*InsertPt; 1252353358Sdim assert((InsertBefore->getFunction() == newFunction || 1253353358Sdim Blocks.count(InsertBefore->getParent())) && 1254353358Sdim "InsertPt should be in new function"); 1255353358Sdim assert(OAI != newFunction->arg_end() && 1256353358Sdim "Number of output arguments should match " 1257353358Sdim "the amount of defined values"); 1258353358Sdim if (AggregateArgs) { 1259353358Sdim Value *Idx[2]; 1260353358Sdim Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 1261353358Sdim Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 1262353358Sdim GetElementPtrInst *GEP = GetElementPtrInst::Create( 1263353358Sdim StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), 1264353358Sdim InsertBefore); 1265353358Sdim new StoreInst(outputs[i], GEP, InsertBefore); 1266353358Sdim // Since there should be only one struct argument aggregating 1267353358Sdim // all the output values, we shouldn't increment OAI, which always 1268353358Sdim // points to the struct argument, in this case. 1269353358Sdim } else { 1270353358Sdim new StoreInst(outputs[i], &*OAI, InsertBefore); 1271353358Sdim ++OAI; 1272353358Sdim } 1273353358Sdim } 1274353358Sdim 1275193323Sed // Now that we've done the deed, simplify the switch instruction. 1276226633Sdim Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 1277193323Sed switch (NumExitBlocks) { 1278193323Sed case 0: 1279193323Sed // There are no successors (the block containing the switch itself), which 1280193323Sed // means that previously this was the last part of the function, and hence 1281193323Sed // this should be rewritten as a `ret' 1282193323Sed 1283193323Sed // Check if the function should return a value 1284202375Srdivacky if (OldFnRetTy->isVoidTy()) { 1285276479Sdim ReturnInst::Create(Context, nullptr, TheSwitch); // Return void 1286193323Sed } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 1287193323Sed // return what we have 1288198090Srdivacky ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); 1289193323Sed } else { 1290193323Sed // Otherwise we must have code extracted an unwind or something, just 1291193323Sed // return whatever we want. 1292341825Sdim ReturnInst::Create(Context, 1293198090Srdivacky Constant::getNullValue(OldFnRetTy), TheSwitch); 1294193323Sed } 1295193323Sed 1296193323Sed TheSwitch->eraseFromParent(); 1297193323Sed break; 1298193323Sed case 1: 1299193323Sed // Only a single destination, change the switch into an unconditional 1300193323Sed // branch. 1301193323Sed BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); 1302193323Sed TheSwitch->eraseFromParent(); 1303193323Sed break; 1304193323Sed case 2: 1305193323Sed BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 1306193323Sed call, TheSwitch); 1307193323Sed TheSwitch->eraseFromParent(); 1308193323Sed break; 1309193323Sed default: 1310193323Sed // Otherwise, make the default destination of the switch instruction be one 1311193323Sed // of the other successors. 1312234353Sdim TheSwitch->setCondition(call); 1313234353Sdim TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); 1314234353Sdim // Remove redundant case 1315261991Sdim TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); 1316193323Sed break; 1317193323Sed } 1318344779Sdim 1319353358Sdim // Insert lifetime markers around the reloads of any output values. The 1320353358Sdim // allocas output values are stored in are only in-use in the codeRepl block. 1321353358Sdim insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call); 1322353358Sdim 1323344779Sdim return call; 1324193323Sed} 1325193323Sed 1326193323Sedvoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 1327239462Sdim Function *oldFunc = (*Blocks.begin())->getParent(); 1328193323Sed Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 1329193323Sed Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 1330193323Sed 1331309124Sdim for (BasicBlock *Block : Blocks) { 1332193323Sed // Delete the basic block from the old function, and the list of blocks 1333309124Sdim oldBlocks.remove(Block); 1334193323Sed 1335193323Sed // Insert this basic block into the new function 1336309124Sdim newBlocks.push_back(Block); 1337193323Sed } 1338193323Sed} 1339193323Sed 1340314564Sdimvoid CodeExtractor::calculateNewCallTerminatorWeights( 1341314564Sdim BasicBlock *CodeReplacer, 1342314564Sdim DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 1343314564Sdim BranchProbabilityInfo *BPI) { 1344327952Sdim using Distribution = BlockFrequencyInfoImplBase::Distribution; 1345327952Sdim using BlockNode = BlockFrequencyInfoImplBase::BlockNode; 1346314564Sdim 1347314564Sdim // Update the branch weights for the exit block. 1348344779Sdim Instruction *TI = CodeReplacer->getTerminator(); 1349314564Sdim SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0); 1350314564Sdim 1351314564Sdim // Block Frequency distribution with dummy node. 1352314564Sdim Distribution BranchDist; 1353314564Sdim 1354314564Sdim // Add each of the frequencies of the successors. 1355314564Sdim for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { 1356314564Sdim BlockNode ExitNode(i); 1357314564Sdim uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency(); 1358314564Sdim if (ExitFreq != 0) 1359314564Sdim BranchDist.addExit(ExitNode, ExitFreq); 1360314564Sdim else 1361314564Sdim BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero()); 1362314564Sdim } 1363314564Sdim 1364314564Sdim // Check for no total weight. 1365314564Sdim if (BranchDist.Total == 0) 1366314564Sdim return; 1367314564Sdim 1368314564Sdim // Normalize the distribution so that they can fit in unsigned. 1369314564Sdim BranchDist.normalize(); 1370314564Sdim 1371314564Sdim // Create normalized branch weights and set the metadata. 1372314564Sdim for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) { 1373314564Sdim const auto &Weight = BranchDist.Weights[I]; 1374314564Sdim 1375314564Sdim // Get the weight and update the current BFI. 1376314564Sdim BranchWeights[Weight.TargetNode.Index] = Weight.Amount; 1377314564Sdim BranchProbability BP(Weight.Amount, BranchDist.Total); 1378314564Sdim BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP); 1379314564Sdim } 1380314564Sdim TI->setMetadata( 1381314564Sdim LLVMContext::MD_prof, 1382314564Sdim MDBuilder(TI->getContext()).createBranchWeights(BranchWeights)); 1383314564Sdim} 1384314564Sdim 1385360784SdimFunction * 1386360784SdimCodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) { 1387239462Sdim if (!isEligible()) 1388276479Sdim return nullptr; 1389193323Sed 1390193323Sed // Assumption: this is a single-entry code region, and the header is the first 1391193323Sed // block in the region. 1392239462Sdim BasicBlock *header = *Blocks.begin(); 1393327952Sdim Function *oldFunction = header->getParent(); 1394193323Sed 1395314564Sdim // Calculate the entry frequency of the new function before we change the root 1396314564Sdim // block. 1397314564Sdim BlockFrequency EntryFreq; 1398314564Sdim if (BFI) { 1399314564Sdim assert(BPI && "Both BPI and BFI are required to preserve profile info"); 1400314564Sdim for (BasicBlock *Pred : predecessors(header)) { 1401314564Sdim if (Blocks.count(Pred)) 1402314564Sdim continue; 1403314564Sdim EntryFreq += 1404314564Sdim BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header); 1405314564Sdim } 1406314564Sdim } 1407314564Sdim 1408360784Sdim if (AC) { 1409360784Sdim // Remove @llvm.assume calls that were moved to the new function from the 1410360784Sdim // old function's assumption cache. 1411360784Sdim for (BasicBlock *Block : Blocks) 1412360784Sdim for (auto &I : *Block) 1413360784Sdim if (match(&I, m_Intrinsic<Intrinsic::assume>())) 1414360784Sdim AC->unregisterAssumption(cast<CallInst>(&I)); 1415360784Sdim } 1416360784Sdim 1417193323Sed // If we have any return instructions in the region, split those blocks so 1418193323Sed // that the return is not in the region. 1419193323Sed splitReturnBlocks(); 1420193323Sed 1421344779Sdim // Calculate the exit blocks for the extracted region and the total exit 1422344779Sdim // weights for each of those blocks. 1423344779Sdim DenseMap<BasicBlock *, BlockFrequency> ExitWeights; 1424344779Sdim SmallPtrSet<BasicBlock *, 1> ExitBlocks; 1425344779Sdim for (BasicBlock *Block : Blocks) { 1426344779Sdim for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE; 1427344779Sdim ++SI) { 1428344779Sdim if (!Blocks.count(*SI)) { 1429344779Sdim // Update the branch weight for this successor. 1430344779Sdim if (BFI) { 1431344779Sdim BlockFrequency &BF = ExitWeights[*SI]; 1432344779Sdim BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI); 1433344779Sdim } 1434344779Sdim ExitBlocks.insert(*SI); 1435344779Sdim } 1436344779Sdim } 1437344779Sdim } 1438344779Sdim NumExitBlocks = ExitBlocks.size(); 1439344779Sdim 1440344779Sdim // If we have to split PHI nodes of the entry or exit blocks, do so now. 1441344779Sdim severSplitPHINodesOfEntry(header); 1442344779Sdim severSplitPHINodesOfExits(ExitBlocks); 1443344779Sdim 1444193323Sed // This takes place of the original loop 1445341825Sdim BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), 1446198090Srdivacky "codeRepl", oldFunction, 1447193323Sed header); 1448193323Sed 1449193323Sed // The new function needs a root node because other nodes can branch to the 1450193323Sed // head of the region, but the entry node of a function cannot have preds. 1451341825Sdim BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 1452198090Srdivacky "newFuncRoot"); 1453327952Sdim auto *BranchI = BranchInst::Create(header); 1454327952Sdim // If the original function has debug info, we have to add a debug location 1455327952Sdim // to the new branch instruction from the artificial entry block. 1456327952Sdim // We use the debug location of the first instruction in the extracted 1457327952Sdim // blocks, as there is no other equivalent line in the source code. 1458327952Sdim if (oldFunction->getSubprogram()) { 1459327952Sdim any_of(Blocks, [&BranchI](const BasicBlock *BB) { 1460327952Sdim return any_of(*BB, [&BranchI](const Instruction &I) { 1461327952Sdim if (!I.getDebugLoc()) 1462327952Sdim return false; 1463327952Sdim BranchI->setDebugLoc(I.getDebugLoc()); 1464327952Sdim return true; 1465327952Sdim }); 1466327952Sdim }); 1467327952Sdim } 1468327952Sdim newFuncRoot->getInstList().push_back(BranchI); 1469193323Sed 1470360784Sdim ValueSet inputs, outputs, SinkingCands, HoistingCands; 1471360784Sdim BasicBlock *CommonExit = nullptr; 1472360784Sdim findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit); 1473321369Sdim assert(HoistingCands.empty() || CommonExit); 1474321369Sdim 1475193323Sed // Find inputs to, outputs from the code region. 1476321369Sdim findInputsOutputs(inputs, outputs, SinkingCands); 1477193323Sed 1478353358Sdim // Now sink all instructions which only have non-phi uses inside the region. 1479353358Sdim // Group the allocas at the start of the block, so that any bitcast uses of 1480353358Sdim // the allocas are well-defined. 1481353358Sdim AllocaInst *FirstSunkAlloca = nullptr; 1482353358Sdim for (auto *II : SinkingCands) { 1483353358Sdim if (auto *AI = dyn_cast<AllocaInst>(II)) { 1484353358Sdim AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt()); 1485353358Sdim if (!FirstSunkAlloca) 1486353358Sdim FirstSunkAlloca = AI; 1487353358Sdim } 1488353358Sdim } 1489353358Sdim assert((SinkingCands.empty() || FirstSunkAlloca) && 1490353358Sdim "Did not expect a sink candidate without any allocas"); 1491353358Sdim for (auto *II : SinkingCands) { 1492353358Sdim if (!isa<AllocaInst>(II)) { 1493353358Sdim cast<Instruction>(II)->moveAfter(FirstSunkAlloca); 1494353358Sdim } 1495353358Sdim } 1496321369Sdim 1497321369Sdim if (!HoistingCands.empty()) { 1498321369Sdim auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit); 1499321369Sdim Instruction *TI = HoistToBlock->getTerminator(); 1500321369Sdim for (auto *II : HoistingCands) 1501321369Sdim cast<Instruction>(II)->moveBefore(TI); 1502321369Sdim } 1503321369Sdim 1504344779Sdim // Collect objects which are inputs to the extraction region and also 1505353358Sdim // referenced by lifetime start markers within it. The effects of these 1506344779Sdim // markers must be replicated in the calling function to prevent the stack 1507344779Sdim // coloring pass from merging slots which store input objects. 1508353358Sdim ValueSet LifetimesStart; 1509353358Sdim eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart); 1510239462Sdim 1511193323Sed // Construct new function based on inputs/outputs & add allocas for all defs. 1512344779Sdim Function *newFunction = 1513344779Sdim constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer, 1514344779Sdim oldFunction, oldFunction->getParent()); 1515193323Sed 1516314564Sdim // Update the entry count of the function. 1517314564Sdim if (BFI) { 1518341825Sdim auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency()); 1519341825Sdim if (Count.hasValue()) 1520341825Sdim newFunction->setEntryCount( 1521341825Sdim ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME 1522314564Sdim BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency()); 1523314564Sdim } 1524314564Sdim 1525344779Sdim CallInst *TheCall = 1526344779Sdim emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 1527193323Sed 1528193323Sed moveCodeToFunction(newFunction); 1529193323Sed 1530344779Sdim // Replicate the effects of any lifetime start/end markers which referenced 1531344779Sdim // input objects in the extraction region by placing markers around the call. 1532353358Sdim insertLifetimeMarkersSurroundingCall( 1533353358Sdim oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall); 1534344779Sdim 1535341825Sdim // Propagate personality info to the new function if there is one. 1536341825Sdim if (oldFunction->hasPersonalityFn()) 1537341825Sdim newFunction->setPersonalityFn(oldFunction->getPersonalityFn()); 1538341825Sdim 1539314564Sdim // Update the branch weights for the exit block. 1540314564Sdim if (BFI && NumExitBlocks > 1) 1541314564Sdim calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI); 1542314564Sdim 1543344779Sdim // Loop over all of the PHI nodes in the header and exit blocks, and change 1544344779Sdim // any references to the old incoming edge to be the new incoming edge. 1545193323Sed for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 1546193323Sed PHINode *PN = cast<PHINode>(I); 1547193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1548239462Sdim if (!Blocks.count(PN->getIncomingBlock(i))) 1549193323Sed PN->setIncomingBlock(i, newFuncRoot); 1550193323Sed } 1551193323Sed 1552344779Sdim for (BasicBlock *ExitBB : ExitBlocks) 1553344779Sdim for (PHINode &PN : ExitBB->phis()) { 1554344779Sdim Value *IncomingCodeReplacerVal = nullptr; 1555344779Sdim for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 1556344779Sdim // Ignore incoming values from outside of the extracted region. 1557344779Sdim if (!Blocks.count(PN.getIncomingBlock(i))) 1558344779Sdim continue; 1559344779Sdim 1560344779Sdim // Ensure that there is only one incoming value from codeReplacer. 1561344779Sdim if (!IncomingCodeReplacerVal) { 1562344779Sdim PN.setIncomingBlock(i, codeReplacer); 1563344779Sdim IncomingCodeReplacerVal = PN.getIncomingValue(i); 1564344779Sdim } else 1565344779Sdim assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) && 1566344779Sdim "PHI has two incompatbile incoming values from codeRepl"); 1567344779Sdim } 1568193323Sed } 1569193323Sed 1570344779Sdim // Erase debug info intrinsics. Variable updates within the new function are 1571344779Sdim // invisible to debuggers. This could be improved by defining a DISubprogram 1572344779Sdim // for the new function. 1573344779Sdim for (BasicBlock &BB : *newFunction) { 1574344779Sdim auto BlockIt = BB.begin(); 1575344779Sdim // Remove debug info intrinsics from the new function. 1576344779Sdim while (BlockIt != BB.end()) { 1577344779Sdim Instruction *Inst = &*BlockIt; 1578344779Sdim ++BlockIt; 1579344779Sdim if (isa<DbgInfoIntrinsic>(Inst)) 1580344779Sdim Inst->eraseFromParent(); 1581344779Sdim } 1582344779Sdim // Remove debug info intrinsics which refer to values in the new function 1583344779Sdim // from the old function. 1584344779Sdim SmallVector<DbgVariableIntrinsic *, 4> DbgUsers; 1585344779Sdim for (Instruction &I : BB) 1586344779Sdim findDbgUsers(DbgUsers, &I); 1587344779Sdim for (DbgVariableIntrinsic *DVI : DbgUsers) 1588344779Sdim DVI->eraseFromParent(); 1589344779Sdim } 1590344779Sdim 1591344779Sdim // Mark the new function `noreturn` if applicable. Terminators which resume 1592344779Sdim // exception propagation are treated as returning instructions. This is to 1593344779Sdim // avoid inserting traps after calls to outlined functions which unwind. 1594344779Sdim bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) { 1595344779Sdim const Instruction *Term = BB.getTerminator(); 1596344779Sdim return isa<ReturnInst>(Term) || isa<ResumeInst>(Term); 1597344779Sdim }); 1598344779Sdim if (doesNotReturn) 1599344779Sdim newFunction->setDoesNotReturn(); 1600344779Sdim 1601344779Sdim LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) { 1602344779Sdim newFunction->dump(); 1603344779Sdim report_fatal_error("verification of newFunction failed!"); 1604344779Sdim }); 1605344779Sdim LLVM_DEBUG(if (verifyFunction(*oldFunction)) 1606344779Sdim report_fatal_error("verification of oldFunction failed!")); 1607360784Sdim LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, AC)) 1608360784Sdim report_fatal_error("Stale Asumption cache for old Function!")); 1609193323Sed return newFunction; 1610193323Sed} 1611360784Sdim 1612360784Sdimbool CodeExtractor::verifyAssumptionCache(const Function& F, 1613360784Sdim AssumptionCache *AC) { 1614360784Sdim for (auto AssumeVH : AC->assumptions()) { 1615360784Sdim CallInst *I = cast<CallInst>(AssumeVH); 1616360784Sdim if (I->getFunction() != &F) 1617360784Sdim return true; 1618360784Sdim } 1619360784Sdim return false; 1620360784Sdim} 1621