LLVM  14.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;
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  OldTargets.push_back(NewExitBlock);
438  return CommonExitBlock;
439 }
440 
441 // Find the pair of life time markers for address 'Addr' that are either
442 // defined inside the outline region or can legally be shrinkwrapped into the
443 // outline region. If there are not other untracked uses of the address, return
444 // the pair of markers if found; otherwise return a pair of nullptr.
445 CodeExtractor::LifetimeMarkerInfo
446 CodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
447  Instruction *Addr,
448  BasicBlock *ExitBlock) const {
449  LifetimeMarkerInfo Info;
450 
451  for (User *U : Addr->users()) {
452  IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
453  if (IntrInst) {
454  // We don't model addresses with multiple start/end markers, but the
455  // markers do not need to be in the region.
456  if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
457  if (Info.LifeStart)
458  return {};
459  Info.LifeStart = IntrInst;
460  continue;
461  }
462  if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
463  if (Info.LifeEnd)
464  return {};
465  Info.LifeEnd = IntrInst;
466  continue;
467  }
468  // At this point, permit debug uses outside of the region.
469  // This is fixed in a later call to fixupDebugInfoPostExtraction().
470  if (isa<DbgInfoIntrinsic>(IntrInst))
471  continue;
472  }
473  // Find untracked uses of the address, bail.
474  if (!definedInRegion(Blocks, U))
475  return {};
476  }
477 
478  if (!Info.LifeStart || !Info.LifeEnd)
479  return {};
480 
481  Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart);
482  Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd);
483  // Do legality check.
484  if ((Info.SinkLifeStart || Info.HoistLifeEnd) &&
486  return {};
487 
488  // Check to see if we have a place to do hoisting, if not, bail.
489  if (Info.HoistLifeEnd && !ExitBlock)
490  return {};
491 
492  return Info;
493 }
494 
496  ValueSet &SinkCands, ValueSet &HoistCands,
497  BasicBlock *&ExitBlock) const {
498  Function *Func = (*Blocks.begin())->getParent();
499  ExitBlock = getCommonExitBlock(Blocks);
500 
501  auto moveOrIgnoreLifetimeMarkers =
502  [&](const LifetimeMarkerInfo &LMI) -> bool {
503  if (!LMI.LifeStart)
504  return false;
505  if (LMI.SinkLifeStart) {
506  LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStart
507  << "\n");
508  SinkCands.insert(LMI.LifeStart);
509  }
510  if (LMI.HoistLifeEnd) {
511  LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n");
512  HoistCands.insert(LMI.LifeEnd);
513  }
514  return true;
515  };
516 
517  // Look up allocas in the original function in CodeExtractorAnalysisCache, as
518  // this is much faster than walking all the instructions.
519  for (AllocaInst *AI : CEAC.getAllocas()) {
520  BasicBlock *BB = AI->getParent();
521  if (Blocks.count(BB))
522  continue;
523 
524  // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca,
525  // check whether it is actually still in the original function.
526  Function *AIFunc = BB->getParent();
527  if (AIFunc != Func)
528  continue;
529 
530  LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock);
531  bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);
532  if (Moved) {
533  LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n");
534  SinkCands.insert(AI);
535  continue;
536  }
537 
538  // Find bitcasts in the outlined region that have lifetime marker users
539  // outside that region. Replace the lifetime marker use with an
540  // outside region bitcast to avoid unnecessary alloca/reload instructions
541  // and extra lifetime markers.
542  SmallVector<Instruction *, 2> LifetimeBitcastUsers;
543  for (User *U : AI->users()) {
544  if (!definedInRegion(Blocks, U))
545  continue;
546 
547  if (U->stripInBoundsConstantOffsets() != AI)
548  continue;
549 
550  Instruction *Bitcast = cast<Instruction>(U);
551  for (User *BU : Bitcast->users()) {
552  IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(BU);
553  if (!IntrInst)
554  continue;
555 
556  if (!IntrInst->isLifetimeStartOrEnd())
557  continue;
558 
559  if (definedInRegion(Blocks, IntrInst))
560  continue;
561 
562  LLVM_DEBUG(dbgs() << "Replace use of extracted region bitcast"
563  << *Bitcast << " in out-of-region lifetime marker "
564  << *IntrInst << "\n");
565  LifetimeBitcastUsers.push_back(IntrInst);
566  }
567  }
568 
569  for (Instruction *I : LifetimeBitcastUsers) {
570  Module *M = AIFunc->getParent();
571  LLVMContext &Ctx = M->getContext();
572  auto *Int8PtrTy = Type::getInt8PtrTy(Ctx);
573  CastInst *CastI =
574  CastInst::CreatePointerCast(AI, Int8PtrTy, "lt.cast", I);
575  I->replaceUsesOfWith(I->getOperand(1), CastI);
576  }
577 
578  // Follow any bitcasts.
580  SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo;
581  for (User *U : AI->users()) {
582  if (U->stripInBoundsConstantOffsets() == AI) {
583  Instruction *Bitcast = cast<Instruction>(U);
584  LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock);
585  if (LMI.LifeStart) {
586  Bitcasts.push_back(Bitcast);
587  BitcastLifetimeInfo.push_back(LMI);
588  continue;
589  }
590  }
591 
592  // Found unknown use of AI.
593  if (!definedInRegion(Blocks, U)) {
594  Bitcasts.clear();
595  break;
596  }
597  }
598 
599  // Either no bitcasts reference the alloca or there are unknown uses.
600  if (Bitcasts.empty())
601  continue;
602 
603  LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n");
604  SinkCands.insert(AI);
605  for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) {
606  Instruction *BitcastAddr = Bitcasts[I];
607  const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I];
608  assert(LMI.LifeStart &&
609  "Unsafe to sink bitcast without lifetime markers");
610  moveOrIgnoreLifetimeMarkers(LMI);
611  if (!definedInRegion(Blocks, BitcastAddr)) {
612  LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddr
613  << "\n");
614  SinkCands.insert(BitcastAddr);
615  }
616  }
617  }
618 }
619 
621  if (Blocks.empty())
622  return false;
623  BasicBlock *Header = *Blocks.begin();
624  Function *F = Header->getParent();
625 
626  // For functions with varargs, check that varargs handling is only done in the
627  // outlined function, i.e vastart and vaend are only used in outlined blocks.
628  if (AllowVarArgs && F->getFunctionType()->isVarArg()) {
629  auto containsVarArgIntrinsic = [](const Instruction &I) {
630  if (const CallInst *CI = dyn_cast<CallInst>(&I))
631  if (const Function *Callee = CI->getCalledFunction())
632  return Callee->getIntrinsicID() == Intrinsic::vastart ||
633  Callee->getIntrinsicID() == Intrinsic::vaend;
634  return false;
635  };
636 
637  for (auto &BB : *F) {
638  if (Blocks.count(&BB))
639  continue;
640  if (llvm::any_of(BB, containsVarArgIntrinsic))
641  return false;
642  }
643  }
644  return true;
645 }
646 
648  const ValueSet &SinkCands) const {
649  for (BasicBlock *BB : Blocks) {
650  // If a used value is defined outside the region, it's an input. If an
651  // instruction is used outside the region, it's an output.
652  for (Instruction &II : *BB) {
653  for (auto &OI : II.operands()) {
654  Value *V = OI;
655  if (!SinkCands.count(V) && definedInCaller(Blocks, V))
656  Inputs.insert(V);
657  }
658 
659  for (User *U : II.users())
660  if (!definedInRegion(Blocks, U)) {
661  Outputs.insert(&II);
662  break;
663  }
664  }
665  }
666 }
667 
668 /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside
669 /// of the region, we need to split the entry block of the region so that the
670 /// PHI node is easier to deal with.
671 void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {
672  unsigned NumPredsFromRegion = 0;
673  unsigned NumPredsOutsideRegion = 0;
674 
675  if (Header != &Header->getParent()->getEntryBlock()) {
676  PHINode *PN = dyn_cast<PHINode>(Header->begin());
677  if (!PN) return; // No PHI nodes.
678 
679  // If the header node contains any PHI nodes, check to see if there is more
680  // than one entry from outside the region. If so, we need to sever the
681  // header block into two.
682  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
683  if (Blocks.count(PN->getIncomingBlock(i)))
684  ++NumPredsFromRegion;
685  else
686  ++NumPredsOutsideRegion;
687 
688  // If there is one (or fewer) predecessor from outside the region, we don't
689  // need to do anything special.
690  if (NumPredsOutsideRegion <= 1) return;
691  }
692 
693  // Otherwise, we need to split the header block into two pieces: one
694  // containing PHI nodes merging values from outside of the region, and a
695  // second that contains all of the code for the block and merges back any
696  // incoming values from inside of the region.
697  BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
698 
699  // We only want to code extract the second block now, and it becomes the new
700  // header of the region.
701  BasicBlock *OldPred = Header;
702  Blocks.remove(OldPred);
703  Blocks.insert(NewBB);
704  Header = NewBB;
705 
706  // Okay, now we need to adjust the PHI nodes and any branches from within the
707  // region to go to the new header block instead of the old header block.
708  if (NumPredsFromRegion) {
709  PHINode *PN = cast<PHINode>(OldPred->begin());
710  // Loop over all of the predecessors of OldPred that are in the region,
711  // changing them to branch to NewBB instead.
712  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
713  if (Blocks.count(PN->getIncomingBlock(i))) {
715  TI->replaceUsesOfWith(OldPred, NewBB);
716  }
717 
718  // Okay, everything within the region is now branching to the right block, we
719  // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
720  BasicBlock::iterator AfterPHIs;
721  for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
722  PHINode *PN = cast<PHINode>(AfterPHIs);
723  // Create a new PHI node in the new region, which has an incoming value
724  // from OldPred of PN.
725  PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
726  PN->getName() + ".ce", &NewBB->front());
727  PN->replaceAllUsesWith(NewPN);
728  NewPN->addIncoming(PN, OldPred);
729 
730  // Loop over all of the incoming value in PN, moving them to NewPN if they
731  // are from the extracted region.
732  for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
733  if (Blocks.count(PN->getIncomingBlock(i))) {
734  NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
735  PN->removeIncomingValue(i);
736  --i;
737  }
738  }
739  }
740  }
741 }
742 
743 /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
744 /// outlined region, we split these PHIs on two: one with inputs from region
745 /// and other with remaining incoming blocks; then first PHIs are placed in
746 /// outlined region.
747 void CodeExtractor::severSplitPHINodesOfExits(
748  const SmallPtrSetImpl<BasicBlock *> &Exits) {
749  for (BasicBlock *ExitBB : Exits) {
750  BasicBlock *NewBB = nullptr;
751 
752  for (PHINode &PN : ExitBB->phis()) {
753  // Find all incoming values from the outlining region.
754  SmallVector<unsigned, 2> IncomingVals;
755  for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
756  if (Blocks.count(PN.getIncomingBlock(i)))
757  IncomingVals.push_back(i);
758 
759  // Do not process PHI if there is one (or fewer) predecessor from region.
760  // If PHI has exactly one predecessor from region, only this one incoming
761  // will be replaced on codeRepl block, so it should be safe to skip PHI.
762  if (IncomingVals.size() <= 1)
763  continue;
764 
765  // Create block for new PHIs and add it to the list of outlined if it
766  // wasn't done before.
767  if (!NewBB) {
768  NewBB = BasicBlock::Create(ExitBB->getContext(),
769  ExitBB->getName() + ".split",
770  ExitBB->getParent(), ExitBB);
772  for (BasicBlock *PredBB : Preds)
773  if (Blocks.count(PredBB))
774  PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
775  BranchInst::Create(ExitBB, NewBB);
776  Blocks.insert(NewBB);
777  }
778 
779  // Split this PHI.
780  PHINode *NewPN =
781  PHINode::Create(PN.getType(), IncomingVals.size(),
782  PN.getName() + ".ce", NewBB->getFirstNonPHI());
783  for (unsigned i : IncomingVals)
785  for (unsigned i : reverse(IncomingVals))
786  PN.removeIncomingValue(i, false);
787  PN.addIncoming(NewPN, NewBB);
788  }
789  }
790 }
791 
792 void CodeExtractor::splitReturnBlocks() {
793  for (BasicBlock *Block : Blocks)
794  if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
795  BasicBlock *New =
796  Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
797  if (DT) {
798  // Old dominates New. New node dominates all other nodes dominated
799  // by Old.
800  DomTreeNode *OldNode = DT->getNode(Block);
801  SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
802  OldNode->end());
803 
804  DomTreeNode *NewNode = DT->addNewBlock(New, Block);
805 
806  for (DomTreeNode *I : Children)
807  DT->changeImmediateDominator(I, NewNode);
808  }
809  }
810 }
811 
812 /// constructFunction - make a function based on inputs and outputs, as follows:
813 /// f(in0, ..., inN, out0, ..., outN)
814 Function *CodeExtractor::constructFunction(const ValueSet &inputs,
815  const ValueSet &outputs,
816  BasicBlock *header,
817  BasicBlock *newRootNode,
818  BasicBlock *newHeader,
819  Function *oldFunction,
820  Module *M) {
821  LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
822  LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
823 
824  // This function returns unsigned, outputs will go back by reference.
825  switch (NumExitBlocks) {
826  case 0:
827  case 1: RetTy = Type::getVoidTy(header->getContext()); break;
828  case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
829  default: RetTy = Type::getInt16Ty(header->getContext()); break;
830  }
831 
832  std::vector<Type *> paramTy;
833 
834  // Add the types of the input values to the function's argument list
835  for (Value *value : inputs) {
836  LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
837  paramTy.push_back(value->getType());
838  }
839 
840  // Add the types of the output values to the function's argument list.
841  for (Value *output : outputs) {
842  LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
843  if (AggregateArgs)
844  paramTy.push_back(output->getType());
845  else
846  paramTy.push_back(PointerType::getUnqual(output->getType()));
847  }
848 
849  LLVM_DEBUG({
850  dbgs() << "Function type: " << *RetTy << " f(";
851  for (Type *i : paramTy)
852  dbgs() << *i << ", ";
853  dbgs() << ")\n";
854  });
855 
856  StructType *StructTy = nullptr;
857  if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
858  StructTy = StructType::get(M->getContext(), paramTy);
859  paramTy.clear();
860  paramTy.push_back(PointerType::getUnqual(StructTy));
861  }
862  FunctionType *funcType =
863  FunctionType::get(RetTy, paramTy,
864  AllowVarArgs && oldFunction->isVarArg());
865 
866  std::string SuffixToUse =
867  Suffix.empty()
868  ? (header->getName().empty() ? "extracted" : header->getName().str())
869  : Suffix;
870  // Create the new function
871  Function *newFunction = Function::Create(
872  funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
873  oldFunction->getName() + "." + SuffixToUse, M);
874  // If the old function is no-throw, so is the new one.
875  if (oldFunction->doesNotThrow())
876  newFunction->setDoesNotThrow();
877 
878  // Inherit the uwtable attribute if we need to.
879  if (oldFunction->hasUWTable())
880  newFunction->setHasUWTable();
881 
882  // Inherit all of the target dependent attributes and white-listed
883  // target independent attributes.
884  // (e.g. If the extracted region contains a call to an x86.sse
885  // instruction we need to make sure that the extracted region has the
886  // "target-features" attribute allowing it to be lowered.
887  // FIXME: This should be changed to check to see if a specific
888  // attribute can not be inherited.
889  for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) {
890  if (Attr.isStringAttribute()) {
891  if (Attr.getKindAsString() == "thunk")
892  continue;
893  } else
894  switch (Attr.getKindAsEnum()) {
895  // Those attributes cannot be propagated safely. Explicitly list them
896  // here so we get a warning if new attributes are added. This list also
897  // includes non-function attributes.
898  case Attribute::Alignment:
899  case Attribute::AllocSize:
900  case Attribute::ArgMemOnly:
901  case Attribute::Builtin:
902  case Attribute::ByVal:
904  case Attribute::Dereferenceable:
905  case Attribute::DereferenceableOrNull:
906  case Attribute::ElementType:
907  case Attribute::InAlloca:
908  case Attribute::InReg:
909  case Attribute::InaccessibleMemOnly:
910  case Attribute::InaccessibleMemOrArgMemOnly:
912  case Attribute::Naked:
913  case Attribute::Nest:
914  case Attribute::NoAlias:
915  case Attribute::NoBuiltin:
916  case Attribute::NoCapture:
917  case Attribute::NoMerge:
918  case Attribute::NoReturn:
919  case Attribute::NoSync:
920  case Attribute::NoUndef:
921  case Attribute::None:
922  case Attribute::NonNull:
923  case Attribute::Preallocated:
924  case Attribute::ReadNone:
925  case Attribute::ReadOnly:
926  case Attribute::Returned:
927  case Attribute::ReturnsTwice:
928  case Attribute::SExt:
929  case Attribute::Speculatable:
930  case Attribute::StackAlignment:
931  case Attribute::StructRet:
932  case Attribute::SwiftError:
933  case Attribute::SwiftSelf:
934  case Attribute::SwiftAsync:
935  case Attribute::WillReturn:
936  case Attribute::WriteOnly:
937  case Attribute::ZExt:
938  case Attribute::ImmArg:
939  case Attribute::ByRef:
941  case Attribute::EmptyKey:
943  continue;
944  // Those attributes should be safe to propagate to the extracted function.
945  case Attribute::AlwaysInline:
946  case Attribute::Cold:
947  case Attribute::DisableSanitizerInstrumentation:
948  case Attribute::Hot:
949  case Attribute::NoRecurse:
950  case Attribute::InlineHint:
951  case Attribute::MinSize:
952  case Attribute::NoCallback:
953  case Attribute::NoDuplicate:
954  case Attribute::NoFree:
955  case Attribute::NoImplicitFloat:
956  case Attribute::NoInline:
957  case Attribute::NonLazyBind:
958  case Attribute::NoRedZone:
959  case Attribute::NoUnwind:
960  case Attribute::NoSanitizeCoverage:
961  case Attribute::NullPointerIsValid:
962  case Attribute::OptForFuzzing:
963  case Attribute::OptimizeNone:
964  case Attribute::OptimizeForSize:
965  case Attribute::SafeStack:
966  case Attribute::ShadowCallStack:
967  case Attribute::SanitizeAddress:
968  case Attribute::SanitizeMemory:
969  case Attribute::SanitizeThread:
970  case Attribute::SanitizeHWAddress:
971  case Attribute::SanitizeMemTag:
972  case Attribute::SpeculativeLoadHardening:
973  case Attribute::StackProtect:
974  case Attribute::StackProtectReq:
975  case Attribute::StackProtectStrong:
976  case Attribute::StrictFP:
977  case Attribute::UWTable:
978  case Attribute::VScaleRange:
979  case Attribute::NoCfCheck:
980  case Attribute::MustProgress:
981  case Attribute::NoProfile:
982  break;
983  }
984 
985  newFunction->addFnAttr(Attr);
986  }
987  newFunction->getBasicBlockList().push_back(newRootNode);
988 
989  // Create an iterator to name all of the arguments we inserted.
990  Function::arg_iterator AI = newFunction->arg_begin();
991 
992  // Rewrite all users of the inputs in the extracted region to use the
993  // arguments (or appropriate addressing into struct) instead.
994  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
995  Value *RewriteVal;
996  if (AggregateArgs) {
997  Value *Idx[2];
999  Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
1000  Instruction *TI = newFunction->begin()->getTerminator();
1002  StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
1003  RewriteVal = new LoadInst(StructTy->getElementType(i), GEP,
1004  "loadgep_" + inputs[i]->getName(), TI);
1005  } else
1006  RewriteVal = &*AI++;
1007 
1008  std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
1009  for (User *use : Users)
1010  if (Instruction *inst = dyn_cast<Instruction>(use))
1011  if (Blocks.count(inst->getParent()))
1012  inst->replaceUsesOfWith(inputs[i], RewriteVal);
1013  }
1014 
1015  // Set names for input and output arguments.
1016  if (!AggregateArgs) {
1017  AI = newFunction->arg_begin();
1018  for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
1019  AI->setName(inputs[i]->getName());
1020  for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
1021  AI->setName(outputs[i]->getName()+".out");
1022  }
1023 
1024  // Rewrite branches to basic blocks outside of the loop to new dummy blocks
1025  // within the new function. This must be done before we lose track of which
1026  // blocks were originally in the code region.
1027  std::vector<User *> Users(header->user_begin(), header->user_end());
1028  for (auto &U : Users)
1029  // The BasicBlock which contains the branch is not in the region
1030  // modify the branch target to a new block
1031  if (Instruction *I = dyn_cast<Instruction>(U))
1032  if (I->isTerminator() && I->getFunction() == oldFunction &&
1033  !Blocks.count(I->getParent()))
1034  I->replaceUsesOfWith(header, newHeader);
1035 
1036  return newFunction;
1037 }
1038 
1039 /// Erase lifetime.start markers which reference inputs to the extraction
1040 /// region, and insert the referenced memory into \p LifetimesStart.
1041 ///
1042 /// The extraction region is defined by a set of blocks (\p Blocks), and a set
1043 /// of allocas which will be moved from the caller function into the extracted
1044 /// function (\p SunkAllocas).
1046  const SetVector<Value *> &SunkAllocas,
1047  SetVector<Value *> &LifetimesStart) {
1048  for (BasicBlock *BB : Blocks) {
1049  for (auto It = BB->begin(), End = BB->end(); It != End;) {
1050  auto *II = dyn_cast<IntrinsicInst>(&*It);
1051  ++It;
1052  if (!II || !II->isLifetimeStartOrEnd())
1053  continue;
1054 
1055  // Get the memory operand of the lifetime marker. If the underlying
1056  // object is a sunk alloca, or is otherwise defined in the extraction
1057  // region, the lifetime marker must not be erased.
1058  Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1059  if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1060  continue;
1061 
1062  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1063  LifetimesStart.insert(Mem);
1064  II->eraseFromParent();
1065  }
1066  }
1067 }
1068 
1069 /// Insert lifetime start/end markers surrounding the call to the new function
1070 /// for objects defined in the caller.
1072  Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1073  CallInst *TheCall) {
1074  LLVMContext &Ctx = M->getContext();
1075  auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
1076  auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1077  Instruction *Term = TheCall->getParent()->getTerminator();
1078 
1079  // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
1080  // needed to satisfy this requirement so they may be reused.
1081  DenseMap<Value *, Value *> Bitcasts;
1082 
1083  // Emit lifetime markers for the pointers given in \p Objects. Insert the
1084  // markers before the call if \p InsertBefore, and after the call otherwise.
1085  auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
1086  bool InsertBefore) {
1087  for (Value *Mem : Objects) {
1088  assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1089  TheCall->getFunction()) &&
1090  "Input memory not defined in original function");
1091  Value *&MemAsI8Ptr = Bitcasts[Mem];
1092  if (!MemAsI8Ptr) {
1093  if (Mem->getType() == Int8PtrTy)
1094  MemAsI8Ptr = Mem;
1095  else
1096  MemAsI8Ptr =
1097  CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
1098  }
1099 
1100  auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
1101  if (InsertBefore)
1102  Marker->insertBefore(TheCall);
1103  else
1104  Marker->insertBefore(Term);
1105  }
1106  };
1107 
1108  if (!LifetimesStart.empty()) {
1109  auto StartFn = llvm::Intrinsic::getDeclaration(
1110  M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
1111  insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
1112  }
1113 
1114  if (!LifetimesEnd.empty()) {
1115  auto EndFn = llvm::Intrinsic::getDeclaration(
1116  M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
1117  insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
1118  }
1119 }
1120 
1121 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
1122 /// the call instruction, splitting any PHI nodes in the header block as
1123 /// necessary.
1124 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1125  BasicBlock *codeReplacer,
1126  ValueSet &inputs,
1127  ValueSet &outputs) {
1128  // Emit a call to the new function, passing in: *pointer to struct (if
1129  // aggregating parameters), or plan inputs and allocated memory for outputs
1130  std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
1131 
1132  Module *M = newFunction->getParent();
1133  LLVMContext &Context = M->getContext();
1134  const DataLayout &DL = M->getDataLayout();
1135  CallInst *call = nullptr;
1136 
1137  // Add inputs as params, or to be filled into the struct
1138  unsigned ArgNo = 0;
1139  SmallVector<unsigned, 1> SwiftErrorArgs;
1140  for (Value *input : inputs) {
1141  if (AggregateArgs)
1142  StructValues.push_back(input);
1143  else {
1144  params.push_back(input);
1145  if (input->isSwiftError())
1146  SwiftErrorArgs.push_back(ArgNo);
1147  }
1148  ++ArgNo;
1149  }
1150 
1151  // Create allocas for the outputs
1152  for (Value *output : outputs) {
1153  if (AggregateArgs) {
1154  StructValues.push_back(output);
1155  } else {
1156  AllocaInst *alloca =
1157  new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1158  nullptr, output->getName() + ".loc",
1159  &codeReplacer->getParent()->front().front());
1160  ReloadOutputs.push_back(alloca);
1161  params.push_back(alloca);
1162  }
1163  }
1164 
1165  StructType *StructArgTy = nullptr;
1166  AllocaInst *Struct = nullptr;
1167  if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
1168  std::vector<Type *> ArgTypes;
1169  for (Value *V : StructValues)
1170  ArgTypes.push_back(V->getType());
1171 
1172  // Allocate a struct at the beginning of this function
1173  StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1174  Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
1175  "structArg",
1176  &codeReplacer->getParent()->front().front());
1177  params.push_back(Struct);
1178 
1179  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
1180  Value *Idx[2];
1184  StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1185  codeReplacer->getInstList().push_back(GEP);
1186  new StoreInst(StructValues[i], GEP, codeReplacer);
1187  }
1188  }
1189 
1190  // Emit the call to the function
1191  call = CallInst::Create(newFunction, params,
1192  NumExitBlocks > 1 ? "targetBlock" : "");
1193  // Add debug location to the new call, if the original function has debug
1194  // info. In that case, the terminator of the entry block of the extracted
1195  // function contains the first debug location of the extracted function,
1196  // set in extractCodeRegion.
1197  if (codeReplacer->getParent()->getSubprogram()) {
1198  if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1199  call->setDebugLoc(DL);
1200  }
1201  codeReplacer->getInstList().push_back(call);
1202 
1203  // Set swifterror parameter attributes.
1204  for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1205  call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1206  newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1207  }
1208 
1209  Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
1210  unsigned FirstOut = inputs.size();
1211  if (!AggregateArgs)
1212  std::advance(OutputArgBegin, inputs.size());
1213 
1214  // Reload the outputs passed in by reference.
1215  for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1216  Value *Output = nullptr;
1217  if (AggregateArgs) {
1218  Value *Idx[2];
1220  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1222  StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1223  codeReplacer->getInstList().push_back(GEP);
1224  Output = GEP;
1225  } else {
1226  Output = ReloadOutputs[i];
1227  }
1228  LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1229  outputs[i]->getName() + ".reload",
1230  codeReplacer);
1231  Reloads.push_back(load);
1232  std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1233  for (unsigned u = 0, e = Users.size(); u != e; ++u) {
1234  Instruction *inst = cast<Instruction>(Users[u]);
1235  if (!Blocks.count(inst->getParent()))
1236  inst->replaceUsesOfWith(outputs[i], load);
1237  }
1238  }
1239 
1240  // Now we can emit a switch statement using the call as a value.
1241  SwitchInst *TheSwitch =
1243  codeReplacer, 0, codeReplacer);
1244 
1245  // Since there may be multiple exits from the original region, make the new
1246  // function return an unsigned, switch on that number. This loop iterates
1247  // over all of the blocks in the extracted region, updating any terminator
1248  // instructions in the to-be-extracted region that branch to blocks that are
1249  // not in the region to be extracted.
1250  std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1251 
1252  // Iterate over the previously collected targets, and create new blocks inside
1253  // the function to branch to.
1254  unsigned switchVal = 0;
1255  for (BasicBlock *OldTarget : OldTargets) {
1256  if (Blocks.count(OldTarget))
1257  continue;
1258  BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1259  if (NewTarget)
1260  continue;
1261 
1262  // If we don't already have an exit stub for this non-extracted
1263  // destination, create one now!
1264  NewTarget = BasicBlock::Create(Context,
1265  OldTarget->getName() + ".exitStub",
1266  newFunction);
1267  unsigned SuccNum = switchVal++;
1268 
1269  Value *brVal = nullptr;
1270  assert(NumExitBlocks < 0xffff && "too many exit blocks for switch");
1271  switch (NumExitBlocks) {
1272  case 0:
1273  case 1: break; // No value needed.
1274  case 2: // Conditional branch, return a bool
1275  brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1276  break;
1277  default:
1278  brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1279  break;
1280  }
1281 
1282  ReturnInst::Create(Context, brVal, NewTarget);
1283 
1284  // Update the switch instruction.
1286  SuccNum),
1287  OldTarget);
1288  }
1289 
1290  for (BasicBlock *Block : Blocks) {
1291  Instruction *TI = Block->getTerminator();
1292  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1293  if (Blocks.count(TI->getSuccessor(i)))
1294  continue;
1295  BasicBlock *OldTarget = TI->getSuccessor(i);
1296  // add a new basic block which returns the appropriate value
1297  BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1298  assert(NewTarget && "Unknown target block!");
1299 
1300  // rewrite the original branch instruction with this new target
1301  TI->setSuccessor(i, NewTarget);
1302  }
1303  }
1304 
1305  // Store the arguments right after the definition of output value.
1306  // This should be proceeded after creating exit stubs to be ensure that invoke
1307  // result restore will be placed in the outlined function.
1308  Function::arg_iterator OAI = OutputArgBegin;
1309  for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1310  auto *OutI = dyn_cast<Instruction>(outputs[i]);
1311  if (!OutI)
1312  continue;
1313 
1314  // Find proper insertion point.
1315  BasicBlock::iterator InsertPt;
1316  // In case OutI is an invoke, we insert the store at the beginning in the
1317  // 'normal destination' BB. Otherwise we insert the store right after OutI.
1318  if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1319  InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1320  else if (auto *Phi = dyn_cast<PHINode>(OutI))
1321  InsertPt = Phi->getParent()->getFirstInsertionPt();
1322  else
1323  InsertPt = std::next(OutI->getIterator());
1324 
1325  Instruction *InsertBefore = &*InsertPt;
1326  assert((InsertBefore->getFunction() == newFunction ||
1327  Blocks.count(InsertBefore->getParent())) &&
1328  "InsertPt should be in new function");
1329  assert(OAI != newFunction->arg_end() &&
1330  "Number of output arguments should match "
1331  "the amount of defined values");
1332  if (AggregateArgs) {
1333  Value *Idx[2];
1335  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1337  StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(),
1338  InsertBefore);
1339  new StoreInst(outputs[i], GEP, InsertBefore);
1340  // Since there should be only one struct argument aggregating
1341  // all the output values, we shouldn't increment OAI, which always
1342  // points to the struct argument, in this case.
1343  } else {
1344  new StoreInst(outputs[i], &*OAI, InsertBefore);
1345  ++OAI;
1346  }
1347  }
1348 
1349  // Now that we've done the deed, simplify the switch instruction.
1350  Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1351  switch (NumExitBlocks) {
1352  case 0:
1353  // There are no successors (the block containing the switch itself), which
1354  // means that previously this was the last part of the function, and hence
1355  // this should be rewritten as a `ret'
1356 
1357  // Check if the function should return a value
1358  if (OldFnRetTy->isVoidTy()) {
1359  ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
1360  } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1361  // return what we have
1362  ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1363  } else {
1364  // Otherwise we must have code extracted an unwind or something, just
1365  // return whatever we want.
1367  Constant::getNullValue(OldFnRetTy), TheSwitch);
1368  }
1369 
1370  TheSwitch->eraseFromParent();
1371  break;
1372  case 1:
1373  // Only a single destination, change the switch into an unconditional
1374  // branch.
1375  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1376  TheSwitch->eraseFromParent();
1377  break;
1378  case 2:
1379  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1380  call, TheSwitch);
1381  TheSwitch->eraseFromParent();
1382  break;
1383  default:
1384  // Otherwise, make the default destination of the switch instruction be one
1385  // of the other successors.
1386  TheSwitch->setCondition(call);
1387  TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1388  // Remove redundant case
1389  TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1390  break;
1391  }
1392 
1393  // Insert lifetime markers around the reloads of any output values. The
1394  // allocas output values are stored in are only in-use in the codeRepl block.
1395  insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1396 
1397  return call;
1398 }
1399 
1400 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1401  Function *oldFunc = (*Blocks.begin())->getParent();
1402  Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1403  Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1404 
1405  auto newFuncIt = newFunction->front().getIterator();
1406  for (BasicBlock *Block : Blocks) {
1407  // Delete the basic block from the old function, and the list of blocks
1408  oldBlocks.remove(Block);
1409 
1410  // Insert this basic block into the new function
1411  // Insert the original blocks after the entry block created
1412  // for the new function. The entry block may be followed
1413  // by a set of exit blocks at this point, but these exit
1414  // blocks better be placed at the end of the new function.
1415  newFuncIt = newBlocks.insertAfter(newFuncIt, Block);
1416  }
1417 }
1418 
1419 void CodeExtractor::calculateNewCallTerminatorWeights(
1420  BasicBlock *CodeReplacer,
1422  BranchProbabilityInfo *BPI) {
1423  using Distribution = BlockFrequencyInfoImplBase::Distribution;
1424  using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1425 
1426  // Update the branch weights for the exit block.
1427  Instruction *TI = CodeReplacer->getTerminator();
1428  SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1429 
1430  // Block Frequency distribution with dummy node.
1431  Distribution BranchDist;
1432 
1433  SmallVector<BranchProbability, 4> EdgeProbabilities(
1435 
1436  // Add each of the frequencies of the successors.
1437  for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1438  BlockNode ExitNode(i);
1439  uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1440  if (ExitFreq != 0)
1441  BranchDist.addExit(ExitNode, ExitFreq);
1442  else
1443  EdgeProbabilities[i] = BranchProbability::getZero();
1444  }
1445 
1446  // Check for no total weight.
1447  if (BranchDist.Total == 0) {
1448  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1449  return;
1450  }
1451 
1452  // Normalize the distribution so that they can fit in unsigned.
1453  BranchDist.normalize();
1454 
1455  // Create normalized branch weights and set the metadata.
1456  for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1457  const auto &Weight = BranchDist.Weights[I];
1458 
1459  // Get the weight and update the current BFI.
1460  BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1461  BranchProbability BP(Weight.Amount, BranchDist.Total);
1462  EdgeProbabilities[Weight.TargetNode.Index] = BP;
1463  }
1464  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1465  TI->setMetadata(
1466  LLVMContext::MD_prof,
1467  MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1468 }
1469 
1470 /// Erase debug info intrinsics which refer to values in \p F but aren't in
1471 /// \p F.
1473  for (Instruction &I : instructions(F)) {
1475  findDbgUsers(DbgUsers, &I);
1476  for (DbgVariableIntrinsic *DVI : DbgUsers)
1477  if (DVI->getFunction() != &F)
1478  DVI->eraseFromParent();
1479  }
1480 }
1481 
1482 /// Fix up the debug info in the old and new functions by pointing line
1483 /// locations and debug intrinsics to the new subprogram scope, and by deleting
1484 /// intrinsics which point to values outside of the new function.
1485 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1486  CallInst &TheCall) {
1487  DISubprogram *OldSP = OldFunc.getSubprogram();
1488  LLVMContext &Ctx = OldFunc.getContext();
1489 
1490  if (!OldSP) {
1491  // Erase any debug info the new function contains.
1492  stripDebugInfo(NewFunc);
1493  // Make sure the old function doesn't contain any non-local metadata refs.
1495  return;
1496  }
1497 
1498  // Create a subprogram for the new function. Leave out a description of the
1499  // function arguments, as the parameters don't correspond to anything at the
1500  // source level.
1501  assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1502  DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,
1503  OldSP->getUnit());
1504  auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
1505  DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1506  DISubprogram::SPFlagOptimized |
1507  DISubprogram::SPFlagLocalToUnit;
1508  auto NewSP = DIB.createFunction(
1509  OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1510  /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1511  NewFunc.setSubprogram(NewSP);
1512 
1513  // Debug intrinsics in the new function need to be updated in one of two
1514  // ways:
1515  // 1) They need to be deleted, because they describe a value in the old
1516  // function.
1517  // 2) They need to point to fresh metadata, e.g. because they currently
1518  // point to a variable in the wrong scope.
1519  SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1520  SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1521  for (Instruction &I : instructions(NewFunc)) {
1522  auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1523  if (!DII)
1524  continue;
1525 
1526  // Point the intrinsic to a fresh label within the new function.
1527  if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1528  DILabel *OldLabel = DLI->getLabel();
1529  DINode *&NewLabel = RemappedMetadata[OldLabel];
1530  if (!NewLabel)
1531  NewLabel = DILabel::get(Ctx, NewSP, OldLabel->getName(),
1532  OldLabel->getFile(), OldLabel->getLine());
1533  DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
1534  continue;
1535  }
1536 
1537  auto IsInvalidLocation = [&NewFunc](Value *Location) {
1538  // Location is invalid if it isn't a constant or an instruction, or is an
1539  // instruction but isn't in the new function.
1540  if (!Location ||
1541  (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1542  return true;
1543  Instruction *LocationInst = dyn_cast<Instruction>(Location);
1544  return LocationInst && LocationInst->getFunction() != &NewFunc;
1545  };
1546 
1547  auto *DVI = cast<DbgVariableIntrinsic>(DII);
1548  // If any of the used locations are invalid, delete the intrinsic.
1549  if (any_of(DVI->location_ops(), IsInvalidLocation)) {
1550  DebugIntrinsicsToDelete.push_back(DVI);
1551  continue;
1552  }
1553 
1554  // Point the intrinsic to a fresh variable within the new function.
1555  DILocalVariable *OldVar = DVI->getVariable();
1556  DINode *&NewVar = RemappedMetadata[OldVar];
1557  if (!NewVar)
1558  NewVar = DIB.createAutoVariable(
1559  NewSP, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1560  OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1561  OldVar->getAlignInBits());
1562  DVI->setVariable(cast<DILocalVariable>(NewVar));
1563  }
1564  for (auto *DII : DebugIntrinsicsToDelete)
1565  DII->eraseFromParent();
1566  DIB.finalizeSubprogram(NewSP);
1567 
1568  // Fix up the scope information attached to the line locations in the new
1569  // function.
1570  for (Instruction &I : instructions(NewFunc)) {
1571  if (const DebugLoc &DL = I.getDebugLoc())
1572  I.setDebugLoc(DILocation::get(Ctx, DL.getLine(), DL.getCol(), NewSP));
1573 
1574  // Loop info metadata may contain line locations. Fix them up.
1575  auto updateLoopInfoLoc = [&Ctx, NewSP](Metadata *MD) -> Metadata * {
1576  if (auto *Loc = dyn_cast_or_null<DILocation>(MD))
1577  return DILocation::get(Ctx, Loc->getLine(), Loc->getColumn(), NewSP,
1578  nullptr);
1579  return MD;
1580  };
1581  updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1582  }
1583  if (!TheCall.getDebugLoc())
1584  TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP));
1585 
1587 }
1588 
1589 Function *
1591  ValueSet Inputs, Outputs;
1592  return extractCodeRegion(CEAC, Inputs, Outputs);
1593 }
1594 
1595 Function *
1597  ValueSet &inputs, ValueSet &outputs) {
1598  if (!isEligible())
1599  return nullptr;
1600 
1601  // Assumption: this is a single-entry code region, and the header is the first
1602  // block in the region.
1603  BasicBlock *header = *Blocks.begin();
1604  Function *oldFunction = header->getParent();
1605 
1606  // Calculate the entry frequency of the new function before we change the root
1607  // block.
1608  BlockFrequency EntryFreq;
1609  if (BFI) {
1610  assert(BPI && "Both BPI and BFI are required to preserve profile info");
1611  for (BasicBlock *Pred : predecessors(header)) {
1612  if (Blocks.count(Pred))
1613  continue;
1614  EntryFreq +=
1615  BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1616  }
1617  }
1618 
1619  // Remove @llvm.assume calls that will be moved to the new function from the
1620  // old function's assumption cache.
1621  for (BasicBlock *Block : Blocks) {
1622  for (auto It = Block->begin(), End = Block->end(); It != End;) {
1623  Instruction *I = &*It;
1624  ++It;
1625 
1626  if (auto *AI = dyn_cast<AssumeInst>(I)) {
1627  if (AC)
1628  AC->unregisterAssumption(AI);
1629  AI->eraseFromParent();
1630  }
1631  }
1632  }
1633 
1634  // If we have any return instructions in the region, split those blocks so
1635  // that the return is not in the region.
1636  splitReturnBlocks();
1637 
1638  // Calculate the exit blocks for the extracted region and the total exit
1639  // weights for each of those blocks.
1641  SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1642  for (BasicBlock *Block : Blocks) {
1643  for (BasicBlock *Succ : successors(Block)) {
1644  if (!Blocks.count(Succ)) {
1645  // Update the branch weight for this successor.
1646  if (BFI) {
1647  BlockFrequency &BF = ExitWeights[Succ];
1648  BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ);
1649  }
1650  ExitBlocks.insert(Succ);
1651  }
1652  }
1653  }
1654  NumExitBlocks = ExitBlocks.size();
1655 
1656  for (BasicBlock *Block : Blocks) {
1657  Instruction *TI = Block->getTerminator();
1658  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1659  if (Blocks.count(TI->getSuccessor(i)))
1660  continue;
1661  BasicBlock *OldTarget = TI->getSuccessor(i);
1662  OldTargets.push_back(OldTarget);
1663  }
1664  }
1665 
1666  // If we have to split PHI nodes of the entry or exit blocks, do so now.
1667  severSplitPHINodesOfEntry(header);
1668  severSplitPHINodesOfExits(ExitBlocks);
1669 
1670  // This takes place of the original loop
1671  BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1672  "codeRepl", oldFunction,
1673  header);
1674 
1675  // The new function needs a root node because other nodes can branch to the
1676  // head of the region, but the entry node of a function cannot have preds.
1677  BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1678  "newFuncRoot");
1679  auto *BranchI = BranchInst::Create(header);
1680  // If the original function has debug info, we have to add a debug location
1681  // to the new branch instruction from the artificial entry block.
1682  // We use the debug location of the first instruction in the extracted
1683  // blocks, as there is no other equivalent line in the source code.
1684  if (oldFunction->getSubprogram()) {
1685  any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1686  return any_of(*BB, [&BranchI](const Instruction &I) {
1687  if (!I.getDebugLoc())
1688  return false;
1689  BranchI->setDebugLoc(I.getDebugLoc());
1690  return true;
1691  });
1692  });
1693  }
1694  newFuncRoot->getInstList().push_back(BranchI);
1695 
1696  ValueSet SinkingCands, HoistingCands;
1697  BasicBlock *CommonExit = nullptr;
1698  findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1699  assert(HoistingCands.empty() || CommonExit);
1700 
1701  // Find inputs to, outputs from the code region.
1702  findInputsOutputs(inputs, outputs, SinkingCands);
1703 
1704  // Now sink all instructions which only have non-phi uses inside the region.
1705  // Group the allocas at the start of the block, so that any bitcast uses of
1706  // the allocas are well-defined.
1707  AllocaInst *FirstSunkAlloca = nullptr;
1708  for (auto *II : SinkingCands) {
1709  if (auto *AI = dyn_cast<AllocaInst>(II)) {
1710  AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1711  if (!FirstSunkAlloca)
1712  FirstSunkAlloca = AI;
1713  }
1714  }
1715  assert((SinkingCands.empty() || FirstSunkAlloca) &&
1716  "Did not expect a sink candidate without any allocas");
1717  for (auto *II : SinkingCands) {
1718  if (!isa<AllocaInst>(II)) {
1719  cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1720  }
1721  }
1722 
1723  if (!HoistingCands.empty()) {
1724  auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1725  Instruction *TI = HoistToBlock->getTerminator();
1726  for (auto *II : HoistingCands)
1727  cast<Instruction>(II)->moveBefore(TI);
1728  }
1729 
1730  // Collect objects which are inputs to the extraction region and also
1731  // referenced by lifetime start markers within it. The effects of these
1732  // markers must be replicated in the calling function to prevent the stack
1733  // coloring pass from merging slots which store input objects.
1734  ValueSet LifetimesStart;
1735  eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1736 
1737  // Construct new function based on inputs/outputs & add allocas for all defs.
1738  Function *newFunction =
1739  constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1740  oldFunction, oldFunction->getParent());
1741 
1742  // Update the entry count of the function.
1743  if (BFI) {
1744  auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1745  if (Count.hasValue())
1746  newFunction->setEntryCount(
1747  ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1748  BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1749  }
1750 
1751  CallInst *TheCall =
1752  emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1753 
1754  moveCodeToFunction(newFunction);
1755 
1756  // Replicate the effects of any lifetime start/end markers which referenced
1757  // input objects in the extraction region by placing markers around the call.
1759  oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1760 
1761  // Propagate personality info to the new function if there is one.
1762  if (oldFunction->hasPersonalityFn())
1763  newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1764 
1765  // Update the branch weights for the exit block.
1766  if (BFI && NumExitBlocks > 1)
1767  calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1768 
1769  // Loop over all of the PHI nodes in the header and exit blocks, and change
1770  // any references to the old incoming edge to be the new incoming edge.
1771  for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1772  PHINode *PN = cast<PHINode>(I);
1773  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1774  if (!Blocks.count(PN->getIncomingBlock(i)))
1775  PN->setIncomingBlock(i, newFuncRoot);
1776  }
1777 
1778  for (BasicBlock *ExitBB : ExitBlocks)
1779  for (PHINode &PN : ExitBB->phis()) {
1780  Value *IncomingCodeReplacerVal = nullptr;
1781  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1782  // Ignore incoming values from outside of the extracted region.
1783  if (!Blocks.count(PN.getIncomingBlock(i)))
1784  continue;
1785 
1786  // Ensure that there is only one incoming value from codeReplacer.
1787  if (!IncomingCodeReplacerVal) {
1788  PN.setIncomingBlock(i, codeReplacer);
1789  IncomingCodeReplacerVal = PN.getIncomingValue(i);
1790  } else
1791  assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1792  "PHI has two incompatbile incoming values from codeRepl");
1793  }
1794  }
1795 
1796  fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1797 
1798  // Mark the new function `noreturn` if applicable. Terminators which resume
1799  // exception propagation are treated as returning instructions. This is to
1800  // avoid inserting traps after calls to outlined functions which unwind.
1801  bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1802  const Instruction *Term = BB.getTerminator();
1803  return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1804  });
1805  if (doesNotReturn)
1806  newFunction->setDoesNotReturn();
1807 
1808  LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1809  newFunction->dump();
1810  report_fatal_error("verification of newFunction failed!");
1811  });
1812  LLVM_DEBUG(if (verifyFunction(*oldFunction))
1813  report_fatal_error("verification of oldFunction failed!"));
1814  LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1815  report_fatal_error("Stale Asumption cache for old Function!"));
1816  return newFunction;
1817 }
1818 
1820  const Function &NewFunc,
1821  AssumptionCache *AC) {
1822  for (auto AssumeVH : AC->assumptions()) {
1823  auto *I = dyn_cast_or_null<CallInst>(AssumeVH);
1824  if (!I)
1825  continue;
1826 
1827  // There shouldn't be any llvm.assume intrinsics in the new function.
1828  if (I->getFunction() != &OldFunc)
1829  return true;
1830 
1831  // There shouldn't be any stale affected values in the assumption cache
1832  // that were previously in the old function, but that have now been moved
1833  // to the new function.
1834  for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1835  auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1836  if (!AffectedCI)
1837  continue;
1838  if (AffectedCI->getFunction() != &OldFunc)
1839  return true;
1840  auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1841  if (AssumedInst->getFunction() != &OldFunc)
1842  return true;
1843  }
1844  }
1845  return false;
1846 }
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:76
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:3231
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:200
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:657
llvm::StringRef::empty
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:153
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:1565
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2986
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:370
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:1379
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:255
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:710
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:495
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:255
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:4759
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:1590
llvm::Attribute::TombstoneKey
@ TombstoneKey
Use as Tombstone key for DenseMap of AttrKind.
Definition: Attributes.h:78
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:3402
llvm::LegacyLegalizeActions::Bitcast
@ Bitcast
Perform the operation on a different, but equivalently sized type.
Definition: LegacyLegalizerInfo.h:54
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1541
ErrorHandling.h
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:717
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::findDbgUsers
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:102
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:113
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:325
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:77
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:5815
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::Function::setDoesNotThrow
void setDoesNotThrow()
Definition: Function.h:569
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:321
BlockFrequency.h
llvm::SetVector::getArrayRef
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
llvm::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:3232
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::BranchProbability::getZero
static BranchProbability getZero()
Definition: BranchProbability.h:49
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1391
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:381
llvm::CallingConv::Cold
@ Cold
Definition: CallingConv.h:48
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:182
llvm::Value::user_begin
user_iterator user_begin()
Definition: Value.h:398
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:517
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:267
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::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1208
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:1336
llvm::SwitchInst::CaseIteratorImpl
Definition: Instructions.h:3253
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:768
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::CodeExtractorAnalysisCache::CodeExtractorAnalysisCache
CodeExtractorAnalysisCache(Function &F)
Definition: CodeExtractor.cpp:311
Instruction.h
CommandLine.h
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1335
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:638
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:2729
llvm::SwitchInst::removeCase
CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
Definition: Instructions.cpp:4199
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3097
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
Intrinsics.h
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::BlockFrequencyInfo::getProfileCountFromFreq
Optional< uint64_t > getProfileCountFromFreq(uint64_t Freq) const
Returns the estimated profile count of Freq.
Definition: BlockFrequencyInfo.cpp:218
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:1518
llvm::DISubprogram::DISPFlags
DISPFlags
Debug info subprogram flags.
Definition: DebugInfoMetadata.h:1835
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:229
false
Definition: StackSlotColoring.cpp:142
llvm::DIBuilder::createFunction
DISubprogram * createFunction(DIScope *Scope, StringRef Name, StringRef LinkageName, DIFile *File, unsigned LineNo, DISubroutineType *Ty, unsigned ScopeLine, DINode::DIFlags Flags=DINode::FlagZero, DISubprogram::DISPFlags SPFlags=DISubprogram::SPFlagZero, DITemplateParameterArray TParams=nullptr, DISubprogram *Decl=nullptr, DITypeArray ThrownTypes=nullptr, DINodeArray Annotations=nullptr)
Create a new descriptor for the specified subprogram.
Definition: DIBuilder.cpp:825
llvm::Function::arg_end
arg_iterator arg_end()
Definition: Function.h:757
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:647
llvm::Instruction
Definition: Instruction.h:45
MDBuilder.h
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::Function::hasPersonalityFn
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:785
llvm::stripDebugInfo
bool stripDebugInfo(Function &F)
Definition: DebugInfo.cpp:441
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:900
SmallPtrSet.h
llvm::Function::PCT_Real
@ PCT_Real
Definition: Function.h:249
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
PatternMatch.h
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp: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::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:245
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:706
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
llvm::None
const NoneType None
Definition: None.h:23
llvm::BranchProbability::getUnknown
static BranchProbability getUnknown()
Definition: BranchProbability.h:51
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:384
Type.h
BranchProbability.h
CFG.h
LoopInfo.h
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:326
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:406
BasicBlock.h
llvm::cl::opt< bool >
llvm::Function::setSubprogram
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1537
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:304
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:181
llvm::PointerType::getUnqual
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
Definition: DerivedTypes.h:651
llvm::SwitchInst::getSuccessor
BasicBlock * getSuccessor(unsigned idx) const
Definition: Instructions.h:3538
uint64_t
llvm::SwitchInst::setDefaultDest
void setDefaultDest(BasicBlock *DefaultCase)
Definition: Instructions.h:3424
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:2768
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
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:3124
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:928
call
S is passed via registers r2 But gcc stores them to the and then reload them to and r3 before issuing the call(r0 contains the address of the format string)
Definition: README.txt:190
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
DIBuilder.h
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:138
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
load
LLVM currently emits rax rax movq rax rax ret It could narrow the loads and stores to emit rax rax movq rax rax ret The trouble is that there is a TokenFactor between the store and the load
Definition: README.txt:1531
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
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:138
llvm::SwitchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3417
llvm::Function::setPersonalityFn
void setPersonalityFn(Constant *Fn)
Definition: Function.cpp:1828
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:2532
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:1113
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:954
llvm::Function::setEntryCount
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:1887
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:1150
llvm::SwitchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3418
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1558
DataLayout.h
llvm::SymbolTableList< BasicBlock >
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:789
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:127
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:2530
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:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
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:990
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::updateLoopMetadataDebugLocations
void updateLoopMetadataDebugLocations(Instruction &I, function_ref< Metadata *(Metadata *)> Updater)
Update the debug locations contained within the MD_loop metadata attached to the instruction I,...
Definition: DebugInfo.cpp:374
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
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:733
llvm::DILabel::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:3233
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:776
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:206
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:566
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:564
Constant.h
Verifier.h
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:204
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:348
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:2675
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:1071
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:914
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:3013
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:1819
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:1472
llvm::BlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
Definition: BlockFrequencyInfo.cpp:204
llvm::Function::getPersonalityFn
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1823
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:748
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:740
llvm::DIVariable::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:2533
llvm::Function::isVarArg
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:189
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:186
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:370
User.h
llvm::Value::stripInBoundsConstantOffsets
const Value * stripInBoundsConstantOffsets() const
Strip off pointer casts and all-constant inbounds GEPs.
Definition: Value.cpp:699
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:641
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:2749
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::Function::addFnAttr
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.cpp:536
llvm::Function::setDoesNotReturn
void setDoesNotReturn()
Definition: Function.h:558
llvm::PHINode
Definition: Instructions.h:2633
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1820
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:2535
llvm::CodeExtractor::isEligible
bool isEligible() const
Test whether this code extractor is eligible.
Definition: CodeExtractor.cpp:620
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:1045
llvm::Type::getInt16Ty
static IntegerType * getInt16Ty(LLVMContext &C)
Definition: Type.cpp:202
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:1475
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:172
llvm::DILabel
Label.
Definition: DebugInfoMetadata.h:3185
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:3168
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:3212
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::Function::ProfileCount
Class to represent profile counts.
Definition: Function.h:254
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4184
llvm::cl::desc
Definition: CommandLine.h:414
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:814
Value.h
llvm::pdb::PDB_SymType::Block
@ Block
llvm::BlockFrequencyInfoImplBase::BlockNode
Representative of a block.
Definition: BlockFrequencyInfoImpl.h:191
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::DIVariable::getType
DIType * getType() const
Definition: DebugInfoMetadata.h:2534
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:1485
SetVector.h
llvm::BasicBlock::const_iterator
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:91
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
llvm::DIScope::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:484
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h: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