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