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