LLVM 17.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", &NewBB->front());
725 PN->replaceAllUsesWith(NewPN);
726 NewPN->addIncoming(PN, OldPred);
727
728 // Loop over all of the incoming value in PN, moving them to NewPN if they
729 // are from the extracted region.
730 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
731 if (Blocks.count(PN->getIncomingBlock(i))) {
732 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
733 PN->removeIncomingValue(i);
734 --i;
735 }
736 }
737 }
738 }
739}
740
741/// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
742/// outlined region, we split these PHIs on two: one with inputs from region
743/// and other with remaining incoming blocks; then first PHIs are placed in
744/// outlined region.
745void CodeExtractor::severSplitPHINodesOfExits(
746 const SmallPtrSetImpl<BasicBlock *> &Exits) {
747 for (BasicBlock *ExitBB : Exits) {
748 BasicBlock *NewBB = nullptr;
749
750 for (PHINode &PN : ExitBB->phis()) {
751 // Find all incoming values from the outlining region.
752 SmallVector<unsigned, 2> IncomingVals;
753 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
754 if (Blocks.count(PN.getIncomingBlock(i)))
755 IncomingVals.push_back(i);
756
757 // Do not process PHI if there is one (or fewer) predecessor from region.
758 // If PHI has exactly one predecessor from region, only this one incoming
759 // will be replaced on codeRepl block, so it should be safe to skip PHI.
760 if (IncomingVals.size() <= 1)
761 continue;
762
763 // Create block for new PHIs and add it to the list of outlined if it
764 // wasn't done before.
765 if (!NewBB) {
766 NewBB = BasicBlock::Create(ExitBB->getContext(),
767 ExitBB->getName() + ".split",
768 ExitBB->getParent(), ExitBB);
770 for (BasicBlock *PredBB : Preds)
771 if (Blocks.count(PredBB))
772 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
773 BranchInst::Create(ExitBB, NewBB);
774 Blocks.insert(NewBB);
775 }
776
777 // Split this PHI.
778 PHINode *NewPN =
779 PHINode::Create(PN.getType(), IncomingVals.size(),
780 PN.getName() + ".ce", NewBB->getFirstNonPHI());
781 for (unsigned i : IncomingVals)
782 NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));
783 for (unsigned i : reverse(IncomingVals))
784 PN.removeIncomingValue(i, false);
785 PN.addIncoming(NewPN, NewBB);
786 }
787 }
788}
789
790void CodeExtractor::splitReturnBlocks() {
791 for (BasicBlock *Block : Blocks)
792 if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
793 BasicBlock *New =
794 Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
795 if (DT) {
796 // Old dominates New. New node dominates all other nodes dominated
797 // by Old.
798 DomTreeNode *OldNode = DT->getNode(Block);
800 OldNode->end());
801
802 DomTreeNode *NewNode = DT->addNewBlock(New, Block);
803
804 for (DomTreeNode *I : Children)
805 DT->changeImmediateDominator(I, NewNode);
806 }
807 }
808}
809
810/// constructFunction - make a function based on inputs and outputs, as follows:
811/// f(in0, ..., inN, out0, ..., outN)
812Function *CodeExtractor::constructFunction(const ValueSet &inputs,
813 const ValueSet &outputs,
814 BasicBlock *header,
815 BasicBlock *newRootNode,
816 BasicBlock *newHeader,
817 Function *oldFunction,
818 Module *M) {
819 LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
820 LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
821
822 // This function returns unsigned, outputs will go back by reference.
823 switch (NumExitBlocks) {
824 case 0:
825 case 1: RetTy = Type::getVoidTy(header->getContext()); break;
826 case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
827 default: RetTy = Type::getInt16Ty(header->getContext()); break;
828 }
829
830 std::vector<Type *> ParamTy;
831 std::vector<Type *> AggParamTy;
832 ValueSet StructValues;
833 const DataLayout &DL = M->getDataLayout();
834
835 // Add the types of the input values to the function's argument list
836 for (Value *value : inputs) {
837 LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
838 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(value)) {
839 AggParamTy.push_back(value->getType());
840 StructValues.insert(value);
841 } else
842 ParamTy.push_back(value->getType());
843 }
844
845 // Add the types of the output values to the function's argument list.
846 for (Value *output : outputs) {
847 LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
848 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {
849 AggParamTy.push_back(output->getType());
850 StructValues.insert(output);
851 } else
852 ParamTy.push_back(
853 PointerType::get(output->getType(), DL.getAllocaAddrSpace()));
854 }
855
856 assert(
857 (ParamTy.size() + AggParamTy.size()) ==
858 (inputs.size() + outputs.size()) &&
859 "Number of scalar and aggregate params does not match inputs, outputs");
860 assert((StructValues.empty() || AggregateArgs) &&
861 "Expeced StructValues only with AggregateArgs set");
862
863 // Concatenate scalar and aggregate params in ParamTy.
864 size_t NumScalarParams = ParamTy.size();
865 StructType *StructTy = nullptr;
866 if (AggregateArgs && !AggParamTy.empty()) {
867 StructTy = StructType::get(M->getContext(), AggParamTy);
868 ParamTy.push_back(PointerType::get(StructTy, DL.getAllocaAddrSpace()));
869 }
870
871 LLVM_DEBUG({
872 dbgs() << "Function type: " << *RetTy << " f(";
873 for (Type *i : ParamTy)
874 dbgs() << *i << ", ";
875 dbgs() << ")\n";
876 });
877
879 RetTy, ParamTy, AllowVarArgs && oldFunction->isVarArg());
880
881 std::string SuffixToUse =
882 Suffix.empty()
883 ? (header->getName().empty() ? "extracted" : header->getName().str())
884 : Suffix;
885 // Create the new function
886 Function *newFunction = Function::Create(
887 funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
888 oldFunction->getName() + "." + SuffixToUse, M);
889
890 // Inherit all of the target dependent attributes and white-listed
891 // target independent attributes.
892 // (e.g. If the extracted region contains a call to an x86.sse
893 // instruction we need to make sure that the extracted region has the
894 // "target-features" attribute allowing it to be lowered.
895 // FIXME: This should be changed to check to see if a specific
896 // attribute can not be inherited.
897 for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) {
898 if (Attr.isStringAttribute()) {
899 if (Attr.getKindAsString() == "thunk")
900 continue;
901 } else
902 switch (Attr.getKindAsEnum()) {
903 // Those attributes cannot be propagated safely. Explicitly list them
904 // here so we get a warning if new attributes are added.
905 case Attribute::AllocSize:
906 case Attribute::Builtin:
907 case Attribute::Convergent:
908 case Attribute::JumpTable:
909 case Attribute::Naked:
910 case Attribute::NoBuiltin:
911 case Attribute::NoMerge:
912 case Attribute::NoReturn:
913 case Attribute::NoSync:
914 case Attribute::ReturnsTwice:
915 case Attribute::Speculatable:
916 case Attribute::StackAlignment:
917 case Attribute::WillReturn:
918 case Attribute::AllocKind:
919 case Attribute::PresplitCoroutine:
920 case Attribute::Memory:
921 case Attribute::NoFPClass:
922 continue;
923 // Those attributes should be safe to propagate to the extracted function.
924 case Attribute::AlwaysInline:
925 case Attribute::Cold:
926 case Attribute::DisableSanitizerInstrumentation:
927 case Attribute::FnRetThunkExtern:
928 case Attribute::Hot:
929 case Attribute::NoRecurse:
930 case Attribute::InlineHint:
931 case Attribute::MinSize:
932 case Attribute::NoCallback:
933 case Attribute::NoDuplicate:
934 case Attribute::NoFree:
935 case Attribute::NoImplicitFloat:
936 case Attribute::NoInline:
937 case Attribute::NonLazyBind:
938 case Attribute::NoRedZone:
939 case Attribute::NoUnwind:
940 case Attribute::NoSanitizeBounds:
941 case Attribute::NoSanitizeCoverage:
942 case Attribute::NullPointerIsValid:
943 case Attribute::OptForFuzzing:
944 case Attribute::OptimizeNone:
945 case Attribute::OptimizeForSize:
946 case Attribute::SafeStack:
947 case Attribute::ShadowCallStack:
948 case Attribute::SanitizeAddress:
949 case Attribute::SanitizeMemory:
950 case Attribute::SanitizeThread:
951 case Attribute::SanitizeHWAddress:
952 case Attribute::SanitizeMemTag:
953 case Attribute::SpeculativeLoadHardening:
954 case Attribute::StackProtect:
955 case Attribute::StackProtectReq:
956 case Attribute::StackProtectStrong:
957 case Attribute::StrictFP:
958 case Attribute::UWTable:
959 case Attribute::VScaleRange:
960 case Attribute::NoCfCheck:
961 case Attribute::MustProgress:
962 case Attribute::NoProfile:
963 case Attribute::SkipProfile:
964 break;
965 // These attributes cannot be applied to functions.
966 case Attribute::Alignment:
967 case Attribute::AllocatedPointer:
968 case Attribute::AllocAlign:
969 case Attribute::ByVal:
970 case Attribute::Dereferenceable:
971 case Attribute::DereferenceableOrNull:
972 case Attribute::ElementType:
973 case Attribute::InAlloca:
974 case Attribute::InReg:
975 case Attribute::Nest:
976 case Attribute::NoAlias:
977 case Attribute::NoCapture:
978 case Attribute::NoUndef:
979 case Attribute::NonNull:
980 case Attribute::Preallocated:
981 case Attribute::ReadNone:
982 case Attribute::ReadOnly:
983 case Attribute::Returned:
984 case Attribute::SExt:
985 case Attribute::StructRet:
986 case Attribute::SwiftError:
987 case Attribute::SwiftSelf:
988 case Attribute::SwiftAsync:
989 case Attribute::ZExt:
990 case Attribute::ImmArg:
991 case Attribute::ByRef:
992 case Attribute::WriteOnly:
993 // These are not really attributes.
994 case Attribute::None:
998 llvm_unreachable("Not a function attribute");
999 }
1000
1001 newFunction->addFnAttr(Attr);
1002 }
1003 newFunction->insert(newFunction->end(), newRootNode);
1004
1005 // Create scalar and aggregate iterators to name all of the arguments we
1006 // inserted.
1007 Function::arg_iterator ScalarAI = newFunction->arg_begin();
1008 Function::arg_iterator AggAI = std::next(ScalarAI, NumScalarParams);
1009
1010 // Rewrite all users of the inputs in the extracted region to use the
1011 // arguments (or appropriate addressing into struct) instead.
1012 for (unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) {
1013 Value *RewriteVal;
1014 if (AggregateArgs && StructValues.contains(inputs[i])) {
1015 Value *Idx[2];
1017 Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), aggIdx);
1018 Instruction *TI = newFunction->begin()->getTerminator();
1020 StructTy, &*AggAI, Idx, "gep_" + inputs[i]->getName(), TI);
1021 RewriteVal = new LoadInst(StructTy->getElementType(aggIdx), GEP,
1022 "loadgep_" + inputs[i]->getName(), TI);
1023 ++aggIdx;
1024 } else
1025 RewriteVal = &*ScalarAI++;
1026
1027 std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
1028 for (User *use : Users)
1029 if (Instruction *inst = dyn_cast<Instruction>(use))
1030 if (Blocks.count(inst->getParent()))
1031 inst->replaceUsesOfWith(inputs[i], RewriteVal);
1032 }
1033
1034 // Set names for input and output arguments.
1035 if (NumScalarParams) {
1036 ScalarAI = newFunction->arg_begin();
1037 for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++ScalarAI)
1038 if (!StructValues.contains(inputs[i]))
1039 ScalarAI->setName(inputs[i]->getName());
1040 for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++ScalarAI)
1041 if (!StructValues.contains(outputs[i]))
1042 ScalarAI->setName(outputs[i]->getName() + ".out");
1043 }
1044
1045 // Rewrite branches to basic blocks outside of the loop to new dummy blocks
1046 // within the new function. This must be done before we lose track of which
1047 // blocks were originally in the code region.
1048 std::vector<User *> Users(header->user_begin(), header->user_end());
1049 for (auto &U : Users)
1050 // The BasicBlock which contains the branch is not in the region
1051 // modify the branch target to a new block
1052 if (Instruction *I = dyn_cast<Instruction>(U))
1053 if (I->isTerminator() && I->getFunction() == oldFunction &&
1054 !Blocks.count(I->getParent()))
1055 I->replaceUsesOfWith(header, newHeader);
1056
1057 return newFunction;
1058}
1059
1060/// Erase lifetime.start markers which reference inputs to the extraction
1061/// region, and insert the referenced memory into \p LifetimesStart.
1062///
1063/// The extraction region is defined by a set of blocks (\p Blocks), and a set
1064/// of allocas which will be moved from the caller function into the extracted
1065/// function (\p SunkAllocas).
1067 const SetVector<Value *> &SunkAllocas,
1068 SetVector<Value *> &LifetimesStart) {
1069 for (BasicBlock *BB : Blocks) {
1071 auto *II = dyn_cast<IntrinsicInst>(&I);
1072 if (!II || !II->isLifetimeStartOrEnd())
1073 continue;
1074
1075 // Get the memory operand of the lifetime marker. If the underlying
1076 // object is a sunk alloca, or is otherwise defined in the extraction
1077 // region, the lifetime marker must not be erased.
1078 Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1079 if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1080 continue;
1081
1082 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1083 LifetimesStart.insert(Mem);
1084 II->eraseFromParent();
1085 }
1086 }
1087}
1088
1089/// Insert lifetime start/end markers surrounding the call to the new function
1090/// for objects defined in the caller.
1092 Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1093 CallInst *TheCall) {
1094 LLVMContext &Ctx = M->getContext();
1095 auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1096 Instruction *Term = TheCall->getParent()->getTerminator();
1097
1098 // Emit lifetime markers for the pointers given in \p Objects. Insert the
1099 // markers before the call if \p InsertBefore, and after the call otherwise.
1100 auto insertMarkers = [&](Intrinsic::ID MarkerFunc, ArrayRef<Value *> Objects,
1101 bool InsertBefore) {
1102 for (Value *Mem : Objects) {
1103 assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1104 TheCall->getFunction()) &&
1105 "Input memory not defined in original function");
1106
1107 Function *Func = Intrinsic::getDeclaration(M, MarkerFunc, Mem->getType());
1108 auto Marker = CallInst::Create(Func, {NegativeOne, Mem});
1109 if (InsertBefore)
1110 Marker->insertBefore(TheCall);
1111 else
1112 Marker->insertBefore(Term);
1113 }
1114 };
1115
1116 if (!LifetimesStart.empty()) {
1117 insertMarkers(Intrinsic::lifetime_start, LifetimesStart,
1118 /*InsertBefore=*/true);
1119 }
1120
1121 if (!LifetimesEnd.empty()) {
1122 insertMarkers(Intrinsic::lifetime_end, LifetimesEnd,
1123 /*InsertBefore=*/false);
1124 }
1125}
1126
1127/// emitCallAndSwitchStatement - This method sets up the caller side by adding
1128/// the call instruction, splitting any PHI nodes in the header block as
1129/// necessary.
1130CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1131 BasicBlock *codeReplacer,
1132 ValueSet &inputs,
1133 ValueSet &outputs) {
1134 // Emit a call to the new function, passing in: *pointer to struct (if
1135 // aggregating parameters), or plan inputs and allocated memory for outputs
1136 std::vector<Value *> params, ReloadOutputs, Reloads;
1137 ValueSet StructValues;
1138
1139 Module *M = newFunction->getParent();
1140 LLVMContext &Context = M->getContext();
1141 const DataLayout &DL = M->getDataLayout();
1142 CallInst *call = nullptr;
1143
1144 // Add inputs as params, or to be filled into the struct
1145 unsigned ScalarInputArgNo = 0;
1146 SmallVector<unsigned, 1> SwiftErrorArgs;
1147 for (Value *input : inputs) {
1148 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(input))
1149 StructValues.insert(input);
1150 else {
1151 params.push_back(input);
1152 if (input->isSwiftError())
1153 SwiftErrorArgs.push_back(ScalarInputArgNo);
1154 }
1155 ++ScalarInputArgNo;
1156 }
1157
1158 // Create allocas for the outputs
1159 unsigned ScalarOutputArgNo = 0;
1160 for (Value *output : outputs) {
1161 if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {
1162 StructValues.insert(output);
1163 } else {
1164 AllocaInst *alloca =
1165 new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1166 nullptr, output->getName() + ".loc",
1167 &codeReplacer->getParent()->front().front());
1168 ReloadOutputs.push_back(alloca);
1169 params.push_back(alloca);
1170 ++ScalarOutputArgNo;
1171 }
1172 }
1173
1174 StructType *StructArgTy = nullptr;
1175 AllocaInst *Struct = nullptr;
1176 unsigned NumAggregatedInputs = 0;
1177 if (AggregateArgs && !StructValues.empty()) {
1178 std::vector<Type *> ArgTypes;
1179 for (Value *V : StructValues)
1180 ArgTypes.push_back(V->getType());
1181
1182 // Allocate a struct at the beginning of this function
1183 StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1184 Struct = new AllocaInst(
1185 StructArgTy, DL.getAllocaAddrSpace(), nullptr, "structArg",
1186 AllocationBlock ? &*AllocationBlock->getFirstInsertionPt()
1187 : &codeReplacer->getParent()->front().front());
1188 params.push_back(Struct);
1189
1190 // Store aggregated inputs in the struct.
1191 for (unsigned i = 0, e = StructValues.size(); i != e; ++i) {
1192 if (inputs.contains(StructValues[i])) {
1193 Value *Idx[2];
1195 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
1197 StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1198 GEP->insertInto(codeReplacer, codeReplacer->end());
1199 new StoreInst(StructValues[i], GEP, codeReplacer);
1200 NumAggregatedInputs++;
1201 }
1202 }
1203 }
1204
1205 // Emit the call to the function
1206 call = CallInst::Create(newFunction, params,
1207 NumExitBlocks > 1 ? "targetBlock" : "");
1208 // Add debug location to the new call, if the original function has debug
1209 // info. In that case, the terminator of the entry block of the extracted
1210 // function contains the first debug location of the extracted function,
1211 // set in extractCodeRegion.
1212 if (codeReplacer->getParent()->getSubprogram()) {
1213 if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1214 call->setDebugLoc(DL);
1215 }
1216 call->insertInto(codeReplacer, codeReplacer->end());
1217
1218 // Set swifterror parameter attributes.
1219 for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1220 call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1221 newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1222 }
1223
1224 // Reload the outputs passed in by reference, use the struct if output is in
1225 // the aggregate or reload from the scalar argument.
1226 for (unsigned i = 0, e = outputs.size(), scalarIdx = 0,
1227 aggIdx = NumAggregatedInputs;
1228 i != e; ++i) {
1229 Value *Output = nullptr;
1230 if (AggregateArgs && StructValues.contains(outputs[i])) {
1231 Value *Idx[2];
1233 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx);
1235 StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1236 GEP->insertInto(codeReplacer, codeReplacer->end());
1237 Output = GEP;
1238 ++aggIdx;
1239 } else {
1240 Output = ReloadOutputs[scalarIdx];
1241 ++scalarIdx;
1242 }
1243 LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1244 outputs[i]->getName() + ".reload",
1245 codeReplacer);
1246 Reloads.push_back(load);
1247 std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1248 for (User *U : Users) {
1249 Instruction *inst = cast<Instruction>(U);
1250 if (!Blocks.count(inst->getParent()))
1251 inst->replaceUsesOfWith(outputs[i], load);
1252 }
1253 }
1254
1255 // Now we can emit a switch statement using the call as a value.
1256 SwitchInst *TheSwitch =
1258 codeReplacer, 0, codeReplacer);
1259
1260 // Since there may be multiple exits from the original region, make the new
1261 // function return an unsigned, switch on that number. This loop iterates
1262 // over all of the blocks in the extracted region, updating any terminator
1263 // instructions in the to-be-extracted region that branch to blocks that are
1264 // not in the region to be extracted.
1265 std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1266
1267 // Iterate over the previously collected targets, and create new blocks inside
1268 // the function to branch to.
1269 unsigned switchVal = 0;
1270 for (BasicBlock *OldTarget : OldTargets) {
1271 if (Blocks.count(OldTarget))
1272 continue;
1273 BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1274 if (NewTarget)
1275 continue;
1276
1277 // If we don't already have an exit stub for this non-extracted
1278 // destination, create one now!
1279 NewTarget = BasicBlock::Create(Context,
1280 OldTarget->getName() + ".exitStub",
1281 newFunction);
1282 unsigned SuccNum = switchVal++;
1283
1284 Value *brVal = nullptr;
1285 assert(NumExitBlocks < 0xffff && "too many exit blocks for switch");
1286 switch (NumExitBlocks) {
1287 case 0:
1288 case 1: break; // No value needed.
1289 case 2: // Conditional branch, return a bool
1290 brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1291 break;
1292 default:
1293 brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1294 break;
1295 }
1296
1297 ReturnInst::Create(Context, brVal, NewTarget);
1298
1299 // Update the switch instruction.
1300 TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
1301 SuccNum),
1302 OldTarget);
1303 }
1304
1305 for (BasicBlock *Block : Blocks) {
1306 Instruction *TI = Block->getTerminator();
1307 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1308 if (Blocks.count(TI->getSuccessor(i)))
1309 continue;
1310 BasicBlock *OldTarget = TI->getSuccessor(i);
1311 // add a new basic block which returns the appropriate value
1312 BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1313 assert(NewTarget && "Unknown target block!");
1314
1315 // rewrite the original branch instruction with this new target
1316 TI->setSuccessor(i, NewTarget);
1317 }
1318 }
1319
1320 // Store the arguments right after the definition of output value.
1321 // This should be proceeded after creating exit stubs to be ensure that invoke
1322 // result restore will be placed in the outlined function.
1323 Function::arg_iterator ScalarOutputArgBegin = newFunction->arg_begin();
1324 std::advance(ScalarOutputArgBegin, ScalarInputArgNo);
1325 Function::arg_iterator AggOutputArgBegin = newFunction->arg_begin();
1326 std::advance(AggOutputArgBegin, ScalarInputArgNo + ScalarOutputArgNo);
1327
1328 for (unsigned i = 0, e = outputs.size(), aggIdx = NumAggregatedInputs; i != e;
1329 ++i) {
1330 auto *OutI = dyn_cast<Instruction>(outputs[i]);
1331 if (!OutI)
1332 continue;
1333
1334 // Find proper insertion point.
1335 BasicBlock::iterator InsertPt;
1336 // In case OutI is an invoke, we insert the store at the beginning in the
1337 // 'normal destination' BB. Otherwise we insert the store right after OutI.
1338 if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1339 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1340 else if (auto *Phi = dyn_cast<PHINode>(OutI))
1341 InsertPt = Phi->getParent()->getFirstInsertionPt();
1342 else
1343 InsertPt = std::next(OutI->getIterator());
1344
1345 Instruction *InsertBefore = &*InsertPt;
1346 assert((InsertBefore->getFunction() == newFunction ||
1347 Blocks.count(InsertBefore->getParent())) &&
1348 "InsertPt should be in new function");
1349 if (AggregateArgs && StructValues.contains(outputs[i])) {
1350 assert(AggOutputArgBegin != newFunction->arg_end() &&
1351 "Number of aggregate output arguments should match "
1352 "the number of defined values");
1353 Value *Idx[2];
1355 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx);
1357 StructArgTy, &*AggOutputArgBegin, Idx, "gep_" + outputs[i]->getName(),
1358 InsertBefore);
1359 new StoreInst(outputs[i], GEP, InsertBefore);
1360 ++aggIdx;
1361 // Since there should be only one struct argument aggregating
1362 // all the output values, we shouldn't increment AggOutputArgBegin, which
1363 // always points to the struct argument, in this case.
1364 } else {
1365 assert(ScalarOutputArgBegin != newFunction->arg_end() &&
1366 "Number of scalar output arguments should match "
1367 "the number of defined values");
1368 new StoreInst(outputs[i], &*ScalarOutputArgBegin, InsertBefore);
1369 ++ScalarOutputArgBegin;
1370 }
1371 }
1372
1373 // Now that we've done the deed, simplify the switch instruction.
1374 Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1375 switch (NumExitBlocks) {
1376 case 0:
1377 // There are no successors (the block containing the switch itself), which
1378 // means that previously this was the last part of the function, and hence
1379 // this should be rewritten as a `ret'
1380
1381 // Check if the function should return a value
1382 if (OldFnRetTy->isVoidTy()) {
1383 ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
1384 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1385 // return what we have
1386 ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1387 } else {
1388 // Otherwise we must have code extracted an unwind or something, just
1389 // return whatever we want.
1390 ReturnInst::Create(Context,
1391 Constant::getNullValue(OldFnRetTy), TheSwitch);
1392 }
1393
1394 TheSwitch->eraseFromParent();
1395 break;
1396 case 1:
1397 // Only a single destination, change the switch into an unconditional
1398 // branch.
1399 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1400 TheSwitch->eraseFromParent();
1401 break;
1402 case 2:
1403 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1404 call, TheSwitch);
1405 TheSwitch->eraseFromParent();
1406 break;
1407 default:
1408 // Otherwise, make the default destination of the switch instruction be one
1409 // of the other successors.
1410 TheSwitch->setCondition(call);
1411 TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1412 // Remove redundant case
1413 TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1414 break;
1415 }
1416
1417 // Insert lifetime markers around the reloads of any output values. The
1418 // allocas output values are stored in are only in-use in the codeRepl block.
1419 insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1420
1421 return call;
1422}
1423
1424void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1425 auto newFuncIt = newFunction->front().getIterator();
1426 for (BasicBlock *Block : Blocks) {
1427 // Delete the basic block from the old function, and the list of blocks
1428 Block->removeFromParent();
1429
1430 // Insert this basic block into the new function
1431 // Insert the original blocks after the entry block created
1432 // for the new function. The entry block may be followed
1433 // by a set of exit blocks at this point, but these exit
1434 // blocks better be placed at the end of the new function.
1435 newFuncIt = newFunction->insert(std::next(newFuncIt), Block);
1436 }
1437}
1438
1439void CodeExtractor::calculateNewCallTerminatorWeights(
1440 BasicBlock *CodeReplacer,
1442 BranchProbabilityInfo *BPI) {
1443 using Distribution = BlockFrequencyInfoImplBase::Distribution;
1444 using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1445
1446 // Update the branch weights for the exit block.
1447 Instruction *TI = CodeReplacer->getTerminator();
1448 SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1449
1450 // Block Frequency distribution with dummy node.
1451 Distribution BranchDist;
1452
1453 SmallVector<BranchProbability, 4> EdgeProbabilities(
1455
1456 // Add each of the frequencies of the successors.
1457 for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1458 BlockNode ExitNode(i);
1459 uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1460 if (ExitFreq != 0)
1461 BranchDist.addExit(ExitNode, ExitFreq);
1462 else
1463 EdgeProbabilities[i] = BranchProbability::getZero();
1464 }
1465
1466 // Check for no total weight.
1467 if (BranchDist.Total == 0) {
1468 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1469 return;
1470 }
1471
1472 // Normalize the distribution so that they can fit in unsigned.
1473 BranchDist.normalize();
1474
1475 // Create normalized branch weights and set the metadata.
1476 for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1477 const auto &Weight = BranchDist.Weights[I];
1478
1479 // Get the weight and update the current BFI.
1480 BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1481 BranchProbability BP(Weight.Amount, BranchDist.Total);
1482 EdgeProbabilities[Weight.TargetNode.Index] = BP;
1483 }
1484 BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1485 TI->setMetadata(
1486 LLVMContext::MD_prof,
1487 MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1488}
1489
1490/// Erase debug info intrinsics which refer to values in \p F but aren't in
1491/// \p F.
1493 for (Instruction &I : instructions(F)) {
1495 findDbgUsers(DbgUsers, &I);
1496 for (DbgVariableIntrinsic *DVI : DbgUsers)
1497 if (DVI->getFunction() != &F)
1498 DVI->eraseFromParent();
1499 }
1500}
1501
1502/// Fix up the debug info in the old and new functions by pointing line
1503/// locations and debug intrinsics to the new subprogram scope, and by deleting
1504/// intrinsics which point to values outside of the new function.
1505static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1506 CallInst &TheCall) {
1507 DISubprogram *OldSP = OldFunc.getSubprogram();
1508 LLVMContext &Ctx = OldFunc.getContext();
1509
1510 if (!OldSP) {
1511 // Erase any debug info the new function contains.
1512 stripDebugInfo(NewFunc);
1513 // Make sure the old function doesn't contain any non-local metadata refs.
1515 return;
1516 }
1517
1518 // Create a subprogram for the new function. Leave out a description of the
1519 // function arguments, as the parameters don't correspond to anything at the
1520 // source level.
1521 assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1522 DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,
1523 OldSP->getUnit());
1524 auto SPType =
1525 DIB.createSubroutineType(DIB.getOrCreateTypeArray(std::nullopt));
1526 DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1527 DISubprogram::SPFlagOptimized |
1528 DISubprogram::SPFlagLocalToUnit;
1529 auto NewSP = DIB.createFunction(
1530 OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1531 /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1532 NewFunc.setSubprogram(NewSP);
1533
1534 // Debug intrinsics in the new function need to be updated in one of two
1535 // ways:
1536 // 1) They need to be deleted, because they describe a value in the old
1537 // function.
1538 // 2) They need to point to fresh metadata, e.g. because they currently
1539 // point to a variable in the wrong scope.
1540 SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1541 SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1543 for (Instruction &I : instructions(NewFunc)) {
1544 auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1545 if (!DII)
1546 continue;
1547
1548 // Point the intrinsic to a fresh label within the new function if the
1549 // intrinsic was not inlined from some other function.
1550 if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1551 if (DLI->getDebugLoc().getInlinedAt())
1552 continue;
1553 DILabel *OldLabel = DLI->getLabel();
1554 DINode *&NewLabel = RemappedMetadata[OldLabel];
1555 if (!NewLabel) {
1557 *OldLabel->getScope(), *NewSP, Ctx, Cache);
1558 NewLabel = DILabel::get(Ctx, NewScope, OldLabel->getName(),
1559 OldLabel->getFile(), OldLabel->getLine());
1560 }
1561 DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
1562 continue;
1563 }
1564
1565 auto IsInvalidLocation = [&NewFunc](Value *Location) {
1566 // Location is invalid if it isn't a constant or an instruction, or is an
1567 // instruction but isn't in the new function.
1568 if (!Location ||
1569 (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1570 return true;
1571 Instruction *LocationInst = dyn_cast<Instruction>(Location);
1572 return LocationInst && LocationInst->getFunction() != &NewFunc;
1573 };
1574
1575 auto *DVI = cast<DbgVariableIntrinsic>(DII);
1576 // If any of the used locations are invalid, delete the intrinsic.
1577 if (any_of(DVI->location_ops(), IsInvalidLocation)) {
1578 DebugIntrinsicsToDelete.push_back(DVI);
1579 continue;
1580 }
1581 // If the variable was in the scope of the old function, i.e. it was not
1582 // inlined, point the intrinsic to a fresh variable within the new function.
1583 if (!DVI->getDebugLoc().getInlinedAt()) {
1584 DILocalVariable *OldVar = DVI->getVariable();
1585 DINode *&NewVar = RemappedMetadata[OldVar];
1586 if (!NewVar) {
1588 *OldVar->getScope(), *NewSP, Ctx, Cache);
1589 NewVar = DIB.createAutoVariable(
1590 NewScope, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1591 OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1592 OldVar->getAlignInBits());
1593 }
1594 DVI->setVariable(cast<DILocalVariable>(NewVar));
1595 }
1596 }
1597
1598 for (auto *DII : DebugIntrinsicsToDelete)
1599 DII->eraseFromParent();
1600 DIB.finalizeSubprogram(NewSP);
1601
1602 // Fix up the scope information attached to the line locations in the new
1603 // function.
1604 for (Instruction &I : instructions(NewFunc)) {
1605 if (const DebugLoc &DL = I.getDebugLoc())
1606 I.setDebugLoc(
1607 DebugLoc::replaceInlinedAtSubprogram(DL, *NewSP, Ctx, Cache));
1608
1609 // Loop info metadata may contain line locations. Fix them up.
1610 auto updateLoopInfoLoc = [&Ctx, &Cache, NewSP](Metadata *MD) -> Metadata * {
1611 if (auto *Loc = dyn_cast_or_null<DILocation>(MD))
1612 return DebugLoc::replaceInlinedAtSubprogram(Loc, *NewSP, Ctx, Cache);
1613 return MD;
1614 };
1615 updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1616 }
1617 if (!TheCall.getDebugLoc())
1618 TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP));
1619
1621}
1622
1623Function *
1625 ValueSet Inputs, Outputs;
1626 return extractCodeRegion(CEAC, Inputs, Outputs);
1627}
1628
1629Function *
1631 ValueSet &inputs, ValueSet &outputs) {
1632 if (!isEligible())
1633 return nullptr;
1634
1635 // Assumption: this is a single-entry code region, and the header is the first
1636 // block in the region.
1637 BasicBlock *header = *Blocks.begin();
1638 Function *oldFunction = header->getParent();
1639
1640 // Calculate the entry frequency of the new function before we change the root
1641 // block.
1642 BlockFrequency EntryFreq;
1643 if (BFI) {
1644 assert(BPI && "Both BPI and BFI are required to preserve profile info");
1645 for (BasicBlock *Pred : predecessors(header)) {
1646 if (Blocks.count(Pred))
1647 continue;
1648 EntryFreq +=
1649 BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1650 }
1651 }
1652
1653 // Remove @llvm.assume calls that will be moved to the new function from the
1654 // old function's assumption cache.
1655 for (BasicBlock *Block : Blocks) {
1657 if (auto *AI = dyn_cast<AssumeInst>(&I)) {
1658 if (AC)
1659 AC->unregisterAssumption(AI);
1660 AI->eraseFromParent();
1661 }
1662 }
1663 }
1664
1665 // If we have any return instructions in the region, split those blocks so
1666 // that the return is not in the region.
1667 splitReturnBlocks();
1668
1669 // Calculate the exit blocks for the extracted region and the total exit
1670 // weights for each of those blocks.
1673 for (BasicBlock *Block : Blocks) {
1674 for (BasicBlock *Succ : successors(Block)) {
1675 if (!Blocks.count(Succ)) {
1676 // Update the branch weight for this successor.
1677 if (BFI) {
1678 BlockFrequency &BF = ExitWeights[Succ];
1679 BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ);
1680 }
1681 ExitBlocks.insert(Succ);
1682 }
1683 }
1684 }
1685 NumExitBlocks = ExitBlocks.size();
1686
1687 for (BasicBlock *Block : Blocks) {
1688 Instruction *TI = Block->getTerminator();
1689 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1690 if (Blocks.count(TI->getSuccessor(i)))
1691 continue;
1692 BasicBlock *OldTarget = TI->getSuccessor(i);
1693 OldTargets.push_back(OldTarget);
1694 }
1695 }
1696
1697 // If we have to split PHI nodes of the entry or exit blocks, do so now.
1698 severSplitPHINodesOfEntry(header);
1699 severSplitPHINodesOfExits(ExitBlocks);
1700
1701 // This takes place of the original loop
1702 BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1703 "codeRepl", oldFunction,
1704 header);
1705
1706 // The new function needs a root node because other nodes can branch to the
1707 // head of the region, but the entry node of a function cannot have preds.
1708 BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1709 "newFuncRoot");
1710 auto *BranchI = BranchInst::Create(header);
1711 // If the original function has debug info, we have to add a debug location
1712 // to the new branch instruction from the artificial entry block.
1713 // We use the debug location of the first instruction in the extracted
1714 // blocks, as there is no other equivalent line in the source code.
1715 if (oldFunction->getSubprogram()) {
1716 any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1717 return any_of(*BB, [&BranchI](const Instruction &I) {
1718 if (!I.getDebugLoc())
1719 return false;
1720 BranchI->setDebugLoc(I.getDebugLoc());
1721 return true;
1722 });
1723 });
1724 }
1725 BranchI->insertInto(newFuncRoot, newFuncRoot->end());
1726
1727 ValueSet SinkingCands, HoistingCands;
1728 BasicBlock *CommonExit = nullptr;
1729 findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1730 assert(HoistingCands.empty() || CommonExit);
1731
1732 // Find inputs to, outputs from the code region.
1733 findInputsOutputs(inputs, outputs, SinkingCands);
1734
1735 // Now sink all instructions which only have non-phi uses inside the region.
1736 // Group the allocas at the start of the block, so that any bitcast uses of
1737 // the allocas are well-defined.
1738 AllocaInst *FirstSunkAlloca = nullptr;
1739 for (auto *II : SinkingCands) {
1740 if (auto *AI = dyn_cast<AllocaInst>(II)) {
1741 AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1742 if (!FirstSunkAlloca)
1743 FirstSunkAlloca = AI;
1744 }
1745 }
1746 assert((SinkingCands.empty() || FirstSunkAlloca) &&
1747 "Did not expect a sink candidate without any allocas");
1748 for (auto *II : SinkingCands) {
1749 if (!isa<AllocaInst>(II)) {
1750 cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1751 }
1752 }
1753
1754 if (!HoistingCands.empty()) {
1755 auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1756 Instruction *TI = HoistToBlock->getTerminator();
1757 for (auto *II : HoistingCands)
1758 cast<Instruction>(II)->moveBefore(TI);
1759 }
1760
1761 // Collect objects which are inputs to the extraction region and also
1762 // referenced by lifetime start markers within it. The effects of these
1763 // markers must be replicated in the calling function to prevent the stack
1764 // coloring pass from merging slots which store input objects.
1765 ValueSet LifetimesStart;
1766 eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1767
1768 // Construct new function based on inputs/outputs & add allocas for all defs.
1769 Function *newFunction =
1770 constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1771 oldFunction, oldFunction->getParent());
1772
1773 // Update the entry count of the function.
1774 if (BFI) {
1775 auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1776 if (Count)
1777 newFunction->setEntryCount(
1778 ProfileCount(*Count, Function::PCT_Real)); // FIXME
1779 BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1780 }
1781
1782 CallInst *TheCall =
1783 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1784
1785 moveCodeToFunction(newFunction);
1786
1787 // Replicate the effects of any lifetime start/end markers which referenced
1788 // input objects in the extraction region by placing markers around the call.
1790 oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1791
1792 // Propagate personality info to the new function if there is one.
1793 if (oldFunction->hasPersonalityFn())
1794 newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1795
1796 // Update the branch weights for the exit block.
1797 if (BFI && NumExitBlocks > 1)
1798 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1799
1800 // Loop over all of the PHI nodes in the header and exit blocks, and change
1801 // any references to the old incoming edge to be the new incoming edge.
1802 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1803 PHINode *PN = cast<PHINode>(I);
1804 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1805 if (!Blocks.count(PN->getIncomingBlock(i)))
1806 PN->setIncomingBlock(i, newFuncRoot);
1807 }
1808
1809 for (BasicBlock *ExitBB : ExitBlocks)
1810 for (PHINode &PN : ExitBB->phis()) {
1811 Value *IncomingCodeReplacerVal = nullptr;
1812 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1813 // Ignore incoming values from outside of the extracted region.
1814 if (!Blocks.count(PN.getIncomingBlock(i)))
1815 continue;
1816
1817 // Ensure that there is only one incoming value from codeReplacer.
1818 if (!IncomingCodeReplacerVal) {
1819 PN.setIncomingBlock(i, codeReplacer);
1820 IncomingCodeReplacerVal = PN.getIncomingValue(i);
1821 } else
1822 assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1823 "PHI has two incompatbile incoming values from codeRepl");
1824 }
1825 }
1826
1827 fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1828
1829 // Mark the new function `noreturn` if applicable. Terminators which resume
1830 // exception propagation are treated as returning instructions. This is to
1831 // avoid inserting traps after calls to outlined functions which unwind.
1832 bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1833 const Instruction *Term = BB.getTerminator();
1834 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1835 });
1836 if (doesNotReturn)
1837 newFunction->setDoesNotReturn();
1838
1839 LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1840 newFunction->dump();
1841 report_fatal_error("verification of newFunction failed!");
1842 });
1843 LLVM_DEBUG(if (verifyFunction(*oldFunction))
1844 report_fatal_error("verification of oldFunction failed!"));
1845 LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1846 report_fatal_error("Stale Asumption cache for old Function!"));
1847 return newFunction;
1848}
1849
1851 const Function &NewFunc,
1852 AssumptionCache *AC) {
1853 for (auto AssumeVH : AC->assumptions()) {
1854 auto *I = dyn_cast_or_null<CallInst>(AssumeVH);
1855 if (!I)
1856 continue;
1857
1858 // There shouldn't be any llvm.assume intrinsics in the new function.
1859 if (I->getFunction() != &OldFunc)
1860 return true;
1861
1862 // There shouldn't be any stale affected values in the assumption cache
1863 // that were previously in the old function, but that have now been moved
1864 // to the new function.
1865 for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1866 auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1867 if (!AffectedCI)
1868 continue;
1869 if (AffectedCI->getFunction() != &OldFunc)
1870 return true;
1871 auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1872 if (AssumedInst->getFunction() != &OldFunc)
1873 return true;
1874 }
1875 }
1876 return false;
1877}
1878
1880 ExcludeArgsFromAggregate.insert(Arg);
1881}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Callee
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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:491
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
Hexagon Common GEP
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
Definition: IVUsers.cpp:48
Move duplicate certain instructions close to their use
Definition: Localizer.cpp: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.
print must be executed print the must be executed context for all instructions
LLVMContext & Context
static StringRef getName(Value *V)
@ SI
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:158
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:94
@ None
No attributes have been set.
Definition: Attributes.h:89
@ EmptyKey
Use as Empty key for DenseMap of AttrKind.
Definition: Attributes.h:93
@ EndAttrKinds
Sentinal value useful for loops.
Definition: Attributes.h:92
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:328
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:326
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:253
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:507
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:338
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:409
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:1542
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:542
void finalizeSubprogram(DISubprogram *SP)
Finalize a specific subprogram - no new variables may be added to this subprogram afterwards.
Definition: DIBuilder.cpp:54
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:842
DITypeRefArray getOrCreateTypeArray(ArrayRef< Metadata * > Elements)
Get a DITypeRefArray, create one if required.
Definition: DIBuilder.cpp:683
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:793
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:252
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.cpp:554
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1721
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
const BasicBlock & getEntryBlock() const
Definition: Function.h:745
const BasicBlock & front() const
Definition: Function.h:768
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1725
void setDoesNotReturn()
Definition: Function.h:528
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:813
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1961
void setPersonalityFn(Constant *Fn)
Definition: Function.cpp:1966
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:313
arg_iterator arg_end()
Definition: Function.h:785
iterator begin()
Definition: Function.h:761
arg_iterator arg_begin()
Definition: Function.h:776
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
Definition: Function.cpp:582
Function::iterator insert(Function::iterator Position, BasicBlock *BB)
Insert BB in the basic block list at Position.
Definition: Function.h:692
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:179
iterator end()
Definition: Function.h:763
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:2025
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:187
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:88
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
const BasicBlock * getParent() const
Definition: Instruction.h:90
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:74
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:98
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
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:51
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:219
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:213
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:83
ArrayRef< value_type > getArrayRef() const
Definition: SetVector.h:74
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:344
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:434
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:4938
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:1465
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:6511
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:748
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:1826
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:511
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:1833
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
auto predecessors(const MachineBasicBlock *BB)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
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.