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