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