LLVM  16.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 (const 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);
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  const DataLayout &DL = M->getDataLayout();
835 
836  // Add the types of the input values to the function's argument list
837  for (Value *value : inputs) {
838  LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
839  if (AggregateArgs && !ExcludeArgsFromAggregate.contains(value)) {
840  AggParamTy.push_back(value->getType());
841  StructValues.insert(value);
842  } else
843  ParamTy.push_back(value->getType());
844  }
845 
846  // Add the types of the output values to the function's argument list.
847  for (Value *output : outputs) {
848  LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
849  if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {
850  AggParamTy.push_back(output->getType());
851  StructValues.insert(output);
852  } else
853  ParamTy.push_back(
854  PointerType::get(output->getType(), DL.getAllocaAddrSpace()));
855  }
856 
857  assert(
858  (ParamTy.size() + AggParamTy.size()) ==
859  (inputs.size() + outputs.size()) &&
860  "Number of scalar and aggregate params does not match inputs, outputs");
861  assert((StructValues.empty() || AggregateArgs) &&
862  "Expeced StructValues only with AggregateArgs set");
863 
864  // Concatenate scalar and aggregate params in ParamTy.
865  size_t NumScalarParams = ParamTy.size();
866  StructType *StructTy = nullptr;
867  if (AggregateArgs && !AggParamTy.empty()) {
868  StructTy = StructType::get(M->getContext(), AggParamTy);
869  ParamTy.push_back(PointerType::get(StructTy, DL.getAllocaAddrSpace()));
870  }
871 
872  LLVM_DEBUG({
873  dbgs() << "Function type: " << *RetTy << " f(";
874  for (Type *i : ParamTy)
875  dbgs() << *i << ", ";
876  dbgs() << ")\n";
877  });
878 
879  FunctionType *funcType = FunctionType::get(
880  RetTy, ParamTy, AllowVarArgs && oldFunction->isVarArg());
881 
882  std::string SuffixToUse =
883  Suffix.empty()
884  ? (header->getName().empty() ? "extracted" : header->getName().str())
885  : Suffix;
886  // Create the new function
887  Function *newFunction = Function::Create(
888  funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
889  oldFunction->getName() + "." + SuffixToUse, M);
890 
891  // Inherit all of the target dependent attributes and white-listed
892  // target independent attributes.
893  // (e.g. If the extracted region contains a call to an x86.sse
894  // instruction we need to make sure that the extracted region has the
895  // "target-features" attribute allowing it to be lowered.
896  // FIXME: This should be changed to check to see if a specific
897  // attribute can not be inherited.
898  for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) {
899  if (Attr.isStringAttribute()) {
900  if (Attr.getKindAsString() == "thunk")
901  continue;
902  } else
903  switch (Attr.getKindAsEnum()) {
904  // Those attributes cannot be propagated safely. Explicitly list them
905  // here so we get a warning if new attributes are added.
906  case Attribute::AllocSize:
907  case Attribute::Builtin:
910  case Attribute::Naked:
911  case Attribute::NoBuiltin:
912  case Attribute::NoMerge:
913  case Attribute::NoReturn:
914  case Attribute::NoSync:
915  case Attribute::ReturnsTwice:
916  case Attribute::Speculatable:
917  case Attribute::StackAlignment:
918  case Attribute::WillReturn:
919  case Attribute::AllocKind:
920  case Attribute::PresplitCoroutine:
921  case Attribute::Memory:
922  continue;
923  // Those attributes should be safe to propagate to the extracted function.
924  case Attribute::AlwaysInline:
925  case Attribute::Cold:
926  case Attribute::DisableSanitizerInstrumentation:
927  case Attribute::FnRetThunkExtern:
928  case Attribute::Hot:
929  case Attribute::NoRecurse:
930  case Attribute::InlineHint:
931  case Attribute::MinSize:
932  case Attribute::NoCallback:
933  case Attribute::NoDuplicate:
934  case Attribute::NoFree:
935  case Attribute::NoImplicitFloat:
936  case Attribute::NoInline:
937  case Attribute::NonLazyBind:
938  case Attribute::NoRedZone:
939  case Attribute::NoUnwind:
940  case Attribute::NoSanitizeBounds:
941  case Attribute::NoSanitizeCoverage:
942  case Attribute::NullPointerIsValid:
943  case Attribute::OptForFuzzing:
944  case Attribute::OptimizeNone:
945  case Attribute::OptimizeForSize:
946  case Attribute::SafeStack:
947  case Attribute::ShadowCallStack:
948  case Attribute::SanitizeAddress:
949  case Attribute::SanitizeMemory:
950  case Attribute::SanitizeThread:
951  case Attribute::SanitizeHWAddress:
952  case Attribute::SanitizeMemTag:
953  case Attribute::SpeculativeLoadHardening:
954  case Attribute::StackProtect:
955  case Attribute::StackProtectReq:
956  case Attribute::StackProtectStrong:
957  case Attribute::StrictFP:
958  case Attribute::UWTable:
959  case Attribute::VScaleRange:
960  case Attribute::NoCfCheck:
961  case Attribute::MustProgress:
962  case Attribute::NoProfile:
963  case Attribute::SkipProfile:
964  break;
965  // These attributes cannot be applied to functions.
966  case Attribute::Alignment:
967  case Attribute::AllocatedPointer:
968  case Attribute::AllocAlign:
969  case Attribute::ByVal:
970  case Attribute::Dereferenceable:
971  case Attribute::DereferenceableOrNull:
972  case Attribute::ElementType:
973  case Attribute::InAlloca:
974  case Attribute::InReg:
975  case Attribute::Nest:
976  case Attribute::NoAlias:
977  case Attribute::NoCapture:
978  case Attribute::NoUndef:
979  case Attribute::NonNull:
980  case Attribute::Preallocated:
981  case Attribute::ReadNone:
982  case Attribute::ReadOnly:
983  case Attribute::Returned:
984  case Attribute::SExt:
985  case Attribute::StructRet:
986  case Attribute::SwiftError:
987  case Attribute::SwiftSelf:
988  case Attribute::SwiftAsync:
989  case Attribute::ZExt:
990  case Attribute::ImmArg:
991  case Attribute::ByRef:
992  case Attribute::WriteOnly:
993  // These are not really attributes.
994  case Attribute::None:
996  case Attribute::EmptyKey:
998  llvm_unreachable("Not a function attribute");
999  }
1000 
1001  newFunction->addFnAttr(Attr);
1002  }
1003  newFunction->getBasicBlockList().push_back(newRootNode);
1004 
1005  // Create scalar and aggregate iterators to name all of the arguments we
1006  // inserted.
1007  Function::arg_iterator ScalarAI = newFunction->arg_begin();
1008  Function::arg_iterator AggAI = std::next(ScalarAI, NumScalarParams);
1009 
1010  // Rewrite all users of the inputs in the extracted region to use the
1011  // arguments (or appropriate addressing into struct) instead.
1012  for (unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) {
1013  Value *RewriteVal;
1014  if (AggregateArgs && StructValues.contains(inputs[i])) {
1015  Value *Idx[2];
1016  Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
1017  Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), aggIdx);
1018  Instruction *TI = newFunction->begin()->getTerminator();
1020  StructTy, &*AggAI, Idx, "gep_" + inputs[i]->getName(), TI);
1021  RewriteVal = new LoadInst(StructTy->getElementType(aggIdx), GEP,
1022  "loadgep_" + inputs[i]->getName(), TI);
1023  ++aggIdx;
1024  } else
1025  RewriteVal = &*ScalarAI++;
1026 
1027  std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
1028  for (User *use : Users)
1029  if (Instruction *inst = dyn_cast<Instruction>(use))
1030  if (Blocks.count(inst->getParent()))
1031  inst->replaceUsesOfWith(inputs[i], RewriteVal);
1032  }
1033 
1034  // Set names for input and output arguments.
1035  if (NumScalarParams) {
1036  ScalarAI = newFunction->arg_begin();
1037  for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++ScalarAI)
1038  if (!StructValues.contains(inputs[i]))
1039  ScalarAI->setName(inputs[i]->getName());
1040  for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++ScalarAI)
1041  if (!StructValues.contains(outputs[i]))
1042  ScalarAI->setName(outputs[i]->getName() + ".out");
1043  }
1044 
1045  // Rewrite branches to basic blocks outside of the loop to new dummy blocks
1046  // within the new function. This must be done before we lose track of which
1047  // blocks were originally in the code region.
1048  std::vector<User *> Users(header->user_begin(), header->user_end());
1049  for (auto &U : Users)
1050  // The BasicBlock which contains the branch is not in the region
1051  // modify the branch target to a new block
1052  if (Instruction *I = dyn_cast<Instruction>(U))
1053  if (I->isTerminator() && I->getFunction() == oldFunction &&
1054  !Blocks.count(I->getParent()))
1055  I->replaceUsesOfWith(header, newHeader);
1056 
1057  return newFunction;
1058 }
1059 
1060 /// Erase lifetime.start markers which reference inputs to the extraction
1061 /// region, and insert the referenced memory into \p LifetimesStart.
1062 ///
1063 /// The extraction region is defined by a set of blocks (\p Blocks), and a set
1064 /// of allocas which will be moved from the caller function into the extracted
1065 /// function (\p SunkAllocas).
1067  const SetVector<Value *> &SunkAllocas,
1068  SetVector<Value *> &LifetimesStart) {
1069  for (BasicBlock *BB : Blocks) {
1071  auto *II = dyn_cast<IntrinsicInst>(&I);
1072  if (!II || !II->isLifetimeStartOrEnd())
1073  continue;
1074 
1075  // Get the memory operand of the lifetime marker. If the underlying
1076  // object is a sunk alloca, or is otherwise defined in the extraction
1077  // region, the lifetime marker must not be erased.
1078  Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1079  if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1080  continue;
1081 
1082  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1083  LifetimesStart.insert(Mem);
1084  II->eraseFromParent();
1085  }
1086  }
1087 }
1088 
1089 /// Insert lifetime start/end markers surrounding the call to the new function
1090 /// for objects defined in the caller.
1092  Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1093  CallInst *TheCall) {
1094  LLVMContext &Ctx = M->getContext();
1095  auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
1096  auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1097  Instruction *Term = TheCall->getParent()->getTerminator();
1098 
1099  // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
1100  // needed to satisfy this requirement so they may be reused.
1101  DenseMap<Value *, Value *> Bitcasts;
1102 
1103  // Emit lifetime markers for the pointers given in \p Objects. Insert the
1104  // markers before the call if \p InsertBefore, and after the call otherwise.
1105  auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
1106  bool InsertBefore) {
1107  for (Value *Mem : Objects) {
1108  assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1109  TheCall->getFunction()) &&
1110  "Input memory not defined in original function");
1111  Value *&MemAsI8Ptr = Bitcasts[Mem];
1112  if (!MemAsI8Ptr) {
1113  if (Mem->getType() == Int8PtrTy)
1114  MemAsI8Ptr = Mem;
1115  else
1116  MemAsI8Ptr =
1117  CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
1118  }
1119 
1120  auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
1121  if (InsertBefore)
1122  Marker->insertBefore(TheCall);
1123  else
1124  Marker->insertBefore(Term);
1125  }
1126  };
1127 
1128  if (!LifetimesStart.empty()) {
1129  auto StartFn = llvm::Intrinsic::getDeclaration(
1130  M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
1131  insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
1132  }
1133 
1134  if (!LifetimesEnd.empty()) {
1135  auto EndFn = llvm::Intrinsic::getDeclaration(
1136  M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
1137  insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
1138  }
1139 }
1140 
1141 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
1142 /// the call instruction, splitting any PHI nodes in the header block as
1143 /// necessary.
1144 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1145  BasicBlock *codeReplacer,
1146  ValueSet &inputs,
1147  ValueSet &outputs) {
1148  // Emit a call to the new function, passing in: *pointer to struct (if
1149  // aggregating parameters), or plan inputs and allocated memory for outputs
1150  std::vector<Value *> params, ReloadOutputs, Reloads;
1151  ValueSet StructValues;
1152 
1153  Module *M = newFunction->getParent();
1154  LLVMContext &Context = M->getContext();
1155  const DataLayout &DL = M->getDataLayout();
1156  CallInst *call = nullptr;
1157 
1158  // Add inputs as params, or to be filled into the struct
1159  unsigned ScalarInputArgNo = 0;
1160  SmallVector<unsigned, 1> SwiftErrorArgs;
1161  for (Value *input : inputs) {
1162  if (AggregateArgs && !ExcludeArgsFromAggregate.contains(input))
1163  StructValues.insert(input);
1164  else {
1165  params.push_back(input);
1166  if (input->isSwiftError())
1167  SwiftErrorArgs.push_back(ScalarInputArgNo);
1168  }
1169  ++ScalarInputArgNo;
1170  }
1171 
1172  // Create allocas for the outputs
1173  unsigned ScalarOutputArgNo = 0;
1174  for (Value *output : outputs) {
1175  if (AggregateArgs && !ExcludeArgsFromAggregate.contains(output)) {
1176  StructValues.insert(output);
1177  } else {
1178  AllocaInst *alloca =
1179  new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1180  nullptr, output->getName() + ".loc",
1181  &codeReplacer->getParent()->front().front());
1182  ReloadOutputs.push_back(alloca);
1183  params.push_back(alloca);
1184  ++ScalarOutputArgNo;
1185  }
1186  }
1187 
1188  StructType *StructArgTy = nullptr;
1189  AllocaInst *Struct = nullptr;
1190  unsigned NumAggregatedInputs = 0;
1191  if (AggregateArgs && !StructValues.empty()) {
1192  std::vector<Type *> ArgTypes;
1193  for (Value *V : StructValues)
1194  ArgTypes.push_back(V->getType());
1195 
1196  // Allocate a struct at the beginning of this function
1197  StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1198  Struct = new AllocaInst(
1199  StructArgTy, DL.getAllocaAddrSpace(), nullptr, "structArg",
1200  AllocationBlock ? &*AllocationBlock->getFirstInsertionPt()
1201  : &codeReplacer->getParent()->front().front());
1202  params.push_back(Struct);
1203 
1204  // Store aggregated inputs in the struct.
1205  for (unsigned i = 0, e = StructValues.size(); i != e; ++i) {
1206  if (inputs.contains(StructValues[i])) {
1207  Value *Idx[2];
1211  StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1212  codeReplacer->getInstList().push_back(GEP);
1213  new StoreInst(StructValues[i], GEP, codeReplacer);
1214  NumAggregatedInputs++;
1215  }
1216  }
1217  }
1218 
1219  // Emit the call to the function
1220  call = CallInst::Create(newFunction, params,
1221  NumExitBlocks > 1 ? "targetBlock" : "");
1222  // Add debug location to the new call, if the original function has debug
1223  // info. In that case, the terminator of the entry block of the extracted
1224  // function contains the first debug location of the extracted function,
1225  // set in extractCodeRegion.
1226  if (codeReplacer->getParent()->getSubprogram()) {
1227  if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1228  call->setDebugLoc(DL);
1229  }
1230  codeReplacer->getInstList().push_back(call);
1231 
1232  // Set swifterror parameter attributes.
1233  for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1234  call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1235  newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1236  }
1237 
1238  // Reload the outputs passed in by reference, use the struct if output is in
1239  // the aggregate or reload from the scalar argument.
1240  for (unsigned i = 0, e = outputs.size(), scalarIdx = 0,
1241  aggIdx = NumAggregatedInputs;
1242  i != e; ++i) {
1243  Value *Output = nullptr;
1244  if (AggregateArgs && StructValues.contains(outputs[i])) {
1245  Value *Idx[2];
1247  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx);
1249  StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1250  codeReplacer->getInstList().push_back(GEP);
1251  Output = GEP;
1252  ++aggIdx;
1253  } else {
1254  Output = ReloadOutputs[scalarIdx];
1255  ++scalarIdx;
1256  }
1257  LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1258  outputs[i]->getName() + ".reload",
1259  codeReplacer);
1260  Reloads.push_back(load);
1261  std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1262  for (User *U : Users) {
1263  Instruction *inst = cast<Instruction>(U);
1264  if (!Blocks.count(inst->getParent()))
1265  inst->replaceUsesOfWith(outputs[i], load);
1266  }
1267  }
1268 
1269  // Now we can emit a switch statement using the call as a value.
1270  SwitchInst *TheSwitch =
1272  codeReplacer, 0, codeReplacer);
1273 
1274  // Since there may be multiple exits from the original region, make the new
1275  // function return an unsigned, switch on that number. This loop iterates
1276  // over all of the blocks in the extracted region, updating any terminator
1277  // instructions in the to-be-extracted region that branch to blocks that are
1278  // not in the region to be extracted.
1279  std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1280 
1281  // Iterate over the previously collected targets, and create new blocks inside
1282  // the function to branch to.
1283  unsigned switchVal = 0;
1284  for (BasicBlock *OldTarget : OldTargets) {
1285  if (Blocks.count(OldTarget))
1286  continue;
1287  BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1288  if (NewTarget)
1289  continue;
1290 
1291  // If we don't already have an exit stub for this non-extracted
1292  // destination, create one now!
1293  NewTarget = BasicBlock::Create(Context,
1294  OldTarget->getName() + ".exitStub",
1295  newFunction);
1296  unsigned SuccNum = switchVal++;
1297 
1298  Value *brVal = nullptr;
1299  assert(NumExitBlocks < 0xffff && "too many exit blocks for switch");
1300  switch (NumExitBlocks) {
1301  case 0:
1302  case 1: break; // No value needed.
1303  case 2: // Conditional branch, return a bool
1304  brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1305  break;
1306  default:
1307  brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1308  break;
1309  }
1310 
1311  ReturnInst::Create(Context, brVal, NewTarget);
1312 
1313  // Update the switch instruction.
1315  SuccNum),
1316  OldTarget);
1317  }
1318 
1319  for (BasicBlock *Block : Blocks) {
1320  Instruction *TI = Block->getTerminator();
1321  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1322  if (Blocks.count(TI->getSuccessor(i)))
1323  continue;
1324  BasicBlock *OldTarget = TI->getSuccessor(i);
1325  // add a new basic block which returns the appropriate value
1326  BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1327  assert(NewTarget && "Unknown target block!");
1328 
1329  // rewrite the original branch instruction with this new target
1330  TI->setSuccessor(i, NewTarget);
1331  }
1332  }
1333 
1334  // Store the arguments right after the definition of output value.
1335  // This should be proceeded after creating exit stubs to be ensure that invoke
1336  // result restore will be placed in the outlined function.
1337  Function::arg_iterator ScalarOutputArgBegin = newFunction->arg_begin();
1338  std::advance(ScalarOutputArgBegin, ScalarInputArgNo);
1339  Function::arg_iterator AggOutputArgBegin = newFunction->arg_begin();
1340  std::advance(AggOutputArgBegin, ScalarInputArgNo + ScalarOutputArgNo);
1341 
1342  for (unsigned i = 0, e = outputs.size(), aggIdx = NumAggregatedInputs; i != e;
1343  ++i) {
1344  auto *OutI = dyn_cast<Instruction>(outputs[i]);
1345  if (!OutI)
1346  continue;
1347 
1348  // Find proper insertion point.
1349  BasicBlock::iterator InsertPt;
1350  // In case OutI is an invoke, we insert the store at the beginning in the
1351  // 'normal destination' BB. Otherwise we insert the store right after OutI.
1352  if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1353  InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1354  else if (auto *Phi = dyn_cast<PHINode>(OutI))
1355  InsertPt = Phi->getParent()->getFirstInsertionPt();
1356  else
1357  InsertPt = std::next(OutI->getIterator());
1358 
1359  Instruction *InsertBefore = &*InsertPt;
1360  assert((InsertBefore->getFunction() == newFunction ||
1361  Blocks.count(InsertBefore->getParent())) &&
1362  "InsertPt should be in new function");
1363  if (AggregateArgs && StructValues.contains(outputs[i])) {
1364  assert(AggOutputArgBegin != newFunction->arg_end() &&
1365  "Number of aggregate output arguments should match "
1366  "the number of defined values");
1367  Value *Idx[2];
1369  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), aggIdx);
1371  StructArgTy, &*AggOutputArgBegin, Idx, "gep_" + outputs[i]->getName(),
1372  InsertBefore);
1373  new StoreInst(outputs[i], GEP, InsertBefore);
1374  ++aggIdx;
1375  // Since there should be only one struct argument aggregating
1376  // all the output values, we shouldn't increment AggOutputArgBegin, which
1377  // always points to the struct argument, in this case.
1378  } else {
1379  assert(ScalarOutputArgBegin != newFunction->arg_end() &&
1380  "Number of scalar output arguments should match "
1381  "the number of defined values");
1382  new StoreInst(outputs[i], &*ScalarOutputArgBegin, InsertBefore);
1383  ++ScalarOutputArgBegin;
1384  }
1385  }
1386 
1387  // Now that we've done the deed, simplify the switch instruction.
1388  Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1389  switch (NumExitBlocks) {
1390  case 0:
1391  // There are no successors (the block containing the switch itself), which
1392  // means that previously this was the last part of the function, and hence
1393  // this should be rewritten as a `ret'
1394 
1395  // Check if the function should return a value
1396  if (OldFnRetTy->isVoidTy()) {
1397  ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
1398  } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1399  // return what we have
1400  ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1401  } else {
1402  // Otherwise we must have code extracted an unwind or something, just
1403  // return whatever we want.
1405  Constant::getNullValue(OldFnRetTy), TheSwitch);
1406  }
1407 
1408  TheSwitch->eraseFromParent();
1409  break;
1410  case 1:
1411  // Only a single destination, change the switch into an unconditional
1412  // branch.
1413  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1414  TheSwitch->eraseFromParent();
1415  break;
1416  case 2:
1417  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1418  call, TheSwitch);
1419  TheSwitch->eraseFromParent();
1420  break;
1421  default:
1422  // Otherwise, make the default destination of the switch instruction be one
1423  // of the other successors.
1424  TheSwitch->setCondition(call);
1425  TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1426  // Remove redundant case
1427  TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1428  break;
1429  }
1430 
1431  // Insert lifetime markers around the reloads of any output values. The
1432  // allocas output values are stored in are only in-use in the codeRepl block.
1433  insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1434 
1435  return call;
1436 }
1437 
1438 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1439  Function *oldFunc = (*Blocks.begin())->getParent();
1440  Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1441  Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1442 
1443  auto newFuncIt = newFunction->front().getIterator();
1444  for (BasicBlock *Block : Blocks) {
1445  // Delete the basic block from the old function, and the list of blocks
1446  oldBlocks.remove(Block);
1447 
1448  // Insert this basic block into the new function
1449  // Insert the original blocks after the entry block created
1450  // for the new function. The entry block may be followed
1451  // by a set of exit blocks at this point, but these exit
1452  // blocks better be placed at the end of the new function.
1453  newFuncIt = newBlocks.insertAfter(newFuncIt, Block);
1454  }
1455 }
1456 
1457 void CodeExtractor::calculateNewCallTerminatorWeights(
1458  BasicBlock *CodeReplacer,
1460  BranchProbabilityInfo *BPI) {
1461  using Distribution = BlockFrequencyInfoImplBase::Distribution;
1462  using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1463 
1464  // Update the branch weights for the exit block.
1465  Instruction *TI = CodeReplacer->getTerminator();
1466  SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1467 
1468  // Block Frequency distribution with dummy node.
1469  Distribution BranchDist;
1470 
1471  SmallVector<BranchProbability, 4> EdgeProbabilities(
1473 
1474  // Add each of the frequencies of the successors.
1475  for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1476  BlockNode ExitNode(i);
1477  uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1478  if (ExitFreq != 0)
1479  BranchDist.addExit(ExitNode, ExitFreq);
1480  else
1481  EdgeProbabilities[i] = BranchProbability::getZero();
1482  }
1483 
1484  // Check for no total weight.
1485  if (BranchDist.Total == 0) {
1486  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1487  return;
1488  }
1489 
1490  // Normalize the distribution so that they can fit in unsigned.
1491  BranchDist.normalize();
1492 
1493  // Create normalized branch weights and set the metadata.
1494  for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1495  const auto &Weight = BranchDist.Weights[I];
1496 
1497  // Get the weight and update the current BFI.
1498  BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1499  BranchProbability BP(Weight.Amount, BranchDist.Total);
1500  EdgeProbabilities[Weight.TargetNode.Index] = BP;
1501  }
1502  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1503  TI->setMetadata(
1504  LLVMContext::MD_prof,
1505  MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1506 }
1507 
1508 /// Erase debug info intrinsics which refer to values in \p F but aren't in
1509 /// \p F.
1511  for (Instruction &I : instructions(F)) {
1513  findDbgUsers(DbgUsers, &I);
1514  for (DbgVariableIntrinsic *DVI : DbgUsers)
1515  if (DVI->getFunction() != &F)
1516  DVI->eraseFromParent();
1517  }
1518 }
1519 
1520 /// Fix up the debug info in the old and new functions by pointing line
1521 /// locations and debug intrinsics to the new subprogram scope, and by deleting
1522 /// intrinsics which point to values outside of the new function.
1523 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1524  CallInst &TheCall) {
1525  DISubprogram *OldSP = OldFunc.getSubprogram();
1526  LLVMContext &Ctx = OldFunc.getContext();
1527 
1528  if (!OldSP) {
1529  // Erase any debug info the new function contains.
1530  stripDebugInfo(NewFunc);
1531  // Make sure the old function doesn't contain any non-local metadata refs.
1533  return;
1534  }
1535 
1536  // Create a subprogram for the new function. Leave out a description of the
1537  // function arguments, as the parameters don't correspond to anything at the
1538  // source level.
1539  assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1540  DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,
1541  OldSP->getUnit());
1542  auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
1543  DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1544  DISubprogram::SPFlagOptimized |
1545  DISubprogram::SPFlagLocalToUnit;
1546  auto NewSP = DIB.createFunction(
1547  OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1548  /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1549  NewFunc.setSubprogram(NewSP);
1550 
1551  // Debug intrinsics in the new function need to be updated in one of two
1552  // ways:
1553  // 1) They need to be deleted, because they describe a value in the old
1554  // function.
1555  // 2) They need to point to fresh metadata, e.g. because they currently
1556  // point to a variable in the wrong scope.
1557  SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1558  SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1559  for (Instruction &I : instructions(NewFunc)) {
1560  auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1561  if (!DII)
1562  continue;
1563 
1564  // Point the intrinsic to a fresh label within the new function.
1565  if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1566  DILabel *OldLabel = DLI->getLabel();
1567  DINode *&NewLabel = RemappedMetadata[OldLabel];
1568  if (!NewLabel)
1569  NewLabel = DILabel::get(Ctx, NewSP, OldLabel->getName(),
1570  OldLabel->getFile(), OldLabel->getLine());
1571  DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
1572  continue;
1573  }
1574 
1575  auto IsInvalidLocation = [&NewFunc](Value *Location) {
1576  // Location is invalid if it isn't a constant or an instruction, or is an
1577  // instruction but isn't in the new function.
1578  if (!Location ||
1579  (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1580  return true;
1581  Instruction *LocationInst = dyn_cast<Instruction>(Location);
1582  return LocationInst && LocationInst->getFunction() != &NewFunc;
1583  };
1584 
1585  auto *DVI = cast<DbgVariableIntrinsic>(DII);
1586  // If any of the used locations are invalid, delete the intrinsic.
1587  if (any_of(DVI->location_ops(), IsInvalidLocation)) {
1588  DebugIntrinsicsToDelete.push_back(DVI);
1589  continue;
1590  }
1591 
1592  // Point the intrinsic to a fresh variable within the new function.
1593  DILocalVariable *OldVar = DVI->getVariable();
1594  DINode *&NewVar = RemappedMetadata[OldVar];
1595  if (!NewVar)
1596  NewVar = DIB.createAutoVariable(
1597  NewSP, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1598  OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1599  OldVar->getAlignInBits());
1600  DVI->setVariable(cast<DILocalVariable>(NewVar));
1601  }
1602  for (auto *DII : DebugIntrinsicsToDelete)
1603  DII->eraseFromParent();
1604  DIB.finalizeSubprogram(NewSP);
1605 
1606  // Fix up the scope information attached to the line locations in the new
1607  // function.
1608  for (Instruction &I : instructions(NewFunc)) {
1609  if (const DebugLoc &DL = I.getDebugLoc())
1610  I.setDebugLoc(DILocation::get(Ctx, DL.getLine(), DL.getCol(), NewSP));
1611 
1612  // Loop info metadata may contain line locations. Fix them up.
1613  auto updateLoopInfoLoc = [&Ctx, NewSP](Metadata *MD) -> Metadata * {
1614  if (auto *Loc = dyn_cast_or_null<DILocation>(MD))
1615  return DILocation::get(Ctx, Loc->getLine(), Loc->getColumn(), NewSP,
1616  nullptr);
1617  return MD;
1618  };
1619  updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1620  }
1621  if (!TheCall.getDebugLoc())
1622  TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP));
1623 
1625 }
1626 
1627 Function *
1629  ValueSet Inputs, Outputs;
1630  return extractCodeRegion(CEAC, Inputs, Outputs);
1631 }
1632 
1633 Function *
1635  ValueSet &inputs, ValueSet &outputs) {
1636  if (!isEligible())
1637  return nullptr;
1638 
1639  // Assumption: this is a single-entry code region, and the header is the first
1640  // block in the region.
1641  BasicBlock *header = *Blocks.begin();
1642  Function *oldFunction = header->getParent();
1643 
1644  // Calculate the entry frequency of the new function before we change the root
1645  // block.
1646  BlockFrequency EntryFreq;
1647  if (BFI) {
1648  assert(BPI && "Both BPI and BFI are required to preserve profile info");
1649  for (BasicBlock *Pred : predecessors(header)) {
1650  if (Blocks.count(Pred))
1651  continue;
1652  EntryFreq +=
1653  BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1654  }
1655  }
1656 
1657  // Remove @llvm.assume calls that will be moved to the new function from the
1658  // old function's assumption cache.
1659  for (BasicBlock *Block : Blocks) {
1660  for (Instruction &I : llvm::make_early_inc_range(*Block)) {
1661  if (auto *AI = dyn_cast<AssumeInst>(&I)) {
1662  if (AC)
1663  AC->unregisterAssumption(AI);
1664  AI->eraseFromParent();
1665  }
1666  }
1667  }
1668 
1669  // If we have any return instructions in the region, split those blocks so
1670  // that the return is not in the region.
1671  splitReturnBlocks();
1672 
1673  // Calculate the exit blocks for the extracted region and the total exit
1674  // weights for each of those blocks.
1676  SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1677  for (BasicBlock *Block : Blocks) {
1678  for (BasicBlock *Succ : successors(Block)) {
1679  if (!Blocks.count(Succ)) {
1680  // Update the branch weight for this successor.
1681  if (BFI) {
1682  BlockFrequency &BF = ExitWeights[Succ];
1683  BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ);
1684  }
1685  ExitBlocks.insert(Succ);
1686  }
1687  }
1688  }
1689  NumExitBlocks = ExitBlocks.size();
1690 
1691  for (BasicBlock *Block : Blocks) {
1692  Instruction *TI = Block->getTerminator();
1693  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1694  if (Blocks.count(TI->getSuccessor(i)))
1695  continue;
1696  BasicBlock *OldTarget = TI->getSuccessor(i);
1697  OldTargets.push_back(OldTarget);
1698  }
1699  }
1700 
1701  // If we have to split PHI nodes of the entry or exit blocks, do so now.
1702  severSplitPHINodesOfEntry(header);
1703  severSplitPHINodesOfExits(ExitBlocks);
1704 
1705  // This takes place of the original loop
1706  BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1707  "codeRepl", oldFunction,
1708  header);
1709 
1710  // The new function needs a root node because other nodes can branch to the
1711  // head of the region, but the entry node of a function cannot have preds.
1712  BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1713  "newFuncRoot");
1714  auto *BranchI = BranchInst::Create(header);
1715  // If the original function has debug info, we have to add a debug location
1716  // to the new branch instruction from the artificial entry block.
1717  // We use the debug location of the first instruction in the extracted
1718  // blocks, as there is no other equivalent line in the source code.
1719  if (oldFunction->getSubprogram()) {
1720  any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1721  return any_of(*BB, [&BranchI](const Instruction &I) {
1722  if (!I.getDebugLoc())
1723  return false;
1724  BranchI->setDebugLoc(I.getDebugLoc());
1725  return true;
1726  });
1727  });
1728  }
1729  newFuncRoot->getInstList().push_back(BranchI);
1730 
1731  ValueSet SinkingCands, HoistingCands;
1732  BasicBlock *CommonExit = nullptr;
1733  findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1734  assert(HoistingCands.empty() || CommonExit);
1735 
1736  // Find inputs to, outputs from the code region.
1737  findInputsOutputs(inputs, outputs, SinkingCands);
1738 
1739  // Now sink all instructions which only have non-phi uses inside the region.
1740  // Group the allocas at the start of the block, so that any bitcast uses of
1741  // the allocas are well-defined.
1742  AllocaInst *FirstSunkAlloca = nullptr;
1743  for (auto *II : SinkingCands) {
1744  if (auto *AI = dyn_cast<AllocaInst>(II)) {
1745  AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1746  if (!FirstSunkAlloca)
1747  FirstSunkAlloca = AI;
1748  }
1749  }
1750  assert((SinkingCands.empty() || FirstSunkAlloca) &&
1751  "Did not expect a sink candidate without any allocas");
1752  for (auto *II : SinkingCands) {
1753  if (!isa<AllocaInst>(II)) {
1754  cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1755  }
1756  }
1757 
1758  if (!HoistingCands.empty()) {
1759  auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1760  Instruction *TI = HoistToBlock->getTerminator();
1761  for (auto *II : HoistingCands)
1762  cast<Instruction>(II)->moveBefore(TI);
1763  }
1764 
1765  // Collect objects which are inputs to the extraction region and also
1766  // referenced by lifetime start markers within it. The effects of these
1767  // markers must be replicated in the calling function to prevent the stack
1768  // coloring pass from merging slots which store input objects.
1769  ValueSet LifetimesStart;
1770  eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1771 
1772  // Construct new function based on inputs/outputs & add allocas for all defs.
1773  Function *newFunction =
1774  constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1775  oldFunction, oldFunction->getParent());
1776 
1777  // Update the entry count of the function.
1778  if (BFI) {
1779  auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1780  if (Count)
1781  newFunction->setEntryCount(
1782  ProfileCount(Count.value(), Function::PCT_Real)); // FIXME
1783  BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1784  }
1785 
1786  CallInst *TheCall =
1787  emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1788 
1789  moveCodeToFunction(newFunction);
1790 
1791  // Replicate the effects of any lifetime start/end markers which referenced
1792  // input objects in the extraction region by placing markers around the call.
1794  oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1795 
1796  // Propagate personality info to the new function if there is one.
1797  if (oldFunction->hasPersonalityFn())
1798  newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1799 
1800  // Update the branch weights for the exit block.
1801  if (BFI && NumExitBlocks > 1)
1802  calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1803 
1804  // Loop over all of the PHI nodes in the header and exit blocks, and change
1805  // any references to the old incoming edge to be the new incoming edge.
1806  for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1807  PHINode *PN = cast<PHINode>(I);
1808  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1809  if (!Blocks.count(PN->getIncomingBlock(i)))
1810  PN->setIncomingBlock(i, newFuncRoot);
1811  }
1812 
1813  for (BasicBlock *ExitBB : ExitBlocks)
1814  for (PHINode &PN : ExitBB->phis()) {
1815  Value *IncomingCodeReplacerVal = nullptr;
1816  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1817  // Ignore incoming values from outside of the extracted region.
1818  if (!Blocks.count(PN.getIncomingBlock(i)))
1819  continue;
1820 
1821  // Ensure that there is only one incoming value from codeReplacer.
1822  if (!IncomingCodeReplacerVal) {
1823  PN.setIncomingBlock(i, codeReplacer);
1824  IncomingCodeReplacerVal = PN.getIncomingValue(i);
1825  } else
1826  assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1827  "PHI has two incompatbile incoming values from codeRepl");
1828  }
1829  }
1830 
1831  fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1832 
1833  // Mark the new function `noreturn` if applicable. Terminators which resume
1834  // exception propagation are treated as returning instructions. This is to
1835  // avoid inserting traps after calls to outlined functions which unwind.
1836  bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1837  const Instruction *Term = BB.getTerminator();
1838  return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1839  });
1840  if (doesNotReturn)
1841  newFunction->setDoesNotReturn();
1842 
1843  LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1844  newFunction->dump();
1845  report_fatal_error("verification of newFunction failed!");
1846  });
1847  LLVM_DEBUG(if (verifyFunction(*oldFunction))
1848  report_fatal_error("verification of oldFunction failed!"));
1849  LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1850  report_fatal_error("Stale Asumption cache for old Function!"));
1851  return newFunction;
1852 }
1853 
1855  const Function &NewFunc,
1856  AssumptionCache *AC) {
1857  for (auto AssumeVH : AC->assumptions()) {
1858  auto *I = dyn_cast_or_null<CallInst>(AssumeVH);
1859  if (!I)
1860  continue;
1861 
1862  // There shouldn't be any llvm.assume intrinsics in the new function.
1863  if (I->getFunction() != &OldFunc)
1864  return true;
1865 
1866  // There shouldn't be any stale affected values in the assumption cache
1867  // that were previously in the old function, but that have now been moved
1868  // to the new function.
1869  for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1870  auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1871  if (!AffectedCI)
1872  continue;
1873  if (AffectedCI->getFunction() != &OldFunc)
1874  return true;
1875  auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1876  if (AssumedInst->getFunction() != &OldFunc)
1877  return true;
1878  }
1879  }
1880  return false;
1881 }
1882 
1884  ExcludeArgsFromAggregate.insert(Arg);
1885 }
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:90
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:3229
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:20
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Definition: Instruction.cpp:807
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp: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:687
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:1723
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3051
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:1481
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:42
DebugInfoMetadata.h
llvm::Function::getBasicBlockList
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:684
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:236
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::Value::dump
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4919
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:1628
llvm::PointerType::get
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
Definition: Type.cpp:727
llvm::Attribute::TombstoneKey
@ TombstoneKey
Use as Tombstone key for DenseMap of AttrKind.
Definition: Attributes.h:92
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
output
Current output
Definition: README.txt:1350
llvm::SwitchInst::Create
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3466
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:1626
ErrorHandling.h
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:691
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::findDbgUsers
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:111
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:115
llvm::CallingConv::Cold
@ Cold
Attempts to make code in the caller as efficient as possible under the assumption that the call is no...
Definition: CallingConv.h:47
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:87
llvm::Attribute::EmptyKey
@ EmptyKey
Use as Empty key for DenseMap of AttrKind.
Definition: Attributes.h:91
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:6315
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:321
BlockFrequency.h
llvm::SetVector::getArrayRef
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
llvm::DILabel::getName
StringRef getName() const
Definition: DebugInfoMetadata.h:3230
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::BranchProbability::getZero
static BranchProbability getZero()
Definition: BranchProbability.h:49
Module.h
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1470
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:402
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
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:891
STLExtras.h
llvm::DIBuilder::createSubroutineType
DISubroutineType * createSubroutineType(DITypeRefArray ParameterTypes, DINode::DIFlags Flags=DINode::FlagZero, unsigned CC=0)
Create subroutine type.
Definition: DIBuilder.cpp:546
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:1400
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:1456
llvm::SwitchInst::CaseIteratorImpl
Definition: Instructions.h:3318
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:797
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:187
Instruction.h
CommandLine.h
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
llvm::Instruction::isLifetimeStartOrEnd
bool isLifetimeStartOrEnd() const LLVM_READONLY
Return true if the instruction is a llvm.lifetime.start or llvm.lifetime.end marker.
Definition: Instruction.cpp:748
GlobalValue.h
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2794
llvm::SwitchInst::removeCase
CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
Definition: Instructions.cpp:4533
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3096
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:306
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:1516
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::DISubprogram::DISPFlags
DISPFlags
Debug info subprogram flags.
Definition: DebugInfoMetadata.h:1856
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:731
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:145
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:375
llvm::Function::hasPersonalityFn
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:759
llvm::stripDebugInfo
bool stripDebugInfo(Function &F)
Definition: DebugInfo.cpp:461
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:879
SmallPtrSet.h
llvm::Function::PCT_Real
@ PCT_Real
Definition: Function.h:248
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::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2790
llvm::BranchProbability::getUnknown
static BranchProbability getUnknown()
Definition: BranchProbability.h:51
definedInCaller
static bool definedInCaller(const SetVector< BasicBlock * > &Blocks, Value *V)
definedInCaller - Return true if the specified value is defined in the function being code extracted,...
Definition: CodeExtractor.cpp: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
llvm::StringRef::empty
constexpr bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:134
BasicBlock.h
llvm::cl::opt< bool >
llvm::Function::setSubprogram
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1622
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:180
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::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:819
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
BranchProbabilityInfo.h
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:180
llvm::SwitchInst::getSuccessor
BasicBlock * getSuccessor(unsigned idx) const
Definition: Instructions.h:3599
uint64_t
llvm::SwitchInst::setDefaultDest
void setDefaultDest(BasicBlock *DefaultCase)
Definition: Instructions.h:3488
llvm::Attribute::None
@ None
No attributes have been set.
Definition: Attributes.h:87
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:650
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2833
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2848
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3189
llvm::DenseMap
Definition: DenseMap.h:714
DebugInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:34
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
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:716
DIBuilder.h
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
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
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:3481
llvm::Function::setPersonalityFn
void setPersonalityFn(Constant *Fn)
Definition: Function.cpp:1973
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:2542
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:1100
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
getType
static M68kRelType getType(unsigned Kind, MCSymbolRefExpr::VariantKind &Modifier, bool &IsPCRel)
Definition: M68kELFObjectWriter.cpp:48
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:954
llvm::Function::setEntryCount
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:2032
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:1137
llvm::SwitchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3482
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:1716
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:1883
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:831
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:131
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:2540
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:73
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:805
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
llvm::BranchProbability
Definition: BranchProbability.h:30
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DomTreeNodeBase::begin
iterator begin()
Definition: GenericDomTree.h: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:395
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:432
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h: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:707
llvm::DILabel::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:3231
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::Value::stripInBoundsOffsets
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Definition: Value.cpp:777
Argument.h
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
Attributes.h
llvm::Function::addParamAttr
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
Definition: Function.cpp:567
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::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::MetadataAsValue::get
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:103
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:2740
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
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:1091
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:893
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:3078
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:1854
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::CodeExtractorAnalysisCache
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
eraseDebugIntrinsicsWithNonLocalRefs
static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F)
Erase debug info intrinsics which refer to values in F but aren't in F.
Definition: CodeExtractor.cpp:1510
llvm::Function::getPersonalityFn
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1968
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:722
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::MDBuilder
Definition: MDBuilder.h:36
llvm::GlobalValue::getAddressSpace
unsigned getAddressSpace() const
Definition: Globals.cpp:121
llvm::Function::front
const BasicBlock & front() const
Definition: Function.h:714
llvm::DIVariable::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:2543
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:846
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:373
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:354
User.h
llvm::Value::stripInBoundsConstantOffsets
const Value * stripInBoundsConstantOffsets() const
Strip off pointer casts and all-constant inbounds GEPs.
Definition: Value.cpp:697
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:150
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2814
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
llvm::Function::addFnAttr
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.cpp:539
llvm::Function::setDoesNotReturn
void setDoesNotReturn()
Definition: Function.h:528
llvm::PHINode
Definition: Instructions.h:2698
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:1841
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:2545
llvm::StructType::getElementType
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:328
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
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:1066
Struct
@ Struct
Definition: TargetLibraryInfo.cpp:61
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::StringRef::str
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:221
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1473
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:3186
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:3432
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:3277
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:4518
llvm::cl::desc
Definition: CommandLine.h:413
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:918
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:2544
llvm::logicalview::LVReportKind::Children
@ Children
fixupDebugInfoPostExtraction
static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc, CallInst &TheCall)
Fix up the debug info in the old and new functions by pointing line locations and debug intrinsics to...
Definition: CodeExtractor.cpp:1523
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:100
llvm::DIScope::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:517
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809
AggregateArgsOpt
static cl::opt< bool > AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, cl::desc("Aggregate arguments to code-extracted functions"))
llvm::AssumptionCache::assumptionsFor
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
Definition: AssumptionCache.h:157