LLVM  8.0.0svn
CodeExtractor.cpp
Go to the documentation of this file.
1 //===- CodeExtractor.cpp - Pull code region into a new function -----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the interface to tear out a code region, such as an
11 // individual loop or a parallel section, into a new function, replacing it with
12 // a call to the new function.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #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/DataLayout.h"
35 #include "llvm/IR/DerivedTypes.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/GlobalValue.h"
39 #include "llvm/IR/InstrTypes.h"
40 #include "llvm/IR/Instruction.h"
41 #include "llvm/IR/Instructions.h"
42 #include "llvm/IR/IntrinsicInst.h"
43 #include "llvm/IR/Intrinsics.h"
44 #include "llvm/IR/LLVMContext.h"
45 #include "llvm/IR/MDBuilder.h"
46 #include "llvm/IR/Module.h"
47 #include "llvm/IR/Type.h"
48 #include "llvm/IR/User.h"
49 #include "llvm/IR/Value.h"
50 #include "llvm/IR/Verifier.h"
51 #include "llvm/Pass.h"
54 #include "llvm/Support/Casting.h"
56 #include "llvm/Support/Debug.h"
61 #include <cassert>
62 #include <cstdint>
63 #include <iterator>
64 #include <map>
65 #include <set>
66 #include <utility>
67 #include <vector>
68 
69 using namespace llvm;
71 
72 #define DEBUG_TYPE "code-extractor"
73 
74 // Provide a command-line option to aggregate function arguments into a struct
75 // for functions produced by the code extractor. This is useful when converting
76 // extracted functions to pthread-based code, as only one argument (void*) can
77 // be passed in to pthread_create().
78 static cl::opt<bool>
79 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
80  cl::desc("Aggregate arguments to code-extracted functions"));
81 
82 /// Test whether a block is valid for extraction.
83 static bool isBlockValidForExtraction(const BasicBlock &BB,
84  const SetVector<BasicBlock *> &Result,
85  bool AllowVarArgs, bool AllowAlloca) {
86  // taking the address of a basic block moved to another function is illegal
87  if (BB.hasAddressTaken())
88  return false;
89 
90  // don't hoist code that uses another basicblock address, as it's likely to
91  // lead to unexpected behavior, like cross-function jumps
94 
95  for (Instruction const &Inst : BB)
96  ToVisit.push_back(&Inst);
97 
98  while (!ToVisit.empty()) {
99  User const *Curr = ToVisit.pop_back_val();
100  if (!Visited.insert(Curr).second)
101  continue;
102  if (isa<BlockAddress const>(Curr))
103  return false; // even a reference to self is likely to be not compatible
104 
105  if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)
106  continue;
107 
108  for (auto const &U : Curr->operands()) {
109  if (auto *UU = dyn_cast<User>(U))
110  ToVisit.push_back(UU);
111  }
112  }
113 
114  // If explicitly requested, allow vastart and alloca. For invoke instructions
115  // verify that extraction is valid.
116  for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
117  if (isa<AllocaInst>(I)) {
118  if (!AllowAlloca)
119  return false;
120  continue;
121  }
122 
123  if (const auto *II = dyn_cast<InvokeInst>(I)) {
124  // Unwind destination (either a landingpad, catchswitch, or cleanuppad)
125  // must be a part of the subgraph which is being extracted.
126  if (auto *UBB = II->getUnwindDest())
127  if (!Result.count(UBB))
128  return false;
129  continue;
130  }
131 
132  // All catch handlers of a catchswitch instruction as well as the unwind
133  // destination must be in the subgraph.
134  if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) {
135  if (auto *UBB = CSI->getUnwindDest())
136  if (!Result.count(UBB))
137  return false;
138  for (auto *HBB : CSI->handlers())
139  if (!Result.count(const_cast<BasicBlock*>(HBB)))
140  return false;
141  continue;
142  }
143 
144  // Make sure that entire catch handler is within subgraph. It is sufficient
145  // to check that catch return's block is in the list.
146  if (const auto *CPI = dyn_cast<CatchPadInst>(I)) {
147  for (const auto *U : CPI->users())
148  if (const auto *CRI = dyn_cast<CatchReturnInst>(U))
149  if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
150  return false;
151  continue;
152  }
153 
154  // And do similar checks for cleanup handler - the entire handler must be
155  // in subgraph which is going to be extracted. For cleanup return should
156  // additionally check that the unwind destination is also in the subgraph.
157  if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) {
158  for (const auto *U : CPI->users())
159  if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
160  if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
161  return false;
162  continue;
163  }
164  if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) {
165  if (auto *UBB = CRI->getUnwindDest())
166  if (!Result.count(UBB))
167  return false;
168  continue;
169  }
170 
171  if (const CallInst *CI = dyn_cast<CallInst>(I)) {
172  if (const Function *F = CI->getCalledFunction()) {
173  auto IID = F->getIntrinsicID();
174  if (IID == Intrinsic::vastart) {
175  if (AllowVarArgs)
176  continue;
177  else
178  return false;
179  }
180 
181  // Currently, we miscompile outlined copies of eh_typid_for. There are
182  // proposals for fixing this in llvm.org/PR39545.
183  if (IID == Intrinsic::eh_typeid_for)
184  return false;
185  }
186  }
187  }
188 
189  return true;
190 }
191 
192 /// Build a set of blocks to extract if the input blocks are viable.
195  bool AllowVarArgs, bool AllowAlloca) {
196  assert(!BBs.empty() && "The set of blocks to extract must be non-empty");
198 
199  // Loop over the blocks, adding them to our set-vector, and aborting with an
200  // empty set if we encounter invalid blocks.
201  for (BasicBlock *BB : BBs) {
202  // If this block is dead, don't process it.
203  if (DT && !DT->isReachableFromEntry(BB))
204  continue;
205 
206  if (!Result.insert(BB))
207  llvm_unreachable("Repeated basic blocks in extraction input");
208  }
209 
210  for (auto *BB : Result) {
211  if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca))
212  return {};
213 
214  // Make sure that the first block is not a landing pad.
215  if (BB == Result.front()) {
216  if (BB->isEHPad()) {
217  LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n");
218  return {};
219  }
220  continue;
221  }
222 
223  // All blocks other than the first must not have predecessors outside of
224  // the subgraph which is being extracted.
225  for (auto *PBB : predecessors(BB))
226  if (!Result.count(PBB)) {
227  LLVM_DEBUG(
228  dbgs() << "No blocks in this region may have entries from "
229  "outside the region except for the first block!\n");
230  return {};
231  }
232  }
233 
234  return Result;
235 }
236 
238  bool AggregateArgs, BlockFrequencyInfo *BFI,
239  BranchProbabilityInfo *BPI, bool AllowVarArgs,
240  bool AllowAlloca, std::string Suffix)
241  : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
242  BPI(BPI), AllowVarArgs(AllowVarArgs),
243  Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)),
244  Suffix(Suffix) {}
245 
246 CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs,
247  BlockFrequencyInfo *BFI,
248  BranchProbabilityInfo *BPI, std::string Suffix)
249  : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
250  BPI(BPI), AllowVarArgs(false),
251  Blocks(buildExtractionBlockSet(L.getBlocks(), &DT,
252  /* AllowVarArgs */ false,
253  /* AllowAlloca */ false)),
254  Suffix(Suffix) {}
255 
256 /// definedInRegion - Return true if the specified value is defined in the
257 /// extracted region.
258 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
259  if (Instruction *I = dyn_cast<Instruction>(V))
260  if (Blocks.count(I->getParent()))
261  return true;
262  return false;
263 }
264 
265 /// definedInCaller - Return true if the specified value is defined in the
266 /// function being code extracted, but not in the region being extracted.
267 /// These values must be passed in as live-ins to the function.
268 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
269  if (isa<Argument>(V)) return true;
270  if (Instruction *I = dyn_cast<Instruction>(V))
271  if (!Blocks.count(I->getParent()))
272  return true;
273  return false;
274 }
275 
277  BasicBlock *CommonExitBlock = nullptr;
278  auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
279  for (auto *Succ : successors(Block)) {
280  // Internal edges, ok.
281  if (Blocks.count(Succ))
282  continue;
283  if (!CommonExitBlock) {
284  CommonExitBlock = Succ;
285  continue;
286  }
287  if (CommonExitBlock == Succ)
288  continue;
289 
290  return true;
291  }
292  return false;
293  };
294 
295  if (any_of(Blocks, hasNonCommonExitSucc))
296  return nullptr;
297 
298  return CommonExitBlock;
299 }
300 
302  Instruction *Addr) const {
303  AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
304  Function *Func = (*Blocks.begin())->getParent();
305  for (BasicBlock &BB : *Func) {
306  if (Blocks.count(&BB))
307  continue;
308  for (Instruction &II : BB) {
309  if (isa<DbgInfoIntrinsic>(II))
310  continue;
311 
312  unsigned Opcode = II.getOpcode();
313  Value *MemAddr = nullptr;
314  switch (Opcode) {
315  case Instruction::Store:
316  case Instruction::Load: {
317  if (Opcode == Instruction::Store) {
318  StoreInst *SI = cast<StoreInst>(&II);
319  MemAddr = SI->getPointerOperand();
320  } else {
321  LoadInst *LI = cast<LoadInst>(&II);
322  MemAddr = LI->getPointerOperand();
323  }
324  // Global variable can not be aliased with locals.
325  if (dyn_cast<Constant>(MemAddr))
326  break;
328  if (!dyn_cast<AllocaInst>(Base) || Base == AI)
329  return false;
330  break;
331  }
332  default: {
333  IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
334  if (IntrInst) {
335  if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start ||
336  IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
337  break;
338  return false;
339  }
340  // Treat all the other cases conservatively if it has side effects.
341  if (II.mayHaveSideEffects())
342  return false;
343  }
344  }
345  }
346  }
347 
348  return true;
349 }
350 
351 BasicBlock *
353  BasicBlock *SinglePredFromOutlineRegion = nullptr;
354  assert(!Blocks.count(CommonExitBlock) &&
355  "Expect a block outside the region!");
356  for (auto *Pred : predecessors(CommonExitBlock)) {
357  if (!Blocks.count(Pred))
358  continue;
359  if (!SinglePredFromOutlineRegion) {
360  SinglePredFromOutlineRegion = Pred;
361  } else if (SinglePredFromOutlineRegion != Pred) {
362  SinglePredFromOutlineRegion = nullptr;
363  break;
364  }
365  }
366 
367  if (SinglePredFromOutlineRegion)
368  return SinglePredFromOutlineRegion;
369 
370 #ifndef NDEBUG
371  auto getFirstPHI = [](BasicBlock *BB) {
372  BasicBlock::iterator I = BB->begin();
373  PHINode *FirstPhi = nullptr;
374  while (I != BB->end()) {
375  PHINode *Phi = dyn_cast<PHINode>(I);
376  if (!Phi)
377  break;
378  if (!FirstPhi) {
379  FirstPhi = Phi;
380  break;
381  }
382  }
383  return FirstPhi;
384  };
385  // If there are any phi nodes, the single pred either exists or has already
386  // be created before code extraction.
387  assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
388 #endif
389 
390  BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
391  CommonExitBlock->getFirstNonPHI()->getIterator());
392 
393  for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock);
394  PI != PE;) {
395  BasicBlock *Pred = *PI++;
396  if (Blocks.count(Pred))
397  continue;
398  Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
399  }
400  // Now add the old exit block to the outline region.
401  Blocks.insert(CommonExitBlock);
402  return CommonExitBlock;
403 }
404 
405 void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
406  BasicBlock *&ExitBlock) const {
407  Function *Func = (*Blocks.begin())->getParent();
408  ExitBlock = getCommonExitBlock(Blocks);
409 
410  for (BasicBlock &BB : *Func) {
411  if (Blocks.count(&BB))
412  continue;
413  for (Instruction &II : BB) {
414  auto *AI = dyn_cast<AllocaInst>(&II);
415  if (!AI)
416  continue;
417 
418  // Find the pair of life time markers for address 'Addr' that are either
419  // defined inside the outline region or can legally be shrinkwrapped into
420  // the outline region. If there are not other untracked uses of the
421  // address, return the pair of markers if found; otherwise return a pair
422  // of nullptr.
423  auto GetLifeTimeMarkers =
424  [&](Instruction *Addr, bool &SinkLifeStart,
425  bool &HoistLifeEnd) -> std::pair<Instruction *, Instruction *> {
426  Instruction *LifeStart = nullptr, *LifeEnd = nullptr;
427 
428  for (User *U : Addr->users()) {
429  IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
430  if (IntrInst) {
431  if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
432  // Do not handle the case where AI has multiple start markers.
433  if (LifeStart)
434  return std::make_pair<Instruction *>(nullptr, nullptr);
435  LifeStart = IntrInst;
436  }
437  if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
438  if (LifeEnd)
439  return std::make_pair<Instruction *>(nullptr, nullptr);
440  LifeEnd = IntrInst;
441  }
442  continue;
443  }
444  // Find untracked uses of the address, bail.
445  if (!definedInRegion(Blocks, U))
446  return std::make_pair<Instruction *>(nullptr, nullptr);
447  }
448 
449  if (!LifeStart || !LifeEnd)
450  return std::make_pair<Instruction *>(nullptr, nullptr);
451 
452  SinkLifeStart = !definedInRegion(Blocks, LifeStart);
453  HoistLifeEnd = !definedInRegion(Blocks, LifeEnd);
454  // Do legality Check.
455  if ((SinkLifeStart || HoistLifeEnd) &&
457  return std::make_pair<Instruction *>(nullptr, nullptr);
458 
459  // Check to see if we have a place to do hoisting, if not, bail.
460  if (HoistLifeEnd && !ExitBlock)
461  return std::make_pair<Instruction *>(nullptr, nullptr);
462 
463  return std::make_pair(LifeStart, LifeEnd);
464  };
465 
466  bool SinkLifeStart = false, HoistLifeEnd = false;
467  auto Markers = GetLifeTimeMarkers(AI, SinkLifeStart, HoistLifeEnd);
468 
469  if (Markers.first) {
470  if (SinkLifeStart)
471  SinkCands.insert(Markers.first);
472  SinkCands.insert(AI);
473  if (HoistLifeEnd)
474  HoistCands.insert(Markers.second);
475  continue;
476  }
477 
478  // Follow the bitcast.
479  Instruction *MarkerAddr = nullptr;
480  for (User *U : AI->users()) {
481  if (U->stripInBoundsConstantOffsets() == AI) {
482  SinkLifeStart = false;
483  HoistLifeEnd = false;
484  Instruction *Bitcast = cast<Instruction>(U);
485  Markers = GetLifeTimeMarkers(Bitcast, SinkLifeStart, HoistLifeEnd);
486  if (Markers.first) {
487  MarkerAddr = Bitcast;
488  continue;
489  }
490  }
491 
492  // Found unknown use of AI.
493  if (!definedInRegion(Blocks, U)) {
494  MarkerAddr = nullptr;
495  break;
496  }
497  }
498 
499  if (MarkerAddr) {
500  if (SinkLifeStart)
501  SinkCands.insert(Markers.first);
502  if (!definedInRegion(Blocks, MarkerAddr))
503  SinkCands.insert(MarkerAddr);
504  SinkCands.insert(AI);
505  if (HoistLifeEnd)
506  HoistCands.insert(Markers.second);
507  }
508  }
509  }
510 }
511 
513  const ValueSet &SinkCands) const {
514  for (BasicBlock *BB : Blocks) {
515  // If a used value is defined outside the region, it's an input. If an
516  // instruction is used outside the region, it's an output.
517  for (Instruction &II : *BB) {
518  for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE;
519  ++OI) {
520  Value *V = *OI;
521  if (!SinkCands.count(V) && definedInCaller(Blocks, V))
522  Inputs.insert(V);
523  }
524 
525  for (User *U : II.users())
526  if (!definedInRegion(Blocks, U)) {
527  Outputs.insert(&II);
528  break;
529  }
530  }
531  }
532 }
533 
534 /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside
535 /// of the region, we need to split the entry block of the region so that the
536 /// PHI node is easier to deal with.
537 void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {
538  unsigned NumPredsFromRegion = 0;
539  unsigned NumPredsOutsideRegion = 0;
540 
541  if (Header != &Header->getParent()->getEntryBlock()) {
542  PHINode *PN = dyn_cast<PHINode>(Header->begin());
543  if (!PN) return; // No PHI nodes.
544 
545  // If the header node contains any PHI nodes, check to see if there is more
546  // than one entry from outside the region. If so, we need to sever the
547  // header block into two.
548  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
549  if (Blocks.count(PN->getIncomingBlock(i)))
550  ++NumPredsFromRegion;
551  else
552  ++NumPredsOutsideRegion;
553 
554  // If there is one (or fewer) predecessor from outside the region, we don't
555  // need to do anything special.
556  if (NumPredsOutsideRegion <= 1) return;
557  }
558 
559  // Otherwise, we need to split the header block into two pieces: one
560  // containing PHI nodes merging values from outside of the region, and a
561  // second that contains all of the code for the block and merges back any
562  // incoming values from inside of the region.
563  BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
564 
565  // We only want to code extract the second block now, and it becomes the new
566  // header of the region.
567  BasicBlock *OldPred = Header;
568  Blocks.remove(OldPred);
569  Blocks.insert(NewBB);
570  Header = NewBB;
571 
572  // Okay, now we need to adjust the PHI nodes and any branches from within the
573  // region to go to the new header block instead of the old header block.
574  if (NumPredsFromRegion) {
575  PHINode *PN = cast<PHINode>(OldPred->begin());
576  // Loop over all of the predecessors of OldPred that are in the region,
577  // changing them to branch to NewBB instead.
578  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
579  if (Blocks.count(PN->getIncomingBlock(i))) {
581  TI->replaceUsesOfWith(OldPred, NewBB);
582  }
583 
584  // Okay, everything within the region is now branching to the right block, we
585  // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
586  BasicBlock::iterator AfterPHIs;
587  for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
588  PHINode *PN = cast<PHINode>(AfterPHIs);
589  // Create a new PHI node in the new region, which has an incoming value
590  // from OldPred of PN.
591  PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
592  PN->getName() + ".ce", &NewBB->front());
593  PN->replaceAllUsesWith(NewPN);
594  NewPN->addIncoming(PN, OldPred);
595 
596  // Loop over all of the incoming value in PN, moving them to NewPN if they
597  // are from the extracted region.
598  for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
599  if (Blocks.count(PN->getIncomingBlock(i))) {
600  NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
601  PN->removeIncomingValue(i);
602  --i;
603  }
604  }
605  }
606  }
607 }
608 
609 /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
610 /// outlined region, we split these PHIs on two: one with inputs from region
611 /// and other with remaining incoming blocks; then first PHIs are placed in
612 /// outlined region.
613 void CodeExtractor::severSplitPHINodesOfExits(
614  const SmallPtrSetImpl<BasicBlock *> &Exits) {
615  for (BasicBlock *ExitBB : Exits) {
616  BasicBlock *NewBB = nullptr;
617 
618  for (PHINode &PN : ExitBB->phis()) {
619  // Find all incoming values from the outlining region.
620  SmallVector<unsigned, 2> IncomingVals;
621  for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
622  if (Blocks.count(PN.getIncomingBlock(i)))
623  IncomingVals.push_back(i);
624 
625  // Do not process PHI if there is one (or fewer) predecessor from region.
626  // If PHI has exactly one predecessor from region, only this one incoming
627  // will be replaced on codeRepl block, so it should be safe to skip PHI.
628  if (IncomingVals.size() <= 1)
629  continue;
630 
631  // Create block for new PHIs and add it to the list of outlined if it
632  // wasn't done before.
633  if (!NewBB) {
634  NewBB = BasicBlock::Create(ExitBB->getContext(),
635  ExitBB->getName() + ".split",
636  ExitBB->getParent(), ExitBB);
638  pred_end(ExitBB));
639  for (BasicBlock *PredBB : Preds)
640  if (Blocks.count(PredBB))
641  PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
642  BranchInst::Create(ExitBB, NewBB);
643  Blocks.insert(NewBB);
644  }
645 
646  // Split this PHI.
647  PHINode *NewPN =
648  PHINode::Create(PN.getType(), IncomingVals.size(),
649  PN.getName() + ".ce", NewBB->getFirstNonPHI());
650  for (unsigned i : IncomingVals)
651  NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));
652  for (unsigned i : reverse(IncomingVals))
653  PN.removeIncomingValue(i, false);
654  PN.addIncoming(NewPN, NewBB);
655  }
656  }
657 }
658 
659 void CodeExtractor::splitReturnBlocks() {
660  for (BasicBlock *Block : Blocks)
661  if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
662  BasicBlock *New =
663  Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
664  if (DT) {
665  // Old dominates New. New node dominates all other nodes dominated
666  // by Old.
667  DomTreeNode *OldNode = DT->getNode(Block);
668  SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
669  OldNode->end());
670 
671  DomTreeNode *NewNode = DT->addNewBlock(New, Block);
672 
673  for (DomTreeNode *I : Children)
674  DT->changeImmediateDominator(I, NewNode);
675  }
676  }
677 }
678 
679 /// constructFunction - make a function based on inputs and outputs, as follows:
680 /// f(in0, ..., inN, out0, ..., outN)
681 Function *CodeExtractor::constructFunction(const ValueSet &inputs,
682  const ValueSet &outputs,
683  BasicBlock *header,
684  BasicBlock *newRootNode,
685  BasicBlock *newHeader,
686  Function *oldFunction,
687  Module *M) {
688  LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
689  LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
690 
691  // This function returns unsigned, outputs will go back by reference.
692  switch (NumExitBlocks) {
693  case 0:
694  case 1: RetTy = Type::getVoidTy(header->getContext()); break;
695  case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
696  default: RetTy = Type::getInt16Ty(header->getContext()); break;
697  }
698 
699  std::vector<Type *> paramTy;
700 
701  // Add the types of the input values to the function's argument list
702  for (Value *value : inputs) {
703  LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n");
704  paramTy.push_back(value->getType());
705  }
706 
707  // Add the types of the output values to the function's argument list.
708  for (Value *output : outputs) {
709  LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n");
710  if (AggregateArgs)
711  paramTy.push_back(output->getType());
712  else
713  paramTy.push_back(PointerType::getUnqual(output->getType()));
714  }
715 
716  LLVM_DEBUG({
717  dbgs() << "Function type: " << *RetTy << " f(";
718  for (Type *i : paramTy)
719  dbgs() << *i << ", ";
720  dbgs() << ")\n";
721  });
722 
723  StructType *StructTy;
724  if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
725  StructTy = StructType::get(M->getContext(), paramTy);
726  paramTy.clear();
727  paramTy.push_back(PointerType::getUnqual(StructTy));
728  }
729  FunctionType *funcType =
730  FunctionType::get(RetTy, paramTy,
731  AllowVarArgs && oldFunction->isVarArg());
732 
733  std::string SuffixToUse =
734  Suffix.empty()
735  ? (header->getName().empty() ? "extracted" : header->getName().str())
736  : Suffix;
737  // Create the new function
738  Function *newFunction = Function::Create(
739  funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
740  oldFunction->getName() + "." + SuffixToUse, M);
741  // If the old function is no-throw, so is the new one.
742  if (oldFunction->doesNotThrow())
743  newFunction->setDoesNotThrow();
744 
745  // Inherit the uwtable attribute if we need to.
746  if (oldFunction->hasUWTable())
747  newFunction->setHasUWTable();
748 
749  // Inherit all of the target dependent attributes and white-listed
750  // target independent attributes.
751  // (e.g. If the extracted region contains a call to an x86.sse
752  // instruction we need to make sure that the extracted region has the
753  // "target-features" attribute allowing it to be lowered.
754  // FIXME: This should be changed to check to see if a specific
755  // attribute can not be inherited.
756  for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) {
757  if (Attr.isStringAttribute()) {
758  if (Attr.getKindAsString() == "thunk")
759  continue;
760  } else
761  switch (Attr.getKindAsEnum()) {
762  // Those attributes cannot be propagated safely. Explicitly list them
763  // here so we get a warning if new attributes are added. This list also
764  // includes non-function attributes.
765  case Attribute::Alignment:
766  case Attribute::AllocSize:
767  case Attribute::ArgMemOnly:
768  case Attribute::Builtin:
769  case Attribute::ByVal:
771  case Attribute::Dereferenceable:
772  case Attribute::DereferenceableOrNull:
773  case Attribute::InAlloca:
774  case Attribute::InReg:
775  case Attribute::InaccessibleMemOnly:
776  case Attribute::InaccessibleMemOrArgMemOnly:
778  case Attribute::Naked:
779  case Attribute::Nest:
780  case Attribute::NoAlias:
781  case Attribute::NoBuiltin:
782  case Attribute::NoCapture:
783  case Attribute::NoReturn:
784  case Attribute::None:
785  case Attribute::NonNull:
786  case Attribute::ReadNone:
787  case Attribute::ReadOnly:
788  case Attribute::Returned:
789  case Attribute::ReturnsTwice:
790  case Attribute::SExt:
791  case Attribute::Speculatable:
792  case Attribute::StackAlignment:
793  case Attribute::StructRet:
794  case Attribute::SwiftError:
795  case Attribute::SwiftSelf:
796  case Attribute::WriteOnly:
797  case Attribute::ZExt:
799  continue;
800  // Those attributes should be safe to propagate to the extracted function.
801  case Attribute::AlwaysInline:
802  case Attribute::Cold:
803  case Attribute::NoRecurse:
804  case Attribute::InlineHint:
805  case Attribute::MinSize:
806  case Attribute::NoDuplicate:
807  case Attribute::NoImplicitFloat:
808  case Attribute::NoInline:
809  case Attribute::NonLazyBind:
810  case Attribute::NoRedZone:
811  case Attribute::NoUnwind:
812  case Attribute::OptForFuzzing:
813  case Attribute::OptimizeNone:
814  case Attribute::OptimizeForSize:
815  case Attribute::SafeStack:
816  case Attribute::ShadowCallStack:
817  case Attribute::SanitizeAddress:
818  case Attribute::SanitizeMemory:
819  case Attribute::SanitizeThread:
820  case Attribute::SanitizeHWAddress:
821  case Attribute::SpeculativeLoadHardening:
822  case Attribute::StackProtect:
823  case Attribute::StackProtectReq:
824  case Attribute::StackProtectStrong:
825  case Attribute::StrictFP:
826  case Attribute::UWTable:
827  case Attribute::NoCfCheck:
828  break;
829  }
830 
831  newFunction->addFnAttr(Attr);
832  }
833  newFunction->getBasicBlockList().push_back(newRootNode);
834 
835  // Create an iterator to name all of the arguments we inserted.
836  Function::arg_iterator AI = newFunction->arg_begin();
837 
838  // Rewrite all users of the inputs in the extracted region to use the
839  // arguments (or appropriate addressing into struct) instead.
840  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
841  Value *RewriteVal;
842  if (AggregateArgs) {
843  Value *Idx[2];
845  Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
846  Instruction *TI = newFunction->begin()->getTerminator();
848  StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
849  RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI);
850  } else
851  RewriteVal = &*AI++;
852 
853  std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
854  for (User *use : Users)
855  if (Instruction *inst = dyn_cast<Instruction>(use))
856  if (Blocks.count(inst->getParent()))
857  inst->replaceUsesOfWith(inputs[i], RewriteVal);
858  }
859 
860  // Set names for input and output arguments.
861  if (!AggregateArgs) {
862  AI = newFunction->arg_begin();
863  for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
864  AI->setName(inputs[i]->getName());
865  for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
866  AI->setName(outputs[i]->getName()+".out");
867  }
868 
869  // Rewrite branches to basic blocks outside of the loop to new dummy blocks
870  // within the new function. This must be done before we lose track of which
871  // blocks were originally in the code region.
872  std::vector<User *> Users(header->user_begin(), header->user_end());
873  for (unsigned i = 0, e = Users.size(); i != e; ++i)
874  // The BasicBlock which contains the branch is not in the region
875  // modify the branch target to a new block
876  if (Instruction *I = dyn_cast<Instruction>(Users[i]))
877  if (I->isTerminator() && !Blocks.count(I->getParent()) &&
878  I->getParent()->getParent() == oldFunction)
879  I->replaceUsesOfWith(header, newHeader);
880 
881  return newFunction;
882 }
883 
884 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
885 /// the call instruction, splitting any PHI nodes in the header block as
886 /// necessary.
887 void CodeExtractor::
888 emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer,
889  ValueSet &inputs, ValueSet &outputs) {
890  // Emit a call to the new function, passing in: *pointer to struct (if
891  // aggregating parameters), or plan inputs and allocated memory for outputs
892  std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
893 
894  Module *M = newFunction->getParent();
896  const DataLayout &DL = M->getDataLayout();
897 
898  // Add inputs as params, or to be filled into the struct
899  for (Value *input : inputs)
900  if (AggregateArgs)
901  StructValues.push_back(input);
902  else
903  params.push_back(input);
904 
905  // Create allocas for the outputs
906  for (Value *output : outputs) {
907  if (AggregateArgs) {
908  StructValues.push_back(output);
909  } else {
910  AllocaInst *alloca =
911  new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
912  nullptr, output->getName() + ".loc",
913  &codeReplacer->getParent()->front().front());
914  ReloadOutputs.push_back(alloca);
915  params.push_back(alloca);
916  }
917  }
918 
919  StructType *StructArgTy = nullptr;
920  AllocaInst *Struct = nullptr;
921  if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
922  std::vector<Type *> ArgTypes;
923  for (ValueSet::iterator v = StructValues.begin(),
924  ve = StructValues.end(); v != ve; ++v)
925  ArgTypes.push_back((*v)->getType());
926 
927  // Allocate a struct at the beginning of this function
928  StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
929  Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
930  "structArg",
931  &codeReplacer->getParent()->front().front());
932  params.push_back(Struct);
933 
934  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
935  Value *Idx[2];
936  Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
937  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
939  StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
940  codeReplacer->getInstList().push_back(GEP);
941  StoreInst *SI = new StoreInst(StructValues[i], GEP);
942  codeReplacer->getInstList().push_back(SI);
943  }
944  }
945 
946  // Emit the call to the function
947  CallInst *call = CallInst::Create(newFunction, params,
948  NumExitBlocks > 1 ? "targetBlock" : "");
949  // Add debug location to the new call, if the original function has debug
950  // info. In that case, the terminator of the entry block of the extracted
951  // function contains the first debug location of the extracted function,
952  // set in extractCodeRegion.
953  if (codeReplacer->getParent()->getSubprogram()) {
954  if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
955  call->setDebugLoc(DL);
956  }
957  codeReplacer->getInstList().push_back(call);
958 
959  Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
960  unsigned FirstOut = inputs.size();
961  if (!AggregateArgs)
962  std::advance(OutputArgBegin, inputs.size());
963 
964  // Reload the outputs passed in by reference.
965  Function::arg_iterator OAI = OutputArgBegin;
966  for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
967  Value *Output = nullptr;
968  if (AggregateArgs) {
969  Value *Idx[2];
970  Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
971  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
973  StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
974  codeReplacer->getInstList().push_back(GEP);
975  Output = GEP;
976  } else {
977  Output = ReloadOutputs[i];
978  }
979  LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload");
980  Reloads.push_back(load);
981  codeReplacer->getInstList().push_back(load);
982  std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
983  for (unsigned u = 0, e = Users.size(); u != e; ++u) {
984  Instruction *inst = cast<Instruction>(Users[u]);
985  if (!Blocks.count(inst->getParent()))
986  inst->replaceUsesOfWith(outputs[i], load);
987  }
988 
989  // Store to argument right after the definition of output value.
990  auto *OutI = dyn_cast<Instruction>(outputs[i]);
991  if (!OutI)
992  continue;
993 
994  // Find proper insertion point.
995  BasicBlock::iterator InsertPt;
996  // In case OutI is an invoke, we insert the store at the beginning in the
997  // 'normal destination' BB. Otherwise we insert the store right after OutI.
998  if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
999  InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1000  else if (auto *Phi = dyn_cast<PHINode>(OutI))
1001  InsertPt = Phi->getParent()->getFirstInsertionPt();
1002  else
1003  InsertPt = std::next(OutI->getIterator());
1004 
1005  assert(OAI != newFunction->arg_end() &&
1006  "Number of output arguments should match "
1007  "the amount of defined values");
1008  if (AggregateArgs) {
1009  Value *Idx[2];
1010  Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
1011  Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
1013  StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), &*InsertPt);
1014  new StoreInst(outputs[i], GEP, &*InsertPt);
1015  // Since there should be only one struct argument aggregating
1016  // all the output values, we shouldn't increment OAI, which always
1017  // points to the struct argument, in this case.
1018  } else {
1019  new StoreInst(outputs[i], &*OAI, &*InsertPt);
1020  ++OAI;
1021  }
1022  }
1023 
1024  // Now we can emit a switch statement using the call as a value.
1025  SwitchInst *TheSwitch =
1027  codeReplacer, 0, codeReplacer);
1028 
1029  // Since there may be multiple exits from the original region, make the new
1030  // function return an unsigned, switch on that number. This loop iterates
1031  // over all of the blocks in the extracted region, updating any terminator
1032  // instructions in the to-be-extracted region that branch to blocks that are
1033  // not in the region to be extracted.
1034  std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1035 
1036  unsigned switchVal = 0;
1037  for (BasicBlock *Block : Blocks) {
1038  Instruction *TI = Block->getTerminator();
1039  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
1040  if (!Blocks.count(TI->getSuccessor(i))) {
1041  BasicBlock *OldTarget = TI->getSuccessor(i);
1042  // add a new basic block which returns the appropriate value
1043  BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1044  if (!NewTarget) {
1045  // If we don't already have an exit stub for this non-extracted
1046  // destination, create one now!
1047  NewTarget = BasicBlock::Create(Context,
1048  OldTarget->getName() + ".exitStub",
1049  newFunction);
1050  unsigned SuccNum = switchVal++;
1051 
1052  Value *brVal = nullptr;
1053  switch (NumExitBlocks) {
1054  case 0:
1055  case 1: break; // No value needed.
1056  case 2: // Conditional branch, return a bool
1057  brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
1058  break;
1059  default:
1060  brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
1061  break;
1062  }
1063 
1064  ReturnInst::Create(Context, brVal, NewTarget);
1065 
1066  // Update the switch instruction.
1067  TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
1068  SuccNum),
1069  OldTarget);
1070  }
1071 
1072  // rewrite the original branch instruction with this new target
1073  TI->setSuccessor(i, NewTarget);
1074  }
1075  }
1076 
1077  // Now that we've done the deed, simplify the switch instruction.
1078  Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
1079  switch (NumExitBlocks) {
1080  case 0:
1081  // There are no successors (the block containing the switch itself), which
1082  // means that previously this was the last part of the function, and hence
1083  // this should be rewritten as a `ret'
1084 
1085  // Check if the function should return a value
1086  if (OldFnRetTy->isVoidTy()) {
1087  ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
1088  } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
1089  // return what we have
1090  ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
1091  } else {
1092  // Otherwise we must have code extracted an unwind or something, just
1093  // return whatever we want.
1094  ReturnInst::Create(Context,
1095  Constant::getNullValue(OldFnRetTy), TheSwitch);
1096  }
1097 
1098  TheSwitch->eraseFromParent();
1099  break;
1100  case 1:
1101  // Only a single destination, change the switch into an unconditional
1102  // branch.
1103  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
1104  TheSwitch->eraseFromParent();
1105  break;
1106  case 2:
1107  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
1108  call, TheSwitch);
1109  TheSwitch->eraseFromParent();
1110  break;
1111  default:
1112  // Otherwise, make the default destination of the switch instruction be one
1113  // of the other successors.
1114  TheSwitch->setCondition(call);
1115  TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
1116  // Remove redundant case
1117  TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
1118  break;
1119  }
1120 }
1121 
1122 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
1123  Function *oldFunc = (*Blocks.begin())->getParent();
1124  Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
1125  Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
1126 
1127  for (BasicBlock *Block : Blocks) {
1128  // Delete the basic block from the old function, and the list of blocks
1129  oldBlocks.remove(Block);
1130 
1131  // Insert this basic block into the new function
1132  newBlocks.push_back(Block);
1133  }
1134 }
1135 
1136 void CodeExtractor::calculateNewCallTerminatorWeights(
1137  BasicBlock *CodeReplacer,
1139  BranchProbabilityInfo *BPI) {
1140  using Distribution = BlockFrequencyInfoImplBase::Distribution;
1141  using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
1142 
1143  // Update the branch weights for the exit block.
1144  Instruction *TI = CodeReplacer->getTerminator();
1145  SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
1146 
1147  // Block Frequency distribution with dummy node.
1148  Distribution BranchDist;
1149 
1150  // Add each of the frequencies of the successors.
1151  for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
1152  BlockNode ExitNode(i);
1153  uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
1154  if (ExitFreq != 0)
1155  BranchDist.addExit(ExitNode, ExitFreq);
1156  else
1157  BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero());
1158  }
1159 
1160  // Check for no total weight.
1161  if (BranchDist.Total == 0)
1162  return;
1163 
1164  // Normalize the distribution so that they can fit in unsigned.
1165  BranchDist.normalize();
1166 
1167  // Create normalized branch weights and set the metadata.
1168  for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
1169  const auto &Weight = BranchDist.Weights[I];
1170 
1171  // Get the weight and update the current BFI.
1172  BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1173  BranchProbability BP(Weight.Amount, BranchDist.Total);
1174  BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP);
1175  }
1176  TI->setMetadata(
1178  MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1179 }
1180 
1182  if (!isEligible())
1183  return nullptr;
1184 
1185  // Assumption: this is a single-entry code region, and the header is the first
1186  // block in the region.
1187  BasicBlock *header = *Blocks.begin();
1188  Function *oldFunction = header->getParent();
1189 
1190  // For functions with varargs, check that varargs handling is only done in the
1191  // outlined function, i.e vastart and vaend are only used in outlined blocks.
1192  if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) {
1193  auto containsVarArgIntrinsic = [](Instruction &I) {
1194  if (const CallInst *CI = dyn_cast<CallInst>(&I))
1195  if (const Function *F = CI->getCalledFunction())
1196  return F->getIntrinsicID() == Intrinsic::vastart ||
1197  F->getIntrinsicID() == Intrinsic::vaend;
1198  return false;
1199  };
1200 
1201  for (auto &BB : *oldFunction) {
1202  if (Blocks.count(&BB))
1203  continue;
1204  if (llvm::any_of(BB, containsVarArgIntrinsic))
1205  return nullptr;
1206  }
1207  }
1208  ValueSet inputs, outputs, SinkingCands, HoistingCands;
1209  BasicBlock *CommonExit = nullptr;
1210 
1211  // Calculate the entry frequency of the new function before we change the root
1212  // block.
1213  BlockFrequency EntryFreq;
1214  if (BFI) {
1215  assert(BPI && "Both BPI and BFI are required to preserve profile info");
1216  for (BasicBlock *Pred : predecessors(header)) {
1217  if (Blocks.count(Pred))
1218  continue;
1219  EntryFreq +=
1220  BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1221  }
1222  }
1223 
1224  // If we have any return instructions in the region, split those blocks so
1225  // that the return is not in the region.
1226  splitReturnBlocks();
1227 
1228  // Calculate the exit blocks for the extracted region and the total exit
1229  // weights for each of those blocks.
1231  SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1232  for (BasicBlock *Block : Blocks) {
1233  for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
1234  ++SI) {
1235  if (!Blocks.count(*SI)) {
1236  // Update the branch weight for this successor.
1237  if (BFI) {
1238  BlockFrequency &BF = ExitWeights[*SI];
1239  BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
1240  }
1241  ExitBlocks.insert(*SI);
1242  }
1243  }
1244  }
1245  NumExitBlocks = ExitBlocks.size();
1246 
1247  // If we have to split PHI nodes of the entry or exit blocks, do so now.
1248  severSplitPHINodesOfEntry(header);
1249  severSplitPHINodesOfExits(ExitBlocks);
1250 
1251  // This takes place of the original loop
1252  BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1253  "codeRepl", oldFunction,
1254  header);
1255 
1256  // The new function needs a root node because other nodes can branch to the
1257  // head of the region, but the entry node of a function cannot have preds.
1258  BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1259  "newFuncRoot");
1260  auto *BranchI = BranchInst::Create(header);
1261  // If the original function has debug info, we have to add a debug location
1262  // to the new branch instruction from the artificial entry block.
1263  // We use the debug location of the first instruction in the extracted
1264  // blocks, as there is no other equivalent line in the source code.
1265  if (oldFunction->getSubprogram()) {
1266  any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1267  return any_of(*BB, [&BranchI](const Instruction &I) {
1268  if (!I.getDebugLoc())
1269  return false;
1270  BranchI->setDebugLoc(I.getDebugLoc());
1271  return true;
1272  });
1273  });
1274  }
1275  newFuncRoot->getInstList().push_back(BranchI);
1276 
1277  findAllocas(SinkingCands, HoistingCands, CommonExit);
1278  assert(HoistingCands.empty() || CommonExit);
1279 
1280  // Find inputs to, outputs from the code region.
1281  findInputsOutputs(inputs, outputs, SinkingCands);
1282 
1283  // Now sink all instructions which only have non-phi uses inside the region
1284  for (auto *II : SinkingCands)
1285  cast<Instruction>(II)->moveBefore(*newFuncRoot,
1286  newFuncRoot->getFirstInsertionPt());
1287 
1288  if (!HoistingCands.empty()) {
1289  auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1290  Instruction *TI = HoistToBlock->getTerminator();
1291  for (auto *II : HoistingCands)
1292  cast<Instruction>(II)->moveBefore(TI);
1293  }
1294 
1295  // Construct new function based on inputs/outputs & add allocas for all defs.
1296  Function *newFunction = constructFunction(inputs, outputs, header,
1297  newFuncRoot,
1298  codeReplacer, oldFunction,
1299  oldFunction->getParent());
1300 
1301  // Update the entry count of the function.
1302  if (BFI) {
1303  auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1304  if (Count.hasValue())
1305  newFunction->setEntryCount(
1306  ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
1307  BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1308  }
1309 
1310  emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1311 
1312  moveCodeToFunction(newFunction);
1313 
1314  // Propagate personality info to the new function if there is one.
1315  if (oldFunction->hasPersonalityFn())
1316  newFunction->setPersonalityFn(oldFunction->getPersonalityFn());
1317 
1318  // Update the branch weights for the exit block.
1319  if (BFI && NumExitBlocks > 1)
1320  calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1321 
1322  // Loop over all of the PHI nodes in the header and exit blocks, and change
1323  // any references to the old incoming edge to be the new incoming edge.
1324  for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1325  PHINode *PN = cast<PHINode>(I);
1326  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1327  if (!Blocks.count(PN->getIncomingBlock(i)))
1328  PN->setIncomingBlock(i, newFuncRoot);
1329  }
1330 
1331  for (BasicBlock *ExitBB : ExitBlocks)
1332  for (PHINode &PN : ExitBB->phis()) {
1333  Value *IncomingCodeReplacerVal = nullptr;
1334  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1335  // Ignore incoming values from outside of the extracted region.
1336  if (!Blocks.count(PN.getIncomingBlock(i)))
1337  continue;
1338 
1339  // Ensure that there is only one incoming value from codeReplacer.
1340  if (!IncomingCodeReplacerVal) {
1341  PN.setIncomingBlock(i, codeReplacer);
1342  IncomingCodeReplacerVal = PN.getIncomingValue(i);
1343  } else
1344  assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
1345  "PHI has two incompatbile incoming values from codeRepl");
1346  }
1347  }
1348 
1349  // Erase debug info intrinsics. Variable updates within the new function are
1350  // invisible to debuggers. This could be improved by defining a DISubprogram
1351  // for the new function.
1352  for (BasicBlock &BB : *newFunction) {
1353  auto BlockIt = BB.begin();
1354  // Remove debug info intrinsics from the new function.
1355  while (BlockIt != BB.end()) {
1356  Instruction *Inst = &*BlockIt;
1357  ++BlockIt;
1358  if (isa<DbgInfoIntrinsic>(Inst))
1359  Inst->eraseFromParent();
1360  }
1361  // Remove debug info intrinsics which refer to values in the new function
1362  // from the old function.
1364  for (Instruction &I : BB)
1365  findDbgUsers(DbgUsers, &I);
1366  for (DbgVariableIntrinsic *DVI : DbgUsers)
1367  DVI->eraseFromParent();
1368  }
1369 
1370  // Mark the new function `noreturn` if applicable. Terminators which resume
1371  // exception propagation are treated as returning instructions. This is to
1372  // avoid inserting traps after calls to outlined functions which unwind.
1373  bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
1374  const Instruction *Term = BB.getTerminator();
1375  return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1376  });
1377  if (doesNotReturn)
1378  newFunction->setDoesNotReturn();
1379 
1380  LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {
1381  newFunction->dump();
1382  report_fatal_error("verification of newFunction failed!");
1383  });
1384  LLVM_DEBUG(if (verifyFunction(*oldFunction))
1385  report_fatal_error("verification of oldFunction failed!"));
1386  return newFunction;
1387 }
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:177
static BasicBlock * getCommonExitBlock(const SetVector< BasicBlock *> &Blocks)
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:228
LLVMContext & Context
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:24
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
Compute the set of input values and output values for the code.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
static cl::opt< bool > AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, cl::desc("Aggregate arguments to code-extracted functions"))
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:869
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic *> &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: Local.cpp:1507
This class represents a function call, abstracting a target machine&#39;s calling convention.
CodeExtractor(ArrayRef< BasicBlock *> BBs, DominatorTree *DT=nullptr, bool AggregateArgs=false, BlockFrequencyInfo *BFI=nullptr, BranchProbabilityInfo *BPI=nullptr, bool AllowVarArgs=false, bool AllowAlloca=false, std::string Suffix="")
Create a code extractor for a sequence of blocks.
Value * getCondition() const
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Function * extractCodeRegion()
Perform the extraction, returning the new function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:705
arg_iterator arg_end()
Definition: Function.h:680
F(f)
static CallInst * Create(Value *Func, ArrayRef< Value *> Args, ArrayRef< OperandBundleDef > Bundles=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
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:138
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
iv Induction Variable Users
Definition: IVUsers.cpp:52
static IntegerType * getInt16Ty(LLVMContext &C)
Definition: Type.cpp:175
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:300
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:265
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
void setDoesNotThrow()
Definition: Function.h:523
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
static bool isBlockValidForExtraction(const BasicBlock &BB, const SetVector< BasicBlock *> &Result, bool AllowVarArgs, bool AllowAlloca)
Test whether a block is valid for extraction.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:258
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:365
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:1366
static bool definedInCaller(const SetVector< BasicBlock *> &Blocks, Value *V)
definedInCaller - Return true if the specified value is defined in the function being code extracted...
Class to represent struct types.
Definition: DerivedTypes.h:201
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
bool hasUWTable() const
True if the ABI mandates (or the user requested) that this function be in a unwind table...
Definition: Function.h:565
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:1194
static StringRef getName(Value *V)
This file contains the simple types necessary to represent the attributes associated with functions a...
No attributes have been set.
Definition: Attributes.h:72
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.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
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:342
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
Class to represent function types.
Definition: DerivedTypes.h:103
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:88
bool isVarArg() const
Definition: DerivedTypes.h:123
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:224
An instruction for storing to memory.
Definition: Instructions.h:310
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:702
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
BasicBlock * getSuccessor(unsigned idx) const
iterator begin()
Definition: Function.h:656
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
static bool definedInRegion(const SetVector< BasicBlock *> &Blocks, Value *V)
definedInRegion - Return true if the specified value is defined in the extracted region.
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:843
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:169
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:190
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1508
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:281
Distribution of unscaled probability weight.
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:371
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
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:1187
unsigned getAddressSpace() const
Definition: Globals.cpp:111
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:297
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
op_range operands()
Definition: User.h:238
Value * getPointerOperand()
Definition: Instructions.h:274
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
arg_iterator arg_begin()
Definition: Function.h:671
self_iterator getIterator()
Definition: ilist_node.h:82
void setHasUWTable()
Definition: Function.h:568
CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
Sentinal value useful for loops.
Definition: Attributes.h:75
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
Class to represent profile counts.
Definition: Function.h:261
size_t size() const
Definition: SmallVector.h:53
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1226
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:51
bool doesNotThrow() const
Determine if the function cannot unwind.
Definition: Function.h:520
size_type size() const
Definition: SmallPtrSet.h:93
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:392
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:334
typename vector_type::const_iterator iterator
Definition: SetVector.h:49
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the generic address space (address sp...
Definition: DerivedTypes.h:482
void setIncomingBlock(unsigned i, BasicBlock *BB)
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors, BranchProbability Prob)
Set the raw edge probability for the given edge.
void setBlockFreq(const BasicBlock *BB, uint64_t Freq)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
bool isEligible() const
Test whether this code extractor is eligible.
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:622
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:125
unsigned getNumIncomingValues() const
Return the number of incoming edges.
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:164
bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const
Check if life time marker nodes can be hoisted/sunk into the outline region.
BasicBlock * findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock)
Find or create a block within the outline region for placing hoisted code.
void push_back(pointer val)
Definition: ilist.h:313
iterator_range< user_iterator > users()
Definition: Value.h:400
Function::ProfileCount ProfileCount
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
pointer remove(iterator &IT)
Definition: ilist.h:251
Analysis providing branch probability information.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:311
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
void setCondition(Value *V)
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:4807
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:633
Rename collisions when linking (static functions).
Definition: GlobalValue.h:56
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:410
pgo instr use
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:376
const BasicBlock & front() const
Definition: Function.h:663
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
LLVM Value Representation.
Definition: Value.h:73
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1302
void setDefaultDest(BasicBlock *DefaultCase)
A vector that has set insertion semantics.
Definition: SetVector.h:41
succ_range successors(Instruction *I)
Definition: CFG.h:264
void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, BasicBlock *&ExitBlock) const
Find the set of allocas whose life ranges are contained within the outlined region.
static const Function * getParent(const Value *V)
AttributeSet getFnAttributes() const
The function attributes are returned.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:230
void setPersonalityFn(Constant *Fn)
Definition: Function.cpp:1307
static BranchProbability getZero()
const Value * stripInBoundsConstantOffsets() const
Strip off pointer casts and all-constant inbounds GEPs.
Definition: Value.cpp:538
#define LLVM_DEBUG(X)
Definition: Debug.h:123
Value * getPointerOperand()
Definition: Instructions.h:402
Optional< uint64_t > getProfileCountFromFreq(uint64_t Freq) const
Returns the estimated profile count of Freq.
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
user_iterator user_end()
Definition: Value.h:384