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