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