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 
875  // Inherit all of the target dependent attributes and white-listed
876  // target independent attributes.
877  // (e.g. If the extracted region contains a call to an x86.sse
878  // instruction we need to make sure that the extracted region has the
879  // "target-features" attribute allowing it to be lowered.
880  // FIXME: This should be changed to check to see if a specific
881  // attribute can not be inherited.
882  for (const auto &Attr : oldFunction->getAttributes().getFnAttrs()) {
883  if (Attr.isStringAttribute()) {
884  if (Attr.getKindAsString() == "thunk")
885  continue;
886  } else
887  switch (Attr.getKindAsEnum()) {
888  // Those attributes cannot be propagated safely. Explicitly list them
889  // here so we get a warning if new attributes are added.
890  case Attribute::AllocSize:
891  case Attribute::ArgMemOnly:
892  case Attribute::Builtin:
894  case Attribute::InaccessibleMemOnly:
895  case Attribute::InaccessibleMemOrArgMemOnly:
897  case Attribute::Naked:
898  case Attribute::NoBuiltin:
899  case Attribute::NoMerge:
900  case Attribute::NoReturn:
901  case Attribute::NoSync:
902  case Attribute::ReadNone:
903  case Attribute::ReadOnly:
904  case Attribute::ReturnsTwice:
905  case Attribute::Speculatable:
906  case Attribute::StackAlignment:
907  case Attribute::WillReturn:
908  case Attribute::WriteOnly:
909  continue;
910  // Those attributes should be safe to propagate to the extracted function.
911  case Attribute::AlwaysInline:
912  case Attribute::Cold:
913  case Attribute::DisableSanitizerInstrumentation:
914  case Attribute::Hot:
915  case Attribute::NoRecurse:
916  case Attribute::InlineHint:
917  case Attribute::MinSize:
918  case Attribute::NoCallback:
919  case Attribute::NoDuplicate:
920  case Attribute::NoFree:
921  case Attribute::NoImplicitFloat:
922  case Attribute::NoInline:
923  case Attribute::NonLazyBind:
924  case Attribute::NoRedZone:
925  case Attribute::NoUnwind:
926  case Attribute::NoSanitizeCoverage:
927  case Attribute::NullPointerIsValid:
928  case Attribute::OptForFuzzing:
929  case Attribute::OptimizeNone:
930  case Attribute::OptimizeForSize:
931  case Attribute::SafeStack:
932  case Attribute::ShadowCallStack:
933  case Attribute::SanitizeAddress:
934  case Attribute::SanitizeMemory:
935  case Attribute::SanitizeThread:
936  case Attribute::SanitizeHWAddress:
937  case Attribute::SanitizeMemTag:
938  case Attribute::SpeculativeLoadHardening:
939  case Attribute::StackProtect:
940  case Attribute::StackProtectReq:
941  case Attribute::StackProtectStrong:
942  case Attribute::StrictFP:
943  case Attribute::UWTable:
944  case Attribute::VScaleRange:
945  case Attribute::NoCfCheck:
946  case Attribute::MustProgress:
947  case Attribute::NoProfile:
948  break;
949  // These attributes cannot be applied to functions.
950  case Attribute::Alignment:
951  case Attribute::ByVal:
952  case Attribute::Dereferenceable:
953  case Attribute::DereferenceableOrNull:
954  case Attribute::ElementType:
955  case Attribute::InAlloca:
956  case Attribute::InReg:
957  case Attribute::Nest:
958  case Attribute::NoAlias:
959  case Attribute::NoCapture:
960  case Attribute::NoUndef:
961  case Attribute::NonNull:
962  case Attribute::Preallocated:
963  case Attribute::Returned:
964  case Attribute::SExt:
965  case Attribute::StructRet:
966  case Attribute::SwiftError:
967  case Attribute::SwiftSelf:
968  case Attribute::SwiftAsync:
969  case Attribute::ZExt:
970  case Attribute::ImmArg:
971  case Attribute::ByRef:
972  // These are not really attributes.
973  case Attribute::None:
975  case Attribute::EmptyKey:
977  llvm_unreachable("Not a function attribute");
978  }
979 
980  newFunction->addFnAttr(Attr);
981  }
982  newFunction->getBasicBlockList().push_back(newRootNode);
983 
984  // Create an iterator to name all of the arguments we inserted.
985  Function::arg_iterator AI = newFunction->arg_begin();
986 
987  // Rewrite all users of the inputs in the extracted region to use the
988  // arguments (or appropriate addressing into struct) instead.
989  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
990  Value *RewriteVal;
991  if (AggregateArgs) {
992  Value *Idx[2];
994  Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
995  Instruction *TI = newFunction->begin()->getTerminator();
997  StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
998  RewriteVal = new LoadInst(StructTy->getElementType(i), GEP,
999  "loadgep_" + inputs[i]->getName(), TI);
1000  } else
1001  RewriteVal = &*AI++;
1002 
1003  std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
1004  for (User *use : Users)
1005  if (Instruction *inst = dyn_cast<Instruction>(use))
1006  if (Blocks.count(inst->getParent()))
1007  inst->replaceUsesOfWith(inputs[i], RewriteVal);
1008  }
1009 
1010  // Set names for input and output arguments.
1011  if (!AggregateArgs) {
1012  AI = newFunction->arg_begin();
1013  for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
1014  AI->setName(inputs[i]->getName());
1015  for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
1016  AI->setName(outputs[i]->getName()+".out");
1017  }
1018 
1019  // Rewrite branches to basic blocks outside of the loop to new dummy blocks
1020  // within the new function. This must be done before we lose track of which
1021  // blocks were originally in the code region.
1022  std::vector<User *> Users(header->user_begin(), header->user_end());
1023  for (auto &U : Users)
1024  // The BasicBlock which contains the branch is not in the region
1025  // modify the branch target to a new block
1026  if (Instruction *I = dyn_cast<Instruction>(U))
1027  if (I->isTerminator() && I->getFunction() == oldFunction &&
1028  !Blocks.count(I->getParent()))
1029  I->replaceUsesOfWith(header, newHeader);
1030 
1031  return newFunction;
1032 }
1033 
1034 /// Erase lifetime.start markers which reference inputs to the extraction
1035 /// region, and insert the referenced memory into \p LifetimesStart.
1036 ///
1037 /// The extraction region is defined by a set of blocks (\p Blocks), and a set
1038 /// of allocas which will be moved from the caller function into the extracted
1039 /// function (\p SunkAllocas).
1041  const SetVector<Value *> &SunkAllocas,
1042  SetVector<Value *> &LifetimesStart) {
1043  for (BasicBlock *BB : Blocks) {
1045  auto *II = dyn_cast<IntrinsicInst>(&I);
1046  if (!II || !II->isLifetimeStartOrEnd())
1047  continue;
1048 
1049  // Get the memory operand of the lifetime marker. If the underlying
1050  // object is a sunk alloca, or is otherwise defined in the extraction
1051  // region, the lifetime marker must not be erased.
1052  Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
1053  if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
1054  continue;
1055 
1056  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1057  LifetimesStart.insert(Mem);
1058  II->eraseFromParent();
1059  }
1060  }
1061 }
1062 
1063 /// Insert lifetime start/end markers surrounding the call to the new function
1064 /// for objects defined in the caller.
1066  Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
1067  CallInst *TheCall) {
1068  LLVMContext &Ctx = M->getContext();
1069  auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
1070  auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
1071  Instruction *Term = TheCall->getParent()->getTerminator();
1072 
1073  // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
1074  // needed to satisfy this requirement so they may be reused.
1075  DenseMap<Value *, Value *> Bitcasts;
1076 
1077  // Emit lifetime markers for the pointers given in \p Objects. Insert the
1078  // markers before the call if \p InsertBefore, and after the call otherwise.
1079  auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
1080  bool InsertBefore) {
1081  for (Value *Mem : Objects) {
1082  assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==
1083  TheCall->getFunction()) &&
1084  "Input memory not defined in original function");
1085  Value *&MemAsI8Ptr = Bitcasts[Mem];
1086  if (!MemAsI8Ptr) {
1087  if (Mem->getType() == Int8PtrTy)
1088  MemAsI8Ptr = Mem;
1089  else
1090  MemAsI8Ptr =
1091  CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
1092  }
1093 
1094  auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
1095  if (InsertBefore)
1096  Marker->insertBefore(TheCall);
1097  else
1098  Marker->insertBefore(Term);
1099  }
1100  };
1101 
1102  if (!LifetimesStart.empty()) {
1103  auto StartFn = llvm::Intrinsic::getDeclaration(
1104  M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
1105  insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
1106  }
1107 
1108  if (!LifetimesEnd.empty()) {
1109  auto EndFn = llvm::Intrinsic::getDeclaration(
1110  M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
1111  insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
1112  }
1113 }
1114 
1115 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
1116 /// the call instruction, splitting any PHI nodes in the header block as
1117 /// necessary.
1118 CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
1119  BasicBlock *codeReplacer,
1120  ValueSet &inputs,
1121  ValueSet &outputs) {
1122  // Emit a call to the new function, passing in: *pointer to struct (if
1123  // aggregating parameters), or plan inputs and allocated memory for outputs
1124  std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
1125 
1126  Module *M = newFunction->getParent();
1127  LLVMContext &Context = M->getContext();
1128  const DataLayout &DL = M->getDataLayout();
1129  CallInst *call = nullptr;
1130 
1131  // Add inputs as params, or to be filled into the struct
1132  unsigned ArgNo = 0;
1133  SmallVector<unsigned, 1> SwiftErrorArgs;
1134  for (Value *input : inputs) {
1135  if (AggregateArgs)
1136  StructValues.push_back(input);
1137  else {
1138  params.push_back(input);
1139  if (input->isSwiftError())
1140  SwiftErrorArgs.push_back(ArgNo);
1141  }
1142  ++ArgNo;
1143  }
1144 
1145  // Create allocas for the outputs
1146  for (Value *output : outputs) {
1147  if (AggregateArgs) {
1148  StructValues.push_back(output);
1149  } else {
1150  AllocaInst *alloca =
1151  new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
1152  nullptr, output->getName() + ".loc",
1153  &codeReplacer->getParent()->front().front());
1154  ReloadOutputs.push_back(alloca);
1155  params.push_back(alloca);
1156  }
1157  }
1158 
1159  StructType *StructArgTy = nullptr;
1160  AllocaInst *Struct = nullptr;
1161  if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
1162  std::vector<Type *> ArgTypes;
1163  for (Value *V : StructValues)
1164  ArgTypes.push_back(V->getType());
1165 
1166  // Allocate a struct at the beginning of this function
1167  StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
1168  Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
1169  "structArg",
1170  &codeReplacer->getParent()->front().front());
1171  params.push_back(Struct);
1172 
1173  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
1174  Value *Idx[2];
1178  StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
1179  codeReplacer->getInstList().push_back(GEP);
1180  new StoreInst(StructValues[i], GEP, codeReplacer);
1181  }
1182  }
1183 
1184  // Emit the call to the function
1185  call = CallInst::Create(newFunction, params,
1186  NumExitBlocks > 1 ? "targetBlock" : "");
1187  // Add debug location to the new call, if the original function has debug
1188  // info. In that case, the terminator of the entry block of the extracted
1189  // function contains the first debug location of the extracted function,
1190  // set in extractCodeRegion.
1191  if (codeReplacer->getParent()->getSubprogram()) {
1192  if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
1193  call->setDebugLoc(DL);
1194  }
1195  codeReplacer->getInstList().push_back(call);
1196 
1197  // Set swifterror parameter attributes.
1198  for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
1199  call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1200  newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1201  }
1202 
1203  Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
1204  unsigned FirstOut = inputs.size();
1205  if (!AggregateArgs)
1206  std::advance(OutputArgBegin, inputs.size());
1207 
1208  // Reload the outputs passed in by reference.
1209  for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1210  Value *Output = nullptr;
1211  if (AggregateArgs) {
1212  Value *Idx[2];
1214  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1216  StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
1217  codeReplacer->getInstList().push_back(GEP);
1218  Output = GEP;
1219  } else {
1220  Output = ReloadOutputs[i];
1221  }
1222  LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
1223  outputs[i]->getName() + ".reload",
1224  codeReplacer);
1225  Reloads.push_back(load);
1226  std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
1227  for (unsigned u = 0, e = Users.size(); u != e; ++u) {
1228  Instruction *inst = cast<Instruction>(Users[u]);
1229  if (!Blocks.count(inst->getParent()))
1230  inst->replaceUsesOfWith(outputs[i], load);
1231  }
1232  }
1233 
1234  // Now we can emit a switch statement using the call as a value.
1235  SwitchInst *TheSwitch =
1237  codeReplacer, 0, codeReplacer);
1238 
1239  // Since there may be multiple exits from the original region, make the new
1240  // function return an unsigned, switch on that number. This loop iterates
1241  // over all of the blocks in the extracted region, updating any terminator
1242  // instructions in the to-be-extracted region that branch to blocks that are
1243  // not in the region to be extracted.
1244  std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1245 
1246  // Iterate over the previously collected targets, and create new blocks inside
1247  // the function to branch to.
1248  unsigned switchVal = 0;
1249  for (BasicBlock *OldTarget : OldTargets) {
1250  if (Blocks.count(OldTarget))
1251  continue;
1252  BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1253  if (NewTarget)
1254  continue;
1255 
1256  // If we don't already have an exit stub for this non-extracted
1257  // destination, create one now!
1258  NewTarget = BasicBlock::Create(Context,
1259  OldTarget->getName() + ".exitStub",
1260  newFunction);
1261  unsigned SuccNum = switchVal++;
1262 
1263  Value *brVal = nullptr;
1264  assert(NumExitBlocks < 0xffff && "too many exit blocks for switch");
1265  switch (NumExitBlocks) {
1266  case 0:
1267  case 1: break; // No value needed.
1268  case 2: // Conditional branch, return a bool
1269  brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1270  break;
1271  default:
1272  brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1273  break;
1274  }
1275 
1276  ReturnInst::Create(Context, brVal, NewTarget);
1277 
1278  // Update the switch instruction.
1280  SuccNum),
1281  OldTarget);
1282  }
1283 
1284  for (BasicBlock *Block : Blocks) {
1285  Instruction *TI = Block->getTerminator();
1286  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1287  if (Blocks.count(TI->getSuccessor(i)))
1288  continue;
1289  BasicBlock *OldTarget = TI->getSuccessor(i);
1290  // add a new basic block which returns the appropriate value
1291  BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1292  assert(NewTarget && "Unknown target block!");
1293 
1294  // rewrite the original branch instruction with this new target
1295  TI->setSuccessor(i, NewTarget);
1296  }
1297  }
1298 
1299  // Store the arguments right after the definition of output value.
1300  // This should be proceeded after creating exit stubs to be ensure that invoke
1301  // result restore will be placed in the outlined function.
1302  Function::arg_iterator OAI = OutputArgBegin;
1303  for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
1304  auto *OutI = dyn_cast<Instruction>(outputs[i]);
1305  if (!OutI)
1306  continue;
1307 
1308  // Find proper insertion point.
1309  BasicBlock::iterator InsertPt;
1310  // In case OutI is an invoke, we insert the store at the beginning in the
1311  // 'normal destination' BB. Otherwise we insert the store right after OutI.
1312  if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1313  InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1314  else if (auto *Phi = dyn_cast<PHINode>(OutI))
1315  InsertPt = Phi->getParent()->getFirstInsertionPt();
1316  else
1317  InsertPt = std::next(OutI->getIterator());
1318 
1319  Instruction *InsertBefore = &*InsertPt;
1320  assert((InsertBefore->getFunction() == newFunction ||
1321  Blocks.count(InsertBefore->getParent())) &&
1322  "InsertPt should be in new function");
1323  assert(OAI != newFunction->arg_end() &&
1324  "Number of output arguments should match "
1325  "the amount of defined values");
1326  if (AggregateArgs) {
1327  Value *Idx[2];
1329  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1331  StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(),
1332  InsertBefore);
1333  new StoreInst(outputs[i], GEP, InsertBefore);
1334  // Since there should be only one struct argument aggregating
1335  // all the output values, we shouldn't increment OAI, which always
1336  // points to the struct argument, in this case.
1337  } else {
1338  new StoreInst(outputs[i], &*OAI, InsertBefore);
1339  ++OAI;
1340  }
1341  }
1342 
1343  // Now that we've done the deed, simplify the switch instruction.
1344  Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1345  switch (NumExitBlocks) {
1346  case 0:
1347  // There are no successors (the block containing the switch itself), which
1348  // means that previously this was the last part of the function, and hence
1349  // this should be rewritten as a `ret'
1350 
1351  // Check if the function should return a value
1352  if (OldFnRetTy->isVoidTy()) {
1353  ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
1354  } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1355  // return what we have
1356  ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1357  } else {
1358  // Otherwise we must have code extracted an unwind or something, just
1359  // return whatever we want.
1361  Constant::getNullValue(OldFnRetTy), TheSwitch);
1362  }
1363 
1364  TheSwitch->eraseFromParent();
1365  break;
1366  case 1:
1367  // Only a single destination, change the switch into an unconditional
1368  // branch.
1369  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1370  TheSwitch->eraseFromParent();
1371  break;
1372  case 2:
1373  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1374  call, TheSwitch);
1375  TheSwitch->eraseFromParent();
1376  break;
1377  default:
1378  // Otherwise, make the default destination of the switch instruction be one
1379  // of the other successors.
1380  TheSwitch->setCondition(call);
1381  TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1382  // Remove redundant case
1383  TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1384  break;
1385  }
1386 
1387  // Insert lifetime markers around the reloads of any output values. The
1388  // allocas output values are stored in are only in-use in the codeRepl block.
1389  insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);
1390 
1391  return call;
1392 }
1393 
1394 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1395  Function *oldFunc = (*Blocks.begin())->getParent();
1396  Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1397  Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1398 
1399  auto newFuncIt = newFunction->front().getIterator();
1400  for (BasicBlock *Block : Blocks) {
1401  // Delete the basic block from the old function, and the list of blocks
1402  oldBlocks.remove(Block);
1403 
1404  // Insert this basic block into the new function
1405  // Insert the original blocks after the entry block created
1406  // for the new function. The entry block may be followed
1407  // by a set of exit blocks at this point, but these exit
1408  // blocks better be placed at the end of the new function.
1409  newFuncIt = newBlocks.insertAfter(newFuncIt, Block);
1410  }
1411 }
1412 
1413 void CodeExtractor::calculateNewCallTerminatorWeights(
1414  BasicBlock *CodeReplacer,
1416  BranchProbabilityInfo *BPI) {
1417  using Distribution = BlockFrequencyInfoImplBase::Distribution;
1418  using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1419 
1420  // Update the branch weights for the exit block.
1421  Instruction *TI = CodeReplacer->getTerminator();
1422  SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1423 
1424  // Block Frequency distribution with dummy node.
1425  Distribution BranchDist;
1426 
1427  SmallVector<BranchProbability, 4> EdgeProbabilities(
1429 
1430  // Add each of the frequencies of the successors.
1431  for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1432  BlockNode ExitNode(i);
1433  uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1434  if (ExitFreq != 0)
1435  BranchDist.addExit(ExitNode, ExitFreq);
1436  else
1437  EdgeProbabilities[i] = BranchProbability::getZero();
1438  }
1439 
1440  // Check for no total weight.
1441  if (BranchDist.Total == 0) {
1442  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1443  return;
1444  }
1445 
1446  // Normalize the distribution so that they can fit in unsigned.
1447  BranchDist.normalize();
1448 
1449  // Create normalized branch weights and set the metadata.
1450  for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1451  const auto &Weight = BranchDist.Weights[I];
1452 
1453  // Get the weight and update the current BFI.
1454  BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1455  BranchProbability BP(Weight.Amount, BranchDist.Total);
1456  EdgeProbabilities[Weight.TargetNode.Index] = BP;
1457  }
1458  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
1459  TI->setMetadata(
1460  LLVMContext::MD_prof,
1461  MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1462 }
1463 
1464 /// Erase debug info intrinsics which refer to values in \p F but aren't in
1465 /// \p F.
1467  for (Instruction &I : instructions(F)) {
1469  findDbgUsers(DbgUsers, &I);
1470  for (DbgVariableIntrinsic *DVI : DbgUsers)
1471  if (DVI->getFunction() != &F)
1472  DVI->eraseFromParent();
1473  }
1474 }
1475 
1476 /// Fix up the debug info in the old and new functions by pointing line
1477 /// locations and debug intrinsics to the new subprogram scope, and by deleting
1478 /// intrinsics which point to values outside of the new function.
1479 static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
1480  CallInst &TheCall) {
1481  DISubprogram *OldSP = OldFunc.getSubprogram();
1482  LLVMContext &Ctx = OldFunc.getContext();
1483 
1484  if (!OldSP) {
1485  // Erase any debug info the new function contains.
1486  stripDebugInfo(NewFunc);
1487  // Make sure the old function doesn't contain any non-local metadata refs.
1489  return;
1490  }
1491 
1492  // Create a subprogram for the new function. Leave out a description of the
1493  // function arguments, as the parameters don't correspond to anything at the
1494  // source level.
1495  assert(OldSP->getUnit() && "Missing compile unit for subprogram");
1496  DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,
1497  OldSP->getUnit());
1498  auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
1499  DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
1500  DISubprogram::SPFlagOptimized |
1501  DISubprogram::SPFlagLocalToUnit;
1502  auto NewSP = DIB.createFunction(
1503  OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
1504  /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
1505  NewFunc.setSubprogram(NewSP);
1506 
1507  // Debug intrinsics in the new function need to be updated in one of two
1508  // ways:
1509  // 1) They need to be deleted, because they describe a value in the old
1510  // function.
1511  // 2) They need to point to fresh metadata, e.g. because they currently
1512  // point to a variable in the wrong scope.
1513  SmallDenseMap<DINode *, DINode *> RemappedMetadata;
1514  SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
1515  for (Instruction &I : instructions(NewFunc)) {
1516  auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
1517  if (!DII)
1518  continue;
1519 
1520  // Point the intrinsic to a fresh label within the new function.
1521  if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
1522  DILabel *OldLabel = DLI->getLabel();
1523  DINode *&NewLabel = RemappedMetadata[OldLabel];
1524  if (!NewLabel)
1525  NewLabel = DILabel::get(Ctx, NewSP, OldLabel->getName(),
1526  OldLabel->getFile(), OldLabel->getLine());
1527  DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
1528  continue;
1529  }
1530 
1531  auto IsInvalidLocation = [&NewFunc](Value *Location) {
1532  // Location is invalid if it isn't a constant or an instruction, or is an
1533  // instruction but isn't in the new function.
1534  if (!Location ||
1535  (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1536  return true;
1537  Instruction *LocationInst = dyn_cast<Instruction>(Location);
1538  return LocationInst && LocationInst->getFunction() != &NewFunc;
1539  };
1540 
1541  auto *DVI = cast<DbgVariableIntrinsic>(DII);
1542  // If any of the used locations are invalid, delete the intrinsic.
1543  if (any_of(DVI->location_ops(), IsInvalidLocation)) {
1544  DebugIntrinsicsToDelete.push_back(DVI);
1545  continue;
1546  }
1547 
1548  // Point the intrinsic to a fresh variable within the new function.
1549  DILocalVariable *OldVar = DVI->getVariable();
1550  DINode *&NewVar = RemappedMetadata[OldVar];
1551  if (!NewVar)
1552  NewVar = DIB.createAutoVariable(
1553  NewSP, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
1554  OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
1555  OldVar->getAlignInBits());
1556  DVI->setVariable(cast<DILocalVariable>(NewVar));
1557  }
1558  for (auto *DII : DebugIntrinsicsToDelete)
1559  DII->eraseFromParent();
1560  DIB.finalizeSubprogram(NewSP);
1561 
1562  // Fix up the scope information attached to the line locations in the new
1563  // function.
1564  for (Instruction &I : instructions(NewFunc)) {
1565  if (const DebugLoc &DL = I.getDebugLoc())
1566  I.setDebugLoc(DILocation::get(Ctx, DL.getLine(), DL.getCol(), NewSP));
1567 
1568  // Loop info metadata may contain line locations. Fix them up.
1569  auto updateLoopInfoLoc = [&Ctx, NewSP](Metadata *MD) -> Metadata * {
1570  if (auto *Loc = dyn_cast_or_null<DILocation>(MD))
1571  return DILocation::get(Ctx, Loc->getLine(), Loc->getColumn(), NewSP,
1572  nullptr);
1573  return MD;
1574  };
1575  updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
1576  }
1577  if (!TheCall.getDebugLoc())
1578  TheCall.setDebugLoc(DILocation::get(Ctx, 0, 0, OldSP));
1579 
1581 }
1582 
1583 Function *
1585  ValueSet Inputs, Outputs;
1586  return extractCodeRegion(CEAC, Inputs, Outputs);
1587 }
1588 
1589 Function *
1591  ValueSet &inputs, ValueSet &outputs) {
1592  if (!isEligible())
1593  return nullptr;
1594 
1595  // Assumption: this is a single-entry code region, and the header is the first
1596  // block in the region.
1597  BasicBlock *header = *Blocks.begin();
1598  Function *oldFunction = header->getParent();
1599 
1600  // Calculate the entry frequency of the new function before we change the root
1601  // block.
1602  BlockFrequency EntryFreq;
1603  if (BFI) {
1604  assert(BPI && "Both BPI and BFI are required to preserve profile info");
1605  for (BasicBlock *Pred : predecessors(header)) {
1606  if (Blocks.count(Pred))
1607  continue;
1608  EntryFreq +=
1609  BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1610  }
1611  }
1612 
1613  // Remove @llvm.assume calls that will be moved to the new function from the
1614  // old function's assumption cache.
1615  for (BasicBlock *Block : Blocks) {
1616  for (Instruction &I : llvm::make_early_inc_range(*Block)) {
1617  if (auto *AI = dyn_cast<AssumeInst>(&I)) {
1618  if (AC)
1619  AC->unregisterAssumption(AI);
1620  AI->eraseFromParent();
1621  }
1622  }
1623  }
1624 
1625  // If we have any return instructions in the region, split those blocks so
1626  // that the return is not in the region.
1627  splitReturnBlocks();
1628 
1629  // Calculate the exit blocks for the extracted region and the total exit
1630  // weights for each of those blocks.
1632  SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1633  for (BasicBlock *Block : Blocks) {
1634  for (BasicBlock *Succ : successors(Block)) {
1635  if (!Blocks.count(Succ)) {
1636  // Update the branch weight for this successor.
1637  if (BFI) {
1638  BlockFrequency &BF = ExitWeights[Succ];
1639  BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, Succ);
1640  }
1641  ExitBlocks.insert(Succ);
1642  }
1643  }
1644  }
1645  NumExitBlocks = ExitBlocks.size();
1646 
1647  for (BasicBlock *Block : Blocks) {
1648  Instruction *TI = Block->getTerminator();
1649  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1650  if (Blocks.count(TI->getSuccessor(i)))
1651  continue;
1652  BasicBlock *OldTarget = TI->getSuccessor(i);
1653  OldTargets.push_back(OldTarget);
1654  }
1655  }
1656 
1657  // If we have to split PHI nodes of the entry or exit blocks, do so now.
1658  severSplitPHINodesOfEntry(header);
1659  severSplitPHINodesOfExits(ExitBlocks);
1660 
1661  // This takes place of the original loop
1662  BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1663  "codeRepl", oldFunction,
1664  header);
1665 
1666  // The new function needs a root node because other nodes can branch to the
1667  // head of the region, but the entry node of a function cannot have preds.
1668  BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1669  "newFuncRoot");
1670  auto *BranchI = BranchInst::Create(header);
1671  // If the original function has debug info, we have to add a debug location
1672  // to the new branch instruction from the artificial entry block.
1673  // We use the debug location of the first instruction in the extracted
1674  // blocks, as there is no other equivalent line in the source code.
1675  if (oldFunction->getSubprogram()) {
1676  any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1677  return any_of(*BB, [&BranchI](const Instruction &I) {
1678  if (!I.getDebugLoc())
1679  return false;
1680  BranchI->setDebugLoc(I.getDebugLoc());
1681  return true;
1682  });
1683  });
1684  }
1685  newFuncRoot->getInstList().push_back(BranchI);
1686 
1687  ValueSet SinkingCands, HoistingCands;
1688  BasicBlock *CommonExit = nullptr;
1689  findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1690  assert(HoistingCands.empty() || CommonExit);
1691 
1692  // Find inputs to, outputs from the code region.
1693  findInputsOutputs(inputs, outputs, SinkingCands);
1694 
1695  // Now sink all instructions which only have non-phi uses inside the region.
1696  // Group the allocas at the start of the block, so that any bitcast uses of
1697  // the allocas are well-defined.
1698  AllocaInst *FirstSunkAlloca = nullptr;
1699  for (auto *II : SinkingCands) {
1700  if (auto *AI = dyn_cast<AllocaInst>(II)) {
1701  AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
1702  if (!FirstSunkAlloca)
1703  FirstSunkAlloca = AI;
1704  }
1705  }
1706  assert((SinkingCands.empty() || FirstSunkAlloca) &&
1707  "Did not expect a sink candidate without any allocas");
1708  for (auto *II : SinkingCands) {
1709  if (!isa<AllocaInst>(II)) {
1710  cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1711  }
1712  }
1713 
1714  if (!HoistingCands.empty()) {
1715  auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1716  Instruction *TI = HoistToBlock->getTerminator();
1717  for (auto *II : HoistingCands)
1718  cast<Instruction>(II)->moveBefore(TI);
1719  }
1720 
1721  // Collect objects which are inputs to the extraction region and also
1722  // referenced by lifetime start markers within it. The effects of these
1723  // markers must be replicated in the calling function to prevent the stack
1724  // coloring pass from merging slots which store input objects.
1725  ValueSet LifetimesStart;
1726  eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);
1727 
1728  // Construct new function based on inputs/outputs & add allocas for all defs.
1729  Function *newFunction =
1730  constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1731  oldFunction, oldFunction->getParent());
1732 
1733  // Update the entry count of the function.
1734  if (BFI) {
1735  auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1736  if (Count.hasValue())
1737  newFunction->setEntryCount(
1738  ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1739  BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1740  }
1741 
1742  CallInst *TheCall =
1743  emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1744 
1745  moveCodeToFunction(newFunction);
1746 
1747  // Replicate the effects of any lifetime start/end markers which referenced
1748  // input objects in the extraction region by placing markers around the call.
1750  oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);
1751 
1752  // Propagate personality info to the new function if there is one.
1753  if (oldFunction->hasPersonalityFn())
1754  newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1755 
1756  // Update the branch weights for the exit block.
1757  if (BFI && NumExitBlocks > 1)
1758  calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1759 
1760  // Loop over all of the PHI nodes in the header and exit blocks, and change
1761  // any references to the old incoming edge to be the new incoming edge.
1762  for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1763  PHINode *PN = cast<PHINode>(I);
1764  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1765  if (!Blocks.count(PN->getIncomingBlock(i)))
1766  PN->setIncomingBlock(i, newFuncRoot);
1767  }
1768 
1769  for (BasicBlock *ExitBB : ExitBlocks)
1770  for (PHINode &PN : ExitBB->phis()) {
1771  Value *IncomingCodeReplacerVal = nullptr;
1772  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1773  // Ignore incoming values from outside of the extracted region.
1774  if (!Blocks.count(PN.getIncomingBlock(i)))
1775  continue;
1776 
1777  // Ensure that there is only one incoming value from codeReplacer.
1778  if (!IncomingCodeReplacerVal) {
1779  PN.setIncomingBlock(i, codeReplacer);
1780  IncomingCodeReplacerVal = PN.getIncomingValue(i);
1781  } else
1782  assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1783  "PHI has two incompatbile incoming values from codeRepl");
1784  }
1785  }
1786 
1787  fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);
1788 
1789  // Mark the new function `noreturn` if applicable. Terminators which resume
1790  // exception propagation are treated as returning instructions. This is to
1791  // avoid inserting traps after calls to outlined functions which unwind.
1792  bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1793  const Instruction *Term = BB.getTerminator();
1794  return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1795  });
1796  if (doesNotReturn)
1797  newFunction->setDoesNotReturn();
1798 
1799  LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1800  newFunction->dump();
1801  report_fatal_error("verification of newFunction failed!");
1802  });
1803  LLVM_DEBUG(if (verifyFunction(*oldFunction))
1804  report_fatal_error("verification of oldFunction failed!"));
1805  LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
1806  report_fatal_error("Stale Asumption cache for old Function!"));
1807  return newFunction;
1808 }
1809 
1811  const Function &NewFunc,
1812  AssumptionCache *AC) {
1813  for (auto AssumeVH : AC->assumptions()) {
1814  auto *I = dyn_cast_or_null<CallInst>(AssumeVH);
1815  if (!I)
1816  continue;
1817 
1818  // There shouldn't be any llvm.assume intrinsics in the new function.
1819  if (I->getFunction() != &OldFunc)
1820  return true;
1821 
1822  // There shouldn't be any stale affected values in the assumption cache
1823  // that were previously in the old function, but that have now been moved
1824  // to the new function.
1825  for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
1826  auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1827  if (!AffectedCI)
1828  continue;
1829  if (AffectedCI->getFunction() != &OldFunc)
1830  return true;
1831  auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1832  if (AssumedInst->getFunction() != &OldFunc)
1833  return true;
1834  }
1835  }
1836  return false;
1837 }
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:3238
llvm::pdb::PDB_UdtType::Struct
@ Struct
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:238
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::DIBuilder::getOrCreateTypeArray
DITypeRefArray getOrCreateTypeArray(ArrayRef< Metadata * > Elements)
Get a DITypeRefArray, create one if required.
Definition: DIBuilder.cpp:672
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:1606
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3010
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:408
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1400
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:293
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:700
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:62
llvm::DIBuilder::finalizeSubprogram
void finalizeSubprogram(DISubprogram *SP)
Finalize a specific subprogram - no new variables may be added to this subprogram afterwards.
Definition: DIBuilder.cpp:62
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:235
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:4815
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:1584
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:1175
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:3425
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:707
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:363
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:5920
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
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:62
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:3239
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:48
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:357
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:1352
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:385
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:397
CodeExtractor.h
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
STLExtras.h
llvm::DIBuilder::createSubroutineType
DISubroutineType * createSubroutineType(DITypeRefArray ParameterTypes, DINode::DIFlags Flags=DINode::FlagZero, unsigned CC=0)
Create subroutine type.
Definition: DIBuilder.cpp:531
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:642
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:272
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:241
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1233
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1336
llvm::SwitchInst::CaseIteratorImpl
Definition: Instructions.h:3277
ProfileCount
Function::ProfileCount ProfileCount
Definition: CodeExtractor.cpp:75
Context
ManagedStatic< detail::RecordContext > Context
Definition: Record.cpp:96
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:782
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:775
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1356
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::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:2753
llvm::SwitchInst::removeCase
CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
Definition: Instructions.cpp:4345
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3104
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:1521
llvm::DISubprogram::DISPFlags
DISPFlags
Debug info subprogram flags.
Definition: DebugInfoMetadata.h:1841
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::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:253
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:831
llvm::Function::arg_end
arg_iterator arg_end()
Definition: Function.h:747
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:143
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
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:775
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:925
SmallPtrSet.h
llvm::Function::PCT_Real
@ PCT_Real
Definition: Function.h:250
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:787
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:216
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::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:71
llvm::Instruction::isLifetimeStartOrEnd
bool isLifetimeStartOrEnd() const
Return true if the instruction is a llvm.lifetime.start or llvm.lifetime.end marker.
Definition: Instruction.cpp:716
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2749
llvm::None
const NoneType None
Definition: None.h:23
llvm::BranchProbability::getUnknown
static BranchProbability getUnknown()
Definition: BranchProbability.h:50
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:385
Type.h
BranchProbability.h
CFG.h
LoopInfo.h
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:316
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:405
BasicBlock.h
llvm::cl::opt< bool >
llvm::Function::setSubprogram
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp: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:47
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:309
llvm::BlockFrequency
Definition: BlockFrequency.h:23
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
BranchProbabilityInfo.h
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:182
llvm::PointerType::getUnqual
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
Definition: DerivedTypes.h:651
llvm::StringRef::empty
constexpr LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:153
llvm::SwitchInst::getSuccessor
BasicBlock * getSuccessor(unsigned idx) const
Definition: Instructions.h:3558
uint64_t
llvm::SwitchInst::setDefaultDest
void setDefaultDest(BasicBlock *DefaultCase)
Definition: Instructions.h:3447
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:578
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2792
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2807
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:3148
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:34
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:933
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:585
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:139
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::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:3440
llvm::Function::setPersonalityFn
void setPersonalityFn(Constant *Fn)
Definition: Function.cpp:1851
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::DIVariable::getName
StringRef getName() const
Definition: DebugInfoMetadata.h:2542
llvm::BranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1107
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:140
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:959
llvm::Function::setEntryCount
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:1910
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:1144
llvm::SwitchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3441
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:1599
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:799
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::DINode
Tagged DWARF-like metadata node.
Definition: DebugInfoMetadata.h:127
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::DIVariable::getLine
unsigned getLine() const
Definition: DebugInfoMetadata.h:2540
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp: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:870
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
llvm::BranchProbability
Definition: BranchProbability.h:29
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h: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:431
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:431
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:180
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:152
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:723
llvm::DILabel::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:3240
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:777
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:185
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
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:242
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::CallingConv::Cold
@ Cold
Definition: CallingConv.h:48
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:2699
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:1065
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:939
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:214
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3037
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:1810
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:579
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:1466
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:1846
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:738
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:119
llvm::Function::front
const BasicBlock & front() const
Definition: Function.h:730
llvm::DIVariable::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:2543
llvm::Function::isVarArg
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:190
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:224
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:697
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:150
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2773
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:548
llvm::PHINode
Definition: Instructions.h:2657
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1826
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:151
llvm::DIVariable::getAlignInBits
uint32_t getAlignInBits() const
Definition: DebugInfoMetadata.h:2545
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:1040
llvm::Type::getInt16Ty
static IntegerType * getInt16Ty(LLVMContext &C)
Definition: Type.cpp:240
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
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:3194
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:3244
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:3236
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:255
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4330
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:39
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:839
Value.h
llvm::pdb::PDB_SymType::Block
@ Block
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::BlockFrequencyInfoImplBase::BlockNode
Representative of a block.
Definition: BlockFrequencyInfoImpl.h:192
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::DIVariable::getType
DIType * getType() const
Definition: DebugInfoMetadata.h:2544
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:1479
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:157