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