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