LLVM  16.0.0git
IROutliner.cpp
Go to the documentation of this file.
1 //===- IROutliner.cpp -- Outline Similar Regions ----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 // Implementation for the IROutliner which is used by the IROutliner Pass.
11 //
12 //===----------------------------------------------------------------------===//
13 
18 #include "llvm/IR/Attributes.h"
19 #include "llvm/IR/DIBuilder.h"
20 #include "llvm/IR/DebugInfo.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/Mangler.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Pass.h"
28 #include "llvm/Transforms/IPO.h"
29 #include <vector>
30 
31 #define DEBUG_TYPE "iroutliner"
32 
33 using namespace llvm;
34 using namespace IRSimilarity;
35 
36 // A command flag to be used for debugging to exclude branches from similarity
37 // matching and outlining.
38 namespace llvm {
40 
41 // A command flag to be used for debugging to indirect calls from similarity
42 // matching and outlining.
44 
45 // A command flag to be used for debugging to exclude intrinsics from similarity
46 // matching and outlining.
48 
49 } // namespace llvm
50 
51 // Set to true if the user wants the ir outliner to run on linkonceodr linkage
52 // functions. This is false by default because the linker can dedupe linkonceodr
53 // functions. Since the outliner is confined to a single module (modulo LTO),
54 // this is off by default. It should, however, be the default behavior in
55 // LTO.
57  "enable-linkonceodr-ir-outlining", cl::Hidden,
58  cl::desc("Enable the IR outliner on linkonceodr functions"),
59  cl::init(false));
60 
61 // This is a debug option to test small pieces of code to ensure that outlining
62 // works correctly.
64  "ir-outlining-no-cost", cl::init(false), cl::ReallyHidden,
65  cl::desc("Debug option to outline greedily, without restriction that "
66  "calculated benefit outweighs cost"));
67 
68 /// The OutlinableGroup holds all the overarching information for outlining
69 /// a set of regions that are structurally similar to one another, such as the
70 /// types of the overall function, the output blocks, the sets of stores needed
71 /// and a list of the different regions. This information is used in the
72 /// deduplication of extracted regions with the same structure.
74  /// The sections that could be outlined
75  std::vector<OutlinableRegion *> Regions;
76 
77  /// The argument types for the function created as the overall function to
78  /// replace the extracted function for each region.
79  std::vector<Type *> ArgumentTypes;
80  /// The FunctionType for the overall function.
81  FunctionType *OutlinedFunctionType = nullptr;
82  /// The Function for the collective overall function.
83  Function *OutlinedFunction = nullptr;
84 
85  /// Flag for whether we should not consider this group of OutlinableRegions
86  /// for extraction.
87  bool IgnoreGroup = false;
88 
89  /// The return blocks for the overall function.
91 
92  /// The PHIBlocks with their corresponding return block based on the return
93  /// value as the key.
95 
96  /// A set containing the different GVN store sets needed. Each array contains
97  /// a sorted list of the different values that need to be stored into output
98  /// registers.
100 
101  /// Flag for whether the \ref ArgumentTypes have been defined after the
102  /// extraction of the first region.
103  bool InputTypesSet = false;
104 
105  /// The number of input values in \ref ArgumentTypes. Anything after this
106  /// index in ArgumentTypes is an output argument.
107  unsigned NumAggregateInputs = 0;
108 
109  /// The mapping of the canonical numbering of the values in outlined sections
110  /// to specific arguments.
112 
113  /// The number of branches in the region target a basic block that is outside
114  /// of the region.
115  unsigned BranchesToOutside = 0;
116 
117  /// Tracker counting backwards from the highest unsigned value possible to
118  /// avoid conflicting with the GVNs of assigned values. We start at -3 since
119  /// -2 and -1 are assigned by the DenseMap.
120  unsigned PHINodeGVNTracker = -3;
121 
122  DenseMap<unsigned,
123  std::pair<std::pair<unsigned, unsigned>, SmallVector<unsigned, 2>>>
126 
127  /// The number of instructions that will be outlined by extracting \ref
128  /// Regions.
129  InstructionCost Benefit = 0;
130  /// The number of added instructions needed for the outlining of the \ref
131  /// Regions.
133 
134  /// The argument that needs to be marked with the swifterr attribute. If not
135  /// needed, there is no value.
137 
138  /// For the \ref Regions, we look at every Value. If it is a constant,
139  /// we check whether it is the same in Region.
140  ///
141  /// \param [in,out] NotSame contains the global value numbers where the
142  /// constant is not always the same, and must be passed in as an argument.
143  void findSameConstants(DenseSet<unsigned> &NotSame);
144 
145  /// For the regions, look at each set of GVN stores needed and account for
146  /// each combination. Add an argument to the argument types if there is
147  /// more than one combination.
148  ///
149  /// \param [in] M - The module we are outlining from.
150  void collectGVNStoreSets(Module &M);
151 };
152 
153 /// Move the contents of \p SourceBB to before the last instruction of \p
154 /// TargetBB.
155 /// \param SourceBB - the BasicBlock to pull Instructions from.
156 /// \param TargetBB - the BasicBlock to put Instruction into.
157 static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB) {
158  for (Instruction &I : llvm::make_early_inc_range(SourceBB))
159  I.moveBefore(TargetBB, TargetBB.end());
160 }
161 
162 /// A function to sort the keys of \p Map, which must be a mapping of constant
163 /// values to basic blocks and return it in \p SortedKeys
164 ///
165 /// \param SortedKeys - The vector the keys will be return in and sorted.
166 /// \param Map - The DenseMap containing keys to sort.
167 static void getSortedConstantKeys(std::vector<Value *> &SortedKeys,
169  for (auto &VtoBB : Map)
170  SortedKeys.push_back(VtoBB.first);
171 
172  // Here we expect to have either 1 value that is void (nullptr) or multiple
173  // values that are all constant integers.
174  if (SortedKeys.size() == 1) {
175  assert(!SortedKeys[0] && "Expected a single void value.");
176  return;
177  }
178 
179  stable_sort(SortedKeys, [](const Value *LHS, const Value *RHS) {
180  assert(LHS && RHS && "Expected non void values.");
181  const ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS);
182  const ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS);
183  assert(RHSC && "Not a constant integer in return value?");
184  assert(LHSC && "Not a constant integer in return value?");
185 
186  return LHSC->getLimitedValue() < RHSC->getLimitedValue();
187  });
188 }
189 
191  Value *V) {
192  Optional<unsigned> GVN = Candidate->getGVN(V);
193  assert(GVN && "No GVN for incoming value");
194  Optional<unsigned> CanonNum = Candidate->getCanonicalNum(*GVN);
195  Optional<unsigned> FirstGVN = Other.Candidate->fromCanonicalNum(*CanonNum);
196  Optional<Value *> FoundValueOpt = Other.Candidate->fromGVN(*FirstGVN);
197  return FoundValueOpt.value_or(nullptr);
198 }
199 
200 BasicBlock *
202  BasicBlock *BB) {
203  Instruction *FirstNonPHI = BB->getFirstNonPHI();
204  assert(FirstNonPHI && "block is empty?");
205  Value *CorrespondingVal = findCorrespondingValueIn(Other, FirstNonPHI);
206  if (!CorrespondingVal)
207  return nullptr;
208  BasicBlock *CorrespondingBlock =
209  cast<Instruction>(CorrespondingVal)->getParent();
210  return CorrespondingBlock;
211 }
212 
213 /// Rewrite the BranchInsts in the incoming blocks to \p PHIBlock that are found
214 /// in \p Included to branch to BasicBlock \p Replace if they currently branch
215 /// to the BasicBlock \p Find. This is used to fix up the incoming basic blocks
216 /// when PHINodes are included in outlined regions.
217 ///
218 /// \param PHIBlock - The BasicBlock containing the PHINodes that need to be
219 /// checked.
220 /// \param Find - The successor block to be replaced.
221 /// \param Replace - The new succesor block to branch to.
222 /// \param Included - The set of blocks about to be outlined.
224  BasicBlock *Replace,
225  DenseSet<BasicBlock *> &Included) {
226  for (PHINode &PN : PHIBlock->phis()) {
227  for (unsigned Idx = 0, PNEnd = PN.getNumIncomingValues(); Idx != PNEnd;
228  ++Idx) {
229  // Check if the incoming block is included in the set of blocks being
230  // outlined.
231  BasicBlock *Incoming = PN.getIncomingBlock(Idx);
232  if (!Included.contains(Incoming))
233  continue;
234 
235  BranchInst *BI = dyn_cast<BranchInst>(Incoming->getTerminator());
236  assert(BI && "Not a branch instruction?");
237  // Look over the branching instructions into this block to see if we
238  // used to branch to Find in this outlined block.
239  for (unsigned Succ = 0, End = BI->getNumSuccessors(); Succ != End;
240  Succ++) {
241  // If we have found the block to replace, we do so here.
242  if (BI->getSuccessor(Succ) != Find)
243  continue;
244  BI->setSuccessor(Succ, Replace);
245  }
246  }
247  }
248 }
249 
250 
252  assert(!CandidateSplit && "Candidate already split!");
253 
254  Instruction *BackInst = Candidate->backInstruction();
255 
256  Instruction *EndInst = nullptr;
257  // Check whether the last instruction is a terminator, if it is, we do
258  // not split on the following instruction. We leave the block as it is. We
259  // also check that this is not the last instruction in the Module, otherwise
260  // the check for whether the current following instruction matches the
261  // previously recorded instruction will be incorrect.
262  if (!BackInst->isTerminator() ||
263  BackInst->getParent() != &BackInst->getFunction()->back()) {
264  EndInst = Candidate->end()->Inst;
265  assert(EndInst && "Expected an end instruction?");
266  }
267 
268  // We check if the current instruction following the last instruction in the
269  // region is the same as the recorded instruction following the last
270  // instruction. If they do not match, there could be problems in rewriting
271  // the program after outlining, so we ignore it.
272  if (!BackInst->isTerminator() &&
273  EndInst != BackInst->getNextNonDebugInstruction())
274  return;
275 
276  Instruction *StartInst = (*Candidate->begin()).Inst;
277  assert(StartInst && "Expected a start instruction?");
278  StartBB = StartInst->getParent();
279  PrevBB = StartBB;
280 
282  Candidate->getBasicBlocks(BBSet);
283 
284  // We iterate over the instructions in the region, if we find a PHINode, we
285  // check if there are predecessors outside of the region, if there are,
286  // we ignore this region since we are unable to handle the severing of the
287  // phi node right now.
288 
289  // TODO: Handle extraneous inputs for PHINodes through variable number of
290  // inputs, similar to how outputs are handled.
291  BasicBlock::iterator It = StartInst->getIterator();
292  EndBB = BackInst->getParent();
293  BasicBlock *IBlock;
294  BasicBlock *PHIPredBlock = nullptr;
295  bool EndBBTermAndBackInstDifferent = EndBB->getTerminator() != BackInst;
296  while (PHINode *PN = dyn_cast<PHINode>(&*It)) {
297  unsigned NumPredsOutsideRegion = 0;
298  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
299  if (!BBSet.contains(PN->getIncomingBlock(i))) {
300  PHIPredBlock = PN->getIncomingBlock(i);
301  ++NumPredsOutsideRegion;
302  continue;
303  }
304 
305  // We must consider the case there the incoming block to the PHINode is
306  // the same as the final block of the OutlinableRegion. If this is the
307  // case, the branch from this block must also be outlined to be valid.
308  IBlock = PN->getIncomingBlock(i);
309  if (IBlock == EndBB && EndBBTermAndBackInstDifferent) {
310  PHIPredBlock = PN->getIncomingBlock(i);
311  ++NumPredsOutsideRegion;
312  }
313  }
314 
315  if (NumPredsOutsideRegion > 1)
316  return;
317 
318  It++;
319  }
320 
321  // If the region starts with a PHINode, but is not the initial instruction of
322  // the BasicBlock, we ignore this region for now.
323  if (isa<PHINode>(StartInst) && StartInst != &*StartBB->begin())
324  return;
325 
326  // If the region ends with a PHINode, but does not contain all of the phi node
327  // instructions of the region, we ignore it for now.
328  if (isa<PHINode>(BackInst) &&
329  BackInst != &*std::prev(EndBB->getFirstInsertionPt()))
330  return;
331 
332  // The basic block gets split like so:
333  // block: block:
334  // inst1 inst1
335  // inst2 inst2
336  // region1 br block_to_outline
337  // region2 block_to_outline:
338  // region3 -> region1
339  // region4 region2
340  // inst3 region3
341  // inst4 region4
342  // br block_after_outline
343  // block_after_outline:
344  // inst3
345  // inst4
346 
347  std::string OriginalName = PrevBB->getName().str();
348 
349  StartBB = PrevBB->splitBasicBlock(StartInst, OriginalName + "_to_outline");
350  PrevBB->replaceSuccessorsPhiUsesWith(PrevBB, StartBB);
351  // If there was a PHINode with an incoming block outside the region,
352  // make sure is correctly updated in the newly split block.
353  if (PHIPredBlock)
354  PrevBB->replaceSuccessorsPhiUsesWith(PHIPredBlock, PrevBB);
355 
356  CandidateSplit = true;
357  if (!BackInst->isTerminator()) {
358  EndBB = EndInst->getParent();
359  FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName + "_after_outline");
360  EndBB->replaceSuccessorsPhiUsesWith(EndBB, FollowBB);
361  FollowBB->replaceSuccessorsPhiUsesWith(PrevBB, FollowBB);
362  } else {
363  EndBB = BackInst->getParent();
364  EndsInBranch = true;
365  FollowBB = nullptr;
366  }
367 
368  // Refind the basic block set.
369  BBSet.clear();
370  Candidate->getBasicBlocks(BBSet);
371  // For the phi nodes in the new starting basic block of the region, we
372  // reassign the targets of the basic blocks branching instructions.
373  replaceTargetsFromPHINode(StartBB, PrevBB, StartBB, BBSet);
374  if (FollowBB)
375  replaceTargetsFromPHINode(FollowBB, EndBB, FollowBB, BBSet);
376 }
377 
379  assert(CandidateSplit && "Candidate is not split!");
380 
381  // The basic block gets reattached like so:
382  // block: block:
383  // inst1 inst1
384  // inst2 inst2
385  // br block_to_outline region1
386  // block_to_outline: -> region2
387  // region1 region3
388  // region2 region4
389  // region3 inst3
390  // region4 inst4
391  // br block_after_outline
392  // block_after_outline:
393  // inst3
394  // inst4
395  assert(StartBB != nullptr && "StartBB for Candidate is not defined!");
396 
397  assert(PrevBB->getTerminator() && "Terminator removed from PrevBB!");
398  // Make sure PHINode references to the block we are merging into are
399  // updated to be incoming blocks from the predecessor to the current block.
400 
401  // NOTE: If this is updated such that the outlined block can have more than
402  // one incoming block to a PHINode, this logic will have to updated
403  // to handle multiple precessors instead.
404 
405  // We only need to update this if the outlined section contains a PHINode, if
406  // it does not, then the incoming block was never changed in the first place.
407  // On the other hand, if PrevBB has no predecessors, it means that all
408  // incoming blocks to the first block are contained in the region, and there
409  // will be nothing to update.
410  Instruction *StartInst = (*Candidate->begin()).Inst;
411  if (isa<PHINode>(StartInst) && !PrevBB->hasNPredecessors(0)) {
412  assert(!PrevBB->hasNPredecessorsOrMore(2) &&
413  "PrevBB has more than one predecessor. Should be 0 or 1.");
414  BasicBlock *BeforePrevBB = PrevBB->getSinglePredecessor();
415  PrevBB->replaceSuccessorsPhiUsesWith(PrevBB, BeforePrevBB);
416  }
417  PrevBB->getTerminator()->eraseFromParent();
418 
419  // If we reattaching after outlining, we iterate over the phi nodes to
420  // the initial block, and reassign the branch instructions of the incoming
421  // blocks to the block we are remerging into.
422  if (!ExtractedFunction) {
424  Candidate->getBasicBlocks(BBSet);
425 
426  replaceTargetsFromPHINode(StartBB, StartBB, PrevBB, BBSet);
427  if (!EndsInBranch)
428  replaceTargetsFromPHINode(FollowBB, FollowBB, EndBB, BBSet);
429  }
430 
431  moveBBContents(*StartBB, *PrevBB);
432 
433  BasicBlock *PlacementBB = PrevBB;
434  if (StartBB != EndBB)
435  PlacementBB = EndBB;
436  if (!EndsInBranch && PlacementBB->getUniqueSuccessor() != nullptr) {
437  assert(FollowBB != nullptr && "FollowBB for Candidate is not defined!");
438  assert(PlacementBB->getTerminator() && "Terminator removed from EndBB!");
439  PlacementBB->getTerminator()->eraseFromParent();
440  moveBBContents(*FollowBB, *PlacementBB);
441  PlacementBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB);
442  FollowBB->eraseFromParent();
443  }
444 
445  PrevBB->replaceSuccessorsPhiUsesWith(StartBB, PrevBB);
446  StartBB->eraseFromParent();
447 
448  // Make sure to save changes back to the StartBB.
449  StartBB = PrevBB;
450  EndBB = nullptr;
451  PrevBB = nullptr;
452  FollowBB = nullptr;
453 
454  CandidateSplit = false;
455 }
456 
457 /// Find whether \p V matches the Constants previously found for the \p GVN.
458 ///
459 /// \param V - The value to check for consistency.
460 /// \param GVN - The global value number assigned to \p V.
461 /// \param GVNToConstant - The mapping of global value number to Constants.
462 /// \returns true if the Value matches the Constant mapped to by V and false if
463 /// it \p V is a Constant but does not match.
464 /// \returns None if \p V is not a Constant.
465 static Optional<bool>
466 constantMatches(Value *V, unsigned GVN,
467  DenseMap<unsigned, Constant *> &GVNToConstant) {
468  // See if we have a constants
469  Constant *CST = dyn_cast<Constant>(V);
470  if (!CST)
471  return None;
472 
473  // Holds a mapping from a global value number to a Constant.
475  bool Inserted;
476 
477 
478  // If we have a constant, try to make a new entry in the GVNToConstant.
479  std::tie(GVNToConstantIt, Inserted) =
480  GVNToConstant.insert(std::make_pair(GVN, CST));
481  // If it was found and is not equal, it is not the same. We do not
482  // handle this case yet, and exit early.
483  if (Inserted || (GVNToConstantIt->second == CST))
484  return true;
485 
486  return false;
487 }
488 
490  InstructionCost Benefit = 0;
491 
492  // Estimate the benefit of outlining a specific sections of the program. We
493  // delegate mostly this task to the TargetTransformInfo so that if the target
494  // has specific changes, we can have a more accurate estimate.
495 
496  // However, getInstructionCost delegates the code size calculation for
497  // arithmetic instructions to getArithmeticInstrCost in
498  // include/Analysis/TargetTransformImpl.h, where it always estimates that the
499  // code size for a division and remainder instruction to be equal to 4, and
500  // everything else to 1. This is not an accurate representation of the
501  // division instruction for targets that have a native division instruction.
502  // To be overly conservative, we only add 1 to the number of instructions for
503  // each division instruction.
504  for (IRInstructionData &ID : *Candidate) {
505  Instruction *I = ID.Inst;
506  switch (I->getOpcode()) {
507  case Instruction::FDiv:
508  case Instruction::FRem:
509  case Instruction::SDiv:
510  case Instruction::SRem:
511  case Instruction::UDiv:
512  case Instruction::URem:
513  Benefit += 1;
514  break;
515  default:
517  break;
518  }
519  }
520 
521  return Benefit;
522 }
523 
524 /// Check the \p OutputMappings structure for value \p Input, if it exists
525 /// it has been used as an output for outlining, and has been renamed, and we
526 /// return the new value, otherwise, we return the same value.
527 ///
528 /// \param OutputMappings [in] - The mapping of values to their renamed value
529 /// after being used as an output for an outlined region.
530 /// \param Input [in] - The value to find the remapped value of, if it exists.
531 /// \return The remapped value if it has been renamed, and the same value if has
532 /// not.
534  Value *Input) {
536  OutputMappings.find(Input);
537  if (OutputMapping != OutputMappings.end())
538  return OutputMapping->second;
539  return Input;
540 }
541 
542 /// Find whether \p Region matches the global value numbering to Constant
543 /// mapping found so far.
544 ///
545 /// \param Region - The OutlinableRegion we are checking for constants
546 /// \param GVNToConstant - The mapping of global value number to Constants.
547 /// \param NotSame - The set of global value numbers that do not have the same
548 /// constant in each region.
549 /// \returns true if all Constants are the same in every use of a Constant in \p
550 /// Region and false if not
551 static bool
553  DenseMap<unsigned, Constant *> &GVNToConstant,
554  DenseSet<unsigned> &NotSame) {
555  bool ConstantsTheSame = true;
556 
557  IRSimilarityCandidate &C = *Region.Candidate;
558  for (IRInstructionData &ID : C) {
559 
560  // Iterate over the operands in an instruction. If the global value number,
561  // assigned by the IRSimilarityCandidate, has been seen before, we check if
562  // the the number has been found to be not the same value in each instance.
563  for (Value *V : ID.OperVals) {
564  Optional<unsigned> GVNOpt = C.getGVN(V);
565  assert(GVNOpt && "Expected a GVN for operand?");
566  unsigned GVN = GVNOpt.value();
567 
568  // Check if this global value has been found to not be the same already.
569  if (NotSame.contains(GVN)) {
570  if (isa<Constant>(V))
571  ConstantsTheSame = false;
572  continue;
573  }
574 
575  // If it has been the same so far, we check the value for if the
576  // associated Constant value match the previous instances of the same
577  // global value number. If the global value does not map to a Constant,
578  // it is considered to not be the same value.
579  Optional<bool> ConstantMatches = constantMatches(V, GVN, GVNToConstant);
580  if (ConstantMatches) {
581  if (ConstantMatches.value())
582  continue;
583  else
584  ConstantsTheSame = false;
585  }
586 
587  // While this value is a register, it might not have been previously,
588  // make sure we don't already have a constant mapped to this global value
589  // number.
590  if (GVNToConstant.find(GVN) != GVNToConstant.end())
591  ConstantsTheSame = false;
592 
593  NotSame.insert(GVN);
594  }
595  }
596 
597  return ConstantsTheSame;
598 }
599 
601  DenseMap<unsigned, Constant *> GVNToConstant;
602 
603  for (OutlinableRegion *Region : Regions)
604  collectRegionsConstants(*Region, GVNToConstant, NotSame);
605 }
606 
608  for (OutlinableRegion *OS : Regions)
609  OutputGVNCombinations.insert(OS->GVNStores);
610 
611  // We are adding an extracted argument to decide between which output path
612  // to use in the basic block. It is used in a switch statement and only
613  // needs to be an integer.
614  if (OutputGVNCombinations.size() > 1)
615  ArgumentTypes.push_back(Type::getInt32Ty(M.getContext()));
616 }
617 
618 /// Get the subprogram if it exists for one of the outlined regions.
619 ///
620 /// \param [in] Group - The set of regions to find a subprogram for.
621 /// \returns the subprogram if it exists, or nullptr.
623  for (OutlinableRegion *OS : Group.Regions)
624  if (Function *F = OS->Call->getFunction())
625  if (DISubprogram *SP = F->getSubprogram())
626  return SP;
627 
628  return nullptr;
629 }
630 
631 Function *IROutliner::createFunction(Module &M, OutlinableGroup &Group,
632  unsigned FunctionNameSuffix) {
633  assert(!Group.OutlinedFunction && "Function is already defined!");
634 
635  Type *RetTy = Type::getVoidTy(M.getContext());
636  // All extracted functions _should_ have the same return type at this point
637  // since the similarity identifier ensures that all branches outside of the
638  // region occur in the same place.
639 
640  // NOTE: Should we ever move to the model that uses a switch at every point
641  // needed, meaning that we could branch within the region or out, it is
642  // possible that we will need to switch to using the most general case all of
643  // the time.
644  for (OutlinableRegion *R : Group.Regions) {
645  Type *ExtractedFuncType = R->ExtractedFunction->getReturnType();
646  if ((RetTy->isVoidTy() && !ExtractedFuncType->isVoidTy()) ||
647  (RetTy->isIntegerTy(1) && ExtractedFuncType->isIntegerTy(16)))
648  RetTy = ExtractedFuncType;
649  }
650 
652  RetTy, Group.ArgumentTypes, false);
653 
654  // These functions will only be called from within the same module, so
655  // we can set an internal linkage.
658  "outlined_ir_func_" + std::to_string(FunctionNameSuffix), M);
659 
660  // Transfer the swifterr attribute to the correct function parameter.
661  if (Group.SwiftErrorArgument)
663  Attribute::SwiftError);
664 
665  Group.OutlinedFunction->addFnAttr(Attribute::OptimizeForSize);
666  Group.OutlinedFunction->addFnAttr(Attribute::MinSize);
667 
668  // If there's a DISubprogram associated with this outlined function, then
669  // emit debug info for the outlined function.
670  if (DISubprogram *SP = getSubprogramOrNull(Group)) {
671  Function *F = Group.OutlinedFunction;
672  // We have a DISubprogram. Get its DICompileUnit.
673  DICompileUnit *CU = SP->getUnit();
674  DIBuilder DB(M, true, CU);
675  DIFile *Unit = SP->getFile();
676  Mangler Mg;
677  // Get the mangled name of the function for the linkage name.
678  std::string Dummy;
679  llvm::raw_string_ostream MangledNameStream(Dummy);
680  Mg.getNameWithPrefix(MangledNameStream, F, false);
681 
682  DISubprogram *OutlinedSP = DB.createFunction(
683  Unit /* Context */, F->getName(), MangledNameStream.str(),
684  Unit /* File */,
685  0 /* Line 0 is reserved for compiler-generated code. */,
686  DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
687  0, /* Line 0 is reserved for compiler-generated code. */
688  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
689  /* Outlined code is optimized code by definition. */
690  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
691 
692  // Don't add any new variables to the subprogram.
693  DB.finalizeSubprogram(OutlinedSP);
694 
695  // Attach subprogram to the function.
696  F->setSubprogram(OutlinedSP);
697  // We're done with the DIBuilder.
698  DB.finalize();
699  }
700 
701  return Group.OutlinedFunction;
702 }
703 
704 /// Move each BasicBlock in \p Old to \p New.
705 ///
706 /// \param [in] Old - The function to move the basic blocks from.
707 /// \param [in] New - The function to move the basic blocks to.
708 /// \param [out] NewEnds - The return blocks of the new overall function.
709 static void moveFunctionData(Function &Old, Function &New,
711  for (BasicBlock &CurrBB : llvm::make_early_inc_range(Old)) {
712  CurrBB.removeFromParent();
713  CurrBB.insertInto(&New);
714  Instruction *I = CurrBB.getTerminator();
715 
716  // For each block we find a return instruction is, it is a potential exit
717  // path for the function. We keep track of each block based on the return
718  // value here.
719  if (ReturnInst *RI = dyn_cast<ReturnInst>(I))
720  NewEnds.insert(std::make_pair(RI->getReturnValue(), &CurrBB));
721 
722  std::vector<Instruction *> DebugInsts;
723 
724  for (Instruction &Val : CurrBB) {
725  // We must handle the scoping of called functions differently than
726  // other outlined instructions.
727  if (!isa<CallInst>(&Val)) {
728  // Remove the debug information for outlined functions.
729  Val.setDebugLoc(DebugLoc());
730 
731  // Loop info metadata may contain line locations. Update them to have no
732  // value in the new subprogram since the outlined code could be from
733  // several locations.
734  auto updateLoopInfoLoc = [&New](Metadata *MD) -> Metadata * {
735  if (DISubprogram *SP = New.getSubprogram())
736  if (auto *Loc = dyn_cast_or_null<DILocation>(MD))
737  return DILocation::get(New.getContext(), Loc->getLine(),
738  Loc->getColumn(), SP, nullptr);
739  return MD;
740  };
741  updateLoopMetadataDebugLocations(Val, updateLoopInfoLoc);
742  continue;
743  }
744 
745  // From this point we are only handling call instructions.
746  CallInst *CI = cast<CallInst>(&Val);
747 
748  // We add any debug statements here, to be removed after. Since the
749  // instructions originate from many different locations in the program,
750  // it will cause incorrect reporting from a debugger if we keep the
751  // same debug instructions.
752  if (isa<DbgInfoIntrinsic>(CI)) {
753  DebugInsts.push_back(&Val);
754  continue;
755  }
756 
757  // Edit the scope of called functions inside of outlined functions.
758  if (DISubprogram *SP = New.getSubprogram()) {
759  DILocation *DI = DILocation::get(New.getContext(), 0, 0, SP);
760  Val.setDebugLoc(DI);
761  }
762  }
763 
764  for (Instruction *I : DebugInsts)
765  I->eraseFromParent();
766  }
767 }
768 
769 /// Find the the constants that will need to be lifted into arguments
770 /// as they are not the same in each instance of the region.
771 ///
772 /// \param [in] C - The IRSimilarityCandidate containing the region we are
773 /// analyzing.
774 /// \param [in] NotSame - The set of global value numbers that do not have a
775 /// single Constant across all OutlinableRegions similar to \p C.
776 /// \param [out] Inputs - The list containing the global value numbers of the
777 /// arguments needed for the region of code.
779  std::vector<unsigned> &Inputs) {
780  DenseSet<unsigned> Seen;
781  // Iterate over the instructions, and find what constants will need to be
782  // extracted into arguments.
783  for (IRInstructionDataList::iterator IDIt = C.begin(), EndIDIt = C.end();
784  IDIt != EndIDIt; IDIt++) {
785  for (Value *V : (*IDIt).OperVals) {
786  // Since these are stored before any outlining, they will be in the
787  // global value numbering.
788  unsigned GVN = *C.getGVN(V);
789  if (isa<Constant>(V))
790  if (NotSame.contains(GVN) && !Seen.contains(GVN)) {
791  Inputs.push_back(GVN);
792  Seen.insert(GVN);
793  }
794  }
795  }
796 }
797 
798 /// Find the GVN for the inputs that have been found by the CodeExtractor.
799 ///
800 /// \param [in] C - The IRSimilarityCandidate containing the region we are
801 /// analyzing.
802 /// \param [in] CurrentInputs - The set of inputs found by the
803 /// CodeExtractor.
804 /// \param [in] OutputMappings - The mapping of values that have been replaced
805 /// by a new output value.
806 /// \param [out] EndInputNumbers - The global value numbers for the extracted
807 /// arguments.
809  SetVector<Value *> &CurrentInputs,
810  const DenseMap<Value *, Value *> &OutputMappings,
811  std::vector<unsigned> &EndInputNumbers) {
812  // Get the Global Value Number for each input. We check if the Value has been
813  // replaced by a different value at output, and use the original value before
814  // replacement.
815  for (Value *Input : CurrentInputs) {
816  assert(Input && "Have a nullptr as an input");
817  if (OutputMappings.find(Input) != OutputMappings.end())
818  Input = OutputMappings.find(Input)->second;
819  assert(C.getGVN(Input) && "Could not find a numbering for the given input");
820  EndInputNumbers.push_back(C.getGVN(Input).value());
821  }
822 }
823 
824 /// Find the original value for the \p ArgInput values if any one of them was
825 /// replaced during a previous extraction.
826 ///
827 /// \param [in] ArgInputs - The inputs to be extracted by the code extractor.
828 /// \param [in] OutputMappings - The mapping of values that have been replaced
829 /// by a new output value.
830 /// \param [out] RemappedArgInputs - The remapped values according to
831 /// \p OutputMappings that will be extracted.
832 static void
834  const DenseMap<Value *, Value *> &OutputMappings,
835  SetVector<Value *> &RemappedArgInputs) {
836  // Get the global value number for each input that will be extracted as an
837  // argument by the code extractor, remapping if needed for reloaded values.
838  for (Value *Input : ArgInputs) {
839  if (OutputMappings.find(Input) != OutputMappings.end())
840  Input = OutputMappings.find(Input)->second;
841  RemappedArgInputs.insert(Input);
842  }
843 }
844 
845 /// Find the input GVNs and the output values for a region of Instructions.
846 /// Using the code extractor, we collect the inputs to the extracted function.
847 ///
848 /// The \p Region can be identified as needing to be ignored in this function.
849 /// It should be checked whether it should be ignored after a call to this
850 /// function.
851 ///
852 /// \param [in,out] Region - The region of code to be analyzed.
853 /// \param [out] InputGVNs - The global value numbers for the extracted
854 /// arguments.
855 /// \param [in] NotSame - The global value numbers in the region that do not
856 /// have the same constant value in the regions structurally similar to
857 /// \p Region.
858 /// \param [in] OutputMappings - The mapping of values that have been replaced
859 /// by a new output value after extraction.
860 /// \param [out] ArgInputs - The values of the inputs to the extracted function.
861 /// \param [out] Outputs - The set of values extracted by the CodeExtractor
862 /// as outputs.
864  OutlinableRegion &Region, std::vector<unsigned> &InputGVNs,
865  DenseSet<unsigned> &NotSame, DenseMap<Value *, Value *> &OutputMappings,
866  SetVector<Value *> &ArgInputs, SetVector<Value *> &Outputs) {
867  IRSimilarityCandidate &C = *Region.Candidate;
868 
869  // OverallInputs are the inputs to the region found by the CodeExtractor,
870  // SinkCands and HoistCands are used by the CodeExtractor to find sunken
871  // allocas of values whose lifetimes are contained completely within the
872  // outlined region. PremappedInputs are the arguments found by the
873  // CodeExtractor, removing conditions such as sunken allocas, but that
874  // may need to be remapped due to the extracted output values replacing
875  // the original values. We use DummyOutputs for this first run of finding
876  // inputs and outputs since the outputs could change during findAllocas,
877  // the correct set of extracted outputs will be in the final Outputs ValueSet.
878  SetVector<Value *> OverallInputs, PremappedInputs, SinkCands, HoistCands,
879  DummyOutputs;
880 
881  // Use the code extractor to get the inputs and outputs, without sunken
882  // allocas or removing llvm.assumes.
883  CodeExtractor *CE = Region.CE;
884  CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
885  assert(Region.StartBB && "Region must have a start BasicBlock!");
886  Function *OrigF = Region.StartBB->getParent();
887  CodeExtractorAnalysisCache CEAC(*OrigF);
888  BasicBlock *Dummy = nullptr;
889 
890  // The region may be ineligible due to VarArgs in the parent function. In this
891  // case we ignore the region.
892  if (!CE->isEligible()) {
893  Region.IgnoreRegion = true;
894  return;
895  }
896 
897  // Find if any values are going to be sunk into the function when extracted
898  CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);
899  CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
900 
901  // TODO: Support regions with sunken allocas: values whose lifetimes are
902  // contained completely within the outlined region. These are not guaranteed
903  // to be the same in every region, so we must elevate them all to arguments
904  // when they appear. If these values are not equal, it means there is some
905  // Input in OverallInputs that was removed for ArgInputs.
906  if (OverallInputs.size() != PremappedInputs.size()) {
907  Region.IgnoreRegion = true;
908  return;
909  }
910 
911  findConstants(C, NotSame, InputGVNs);
912 
913  mapInputsToGVNs(C, OverallInputs, OutputMappings, InputGVNs);
914 
915  remapExtractedInputs(PremappedInputs.getArrayRef(), OutputMappings,
916  ArgInputs);
917 
918  // Sort the GVNs, since we now have constants included in the \ref InputGVNs
919  // we need to make sure they are in a deterministic order.
920  stable_sort(InputGVNs);
921 }
922 
923 /// Look over the inputs and map each input argument to an argument in the
924 /// overall function for the OutlinableRegions. This creates a way to replace
925 /// the arguments of the extracted function with the arguments of the new
926 /// overall function.
927 ///
928 /// \param [in,out] Region - The region of code to be analyzed.
929 /// \param [in] InputGVNs - The global value numbering of the input values
930 /// collected.
931 /// \param [in] ArgInputs - The values of the arguments to the extracted
932 /// function.
933 static void
935  std::vector<unsigned> &InputGVNs,
936  SetVector<Value *> &ArgInputs) {
937 
938  IRSimilarityCandidate &C = *Region.Candidate;
939  OutlinableGroup &Group = *Region.Parent;
940 
941  // This counts the argument number in the overall function.
942  unsigned TypeIndex = 0;
943 
944  // This counts the argument number in the extracted function.
945  unsigned OriginalIndex = 0;
946 
947  // Find the mapping of the extracted arguments to the arguments for the
948  // overall function. Since there may be extra arguments in the overall
949  // function to account for the extracted constants, we have two different
950  // counters as we find extracted arguments, and as we come across overall
951  // arguments.
952 
953  // Additionally, in our first pass, for the first extracted function,
954  // we find argument locations for the canonical value numbering. This
955  // numbering overrides any discovered location for the extracted code.
956  for (unsigned InputVal : InputGVNs) {
957  Optional<unsigned> CanonicalNumberOpt = C.getCanonicalNum(InputVal);
958  assert(CanonicalNumberOpt && "Canonical number not found?");
959  unsigned CanonicalNumber = CanonicalNumberOpt.value();
960 
961  Optional<Value *> InputOpt = C.fromGVN(InputVal);
962  assert(InputOpt && "Global value number not found?");
963  Value *Input = InputOpt.value();
964 
966  Group.CanonicalNumberToAggArg.find(CanonicalNumber);
967 
968  if (!Group.InputTypesSet) {
969  Group.ArgumentTypes.push_back(Input->getType());
970  // If the input value has a swifterr attribute, make sure to mark the
971  // argument in the overall function.
972  if (Input->isSwiftError()) {
973  assert(
974  !Group.SwiftErrorArgument &&
975  "Argument already marked with swifterr for this OutlinableGroup!");
976  Group.SwiftErrorArgument = TypeIndex;
977  }
978  }
979 
980  // Check if we have a constant. If we do add it to the overall argument
981  // number to Constant map for the region, and continue to the next input.
982  if (Constant *CST = dyn_cast<Constant>(Input)) {
983  if (AggArgIt != Group.CanonicalNumberToAggArg.end())
984  Region.AggArgToConstant.insert(std::make_pair(AggArgIt->second, CST));
985  else {
987  std::make_pair(CanonicalNumber, TypeIndex));
988  Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
989  }
990  TypeIndex++;
991  continue;
992  }
993 
994  // It is not a constant, we create the mapping from extracted argument list
995  // to the overall argument list, using the canonical location, if it exists.
996  assert(ArgInputs.count(Input) && "Input cannot be found!");
997 
998  if (AggArgIt != Group.CanonicalNumberToAggArg.end()) {
999  if (OriginalIndex != AggArgIt->second)
1000  Region.ChangedArgOrder = true;
1001  Region.ExtractedArgToAgg.insert(
1002  std::make_pair(OriginalIndex, AggArgIt->second));
1003  Region.AggArgToExtracted.insert(
1004  std::make_pair(AggArgIt->second, OriginalIndex));
1005  } else {
1007  std::make_pair(CanonicalNumber, TypeIndex));
1008  Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
1009  Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
1010  }
1011  OriginalIndex++;
1012  TypeIndex++;
1013  }
1014 
1015  // If the function type definitions for the OutlinableGroup holding the region
1016  // have not been set, set the length of the inputs here. We should have the
1017  // same inputs for all of the different regions contained in the
1018  // OutlinableGroup since they are all structurally similar to one another.
1019  if (!Group.InputTypesSet) {
1020  Group.NumAggregateInputs = TypeIndex;
1021  Group.InputTypesSet = true;
1022  }
1023 
1024  Region.NumExtractedInputs = OriginalIndex;
1025 }
1026 
1027 /// Check if the \p V has any uses outside of the region other than \p PN.
1028 ///
1029 /// \param V [in] - The value to check.
1030 /// \param PHILoc [in] - The location in the PHINode of \p V.
1031 /// \param PN [in] - The PHINode using \p V.
1032 /// \param Exits [in] - The potential blocks we exit to from the outlined
1033 /// region.
1034 /// \param BlocksInRegion [in] - The basic blocks contained in the region.
1035 /// \returns true if \p V has any use soutside its region other than \p PN.
1036 static bool outputHasNonPHI(Value *V, unsigned PHILoc, PHINode &PN,
1038  DenseSet<BasicBlock *> &BlocksInRegion) {
1039  // We check to see if the value is used by the PHINode from some other
1040  // predecessor not included in the region. If it is, we make sure
1041  // to keep it as an output.
1042  if (any_of(llvm::seq<unsigned>(0, PN.getNumIncomingValues()),
1043  [PHILoc, &PN, V, &BlocksInRegion](unsigned Idx) {
1044  return (Idx != PHILoc && V == PN.getIncomingValue(Idx) &&
1045  !BlocksInRegion.contains(PN.getIncomingBlock(Idx)));
1046  }))
1047  return true;
1048 
1049  // Check if the value is used by any other instructions outside the region.
1050  return any_of(V->users(), [&Exits, &BlocksInRegion](User *U) {
1051  Instruction *I = dyn_cast<Instruction>(U);
1052  if (!I)
1053  return false;
1054 
1055  // If the use of the item is inside the region, we skip it. Uses
1056  // inside the region give us useful information about how the item could be
1057  // used as an output.
1058  BasicBlock *Parent = I->getParent();
1059  if (BlocksInRegion.contains(Parent))
1060  return false;
1061 
1062  // If it's not a PHINode then we definitely know the use matters. This
1063  // output value will not completely combined with another item in a PHINode
1064  // as it is directly reference by another non-phi instruction
1065  if (!isa<PHINode>(I))
1066  return true;
1067 
1068  // If we have a PHINode outside one of the exit locations, then it
1069  // can be considered an outside use as well. If there is a PHINode
1070  // contained in the Exit where this values use matters, it will be
1071  // caught when we analyze that PHINode.
1072  if (!Exits.contains(Parent))
1073  return true;
1074 
1075  return false;
1076  });
1077 }
1078 
1079 /// Test whether \p CurrentExitFromRegion contains any PhiNodes that should be
1080 /// considered outputs. A PHINodes is an output when more than one incoming
1081 /// value has been marked by the CodeExtractor as an output.
1082 ///
1083 /// \param CurrentExitFromRegion [in] - The block to analyze.
1084 /// \param PotentialExitsFromRegion [in] - The potential exit blocks from the
1085 /// region.
1086 /// \param RegionBlocks [in] - The basic blocks in the region.
1087 /// \param Outputs [in, out] - The existing outputs for the region, we may add
1088 /// PHINodes to this as we find that they replace output values.
1089 /// \param OutputsReplacedByPHINode [out] - A set containing outputs that are
1090 /// totally replaced by a PHINode.
1091 /// \param OutputsWithNonPhiUses [out] - A set containing outputs that are used
1092 /// in PHINodes, but have other uses, and should still be considered outputs.
1094  BasicBlock *CurrentExitFromRegion,
1095  SmallPtrSet<BasicBlock *, 1> &PotentialExitsFromRegion,
1096  DenseSet<BasicBlock *> &RegionBlocks, SetVector<Value *> &Outputs,
1097  DenseSet<Value *> &OutputsReplacedByPHINode,
1098  DenseSet<Value *> &OutputsWithNonPhiUses) {
1099  for (PHINode &PN : CurrentExitFromRegion->phis()) {
1100  // Find all incoming values from the outlining region.
1101  SmallVector<unsigned, 2> IncomingVals;
1102  for (unsigned I = 0, E = PN.getNumIncomingValues(); I < E; ++I)
1103  if (RegionBlocks.contains(PN.getIncomingBlock(I)))
1104  IncomingVals.push_back(I);
1105 
1106  // Do not process PHI if there are no predecessors from region.
1107  unsigned NumIncomingVals = IncomingVals.size();
1108  if (NumIncomingVals == 0)
1109  continue;
1110 
1111  // If there is one predecessor, we mark it as a value that needs to be kept
1112  // as an output.
1113  if (NumIncomingVals == 1) {
1114  Value *V = PN.getIncomingValue(*IncomingVals.begin());
1115  OutputsWithNonPhiUses.insert(V);
1116  OutputsReplacedByPHINode.erase(V);
1117  continue;
1118  }
1119 
1120  // This PHINode will be used as an output value, so we add it to our list.
1121  Outputs.insert(&PN);
1122 
1123  // Not all of the incoming values should be ignored as other inputs and
1124  // outputs may have uses in outlined region. If they have other uses
1125  // outside of the single PHINode we should not skip over it.
1126  for (unsigned Idx : IncomingVals) {
1127  Value *V = PN.getIncomingValue(Idx);
1128  if (outputHasNonPHI(V, Idx, PN, PotentialExitsFromRegion, RegionBlocks)) {
1129  OutputsWithNonPhiUses.insert(V);
1130  OutputsReplacedByPHINode.erase(V);
1131  continue;
1132  }
1133  if (!OutputsWithNonPhiUses.contains(V))
1134  OutputsReplacedByPHINode.insert(V);
1135  }
1136  }
1137 }
1138 
1139 // Represents the type for the unsigned number denoting the output number for
1140 // phi node, along with the canonical number for the exit block.
1141 using ArgLocWithBBCanon = std::pair<unsigned, unsigned>;
1142 // The list of canonical numbers for the incoming values to a PHINode.
1144 // The pair type representing the set of canonical values being combined in the
1145 // PHINode, along with the location data for the PHINode.
1146 using PHINodeData = std::pair<ArgLocWithBBCanon, CanonList>;
1147 
1148 /// Encode \p PND as an integer for easy lookup based on the argument location,
1149 /// the parent BasicBlock canonical numbering, and the canonical numbering of
1150 /// the values stored in the PHINode.
1151 ///
1152 /// \param PND - The data to hash.
1153 /// \returns The hash code of \p PND.
1155  return llvm::hash_combine(
1156  llvm::hash_value(PND.first.first), llvm::hash_value(PND.first.second),
1157  llvm::hash_combine_range(PND.second.begin(), PND.second.end()));
1158 }
1159 
1160 /// Create a special GVN for PHINodes that will be used outside of
1161 /// the region. We create a hash code based on the Canonical number of the
1162 /// parent BasicBlock, the canonical numbering of the values stored in the
1163 /// PHINode and the aggregate argument location. This is used to find whether
1164 /// this PHINode type has been given a canonical numbering already. If not, we
1165 /// assign it a value and store it for later use. The value is returned to
1166 /// identify different output schemes for the set of regions.
1167 ///
1168 /// \param Region - The region that \p PN is an output for.
1169 /// \param PN - The PHINode we are analyzing.
1170 /// \param Blocks - The blocks for the region we are analyzing.
1171 /// \param AggArgIdx - The argument \p PN will be stored into.
1172 /// \returns An optional holding the assigned canonical number, or None if
1173 /// there is some attribute of the PHINode blocking it from being used.
1175  PHINode *PN,
1176  DenseSet<BasicBlock *> &Blocks,
1177  unsigned AggArgIdx) {
1178  OutlinableGroup &Group = *Region.Parent;
1179  IRSimilarityCandidate &Cand = *Region.Candidate;
1180  BasicBlock *PHIBB = PN->getParent();
1181  CanonList PHIGVNs;
1182  Value *Incoming;
1183  BasicBlock *IncomingBlock;
1184  for (unsigned Idx = 0, EIdx = PN->getNumIncomingValues(); Idx < EIdx; Idx++) {
1185  Incoming = PN->getIncomingValue(Idx);
1186  IncomingBlock = PN->getIncomingBlock(Idx);
1187  // If we cannot find a GVN, and the incoming block is included in the region
1188  // this means that the input to the PHINode is not included in the region we
1189  // are trying to analyze, meaning, that if it was outlined, we would be
1190  // adding an extra input. We ignore this case for now, and so ignore the
1191  // region.
1192  Optional<unsigned> OGVN = Cand.getGVN(Incoming);
1193  if (!OGVN && Blocks.contains(IncomingBlock)) {
1194  Region.IgnoreRegion = true;
1195  return None;
1196  }
1197 
1198  // If the incoming block isn't in the region, we don't have to worry about
1199  // this incoming value.
1200  if (!Blocks.contains(IncomingBlock))
1201  continue;
1202 
1203  // Collect the canonical numbers of the values in the PHINode.
1204  unsigned GVN = *OGVN;
1205  OGVN = Cand.getCanonicalNum(GVN);
1206  assert(OGVN && "No GVN found for incoming value?");
1207  PHIGVNs.push_back(*OGVN);
1208 
1209  // Find the incoming block and use the canonical numbering as well to define
1210  // the hash for the PHINode.
1211  OGVN = Cand.getGVN(IncomingBlock);
1212 
1213  // If there is no number for the incoming block, it is because we have
1214  // split the candidate basic blocks. So we use the previous block that it
1215  // was split from to find the valid global value numbering for the PHINode.
1216  if (!OGVN) {
1217  assert(Cand.getStartBB() == IncomingBlock &&
1218  "Unknown basic block used in exit path PHINode.");
1219 
1220  BasicBlock *PrevBlock = nullptr;
1221  // Iterate over the predecessors to the incoming block of the
1222  // PHINode, when we find a block that is not contained in the region
1223  // we know that this is the first block that we split from, and should
1224  // have a valid global value numbering.
1225  for (BasicBlock *Pred : predecessors(IncomingBlock))
1226  if (!Blocks.contains(Pred)) {
1227  PrevBlock = Pred;
1228  break;
1229  }
1230  assert(PrevBlock && "Expected a predecessor not in the reigon!");
1231  OGVN = Cand.getGVN(PrevBlock);
1232  }
1233  GVN = *OGVN;
1234  OGVN = Cand.getCanonicalNum(GVN);
1235  assert(OGVN && "No GVN found for incoming block?");
1236  PHIGVNs.push_back(*OGVN);
1237  }
1238 
1239  // Now that we have the GVNs for the incoming values, we are going to combine
1240  // them with the GVN of the incoming bock, and the output location of the
1241  // PHINode to generate a hash value representing this instance of the PHINode.
1244  Optional<unsigned> BBGVN = Cand.getGVN(PHIBB);
1245  assert(BBGVN && "Could not find GVN for the incoming block!");
1246 
1247  BBGVN = Cand.getCanonicalNum(BBGVN.value());
1248  assert(BBGVN && "Could not find canonical number for the incoming block!");
1249  // Create a pair of the exit block canonical value, and the aggregate
1250  // argument location, connected to the canonical numbers stored in the
1251  // PHINode.
1252  PHINodeData TemporaryPair =
1253  std::make_pair(std::make_pair(BBGVN.value(), AggArgIdx), PHIGVNs);
1254  hash_code PHINodeDataHash = encodePHINodeData(TemporaryPair);
1255 
1256  // Look for and create a new entry in our connection between canonical
1257  // numbers for PHINodes, and the set of objects we just created.
1258  GVNToPHIIt = Group.GVNsToPHINodeGVN.find(PHINodeDataHash);
1259  if (GVNToPHIIt == Group.GVNsToPHINodeGVN.end()) {
1260  bool Inserted = false;
1261  std::tie(PHIToGVNIt, Inserted) = Group.PHINodeGVNToGVNs.insert(
1262  std::make_pair(Group.PHINodeGVNTracker, TemporaryPair));
1263  std::tie(GVNToPHIIt, Inserted) = Group.GVNsToPHINodeGVN.insert(
1264  std::make_pair(PHINodeDataHash, Group.PHINodeGVNTracker--));
1265  }
1266 
1267  return GVNToPHIIt->second;
1268 }
1269 
1270 /// Create a mapping of the output arguments for the \p Region to the output
1271 /// arguments of the overall outlined function.
1272 ///
1273 /// \param [in,out] Region - The region of code to be analyzed.
1274 /// \param [in] Outputs - The values found by the code extractor.
1275 static void
1277  SetVector<Value *> &Outputs) {
1278  OutlinableGroup &Group = *Region.Parent;
1279  IRSimilarityCandidate &C = *Region.Candidate;
1280 
1282  DenseSet<BasicBlock *> BlocksInRegion;
1283  C.getBasicBlocks(BlocksInRegion, BE);
1284 
1285  // Find the exits to the region.
1287  for (BasicBlock *Block : BE)
1288  for (BasicBlock *Succ : successors(Block))
1289  if (!BlocksInRegion.contains(Succ))
1290  Exits.insert(Succ);
1291 
1292  // After determining which blocks exit to PHINodes, we add these PHINodes to
1293  // the set of outputs to be processed. We also check the incoming values of
1294  // the PHINodes for whether they should no longer be considered outputs.
1295  DenseSet<Value *> OutputsReplacedByPHINode;
1296  DenseSet<Value *> OutputsWithNonPhiUses;
1297  for (BasicBlock *ExitBB : Exits)
1298  analyzeExitPHIsForOutputUses(ExitBB, Exits, BlocksInRegion, Outputs,
1299  OutputsReplacedByPHINode,
1300  OutputsWithNonPhiUses);
1301 
1302  // This counts the argument number in the extracted function.
1303  unsigned OriginalIndex = Region.NumExtractedInputs;
1304 
1305  // This counts the argument number in the overall function.
1306  unsigned TypeIndex = Group.NumAggregateInputs;
1307  bool TypeFound;
1308  DenseSet<unsigned> AggArgsUsed;
1309 
1310  // Iterate over the output types and identify if there is an aggregate pointer
1311  // type whose base type matches the current output type. If there is, we mark
1312  // that we will use this output register for this value. If not we add another
1313  // type to the overall argument type list. We also store the GVNs used for
1314  // stores to identify which values will need to be moved into an special
1315  // block that holds the stores to the output registers.
1316  for (Value *Output : Outputs) {
1317  TypeFound = false;
1318  // We can do this since it is a result value, and will have a number
1319  // that is necessarily the same. BUT if in the future, the instructions
1320  // do not have to be in same order, but are functionally the same, we will
1321  // have to use a different scheme, as one-to-one correspondence is not
1322  // guaranteed.
1323  unsigned ArgumentSize = Group.ArgumentTypes.size();
1324 
1325  // If the output is combined in a PHINode, we make sure to skip over it.
1326  if (OutputsReplacedByPHINode.contains(Output))
1327  continue;
1328 
1329  unsigned AggArgIdx = 0;
1330  for (unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
1331  if (Group.ArgumentTypes[Jdx] != PointerType::getUnqual(Output->getType()))
1332  continue;
1333 
1334  if (AggArgsUsed.contains(Jdx))
1335  continue;
1336 
1337  TypeFound = true;
1338  AggArgsUsed.insert(Jdx);
1339  Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
1340  Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
1341  AggArgIdx = Jdx;
1342  break;
1343  }
1344 
1345  // We were unable to find an unused type in the output type set that matches
1346  // the output, so we add a pointer type to the argument types of the overall
1347  // function to handle this output and create a mapping to it.
1348  if (!TypeFound) {
1349  Group.ArgumentTypes.push_back(PointerType::getUnqual(Output->getType()));
1350  // Mark the new pointer type as the last value in the aggregate argument
1351  // list.
1352  unsigned ArgTypeIdx = Group.ArgumentTypes.size() - 1;
1353  AggArgsUsed.insert(ArgTypeIdx);
1354  Region.ExtractedArgToAgg.insert(
1355  std::make_pair(OriginalIndex, ArgTypeIdx));
1356  Region.AggArgToExtracted.insert(
1357  std::make_pair(ArgTypeIdx, OriginalIndex));
1358  AggArgIdx = ArgTypeIdx;
1359  }
1360 
1361  // TODO: Adapt to the extra input from the PHINode.
1362  PHINode *PN = dyn_cast<PHINode>(Output);
1363 
1364  Optional<unsigned> GVN;
1365  if (PN && !BlocksInRegion.contains(PN->getParent())) {
1366  // Values outside the region can be combined into PHINode when we
1367  // have multiple exits. We collect both of these into a list to identify
1368  // which values are being used in the PHINode. Each list identifies a
1369  // different PHINode, and a different output. We store the PHINode as it's
1370  // own canonical value. These canonical values are also dependent on the
1371  // output argument it is saved to.
1372 
1373  // If two PHINodes have the same canonical values, but different aggregate
1374  // argument locations, then they will have distinct Canonical Values.
1375  GVN = getGVNForPHINode(Region, PN, BlocksInRegion, AggArgIdx);
1376  if (!GVN)
1377  return;
1378  } else {
1379  // If we do not have a PHINode we use the global value numbering for the
1380  // output value, to find the canonical number to add to the set of stored
1381  // values.
1382  GVN = C.getGVN(Output);
1383  GVN = C.getCanonicalNum(*GVN);
1384  }
1385 
1386  // Each region has a potentially unique set of outputs. We save which
1387  // values are output in a list of canonical values so we can differentiate
1388  // among the different store schemes.
1389  Region.GVNStores.push_back(*GVN);
1390 
1391  OriginalIndex++;
1392  TypeIndex++;
1393  }
1394 
1395  // We sort the stored values to make sure that we are not affected by analysis
1396  // order when determining what combination of items were stored.
1397  stable_sort(Region.GVNStores);
1398 }
1399 
1400 void IROutliner::findAddInputsOutputs(Module &M, OutlinableRegion &Region,
1401  DenseSet<unsigned> &NotSame) {
1402  std::vector<unsigned> Inputs;
1403  SetVector<Value *> ArgInputs, Outputs;
1404 
1405  getCodeExtractorArguments(Region, Inputs, NotSame, OutputMappings, ArgInputs,
1406  Outputs);
1407 
1408  if (Region.IgnoreRegion)
1409  return;
1410 
1411  // Map the inputs found by the CodeExtractor to the arguments found for
1412  // the overall function.
1413  findExtractedInputToOverallInputMapping(Region, Inputs, ArgInputs);
1414 
1415  // Map the outputs found by the CodeExtractor to the arguments found for
1416  // the overall function.
1418 }
1419 
1420 /// Replace the extracted function in the Region with a call to the overall
1421 /// function constructed from the deduplicated similar regions, replacing and
1422 /// remapping the values passed to the extracted function as arguments to the
1423 /// new arguments of the overall function.
1424 ///
1425 /// \param [in] M - The module to outline from.
1426 /// \param [in] Region - The regions of extracted code to be replaced with a new
1427 /// function.
1428 /// \returns a call instruction with the replaced function.
1430  std::vector<Value *> NewCallArgs;
1432 
1433  OutlinableGroup &Group = *Region.Parent;
1434  CallInst *Call = Region.Call;
1435  assert(Call && "Call to replace is nullptr?");
1436  Function *AggFunc = Group.OutlinedFunction;
1437  assert(AggFunc && "Function to replace with is nullptr?");
1438 
1439  // If the arguments are the same size, there are not values that need to be
1440  // made into an argument, the argument ordering has not been change, or
1441  // different output registers to handle. We can simply replace the called
1442  // function in this case.
1443  if (!Region.ChangedArgOrder && AggFunc->arg_size() == Call->arg_size()) {
1444  LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "
1445  << *AggFunc << " with same number of arguments\n");
1446  Call->setCalledFunction(AggFunc);
1447  return Call;
1448  }
1449 
1450  // We have a different number of arguments than the new function, so
1451  // we need to use our previously mappings off extracted argument to overall
1452  // function argument, and constants to overall function argument to create the
1453  // new argument list.
1454  for (unsigned AggArgIdx = 0; AggArgIdx < AggFunc->arg_size(); AggArgIdx++) {
1455 
1456  if (AggArgIdx == AggFunc->arg_size() - 1 &&
1457  Group.OutputGVNCombinations.size() > 1) {
1458  // If we are on the last argument, and we need to differentiate between
1459  // output blocks, add an integer to the argument list to determine
1460  // what block to take
1461  LLVM_DEBUG(dbgs() << "Set switch block argument to "
1462  << Region.OutputBlockNum << "\n");
1463  NewCallArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()),
1464  Region.OutputBlockNum));
1465  continue;
1466  }
1467 
1468  ArgPair = Region.AggArgToExtracted.find(AggArgIdx);
1469  if (ArgPair != Region.AggArgToExtracted.end()) {
1470  Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
1471  // If we found the mapping from the extracted function to the overall
1472  // function, we simply add it to the argument list. We use the same
1473  // value, it just needs to honor the new order of arguments.
1474  LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "
1475  << *ArgumentValue << "\n");
1476  NewCallArgs.push_back(ArgumentValue);
1477  continue;
1478  }
1479 
1480  // If it is a constant, we simply add it to the argument list as a value.
1481  if (Region.AggArgToConstant.find(AggArgIdx) !=
1482  Region.AggArgToConstant.end()) {
1483  Constant *CST = Region.AggArgToConstant.find(AggArgIdx)->second;
1484  LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "
1485  << *CST << "\n");
1486  NewCallArgs.push_back(CST);
1487  continue;
1488  }
1489 
1490  // Add a nullptr value if the argument is not found in the extracted
1491  // function. If we cannot find a value, it means it is not in use
1492  // for the region, so we should not pass anything to it.
1493  LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to nullptr\n");
1494  NewCallArgs.push_back(ConstantPointerNull::get(
1495  static_cast<PointerType *>(AggFunc->getArg(AggArgIdx)->getType())));
1496  }
1497 
1498  LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "
1499  << *AggFunc << " with new set of arguments\n");
1500  // Create the new call instruction and erase the old one.
1501  Call = CallInst::Create(AggFunc->getFunctionType(), AggFunc, NewCallArgs, "",
1502  Call);
1503 
1504  // It is possible that the call to the outlined function is either the first
1505  // instruction is in the new block, the last instruction, or both. If either
1506  // of these is the case, we need to make sure that we replace the instruction
1507  // in the IRInstructionData struct with the new call.
1508  CallInst *OldCall = Region.Call;
1509  if (Region.NewFront->Inst == OldCall)
1510  Region.NewFront->Inst = Call;
1511  if (Region.NewBack->Inst == OldCall)
1512  Region.NewBack->Inst = Call;
1513 
1514  // Transfer any debug information.
1515  Call->setDebugLoc(Region.Call->getDebugLoc());
1516  // Since our output may determine which branch we go to, we make sure to
1517  // propogate this new call value through the module.
1518  OldCall->replaceAllUsesWith(Call);
1519 
1520  // Remove the old instruction.
1521  OldCall->eraseFromParent();
1522  Region.Call = Call;
1523 
1524  // Make sure that the argument in the new function has the SwiftError
1525  // argument.
1526  if (Group.SwiftErrorArgument)
1527  Call->addParamAttr(Group.SwiftErrorArgument.value(), Attribute::SwiftError);
1528 
1529  return Call;
1530 }
1531 
1532 /// Find or create a BasicBlock in the outlined function containing PhiBlocks
1533 /// for \p RetVal.
1534 ///
1535 /// \param Group - The OutlinableGroup containing the information about the
1536 /// overall outlined function.
1537 /// \param RetVal - The return value or exit option that we are currently
1538 /// evaluating.
1539 /// \returns The found or newly created BasicBlock to contain the needed
1540 /// PHINodes to be used as outputs.
1543  ReturnBlockForRetVal;
1544  PhiBlockForRetVal = Group.PHIBlocks.find(RetVal);
1545  ReturnBlockForRetVal = Group.EndBBs.find(RetVal);
1546  assert(ReturnBlockForRetVal != Group.EndBBs.end() &&
1547  "Could not find output value!");
1548  BasicBlock *ReturnBB = ReturnBlockForRetVal->second;
1549 
1550  // Find if a PHIBlock exists for this return value already. If it is
1551  // the first time we are analyzing this, we will not, so we record it.
1552  PhiBlockForRetVal = Group.PHIBlocks.find(RetVal);
1553  if (PhiBlockForRetVal != Group.PHIBlocks.end())
1554  return PhiBlockForRetVal->second;
1555 
1556  // If we did not find a block, we create one, and insert it into the
1557  // overall function and record it.
1558  bool Inserted = false;
1559  BasicBlock *PHIBlock = BasicBlock::Create(ReturnBB->getContext(), "phi_block",
1560  ReturnBB->getParent());
1561  std::tie(PhiBlockForRetVal, Inserted) =
1562  Group.PHIBlocks.insert(std::make_pair(RetVal, PHIBlock));
1563 
1564  // We find the predecessors of the return block in the newly created outlined
1565  // function in order to point them to the new PHIBlock rather than the already
1566  // existing return block.
1567  SmallVector<BranchInst *, 2> BranchesToChange;
1568  for (BasicBlock *Pred : predecessors(ReturnBB))
1569  BranchesToChange.push_back(cast<BranchInst>(Pred->getTerminator()));
1570 
1571  // Now we mark the branch instructions found, and change the references of the
1572  // return block to the newly created PHIBlock.
1573  for (BranchInst *BI : BranchesToChange)
1574  for (unsigned Succ = 0, End = BI->getNumSuccessors(); Succ < End; Succ++) {
1575  if (BI->getSuccessor(Succ) != ReturnBB)
1576  continue;
1577  BI->setSuccessor(Succ, PHIBlock);
1578  }
1579 
1580  BranchInst::Create(ReturnBB, PHIBlock);
1581 
1582  return PhiBlockForRetVal->second;
1583 }
1584 
1585 /// For the function call now representing the \p Region, find the passed value
1586 /// to that call that represents Argument \p A at the call location if the
1587 /// call has already been replaced with a call to the overall, aggregate
1588 /// function.
1589 ///
1590 /// \param A - The Argument to get the passed value for.
1591 /// \param Region - The extracted Region corresponding to the outlined function.
1592 /// \returns The Value representing \p A at the call site.
1593 static Value *
1595  const OutlinableRegion &Region) {
1596  // If we don't need to adjust the argument number at all (since the call
1597  // has already been replaced by a call to the overall outlined function)
1598  // we can just get the specified argument.
1599  return Region.Call->getArgOperand(A->getArgNo());
1600 }
1601 
1602 /// For the function call now representing the \p Region, find the passed value
1603 /// to that call that represents Argument \p A at the call location if the
1604 /// call has only been replaced by the call to the aggregate function.
1605 ///
1606 /// \param A - The Argument to get the passed value for.
1607 /// \param Region - The extracted Region corresponding to the outlined function.
1608 /// \returns The Value representing \p A at the call site.
1609 static Value *
1611  const OutlinableRegion &Region) {
1612  unsigned ArgNum = A->getArgNo();
1613 
1614  // If it is a constant, we can look at our mapping from when we created
1615  // the outputs to figure out what the constant value is.
1616  if (Region.AggArgToConstant.count(ArgNum))
1617  return Region.AggArgToConstant.find(ArgNum)->second;
1618 
1619  // If it is not a constant, and we are not looking at the overall function, we
1620  // need to adjust which argument we are looking at.
1621  ArgNum = Region.AggArgToExtracted.find(ArgNum)->second;
1622  return Region.Call->getArgOperand(ArgNum);
1623 }
1624 
1625 /// Find the canonical numbering for the incoming Values into the PHINode \p PN.
1626 ///
1627 /// \param PN [in] - The PHINode that we are finding the canonical numbers for.
1628 /// \param Region [in] - The OutlinableRegion containing \p PN.
1629 /// \param OutputMappings [in] - The mapping of output values from outlined
1630 /// region to their original values.
1631 /// \param CanonNums [out] - The canonical numbering for the incoming values to
1632 /// \p PN paired with their incoming block.
1633 /// \param ReplacedWithOutlinedCall - A flag to use the extracted function call
1634 /// of \p Region rather than the overall function's call.
1637  const DenseMap<Value *, Value *> &OutputMappings,
1638  SmallVector<std::pair<unsigned, BasicBlock *>> &CanonNums,
1639  bool ReplacedWithOutlinedCall = true) {
1640  // Iterate over the incoming values.
1641  for (unsigned Idx = 0, EIdx = PN->getNumIncomingValues(); Idx < EIdx; Idx++) {
1642  Value *IVal = PN->getIncomingValue(Idx);
1643  BasicBlock *IBlock = PN->getIncomingBlock(Idx);
1644  // If we have an argument as incoming value, we need to grab the passed
1645  // value from the call itself.
1646  if (Argument *A = dyn_cast<Argument>(IVal)) {
1647  if (ReplacedWithOutlinedCall)
1649  else
1651  }
1652 
1653  // Get the original value if it has been replaced by an output value.
1654  IVal = findOutputMapping(OutputMappings, IVal);
1655 
1656  // Find and add the canonical number for the incoming value.
1657  Optional<unsigned> GVN = Region.Candidate->getGVN(IVal);
1658  assert(GVN && "No GVN for incoming value");
1659  Optional<unsigned> CanonNum = Region.Candidate->getCanonicalNum(*GVN);
1660  assert(CanonNum && "No Canonical Number for GVN");
1661  CanonNums.push_back(std::make_pair(*CanonNum, IBlock));
1662  }
1663 }
1664 
1665 /// Find, or add PHINode \p PN to the combined PHINode Block \p OverallPHIBlock
1666 /// in order to condense the number of instructions added to the outlined
1667 /// function.
1668 ///
1669 /// \param PN [in] - The PHINode that we are finding the canonical numbers for.
1670 /// \param Region [in] - The OutlinableRegion containing \p PN.
1671 /// \param OverallPhiBlock [in] - The overall PHIBlock we are trying to find
1672 /// \p PN in.
1673 /// \param OutputMappings [in] - The mapping of output values from outlined
1674 /// region to their original values.
1675 /// \param UsedPHIs [in, out] - The PHINodes in the block that have already been
1676 /// matched.
1677 /// \return the newly found or created PHINode in \p OverallPhiBlock.
1678 static PHINode*
1680  BasicBlock *OverallPhiBlock,
1681  const DenseMap<Value *, Value *> &OutputMappings,
1682  DenseSet<PHINode *> &UsedPHIs) {
1683  OutlinableGroup &Group = *Region.Parent;
1684 
1685 
1686  // A list of the canonical numbering assigned to each incoming value, paired
1687  // with the incoming block for the PHINode passed into this function.
1689 
1690  // We have to use the extracted function since we have merged this region into
1691  // the overall function yet. We make sure to reassign the argument numbering
1692  // since it is possible that the argument ordering is different between the
1693  // functions.
1694  findCanonNumsForPHI(&PN, Region, OutputMappings, PNCanonNums,
1695  /* ReplacedWithOutlinedCall = */ false);
1696 
1697  OutlinableRegion *FirstRegion = Group.Regions[0];
1698 
1699  // A list of the canonical numbering assigned to each incoming value, paired
1700  // with the incoming block for the PHINode that we are currently comparing
1701  // the passed PHINode to.
1703 
1704  // Find the Canonical Numbering for each PHINode, if it matches, we replace
1705  // the uses of the PHINode we are searching for, with the found PHINode.
1706  for (PHINode &CurrPN : OverallPhiBlock->phis()) {
1707  // If this PHINode has already been matched to another PHINode to be merged,
1708  // we skip it.
1709  if (UsedPHIs.contains(&CurrPN))
1710  continue;
1711 
1712  CurrentCanonNums.clear();
1713  findCanonNumsForPHI(&CurrPN, *FirstRegion, OutputMappings, CurrentCanonNums,
1714  /* ReplacedWithOutlinedCall = */ true);
1715 
1716  // If the list of incoming values is not the same length, then they cannot
1717  // match since there is not an analogue for each incoming value.
1718  if (PNCanonNums.size() != CurrentCanonNums.size())
1719  continue;
1720 
1721  bool FoundMatch = true;
1722 
1723  // We compare the canonical value for each incoming value in the passed
1724  // in PHINode to one already present in the outlined region. If the
1725  // incoming values do not match, then the PHINodes do not match.
1726 
1727  // We also check to make sure that the incoming block matches as well by
1728  // finding the corresponding incoming block in the combined outlined region
1729  // for the current outlined region.
1730  for (unsigned Idx = 0, Edx = PNCanonNums.size(); Idx < Edx; ++Idx) {
1731  std::pair<unsigned, BasicBlock *> ToCompareTo = CurrentCanonNums[Idx];
1732  std::pair<unsigned, BasicBlock *> ToAdd = PNCanonNums[Idx];
1733  if (ToCompareTo.first != ToAdd.first) {
1734  FoundMatch = false;
1735  break;
1736  }
1737 
1738  BasicBlock *CorrespondingBlock =
1739  Region.findCorrespondingBlockIn(*FirstRegion, ToAdd.second);
1740  assert(CorrespondingBlock && "Found block is nullptr");
1741  if (CorrespondingBlock != ToCompareTo.second) {
1742  FoundMatch = false;
1743  break;
1744  }
1745  }
1746 
1747  // If all incoming values and branches matched, then we can merge
1748  // into the found PHINode.
1749  if (FoundMatch) {
1750  UsedPHIs.insert(&CurrPN);
1751  return &CurrPN;
1752  }
1753  }
1754 
1755  // If we've made it here, it means we weren't able to replace the PHINode, so
1756  // we must insert it ourselves.
1757  PHINode *NewPN = cast<PHINode>(PN.clone());
1758  NewPN->insertBefore(&*OverallPhiBlock->begin());
1759  for (unsigned Idx = 0, Edx = NewPN->getNumIncomingValues(); Idx < Edx;
1760  Idx++) {
1761  Value *IncomingVal = NewPN->getIncomingValue(Idx);
1762  BasicBlock *IncomingBlock = NewPN->getIncomingBlock(Idx);
1763 
1764  // Find corresponding basic block in the overall function for the incoming
1765  // block.
1766  BasicBlock *BlockToUse =
1767  Region.findCorrespondingBlockIn(*FirstRegion, IncomingBlock);
1768  NewPN->setIncomingBlock(Idx, BlockToUse);
1769 
1770  // If we have an argument we make sure we replace using the argument from
1771  // the correct function.
1772  if (Argument *A = dyn_cast<Argument>(IncomingVal)) {
1773  Value *Val = Group.OutlinedFunction->getArg(A->getArgNo());
1774  NewPN->setIncomingValue(Idx, Val);
1775  continue;
1776  }
1777 
1778  // Find the corresponding value in the overall function.
1779  IncomingVal = findOutputMapping(OutputMappings, IncomingVal);
1780  Value *Val = Region.findCorrespondingValueIn(*FirstRegion, IncomingVal);
1781  assert(Val && "Value is nullptr?");
1783  FirstRegion->RemappedArguments.find(Val);
1784  if (RemappedIt != FirstRegion->RemappedArguments.end())
1785  Val = RemappedIt->second;
1786  NewPN->setIncomingValue(Idx, Val);
1787  }
1788  return NewPN;
1789 }
1790 
1791 // Within an extracted function, replace the argument uses of the extracted
1792 // region with the arguments of the function for an OutlinableGroup.
1793 //
1794 /// \param [in] Region - The region of extracted code to be changed.
1795 /// \param [in,out] OutputBBs - The BasicBlock for the output stores for this
1796 /// region.
1797 /// \param [in] FirstFunction - A flag to indicate whether we are using this
1798 /// function to define the overall outlined function for all the regions, or
1799 /// if we are operating on one of the following regions.
1800 static void
1803  const DenseMap<Value *, Value *> &OutputMappings,
1804  bool FirstFunction = false) {
1805  OutlinableGroup &Group = *Region.Parent;
1806  assert(Region.ExtractedFunction && "Region has no extracted function?");
1807 
1808  Function *DominatingFunction = Region.ExtractedFunction;
1809  if (FirstFunction)
1810  DominatingFunction = Group.OutlinedFunction;
1811  DominatorTree DT(*DominatingFunction);
1812  DenseSet<PHINode *> UsedPHIs;
1813 
1814  for (unsigned ArgIdx = 0; ArgIdx < Region.ExtractedFunction->arg_size();
1815  ArgIdx++) {
1816  assert(Region.ExtractedArgToAgg.find(ArgIdx) !=
1817  Region.ExtractedArgToAgg.end() &&
1818  "No mapping from extracted to outlined?");
1819  unsigned AggArgIdx = Region.ExtractedArgToAgg.find(ArgIdx)->second;
1820  Argument *AggArg = Group.OutlinedFunction->getArg(AggArgIdx);
1821  Argument *Arg = Region.ExtractedFunction->getArg(ArgIdx);
1822  // The argument is an input, so we can simply replace it with the overall
1823  // argument value
1824  if (ArgIdx < Region.NumExtractedInputs) {
1825  LLVM_DEBUG(dbgs() << "Replacing uses of input " << *Arg << " in function "
1826  << *Region.ExtractedFunction << " with " << *AggArg
1827  << " in function " << *Group.OutlinedFunction << "\n");
1828  Arg->replaceAllUsesWith(AggArg);
1829  Value *V = Region.Call->getArgOperand(ArgIdx);
1830  Region.RemappedArguments.insert(std::make_pair(V, AggArg));
1831  continue;
1832  }
1833 
1834  // If we are replacing an output, we place the store value in its own
1835  // block inside the overall function before replacing the use of the output
1836  // in the function.
1837  assert(Arg->hasOneUse() && "Output argument can only have one use");
1838  User *InstAsUser = Arg->user_back();
1839  assert(InstAsUser && "User is nullptr!");
1840 
1841  Instruction *I = cast<Instruction>(InstAsUser);
1842  BasicBlock *BB = I->getParent();
1843  SmallVector<BasicBlock *, 4> Descendants;
1844  DT.getDescendants(BB, Descendants);
1845  bool EdgeAdded = false;
1846  if (Descendants.size() == 0) {
1847  EdgeAdded = true;
1848  DT.insertEdge(&DominatingFunction->getEntryBlock(), BB);
1849  DT.getDescendants(BB, Descendants);
1850  }
1851 
1852  // Iterate over the following blocks, looking for return instructions,
1853  // if we find one, find the corresponding output block for the return value
1854  // and move our store instruction there.
1855  for (BasicBlock *DescendBB : Descendants) {
1856  ReturnInst *RI = dyn_cast<ReturnInst>(DescendBB->getTerminator());
1857  if (!RI)
1858  continue;
1859  Value *RetVal = RI->getReturnValue();
1860  auto VBBIt = OutputBBs.find(RetVal);
1861  assert(VBBIt != OutputBBs.end() && "Could not find output value!");
1862 
1863  // If this is storing a PHINode, we must make sure it is included in the
1864  // overall function.
1865  StoreInst *SI = cast<StoreInst>(I);
1866 
1867  Value *ValueOperand = SI->getValueOperand();
1868 
1869  StoreInst *NewI = cast<StoreInst>(I->clone());
1870  NewI->setDebugLoc(DebugLoc());
1871  BasicBlock *OutputBB = VBBIt->second;
1872  OutputBB->getInstList().push_back(NewI);
1873  LLVM_DEBUG(dbgs() << "Move store for instruction " << *I << " to "
1874  << *OutputBB << "\n");
1875 
1876  // If this is storing a PHINode, we must make sure it is included in the
1877  // overall function.
1878  if (!isa<PHINode>(ValueOperand) ||
1879  Region.Candidate->getGVN(ValueOperand).has_value()) {
1880  if (FirstFunction)
1881  continue;
1882  Value *CorrVal =
1883  Region.findCorrespondingValueIn(*Group.Regions[0], ValueOperand);
1884  assert(CorrVal && "Value is nullptr?");
1885  NewI->setOperand(0, CorrVal);
1886  continue;
1887  }
1888  PHINode *PN = cast<PHINode>(SI->getValueOperand());
1889  // If it has a value, it was not split by the code extractor, which
1890  // is what we are looking for.
1891  if (Region.Candidate->getGVN(PN))
1892  continue;
1893 
1894  // We record the parent block for the PHINode in the Region so that
1895  // we can exclude it from checks later on.
1896  Region.PHIBlocks.insert(std::make_pair(RetVal, PN->getParent()));
1897 
1898  // If this is the first function, we do not need to worry about mergiing
1899  // this with any other block in the overall outlined function, so we can
1900  // just continue.
1901  if (FirstFunction) {
1902  BasicBlock *PHIBlock = PN->getParent();
1903  Group.PHIBlocks.insert(std::make_pair(RetVal, PHIBlock));
1904  continue;
1905  }
1906 
1907  // We look for the aggregate block that contains the PHINodes leading into
1908  // this exit path. If we can't find one, we create one.
1909  BasicBlock *OverallPhiBlock = findOrCreatePHIBlock(Group, RetVal);
1910 
1911  // For our PHINode, we find the combined canonical numbering, and
1912  // attempt to find a matching PHINode in the overall PHIBlock. If we
1913  // cannot, we copy the PHINode and move it into this new block.
1914  PHINode *NewPN = findOrCreatePHIInBlock(*PN, Region, OverallPhiBlock,
1915  OutputMappings, UsedPHIs);
1916  NewI->setOperand(0, NewPN);
1917  }
1918 
1919  // If we added an edge for basic blocks without a predecessor, we remove it
1920  // here.
1921  if (EdgeAdded)
1922  DT.deleteEdge(&DominatingFunction->getEntryBlock(), BB);
1923  I->eraseFromParent();
1924 
1925  LLVM_DEBUG(dbgs() << "Replacing uses of output " << *Arg << " in function "
1926  << *Region.ExtractedFunction << " with " << *AggArg
1927  << " in function " << *Group.OutlinedFunction << "\n");
1928  Arg->replaceAllUsesWith(AggArg);
1929  }
1930 }
1931 
1932 /// Within an extracted function, replace the constants that need to be lifted
1933 /// into arguments with the actual argument.
1934 ///
1935 /// \param Region [in] - The region of extracted code to be changed.
1937  OutlinableGroup &Group = *Region.Parent;
1938  // Iterate over the constants that need to be elevated into arguments
1939  for (std::pair<unsigned, Constant *> &Const : Region.AggArgToConstant) {
1940  unsigned AggArgIdx = Const.first;
1941  Function *OutlinedFunction = Group.OutlinedFunction;
1942  assert(OutlinedFunction && "Overall Function is not defined?");
1943  Constant *CST = Const.second;
1944  Argument *Arg = Group.OutlinedFunction->getArg(AggArgIdx);
1945  // Identify the argument it will be elevated to, and replace instances of
1946  // that constant in the function.
1947 
1948  // TODO: If in the future constants do not have one global value number,
1949  // i.e. a constant 1 could be mapped to several values, this check will
1950  // have to be more strict. It cannot be using only replaceUsesWithIf.
1951 
1952  LLVM_DEBUG(dbgs() << "Replacing uses of constant " << *CST
1953  << " in function " << *OutlinedFunction << " with "
1954  << *Arg << "\n");
1955  CST->replaceUsesWithIf(Arg, [OutlinedFunction](Use &U) {
1956  if (Instruction *I = dyn_cast<Instruction>(U.getUser()))
1957  return I->getFunction() == OutlinedFunction;
1958  return false;
1959  });
1960  }
1961 }
1962 
1963 /// It is possible that there is a basic block that already performs the same
1964 /// stores. This returns a duplicate block, if it exists
1965 ///
1966 /// \param OutputBBs [in] the blocks we are looking for a duplicate of.
1967 /// \param OutputStoreBBs [in] The existing output blocks.
1968 /// \returns an optional value with the number output block if there is a match.
1971  std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) {
1972 
1973  bool Mismatch = false;
1974  unsigned MatchingNum = 0;
1975  // We compare the new set output blocks to the other sets of output blocks.
1976  // If they are the same number, and have identical instructions, they are
1977  // considered to be the same.
1978  for (DenseMap<Value *, BasicBlock *> &CompBBs : OutputStoreBBs) {
1979  Mismatch = false;
1980  for (std::pair<Value *, BasicBlock *> &VToB : CompBBs) {
1982  OutputBBs.find(VToB.first);
1983  if (OutputBBIt == OutputBBs.end()) {
1984  Mismatch = true;
1985  break;
1986  }
1987 
1988  BasicBlock *CompBB = VToB.second;
1989  BasicBlock *OutputBB = OutputBBIt->second;
1990  if (CompBB->size() - 1 != OutputBB->size()) {
1991  Mismatch = true;
1992  break;
1993  }
1994 
1995  BasicBlock::iterator NIt = OutputBB->begin();
1996  for (Instruction &I : *CompBB) {
1997  if (isa<BranchInst>(&I))
1998  continue;
1999 
2000  if (!I.isIdenticalTo(&(*NIt))) {
2001  Mismatch = true;
2002  break;
2003  }
2004 
2005  NIt++;
2006  }
2007  }
2008 
2009  if (!Mismatch)
2010  return MatchingNum;
2011 
2012  MatchingNum++;
2013  }
2014 
2015  return None;
2016 }
2017 
2018 /// Remove empty output blocks from the outlined region.
2019 ///
2020 /// \param BlocksToPrune - Mapping of return values output blocks for the \p
2021 /// Region.
2022 /// \param Region - The OutlinableRegion we are analyzing.
2023 static bool
2026  bool AllRemoved = true;
2027  Value *RetValueForBB;
2028  BasicBlock *NewBB;
2030  // Iterate over the output blocks created in the outlined section.
2031  for (std::pair<Value *, BasicBlock *> &VtoBB : BlocksToPrune) {
2032  RetValueForBB = VtoBB.first;
2033  NewBB = VtoBB.second;
2034 
2035  // If there are no instructions, we remove it from the module, and also
2036  // mark the value for removal from the return value to output block mapping.
2037  if (NewBB->size() == 0) {
2038  NewBB->eraseFromParent();
2039  ToRemove.push_back(RetValueForBB);
2040  continue;
2041  }
2042 
2043  // Mark that we could not remove all the blocks since they were not all
2044  // empty.
2045  AllRemoved = false;
2046  }
2047 
2048  // Remove the return value from the mapping.
2049  for (Value *V : ToRemove)
2050  BlocksToPrune.erase(V);
2051 
2052  // Mark the region as having the no output scheme.
2053  if (AllRemoved)
2054  Region.OutputBlockNum = -1;
2055 
2056  return AllRemoved;
2057 }
2058 
2059 /// For the outlined section, move needed the StoreInsts for the output
2060 /// registers into their own block. Then, determine if there is a duplicate
2061 /// output block already created.
2062 ///
2063 /// \param [in] OG - The OutlinableGroup of regions to be outlined.
2064 /// \param [in] Region - The OutlinableRegion that is being analyzed.
2065 /// \param [in,out] OutputBBs - the blocks that stores for this region will be
2066 /// placed in.
2067 /// \param [in] EndBBs - the final blocks of the extracted function.
2068 /// \param [in] OutputMappings - OutputMappings the mapping of values that have
2069 /// been replaced by a new output value.
2070 /// \param [in,out] OutputStoreBBs - The existing output blocks.
2075  const DenseMap<Value *, Value *> &OutputMappings,
2076  std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) {
2077  // If none of the output blocks have any instructions, this means that we do
2078  // not have to determine if it matches any of the other output schemes, and we
2079  // don't have to do anything else.
2080  if (analyzeAndPruneOutputBlocks(OutputBBs, Region))
2081  return;
2082 
2083  // Determine is there is a duplicate set of blocks.
2084  Optional<unsigned> MatchingBB =
2085  findDuplicateOutputBlock(OutputBBs, OutputStoreBBs);
2086 
2087  // If there is, we remove the new output blocks. If it does not,
2088  // we add it to our list of sets of output blocks.
2089  if (MatchingBB) {
2090  LLVM_DEBUG(dbgs() << "Set output block for region in function"
2091  << Region.ExtractedFunction << " to "
2092  << MatchingBB.value());
2093 
2094  Region.OutputBlockNum = MatchingBB.value();
2095  for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs)
2096  VtoBB.second->eraseFromParent();
2097  return;
2098  }
2099 
2100  Region.OutputBlockNum = OutputStoreBBs.size();
2101 
2102  Value *RetValueForBB;
2103  BasicBlock *NewBB;
2104  OutputStoreBBs.push_back(DenseMap<Value *, BasicBlock *>());
2105  for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs) {
2106  RetValueForBB = VtoBB.first;
2107  NewBB = VtoBB.second;
2109  EndBBs.find(RetValueForBB);
2110  LLVM_DEBUG(dbgs() << "Create output block for region in"
2111  << Region.ExtractedFunction << " to "
2112  << *NewBB);
2113  BranchInst::Create(VBBIt->second, NewBB);
2114  OutputStoreBBs.back().insert(std::make_pair(RetValueForBB, NewBB));
2115  }
2116 }
2117 
2118 /// Takes in a mapping, \p OldMap of ConstantValues to BasicBlocks, sorts keys,
2119 /// before creating a basic block for each \p NewMap, and inserting into the new
2120 /// block. Each BasicBlock is named with the scheme "<basename>_<key_idx>".
2121 ///
2122 /// \param OldMap [in] - The mapping to base the new mapping off of.
2123 /// \param NewMap [out] - The output mapping using the keys of \p OldMap.
2124 /// \param ParentFunc [in] - The function to put the new basic block in.
2125 /// \param BaseName [in] - The start of the BasicBlock names to be appended to
2126 /// by an index value.
2129  Function *ParentFunc, Twine BaseName) {
2130  unsigned Idx = 0;
2131  std::vector<Value *> SortedKeys;
2132 
2133  getSortedConstantKeys(SortedKeys, OldMap);
2134 
2135  for (Value *RetVal : SortedKeys) {
2136  BasicBlock *NewBB = BasicBlock::Create(
2137  ParentFunc->getContext(),
2138  Twine(BaseName) + Twine("_") + Twine(static_cast<unsigned>(Idx++)),
2139  ParentFunc);
2140  NewMap.insert(std::make_pair(RetVal, NewBB));
2141  }
2142 }
2143 
2144 /// Create the switch statement for outlined function to differentiate between
2145 /// all the output blocks.
2146 ///
2147 /// For the outlined section, determine if an outlined block already exists that
2148 /// matches the needed stores for the extracted section.
2149 /// \param [in] M - The module we are outlining from.
2150 /// \param [in] OG - The group of regions to be outlined.
2151 /// \param [in] EndBBs - The final blocks of the extracted function.
2152 /// \param [in,out] OutputStoreBBs - The existing output blocks.
2155  std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) {
2156  // We only need the switch statement if there is more than one store
2157  // combination, or there is more than one set of output blocks. The first
2158  // will occur when we store different sets of values for two different
2159  // regions. The second will occur when we have two outputs that are combined
2160  // in a PHINode outside of the region in one outlined instance, and are used
2161  // seaparately in another. This will create the same set of OutputGVNs, but
2162  // will generate two different output schemes.
2163  if (OG.OutputGVNCombinations.size() > 1) {
2164  Function *AggFunc = OG.OutlinedFunction;
2165  // Create a final block for each different return block.
2167  createAndInsertBasicBlocks(OG.EndBBs, ReturnBBs, AggFunc, "final_block");
2168 
2169  for (std::pair<Value *, BasicBlock *> &RetBlockPair : ReturnBBs) {
2170  std::pair<Value *, BasicBlock *> &OutputBlock =
2171  *OG.EndBBs.find(RetBlockPair.first);
2172  BasicBlock *ReturnBlock = RetBlockPair.second;
2173  BasicBlock *EndBB = OutputBlock.second;
2174  Instruction *Term = EndBB->getTerminator();
2175  // Move the return value to the final block instead of the original exit
2176  // stub.
2177  Term->moveBefore(*ReturnBlock, ReturnBlock->end());
2178  // Put the switch statement in the old end basic block for the function
2179  // with a fall through to the new return block.
2180  LLVM_DEBUG(dbgs() << "Create switch statement in " << *AggFunc << " for "
2181  << OutputStoreBBs.size() << "\n");
2182  SwitchInst *SwitchI =
2183  SwitchInst::Create(AggFunc->getArg(AggFunc->arg_size() - 1),
2184  ReturnBlock, OutputStoreBBs.size(), EndBB);
2185 
2186  unsigned Idx = 0;
2187  for (DenseMap<Value *, BasicBlock *> &OutputStoreBB : OutputStoreBBs) {
2189  OutputStoreBB.find(OutputBlock.first);
2190 
2191  if (OSBBIt == OutputStoreBB.end())
2192  continue;
2193 
2194  BasicBlock *BB = OSBBIt->second;
2195  SwitchI->addCase(
2196  ConstantInt::get(Type::getInt32Ty(M.getContext()), Idx), BB);
2197  Term = BB->getTerminator();
2198  Term->setSuccessor(0, ReturnBlock);
2199  Idx++;
2200  }
2201  }
2202  return;
2203  }
2204 
2205  assert(OutputStoreBBs.size() < 2 && "Different store sets not handled!");
2206 
2207  // If there needs to be stores, move them from the output blocks to their
2208  // corresponding ending block. We do not check that the OutputGVNCombinations
2209  // is equal to 1 here since that could just been the case where there are 0
2210  // outputs. Instead, we check whether there is more than one set of output
2211  // blocks since this is the only case where we would have to move the
2212  // stores, and erase the extraneous blocks.
2213  if (OutputStoreBBs.size() == 1) {
2214  LLVM_DEBUG(dbgs() << "Move store instructions to the end block in "
2215  << *OG.OutlinedFunction << "\n");
2216  DenseMap<Value *, BasicBlock *> OutputBlocks = OutputStoreBBs[0];
2217  for (std::pair<Value *, BasicBlock *> &VBPair : OutputBlocks) {
2219  EndBBs.find(VBPair.first);
2220  assert(EndBBIt != EndBBs.end() && "Could not find end block");
2221  BasicBlock *EndBB = EndBBIt->second;
2222  BasicBlock *OutputBB = VBPair.second;
2223  Instruction *Term = OutputBB->getTerminator();
2224  Term->eraseFromParent();
2225  Term = EndBB->getTerminator();
2226  moveBBContents(*OutputBB, *EndBB);
2227  Term->moveBefore(*EndBB, EndBB->end());
2228  OutputBB->eraseFromParent();
2229  }
2230  }
2231 }
2232 
2233 /// Fill the new function that will serve as the replacement function for all of
2234 /// the extracted regions of a certain structure from the first region in the
2235 /// list of regions. Replace this first region's extracted function with the
2236 /// new overall function.
2237 ///
2238 /// \param [in] M - The module we are outlining from.
2239 /// \param [in] CurrentGroup - The group of regions to be outlined.
2240 /// \param [in,out] OutputStoreBBs - The output blocks for each different
2241 /// set of stores needed for the different functions.
2242 /// \param [in,out] FuncsToRemove - Extracted functions to erase from module
2243 /// once outlining is complete.
2244 /// \param [in] OutputMappings - Extracted functions to erase from module
2245 /// once outlining is complete.
2247  Module &M, OutlinableGroup &CurrentGroup,
2248  std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs,
2249  std::vector<Function *> &FuncsToRemove,
2250  const DenseMap<Value *, Value *> &OutputMappings) {
2251  OutlinableRegion *CurrentOS = CurrentGroup.Regions[0];
2252 
2253  // Move first extracted function's instructions into new function.
2254  LLVM_DEBUG(dbgs() << "Move instructions from "
2255  << *CurrentOS->ExtractedFunction << " to instruction "
2256  << *CurrentGroup.OutlinedFunction << "\n");
2257  moveFunctionData(*CurrentOS->ExtractedFunction,
2258  *CurrentGroup.OutlinedFunction, CurrentGroup.EndBBs);
2259 
2260  // Transfer the attributes from the function to the new function.
2261  for (Attribute A : CurrentOS->ExtractedFunction->getAttributes().getFnAttrs())
2262  CurrentGroup.OutlinedFunction->addFnAttr(A);
2263 
2264  // Create a new set of output blocks for the first extracted function.
2266  createAndInsertBasicBlocks(CurrentGroup.EndBBs, NewBBs,
2267  CurrentGroup.OutlinedFunction, "output_block_0");
2268  CurrentOS->OutputBlockNum = 0;
2269 
2270  replaceArgumentUses(*CurrentOS, NewBBs, OutputMappings, true);
2271  replaceConstants(*CurrentOS);
2272 
2273  // We first identify if any output blocks are empty, if they are we remove
2274  // them. We then create a branch instruction to the basic block to the return
2275  // block for the function for each non empty output block.
2276  if (!analyzeAndPruneOutputBlocks(NewBBs, *CurrentOS)) {
2277  OutputStoreBBs.push_back(DenseMap<Value *, BasicBlock *>());
2278  for (std::pair<Value *, BasicBlock *> &VToBB : NewBBs) {
2280  CurrentGroup.EndBBs.find(VToBB.first);
2281  BasicBlock *EndBB = VBBIt->second;
2282  BranchInst::Create(EndBB, VToBB.second);
2283  OutputStoreBBs.back().insert(VToBB);
2284  }
2285  }
2286 
2287  // Replace the call to the extracted function with the outlined function.
2288  CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
2289 
2290  // We only delete the extracted functions at the end since we may need to
2291  // reference instructions contained in them for mapping purposes.
2292  FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
2293 }
2294 
2295 void IROutliner::deduplicateExtractedSections(
2296  Module &M, OutlinableGroup &CurrentGroup,
2297  std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) {
2298  createFunction(M, CurrentGroup, OutlinedFunctionNum);
2299 
2300  std::vector<DenseMap<Value *, BasicBlock *>> OutputStoreBBs;
2301 
2302  OutlinableRegion *CurrentOS;
2303 
2304  fillOverallFunction(M, CurrentGroup, OutputStoreBBs, FuncsToRemove,
2305  OutputMappings);
2306 
2307  std::vector<Value *> SortedKeys;
2308  for (unsigned Idx = 1; Idx < CurrentGroup.Regions.size(); Idx++) {
2309  CurrentOS = CurrentGroup.Regions[Idx];
2311  *CurrentOS->ExtractedFunction);
2312 
2313  // Create a set of BasicBlocks, one for each return block, to hold the
2314  // needed store instructions.
2317  CurrentGroup.EndBBs, NewBBs, CurrentGroup.OutlinedFunction,
2318  "output_block_" + Twine(static_cast<unsigned>(Idx)));
2319  replaceArgumentUses(*CurrentOS, NewBBs, OutputMappings);
2320  alignOutputBlockWithAggFunc(CurrentGroup, *CurrentOS, NewBBs,
2321  CurrentGroup.EndBBs, OutputMappings,
2322  OutputStoreBBs);
2323 
2324  CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
2325  FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
2326  }
2327 
2328  // Create a switch statement to handle the different output schemes.
2329  createSwitchStatement(M, CurrentGroup, CurrentGroup.EndBBs, OutputStoreBBs);
2330 
2331  OutlinedFunctionNum++;
2332 }
2333 
2334 /// Checks that the next instruction in the InstructionDataList matches the
2335 /// next instruction in the module. If they do not, there could be the
2336 /// possibility that extra code has been inserted, and we must ignore it.
2337 ///
2338 /// \param ID - The IRInstructionData to check the next instruction of.
2339 /// \returns true if the InstructionDataList and actual instruction match.
2341  // We check if there is a discrepancy between the InstructionDataList
2342  // and the actual next instruction in the module. If there is, it means
2343  // that an extra instruction was added, likely by the CodeExtractor.
2344 
2345  // Since we do not have any similarity data about this particular
2346  // instruction, we cannot confidently outline it, and must discard this
2347  // candidate.
2348  IRInstructionDataList::iterator NextIDIt = std::next(ID.getIterator());
2349  Instruction *NextIDLInst = NextIDIt->Inst;
2350  Instruction *NextModuleInst = nullptr;
2351  if (!ID.Inst->isTerminator())
2352  NextModuleInst = ID.Inst->getNextNonDebugInstruction();
2353  else if (NextIDLInst != nullptr)
2354  NextModuleInst =
2355  &*NextIDIt->Inst->getParent()->instructionsWithoutDebug().begin();
2356 
2357  if (NextIDLInst && NextIDLInst != NextModuleInst)
2358  return false;
2359 
2360  return true;
2361 }
2362 
2363 bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
2364  const OutlinableRegion &Region) {
2365  IRSimilarityCandidate *IRSC = Region.Candidate;
2366  unsigned StartIdx = IRSC->getStartIdx();
2367  unsigned EndIdx = IRSC->getEndIdx();
2368 
2369  // A check to make sure that we are not about to attempt to outline something
2370  // that has already been outlined.
2371  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
2372  if (Outlined.contains(Idx))
2373  return false;
2374 
2375  // We check if the recorded instruction matches the actual next instruction,
2376  // if it does not, we fix it in the InstructionDataList.
2377  if (!Region.Candidate->backInstruction()->isTerminator()) {
2378  Instruction *NewEndInst =
2379  Region.Candidate->backInstruction()->getNextNonDebugInstruction();
2380  assert(NewEndInst && "Next instruction is a nullptr?");
2381  if (Region.Candidate->end()->Inst != NewEndInst) {
2382  IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
2383  IRInstructionData *NewEndIRID = new (InstDataAllocator.Allocate())
2384  IRInstructionData(*NewEndInst,
2385  InstructionClassifier.visit(*NewEndInst), *IDL);
2386 
2387  // Insert the first IRInstructionData of the new region after the
2388  // last IRInstructionData of the IRSimilarityCandidate.
2389  IDL->insert(Region.Candidate->end(), *NewEndIRID);
2390  }
2391  }
2392 
2393  return none_of(*IRSC, [this](IRInstructionData &ID) {
2395  return true;
2396 
2397  return !this->InstructionClassifier.visit(ID.Inst);
2398  });
2399 }
2400 
2401 void IROutliner::pruneIncompatibleRegions(
2402  std::vector<IRSimilarityCandidate> &CandidateVec,
2403  OutlinableGroup &CurrentGroup) {
2404  bool PreviouslyOutlined;
2405 
2406  // Sort from beginning to end, so the IRSimilarityCandidates are in order.
2407  stable_sort(CandidateVec, [](const IRSimilarityCandidate &LHS,
2408  const IRSimilarityCandidate &RHS) {
2409  return LHS.getStartIdx() < RHS.getStartIdx();
2410  });
2411 
2412  IRSimilarityCandidate &FirstCandidate = CandidateVec[0];
2413  // Since outlining a call and a branch instruction will be the same as only
2414  // outlinining a call instruction, we ignore it as a space saving.
2415  if (FirstCandidate.getLength() == 2) {
2416  if (isa<CallInst>(FirstCandidate.front()->Inst) &&
2417  isa<BranchInst>(FirstCandidate.back()->Inst))
2418  return;
2419  }
2420 
2421  unsigned CurrentEndIdx = 0;
2422  for (IRSimilarityCandidate &IRSC : CandidateVec) {
2423  PreviouslyOutlined = false;
2424  unsigned StartIdx = IRSC.getStartIdx();
2425  unsigned EndIdx = IRSC.getEndIdx();
2426 
2427  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
2428  if (Outlined.contains(Idx)) {
2429  PreviouslyOutlined = true;
2430  break;
2431  }
2432 
2433  if (PreviouslyOutlined)
2434  continue;
2435 
2436  // Check over the instructions, and if the basic block has its address
2437  // taken for use somewhere else, we do not outline that block.
2438  bool BBHasAddressTaken = any_of(IRSC, [](IRInstructionData &ID){
2439  return ID.Inst->getParent()->hasAddressTaken();
2440  });
2441 
2442  if (BBHasAddressTaken)
2443  continue;
2444 
2445  if (IRSC.getFunction()->hasOptNone())
2446  continue;
2447 
2448  if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
2449  !OutlineFromLinkODRs)
2450  continue;
2451 
2452  // Greedily prune out any regions that will overlap with already chosen
2453  // regions.
2454  if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
2455  continue;
2456 
2457  bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {
2459  return true;
2460 
2461  return !this->InstructionClassifier.visit(ID.Inst);
2462  });
2463 
2464  if (BadInst)
2465  continue;
2466 
2467  OutlinableRegion *OS = new (RegionAllocator.Allocate())
2468  OutlinableRegion(IRSC, CurrentGroup);
2469  CurrentGroup.Regions.push_back(OS);
2470 
2471  CurrentEndIdx = EndIdx;
2472  }
2473 }
2474 
2476 IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) {
2477  InstructionCost RegionBenefit = 0;
2478  for (OutlinableRegion *Region : CurrentGroup.Regions) {
2479  TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
2480  // We add the number of instructions in the region to the benefit as an
2481  // estimate as to how much will be removed.
2482  RegionBenefit += Region->getBenefit(TTI);
2483  LLVM_DEBUG(dbgs() << "Adding: " << RegionBenefit
2484  << " saved instructions to overfall benefit.\n");
2485  }
2486 
2487  return RegionBenefit;
2488 }
2489 
2490 /// For the \p OutputCanon number passed in find the value represented by this
2491 /// canonical number. If it is from a PHINode, we pick the first incoming
2492 /// value and return that Value instead.
2493 ///
2494 /// \param Region - The OutlinableRegion to get the Value from.
2495 /// \param OutputCanon - The canonical number to find the Value from.
2496 /// \returns The Value represented by a canonical number \p OutputCanon in \p
2497 /// Region.
2499  unsigned OutputCanon) {
2500  OutlinableGroup &CurrentGroup = *Region.Parent;
2501  // If the value is greater than the value in the tracker, we have a
2502  // PHINode and will instead use one of the incoming values to find the
2503  // type.
2504  if (OutputCanon > CurrentGroup.PHINodeGVNTracker) {
2505  auto It = CurrentGroup.PHINodeGVNToGVNs.find(OutputCanon);
2506  assert(It != CurrentGroup.PHINodeGVNToGVNs.end() &&
2507  "Could not find GVN set for PHINode number!");
2508  assert(It->second.second.size() > 0 && "PHINode does not have any values!");
2509  OutputCanon = *It->second.second.begin();
2510  }
2511  Optional<unsigned> OGVN = Region.Candidate->fromCanonicalNum(OutputCanon);
2512  assert(OGVN && "Could not find GVN for Canonical Number?");
2513  Optional<Value *> OV = Region.Candidate->fromGVN(*OGVN);
2514  assert(OV && "Could not find value for GVN?");
2515  return *OV;
2516 }
2517 
2519 IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) {
2520  InstructionCost OverallCost = 0;
2521  for (OutlinableRegion *Region : CurrentGroup.Regions) {
2522  TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
2523 
2524  // Each output incurs a load after the call, so we add that to the cost.
2525  for (unsigned OutputCanon : Region->GVNStores) {
2526  Value *V = findOutputValueInRegion(*Region, OutputCanon);
2527  InstructionCost LoadCost =
2530 
2531  LLVM_DEBUG(dbgs() << "Adding: " << LoadCost
2532  << " instructions to cost for output of type "
2533  << *V->getType() << "\n");
2534  OverallCost += LoadCost;
2535  }
2536  }
2537 
2538  return OverallCost;
2539 }
2540 
2541 /// Find the extra instructions needed to handle any output values for the
2542 /// region.
2543 ///
2544 /// \param [in] M - The Module to outline from.
2545 /// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze.
2546 /// \param [in] TTI - The TargetTransformInfo used to collect information for
2547 /// new instruction costs.
2548 /// \returns the additional cost to handle the outputs.
2550  OutlinableGroup &CurrentGroup,
2552  InstructionCost OutputCost = 0;
2553  unsigned NumOutputBranches = 0;
2554 
2555  OutlinableRegion &FirstRegion = *CurrentGroup.Regions[0];
2556  IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
2557  DenseSet<BasicBlock *> CandidateBlocks;
2558  Candidate.getBasicBlocks(CandidateBlocks);
2559 
2560  // Count the number of different output branches that point to blocks outside
2561  // of the region.
2562  DenseSet<BasicBlock *> FoundBlocks;
2563  for (IRInstructionData &ID : Candidate) {
2564  if (!isa<BranchInst>(ID.Inst))
2565  continue;
2566 
2567  for (Value *V : ID.OperVals) {
2568  BasicBlock *BB = static_cast<BasicBlock *>(V);
2569  if (!CandidateBlocks.contains(BB) && FoundBlocks.insert(BB).second)
2570  NumOutputBranches++;
2571  }
2572  }
2573 
2574  CurrentGroup.BranchesToOutside = NumOutputBranches;
2575 
2576  for (const ArrayRef<unsigned> &OutputUse :
2577  CurrentGroup.OutputGVNCombinations) {
2578  for (unsigned OutputCanon : OutputUse) {
2579  Value *V = findOutputValueInRegion(FirstRegion, OutputCanon);
2580  InstructionCost StoreCost =
2583 
2584  // An instruction cost is added for each store set that needs to occur for
2585  // various output combinations inside the function, plus a branch to
2586  // return to the exit block.
2587  LLVM_DEBUG(dbgs() << "Adding: " << StoreCost
2588  << " instructions to cost for output of type "
2589  << *V->getType() << "\n");
2590  OutputCost += StoreCost * NumOutputBranches;
2591  }
2592 
2593  InstructionCost BranchCost =
2595  LLVM_DEBUG(dbgs() << "Adding " << BranchCost << " to the current cost for"
2596  << " a branch instruction\n");
2597  OutputCost += BranchCost * NumOutputBranches;
2598  }
2599 
2600  // If there is more than one output scheme, we must have a comparison and
2601  // branch for each different item in the switch statement.
2602  if (CurrentGroup.OutputGVNCombinations.size() > 1) {
2603  InstructionCost ComparisonCost = TTI.getCmpSelInstrCost(
2604  Instruction::ICmp, Type::getInt32Ty(M.getContext()),
2607  InstructionCost BranchCost =
2609 
2610  unsigned DifferentBlocks = CurrentGroup.OutputGVNCombinations.size();
2611  InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
2612 
2613  LLVM_DEBUG(dbgs() << "Adding: " << TotalCost
2614  << " instructions for each switch case for each different"
2615  << " output path in a function\n");
2616  OutputCost += TotalCost * NumOutputBranches;
2617  }
2618 
2619  return OutputCost;
2620 }
2621 
2622 void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {
2623  InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
2624  CurrentGroup.Benefit += RegionBenefit;
2625  LLVM_DEBUG(dbgs() << "Current Benefit: " << CurrentGroup.Benefit << "\n");
2626 
2627  InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
2628  CurrentGroup.Cost += OutputReloadCost;
2629  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2630 
2631  InstructionCost AverageRegionBenefit =
2632  RegionBenefit / CurrentGroup.Regions.size();
2633  unsigned OverallArgumentNum = CurrentGroup.ArgumentTypes.size();
2634  unsigned NumRegions = CurrentGroup.Regions.size();
2636  getTTI(*CurrentGroup.Regions[0]->Candidate->getFunction());
2637 
2638  // We add one region to the cost once, to account for the instructions added
2639  // inside of the newly created function.
2640  LLVM_DEBUG(dbgs() << "Adding: " << AverageRegionBenefit
2641  << " instructions to cost for body of new function.\n");
2642  CurrentGroup.Cost += AverageRegionBenefit;
2643  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2644 
2645  // For each argument, we must add an instruction for loading the argument
2646  // out of the register and into a value inside of the newly outlined function.
2647  LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum
2648  << " instructions to cost for each argument in the new"
2649  << " function.\n");
2650  CurrentGroup.Cost +=
2651  OverallArgumentNum * TargetTransformInfo::TCC_Basic;
2652  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2653 
2654  // Each argument needs to either be loaded into a register or onto the stack.
2655  // Some arguments will only be loaded into the stack once the argument
2656  // registers are filled.
2657  LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum
2658  << " instructions to cost for each argument in the new"
2659  << " function " << NumRegions << " times for the "
2660  << "needed argument handling at the call site.\n");
2661  CurrentGroup.Cost +=
2662  2 * OverallArgumentNum * TargetTransformInfo::TCC_Basic * NumRegions;
2663  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2664 
2665  CurrentGroup.Cost += findCostForOutputBlocks(M, CurrentGroup, TTI);
2666  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2667 }
2668 
2669 void IROutliner::updateOutputMapping(OutlinableRegion &Region,
2670  ArrayRef<Value *> Outputs,
2671  LoadInst *LI) {
2672  // For and load instructions following the call
2673  Value *Operand = LI->getPointerOperand();
2674  Optional<unsigned> OutputIdx;
2675  // Find if the operand it is an output register.
2676  for (unsigned ArgIdx = Region.NumExtractedInputs;
2677  ArgIdx < Region.Call->arg_size(); ArgIdx++) {
2678  if (Operand == Region.Call->getArgOperand(ArgIdx)) {
2679  OutputIdx = ArgIdx - Region.NumExtractedInputs;
2680  break;
2681  }
2682  }
2683 
2684  // If we found an output register, place a mapping of the new value
2685  // to the original in the mapping.
2686  if (!OutputIdx)
2687  return;
2688 
2689  if (OutputMappings.find(Outputs[OutputIdx.value()]) == OutputMappings.end()) {
2690  LLVM_DEBUG(dbgs() << "Mapping extracted output " << *LI << " to "
2691  << *Outputs[OutputIdx.value()] << "\n");
2692  OutputMappings.insert(std::make_pair(LI, Outputs[OutputIdx.value()]));
2693  } else {
2694  Value *Orig = OutputMappings.find(Outputs[OutputIdx.value()])->second;
2695  LLVM_DEBUG(dbgs() << "Mapping extracted output " << *Orig << " to "
2696  << *Outputs[OutputIdx.value()] << "\n");
2697  OutputMappings.insert(std::make_pair(LI, Orig));
2698  }
2699 }
2700 
2701 bool IROutliner::extractSection(OutlinableRegion &Region) {
2702  SetVector<Value *> ArgInputs, Outputs, SinkCands;
2703  assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!");
2704  BasicBlock *InitialStart = Region.StartBB;
2705  Function *OrigF = Region.StartBB->getParent();
2706  CodeExtractorAnalysisCache CEAC(*OrigF);
2707  Region.ExtractedFunction =
2708  Region.CE->extractCodeRegion(CEAC, ArgInputs, Outputs);
2709 
2710  // If the extraction was successful, find the BasicBlock, and reassign the
2711  // OutlinableRegion blocks
2712  if (!Region.ExtractedFunction) {
2713  LLVM_DEBUG(dbgs() << "CodeExtractor failed to outline " << Region.StartBB
2714  << "\n");
2715  Region.reattachCandidate();
2716  return false;
2717  }
2718 
2719  // Get the block containing the called branch, and reassign the blocks as
2720  // necessary. If the original block still exists, it is because we ended on
2721  // a branch instruction, and so we move the contents into the block before
2722  // and assign the previous block correctly.
2723  User *InstAsUser = Region.ExtractedFunction->user_back();
2724  BasicBlock *RewrittenBB = cast<Instruction>(InstAsUser)->getParent();
2725  Region.PrevBB = RewrittenBB->getSinglePredecessor();
2726  assert(Region.PrevBB && "PrevBB is nullptr?");
2727  if (Region.PrevBB == InitialStart) {
2728  BasicBlock *NewPrev = InitialStart->getSinglePredecessor();
2729  Instruction *BI = NewPrev->getTerminator();
2730  BI->eraseFromParent();
2731  moveBBContents(*InitialStart, *NewPrev);
2732  Region.PrevBB = NewPrev;
2733  InitialStart->eraseFromParent();
2734  }
2735 
2736  Region.StartBB = RewrittenBB;
2737  Region.EndBB = RewrittenBB;
2738 
2739  // The sequences of outlinable regions has now changed. We must fix the
2740  // IRInstructionDataList for consistency. Although they may not be illegal
2741  // instructions, they should not be compared with anything else as they
2742  // should not be outlined in this round. So marking these as illegal is
2743  // allowed.
2744  IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
2745  Instruction *BeginRewritten = &*RewrittenBB->begin();
2746  Instruction *EndRewritten = &*RewrittenBB->begin();
2747  Region.NewFront = new (InstDataAllocator.Allocate()) IRInstructionData(
2748  *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
2749  Region.NewBack = new (InstDataAllocator.Allocate()) IRInstructionData(
2750  *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
2751 
2752  // Insert the first IRInstructionData of the new region in front of the
2753  // first IRInstructionData of the IRSimilarityCandidate.
2754  IDL->insert(Region.Candidate->begin(), *Region.NewFront);
2755  // Insert the first IRInstructionData of the new region after the
2756  // last IRInstructionData of the IRSimilarityCandidate.
2757  IDL->insert(Region.Candidate->end(), *Region.NewBack);
2758  // Remove the IRInstructionData from the IRSimilarityCandidate.
2759  IDL->erase(Region.Candidate->begin(), std::prev(Region.Candidate->end()));
2760 
2761  assert(RewrittenBB != nullptr &&
2762  "Could not find a predecessor after extraction!");
2763 
2764  // Iterate over the new set of instructions to find the new call
2765  // instruction.
2766  for (Instruction &I : *RewrittenBB)
2767  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
2768  if (Region.ExtractedFunction == CI->getCalledFunction())
2769  Region.Call = CI;
2770  } else if (LoadInst *LI = dyn_cast<LoadInst>(&I))
2771  updateOutputMapping(Region, Outputs.getArrayRef(), LI);
2772  Region.reattachCandidate();
2773  return true;
2774 }
2775 
2776 unsigned IROutliner::doOutline(Module &M) {
2777  // Find the possible similarity sections.
2778  InstructionClassifier.EnableBranches = !DisableBranches;
2779  InstructionClassifier.EnableIndirectCalls = !DisableIndirectCalls;
2780  InstructionClassifier.EnableIntrinsics = !DisableIntrinsics;
2781 
2782  IRSimilarityIdentifier &Identifier = getIRSI(M);
2783  SimilarityGroupList &SimilarityCandidates = *Identifier.getSimilarity();
2784 
2785  // Sort them by size of extracted sections
2786  unsigned OutlinedFunctionNum = 0;
2787  // If we only have one SimilarityGroup in SimilarityCandidates, we do not have
2788  // to sort them by the potential number of instructions to be outlined
2789  if (SimilarityCandidates.size() > 1)
2790  llvm::stable_sort(SimilarityCandidates,
2791  [](const std::vector<IRSimilarityCandidate> &LHS,
2792  const std::vector<IRSimilarityCandidate> &RHS) {
2793  return LHS[0].getLength() * LHS.size() >
2794  RHS[0].getLength() * RHS.size();
2795  });
2796  // Creating OutlinableGroups for each SimilarityCandidate to be used in
2797  // each of the following for loops to avoid making an allocator.
2798  std::vector<OutlinableGroup> PotentialGroups(SimilarityCandidates.size());
2799 
2800  DenseSet<unsigned> NotSame;
2801  std::vector<OutlinableGroup *> NegativeCostGroups;
2802  std::vector<OutlinableRegion *> OutlinedRegions;
2803  // Iterate over the possible sets of similarity.
2804  unsigned PotentialGroupIdx = 0;
2805  for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
2806  OutlinableGroup &CurrentGroup = PotentialGroups[PotentialGroupIdx++];
2807 
2808  // Remove entries that were previously outlined
2809  pruneIncompatibleRegions(CandidateVec, CurrentGroup);
2810 
2811  // We pruned the number of regions to 0 to 1, meaning that it's not worth
2812  // trying to outlined since there is no compatible similar instance of this
2813  // code.
2814  if (CurrentGroup.Regions.size() < 2)
2815  continue;
2816 
2817  // Determine if there are any values that are the same constant throughout
2818  // each section in the set.
2819  NotSame.clear();
2820  CurrentGroup.findSameConstants(NotSame);
2821 
2822  if (CurrentGroup.IgnoreGroup)
2823  continue;
2824 
2825  // Create a CodeExtractor for each outlinable region. Identify inputs and
2826  // outputs for each section using the code extractor and create the argument
2827  // types for the Aggregate Outlining Function.
2828  OutlinedRegions.clear();
2829  for (OutlinableRegion *OS : CurrentGroup.Regions) {
2830  // Break the outlinable region out of its parent BasicBlock into its own
2831  // BasicBlocks (see function implementation).
2832  OS->splitCandidate();
2833 
2834  // There's a chance that when the region is split, extra instructions are
2835  // added to the region. This makes the region no longer viable
2836  // to be split, so we ignore it for outlining.
2837  if (!OS->CandidateSplit)
2838  continue;
2839 
2841  DenseSet<BasicBlock *> BlocksInRegion;
2842  OS->Candidate->getBasicBlocks(BlocksInRegion, BE);
2843  OS->CE = new (ExtractorAllocator.Allocate())
2844  CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
2845  false, nullptr, "outlined");
2846  findAddInputsOutputs(M, *OS, NotSame);
2847  if (!OS->IgnoreRegion)
2848  OutlinedRegions.push_back(OS);
2849 
2850  // We recombine the blocks together now that we have gathered all the
2851  // needed information.
2852  OS->reattachCandidate();
2853  }
2854 
2855  CurrentGroup.Regions = std::move(OutlinedRegions);
2856 
2857  if (CurrentGroup.Regions.empty())
2858  continue;
2859 
2860  CurrentGroup.collectGVNStoreSets(M);
2861 
2862  if (CostModel)
2863  findCostBenefit(M, CurrentGroup);
2864 
2865  // If we are adhering to the cost model, skip those groups where the cost
2866  // outweighs the benefits.
2867  if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
2869  getORE(*CurrentGroup.Regions[0]->Candidate->getFunction());
2870  ORE.emit([&]() {
2871  IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
2872  OptimizationRemarkMissed R(DEBUG_TYPE, "WouldNotDecreaseSize",
2873  C->frontInstruction());
2874  R << "did not outline "
2875  << ore::NV(std::to_string(CurrentGroup.Regions.size()))
2876  << " regions due to estimated increase of "
2877  << ore::NV("InstructionIncrease",
2878  CurrentGroup.Cost - CurrentGroup.Benefit)
2879  << " instructions at locations ";
2880  interleave(
2881  CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
2882  [&R](OutlinableRegion *Region) {
2883  R << ore::NV(
2884  "DebugLoc",
2885  Region->Candidate->frontInstruction()->getDebugLoc());
2886  },
2887  [&R]() { R << " "; });
2888  return R;
2889  });
2890  continue;
2891  }
2892 
2893  NegativeCostGroups.push_back(&CurrentGroup);
2894  }
2895 
2896  ExtractorAllocator.DestroyAll();
2897 
2898  if (NegativeCostGroups.size() > 1)
2899  stable_sort(NegativeCostGroups,
2900  [](const OutlinableGroup *LHS, const OutlinableGroup *RHS) {
2901  return LHS->Benefit - LHS->Cost > RHS->Benefit - RHS->Cost;
2902  });
2903 
2904  std::vector<Function *> FuncsToRemove;
2905  for (OutlinableGroup *CG : NegativeCostGroups) {
2906  OutlinableGroup &CurrentGroup = *CG;
2907 
2908  OutlinedRegions.clear();
2909  for (OutlinableRegion *Region : CurrentGroup.Regions) {
2910  // We check whether our region is compatible with what has already been
2911  // outlined, and whether we need to ignore this item.
2912  if (!isCompatibleWithAlreadyOutlinedCode(*Region))
2913  continue;
2914  OutlinedRegions.push_back(Region);
2915  }
2916 
2917  if (OutlinedRegions.size() < 2)
2918  continue;
2919 
2920  // Reestimate the cost and benefit of the OutlinableGroup. Continue only if
2921  // we are still outlining enough regions to make up for the added cost.
2922  CurrentGroup.Regions = std::move(OutlinedRegions);
2923  if (CostModel) {
2924  CurrentGroup.Benefit = 0;
2925  CurrentGroup.Cost = 0;
2926  findCostBenefit(M, CurrentGroup);
2927  if (CurrentGroup.Cost >= CurrentGroup.Benefit)
2928  continue;
2929  }
2930  OutlinedRegions.clear();
2931  for (OutlinableRegion *Region : CurrentGroup.Regions) {
2932  Region->splitCandidate();
2933  if (!Region->CandidateSplit)
2934  continue;
2935  OutlinedRegions.push_back(Region);
2936  }
2937 
2938  CurrentGroup.Regions = std::move(OutlinedRegions);
2939  if (CurrentGroup.Regions.size() < 2) {
2940  for (OutlinableRegion *R : CurrentGroup.Regions)
2941  R->reattachCandidate();
2942  continue;
2943  }
2944 
2945  LLVM_DEBUG(dbgs() << "Outlining regions with cost " << CurrentGroup.Cost
2946  << " and benefit " << CurrentGroup.Benefit << "\n");
2947 
2948  // Create functions out of all the sections, and mark them as outlined.
2949  OutlinedRegions.clear();
2950  for (OutlinableRegion *OS : CurrentGroup.Regions) {
2952  DenseSet<BasicBlock *> BlocksInRegion;
2953  OS->Candidate->getBasicBlocks(BlocksInRegion, BE);
2954  OS->CE = new (ExtractorAllocator.Allocate())
2955  CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
2956  false, nullptr, "outlined");
2957  bool FunctionOutlined = extractSection(*OS);
2958  if (FunctionOutlined) {
2959  unsigned StartIdx = OS->Candidate->getStartIdx();
2960  unsigned EndIdx = OS->Candidate->getEndIdx();
2961  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
2962  Outlined.insert(Idx);
2963 
2964  OutlinedRegions.push_back(OS);
2965  }
2966  }
2967 
2968  LLVM_DEBUG(dbgs() << "Outlined " << OutlinedRegions.size()
2969  << " with benefit " << CurrentGroup.Benefit
2970  << " and cost " << CurrentGroup.Cost << "\n");
2971 
2972  CurrentGroup.Regions = std::move(OutlinedRegions);
2973 
2974  if (CurrentGroup.Regions.empty())
2975  continue;
2976 
2978  getORE(*CurrentGroup.Regions[0]->Call->getFunction());
2979  ORE.emit([&]() {
2980  IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
2981  OptimizationRemark R(DEBUG_TYPE, "Outlined", C->front()->Inst);
2982  R << "outlined " << ore::NV(std::to_string(CurrentGroup.Regions.size()))
2983  << " regions with decrease of "
2984  << ore::NV("Benefit", CurrentGroup.Benefit - CurrentGroup.Cost)
2985  << " instructions at locations ";
2986  interleave(
2987  CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
2988  [&R](OutlinableRegion *Region) {
2989  R << ore::NV("DebugLoc",
2990  Region->Candidate->frontInstruction()->getDebugLoc());
2991  },
2992  [&R]() { R << " "; });
2993  return R;
2994  });
2995 
2996  deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
2997  OutlinedFunctionNum);
2998  }
2999 
3000  for (Function *F : FuncsToRemove)
3001  F->eraseFromParent();
3002 
3003  return OutlinedFunctionNum;
3004 }
3005 
3007  CostModel = !NoCostModel;
3008  OutlineFromLinkODRs = EnableLinkOnceODRIROutlining;
3009 
3010  return doOutline(M) > 0;
3011 }
3012 
3013 // Pass Manager Boilerplate
3014 namespace {
3015 class IROutlinerLegacyPass : public ModulePass {
3016 public:
3017  static char ID;
3018  IROutlinerLegacyPass() : ModulePass(ID) {
3020  }
3021 
3022  void getAnalysisUsage(AnalysisUsage &AU) const override {
3026  }
3027 
3028  bool runOnModule(Module &M) override;
3029 };
3030 } // namespace
3031 
3032 bool IROutlinerLegacyPass::runOnModule(Module &M) {
3033  if (skipModule(M))
3034  return false;
3035 
3036  std::unique_ptr<OptimizationRemarkEmitter> ORE;
3037  auto GORE = [&ORE](Function &F) -> OptimizationRemarkEmitter & {
3038  ORE.reset(new OptimizationRemarkEmitter(&F));
3039  return *ORE;
3040  };
3041 
3042  auto GTTI = [this](Function &F) -> TargetTransformInfo & {
3043  return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
3044  };
3045 
3046  auto GIRSI = [this](Module &) -> IRSimilarityIdentifier & {
3047  return this->getAnalysis<IRSimilarityIdentifierWrapperPass>().getIRSI();
3048  };
3049 
3050  return IROutliner(GTTI, GIRSI, GORE).run(M);
3051 }
3052 
3054  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
3055 
3057  [&FAM](Function &F) -> TargetTransformInfo & {
3058  return FAM.getResult<TargetIRAnalysis>(F);
3059  };
3060 
3062  [&AM](Module &M) -> IRSimilarityIdentifier & {
3063  return AM.getResult<IRSimilarityAnalysis>(M);
3064  };
3065 
3066  std::unique_ptr<OptimizationRemarkEmitter> ORE;
3068  [&ORE](Function &F) -> OptimizationRemarkEmitter & {
3069  ORE.reset(new OptimizationRemarkEmitter(&F));
3070  return *ORE;
3071  };
3072 
3073  if (IROutliner(GTTI, GIRSI, GORE).run(M))
3074  return PreservedAnalyses::none();
3075  return PreservedAnalyses::all();
3076 }
3077 
3078 char IROutlinerLegacyPass::ID = 0;
3079 INITIALIZE_PASS_BEGIN(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false,
3080  false)
3084 INITIALIZE_PASS_END(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false,
3085  false)
3086 
3087 ModulePass *llvm::createIROutlinerPass() { return new IROutlinerLegacyPass(); }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:167
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
alignOutputBlockWithAggFunc
static void alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, DenseMap< Value *, BasicBlock * > &EndBBs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< DenseMap< Value *, BasicBlock * >> &OutputStoreBBs)
For the outlined section, move needed the StoreInsts for the output registers into their own block.
Definition: IROutliner.cpp:2071
IROutliner.h
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:308
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2570
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:735
llvm::DisableIntrinsics
cl::opt< bool > DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))
Definition: IROutliner.cpp:47
getSortedConstantKeys
static void getSortedConstantKeys(std::vector< Value * > &SortedKeys, DenseMap< Value *, BasicBlock * > &Map)
A function to sort the keys of Map, which must be a mapping of constant values to basic blocks and re...
Definition: IROutliner.cpp:167
llvm::AttributeFuncs::mergeAttributesForOutlining
void mergeAttributesForOutlining(Function &Base, const Function &ToMerge)
Merges the functions attributes from ToMerge into function Base.
Definition: Attributes.cpp:2055
llvm::IRSimilarity::IRSimilarityCandidate::getCanonicalNum
Optional< unsigned > getCanonicalNum(unsigned N)
Find the canonical number from the global value number N stored in the candidate.
Definition: IRSimilarityIdentifier.h:917
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::TargetTransformInfo::getInstructionCost
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:224
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
moveBBContents
static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB)
Move the contents of SourceBB to before the last instruction of TargetBB.
Definition: IROutliner.cpp:157
OutlinableGroup::ArgumentTypes
std::vector< Type * > ArgumentTypes
The argument types for the function created as the overall function to replace the extracted function...
Definition: IROutliner.cpp:79
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1604
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3052
llvm::IRSimilarity::IRInstructionDataList
Definition: IRSimilarityIdentifier.h:297
llvm::RegionBase::end
iterator end()
Definition: RegionInfo.h:561
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
findOutputMapping
static Value * findOutputMapping(const DenseMap< Value *, Value * > OutputMappings, Value *Input)
Check the OutputMappings structure for value Input, if it exists it has been used as an output for ou...
Definition: IROutliner.cpp:533
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::DIBuilder
Definition: DIBuilder.h:41
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
DebugInfoMetadata.h
llvm::Function::hasOptNone
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:658
getPassedArgumentInAlreadyOutlinedFunction
static Value * getPassedArgumentInAlreadyOutlinedFunction(const Argument *A, const OutlinableRegion &Region)
For the function call now representing the Region, find the passed value to that call that represents...
Definition: IROutliner.cpp:1594
OutlinableGroup::collectGVNStoreSets
void collectGVNStoreSets(Module &M)
For the regions, look at each set of GVN stores needed and account for each combination.
Definition: IROutliner.cpp:607
llvm::TargetTransformInfo::getCmpSelInstrCost
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:879
llvm::Instruction::getNextNonDebugInstruction
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
Definition: Instruction.cpp:766
OutlinableGroup::EndBBs
DenseMap< Value *, BasicBlock * > EndBBs
The return blocks for the overall function.
Definition: IROutliner.cpp:90
llvm::Function
Definition: Function.h:60
llvm::Attribute
Definition: Attributes.h:65
createAndInsertBasicBlocks
static void createAndInsertBasicBlocks(DenseMap< Value *, BasicBlock * > &OldMap, DenseMap< Value *, BasicBlock * > &NewMap, Function *ParentFunc, Twine BaseName)
Takes in a mapping, OldMap of ConstantValues to BasicBlocks, sorts keys, before creating a basic bloc...
Definition: IROutliner.cpp:2127
OutlinableGroup::OutputGVNCombinations
DenseSet< ArrayRef< unsigned > > OutputGVNCombinations
A set containing the different GVN store sets needed.
Definition: IROutliner.cpp:99
Pass.h
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:628
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::BasicBlock::instructionsWithoutDebug
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:103
llvm::IRSimilarityAnalysis
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
Definition: IRSimilarityIdentifier.h:1115
llvm::ReturnInst::getReturnValue
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
Definition: Instructions.h:3097
llvm::SmallVector< unsigned, 2 >
llvm::SwitchInst::Create
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3467
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:710
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:542
llvm::BasicBlock::replaceSuccessorsPhiUsesWith
void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New)
Update all phi nodes in this basic block's successors to refer to basic block New instead of basic bl...
Definition: BasicBlock.cpp:478
llvm::IRSimilarity::IRSimilarityCandidate::getBasicBlocks
void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const
Definition: IRSimilarityIdentifier.h:831
OutlinableGroup::findSameConstants
void findSameConstants(DenseSet< unsigned > &NotSame)
For the Regions, we look at every Value.
Definition: IROutliner.cpp:600
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:361
OptimizationRemarkEmitter.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:83
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
EnableLinkOnceODRIROutlining
static cl::opt< bool > EnableLinkOnceODRIROutlining("enable-linkonceodr-ir-outlining", cl::Hidden, cl::desc("Enable the IR outliner on linkonceodr functions"), cl::init(false))
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:220
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
findConstants
static void findConstants(IRSimilarityCandidate &C, DenseSet< unsigned > &NotSame, std::vector< unsigned > &Inputs)
Find the the constants that will need to be lifted into arguments as they are not the same in each in...
Definition: IROutliner.cpp:778
llvm::ConstantInt::getLimitedValue
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
Definition: Constants.h:244
OutlinableGroup::OutlinedFunctionType
FunctionType * OutlinedFunctionType
The FunctionType for the overall function.
Definition: IROutliner.cpp:81
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1557
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
replaceTargetsFromPHINode
static void replaceTargetsFromPHINode(BasicBlock *PHIBlock, BasicBlock *Find, BasicBlock *Replace, DenseSet< BasicBlock * > &Included)
Rewrite the BranchInsts in the incoming blocks to PHIBlock that are found in Included to branch to Ba...
Definition: IROutliner.cpp:223
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:320
llvm::Function::arg_size
size_t arg_size() const
Definition: Function.h:774
llvm::SetVector::getArrayRef
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:132
llvm::DisableBranches
cl::opt< bool > DisableBranches("no-ir-sim-branch-matching", cl::init(false), cl::ReallyHidden, cl::desc("disable similarity matching, and outlining, " "across branches for debugging purposes."))
Definition: IROutliner.cpp:39
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1388
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:402
llvm::IRSimilarity::SimilarityGroup
std::vector< IRSimilarityCandidate > SimilarityGroup
Definition: IRSimilarityIdentifier.h:952
llvm::Optional< unsigned >
llvm::TargetTransformInfo::getCFInstrCost
InstructionCost getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:870
llvm::BranchInst::getNumSuccessors
unsigned getNumSuccessors() const
Definition: Instructions.h:3225
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
findCanonNumsForPHI
static void findCanonNumsForPHI(PHINode *PN, OutlinableRegion &Region, const DenseMap< Value *, Value * > &OutputMappings, SmallVector< std::pair< unsigned, BasicBlock * >> &CanonNums, bool ReplacedWithOutlinedCall=true)
Find the canonical numbering for the incoming Values into the PHINode PN.
Definition: IROutliner.cpp:1635
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:261
llvm::IRSimilarity::SimilarityGroupList
std::vector< SimilarityGroup > SimilarityGroupList
Definition: IRSimilarityIdentifier.h:953
llvm::Mangler
Definition: Mangler.h:27
OutlinableGroup::OutlinedFunction
Function * OutlinedFunction
The Function for the collective overall function.
Definition: IROutliner.cpp:83
llvm::hash_value
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4828
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2798
llvm::cl::ReallyHidden
@ ReallyHidden
Definition: CommandLine.h:140
llvm::IROutlinerPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: IROutliner.cpp:3053
llvm::DominatorTreeBase::getDescendants
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
Definition: GenericDomTree.h:374
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1400
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BranchInst::setSuccessor
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Definition: Instructions.h:3232
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
outputHasNonPHI
static bool outputHasNonPHI(Value *V, unsigned PHILoc, PHINode &PN, SmallPtrSet< BasicBlock *, 1 > &Exits, DenseSet< BasicBlock * > &BlocksInRegion)
Check if the V has any uses outside of the region other than PN.
Definition: IROutliner.cpp:1036
llvm::BasicBlock::getUniqueSuccessor
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:323
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::Value::isSwiftError
bool isSwiftError() const
Return true if this value is a swifterror value.
Definition: Value.cpp:1015
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
CommandLine.h
llvm::interleave
void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)
An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...
Definition: STLExtras.h:1864
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
OutlinableGroup::Regions
std::vector< OutlinableRegion * > Regions
The sections that could be outlined.
Definition: IROutliner.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
findExtractedOutputToOverallOutputMapping
static void findExtractedOutputToOverallOutputMapping(OutlinableRegion &Region, SetVector< Value * > &Outputs)
Create a mapping of the output arguments for the Region to the output arguments of the overall outlin...
Definition: IROutliner.cpp:1276
analyzeAndPruneOutputBlocks
static bool analyzeAndPruneOutputBlocks(DenseMap< Value *, BasicBlock * > &BlocksToPrune, OutlinableRegion &Region)
Remove empty output blocks from the outlined region.
Definition: IROutliner.cpp:2024
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2795
DEBUG_TYPE
#define DEBUG_TYPE
Definition: IROutliner.cpp:31
InlinePriorityMode::Cost
@ Cost
llvm::IRSimilarityIdentifierWrapperPass
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
Definition: IRSimilarityIdentifier.h:1095
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DominatorTreeBase::insertEdge
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
Definition: GenericDomTree.h:584
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
findDuplicateOutputBlock
Optional< unsigned > findDuplicateOutputBlock(DenseMap< Value *, BasicBlock * > &OutputBBs, std::vector< DenseMap< Value *, BasicBlock * >> &OutputStoreBBs)
It is possible that there is a basic block that already performs the same stores.
Definition: IROutliner.cpp:1969
OutlinableGroup::PHINodeGVNTracker
unsigned PHINodeGVNTracker
Tracker counting backwards from the highest unsigned value possible to avoid conflicting with the GVN...
Definition: IROutliner.cpp:120
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
OutlinableGroup::GVNsToPHINodeGVN
DenseMap< hash_code, unsigned > GVNsToPHINodeGVN
Definition: IROutliner.cpp:125
OutlinableGroup::NumAggregateInputs
unsigned NumAggregateInputs
The number of input values in ArgumentTypes.
Definition: IROutliner.cpp:107
findExtractedInputToOverallInputMapping
static void findExtractedInputToOverallInputMapping(OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, SetVector< Value * > &ArgInputs)
Look over the inputs and map each input argument to an argument in the overall function for the Outli...
Definition: IROutliner.cpp:934
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1517
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
OutlinableGroup::InputTypesSet
bool InputTypesSet
Flag for whether the ArgumentTypes have been defined after the extraction of the first region.
Definition: IROutliner.cpp:103
getGVNForPHINode
static Optional< unsigned > getGVNForPHINode(OutlinableRegion &Region, PHINode *PN, DenseSet< BasicBlock * > &Blocks, unsigned AggArgIdx)
Create a special GVN for PHINodes that will be used outside of the region.
Definition: IROutliner.cpp:1174
llvm::OutlinableRegion::CandidateSplit
bool CandidateSplit
Flag for whether we have split out the IRSimilarityCanidate.
Definition: IROutliner.h:130
false
Definition: StackSlotColoring.cpp:141
llvm::Mangler::getNameWithPrefix
void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const
Print the appropriate prefix and the specified global variable's name.
Definition: Mangler.cpp:119
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:42
findOrCreatePHIBlock
static BasicBlock * findOrCreatePHIBlock(OutlinableGroup &Group, Value *RetVal)
Find or create a BasicBlock in the outlined function containing PhiBlocks for RetVal.
Definition: IROutliner.cpp:1541
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:364
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
mapInputsToGVNs
static void mapInputsToGVNs(IRSimilarityCandidate &C, SetVector< Value * > &CurrentInputs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< unsigned > &EndInputNumbers)
Find the GVN for the inputs that have been found by the CodeExtractor.
Definition: IROutliner.cpp:808
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:746
llvm::OutlinableRegion::reattachCandidate
void reattachCandidate()
For the contained region, reattach the BasicBlock at the starting and ending instructions of the cont...
Definition: IROutliner.cpp:378
llvm::OutlinableRegion::OutputBlockNum
unsigned OutputBlockNum
The corresponding BasicBlock with the appropriate stores for this OutlinableRegion in the overall fun...
Definition: IROutliner.h:78
llvm::GlobalValue::InternalLinkage
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
llvm::OutlinableRegion::findCorrespondingValueIn
Value * findCorrespondingValueIn(const OutlinableRegion &Other, Value *V)
Find a corresponding value for V in similar OutlinableRegion Other.
Definition: IROutliner.cpp:190
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2791
llvm::None
const NoneType None
Definition: None.h:24
remapExtractedInputs
static void remapExtractedInputs(const ArrayRef< Value * > ArgInputs, const DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &RemappedArgInputs)
Find the original value for the ArgInput values if any one of them was replaced during a previous ext...
Definition: IROutliner.cpp:833
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:314
llvm::IRSimilarity::IRSimilarityCandidate::getEndIdx
unsigned getEndIdx() const
Definition: IRSimilarityIdentifier.h:867
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
OutlinableGroup::CanonicalNumberToAggArg
DenseMap< unsigned, unsigned > CanonicalNumberToAggArg
The mapping of the canonical numbering of the values in outlined sections to specific arguments.
Definition: IROutliner.cpp:111
llvm::OutlinableRegion::getBenefit
InstructionCost getBenefit(TargetTransformInfo &TTI)
Get the size of the code removed from the region.
Definition: IROutliner.cpp:489
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::IRSimilarity::IRSimilarityCandidate::getFunction
Function * getFunction()
Definition: IRSimilarityIdentifier.h:885
llvm::cl::opt< bool >
llvm::IRSimilarity::IRSimilarityCandidate::getStartBB
BasicBlock * getStartBB()
Definition: IRSimilarityIdentifier.h:880
llvm::OutlinableRegion::ExtractedFunction
Function * ExtractedFunction
The function for the extracted region.
Definition: IROutliner.h:126
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::PointerType::getUnqual
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
Definition: DerivedTypes.h:651
llvm::simple_ilist< IRInstructionData, ilist_sentinel_tracking< true > >::iterator
ilist_iterator< OptionsT, false, false > iterator
Definition: simple_ilist.h:95
llvm::OutlinableRegion::Call
CallInst * Call
The call site of the extracted region.
Definition: IROutliner.h:123
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2626
llvm::simple_ilist::erase
iterator erase(iterator I)
Remove a node by iterator; never deletes.
Definition: simple_ilist.h:194
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2834
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1699
IPO.h
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3190
llvm::DenseMap< Value *, BasicBlock * >
OutlinableGroup::PHIBlocks
DenseMap< Value *, BasicBlock * > PHIBlocks
The PHIBlocks with their corresponding return block based on the return value as the key.
Definition: IROutliner.cpp:94
DebugInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:439
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:596
llvm::OutlinableRegion::CE
CodeExtractor * CE
Used to create an outlined function.
Definition: IROutliner.h:120
DIBuilder.h
llvm::DICompileUnit
Compile unit.
Definition: DebugInfoMetadata.h:1322
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:137
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::initializeIROutlinerLegacyPassPass
void initializeIROutlinerLegacyPassPass(PassRegistry &)
SI
StandardInstrumentations SI(Debug, VerifyEach)
collectRegionsConstants
static bool collectRegionsConstants(OutlinableRegion &Region, DenseMap< unsigned, Constant * > &GVNToConstant, DenseSet< unsigned > &NotSame)
Find whether Region matches the global value numbering to Constant mapping found so far.
Definition: IROutliner.cpp:552
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::IRSimilarity::IRInstructionData
This provides the utilities for hashing an Instruction to an unsigned integer.
Definition: IRSimilarityIdentifier.h:114
analyzeExitPHIsForOutputUses
static void analyzeExitPHIsForOutputUses(BasicBlock *CurrentExitFromRegion, SmallPtrSet< BasicBlock *, 1 > &PotentialExitsFromRegion, DenseSet< BasicBlock * > &RegionBlocks, SetVector< Value * > &Outputs, DenseSet< Value * > &OutputsReplacedByPHINode, DenseSet< Value * > &OutputsWithNonPhiUses)
Test whether CurrentExitFromRegion contains any PhiNodes that should be considered outputs.
Definition: IROutliner.cpp:1093
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:752
findOrCreatePHIInBlock
static PHINode * findOrCreatePHIInBlock(PHINode &PN, OutlinableRegion &Region, BasicBlock *OverallPhiBlock, const DenseMap< Value *, Value * > &OutputMappings, DenseSet< PHINode * > &UsedPHIs)
Find, or add PHINode PN to the combined PHINode Block OverallPHIBlock in order to condense the number...
Definition: IROutliner.cpp:1679
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::IRSimilarity::IRSimilarityCandidate::getGVN
Optional< unsigned > getGVN(Value *V)
Finds the positive number associated with V if it has been mapped.
Definition: IRSimilarityIdentifier.h:891
llvm::DisableIndirectCalls
cl::opt< bool > DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))
Definition: IROutliner.cpp:43
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
getPassedArgumentAndAdjustArgumentLocation
static Value * getPassedArgumentAndAdjustArgumentLocation(const Argument *A, const OutlinableRegion &Region)
For the function call now representing the Region, find the passed value to that call that represents...
Definition: IROutliner.cpp:1610
llvm::OutlinableRegion::findCorrespondingBlockIn
BasicBlock * findCorrespondingBlockIn(const OutlinableRegion &Other, BasicBlock *BB)
Find a corresponding BasicBlock for BB in similar OutlinableRegion Other.
Definition: IROutliner.cpp:201
Find
static const T * Find(StringRef S, ArrayRef< T > A)
Find KV in array using binary search.
Definition: MCSubtargetInfo.cpp:25
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
Mangler.h
llvm::IRSimilarity::IRSimilarityCandidate::front
IRInstructionData * front() const
Definition: IRSimilarityIdentifier.h:870
OutlinableGroup::Cost
InstructionCost Cost
The number of added instructions needed for the outlining of the Regions.
Definition: IROutliner.cpp:132
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:888
llvm::NVPTXISD::Dummy
@ Dummy
Definition: NVPTXISelLowering.h:60
llvm::IROutliner::run
bool run(Module &M)
Definition: IROutliner.cpp:3006
OutlinableGroup
The OutlinableGroup holds all the overarching information for outlining a set of regions that are str...
Definition: IROutliner.cpp:73
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false, false) INITIALIZE_PASS_END(IROutlinerLegacyPass
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::IRSimilarity::IRInstructionData::Inst
Instruction * Inst
The source Instruction that is being wrapped.
Definition: IRSimilarityIdentifier.h:118
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1597
llvm::OutlinableRegion::splitCandidate
void splitCandidate()
For the contained region, split the parent BasicBlock at the starting and ending instructions of the ...
Definition: IROutliner.cpp:251
constantMatches
static Optional< bool > constantMatches(Value *V, unsigned GVN, DenseMap< unsigned, Constant * > &GVNToConstant)
Find whether V matches the Constants previously found for the GVN.
Definition: IROutliner.cpp:466
llvm::createIROutlinerPass
ModulePass * createIROutlinerPass()
createIROutlinerPass - This pass finds similar code regions and factors those regions out into functi...
Definition: IROutliner.cpp:3087
replaceCalledFunction
CallInst * replaceCalledFunction(Module &M, OutlinableRegion &Region)
Replace the extracted function in the Region with a call to the overall function constructed from the...
Definition: IROutliner.cpp:1429
findOutputValueInRegion
static Value * findOutputValueInRegion(OutlinableRegion &Region, unsigned OutputCanon)
For the OutputCanon number passed in find the value represented by this canonical number.
Definition: IROutliner.cpp:2498
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:69
OutlinableGroup::Benefit
InstructionCost Benefit
The number of instructions that will be outlined by extracting Regions.
Definition: IROutliner.cpp:129
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::contains
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
llvm::RegionBase::begin
iterator begin()
Definition: RegionInfo.h:560
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
nextIRInstructionDataMatchesNextInst
static bool nextIRInstructionDataMatchesNextInst(IRInstructionData &ID)
Checks that the next instruction in the InstructionDataList matches the next instruction in the modul...
Definition: IROutliner.cpp:2340
findCostForOutputBlocks
static InstructionCost findCostForOutputBlocks(Module &M, OutlinableGroup &CurrentGroup, TargetTransformInfo &TTI)
Find the extra instructions needed to handle any output values for the region.
Definition: IROutliner.cpp:2549
llvm::CodeExtractor
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
llvm::updateLoopMetadataDebugLocations
void updateLoopMetadataDebugLocations(Instruction &I, function_ref< Metadata *(Metadata *)> Updater)
Update the debug locations contained within the MD_loop metadata attached to the instruction I,...
Definition: DebugInfo.cpp:373
llvm::OutlinableRegion::IgnoreRegion
bool IgnoreRegion
Flag for whether we should not consider this region for extraction.
Definition: IROutliner.h:133
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
OutlinableGroup::IgnoreGroup
bool IgnoreGroup
Flag for whether we should not consider this group of OutlinableRegions for extraction.
Definition: IROutliner.cpp:87
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
NoCostModel
static cl::opt< bool > NoCostModel("ir-outlining-no-cost", cl::init(false), cl::ReallyHidden, cl::desc("Debug option to outline greedily, without restriction that " "calculated benefit outweighs cost"))
getSubprogramOrNull
static DISubprogram * getSubprogramOrNull(OutlinableGroup &Group)
Get the subprogram if it exists for one of the outlined regions.
Definition: IROutliner.cpp:622
Attributes.h
replaceArgumentUses
static void replaceArgumentUses(OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, const DenseMap< Value *, Value * > &OutputMappings, bool FirstFunction=false)
Definition: IROutliner.cpp:1801
llvm::Function::addParamAttr
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
Definition: Function.cpp:566
replaceConstants
void replaceConstants(OutlinableRegion &Region)
Within an extracted function, replace the constants that need to be lifted into arguments with the ac...
Definition: IROutliner.cpp:1936
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::GlobalValue::hasLinkOnceODRLinkage
bool hasLinkOnceODRLinkage() const
Definition: GlobalValue.h:508
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:146
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1752
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::Function::getArg
Argument * getArg(unsigned i) const
Definition: Function.h:759
llvm::Function::back
const BasicBlock & back() const
Definition: Function.h:735
llvm::OutlinableRegion
The OutlinableRegion holds all the information for a specific region, or sequence of instructions.
Definition: IROutliner.h:63
IRSimilarityIdentifier.h
llvm::IRSimilarity::IRSimilarityCandidate::getStartIdx
unsigned getStartIdx() const
Definition: IRSimilarityIdentifier.h:864
PassManager.h
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::object::Identifier
@ Identifier
Definition: COFFModuleDefinition.cpp:34
llvm::Function::getFunctionType
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:175
llvm::TargetTransformInfo::getMemoryOpCost
InstructionCost getMemoryOpCost(unsigned Opcode, Type *Src, Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueInfo OpdInfo={OK_AnyValue, OP_None}, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:921
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:596
llvm::IRSimilarity::IRSimilarityCandidate
This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...
Definition: IRSimilarityIdentifier.h:648
llvm::CodeExtractorAnalysisCache
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
getCodeExtractorArguments
static void getCodeExtractorArguments(OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, DenseSet< unsigned > &NotSame, DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &ArgInputs, SetVector< Value * > &Outputs)
Find the input GVNs and the output values for a region of Instructions.
Definition: IROutliner.cpp:863
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:222
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:373
fillOverallFunction
static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup, std::vector< DenseMap< Value *, BasicBlock * >> &OutputStoreBBs, std::vector< Function * > &FuncsToRemove, const DenseMap< Value *, Value * > &OutputMappings)
Fill the new function that will serve as the replacement function for all of the extracted regions of...
Definition: IROutliner.cpp:2246
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:690
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
Dominators.h
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
OutlinableGroup::SwiftErrorArgument
Optional< unsigned > SwiftErrorArgument
The argument that needs to be marked with the swifterr attribute.
Definition: IROutliner.cpp:136
llvm::BasicBlock::size
size_t size() const
Definition: BasicBlock.h:316
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:85
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
TargetTransformInfo.h
llvm::Function::addFnAttr
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.cpp:538
ArgLocWithBBCanon
std::pair< unsigned, unsigned > ArgLocWithBBCanon
Definition: IROutliner.cpp:1141
llvm::PHINode
Definition: Instructions.h:2699
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::Optional::value
constexpr const T & value() const &
Definition: Optional.h:313
llvm::detail::DenseSetImpl::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1803
moveFunctionData
static void moveFunctionData(Function &Old, Function &New, DenseMap< Value *, BasicBlock * > &NewEnds)
Move each BasicBlock in Old to New.
Definition: IROutliner.cpp:709
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::StringRef::str
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:221
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
llvm::IROutliner
This class is a pass that identifies similarity in a Module, extracts instances of the similarity,...
Definition: IROutliner.h:199
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::IRSimilarity::IRSimilarityIdentifier
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Definition: IRSimilarityIdentifier.h:978
llvm::Value::replaceUsesWithIf
void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
Definition: Value.cpp:540
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::simple_ilist::insert
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:157
llvm::TargetTransformInfo::TCC_Basic
@ TCC_Basic
The cost of a typical 'add' instruction.
Definition: TargetTransformInfo.h:244
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3278
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4428
llvm::cl::desc
Definition: CommandLine.h:412
llvm::Region
Definition: RegionInfo.h:889
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
PHINodeData
std::pair< ArgLocWithBBCanon, CanonList > PHINodeData
Definition: IROutliner.cpp:1146
llvm::SetVector< Value * >
OutlinableGroup::PHINodeGVNToGVNs
DenseMap< unsigned, std::pair< std::pair< unsigned, unsigned >, SmallVector< unsigned, 2 > > > PHINodeGVNToGVNs
Definition: IROutliner.cpp:124
encodePHINodeData
static hash_code encodePHINodeData(PHINodeData &PND)
Encode PND as an integer for easy lookup based on the argument location, the parent BasicBlock canoni...
Definition: IROutliner.cpp:1154
llvm::OutlinableRegion::RemappedArguments
DenseMap< Value *, Value * > RemappedArguments
Values in the outlined functions will often be replaced by arguments.
Definition: IROutliner.h:93
CU
Definition: AArch64AsmBackend.cpp:504
OutlinableGroup::BranchesToOutside
unsigned BranchesToOutside
The number of branches in the region target a basic block that is outside of the region.
Definition: IROutliner.cpp:115
llvm::Optional::value_or
constexpr T value_or(U &&alt) const &
Definition: Optional.h:334
InitializePasses.h
iroutliner
iroutliner
Definition: IROutliner.cpp:3084
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::DominatorTreeBase::deleteEdge
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
Definition: GenericDomTree.h:602
llvm::OutlinableRegion::Candidate
IRSimilarityCandidate * Candidate
Describes the region of code.
Definition: IROutliner.h:65
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3227
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1247
llvm::DIFile
File.
Definition: DebugInfoMetadata.h:525
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
createSwitchStatement
void createSwitchStatement(Module &M, OutlinableGroup &OG, DenseMap< Value *, BasicBlock * > &EndBBs, std::vector< DenseMap< Value *, BasicBlock * >> &OutputStoreBBs)
Create the switch statement for outlined function to differentiate between all the output blocks.
Definition: IROutliner.cpp:2153
llvm::Function::size
size_t size() const
Definition: Function.h:731
llvm::RegionBase::getParent
RegionT * getParent() const
Get the parent of the Region.
Definition: RegionInfo.h:364
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
Outliner
IR Outliner
Definition: IROutliner.cpp:3084
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73