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