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