1 //===- CodeExtractor.cpp - Pull code region into a new function -----------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements the interface to tear out a code region, such as an
10 // individual loop or a parallel section, into a new function, replacing it with
11 // a call to the new function.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/CodeExtractor.h"
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Analysis/AssumptionCache.h"
24 #include "llvm/Analysis/BlockFrequencyInfo.h"
25 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
26 #include "llvm/Analysis/BranchProbabilityInfo.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/IR/Argument.h"
29 #include "llvm/IR/Attributes.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/Constant.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DIBuilder.h"
35 #include "llvm/IR/DataLayout.h"
36 #include "llvm/IR/DebugInfoMetadata.h"
37 #include "llvm/IR/DerivedTypes.h"
38 #include "llvm/IR/Dominators.h"
39 #include "llvm/IR/Function.h"
40 #include "llvm/IR/GlobalValue.h"
41 #include "llvm/IR/InstIterator.h"
42 #include "llvm/IR/InstrTypes.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/Intrinsics.h"
47 #include "llvm/IR/LLVMContext.h"
48 #include "llvm/IR/MDBuilder.h"
49 #include "llvm/IR/Module.h"
50 #include "llvm/IR/PatternMatch.h"
51 #include "llvm/IR/Type.h"
52 #include "llvm/IR/User.h"
53 #include "llvm/IR/Value.h"
54 #include "llvm/IR/Verifier.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/BlockFrequency.h"
57 #include "llvm/Support/BranchProbability.h"
58 #include "llvm/Support/Casting.h"
59 #include "llvm/Support/CommandLine.h"
60 #include "llvm/Support/Debug.h"
61 #include "llvm/Support/ErrorHandling.h"
62 #include "llvm/Support/raw_ostream.h"
63 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
64 #include "llvm/Transforms/Utils/Local.h"
74 using namespace llvm::PatternMatch;
75 using ProfileCount = Function::ProfileCount;
77 #define DEBUG_TYPE "code-extractor"
79 // Provide a command-line option to aggregate function arguments into a struct
80 // for functions produced by the code extractor. This is useful when converting
81 // extracted functions to pthread-based code, as only one argument (void*) can
82 // be passed in to pthread_create().
84 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
85 cl::desc("Aggregate arguments to code-extracted functions"));
87 /// Test whether a block is valid for extraction.
88 static bool isBlockValidForExtraction(const BasicBlock &BB,
89 const SetVector<BasicBlock *> &Result,
90 bool AllowVarArgs, bool AllowAlloca) {
91 // taking the address of a basic block moved to another function is illegal
92 if (BB.hasAddressTaken())
95 // don't hoist code that uses another basicblock address, as it's likely to
96 // lead to unexpected behavior, like cross-function jumps
97 SmallPtrSet<User const *, 16> Visited;
98 SmallVector<User const *, 16> ToVisit;
100 for (Instruction const &Inst : BB)
101 ToVisit.push_back(&Inst);
103 while (!ToVisit.empty()) {
104 User const *Curr = ToVisit.pop_back_val();
105 if (!Visited.insert(Curr).second)
107 if (isa<BlockAddress const>(Curr))
108 return false; // even a reference to self is likely to be not compatible
110 if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)
113 for (auto const &U : Curr->operands()) {
114 if (auto *UU = dyn_cast<User>(U))
115 ToVisit.push_back(UU);
119 // If explicitly requested, allow vastart and alloca. For invoke instructions
120 // verify that extraction is valid.
121 for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
122 if (isa<AllocaInst>(I)) {
128 if (const auto *II = dyn_cast<InvokeInst>(I)) {
129 // Unwind destination (either a landingpad, catchswitch, or cleanuppad)
130 // must be a part of the subgraph which is being extracted.
131 if (auto *UBB = II->getUnwindDest())
132 if (!Result.count(UBB))
137 // All catch handlers of a catchswitch instruction as well as the unwind
138 // destination must be in the subgraph.
139 if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) {
140 if (auto *UBB = CSI->getUnwindDest())
141 if (!Result.count(UBB))
143 for (auto *HBB : CSI->handlers())
144 if (!Result.count(const_cast<BasicBlock*>(HBB)))
149 // Make sure that entire catch handler is within subgraph. It is sufficient
150 // to check that catch return's block is in the list.
151 if (const auto *CPI = dyn_cast<CatchPadInst>(I)) {
152 for (const auto *U : CPI->users())
153 if (const auto *CRI = dyn_cast<CatchReturnInst>(U))
154 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
159 // And do similar checks for cleanup handler - the entire handler must be
160 // in subgraph which is going to be extracted. For cleanup return should
161 // additionally check that the unwind destination is also in the subgraph.
162 if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) {
163 for (const auto *U : CPI->users())
164 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
165 if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
169 if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) {
170 if (auto *UBB = CRI->getUnwindDest())
171 if (!Result.count(UBB))
176 if (const CallInst *CI = dyn_cast<CallInst>(I)) {
177 if (const Function *F = CI->getCalledFunction()) {
178 auto IID = F->getIntrinsicID();
179 if (IID == Intrinsic::vastart) {
186 // Currently, we miscompile outlined copies of eh_typid_for. There are
187 // proposals for fixing this in llvm.org/PR39545.
188 if (IID == Intrinsic::eh_typeid_for)
197 /// Build a set of blocks to extract if the input blocks are viable.
198 static SetVector<BasicBlock *>
199 buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
200 bool AllowVarArgs, bool AllowAlloca) {
201 assert(!BBs.empty() && "The set of blocks to extract must be non-empty");
202 SetVector<BasicBlock *> Result;
204 // Loop over the blocks, adding them to our set-vector, and aborting with an
205 // empty set if we encounter invalid blocks.
206 for (BasicBlock *BB : BBs) {
207 // If this block is dead, don't process it.
208 if (DT && !DT->isReachableFromEntry(BB))
211 if (!Result.insert(BB))
212 llvm_unreachable("Repeated basic blocks in extraction input");
215 LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName()
218 for (auto *BB : Result) {
219 if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca))
222 // Make sure that the first block is not a landing pad.
223 if (BB == Result.front()) {
225 LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n");
231 // All blocks other than the first must not have predecessors outside of
232 // the subgraph which is being extracted.
233 for (auto *PBB : predecessors(BB))
234 if (!Result.count(PBB)) {
235 LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from "
236 "outside the region except for the first block!\n"
237 << "Problematic source BB: " << BB->getName() << "\n"
238 << "Problematic destination BB: " << PBB->getName()
247 CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
248 bool AggregateArgs, BlockFrequencyInfo *BFI,
249 BranchProbabilityInfo *BPI, AssumptionCache *AC,
250 bool AllowVarArgs, bool AllowAlloca,
252 : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
253 BPI(BPI), AC(AC), AllowVarArgs(AllowVarArgs),
254 Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)),
257 CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs,
258 BlockFrequencyInfo *BFI,
259 BranchProbabilityInfo *BPI, AssumptionCache *AC,
261 : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
262 BPI(BPI), AC(AC), AllowVarArgs(false),
263 Blocks(buildExtractionBlockSet(L.getBlocks(), &DT,
264 /* AllowVarArgs */ false,
265 /* AllowAlloca */ false)),
268 /// definedInRegion - Return true if the specified value is defined in the
269 /// extracted region.
270 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
271 if (Instruction *I = dyn_cast<Instruction>(V))
272 if (Blocks.count(I->getParent()))
277 /// definedInCaller - Return true if the specified value is defined in the
278 /// function being code extracted, but not in the region being extracted.
279 /// These values must be passed in as live-ins to the function.
280 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
281 if (isa<Argument>(V)) return true;
282 if (Instruction *I = dyn_cast<Instruction>(V))
283 if (!Blocks.count(I->getParent()))
288 static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
289 BasicBlock *CommonExitBlock = nullptr;
290 auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
291 for (auto *Succ : successors(Block)) {
292 // Internal edges, ok.
293 if (Blocks.count(Succ))
295 if (!CommonExitBlock) {
296 CommonExitBlock = Succ;
299 if (CommonExitBlock != Succ)
305 if (any_of(Blocks, hasNonCommonExitSucc))
308 return CommonExitBlock;
311 CodeExtractorAnalysisCache::CodeExtractorAnalysisCache(Function &F) {
312 for (BasicBlock &BB : F) {
313 for (Instruction &II : BB.instructionsWithoutDebug())
314 if (auto *AI = dyn_cast<AllocaInst>(&II))
315 Allocas.push_back(AI);
317 findSideEffectInfoForBlock(BB);
321 void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) {
322 for (Instruction &II : BB.instructionsWithoutDebug()) {
323 unsigned Opcode = II.getOpcode();
324 Value *MemAddr = nullptr;
326 case Instruction::Store:
327 case Instruction::Load: {
328 if (Opcode == Instruction::Store) {
329 StoreInst *SI = cast<StoreInst>(&II);
330 MemAddr = SI->getPointerOperand();
332 LoadInst *LI = cast<LoadInst>(&II);
333 MemAddr = LI->getPointerOperand();
335 // Global variable can not be aliased with locals.
336 if (dyn_cast<Constant>(MemAddr))
338 Value *Base = MemAddr->stripInBoundsConstantOffsets();
339 if (!isa<AllocaInst>(Base)) {
340 SideEffectingBlocks.insert(&BB);
343 BaseMemAddrs[&BB].insert(Base);
347 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
349 if (IntrInst->isLifetimeStartOrEnd())
351 SideEffectingBlocks.insert(&BB);
354 // Treat all the other cases conservatively if it has side effects.
355 if (II.mayHaveSideEffects()) {
356 SideEffectingBlocks.insert(&BB);
364 bool CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr(
365 BasicBlock &BB, AllocaInst *Addr) const {
366 if (SideEffectingBlocks.count(&BB))
368 auto It = BaseMemAddrs.find(&BB);
369 if (It != BaseMemAddrs.end())
370 return It->second.count(Addr);
374 bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(
375 const CodeExtractorAnalysisCache &CEAC, Instruction *Addr) const {
376 AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
377 Function *Func = (*Blocks.begin())->getParent();
378 for (BasicBlock &BB : *Func) {
379 if (Blocks.count(&BB))
381 if (CEAC.doesBlockContainClobberOfAddr(BB, AI))
388 CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
389 BasicBlock *SinglePredFromOutlineRegion = nullptr;
390 assert(!Blocks.count(CommonExitBlock) &&
391 "Expect a block outside the region!");
392 for (auto *Pred : predecessors(CommonExitBlock)) {
393 if (!Blocks.count(Pred))
395 if (!SinglePredFromOutlineRegion) {
396 SinglePredFromOutlineRegion = Pred;
397 } else if (SinglePredFromOutlineRegion != Pred) {
398 SinglePredFromOutlineRegion = nullptr;
403 if (SinglePredFromOutlineRegion)
404 return SinglePredFromOutlineRegion;
407 auto getFirstPHI = [](BasicBlock *BB) {
408 BasicBlock::iterator I = BB->begin();
409 PHINode *FirstPhi = nullptr;
410 while (I != BB->end()) {
411 PHINode *Phi = dyn_cast<PHINode>(I);
421 // If there are any phi nodes, the single pred either exists or has already
422 // be created before code extraction.
423 assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
426 BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
427 CommonExitBlock->getFirstNonPHI()->getIterator());
429 for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock);
431 BasicBlock *Pred = *PI++;
432 if (Blocks.count(Pred))
434 Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
436 // Now add the old exit block to the outline region.
437 Blocks.insert(CommonExitBlock);
438 return CommonExitBlock;
441 // Find the pair of life time markers for address 'Addr' that are either
442 // defined inside the outline region or can legally be shrinkwrapped into the
443 // outline region. If there are not other untracked uses of the address, return
444 // the pair of markers if found; otherwise return a pair of nullptr.
445 CodeExtractor::LifetimeMarkerInfo
446 CodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
448 BasicBlock *ExitBlock) const {
449 LifetimeMarkerInfo Info;
451 for (User *U : Addr->users()) {
452 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
454 // We don't model addresses with multiple start/end markers, but the
455 // markers do not need to be in the region.
456 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
459 Info.LifeStart = IntrInst;
462 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
465 Info.LifeEnd = IntrInst;
468 // At this point, permit debug uses outside of the region.
469 // This is fixed in a later call to fixupDebugInfoPostExtraction().
470 if (isa<DbgInfoIntrinsic>(IntrInst))
473 // Find untracked uses of the address, bail.
474 if (!definedInRegion(Blocks, U))
478 if (!Info.LifeStart || !Info.LifeEnd)
481 Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart);
482 Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd);
483 // Do legality check.
484 if ((Info.SinkLifeStart || Info.HoistLifeEnd) &&
485 !isLegalToShrinkwrapLifetimeMarkers(CEAC, Addr))
488 // Check to see if we have a place to do hoisting, if not, bail.
489 if (Info.HoistLifeEnd && !ExitBlock)
495 void CodeExtractor::findAllocas(const CodeExtractorAnalysisCache &CEAC,
496 ValueSet &SinkCands, ValueSet &HoistCands,
497 BasicBlock *&ExitBlock) const {
498 Function *Func = (*Blocks.begin())->getParent();
499 ExitBlock = getCommonExitBlock(Blocks);
501 auto moveOrIgnoreLifetimeMarkers =
502 [&](const LifetimeMarkerInfo &LMI) -> bool {
505 if (LMI.SinkLifeStart) {
506 LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart
508 SinkCands.insert(LMI.LifeStart);
510 if (LMI.HoistLifeEnd) {
511 LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n");
512 HoistCands.insert(LMI.LifeEnd);
517 // Look up allocas in the original function in CodeExtractorAnalysisCache, as
518 // this is much faster than walking all the instructions.
519 for (AllocaInst *AI : CEAC.getAllocas()) {
520 BasicBlock *BB = AI->getParent();
521 if (Blocks.count(BB))
524 // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca,
525 // check whether it is actually still in the original function.
526 Function *AIFunc = BB->getParent();
530 LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock);
531 bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);
533 LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n");
534 SinkCands.insert(AI);
538 // Follow any bitcasts.
539 SmallVector<Instruction *, 2> Bitcasts;
540 SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo;
541 for (User *U : AI->users()) {
542 if (U->stripInBoundsConstantOffsets() == AI) {
543 Instruction *Bitcast = cast<Instruction>(U);
544 LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock);
546 Bitcasts.push_back(Bitcast);
547 BitcastLifetimeInfo.push_back(LMI);
552 // Found unknown use of AI.
553 if (!definedInRegion(Blocks, U)) {
559 // Either no bitcasts reference the alloca or there are unknown uses.
560 if (Bitcasts.empty())
563 LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n");
564 SinkCands.insert(AI);
565 for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) {
566 Instruction *BitcastAddr = Bitcasts[I];
567 const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I];
568 assert(LMI.LifeStart &&
569 "Unsafe to sink bitcast without lifetime markers");
570 moveOrIgnoreLifetimeMarkers(LMI);
571 if (!definedInRegion(Blocks, BitcastAddr)) {
572 LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr
574 SinkCands.insert(BitcastAddr);
580 bool CodeExtractor::isEligible() const {
583 BasicBlock *Header = *Blocks.begin();
584 Function *F = Header->getParent();
586 // For functions with varargs, check that varargs handling is only done in the
587 // outlined function, i.e vastart and vaend are only used in outlined blocks.
588 if (AllowVarArgs && F->getFunctionType()->isVarArg()) {
589 auto containsVarArgIntrinsic = [](const Instruction &I) {
590 if (const CallInst *CI = dyn_cast<CallInst>(&I))
591 if (const Function *Callee = CI->getCalledFunction())
592 return Callee->getIntrinsicID() == Intrinsic::vastart ||
593 Callee->getIntrinsicID() == Intrinsic::vaend;
597 for (auto &BB : *F) {
598 if (Blocks.count(&BB))
600 if (llvm::any_of(BB, containsVarArgIntrinsic))
607 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
608 const ValueSet &SinkCands) const {
609 for (BasicBlock *BB : Blocks) {
610 // If a used value is defined outside the region, it's an input. If an
611 // instruction is used outside the region, it's an output.
612 for (Instruction &II : *BB) {
613 for (auto &OI : II.operands()) {
615 if (!SinkCands.count(V) && definedInCaller(Blocks, V))
619 for (User *U : II.users())
620 if (!definedInRegion(Blocks, U)) {
628 /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside
629 /// of the region, we need to split the entry block of the region so that the
630 /// PHI node is easier to deal with.
631 void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {
632 unsigned NumPredsFromRegion = 0;
633 unsigned NumPredsOutsideRegion = 0;
635 if (Header != &Header->getParent()->getEntryBlock()) {
636 PHINode *PN = dyn_cast<PHINode>(Header->begin());
637 if (!PN) return; // No PHI nodes.
639 // If the header node contains any PHI nodes, check to see if there is more
640 // than one entry from outside the region. If so, we need to sever the
641 // header block into two.
642 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
643 if (Blocks.count(PN->getIncomingBlock(i)))
644 ++NumPredsFromRegion;
646 ++NumPredsOutsideRegion;
648 // If there is one (or fewer) predecessor from outside the region, we don't
649 // need to do anything special.
650 if (NumPredsOutsideRegion <= 1) return;
653 // Otherwise, we need to split the header block into two pieces: one
654 // containing PHI nodes merging values from outside of the region, and a
655 // second that contains all of the code for the block and merges back any
656 // incoming values from inside of the region.
657 BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
659 // We only want to code extract the second block now, and it becomes the new
660 // header of the region.
661 BasicBlock *OldPred = Header;
662 Blocks.remove(OldPred);
663 Blocks.insert(NewBB);
666 // Okay, now we need to adjust the PHI nodes and any branches from within the
667 // region to go to the new header block instead of the old header block.
668 if (NumPredsFromRegion) {
669 PHINode *PN = cast<PHINode>(OldPred->begin());
670 // Loop over all of the predecessors of OldPred that are in the region,
671 // changing them to branch to NewBB instead.
672 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
673 if (Blocks.count(PN->getIncomingBlock(i))) {
674 Instruction *TI = PN->getIncomingBlock(i)->getTerminator();
675 TI->replaceUsesOfWith(OldPred, NewBB);
678 // Okay, everything within the region is now branching to the right block, we
679 // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
680 BasicBlock::iterator AfterPHIs;
681 for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
682 PHINode *PN = cast<PHINode>(AfterPHIs);
683 // Create a new PHI node in the new region, which has an incoming value
684 // from OldPred of PN.
685 PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
686 PN->getName() + ".ce", &NewBB->front());
687 PN->replaceAllUsesWith(NewPN);
688 NewPN->addIncoming(PN, OldPred);
690 // Loop over all of the incoming value in PN, moving them to NewPN if they
691 // are from the extracted region.
692 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
693 if (Blocks.count(PN->getIncomingBlock(i))) {
694 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
695 PN->removeIncomingValue(i);
703 /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
704 /// outlined region, we split these PHIs on two: one with inputs from region
705 /// and other with remaining incoming blocks; then first PHIs are placed in
707 void CodeExtractor::severSplitPHINodesOfExits(
708 const SmallPtrSetImpl<BasicBlock *> &Exits) {
709 for (BasicBlock *ExitBB : Exits) {
710 BasicBlock *NewBB = nullptr;
712 for (PHINode &PN : ExitBB->phis()) {
713 // Find all incoming values from the outlining region.
714 SmallVector<unsigned, 2> IncomingVals;
715 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
716 if (Blocks.count(PN.getIncomingBlock(i)))
717 IncomingVals.push_back(i);
719 // Do not process PHI if there is one (or fewer) predecessor from region.
720 // If PHI has exactly one predecessor from region, only this one incoming
721 // will be replaced on codeRepl block, so it should be safe to skip PHI.
722 if (IncomingVals.size() <= 1)
725 // Create block for new PHIs and add it to the list of outlined if it
726 // wasn't done before.
728 NewBB = BasicBlock::Create(ExitBB->getContext(),
729 ExitBB->getName() + ".split",
730 ExitBB->getParent(), ExitBB);
731 SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB),
733 for (BasicBlock *PredBB : Preds)
734 if (Blocks.count(PredBB))
735 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
736 BranchInst::Create(ExitBB, NewBB);
737 Blocks.insert(NewBB);
742 PHINode::Create(PN.getType(), IncomingVals.size(),
743 PN.getName() + ".ce", NewBB->getFirstNonPHI());
744 for (unsigned i : IncomingVals)
745 NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));
746 for (unsigned i : reverse(IncomingVals))
747 PN.removeIncomingValue(i, false);
748 PN.addIncoming(NewPN, NewBB);
753 void CodeExtractor::splitReturnBlocks() {
754 for (BasicBlock *Block : Blocks)
755 if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
757 Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
759 // Old dominates New. New node dominates all other nodes dominated
761 DomTreeNode *OldNode = DT->getNode(Block);
762 SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
765 DomTreeNode *NewNode = DT->addNewBlock(New, Block);
767 for (DomTreeNode *I : Children)
768 DT->changeImmediateDominator(I, NewNode);
773 /// constructFunction - make a function based on inputs and outputs, as follows:
774 /// f(in0, ..., inN, out0, ..., outN)
775 Function *CodeExtractor::constructFunction(const ValueSet &inputs,
776 const ValueSet &outputs,
778 BasicBlock *newRootNode,
779 BasicBlock *newHeader,
780 Function *oldFunction,
782 LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
783 LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
785 // This function returns unsigned, outputs will go back by reference.
786 switch (NumExitBlocks) {
788 case 1: RetTy = Type::getVoidTy(header->getContext()); break;
789 case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
790 default: RetTy = Type::getInt16Ty(header->getContext()); break;
793 std::vector<Type *> paramTy;
795 // Add the types of the input values to the function's argument list
796 for (Value *value : inputs) {
797 LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
798 paramTy.push_back(value->getType());
801 // Add the types of the output values to the function's argument list.
802 for (Value *output : outputs) {
803 LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
805 paramTy.push_back(output->getType());
807 paramTy.push_back(PointerType::getUnqual(output->getType()));
811 dbgs() << "Function type: " << *RetTy << " f(";
812 for (Type *i : paramTy)
813 dbgs() << *i << ", ";
817 StructType *StructTy = nullptr;
818 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
819 StructTy = StructType::get(M->getContext(), paramTy);
821 paramTy.push_back(PointerType::getUnqual(StructTy));
823 FunctionType *funcType =
824 FunctionType::get(RetTy, paramTy,
825 AllowVarArgs && oldFunction->isVarArg());
827 std::string SuffixToUse =
829 ? (header->getName().empty() ? "extracted" : header->getName().str())
831 // Create the new function
832 Function *newFunction = Function::Create(
833 funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
834 oldFunction->getName() + "." + SuffixToUse, M);
835 // If the old function is no-throw, so is the new one.
836 if (oldFunction->doesNotThrow())
837 newFunction->setDoesNotThrow();
839 // Inherit the uwtable attribute if we need to.
840 if (oldFunction->hasUWTable())
841 newFunction->setHasUWTable();
843 // Inherit all of the target dependent attributes and white-listed
844 // target independent attributes.
845 // (e.g. If the extracted region contains a call to an x86.sse
846 // instruction we need to make sure that the extracted region has the
847 // "target-features" attribute allowing it to be lowered.
848 // FIXME: This should be changed to check to see if a specific
849 // attribute can not be inherited.
850 for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) {
851 if (Attr.isStringAttribute()) {
852 if (Attr.getKindAsString() == "thunk")
855 switch (Attr.getKindAsEnum()) {
856 // Those attributes cannot be propagated safely. Explicitly list them
857 // here so we get a warning if new attributes are added. This list also
858 // includes non-function attributes.
859 case Attribute::Alignment:
860 case Attribute::AllocSize:
861 case Attribute::ArgMemOnly:
862 case Attribute::Builtin:
863 case Attribute::ByVal:
864 case Attribute::Convergent:
865 case Attribute::Dereferenceable:
866 case Attribute::DereferenceableOrNull:
867 case Attribute::InAlloca:
868 case Attribute::InReg:
869 case Attribute::InaccessibleMemOnly:
870 case Attribute::InaccessibleMemOrArgMemOnly:
871 case Attribute::JumpTable:
872 case Attribute::Naked:
873 case Attribute::Nest:
874 case Attribute::NoAlias:
875 case Attribute::NoBuiltin:
876 case Attribute::NoCapture:
877 case Attribute::NoMerge:
878 case Attribute::NoReturn:
879 case Attribute::NoSync:
880 case Attribute::NoUndef:
881 case Attribute::None:
882 case Attribute::NonNull:
883 case Attribute::Preallocated:
884 case Attribute::ReadNone:
885 case Attribute::ReadOnly:
886 case Attribute::Returned:
887 case Attribute::ReturnsTwice:
888 case Attribute::SExt:
889 case Attribute::Speculatable:
890 case Attribute::StackAlignment:
891 case Attribute::StructRet:
892 case Attribute::SwiftError:
893 case Attribute::SwiftSelf:
894 case Attribute::WillReturn:
895 case Attribute::WriteOnly:
896 case Attribute::ZExt:
897 case Attribute::ImmArg:
898 case Attribute::EndAttrKinds:
899 case Attribute::EmptyKey:
900 case Attribute::TombstoneKey:
902 // Those attributes should be safe to propagate to the extracted function.
903 case Attribute::AlwaysInline:
904 case Attribute::Cold:
905 case Attribute::NoRecurse:
906 case Attribute::InlineHint:
907 case Attribute::MinSize:
908 case Attribute::NoDuplicate:
909 case Attribute::NoFree:
910 case Attribute::NoImplicitFloat:
911 case Attribute::NoInline:
912 case Attribute::NonLazyBind:
913 case Attribute::NoRedZone:
914 case Attribute::NoUnwind:
915 case Attribute::NullPointerIsValid:
916 case Attribute::OptForFuzzing:
917 case Attribute::OptimizeNone:
918 case Attribute::OptimizeForSize:
919 case Attribute::SafeStack:
920 case Attribute::ShadowCallStack:
921 case Attribute::SanitizeAddress:
922 case Attribute::SanitizeMemory:
923 case Attribute::SanitizeThread:
924 case Attribute::SanitizeHWAddress:
925 case Attribute::SanitizeMemTag:
926 case Attribute::SpeculativeLoadHardening:
927 case Attribute::StackProtect:
928 case Attribute::StackProtectReq:
929 case Attribute::StackProtectStrong:
930 case Attribute::StrictFP:
931 case Attribute::UWTable:
932 case Attribute::NoCfCheck:
936 newFunction->addFnAttr(Attr);
938 newFunction->getBasicBlockList().push_back(newRootNode);
940 // Create an iterator to name all of the arguments we inserted.
941 Function::arg_iterator AI = newFunction->arg_begin();
943 // Rewrite all users of the inputs in the extracted region to use the
944 // arguments (or appropriate addressing into struct) instead.
945 for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
949 Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
950 Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
951 Instruction *TI = newFunction->begin()->getTerminator();
952 GetElementPtrInst *GEP = GetElementPtrInst::Create(
953 StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
954 RewriteVal = new LoadInst(StructTy->getElementType(i), GEP,
955 "loadgep_" + inputs[i]->getName(), TI);
959 std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
960 for (User *use : Users)
961 if (Instruction *inst = dyn_cast<Instruction>(use))
962 if (Blocks.count(inst->getParent()))
963 inst->replaceUsesOfWith(inputs[i], RewriteVal);
966 // Set names for input and output arguments.
967 if (!AggregateArgs) {
968 AI = newFunction->arg_begin();
969 for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
970 AI->setName(inputs[i]->getName());
971 for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
972 AI->setName(outputs[i]->getName()+".out");
975 // Rewrite branches to basic blocks outside of the loop to new dummy blocks
976 // within the new function. This must be done before we lose track of which
977 // blocks were originally in the code region.
978 std::vector<User *> Users(header->user_begin(), header->user_end());
979 for (auto &U : Users)
980 // The BasicBlock which contains the branch is not in the region
981 // modify the branch target to a new block
982 if (Instruction *I = dyn_cast<Instruction>(U))
983 if (I->isTerminator() && I->getFunction() == oldFunction &&
984 !Blocks.count(I->getParent()))
985 I->replaceUsesOfWith(header, newHeader);
990 /// Erase lifetime.start markers which reference inputs to the extraction
991 /// region, and insert the referenced memory into \p LifetimesStart.
993 /// The extraction region is defined by a set of blocks (\p Blocks), and a set
994 /// of allocas which will be moved from the caller function into the extracted
995 /// function (\p SunkAllocas).
996 static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks,
997 const SetVector<Value *> &SunkAllocas,
998 SetVector<Value *> &LifetimesStart) {
999 for (BasicBlock *BB : Blocks) {
1000 for (auto It = BB->begin(), End = BB->end(); It != End;) {
1001 auto *II = dyn_cast<IntrinsicInst>(&*It);
1003 if (!II || !II->isLifetimeStartOrEnd())
1006 // Get the memory operand of the lifetime marker. If the underlying
1007 // object is a sunk alloca, or is otherwise defined in the extraction
1008 // region, the lifetime marker must not be erased.
1009 Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1010 if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1013 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1014 LifetimesStart.insert(Mem);
1015 II->eraseFromParent();
1020 /// Insert lifetime start/end markers surrounding the call to the new function
1021 /// for objects defined in the caller.
1022 static void insertLifetimeMarkersSurroundingCall(
1023 Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1024 CallInst *TheCall) {
1025 LLVMContext &Ctx = M->getContext();
1026 auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
1027 auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1028 Instruction *Term = TheCall->getParent()->getTerminator();
1030 // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
1031 // needed to satisfy this requirement so they may be reused.
1032 DenseMap<Value *, Value *> Bitcasts;
1034 // Emit lifetime markers for the pointers given in \p Objects. Insert the
1035 // markers before the call if \p InsertBefore, and after the call otherwise.
1036 auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
1037 bool InsertBefore) {
1038 for (Value *Mem : Objects) {
1039 assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1040 TheCall->getFunction()) &&
1041 "Input memory not defined in original function");
1042 Value *&MemAsI8Ptr = Bitcasts[Mem];
1044 if (Mem->getType() == Int8PtrTy)
1048 CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
1051 auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
1053 Marker->insertBefore(TheCall);
1055 Marker->insertBefore(Term);
1059 if (!LifetimesStart.empty()) {
1060 auto StartFn = llvm::Intrinsic::getDeclaration(
1061 M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
1062 insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
1065 if (!LifetimesEnd.empty()) {
1066 auto EndFn = llvm::Intrinsic::getDeclaration(
1067 M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
1068 insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
1072 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
1073 /// the call instruction, splitting any PHI nodes in the header block as
1075 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1076 BasicBlock *codeReplacer,
1078 ValueSet &outputs) {
1079 // Emit a call to the new function, passing in: *pointer to struct (if
1080 // aggregating parameters), or plan inputs and allocated memory for outputs
1081 std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
1083 Module *M = newFunction->getParent();
1084 LLVMContext &Context = M->getContext();
1085 const DataLayout &DL = M->getDataLayout();
1086 CallInst *call = nullptr;
1088 // Add inputs as params, or to be filled into the struct
1090 SmallVector<unsigned, 1> SwiftErrorArgs;
1091 for (Value *input : inputs) {
1093 StructValues.push_back(input);
1095 params.push_back(input);
1096 if (input->isSwiftError())
1097 SwiftErrorArgs.push_back(ArgNo);
1102 // Create allocas for the outputs
1103 for (Value *output : outputs) {
1104 if (AggregateArgs) {
1105 StructValues.push_back(output);
1107 AllocaInst *alloca =
1108 new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1109 nullptr, output->getName() + ".loc",
1110 &codeReplacer->getParent()->front().front());
1111 ReloadOutputs.push_back(alloca);
1112 params.push_back(alloca);
1116 StructType *StructArgTy = nullptr;
1117 AllocaInst *Struct = nullptr;
1118 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
1119 std::vector<Type *> ArgTypes;
1120 for (ValueSet::iterator v = StructValues.begin(),
1121 ve = StructValues.end(); v != ve; ++v)
1122 ArgTypes.push_back((*v)->getType());
1124 // Allocate a struct at the beginning of this function
1125 StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1126 Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
1128 &codeReplacer->getParent()->front().front());
1129 params.push_back(Struct);
1131 for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
1133 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1134 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
1135 GetElementPtrInst *GEP = GetElementPtrInst::Create(
1136 StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1137 codeReplacer->getInstList().push_back(GEP);
1138 new StoreInst(StructValues[i], GEP, codeReplacer);
1142 // Emit the call to the function
1143 call = CallInst::Create(newFunction, params,
1144 NumExitBlocks > 1 ? "targetBlock" : "");
1145 // Add debug location to the new call, if the original function has debug
1146 // info. In that case, the terminator of the entry block of the extracted
1147 // function contains the first debug location of the extracted function,
1148 // set in extractCodeRegion.
1149 if (codeReplacer->getParent()->getSubprogram()) {
1150 if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1151 call->setDebugLoc(DL);
1153 codeReplacer->getInstList().push_back(call);
1155 // Set swifterror parameter attributes.
1156 for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1157 call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1158 newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1161 Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
1162 unsigned FirstOut = inputs.size();
1164 std::advance(OutputArgBegin, inputs.size());
1166 // Reload the outputs passed in by reference.
1167 for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1168 Value *Output = nullptr;
1169 if (AggregateArgs) {
1171 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1172 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1173 GetElementPtrInst *GEP = GetElementPtrInst::Create(
1174 StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1175 codeReplacer->getInstList().push_back(GEP);
1178 Output = ReloadOutputs[i];
1180 LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1181 outputs[i]->getName() + ".reload",
1183 Reloads.push_back(load);
1184 std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1185 for (unsigned u = 0, e = Users.size(); u != e; ++u) {
1186 Instruction *inst = cast<Instruction>(Users[u]);
1187 if (!Blocks.count(inst->getParent()))
1188 inst->replaceUsesOfWith(outputs[i], load);
1192 // Now we can emit a switch statement using the call as a value.
1193 SwitchInst *TheSwitch =
1194 SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
1195 codeReplacer, 0, codeReplacer);
1197 // Since there may be multiple exits from the original region, make the new
1198 // function return an unsigned, switch on that number. This loop iterates
1199 // over all of the blocks in the extracted region, updating any terminator
1200 // instructions in the to-be-extracted region that branch to blocks that are
1201 // not in the region to be extracted.
1202 std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1204 unsigned switchVal = 0;
1205 for (BasicBlock *Block : Blocks) {
1206 Instruction *TI = Block->getTerminator();
1207 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
1208 if (!Blocks.count(TI->getSuccessor(i))) {
1209 BasicBlock *OldTarget = TI->getSuccessor(i);
1210 // add a new basic block which returns the appropriate value
1211 BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1213 // If we don't already have an exit stub for this non-extracted
1214 // destination, create one now!
1215 NewTarget = BasicBlock::Create(Context,
1216 OldTarget->getName() + ".exitStub",
1218 unsigned SuccNum = switchVal++;
1220 Value *brVal = nullptr;
1221 switch (NumExitBlocks) {
1223 case 1: break; // No value needed.
1224 case 2: // Conditional branch, return a bool
1225 brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1228 brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1232 ReturnInst::Create(Context, brVal, NewTarget);
1234 // Update the switch instruction.
1235 TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
1240 // rewrite the original branch instruction with this new target
1241 TI->setSuccessor(i, NewTarget);
1245 // Store the arguments right after the definition of output value.
1246 // This should be proceeded after creating exit stubs to be ensure that invoke
1247 // result restore will be placed in the outlined function.
1248 Function::arg_iterator OAI = OutputArgBegin;
1249 for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1250 auto *OutI = dyn_cast<Instruction>(outputs[i]);
1254 // Find proper insertion point.
1255 BasicBlock::iterator InsertPt;
1256 // In case OutI is an invoke, we insert the store at the beginning in the
1257 // 'normal destination' BB. Otherwise we insert the store right after OutI.
1258 if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1259 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1260 else if (auto *Phi = dyn_cast<PHINode>(OutI))
1261 InsertPt = Phi->getParent()->getFirstInsertionPt();
1263 InsertPt = std::next(OutI->getIterator());
1265 Instruction *InsertBefore = &*InsertPt;
1266 assert((InsertBefore->getFunction() == newFunction ||
1267 Blocks.count(InsertBefore->getParent())) &&
1268 "InsertPt should be in new function");
1269 assert(OAI != newFunction->arg_end() &&
1270 "Number of output arguments should match "
1271 "the amount of defined values");
1272 if (AggregateArgs) {
1274 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1275 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1276 GetElementPtrInst *GEP = GetElementPtrInst::Create(
1277 StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(),
1279 new StoreInst(outputs[i], GEP, InsertBefore);
1280 // Since there should be only one struct argument aggregating
1281 // all the output values, we shouldn't increment OAI, which always
1282 // points to the struct argument, in this case.
1284 new StoreInst(outputs[i], &*OAI, InsertBefore);
1289 // Now that we've done the deed, simplify the switch instruction.
1290 Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1291 switch (NumExitBlocks) {
1293 // There are no successors (the block containing the switch itself), which
1294 // means that previously this was the last part of the function, and hence
1295 // this should be rewritten as a `ret'
1297 // Check if the function should return a value
1298 if (OldFnRetTy->isVoidTy()) {
1299 ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
1300 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1301 // return what we have
1302 ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1304 // Otherwise we must have code extracted an unwind or something, just
1305 // return whatever we want.
1306 ReturnInst::Create(Context,
1307 Constant::getNullValue(OldFnRetTy), TheSwitch);
1310 TheSwitch->eraseFromParent();
1313 // Only a single destination, change the switch into an unconditional
1315 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1316 TheSwitch->eraseFromParent();
1319 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1321 TheSwitch->eraseFromParent();
1324 // Otherwise, make the default destination of the switch instruction be one
1325 // of the other successors.
1326 TheSwitch->setCondition(call);
1327 TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1328 // Remove redundant case
1329 TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1333 // Insert lifetime markers around the reloads of any output values. The
1334 // allocas output values are stored in are only in-use in the codeRepl block.
1335 insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1340 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1341 Function *oldFunc = (*Blocks.begin())->getParent();
1342 Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1343 Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1345 for (BasicBlock *Block : Blocks) {
1346 // Delete the basic block from the old function, and the list of blocks
1347 oldBlocks.remove(Block);
1349 // Insert this basic block into the new function
1350 newBlocks.push_back(Block);
1354 void CodeExtractor::calculateNewCallTerminatorWeights(
1355 BasicBlock *CodeReplacer,
1356 DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
1357 BranchProbabilityInfo *BPI) {
1358 using Distribution = BlockFrequencyInfoImplBase::Distribution;
1359 using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1361 // Update the branch weights for the exit block.
1362 Instruction *TI = CodeReplacer->getTerminator();
1363 SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1365 // Block Frequency distribution with dummy node.
1366 Distribution BranchDist;
1368 SmallVector<BranchProbability, 4> EdgeProbabilities(
1369 TI->getNumSuccessors(), BranchProbability::getUnknown());
1371 // Add each of the frequencies of the successors.
1372 for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1373 BlockNode ExitNode(i);
1374 uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1376 BranchDist.addExit(ExitNode, ExitFreq);
1378 EdgeProbabilities[i] = BranchProbability::getZero();
1381 // Check for no total weight.
1382 if (BranchDist.Total == 0) {
1383 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1387 // Normalize the distribution so that they can fit in unsigned.
1388 BranchDist.normalize();
1390 // Create normalized branch weights and set the metadata.
1391 for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1392 const auto &Weight = BranchDist.Weights[I];
1394 // Get the weight and update the current BFI.
1395 BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1396 BranchProbability BP(Weight.Amount, BranchDist.Total);
1397 EdgeProbabilities[Weight.TargetNode.Index] = BP;
1399 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1401 LLVMContext::MD_prof,
1402 MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1405 /// Erase debug info intrinsics which refer to values in \p F but aren't in
1407 static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F) {
1408 for (Instruction &I : instructions(F)) {
1409 SmallVector<DbgVariableIntrinsic *, 4> DbgUsers;
1410 findDbgUsers(DbgUsers, &I);
1411 for (DbgVariableIntrinsic *DVI : DbgUsers)
1412 if (DVI->getFunction() != &F)
1413 DVI->eraseFromParent();
1417 /// Fix up the debug info in the old and new functions by pointing line
1418 /// locations and debug intrinsics to the new subprogram scope, and by deleting
1419 /// intrinsics which point to values outside of the new function.
1420 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1421 CallInst &TheCall) {
1422 DISubprogram *OldSP = OldFunc.getSubprogram();
1423 LLVMContext &Ctx = OldFunc.getContext();
1426 // Erase any debug info the new function contains.
1427 stripDebugInfo(NewFunc);
1428 // Make sure the old function doesn't contain any non-local metadata refs.
1429 eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1433 // Create a subprogram for the new function. Leave out a description of the
1434 // function arguments, as the parameters don't correspond to anything at the
1436 assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1437 DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolvedNodes=*/false,
1439 auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
1440 DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1441 DISubprogram::SPFlagOptimized |
1442 DISubprogram::SPFlagLocalToUnit;
1443 auto NewSP = DIB.createFunction(
1444 OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1445 /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1446 NewFunc.setSubprogram(NewSP);
1448 // Debug intrinsics in the new function need to be updated in one of two
1450 // 1) They need to be deleted, because they describe a value in the old
1452 // 2) They need to point to fresh metadata, e.g. because they currently
1453 // point to a variable in the wrong scope.
1454 SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1455 SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1456 for (Instruction &I : instructions(NewFunc)) {
1457 auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1461 // Point the intrinsic to a fresh label within the new function.
1462 if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1463 DILabel *OldLabel = DLI->getLabel();
1464 DINode *&NewLabel = RemappedMetadata[OldLabel];
1466 NewLabel = DILabel::get(Ctx, NewSP, OldLabel->getName(),
1467 OldLabel->getFile(), OldLabel->getLine());
1468 DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
1472 // If the location isn't a constant or an instruction, delete the
1474 auto *DVI = cast<DbgVariableIntrinsic>(DII);
1475 Value *Location = DVI->getVariableLocation();
1477 (!isa<Constant>(Location) && !isa<Instruction>(Location))) {
1478 DebugIntrinsicsToDelete.push_back(DVI);
1482 // If the variable location is an instruction but isn't in the new
1483 // function, delete the intrinsic.
1484 Instruction *LocationInst = dyn_cast<Instruction>(Location);
1485 if (LocationInst && LocationInst->getFunction() != &NewFunc) {
1486 DebugIntrinsicsToDelete.push_back(DVI);
1490 // Point the intrinsic to a fresh variable within the new function.
1491 DILocalVariable *OldVar = DVI->getVariable();
1492 DINode *&NewVar = RemappedMetadata[OldVar];
1494 NewVar = DIB.createAutoVariable(
1495 NewSP, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1496 OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1497 OldVar->getAlignInBits());
1498 DVI->setArgOperand(1, MetadataAsValue::get(Ctx, NewVar));
1500 for (auto *DII : DebugIntrinsicsToDelete)
1501 DII->eraseFromParent();
1502 DIB.finalizeSubprogram(NewSP);
1504 // Fix up the scope information attached to the line locations in the new
1506 for (Instruction &I : instructions(NewFunc)) {
1507 if (const DebugLoc &DL = I.getDebugLoc())
1508 I.setDebugLoc(DebugLoc::get(DL.getLine(), DL.getCol(), NewSP));
1510 // Loop info metadata may contain line locations. Fix them up.
1511 auto updateLoopInfoLoc = [&Ctx,
1512 NewSP](const DILocation &Loc) -> DILocation * {
1513 return DILocation::get(Ctx, Loc.getLine(), Loc.getColumn(), NewSP,
1516 updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1518 if (!TheCall.getDebugLoc())
1519 TheCall.setDebugLoc(DebugLoc::get(0, 0, OldSP));
1521 eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1525 CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) {
1529 // Assumption: this is a single-entry code region, and the header is the first
1530 // block in the region.
1531 BasicBlock *header = *Blocks.begin();
1532 Function *oldFunction = header->getParent();
1534 // Calculate the entry frequency of the new function before we change the root
1536 BlockFrequency EntryFreq;
1538 assert(BPI && "Both BPI and BFI are required to preserve profile info");
1539 for (BasicBlock *Pred : predecessors(header)) {
1540 if (Blocks.count(Pred))
1543 BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1547 // Remove @llvm.assume calls that will be moved to the new function from the
1548 // old function's assumption cache.
1549 for (BasicBlock *Block : Blocks) {
1550 for (auto It = Block->begin(), End = Block->end(); It != End;) {
1551 Instruction *I = &*It;
1554 if (match(I, m_Intrinsic<Intrinsic::assume>())) {
1556 AC->unregisterAssumption(cast<CallInst>(I));
1557 I->eraseFromParent();
1562 // If we have any return instructions in the region, split those blocks so
1563 // that the return is not in the region.
1564 splitReturnBlocks();
1566 // Calculate the exit blocks for the extracted region and the total exit
1567 // weights for each of those blocks.
1568 DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
1569 SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1570 for (BasicBlock *Block : Blocks) {
1571 for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
1573 if (!Blocks.count(*SI)) {
1574 // Update the branch weight for this successor.
1576 BlockFrequency &BF = ExitWeights[*SI];
1577 BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
1579 ExitBlocks.insert(*SI);
1583 NumExitBlocks = ExitBlocks.size();
1585 // If we have to split PHI nodes of the entry or exit blocks, do so now.
1586 severSplitPHINodesOfEntry(header);
1587 severSplitPHINodesOfExits(ExitBlocks);
1589 // This takes place of the original loop
1590 BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1591 "codeRepl", oldFunction,
1594 // The new function needs a root node because other nodes can branch to the
1595 // head of the region, but the entry node of a function cannot have preds.
1596 BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1598 auto *BranchI = BranchInst::Create(header);
1599 // If the original function has debug info, we have to add a debug location
1600 // to the new branch instruction from the artificial entry block.
1601 // We use the debug location of the first instruction in the extracted
1602 // blocks, as there is no other equivalent line in the source code.
1603 if (oldFunction->getSubprogram()) {
1604 any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1605 return any_of(*BB, [&BranchI](const Instruction &I) {
1606 if (!I.getDebugLoc())
1608 BranchI->setDebugLoc(I.getDebugLoc());
1613 newFuncRoot->getInstList().push_back(BranchI);
1615 ValueSet inputs, outputs, SinkingCands, HoistingCands;
1616 BasicBlock *CommonExit = nullptr;
1617 findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1618 assert(HoistingCands.empty() || CommonExit);
1620 // Find inputs to, outputs from the code region.
1621 findInputsOutputs(inputs, outputs, SinkingCands);
1623 // Now sink all instructions which only have non-phi uses inside the region.
1624 // Group the allocas at the start of the block, so that any bitcast uses of
1625 // the allocas are well-defined.
1626 AllocaInst *FirstSunkAlloca = nullptr;
1627 for (auto *II : SinkingCands) {
1628 if (auto *AI = dyn_cast<AllocaInst>(II)) {
1629 AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1630 if (!FirstSunkAlloca)
1631 FirstSunkAlloca = AI;
1634 assert((SinkingCands.empty() || FirstSunkAlloca) &&
1635 "Did not expect a sink candidate without any allocas");
1636 for (auto *II : SinkingCands) {
1637 if (!isa<AllocaInst>(II)) {
1638 cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1642 if (!HoistingCands.empty()) {
1643 auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1644 Instruction *TI = HoistToBlock->getTerminator();
1645 for (auto *II : HoistingCands)
1646 cast<Instruction>(II)->moveBefore(TI);
1649 // Collect objects which are inputs to the extraction region and also
1650 // referenced by lifetime start markers within it. The effects of these
1651 // markers must be replicated in the calling function to prevent the stack
1652 // coloring pass from merging slots which store input objects.
1653 ValueSet LifetimesStart;
1654 eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1656 // Construct new function based on inputs/outputs & add allocas for all defs.
1657 Function *newFunction =
1658 constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1659 oldFunction, oldFunction->getParent());
1661 // Update the entry count of the function.
1663 auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1664 if (Count.hasValue())
1665 newFunction->setEntryCount(
1666 ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1667 BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1671 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1673 moveCodeToFunction(newFunction);
1675 // Replicate the effects of any lifetime start/end markers which referenced
1676 // input objects in the extraction region by placing markers around the call.
1677 insertLifetimeMarkersSurroundingCall(
1678 oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1680 // Propagate personality info to the new function if there is one.
1681 if (oldFunction->hasPersonalityFn())
1682 newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1684 // Update the branch weights for the exit block.
1685 if (BFI && NumExitBlocks > 1)
1686 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1688 // Loop over all of the PHI nodes in the header and exit blocks, and change
1689 // any references to the old incoming edge to be the new incoming edge.
1690 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1691 PHINode *PN = cast<PHINode>(I);
1692 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1693 if (!Blocks.count(PN->getIncomingBlock(i)))
1694 PN->setIncomingBlock(i, newFuncRoot);
1697 for (BasicBlock *ExitBB : ExitBlocks)
1698 for (PHINode &PN : ExitBB->phis()) {
1699 Value *IncomingCodeReplacerVal = nullptr;
1700 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1701 // Ignore incoming values from outside of the extracted region.
1702 if (!Blocks.count(PN.getIncomingBlock(i)))
1705 // Ensure that there is only one incoming value from codeReplacer.
1706 if (!IncomingCodeReplacerVal) {
1707 PN.setIncomingBlock(i, codeReplacer);
1708 IncomingCodeReplacerVal = PN.getIncomingValue(i);
1710 assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1711 "PHI has two incompatbile incoming values from codeRepl");
1715 fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1717 // Mark the new function `noreturn` if applicable. Terminators which resume
1718 // exception propagation are treated as returning instructions. This is to
1719 // avoid inserting traps after calls to outlined functions which unwind.
1720 bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1721 const Instruction *Term = BB.getTerminator();
1722 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1725 newFunction->setDoesNotReturn();
1727 LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1728 newFunction->dump();
1729 report_fatal_error("verification of newFunction failed!");
1731 LLVM_DEBUG(if (verifyFunction(*oldFunction))
1732 report_fatal_error("verification of oldFunction failed!"));
1733 LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1734 report_fatal_error("Stale Asumption cache for old Function!"));
1738 bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc,
1739 const Function &NewFunc,
1740 AssumptionCache *AC) {
1741 for (auto AssumeVH : AC->assumptions()) {
1742 CallInst *I = dyn_cast_or_null<CallInst>(AssumeVH);
1746 // There shouldn't be any llvm.assume intrinsics in the new function.
1747 if (I->getFunction() != &OldFunc)
1750 // There shouldn't be any stale affected values in the assumption cache
1751 // that were previously in the old function, but that have now been moved
1752 // to the new function.
1753 for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1754 CallInst *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1757 if (AffectedCI->getFunction() != &OldFunc)
1759 auto *AssumedInst = dyn_cast<Instruction>(AffectedCI->getOperand(0));
1760 if (AssumedInst->getFunction() != &OldFunc)