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