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