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